Post
Topic
Board Development & Technical Discussion
Re: Pollard's kangaroo ECDLP solver
by
hamnaz
on 16/10/2021, 06:20:18 UTC
Take the privatekey of 4. Half it, you get 2. Take the privatekey of 5 you get 2.5. 2.5 means, 2 + N/2. To get the "half" you subtract 1 and then halve it and get 2.

So if you can determine if the lowest bit is 0 or 1 you can half it properly. But there is no method to determine 0 or 1. Thats why you can theoretically halve multiple times but have to use the false keys. Like you take a big number with 2^120 bit, and can halve it and get two keys were you know one is 2^119 and one is "wrong". Use both keys and halve them. You know one is 2^118 and three are false. Take those four keys and halve them again, one is 2^117 and 7 are false.

So you get exponentially more keys each halving. Which is useful for e.g. 2^60 as you can get 2^45 with 2^15 (15 times halved, you can do more halvings if you like) potential keys to check in very few minutes. But you can not do it with 2^120 as you still get 2^105 range with 2^15 keys, which takes still a long time to crack. Doing 2^120 halvings is basically bruteforcing the key.
any c language script for halve pubkeys with input file ( pubkeys) and output file ( pubkwys) ( for linux )

example
./halve -i inputfile.txt -o output.txt


So halve -i input.txt divide by 2 = -o output.txt ?
yes