We are not able to reach him after this message, he also deleted his Github and Telegram. Let me try to explain, it is not hard and very known discrete logarithm problem in ECC that he stuck. I am also working on this code block more than 2 years. This code block is a bit buggy version actually for example in for loop, the end case is set as G, but it is not adding +1 so when this code block identifies the private key this assertion will always fail "assert PK == PKV".
Anyway, ECC is build on "Double and Add" in behind, and the reverse algorithm idea is "Subtract and Halve". Let's say you have a private key 11, which is "1011" in bit level. How elliptic curve generates public key from this bit is:
Initial = 0G
For 1, algorithm is Double and Add
For 0, just Double
1 -> Double and Add -> 0G * 2 + G = G
0 -> Just Double -> G * 2 = 2G
1 -> Double and Add -> 2G * 2 + G = 5G
1 -> Double and Add -> 5G * 2 + G = 11G
This is how Elliptic Curve generates your public key from the private key. So, what this guy was saying is, it can be reversible by "Subtract and Halve" then. How it will be:
You have the Curve order, which is 115792089237316195423570985008687907852837564279074904382605163141518161494337 for SECP256k1.
And the when you apply modular inverse for "2", it will give 57896044618658097711785492504343953926418782139537452191302581570759080747169, which means if you multiply a point by this number, it will give you the Halved point. So Elliptic Curve is using "Scalar Multiplication" while "Double and Add", and you can use this number for "Scalar Division" while "Subtract and Halve".
How "Subtract and Halve" will be applied, you must know if the Point is "Odd" or "Even". To understand this, let's deep dive. For example in our case the point is 11G, when you halve it, it will give you 5.5G. How elliptic curve handles this fractional number is, it is doing this:
5G + (Half Order G, which is 57896044618658097711785492504343953926418782139537452191302581570759080747169G). So when you halve the point, if it is Odd, the point will go to the left side of the curve, which means after the half point, greater than the half point. If it is even, the result will be just 5G, which will be on the right side of the curve, which means before the half point, lower than the half point. The stuck point is here. We as a team, tried several ways to understand the behavior of a point, how a point behave when it is on left side or right side. However, even our trained AI which we trained with Quadrillions of Points data not clearly identified the point position. However, if you are able to manage this, there won't be any discrete logarithmic problem in Elliptic Curve, which means you will be able to extract the Private Key from any Public Key.
How it will be?
You have X G, you do not know it is 11:
X G -> Halve -> 5.5G -> So the 5.5G point will be on the left side of the curve (assume you managed to identify this) -> Go back to initial point and just apply Subtract and Halve.
11G -> Subtract and Halve -> (11G - G) / 2 -> 5G -> Save the bit as "1" because the operation is "Subtract and Halve"
Now apply the same for 5G, it is also Odd, and when you halve it, you will get 2.5 G, so you must apply again Subtract and Halve:
5G -> Subtract and Halve -> (5G - G) / 2 -> 2G -> Save the bit as "1" because the operation is "Subtract and Halve"
Now apply the same for 2G point, now this is Even point is on right side of the curve, so you should apply just "Halve"
2G -> Halve -> 2G / 2 -> G -> Save the bit as "0" because the operation is "Just Halve"
So in the and you have just "G", where this code will stop here "if NEXT == get_first_point(): break" This part of code is wrong. It must stop on Infinity, which means "0G", not on G (the first point).
So let me give you first the fixed parts of code:
def get_point_infinity():
return Point(SECP256k1.curve,
None,
None)
and change here:
if NEXT == get_point_infinity():
Now this code will continue, what we had left, "G", apply the same for G, it is also Odd, and when you halve it, you will get 0.5 G, so you must apply again Subtract and Halve
G -> Subtract and Halve -> (G - G) / 2 -> INFINITY -> Save the bit as "1" because the operation is "Subtract and Halve"
and now your code will be stopped running. Lets collect all here:
11G -> Subtract and Halve -> (11G - G) / 2 -> 5G -> 1
5G -> Subtract and Halve -> (5G - G) / 2 -> 2G -> 1
2G -> Halve -> 2G / 2 -> G -> 0
G -> Subtract and Halve -> (G - G) / 2 -> INFINITY -> 1
What was our private key "1011", and look up, what you see there?