Pollard's kangaroo ECDLP solver

[zielar]

For a change, this is current progress

To recap (and to return in topic):

#115 -> 114 bit

steps needed to have 50% chance of a collision: about (114/2)+1 = 58 bit -> 2^58

DP = 25

steps performed: 2**25 * 2**33.14 = 2**58.14, then you are close to the result?

I expect a result at any time. You had to add ~ 5% tolerance limit due to inconsistency in ~ 00.05% files, so in my case from 2 ^ 33.167 gives 52%. I have already crossed 2 ^ 33.18 just so it is exactly as you wrote :-)

[1714991025]

1714991025

[1714991025]

1714991025

[1714991025]

1714991025

[zielar]

p.s. Jean_Luc insert in you code not shutdoun then something happen in yours kangaroo or BSGS, but power on "PAUSE" because of no pause I was 2 times lost result of 2-5 day's work.

LOL. Just create .bat file with start command like this:

Code:

Kangaroo.exe [...your start settings -d -gpu etc.] 

pause

and your problem go forget.

[COBRAS]

p.s. Jean_Luc insert in you code not shutdoun then something happen in yours kangaroo or BSGS, but power on "PAUSE" because of no pause I was 2 times lost result of 2-5 day's work.

LOL. Just create .bat file with start command like this:

Code:

Kangaroo.exe [...your start settings -d -gpu etc.] 

pause

and your problem go forget.

Yes, after get 2 shutdown, I understand what was happen after some day's..... already I use bat file but I can't repeat the results that were

[Etar]

Please, someone make a scrypt for automatic shifting pubkey to "zero" ? I was try many times and not found any keys I think because of this. Manualy shift all pubkeys to "zero" is f**ing work, trust me please.

i don`t know for what you need shift pub key but any way here is python code and you can launch this code online https://repl.it/languages/python3

Code:

def inverse(x, p):
    """
    Calculate the modular inverse of x ( mod p )    
    """
    inv1 = 1
    inv2 = 0
    n=1
    while p != 1 and p!=0:        
        quotient = x // p
        
        inv1, inv2 = inv2, inv1 - inv2 * quotient
        x, p = p, x % p        
        n = n+1
    
    return inv2

def dblpt(pt, p):
    """
    Calculate pt+pt = 2*pt
    """
    if pt is None:
        return None
    (x,y)= pt
    if y==0:
        return None 
    
    slope= 3*pow(x,2,p)*pow(2*y,p-2,p)
    
    
    xsum= pow(slope,2,p)-2*x 
    
    ysum= slope*(x-xsum)-y  
    
    return (xsum%p, ysum%p)

def addpt(p1,p2, p):
    """
    Calculate p1+p2
    """
    if p1 is None or p2 is None:
        return None
    (x1,y1)= p1
    (x2,y2)= p2
    if x1==x2:
        return dblpt(p1, p)
        
    # calculate (y1-y2)/(x1-x2)  modulus p
    
    slope=(y1-y2)*pow(x1-x2,p-2,p)
    
    
    xsum= pow(slope,2,p)-(x1+x2)
   
    ysum= slope*(x1-xsum)-y1
    
    
    return (xsum%p, ysum%p)

def ptmul(pt,a, p):
    """
    Calculate pt*a
    """
    scale= pt    
    acc=None
   
    
    while a:
        
        if a&1:
            if acc is None:
                acc= scale 
                
            else:     
                acc= addpt(acc,scale, p)                
               
        scale= dblpt(scale, p)
        a >>= 1
        
            
   
    return acc

def ptdiv(pt,a,p,n):  
    """
    Calculate pt/a
    """
    divpt=inverse(a, n)%n
    return ptmul(pt, divpt, p)


def isoncurve(pt,p):
    """
    returns True when pt is on the secp256k1 curve
    """
    (x,y)= pt
    return (y**2 - x**3 - 7)%p == 0


def getuncompressedpub(compressed_key):
    """
    returns uncompressed public key
    """
    y_parity = int(compressed_key[:2]) - 2    
    x = int(compressed_key[2:], 16)
    a = (pow(x, 3, p) + 7) % p
    y = pow(a, (p+1)//4, p)    
    if y % 2 != y_parity:
        y = -y % p        
    return (x,y)



#secp256k1 constants
Gx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
p = 2**256 - 2**32 - 977
g= (Gx,Gy)

#CHANGE HERE beginrange and pointstr
beginrange=0x80000000000000000000
pointstr = '037e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc'

pt= getuncompressedpub(pointstr)
(subptx,subpty) = ptmul(g, beginrange, p)
result=addpt(pt, (subptx,p-subpty), p)
print("shifted result> 04%064x%064x"%result)

Code have all functions that you need to work with points.
P.S. Kangaroo app automaticly shift range and pubkey if begin range is not zero.

[COBRAS]

Please, someone make a scrypt for automatic shifting pubkey to "zero" ? I was try many times and not found any keys I think because of this. Manualy shift all pubkeys to "zero" is f**ing work, trust me please.

i don`t know for what you need shift pub key but any way here is python code and you can launch this code online https://repl.it/languages/python3

Code:

def inverse(x, p):
    """
    Calculate the modular inverse of x ( mod p )    
    """
    inv1 = 1
    inv2 = 0
    n=1
    while p != 1 and p!=0:        
        quotient = x // p
        
        inv1, inv2 = inv2, inv1 - inv2 * quotient
        x, p = p, x % p        
        n = n+1
    
    return inv2

def dblpt(pt, p):
    """
    Calculate pt+pt = 2*pt
    """
    if pt is None:
        return None
    (x,y)= pt
    if y==0:
        return None 
    
    slope= 3*pow(x,2,p)*pow(2*y,p-2,p)
    
    
    xsum= pow(slope,2,p)-2*x 
    
    ysum= slope*(x-xsum)-y  
    
    return (xsum%p, ysum%p)

def addpt(p1,p2, p):
    """
    Calculate p1+p2
    """
    if p1 is None or p2 is None:
        return None
    (x1,y1)= p1
    (x2,y2)= p2
    if x1==x2:
        return dblpt(p1, p)
        
    # calculate (y1-y2)/(x1-x2)  modulus p
    
    slope=(y1-y2)*pow(x1-x2,p-2,p)
    
    
    xsum= pow(slope,2,p)-(x1+x2)
   
    ysum= slope*(x1-xsum)-y1
    
    
    return (xsum%p, ysum%p)

def ptmul(pt,a, p):
    """
    Calculate pt*a
    """
    scale= pt    
    acc=None
   
    
    while a:
        
        if a&1:
            if acc is None:
                acc= scale 
                
            else:     
                acc= addpt(acc,scale, p)                
               
        scale= dblpt(scale, p)
        a >>= 1
        
            
   
    return acc

def ptdiv(pt,a,p,n):  
    """
    Calculate pt/a
    """
    divpt=inverse(a, n)%n
    return ptmul(pt, divpt, p)


def isoncurve(pt,p):
    """
    returns True when pt is on the secp256k1 curve
    """
    (x,y)= pt
    return (y**2 - x**3 - 7)%p == 0


def getuncompressedpub(compressed_key):
    """
    returns uncompressed public key
    """
    y_parity = int(compressed_key[:2]) - 2    
    x = int(compressed_key[2:], 16)
    a = (pow(x, 3, p) + 7) % p
    y = pow(a, (p+1)//4, p)    
    if y % 2 != y_parity:
        y = -y % p        
    return (x,y)



#secp256k1 constants
Gx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
p = 2**256 - 2**32 - 977
g= (Gx,Gy)

#CHANGE HERE beginrange and pointstr
beginrange=0x80000000000000000000
pointstr = '037e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc'

pt= getuncompressedpub(pointstr)
(subptx,subpty) = ptmul(g, beginrange, p)
result=addpt(pt, (subptx,p-subpty), p)
print("shifted result> 04%064x%064x"%result)

Code have all functions that you need to work with points.

Than you for your help Etar.

I think with shifter ranges difficult of calculus will be not 2^256 but in ex. 2^256-2^200 for 56 bytes key.

And if no key in 56 range need go next, but, if no key  in 256 range this will be understand only after 256 Byts calculus VS 56 bytes.

Buddy, code what you give, is shifted pubkey to zero, or not ? I think sghift key to zero mean what from pubkey deducted a range, or I mistaken in this ?

 

[Etar]

Buddy, code what you give, is shifted pubkey to zero, or not ? I think sghift key to zero mean what from pubkey deducted a range, or I mistaken in this ?  

I write p.s. above that Kangaroo app automaticly shift range and pubkey if begin range is not zero. You not need to do this manualy.
Ofcourse if you want you can do this manualy. Shift range and pubkey mean substract beginrange from range and from pubkey.
And do not use shifting method that i proposed above, he is not working at 100%

[COBRAS]

Becouse above code not exact work. Please, someone make a scrypt for automatic shifting pubkey to "zero" ?

[Etar]

Becouse above code not exact work. Please, someone make a scrypt for automatic shifting pubkey to "zero" ?

python code worked like sharm..

@Jeanluc can you explaine this, please.

[COBRAS]

Becouse above code not exact work. Please, someone make a scrypt for automatic shifting pubkey to "zero" ?

python code worked like sharm..

@Jeanluc can you explaine this, please.

Cool. So not need enother code.

What you think about deduct G from PubKey many times ? Because of no ":" function on EC and we can't get x from pubkey with divide. I thin is idea to get pubkey ready for hack what have no G's component.

[Etar]

What you think about deduct G from PubKey many times ? Because of no ":" function on EC and we can't get x from pubkey with divide. I thin is idea to get pubkey ready for hack what have no G's component.

Look to the python code, function to devide point is called ptdiv(pt,a,p,n)
where pt is point and a is integer devider

[mrxtraf]

interesting solution, but it won’t work if only public keys are known, let's say there is a public key theoretically with private key 1, how to divide the public key by 10 to get public key with 0.1 without knowing the private keys?

You can't.

Let P be a public key with unknown private key k (that means P = k*G)
 
By definition, you can get a public key Q such that 10*Q = P in this way:

Q = inv(10)*P = inv(10)*k*G

that's all you can have (if you don't know k, you don't know inv(10)*k neither)

But it’s really possible to divide any public key into 10 without knowing the private one. But to divide by 3, 6, 7, 9, 14 .... is already more difficult.

It is the same thing. Inv(10) or inv(3), where is the difference?

Therefore, when dividing the public key Q, other methods are used and there is no inv (10). You can give a public key from which you know the private one and I will divide it by 10. And you will check using the private key.

[COBRAS]

interesting solution, but it won’t work if only public keys are known, let's say there is a public key theoretically with private key 1, how to divide the public key by 10 to get public key with 0.1 without knowing the private keys?

You can't.

Let P be a public key with unknown private key k (that means P = k*G)
 
By definition, you can get a public key Q such that 10*Q = P in this way:

Q = inv(10)*P = inv(10)*k*G

that's all you can have (if you don't know k, you don't know inv(10)*k neither)

But it’s really possible to divide any public key into 10 without knowing the private one. But to divide by 3, 6, 7, 9, 14 .... is already more difficult.

It is the same thing. Inv(10) or inv(3), where is the difference?

Therefore, when dividing the public key Q, other methods are used and there is no inv (10). You can give a public key from which you know the private one and I will divide it by 10. And you will check using the private key.

So, PrivKey from 160 bytes = privkey 80 bytes*2 ?

[mrxtraf]

interesting solution, but it won’t work if only public keys are known, let's say there is a public key theoretically with private key 1, how to divide the public key by 10 to get public key with 0.1 without knowing the private keys?

You can't.

Let P be a public key with unknown private key k (that means P = k*G)
 
By definition, you can get a public key Q such that 10*Q = P in this way:

Q = inv(10)*P = inv(10)*k*G

that's all you can have (if you don't know k, you don't know inv(10)*k neither)

But it’s really possible to divide any public key into 10 without knowing the private one. But to divide by 3, 6, 7, 9, 14 .... is already more difficult.

It is the same thing. Inv(10) or inv(3), where is the difference?

Therefore, when dividing the public key Q, other methods are used and there is no inv (10). You can give a public key from which you know the private one and I will divide it by 10. And you will check using the private key.

So, PrivKey from 160 bytes = privkey 80 bytes*2 ?

No. if simple prikey from 160 bytes = privkey 159 bytes * 2.
But what does dividing and multiplying by 2 have to dividing by 10?

[COBRAS]

I was try deduct many times Basis point from pubkey

and get this result in decimal:

Code:

55066263022277343669578718895168534326250603453777594175500187360389116729240

80461206456126903936648321769588210263641381518345730725024477625603510475367

114350281152090415002914225360680879723439364201547916387065294902806089470701

51013628197151087321576517601027944519980487992320239741969820950564947154728

81858063707046191459386939009866976545571746100767742618686877552464701474279

91885386504538144991569604282776563056639230987209343782016348535025109416865

105949401804278716591078498274389076439291177336075085569965846810479473186009

41459912523433373843361567769935953701779569108932744302847774650924271071067

92405715801833063648780028028777895808671753827946407669234064272887784157724

54418341959535059209523319322208425784424076816816028811932505061370156780655

5126047978605685512005484045416997952858866417284486515665253490591400058134

52490963540812138089050326573359765290153157657886160007707578869545978541959


32802036335507597593529078709567273036524674888099370753687496987450852461118


27863773688718935131660845784469550803460621553574213006074163405651052167161


36645545354186924026635864492819248964849682741741028893139627006539149133774

27476149675778769341425383353707820487777155825885410693677584163936411230079


54129827521380745567621263337017653354620280013802747340066967768376390656637


80638523013064036412041871548943079184689297859131619072201660923512812171502

112723772262242031666753037233989715114592529792673293658551104097788592972230

110958129610584237331452391111361457709268353430315048828827348860484327374055

50693572800016527537751387017277354813007969227988932973757409794810631509905

17856908775349033022202533859010614530493029893325487811243073805696696942498

Why if pubkey=G*x so many different result ?

What is algorithm multiply G on x ?

Does a algorithm for get Pubkey is Q=G * x * ?

[Etar]

Interesting thing...
For first experiment I took a public key 03f28773c2d975288bc7d1d205c3748651b075fbc6610e58cddeeddf8f19405aa8  pk=13
Then i made fake Tame file with DP=2 and with only one DP and very small range in DEC 0:17
Small range selected specifically to check if overlap affects.
X-coordinate was 5c778e4b8cef3ca7abac09b95c709ee5 and distance 00000000000000000000000000000002
So DP is c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
After that i make fake Wild file:
X-coordinate was 5c778e4b8cef3ca7abac09b95c709ee5 and distance 0000000000000000000000000000000B sign -
then i merge this 2 file and solve key. Ok it is correct and expected because the pub key is above "zero"


The second experiment was with almost the same key with only a minus sign 02f28773c2d975288bc7d1d205c3748651b075fbc6610e58cddeeddf8f19405aa8
That mean that pub key is under "zero" and -N/2+pub+N/2 do not overlap tame range..

Fake Tame file was almost the same i just change pub key y-coordinate in header

Fake Wild file the same was changed pub  key y-coordinate in header and change sign in distance to +
So we have Wild DP -2 and Tame DP +2
And after merge key was solved:
Range width: 2^5
Key# 0 [0S]Pub:  0x02F28773C2D975288BC7D1D205C3748651B075FBC6610E58CDDEEDDF8F19405AA8
       Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364134

Those my theory is correct and we can reduce the range by half due to symmetry.

And here is question to @JeanLuc why  app can solve this config:
80000000000000000000
ffffffffffffffffffff
0304b504a5122bfa6d4d3c7283b1c42f732f2e68ae129a8e6eea7671aeb6fe075f

but  can`t solve this:
0
3fffffffffffffffffff
023389617b48186abe570e27966546775feaff36037a932b655c10d0c6994d7bf3

Yesterday i was wait 8h when expected time was 15minutes, so i can say that this config was impossible to solve. But what reason is?

EDIT: And one more trick, if the program showed not only just dead kangaroos, but also their type.
From the number of dead wild kangaroos, one can judge indirectly that the public key is close to the beginning of the range.
Due to symmetry, negative steps will be mirrored with positives causing a greater number of dead wild kangaroos.

[mrxtraf]

Simple model. Divided at 2 key and key-1, and paralled other key.

[COBRAS]

Jean_Luc

Can you insert this function in the code ?

Code:

And one more trick, if the program showed not only just dead kangaroos, but also their type.

Please

Big thank you.

[j2002ba2]

@mrxtraf
In the private key group (mod n) we can add, negate, and invert - this allows for multiplication and division.

In the public key group (elliptic curve mod p of size n) we can add, negate, and double only. This leads to multiplication by a scalar.

One public key corresponds to exactly one private key, and vice versa. The proof is very easy. Let G is the generator of secp256k1. Let P=k*G is a point on the curve. Let also P=k'*G. Then (k-k')*G=O => (k-k') divides n. But n is prime, hence k=k' (mod n).

[mrxtraf]

@mrxtraf
In the private key group (mod n) we can add, negate, and invert - this allows for multiplication and division.

In the public key group (elliptic curve mod p of size n) we can add, negate, and double only. This leads to multiplication by a scalar.

One public key corresponds to exactly one private key, and vice versa. The proof is very easy. Let G is the generator of secp256k1. Let P=k*G is a point on the curve. Let also P=k'*G. Then (k-k')*G=O => (k-k') divides n. But n is prime, hence k=k' (mod n).

That is, you can’t divide the public key by 10?
Give me any public key from which you know the private key, I will divide it by 10. And I will give in return the result in the form of a public key. And you yourself divide the private key by 10, get the public key from it and compare.

[j2002ba2]

@mrxtraf
In the private key group (mod n) we can add, negate, and invert - this allows for multiplication and division.

In the public key group (elliptic curve mod p of size n) we can add, negate, and double only. This leads to multiplication by a scalar.

One public key corresponds to exactly one private key, and vice versa. The proof is very easy. Let G is the generator of secp256k1. Let P=k*G is a point on the curve. Let also P=k'*G. Then (k-k')*G=O => (k-k') divides n. But n is prime, hence k=k' (mod n).

That is, you can’t divide the public key by 10?
Give me any public key from which you know the private key, I will divide it by 10. And I will give in return the result in the form of a public key. And you yourself divide the private key by 10, get the public key from it and compare.

The multiplication (and division, which is multiplication with the inverse) is by scalar only. You cannot multiply two public keys without solving ECDLP first. And if you somehow can, then all coins are belong to you.