In some of Andreas Antonopoulos' talks and lectures, he explains how ECDSA works in Bitcoin. He discusses how addition and multiplication of elliptic curves work. He also states that, since there is no division, finding the private key from the public key is infeasible.
He also roughly explains the concept of the point at infinity which, in elliptic curve arithmetic, acts like the number 0.
It can easily be shown that we can accomplish subtraction and also division! Is Andreas wrong? Let's see.
Point Addition on elliptic curves can be written like this:
P + Q = R
Adding P to itself is known as point doubling:
P + P = 2P
The point at infinity has the following property:
P + 0 = P (where 0 is the point at infinity).
There exists a point -P on the curve such that:
P + (-P) = 0
Now if n is a scalar value, then:
nP = P + P + P +.... (n times)
So, if we have:
nP + (-P) + (-P) + (-P) + ... (n times), we will end up with the point at infinity. So, this means we found n. We can divide! Have we found a way to break elliptic curves? I thought so, too. But this is obviously not the case. So, I must have missed something or made the wrong assumption somewhere.
We must remember that we are dealing with very very large numbers when using cryptography. So let's try to calculate how long it would take to do a multiplication like nP with our definitions.
Let's assume my laptop can do 1000 point additions per second. How long will it take to do (2^100 - 3)P? Well, we would have to add P to itself (2^100 - 3) times! Can we do it?
2^100 = 10^(100 log 2)
This is approximately 10^30 operations. At 10^3 operations per second, I would need 10^27 seconds. A year is approximately 10^7 seconds. So, this means we would need 10^20 years!
It is clear that repeated point addition doesn't work. There must be another way. Let's try to use point doubling.
P + P = 2P
2P + 2P = 4P
4P + 4P = 8P
.
.
.
If we continue doubling like this, it becomes clear that, after 100 operations, we arrive at:
2^99P + 2^99P = 2΅100P
Now, adding (-P) three times, we arrive at (2^100 - 3)P. 103 operations!
Let's try to find a more general algorithm. Let's say we wanted to find 100P.
P + P = 2P (1)
2P + P = 3P (2)
3P + 3P = 6P (3)
6P + 6P = 12P (4)
12P + 12P = 24P (5)
24P + P = 25P (6)
25P + 25P = 50P (7)
50P + 50P = 100P (8)
The order and operation is given by the multiply-and-add algorithm (or square and multiply if doing modular exponentiation).
This fast multiplication only works when we know the scalar value. If we are only given the x point on the elliptic curve corresponding to the product, then the only way to divide is by repeated addition using (-P) until we get to the point at infinity.
So, is Andreas wong? No. But explaining why we can't divide with elliptic curve arithmetic is not that easy.
