I still don't fully understand — if a low-bit privkey public key is exposed, how could someone potentially derive the private key from it? Could someone please explain how that's possible?
BSGS or Kangaroo would be sufficiently quick attack methods to find a low-bitlength private key fast enough.
For your example PubKey you should provide more details for others, especially what bitlength the private key has.
~~~
To my knowledge there are no known HASH160() collisions so far. Mathematically they have to exist. I haven't even heard of any known RIPEMD-160 collision so far. Please use your brain before you post.
@Cricktor — With all due respect, maybe it’s better to stay out of topics like these if you clearly don’t understand how ECC actually works. You didn’t even attempt to answer the question. The user asked why a low-bit private key can be recovered — and your answer was just name-dropping “BSGS” and “Kangaroo” with zero explanation. What's the Point in answering if you cannot answer a simple question?
As for the answer to the original question:Suppose your search space is from 1G to 20G, and the target private key is 14G.
Let’s say the final hash160 of the public key is: 726d44b7af8228257c030bafe764d3c5839d5c02
This hash is derived via RIPEMD160(SHA256(pubkey)) therefore any arithmetic on it will be useless.
The only way is to try every private key:
1. 751e76e8199196d454941c45d1b3a323f1433bd6
2. 06afd46bcdfd22ef94ac122aa11f241244a37ecc
3. 7dd65592d0ab2fe0d0257d571abf032cd9db93dc
…
14. 726d44b7af8228257c030bafe764d3c5839d5c02 (match)
If you started from the beginning this would take us 14 operations, from the end 7 operations.
Thats why we say the runtime of bruteforce is O(N) where N is the number of candidates in your search so you have to do at worst N operations.
__________________
Baby step giant stepNow suppose you’re given the actual public key, like: 03499fdf9e895e719cfd64e67f07d38e3226aa7b63678949e6e49b241a60e823e4
or in affine coordinates: P(499fdf9e895e719cfd64e67f07d38e3226aa7b63678949e6e49b241a60e823e4, cac2f6c4b54e855190f044e4a7b3d464464279c27a3f95bcc65f40d403a13f5)
Because you now have an actual elliptic curve point, you can do math with it.
You precompute a table of baby steps:
map[G * 1] = 1
map[G * 2] = 2
...
map[G * 10] = 10
Now you walk backward from the target using giant steps:
Q - G * 10 → check if in map
Q - G * 20 → check again
So in our case:
1) 14G - 10G = 4G | Is 4G in the map? Yes → index = 4
Then we can calculate the real private key by doing tablesize * iterations + index, so 1*10 + 4 = 14
Again, scale this up to a babystep table of 1 billion then you can check 1 billion keys in less than a second, thats why its much much faster than bruteforce.
As for pollard kangaroo it works kinda differently, but the actual operations are much much slower simply because scalar multiplication is needed where in bsgs - you can do it with point addition.