Thank you for your answer. What is nonces ?
I need them for tests and I need know nonces...
Br
Pubkey = 02ceb6cbbcdbdf5ef7150682150f4ce2c6f4807b349827dcdbdd1f2efa885a2630
puzzle #120
---
k1 = 0x00000000000000000000000000000000025d46d0bccbc08eafa03912b3f2c206
r1 = 0x890895144c4a40cd18126d1ce6534e03ab909c8c3692f1cc108fec8e2e4dea97
s1 = 0x51bc4ff0a414d66113e354a7070f47eba8ab76035e776ed2123c7d5ee991b800
z1 = 0xf11d940943f16b4117aea030d0b0cf7f6781e99f2babe05daa574a10b072bc44
k2 = 0x00000000000000000000000000000000029c9ececdceab18cfba91146e5ded7e
r2 = 0x2e772d6ea8cd5dc0b4f06a5f4e5ea057cb65b27a820acb0df711e2855052193f
s2 = 0x83e65d972d090e8d975e5ed99f55c9bbc20fcf692344cf847f3639f4ff026d63
z2 = 0x625ed03aa7e42bb1f65e5546861807a0a52fc52cb20a6b4bdc32b2028e70904b
k3 = 0x000000000000000000000000000000000141bf2eb7b3d7b7b5bbf78d4f28bcda
r3 = 0xb32f2f28d07cd0a9cc139905e1875379b9349fd21ccb838e380215afa5f26eac
s3 = 0x15d30ec6841a4e59bbb87bfc11ebf7cab78b5eb2e5ce742ebe7d07a060ebfc5b
z3 = 0x3677c07287e8742faf74b964476405f1f153466b26234b3461b268ee00676ce8
121 bit : 3 r,s,z use LLL_nonce_leakage.py , you can found private key about 1~2 second
Thank you !!!!
But, no logic with so big nonce, can you generate rsz with nonce 2**30 or less for ex to ,120 puzz pubkey ?
('K(pubkey)', (7629256135660504971600927553074108133507503631055291753784190722374696861083 : 25194535474527288837776266966493444390702606185675650052918194213452675896875 : 1)):
('BP', (114224221225710244008833485319885360327960624386540578738397512880450404677861 : 72429032990058375812461306873221236352211543024398501719746160220160202723318 : 1))
sys:1: DeprecationWarning: use the method .hex instead
See
https://trac.sagemath.org/26756 for details.
('BP*i', (94396044595232036512156845067099144740980476962933515336874287249977680693713 : 103748817412717866899495297471464484401437733019173646860487930588615334617081 : 1))
stride', 61982023939864607551350919997648825866663898650636854501024779331813868694167, 'hex r', '890895144c4a40cd18126d1ce6534e03ab909c8c3692f1cc108fec8e2e4dea97', 'r %n:', '890895144c4a40cd18126d1ce6534e03ab909c8c3692f1cc108fec8e2e4dea97')
('start range', 109059656781699855293660303596617595953680596646633396165073266196958837652548)
yes!!!
('Found real k:', 3142775905973132413425035830673719814, 'i', 'i%n', 3142775905973132413425035830673719814, 'hex i%n', '25d46d0bccbc08eafa03912b3f2c206')
('i / stride', 108201930346108686079071460207770997208299616649283473366433152632256227467196)
@cobras can you please provide the link to the code you used to get this ?
import random
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
E = EllipticCurve(GF(p), [0, 7])
G = E.point( (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)) # Base point
r=0x00fc5e2ab560be4649b85511940daf8302cf2e2e06bfd60a75c8bae5f832da289c
s=0x45c4c9d548699bbc5f3484a2d6d59ac07ea3328a1deb6b2bb9f2f8f0727be1de
z=0x6559f4e4b8d7824a641418b992f913411a1995fa35668c8c634b5a19a93a944c
r= 115780575977492633039504758427830329241728645270042306223540962614150928364886
s= 115784413730767153834193500621449522112098284939719838943229029456606672741370
z= 0#2
#r=0x00fc5e2ab560be4649b85511940daf8302cf2e2e06bfd60a75c8bae5f832da289c
#s=0x45c4c9d548699bbc5f3484a2d6d59ac07ea3328a1deb6b2bb9f2f8f0727be1de
#z=0x6559f4e4b8d7824a641418b992f913411a1995fa35668c8c634b5a19a93a944c
#r = 0x57a463b8ac30f2ed36767d5ccabf04fbe29c94b054b4309996f086556428c748
#s = 0x5a4c7e96159688e8cd2525a3230ec5184597d6cfbaf037ca5815fa01097f67cc
#z = 0xa37f38a2db651ba57f68ef4d0ac297e732d0eb3954bb85ac069569f9b372daa0
#r=91569536891656778098714370566123400538808691962301036137348069575478543413371
#s=21986343255696161951638838250895082624842596755182648655691313830200114210986
#z=6438777035962518887320975299969341061899935085590046638463194556599680845483
#r = 0x57a463b8ac30f2ed36767d5ccabf04fbe29c94b054b4309996f086556428c748
#s = 0x5a4c7e96159688e8cd2525a3230ec5184597d6cfbaf037ca5815fa01097f67cc
#z = 0xa37f38a2db651ba57f68ef4d0ac297e732d0eb3954bb85ac069569f9b372daa0
#r=91569536891656778098714370566123400538808691962301036137348069575478543413371
#s=21986343255696161951638838250895082624842596755182648655691313830200114210986
#z=6438777035962518887320975299969341061899935085590046638463194556599680845483
#k1= 5853058856940450056452093598338931896
#r=61519875576959414226926169384481904657930768090393239472847547225569960244009
#s=29672653379714264364848115664009668074279832200087452759694676488206965592960
#z=0#4050084529116149167467364769454239620376951321631508848629310185885835508238
#k2= 7445435163608072498280972003769376603
#1 (Good):
#r =17456122099107622875979177060034160065534440309384765110770021588156777535269
#s= 39548918176628970790297874101648966881380966278908886743977542233652364916621
#z=11209404430005450692776394377220775389388011163944676048947869460159787075727
#K :15903292315272842822984172996837488417
#r= 67192827200719728671013143999224641878827088629569520859649981708262221161753
#s= 21608529402161090347089631880934247809827970003164648927506043545200098952651
#z= 112249473659839884270956019532951121635444899419588574642077042903180652398468
#k1: 0x3c977dbdb3deeefcffef9fda93cdfeacfb83a8a9a6439585bb37f052a16f314
#r = 0x2c0a015c8976d170edc918480ee981e75c513dfea11086ddc89baadfd9038a29
#s = 0xf06ac541347ff93f4269579d9ca71cf7ad32859b83596721798b370ec9100749
#z= 0x37c7de2760ab892174e6680d621e72eb60b4b7cde365164ee00fee7f3a3e83dd
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
def make_public(r,s,z):
R = E.lift_x(Integer(r))
w = int(modinv(s, n))
u1 = int((z * w) % n)
u2 = int((r * w) % n)
#R=u1*G + u2*public_key
#pub= R*modinv(u2,n) - u1*modinv(u2,n)%n
u_n2=modinv(u2,n)%n
u_n1=- u1*modinv(u2,n)%n
pub=u_n1*G + u_n2*R
pub2=u_n1*G + u_n2*(-R)
return pub,pub2
def verify(r, s,z,public_key):
w = int(modinv(s, n))
u1 = int((z * w) % n)
u2 = int((r * w) % n)
D=u1*G + u2*public_key
x,y=D.xy()
x=int(x)
if (r % n) == (x % n):
print( "signature matches")
else:
print("invalid signature")
def calc_u(r,s,z):
mod_s= modinv(s,n)%n
u1=int(mod_s*z%n)
u2=int(mod_s*r%n)
print("u1:",hex(u1) , "n-u1:",hex(n-u1))
print("u2:",hex(u2) , "n-u2:",hex(n-u2))
return u1,u2
u1 , u2 = calc_u(r,s,z)
pub1,pub2=make_public(r,s,z)
#print("public_key1",pub1)
#print("pub1_x=",hex(pub1.xy()[0]))
#print("public_key2",pub2)
#print("pub2_x=",hex(pub2.xy()[0]))
verify(r,s,z,pub1)
verify(r,s,z,pub2)
print()
i = 0# 0x3c977dbdb3deeefcffef9fda93cdfeacfb83a8a9a6439585bb37f052a16f314 - 100# 15903292315272842822984172996837488410##+ 7445435163608072498280972003769376600 #=z !!!
u_matches = []
while True:#i <= 0x3c977dbdb3deeefcffef9fda93cdfeacfb83a8a9a6439585bb37f052a16f314:
k = i%n #(z+i )#%n # * modinv(s, n) % n #start range
# print("k",k)
R = E.lift_x(Integer(r))
K = (k * ( modinv(s, n) * G *r)) - z*G
Zz = z * ( modinv(s, n) * G)
K =K + Zz
#( modinv(s, n) * G) - base point
u1 = (modinv(s, n) * z) % n
u2 = (modinv(s, n) * r) % n
BP = E.point(modinv(s, n) * G *r)
#if k <=5853058856940450056452093598338931896:print("$$$",k,i)
if K == E.point( ((u1 * G + u2 * R) -z*G )): # () - pubkey
print("&",k)
print("PUBKEY", (u1 * G + u2 * R) - z *G)
print("K(pubkey)",K )
print("BP", BP)
print("BP x", hex(72742032162118480585933344979617114227426107059606997208268050083726572592328))
print("BP y", hex( 35252511027654091311316081050016893461309059670017896859124791030125997564641 ) )
print("BP*i",E.point( BP * (i %n) ))
print("BP * I X", hex(25962615284857788650433366285141778689269351625425698801309571789856719536146) )
print("BP * I Y", hex( 89356828949915730784371396370143898384661978637077061268606979053842025622546 ) )
print("stride",r,"hex r",hex(r),"r %n:",hex(r %n))
print("start range",z)
print("yes!!!")
print("Found real k:", k,"i","i%n",i%n,"hex i%n",hex(i%n) )
print("i / stride", i%n * modinv(r,n)%n )
#print(modinv(s,n)%z+r)
#print(modinv(s,n)//z+r)
break
i =i + 1 %n
i = 0
while True:
k = (r * i + z) * modinv(s, n) % n
#print("Invalid nonce K:", hex(k))
if k == u1:
print("Match found for u1 at i =", i)
u_matches.append(("u1", i))
if k == u2:
print("Match found for u2 at i =", i)
u_matches.append(("u2", i))
if k == (n - u1):
print("Match found for n - u1 at i =", i)
u_matches.append(("n - u1", i))
if k == (n - u2):
print("Match found for n - u2 at i =", i)
u_matches.append(("n - u2", i))
if k <=2**100:
print("!!!",k,i)
break
if len(u_matches) >= 1:
print("Matches found for u values:", u_matches)
break # Break the loop if matches for all u values are found
i += 1
with s = 1, work too
r= 115780575977492633039504758427830329241728645270042306223540962614150928364886
s= 1
z= 0#2
Found real k: 6 i i%n 6 hex i%n 0x6
