Quote from: Cricktor on Today at 04:44:20 PM

Quote from: IlhamCung23 on Today at 03:49:39 PM

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.

Quote from: teguh54321 on Today at 04:20:32 PM

~~~

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 step

Now 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.