Elliptic curve cryptography is powerful. Calculating public key from known private key and base point can be handled easily. On the other hand, extracting private key from known public key and base point is not easy task. This is called as Elliptic Curve Discrete Logarithm Problem. Solving ECDLP requires O(k) operations in big O notation with brute force method. For instance, 256-bit private key should be selected for bitcoin.
Vlog
Objective
Basically, we would like to find k from the equation Q = k x P
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
Baby step giant step
This approach reduces complexity O(√n) where n states the order of group
Suppose that we are working on the bitcoin curve which satisfies y2 = x3 + 7 and the base point is (2, 24). Additionally, modulo would be 199 and order of group would be 211. Suppose that we have a point (14, 39) on that curve as public key.
Now, we would like to find k such that (14, 39) = k x (2, 24)
m = int(sqrt(order)) + 1
for i in range(1, m):
iP = applyDoubleAndAddMethod(x0, y0, i, a, b, mod)
for j in range(1, m):
checkpoint = applyDoubleAndAddMethod(x0, y0, j*m, a, b, mod) #jm x P
checkpoint = pointAddition(publicKey[0], publicKey[1], checkpoint[0], -checkpoint[1], a, b, mod)
if iP == checkpoint:
print("private key is ", i+j*m," mod ",order)
print("ECDLP solved in", i+m,"th step")
terminate = True
break
if terminate == True:
break
Remember that Q = k x P where P is the base point, Q is the public key value, and k is the private key. Herein, we can illustrate private key k as (jm + i).
Let’s put this linear formula instead of the private key.
Q = k x P = (jm + i) x P
Reflect base point multiplier into the parenthesis
Q = jm x P + i x P
Move (jm x P) term into the left side of the equation.
Q – jm x P = i x P
So, the following code will calculate jm x P.
checkpoint = applyDoubleAndAddMethod(x0, y0, j*m, a, b, mod) #jm x P
Remember that elliptic curve is symmetric about x-axis. That’s why, if coordinates of point P is (xp, yp), then negative point -P would be (xp, -yp).
Q + jm x (-P) = i x P
Besides, we can calculate Q + jm x (-P) as coded below. I just set negative of y coordinate (-checkpoint[1]).
checkpoint = pointAddition(publicKey[0], publicKey[1], checkpoint[0], -checkpoint[1], a, b, mod)
Now, all we need is to check this checkpoint is equal to i x P. We’ve already calculated i x P in previous steps.
iP = applyDoubleAndAddMethod(x0, y0, i, a, b, mod)
Attacking
So, private key can be found in 27th operation in baby step giant step approach. On the other hand, it can be found in 177th operation if brute force is applied. This approach runs 6 times faster the brute force method even on very small numbers. It would reduce the complexity dramatically for very large private keys.
Even though, this approach reduces the complexity dramatically, elliptic curve cryptography is still too powerful and elliptic curve discrete logarithm problem is still hard. For instance, the following values are order of group and its square root of bitcoin protocol.
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337 (256 bit)
√n = 340282366920938463463374607431768211455
So, Square root of order is greater than 1038. Suppose that you can check a possibility in microseconds (10-6). Then, finding private key lasts more than years 1024 based on the following calculation.
(1038.10-6)/(60 . 60 . 24 .365) > 1024
Funnily, age of the universe is 109 years. You can imagine that why elliptic curve crypto systems are powerful. This is because of that there is no sub-exponential solution for ECDLP yet! Besides, ECDLP seems much more difficult than the traditional DLP which empowers RSA and Diffie Hellman. Select a 256-bit random private key and leave the rest to ECC!
Code of this tutorial is pushed into my GitHub profile. You can test it by yourself if you clone the repository. Also, I captured this post a video.
So, this answers why you should trust blockchain!
Like this blog? Support me on Patreon
