Topic: Pollard&#039;s kangaroo ECDLP solver - page 102. (Read 58630 times)

Quote from: mrxtraf on June 13, 2020, 10:42:48 AM

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

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: arulbero on June 13, 2020, 05:37:48 AM

Quote from: arulbero on June 13, 2020, 05:37:48 AM

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

member

Activity: 255

Merit: 27

Quote from: COBRAS on June 13, 2020, 10:00:02 AM

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.

Etar

sr. member

Activity: 617

Merit: 312

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.

Huh

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

COBRAS

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: Etar on June 13, 2020, 09:56:35 AM

Quote from: COBRAS on June 13, 2020, 09:43:15 AM

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.

Huh

Etar

sr. member

Activity: 617

Merit: 312

Quote from: COBRAS on June 13, 2020, 09:43:15 AM

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

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

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

Etar

sr. member

Activity: 617

Merit: 312

Quote from: COBRAS on June 13, 2020, 09:17:26 AM

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

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: Etar on June 13, 2020, 08:41:40 AM

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

sr. member

Activity: 617

Merit: 312

Quote from: zielar on June 13, 2020, 08:27:36 AM

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

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

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

zielar

full member

Activity: 281

Merit: 114

Quote from: arulbero on June 13, 2020, 05:44:01 AM

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.

zielar

full member

Activity: 281

Merit: 114

Quote from: zielar on June 12, 2020, 09:10:51 PM

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 :-)

COBRAS

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: Etar on June 13, 2020, 07:47:32 AM

Here is shematic why shifting should work.

In example above(few post ago) pub key after shifting was under "zero" and key was found.
I don`t understant why solution not find when pubkey is close to begin of range..
Any DP no matter "positive" or "negative" have the same X-coordinate, so collission should be any way..

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.

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.

Why we not deducted from pubkey (fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 - OUR RANGE) ? but OUR RANGE ONLY ?

Etar

sr. member

Activity: 617

Merit: 312

Here is shematic why shifting should work.

In example above(few post ago) pub key after shifting was under "zero" and key was found.
I don`t understant why solution not find when pubkey is close to begin of range..
Any DP no matter "positive" or "negative" have the same X-coordinate, so collission should be any way..
If for ex. Wild DP -40 and Tame DP is 40 so there must be collision.

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: zielar on June 12, 2020, 09:10:51 PM

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?

arulbero

legendary

Activity: 1932

Merit: 2077