<<  >> (p.95)
    Author Topic: Pollard's kangaroo ECDLP solver  (Read 62449 times)
    WanderingPhilospher
    Sr. Member
    ****
    Offline Offline

    Activity: 1400
    Merit: 271

    Shooters Shoot...


    View Profile
    June 23, 2021, 11:26:31 PM
     #1881

    The problem is if you were to shift #120 down to 2^70 range, that means you'd have to check 2^50 targets (120 - 70 = 50); which obviously makes it impossible to check that many targets.  How did you come up with 2 million targets?

    I thought you could choose any number of targets to check, at the expense of the likelihood of you finding a match when searching for less targets.
    No. If you are shifting a pubkey down, you can either subtract or divide.  Simple explanation (for those who have asked as well):

    Subtraction only gets you so far, if you know what range the key is in, it can help you speed things up by dropping down a few ranges.  
    Let's say our key is:
    CF36F0

    If I know the key lies in the 2^24 range of 800000:FFFFFF, then I know I can be safe and at least subtract 800000. Now the range shifts to 0:7FFFFF
    Well let's say I know it is somewhere in the C00000:FFFFFF range. I can safely subtract C00000. Now the range shifts to 0:3FFFFF
    But let's say I don't know where the key is but I am 80% sure it starts with a D. So I subtract D00000.  Well, now the key is back around the wheel in no man's land because it won't lie between 0:2FFFFF. D00000-CF36F0 = some negative key.

    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.


    to be clear to me you are saying divide the uncompressed public key (converted to decimal)  by 2 to the power of the number of steps down or can you use the compressed key converted to decimal divided by 1024 if 10 steps then the amount back to hex as the new public key for the lower keyspace?
    No, it's not regular division, it's a lot of mod p this mod p that.
    But when done, you must use uncompressed because you use the x and y coord.

    Brainless may be able to explain it better. He may have some tips or tricks as well. 
Page 94
Viewing Page: 95