Post
Topic
Board Development & Technical Discussion
Re: Pollard's kangaroo ECDLP solver
by
a.a
on 27/09/2021, 18:06:16 UTC
This makes actually no sense, because the underlying principle is different.

example:

Puzzle 11
https://privatekeys.pw/key/0000000000000000000000000000000000000000000000000000000000000483

038b05b0603abd75b0c57489e451f811e1afe54a8715045cdf4888333f3ebc6e8b

halving the bitocins:
03dcaaaaea9e3b34b36c5e029abaf3028b39124ba8b90b0b7480256e10630052f2
02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d

03dcaaaaea9e3b34b36c5e029abaf3028b39124ba8b90b0b7480256e10630052f2 is the result, when the privatekey of puzzle 11 is even and
02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d if the the privatekey of puzzle 11 is odd.

02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d is the correct one, as the privatekey of puzzle 11 is odd  
02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d is https://privatekeys.pw/key/0000000000000000000000000000000000000000000000000000000000000241

So if you do 02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d + 02c2ee47ca8e17112fa255a52021ffd30b6d7a3b7e2341526c559b60a9c768013d, you get 038b05b0603abd75b0c57489e451f811e1afe54a8715045cdf4888333f3ebc6e8b (untested, maybe needs also adding the Generatorpoint)

So what is 03dcaaaaea9e3b34b36c5e029abaf3028b39124ba8b90b0b7480256e10630052f2 then? It is 241.5.
241.5 + 241.5 = 483

So, where do we find 241.5?

https://privatekeys.pw/key/7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b1e5f

How did I find it? key middle range minus halve: 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0 - 0x241 => tada

So from complexity of 11 bits, i just needed to check 10 bits now.

If I divide by 32, I actually do what?

2 * 2 * 2 * 2 * 2 = 32

So we are halving the public key 5 times. This means, that when we do this on key 11, we get 32 keys, from where one of them has the correct endsequence of the private key. So we have to check all keys if they are in the range of 2^6. If we get one, than we know how the first 6 bits of the privatekey are. We can from here determine the last 5 bits easily. I am not interested in the other ranges, as i have now a total valid privatekey