Pollard's kangaroo ECDLP solver

[BorisTheHorist]

I found a method to find any private key within 2^255 bit space. Is that new?

Tell us if you've already decided to brag  

Upd. Better yet, just prove it. I generated a random key. Here is the public key for it
0337aff652dd11e2870636b0c4ce4fb324f4b0df45e70f7d8c77d15fcc9ae73525

I would have to know the key for 0237aff652dd11e2870636b0c4ce4fb324f4b0df45e70f7d8c77d15fcc9ae73525 as it would we below ~2^255 if 0337aff652dd11e2870636b0c4ce4fb324f4b0df45e70f7d8c77d15fcc9ae73525 is above.

[paniker]

I found a method to find any private key within 2^255 bit space. Is that new?

Can you tells us more about it?))

Absolutely, so it seems that the amount of valid public x-coords is exactly half the amount of private keys.
So as the theory is any key in the full range (1-115792089237316195423570985008687907852837564279074904382605163141518161494336 ~2^256) either it is less than half (57896044618658097711785492504343953926418782139537452191302581570759080747168) or has the same x coordinate as one that does (above 57896044618658097711785492504343953926418782139537452191302581570759080747169).

I have a mathematical function to find the resulting twin on either side.
I really do like the work that has been done here on the Kangaroo software so I will provide my python function for reference of finding said twin so long as you know 1 of 2 private keys you will know both.

~2^255 is still a very large number.
In the case of uncompressed keys you still have to compute the y coord after but it is trivial.
(using the bit library for python as the function is not intensive)

from bit import Key
import secrets
def twin(i, pubhex):
    max = 115792089237316195423570985008687907852837564279074904382605163141518161494336
    if len(pubhex) == 66:
        publichex = str(pubhex)[2:66]
        if i < 57896044618658097711785492504343953926418782139537452191302581570759080747169:
            twin = max - (i-1)
            if str(pubhex)[:2] == '02':
                twinprefix = '03'
                return [twin,f'{twinprefix}{publichex}']
            elif str(pubhex)[:2] == '03':
                twinprefix = '02'
                return [twin, f'{twinprefix}{publichex}']
        elif i > 57896044618658097711785492504343953926418782139537452191302581570759080747168:
            twin = 1 + (max-i)
            if str(pubhex)[:2] == '02':
                twinprefix = '03'
                return [twin,f'{twinprefix}{publichex}']
            elif str(pubhex)[:2] == '03':
                twinprefix = '02'
                return [twin,f'{twinprefix}{publichex}']
    elif len(pubhex) == 130:
        publichex = str(pubhex)[2:66]
        if i < 57896044618658097711785492504343953926418782139537452191302581570759080747169:
            twin = max - (i-1)
            return [twin,f'uncomp,{publichex}']
        elif i > 57896044618658097711785492504343953926418782139537452191302581570759080747168:
            twin = 1 + (max-i)
            return [twin, f'uncomp,{publichex}']

max = 115792089237316195423570985008687907852837564279074904382605163141518161494336
for x in range(100):
    q = secrets.randbelow(max)
    k = Key.from_int(x)
    t = twin(x,k.pub_to_hex())
    pt = t[0]
    ptpub = Key.from_int(pt).pub_to_hex()
    print(t[1],ptpub)

'''
# Or you can do this
for x in range(1000):
    x = secrets.randbelow(max)
    k = Key.from_int(x)
    t = twin(x,k.pub_to_hex())
    pt = t[0]
    ptpub = Key.from_int(pt).pub_to_hex()
    assert t[1] == ptpub
'''

'''
# for uncompressed
for x in range(100000):
    x = secrets.randbelow(max)
    k = Key.from_int(x)
    k._public_key = k._pk.public_key.format(compressed=False)
    t = twin(x,k.pub_to_hex())
    pt = Key.from_int(t[0])
    # this next line is not nessicary as we format the response without the leading '04'
    pt._public_key = pt._pk.public_key.format(compressed=False)
    ptpub = pt.pub_to_hex()
    assert t[1] == f'uncomp,{str(ptpub)[2:66]}'
'''

Hi still not understand how it works and whats doing, donot understand big numbers, not all of them

[dextronomous]

paniker this is meaning that you can change the n's

modular elliptic curve

Total of all the wallets n is the last number. n= 115792089237316195423570985008687907852837564279074904382605163141518161494337 (In Dec)

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 (In HEX)

Half way of n n//2 = 57896044618658097711785492504343953926418782139537452191302581570759080747169

57896044618658097711785492504343953926418782139537452191302581570759080747169 Lenght Bits = 255

very nice and thanks to boris.. you still here..

[BorisTheHorist]

paniker this is meaning that you can change the n's

modular elliptic curve

Total of all the wallets n is the last number. n= 115792089237316195423570985008687907852837564279074904382605163141518161494337 (In Dec)

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 (In HEX)

Half way of n n//2 = 57896044618658097711785492504343953926418782139537452191302581570759080747169

57896044618658097711785492504343953926418782139537452191302581570759080747169 Lenght Bits = 255

very nice and thanks to boris.. you still here..

yes I am still here, this was the only thing I have found so far.

[brainless]

paniker this is meaning that you can change the n's

modular elliptic curve

Total of all the wallets n is the last number. n= 115792089237316195423570985008687907852837564279074904382605163141518161494337 (In Dec)

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 (In HEX)

Half way of n n//2 = 57896044618658097711785492504343953926418782139537452191302581570759080747169

57896044618658097711785492504343953926418782139537452191302581570759080747169 Lenght Bits = 255

very nice and thanks to boris.. you still here..

yes I am still here, this was the only thing I have found so far.

Half way of n
n//2 is wrong, check in above posts, mention clearly formula for div
thankx

[dextronomous]

paniker this is meaning that you can change the n's

modular elliptic curve

Total of all the wallets n is the last number. n= 115792089237316195423570985008687907852837564279074904382605163141518161494337 (In Dec)

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 (In HEX)

Half way of n n//2 = 57896044618658097711785492504343953926418782139537452191302581570759080747169

57896044618658097711785492504343953926418782139537452191302581570759080747169 Lenght Bits = 255

very nice and thanks to boris.. you still here..

yes I am still here, this was the only thing I have found so far.

Half way of n
n//2 is wrong, check in above posts, mention clearly formula for div
thankx

do you mean the last "6" ,
115792089237316195423570985008687907852837564279074904382605163141518161494337 ?

[BorisTheHorist]

paniker this is meaning that you can change the n's

modular elliptic curve

Total of all the wallets n is the last number. n= 115792089237316195423570985008687907852837564279074904382605163141518161494337 (In Dec)

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 (In HEX)

Half way of n n//2 = 57896044618658097711785492504343953926418782139537452191302581570759080747169

57896044618658097711785492504343953926418782139537452191302581570759080747169 Lenght Bits = 255

very nice and thanks to boris.. you still here..

yes I am still here, this was the only thing I have found so far.

Half way of n
n//2 is wrong, check in above posts, mention clearly formula for div
thankx

do you mean the last "6" ,
115792089237316195423570985008687907852837564279074904382605163141518161494337 ?

There seems to be some confusion here. the largest possible private key is 115792089237316195423570985008687907852837564279074904382605163141518161494336 or in hex FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140

Zero cannot be a private key therefor there are 115,792,089,237,316,195,423,570,985,008,687,907,852,837,564,279,074,904,382,605,163,141,518,161,494,336 valid private keys
It turns out there are only                                     57,896,044,618,658,097,711,785,492,504,343,953,926,418,782,139,537,452,191,302,581,570,759,080,747,168 valid public x coordinates

It really is not straight forward to grasp as it took me time though it happens at half of the largest key which is 57896044618658097711785492504343953926418782139537452191302581570759080747168 or in hex 7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0
 
you see 57.........168 and 57.........169 have both the same public x coordinate and opposite y parity (fancy word for even/odd)

removing the lead 03 or 02 It turns out that every public x coord from 1 to 57.........168 is exactly equal to the public x coord at the same spot in the sequence from 115........336 to 57.........169
finally, if you search every private key from 1 to 57,896,044,618,658,097,711,785,492,504,343,953,926,418,782,139,537,452,191,302,581,570,759,080,747,168 (exactly half the normal range) for a public x coord (the majority of a compressed public key) you would find it whether or not the original private key was larger or smaller than 57.........169 however a leading 03 would be 02 and vice versa therefor the limitation doesn't apply to the resulting addresses. In a sense the only thing we care about a private key with this equation is the position of the xcoord's "foundkey" 1 + (115........336-foundkey) or 115........336 - (foundkey-1) depending on which side of 57.........168.5 the foundkey is as we can infer the other and deduce the private key.

In other words this would cut the time of brute forcing any public key in half provided you are searching the full range of 1 to 115........336.
57.........168 is still a lot of private keys so bitcoin is not exactly broken.....yet.

[BorisTheHorist]

paniker this is meaning that you can change the n's

modular elliptic curve

Total of all the wallets n is the last number. n= 115792089237316195423570985008687907852837564279074904382605163141518161494337 (In Dec)

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 (In HEX)

Half way of n n//2 = 57896044618658097711785492504343953926418782139537452191302581570759080747169

57896044618658097711785492504343953926418782139537452191302581570759080747169 Lenght Bits = 255

very nice and thanks to boris.. you still here..

yes I am still here, this was the only thing I have found so far.

Half way of n
n//2 is wrong, check in above posts, mention clearly formula for div
thankx

do you mean the last "6" ,
115792089237316195423570985008687907852837564279074904382605163141518161494337 ?

There seems to be some confusion here. the largest possible private key is 115792089237316195423570985008687907852837564279074904382605163141518161494336 or in hex FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140

Zero cannot be a private key therefor there are 115,792,089,237,316,195,423,570,985,008,687,907,852,837,564,279,074,904,382,605,163,141,518,161,494,336 valid private keys
It turns out there are only                                     57,896,044,618,658,097,711,785,492,504,343,953,926,418,782,139,537,452,191,302,581,570,759,080,747,168 valid public x coordinates

It really is not straight forward to grasp as it took me time though it happens at half of the largest key which is 57896044618658097711785492504343953926418782139537452191302581570759080747168 or in hex 7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0
 
you see 57.........168 and 57.........169 have both the same public x coordinate and opposite y parity (fancy word for even/odd)

removing the lead 03 or 02 It turns out that every public x coord from 1 to 57.........168 is exactly equal to the public x coord at the same spot in the sequence from 115........336 to 57.........169
finally, if you search every private key from 1 to 57,896,044,618,658,097,711,785,492,504,343,953,926,418,782,139,537,452,191,302,581,570,759,080,747,168 (exactly half the normal range) for a public x coord (the majority of a compressed public key) you would find it whether or not the original private key was larger or smaller than 57.........169 however a leading 03 would be 02 and vice versa therefor the limitation doesn't apply to the resulting addresses. In a sense the only thing we care about a private key with this equation is the position of the xcoord's "foundkey" 1 + (115........336-foundkey) or 115........336 - (foundkey-1) depending on which side of 57.........168.5 the foundkey is as we can infer the other and deduce the private key.

In other words this would cut the time of brute forcing any public key in half provided you are searching the full range of 1 to 115........336.
57.........168 is still a lot of private keys so bitcoin is not exactly broken.....yet.

Also with regards to the y value,

 What I mean when I say "it is trivial to calculate the y" value I am referencing the following information I had apparently left out, from the spec of Secp256k1
 p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1  (115792089237316195423570985008687907853269984665640564039457584007908834671663)

the aforementioned "twins" that share a public x coord also share a y coords in the manner that they are linked together as adding the two y coords together = p (115792089237316195423570985008687907853269984665640564039457584007908834671663)

therefor it can be computed as following
p - y1 = y2

deriving from my earlier code you can try it with this:
for x in range(100000):
    s1 = secrets.randbelow(max)
    k = Key.from_int(s1)
    k._public_key = k._pk.public_key.format(compressed=False)
    s2 = twin(s1,k.pub_to_hex())
    t = Key.from_int(s2[0])
    t._public_key = t._pk.public_key.format(compressed=False)
    out = bool(115792089237316195423570985008687907853269984665640564039457584007908834671663 == int(t.pub_to_hex()[66:],16)+int(k.pub_to_hex()[66:],16))
    print(out)
    if not out:
        print("Boris Is Wrong")
        break

[brainless]

paniker this is meaning that you can change the n's

modular elliptic curve

Total of all the wallets n is the last number. n= 115792089237316195423570985008687907852837564279074904382605163141518161494337 (In Dec)

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 (In HEX)

Half way of n n//2 = 57896044618658097711785492504343953926418782139537452191302581570759080747169

57896044618658097711785492504343953926418782139537452191302581570759080747169 Lenght Bits = 255

very nice and thanks to boris.. you still here..

yes I am still here, this was the only thing I have found so far.

Half way of n
n//2 is wrong, check in above posts, mention clearly formula for div
thankx

do you mean the last "6" ,
115792089237316195423570985008687907852837564279074904382605163141518161494337 ?

here is script for div for 2

import gmpy
p = 115792089237316195423570985008687907852837564279074904382605163141518161494337
c = gmpy.invert(2,p) %p
print (c)

for div 10

import gmpy
p = 115792089237316195423570985008687907852837564279074904382605163141518161494337
c = gmpy.invert(10,p) %p
print (c)

same modify for your requirements

[COBRAS]

The you div 7 to 3 you get 2.5 = int2 float 0.5

7/3= 2.5

Then you sub 1 from 7 and div to 3 you get 2.

(7-1) / 3 = 2

So fo finding good range from 1 to 3, you need get EXACT integer without  float.


But, why the I div
0xea1a5c66dcc11b5ad180 to 2**64 or 2**128 I always get some float result 0xea1a5c66dcc11b5ad180

[fxsniper]

Can I ask about script python?
Each script and program Pollard's kangaroo ECDLP all are not the same algorithms right?
How can I know the same calculated algorithms?

Compare with calculating same public key and same keyspace search

https://github.com/JeanLucPons/Kangaroo
https://github.com/Telariust/pollard-kangaroo
https://github.com/secoc/Pollard-Rho-kangaroo

or compare with both python script
https://github.com/Telariust/pollard-kangaroo/blob/master/pollard-kangaroo-multi.py
https://github.com/BirminghamUK/Math_Task/blob/master/Recovery_X3.py

I test simply by use-value tame and wild that found the key to script python and swap value to another script it is now works value tame and wild can not use other script
Maybe I test the wrong way?

[0x0TheNullBit0x0]

Hi, is there a way to find private key range from the public key, (Start and Stop range) ? Can someone point me to the right direction

[fxsniper]

it can possible to calculate rollback to know the sample tame and wild?
just idea would like to test check how far tame and wild on 120 bit

[BorisTheHorist]

Hi, is there a way to find private key range from the public key, (Start and Stop range) ? Can someone point me to the right direction

For any random private key this is not (yet?) possible, in the case of the puzzle the creator initially put an amount of btc correlating to the bit length of the corresponding key.
Like 0.64 btc to puzzle 64 (16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN)

[fxsniper]

Now kangaroo found problem same BitCrack  both range search is very large
kangaroo method still works but is stuck with a very large range of search

I do simple easy tests on both 120 bit and 160 bit (and 256) with keyspace (under 32 bit wide) nearby it is still found key
but when used with a very large rank and nowhere is key store, so kangaroo is stunned

[BorisTheHorist]

Now kangaroo found problem same BitCrack  both range search is very large
kangaroo method still works but is stuck with a very large range of search

I do simple easy tests on both 120 bit and 160 bit (and 256) with keyspace (under 32 bit wide) nearby it is still found key
but when used with a very large rank and nowhere is key store, so kangaroo is stunned

Kangaroo and BSGS are both O root n complexity
root 120 is 2^60
2^60 is 1,152,921,504,606,846,976.
Can the discrete logarithm be computed in polynomial time on a classical computer? someday, but not tomorrow.

[COBRAS]

" I got it down to 104 bits today, but with 32,000 pubkeys; better than the normal 2^16 normally required, but I can't figure out a way to shrink it down to one key... "

for 10 bit down = 1024 pubkeys
for 20 bit down = 1024*1024 = 1048576 pubkeys
for 30 bit down = 1024*1024*1024 = 1073741824 pubkeys

1048576 and 1073741824 pubkeys with each other addition and mutiplication will return you 260 pubkeys apear where 16 pubkeys sure inside 10 bit down from main pubkey
these 260 pubkeys again played for get 30 bit down for 1/720 pubkeys
now you can start to find with above tip

can you share script to do these calculations or explain a way please

Someone try making sach scrypt ? Share code pls ?

Br

[fxsniper]

Someone try making sach scrypt ? Share code pls ?

Br

What is sach scrypt ?

Did you mean search script or  scrypt hash algorithms ?

[COBRAS]

Someone try making sach scrypt ? Share code pls ?

Br

What is sach scrypt ?

Did you mean search script or  scrypt hash algorithms ?

1048576 and 1073741824 pubkeys with each other addition and mutiplication

[ruuvnat_aseid]

Someone try making sach scrypt ? Share code pls ?

Br

What is sach scrypt ?

Did you mean search script or  scrypt hash algorithms ?

They meant "such a script"