Running this on GPU will be mush faster,. Let me see if i can write a CUDA program for this.
you are suppose to fill in the rsz after each 0x
in case you need the full code i had use in sagemath.
Code:
import random
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
E = EllipticCurve(GF(p), [0, 7])
G = E.point( (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8))
r=0x
s=0x
z=0x
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")
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()
# Function to check if a point's x-coordinate matches r
def check_k(k):
P = k * G
return P.x() == r
# Iterate to find the correct k
for i in range(1, n):
k = (r * i + z) * modinv(s, n) % n
if check_k(k):
print(f"Found correct k: {k}")
private_key = (s * k - z) * modinv(r, n) % n
print(f"Private Key: {private_key}")
break
Thank you very mach for your code, mister
@krashfire
Please give me an example rsz if your code works correctly.
sample rsz
r=0x
s=0x
z=0x
And, if 2 signatures match how long, it takes to K nonce
edit
i got error,
public_key1 (37231416379298332252575862495769965965364321245932635159006725536777825338696 : 9676366176353189190669004767334277632269117223198125569199055354600699161111 : 1)
pub1_x= 0x52503c225437e35c61b9ee5ec88ea71600e7a710dbebac88b27c2d1a667ac548
public_key2 (84773528361026042599480815013664408603889872484555722313313932231857335756436 : 21504221066078790871098131651817310599861599747961732812418866800256292472755 : 1)
pub2_x= 0xbb6c1de01f36618ae05f7c183c22dfa8797e779f39537752c27e2dc045b0e694
signature matches
signature matches
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
Cell In [1], line 83
81 for i in range(Integer(1), n):
82 k = (r * i + z) * modinv(s, n) % n
---> 83 if check_k(k):
84 print(f"Found correct k: {k}")
85 private_key = (s * k - z) * modinv(r, n) % n
Cell In [1], line 78, in check_k(k)
76 def check_k(k):
77 P = k * G
---> 78 return P.x() == r
File /home/sc_serv/sage/src/sage/structure/element.pyx:489, in sage.structure.element.Element.__getattr__()
487 AttributeError: 'LeftZeroSemigroup_with_category.element_class' object has no attribute 'blah_blah'...
488 """
--> 489 return self.getattr_from_category(name)
490
491 cdef getattr_from_category(self, name) noexcept:
File /home/sc_serv/sage/src/sage/structure/element.pyx:502, in sage.structure.element.Element.getattr_from_category()
500 else:
501 cls = P._abstract_element_class
--> 502 return getattr_from_other_class(self, cls, name)
503
504 def __dir__(self):
File /home/sc_serv/sage/src/sage/cpython/getattr.pyx:362, in sage.cpython.getattr.getattr_from_other_class()
360 dummy_error_message.cls = type(self)
361 dummy_error_message.name = name
--> 362 raise AttributeError(dummy_error_message)
363 att