Pollard's kangaroo ECDLP solver

[wedom]

by the way dont brain (mind) brainless but you got me man~ now before die i really want to see script which you are using to reduce number of keys  . consider it as my last wish 

Giving a ready-made script is very easy. I would hope for hints, and get to the result myself.

[1714494788]

1714494788

[1714494788]

1714494788

[1714494788]

1714494788

[1714494788]

1714494788

[WanderingPhilospher]

@WanderingPhilosopher
If you store it in a file, you can lookup the position. But is there a formula for shifting it up by knowing the position of the pubkey?

@fxsniper

Do you read? It is a memory tradeoff! If you bitshift a 256 bit key 128 bit you will have 2^128 keys to check in a range of 1-2^128. 2^128 is how many petabytes???

Please inform yourself about ECDLP. I invested last few weeks in my freetime to understand how it works and what to do.

Etar showed example:

And this pubkey is 03d01115d548e7561b15c38f004d734633687cf4419620095bc5b0f47070afe85a with privkey 0xC
To produce real privkey need multiply privkey by divisor
0xC*0x8 = 0x60
After this need add to result founded public key number (7)
Totaly privekey = 0x60 +0x7=0x67

[WanderingPhilospher]

Here is no magic, here is script to shiftdown pubkey:

Code:

import random
import math
import hashlib
import base58
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)

def compresspub(uncompressed_key):
    """
    returns uncompressed public key
    """
    (x,y)=uncompressed_key
    y_parity = y&1 
    head='02'
    if y_parity ==1:
        head='03'    
    compressed_key = head+'{:064x}'.format(x)       
    return compressed_key

def hash160(hex_str):
    sha = hashlib.sha256()
    rip = hashlib.new('ripemd160')
    sha.update(hex_str)
    rip.update( sha.digest() )    
    return rip.hexdigest()  # .hexdigest() is hex ASCII
    
def getbtcaddr(pubkeyst):
    
    hex_str = bytearray.fromhex(pubkeyst)
    # Obtain key:
    key_hash = '00' + hash160(hex_str)

    # Obtain signature:

    sha = hashlib.sha256()
    sha.update( bytearray.fromhex(key_hash) )
    checksum = sha.digest()
    sha = hashlib.sha256()
    sha.update(checksum)
    checksum = sha.hexdigest()[0:8]

    return (base58.b58encode( bytes(bytearray.fromhex(key_hash + checksum)) )).decode('utf-8')

def checkpub(realpub, temppub, id):
    localpt = ptmul(temppub, 1024, p)
    localaddpt = ptmul(g, id, p)
    respub= addpt(localpt,localaddpt, p)
    print ("respub-> ", compresspub(respub))
    
#secp256k1 constants
Gx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
p = 2**256 - 2**32 - 977
g= (Gx,Gy)


compressed_key='0234c1fd04d301be89b31c0442d3e6ac24883928b45a9340781867d4232ec2dbdf'
point=getuncompressedpub(compressed_key)

print(getbtcaddr("04%064x%064x"%point))
print(getbtcaddr(compressed_key))
divisor = 2**3
newpub=ptdiv(point,divisor,p,n)

(partGx,partGy)=ptdiv(g,divisor,p,n)
print ("1 Fraction part-> (%x,%064x)" % (partGx,partGy))

with open('pub.txt', 'w') as f:
    f.write("04%064x%064x"%newpub)
    f.write('\n')
    print ("Compressed NewPUB (",0,")-> ", compresspub(newpub),"addr",getbtcaddr(compresspub(newpub)))
    i=1
    (pointx,pointy)=(partGx,partGy)
    while i<divisor:
        (newpubtempx,newpubtempy) = addpt(newpub,(pointx,p-pointy), p)
        f.write("04%064x%064x"%(newpubtempx,newpubtempy))
        f.write('\n')
        print ("Compressed NewPUB (",i,")-> ", compresspub((newpubtempx,newpubtempy)),"addr",getbtcaddr(compresspub((newpubtempx,newpubtempy))))
        (pointx,pointy) = addpt((pointx,pointy),(partGx,partGy), p)   
        i=i+1

   

In this example i use pubkey  0234c1fd04d301be89b31c0442d3e6ac24883928b45a9340781867d4232ec2dbdf, privkey is 0x67 and upper range is 2^7
Divisor is 2^3, so new upper range is 2^7-2^3=2^4
In file pub.txt you will find all pubkeys and their number is equil to divisor.
if you try to find all this keys in range 0x1:0xf you will see that only one pubkey will be lie in range
And this pubkey is 03d01115d548e7561b15c38f004d734633687cf4419620095bc5b0f47070afe85a with privkey 0xC
To produce real privkey need multiply privkey by divisor
0xC*0x8 = 0x60
After this need add to result founded public key number (7)
Totaly privekey = 0x60 +0x7=0x67

same old stuff with different script :p

Etar said, no magic...Etar has probably lost more knowledge on curve math, programming, etc. then most of us have ever known. Super smart, and helpful.

[NotATether]

This makes actually no sense, because the underlying principle is different.
~snip
So we are halving the public key 5 times. This means, that when we do this on key 11, we get 32 keys, from where one of them has the correct endsequence of the private key. So we have to check all keys if they are in the range of 2^6. If we get one, than we know how the first 6 bits of the privatekey are. We can from here determine the last 5 bits easily. I am not interested in the other ranges, as i have now a total valid privatekey

Had a freak day today, so my brain's (no pun intended) not very attentive right now. Will need multiple drinks of jolt cola before I can go over what you did.

I recently did a little research on private key generation via /dev/urandom. More than 100 million keys were used for the test. The bit allocation was about the same = 0.5
Maybe the old versions of OpenSSL, which were probably used in the puzzle creation, had some vulnerabilities and gave some deviation?

It's possible, but also remember a) OpenSSL uses multiple entropy sources - one of which is urandom (another is the entropy it stores in a file somewhere) and 2) the real-life sample size is very small - there were at least 256 256-bit random numbers generated in the process of making the puzzle, and possibly more as several of the numbers were probably not in the appropriate range.

now talk about NotATether script,

the script he posted is doing mod inverses and it is just multiplying value until reach 5 uper bit. (no one can get 120 how can they will get 125 lolololo)

Well all I did is reverse engineer the algorithm until it completely matched the examples that brainless provided so congratulations on explaining in simple terms why the algorithm is so absurd.

now talk about brainless theory -


NotATether and brainless are misunderstanding each other brainless maybe joked that he reduced keys 720 by doing multiplication , addition and subtraction bla bla bla until 90 or 100 bit but NotATether  is insisting what he explained inside his posts is not a way & there is also no way to achieve that and perhaps he never achieved that one and just keep lying.

now what i think is brainless have to explain this to community

Code:

" 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 

720 keys means you've only reduced it by some factor between 2^109 and 2^110, how do you even begin shifting a key down that far while not making the number of group ops explode as well?

Guys fyi 1024 is not div point in ecc, posting here, divideable magic digits for ecc, these will help you to decide bitrange to divide, use these magic ecc div numbers, for pollard kanagroo or other manual div

2   447   7572   564114
3   596   9536   752152
4   631   10096   1128228
6   894   14304   1504304
8   1192   15144   2256456
12   1262   20192   3008608
16   1788   28608   4512912
24   1893   30288   6017216
32   2384   40384   9025824
48   2524   60576   18051648
64   3576   94019   
96   3786   121152   
149   4768   188038   
192   5048   282057   
298   7152   376076   

What the hell is a div point?

This is just a dump of x-points that are on the secp256k1 curve (x=5 is not on the curve IIRC). Again though, I could pick any x-point on the curve to divide by, so this dump doesn't answer the question - How is creating multiple zones supposed to shift the range down, when all it's doing is shifting it up (massively)?  

as how he claimed this one and plus dont forget he claimed before that he found the 120 key but no plan to cash it but same time he asked .75 bitcoin to provide 115 range one key to buy 3090 (WTF)

0.75BTC at the time wouldn't buy you just a 3090, it would buy you an entire fucking 8Pack OrionX (almost).

[WanderingPhilospher]

from here, my answer were no random, and exact in all 256bit range, and what is exact location, i explain about how to calc exact range, simple, bro if you mislead by my those answers and explanation, i love to say SORRY

In brainless' defense concerning this specific convo, what he says is true. The locations aren't random and you can calculate exact range in the example he gave. I went through and found each key in their respective range. Sometimes we have to remember that not everyone speaks this language or that language and that can lead to confusion...sometimes. If you go back to the convo, he does walk you through how to find exact range/location for the example he provided. No magic, no range/key shrinkage, just ranges on the curve.

[WanderingPhilospher]

The cool thing, well, neat to me; is using brainless' "math" I was able to find private keys to x,y and x,-y, or the private keys to both 03 and 02 public keys. The positive and negative Ys that belong to the same X...like I said, I have never found both so it was neat to me lol

[brainless]

Giving you all one more tip , in total numerology, only 30240 is is dividable from 1 to 10, mean 5 even 5 odd, at same time, and no floating result
i gurantee, you never see 30240 secrets
30240.0000   10.0000   3024.0000
30240.0000   9.0000   3360.0000
30240.0000   8.0000   3780.0000
30240.0000   7.0000   4320.0000
30240.0000   6.0000   5040.0000
30240.0000   5.0000   6048.0000
30240.0000   4.0000   7560.0000
30240.0000   3.0000   10080.0000
30240.0000   2.0000   15120.0000
30240.0000   1.0000   30240.0000

if you multuply 30240 to any numbers, and result could also div by 1 to 10, and in result no floating point

30240 * 777 = 23496480.0000
23496480.0000   10.0000   2349648.0000
23496480.0000   9.0000   2610720.0000
23496480.0000   8.0000   2937060.0000
23496480.0000   7.0000   3356640.0000
23496480.0000   6.0000   3916080.0000
23496480.0000   5.0000   4699296.0000
23496480.0000   4.0000   5874120.0000
23496480.0000   3.0000   7832160.0000
23496480.0000   2.0000   11748240.0000
23496480.0000   1.0000   23496480.0000

hope like in my preivios post for magic numbers, you could not understand, same hope you will not understand secrets behind this only 1 magic numberology
 

[wedom]

Giving you all one more tip , in total numerology, only 30240 is is dividable from 1 to 10, mean 5 even 5 odd, at same time, and no floating result
i gurantee, you never see 30240 secrets
30240.0000   10.0000   3024.0000
30240.0000   9.0000   3360.0000
30240.0000   8.0000   3780.0000
30240.0000   7.0000   4320.0000
30240.0000   6.0000   5040.0000
30240.0000   5.0000   6048.0000
30240.0000   4.0000   7560.0000
30240.0000   3.0000   10080.0000
30240.0000   2.0000   15120.0000
30240.0000   1.0000   30240.0000

if you multuply 30240 to any numbers, and result could also div by 1 to 10, and in result no floating point

30240 * 777 = 23496480.0000
23496480.0000   10.0000   2349648.0000
23496480.0000   9.0000   2610720.0000
23496480.0000   8.0000   2937060.0000
23496480.0000   7.0000   3356640.0000
23496480.0000   6.0000   3916080.0000
23496480.0000   5.0000   4699296.0000
23496480.0000   4.0000   5874120.0000
23496480.0000   3.0000   7832160.0000
23496480.0000   2.0000   11748240.0000
23496480.0000   1.0000   23496480.0000

hope like in my preivios post for magic numbers, you could not understand, same hope you will not understand secrets behind this only 1 magic numberology
 

Thanks for the number hint.
I hope to figure it out and solve this problem.

In the previous post, I thought the other way, that we need to find such a divisor and such a multiplier that would get the same division residuals. For example, below are the results of division and multiplication using these and other numbers:

Code:

 2281607788513008375014137388606100914
 2281607788513008375014137388605979764
 2281607788513008375014137388605858614
 2281607788513008375014137388605737464
 2281607788513008375014137388605616314
 2281607788513008375014137388605495164
 2281607788513008375014137388605374014
 2281607788513008375014137388605252864
 2281607788513008375014137388605131714
 2281607788513008375014137388605010564
 2281607788513008375014137388604889414
 2281607788513008375014137388604768264
 2281607788513008375014137388604647114
 2281607788513008375014137388604525964
 2281607788513008375014137388604404814

don't look at the specific values of the numbers, this is for an example. All that matters is that they end in one digit and the second digit alternates.

[WanderingPhilospher]

Giving you all one more tip , in total numerology, only 30240 is is dividable from 1 to 10, mean 5 even 5 odd, at same time, and no floating result
i gurantee, you never see 30240 secrets
30240.0000   10.0000   3024.0000
30240.0000   9.0000   3360.0000
30240.0000   8.0000   3780.0000
30240.0000   7.0000   4320.0000
30240.0000   6.0000   5040.0000
30240.0000   5.0000   6048.0000
30240.0000   4.0000   7560.0000
30240.0000   3.0000   10080.0000
30240.0000   2.0000   15120.0000
30240.0000   1.0000   30240.0000

if you multuply 30240 to any numbers, and result could also div by 1 to 10, and in result no floating point

30240 * 777 = 23496480.0000
23496480.0000   10.0000   2349648.0000
23496480.0000   9.0000   2610720.0000
23496480.0000   8.0000   2937060.0000
23496480.0000   7.0000   3356640.0000
23496480.0000   6.0000   3916080.0000
23496480.0000   5.0000   4699296.0000
23496480.0000   4.0000   5874120.0000
23496480.0000   3.0000   7832160.0000
23496480.0000   2.0000   11748240.0000
23496480.0000   1.0000   23496480.0000

hope like in my preivios post for magic numbers, you could not understand, same hope you will not understand secrets behind this only 1 magic numberology
 

Maybe I am misunderstanding you and what you mean, but any multiple of 2520 would have the same result...

[a.a]

What about 2520?

2520 = 2³ * 3² * 5 * 7

2520 / 10 = 252
2520 / 9 = 280
2520 / 8 = 315
2520 / 7 = 360
2520 / 6 = 420
2520 / 5 = 504
2520 / 4 = 630
2520 / 3 = 830
2520  / 2 = 1260
2520 / 1 = 2520

Only difference is, that dividing by 8 will get you a odd number. If you want that it is even when dividing by 8, then just double 2520. So 5040 is much smaller than 30240. So why is according to you only 30240 dividable from 1 to 10? If it is even relevant as 30240 is not a divisor of N-1.

References:
https://en.wikipedia.org/wiki/Highly_composite_number
https://mrob.com/pub/math/numbers-14.html#lc5040

 

[WanderingPhilospher]

What about 2520?

2520 = 2³ * 3² * 5 * 7

2520 / 10 = 252
2520 / 9 = 280
2520 / 8 = 315
2520 / 7 = 360
2520 / 6 = 420
2520 / 5 = 504
2520 / 4 = 630
2520 / 3 = 830
2520  / 2 = 1260
2520 / 1 = 2520

Only difference is, that dividing by 8 will get you a odd number. If you want that it is even when dividing by 8, then just double 2520. So 5040 is much smaller than 30240. So why is according to you only 30240 dividable from 1 to 10? If it is even relevant as 30240 is not a divisor of N-1.

References:
https://en.wikipedia.org/wiki/Highly_composite_number
https://mrob.com/pub/math/numbers-14.html#lc5040

 

Yeah I already asked about 2520; I did not see where he stated it had to be even or odd, just no float. It could be beneficial, I will have to run more tests tomorrow. But as of now, I can find any key in any range with any divisor. So I did learn something from all of this discussion. Example, if you took a 40 bit public key and divided it by 33, I could find every public key that is generated and ultimately each pub key found in any/every range will lead me back to private key of original pub key, with a click of a button.

I ran several tests with divisor of 33 and a few with a divisor of 192. Find one pubkey in any range and you have the private key of original pub key.

[a.a]

I saw that you posted before I could post. I had already invested about 20 minutes for the post and was like: "Well, it is already said, but not from everyone" and so I posted it anyway.

Also the 33 division makes sense as the distance between each point will be the mod inverse of 33 or so. Its like cutting the whole N into ranges, as mentioned before. Only problem is, that you are only getting one in the lower bruteforcable range and then can jump from that one and can determine the other 32 private keys.

And yes, you just have to multiply the privatekey times your divisor and then mod N to get the right result.

[ssxb]

What about 2520?

2520 = 2³ * 3² * 5 * 7

2520 / 10 = 252
2520 / 9 = 280
2520 / 8 = 315
2520 / 7 = 360
2520 / 6 = 420
2520 / 5 = 504
2520 / 4 = 630
2520 / 3 = 830
2520  / 2 = 1260
2520 / 1 = 2520

Only difference is, that dividing by 8 will get you a odd number. If you want that it is even when dividing by 8, then just double 2520. So 5040 is much smaller than 30240. So why is according to you only 30240 dividable from 1 to 10? If it is even relevant as 30240 is not a divisor of N-1.

References:
https://en.wikipedia.org/wiki/Highly_composite_number
https://mrob.com/pub/math/numbers-14.html#lc5040

 

Yeah I already asked about 2520; I did not see where he stated it had to be even or odd, just no float. It could be beneficial, I will have to run more tests tomorrow. But as of now, I can find any key in any range with any divisor. So I did learn something from all of this discussion. Example, if you took a 40 bit public key and divided it by 33, I could find every public key that is generated and ultimately each pub key found in any/every range will lead me back to private key of original pub key, with a click of a button.

I ran several tests with divisor of 33 and a few with a divisor of 192. Find one pubkey in any range and you have the private key of original pub key.

Find one pubkey in any range and you have the private key of original pub key

that what i said before 

[ssxb]

I saw that you posted before I could post. I had already invested about 20 minutes for the post and was like: "Well, it is already said, but not from everyone" and so I posted it anyway.

Also the 33 division makes sense as the distance between each point will be the mod inverse of 33 or so. Its like cutting the whole N into ranges, as mentioned before. Only problem is, that you are only getting one in the lower bruteforcable range and then can jump from that one and can determine the other 32 private keys.

And yes, you just have to multiply the privatekey times your divisor and then mod N to get the right result.

that what i said before   

[_Counselor]

Giving you all one more tip , in total numerology, only 30240 is is dividable from 1 to 10, mean 5 even 5 odd, at same time, and no floating result

I don't know what you mean by "numerology", but 30240 is not the only such number (some people already told about it)

if you multuply 30240 to any numbers, and result could also div by 1 to 10, and in result no floating point

If you multiply any X by any Y, that resulting number will be divisible without remainder by all factors of Y (and X). There is no secrets. That is basics. Fundamental theorem of arithmetic.

[ssxb]

i am drinking soda right now and watching screen (no red wine as i am Muslim ) 32 keys are in front of me telling me that we are relative to each other and no matter from where you will jump toward us we will be always on distance of 1 with each other. if you knows the private keys you will find these keys are lying but hell yaa man when you work blindly on public keys without knowing private keys you will know they are having relation on curve and on 1 key distance from each other. fck math is beautiful . curse you elliptic curve sorry glass slipped from my hand i need to clean the table  

[a.a]

@WP
I take a 255 bit pubkey, divide it by 33. Now I only have to search the 2^255/33 ~ 2^252  range to find the key. What a reduction.

@ssxb

Well but what is the new knowledge?

[ssxb]

@WP
I take a 255 bit pubkey, divide it by 33. Now I only have to search the 2^255/33 ~ 2^252  range to find the key. What a reduction.

@ssxb

Well but what is the new knowledge?

Well but what is the new knowledge?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

hope you get the point ~
congratulation to me today i learnt how to generate numbers in series from 1 to 32 with python. such a genius (wile-e-coyote)

now i am telling you guys dont follow me you can hardly program this. (My brainless theory)

watching wile e coyote vs bugs bunny

[a.a]

So no new knowledge 

[brainless]

30240 came from astro
360 days in year
7 day in week
12 month in year
360 x 7 x 12 = 30240
Full ver
2520
360 x 7 = 2520
For complete numerology 30240 will work
2520 will make u stuck in some part of calc