Post
Topic
Board Development & Technical Discussion
Merits 2 from 1 user
Re: Pollard's kangaroo ECDLP solver
by
_Counselor
on 24/06/2021, 09:41:38 UTC
⭐ Merited by NotATether (2)
Now, you can also divide a key.  If we know our key lies in the 2^24 range and want to drop it down to the 2^14 range, we can divide by 1024 (2^10) 2^24 - 2^10 = 2^14
But now we have 1024 pubkeys that we have to search for but 2^1000% one of those 1024 pubkeys is in the 2^14 range.

So if one wanted to drop from 2^120 down to 2^70 range, well....that's a lot of pubkeys to search for.

Subtraction is clear to me, and so is division somewhat, but why the need to search 1024 pubkeys after dividing by that number? What will all their values be set to, apart from the one pubkey which is still its original value?

Because you dont know whether the secret key is divisible without remainder by 1024. If not divisible, result will be lie somewhere on an unknown segment of elliptic curve.

Therefore, to reduce key in such a way you have to divide by 1024 not only secret key, but also key+1 key+2 ... key+1023, one of which will be divisible by 1024 and lie in the correct reduced range.