Topic: Pollard's kangaroo ECDLP solver - page 103. (Read 59389 times)
Becouse above code not exact work. Please, someone make a scrypt for automatic shifting pubkey to "zero" ?
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%
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.
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)
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 ?
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.
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)
P.S. Kangaroo app automaticly shift range and pubkey if begin range is not zero.
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.pause
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
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. pause
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 :-)
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..
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 ?
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.
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.
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?
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)
It is the same thing. Inv(10) or inv(3), where is the difference?
Please explain what is DP?
This is like the lucky. You can choose more or less.But every day you because of the no lack of results you will begin to understand that this is something like a game that can only be played by its developer mostly and no one else. You don't know what parameters to use... you can try with a big bet like Zelar or use the free spins provided by the test servers. I think all members of this branch are 60% gamblers. Welcome to roulette.
Please explain what is DP?
how are you subtracting 80000.... from 037e.... and getting 033aeb....
edit: I guess you meant 80000...from the priv key
(7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc,65c7118f1c29cb92d28ce0dfd0dc58144fe5572effebc7fee54c4fce3333a6b2)
-
(769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be,4bf817362fe783bac8dce4cef73f5d4741a177767b7873add5920bffb0d9685f)
=
3aeb4f818ca91912a3e50d1b3db196696f82713bae00ba2b53c09a23f1d284a085b2197137256de f6c05a0f105e1b1eee9c10d23b7a4911040a23e891ebb3dc9
037e.... - (80000....*G) = 033aeb....
pubkey compressed 03769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be
pubkey uncompressed 04769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be65c7118f1c29cb92d28ce0dfd0dc58144fe5572effebc7fee54c4fce3333a6b2
how are you subtracting 80000.... from 037e.... and getting 033aeb....
edit: I guess you meant 80000...from the priv key
(7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc,65c7118f1c29cb92d28ce0dfd0dc58144fe5572effebc7fee54c4fce3333a6b2)
-
(769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be,4bf817362fe783bac8dce4cef73f5d4741a177767b7873add5920bffb0d9685f)
=
3aeb4f818ca91912a3e50d1b3db196696f82713bae00ba2b53c09a23f1d284a085b2197137256de f6c05a0f105e1b1eee9c10d23b7a4911040a23e891ebb3dc9
037e.... - (80000....*G) = 033aeb....
dec: 604462909807314587353088
pubkey: 03769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be
let me clear you more
if pubkey in 80 bit, he is doing minus 79bit, and thinking next key will be in 79 bit, but its not exact, its probability
next could be in 79 bit, or 78 bit, depand on 80 bit key location, which you all dont know, location mean 80bit start, middle, or in near last area of under 80 bit, you love to play try it again and again
btw staudy my 8 month old post and
my exact down bit proof here
https://bitcointalksearch.org/topic/m.54531996
pub - start range * G(generator point) = new pub key
in his first example
(pub)7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc - (start range) 80000000000000000000 * G = (pub) 3aeb....
real: (pub) 7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc
G = 1 or in point pubkey is 0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
hex 80000000000000000000 = pub 03769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be
now play in 2 forms
Real - G(pub)*hex =
Real - hex(pub) =
point to point minus
clear
??how are you subtracting 80000.... from 037e.... and getting 033aeb....
edit: I guess you meant 80000...from the priv key
(7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc,65c7118f1c29cb92d28ce0dfd0dc58144fe5572effebc7fee54c4fce3333a6b2)
-
(769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be,4bf817362fe783bac8dce4cef73f5d4741a177767b7873add5920bffb0d9685f)
=
3aeb4f818ca91912a3e50d1b3db196696f82713bae00ba2b53c09a23f1d284a085b2197137256de f6c05a0f105e1b1eee9c10d23b7a4911040a23e891ebb3dc9
037e.... - (80000....*G) = 033aeb....
dec: 604462909807314587353088
pubkey: 03769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be
let me clear you more
if pubkey in 80 bit, he is doing minus 79bit, and thinking next key will be in 79 bit, but its not exact, its probability
next could be in 79 bit, or 78 bit, depand on 80 bit key location, which you all dont know, location mean 80bit start, middle, or in near last area of under 80 bit, you love to play try it again and again
btw staudy my 8 month old post and
my exact down bit proof here
https://bitcointalksearch.org/topic/m.54531996
pub - start range * G(generator point) = new pub key
in his first example
(pub)7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc - (start range) 80000000000000000000 * G = (pub) 3aeb....
how are you subtracting 80000.... from 037e.... and getting 033aeb....
edit: I guess you meant 80000...from the priv key
(7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc,65c7118f1c29cb92d28ce0dfd0dc58144fe5572effebc7fee54c4fce3333a6b2)
-
(769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be,4bf817362fe783bac8dce4cef73f5d4741a177767b7873add5920bffb0d9685f)
=
3aeb4f818ca91912a3e50d1b3db196696f82713bae00ba2b53c09a23f1d284a085b2197137256de f6c05a0f105e1b1eee9c10d23b7a4911040a23e891ebb3dc9
037e.... - (80000....*G) = 033aeb....
dec: 604462909807314587353088
pubkey: 03769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be
let me clear you more
if pubkey in 80 bit, he is doing minus 79bit, and thinking next key will be in 79 bit, but its not exact, its probability
next could be in 79 bit, or 78 bit, depand on 80 bit key location, which you all dont know, location mean 80bit start, middle, or in near last area of under 80 bit, you love to play try it again and again
btw staudy my 8 month old post and
my exact down bit proof here
https://bitcointalksearch.org/topic/m.54531996
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)
how are you subtracting 80000.... from 037e.... and getting 033aeb....
edit: I guess you meant 80000...from the priv key
(7e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc,65c7118f1c29cb92d28ce0dfd0dc58144fe5572effebc7fee54c4fce3333a6b2)
-
(769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be,4bf817362fe783bac8dce4cef73f5d4741a177767b7873add5920bffb0d9685f)
=
3aeb4f818ca91912a3e50d1b3db196696f82713bae00ba2b53c09a23f1d284a085b2197137256de f6c05a0f105e1b1eee9c10d23b7a4911040a23e891ebb3dc9
037e.... - (80000....*G) = 033aeb....
dec: 604462909807314587353088
pubkey: 03769bc75842bff58edc8366ecd78f8950ee4ab2e81359d90f9921fa3d2c4561be
-snip-
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?
i think that not all points have private key, maybe i am wronginteresting 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?
For example simple 7/5 it is (3ef1f322847965ee7f8d745af562e6507568fea5316b199f7349a2717021661d,b9a20bc3783777d2681f64d92740817f95b2c169c5db92ce0bab00efb36c0d74)
i don`t know if this result have private key.. (n+7)/5 give the same result as for ex. (n+3)/5 = 0x33333333333333333333333333333332f222f8faefdb533f265d461c29a47374
but 0x33333333333333333333333333333332f222f8faefdb533f265d461c29a47374 for (n+3)/5 is correct.
becouse if 1 have the same x-coordinate as n-1 so there only 2^255 points with unique x-coordinate. So there can be around 2^255 points that not have private key.(maybe
)Another thing is that one public key can have several private keys. But this collision has not yet been proven.
Jump to: