first pubkey coliisions - in signature transactions:)

[ecdsa123]

Code:

import hashlib

g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,       0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)

p = ZZ( '0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F'.replace( ' ', '' ) )

n = ZZ( '0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141'.replace( ' ', '' ) )

E = EllipticCurve(GF(p), [0, 7])

G = E.point( g )

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 verify(r, s,z,public_key):
     
    
    w = modinv(s, n)
    u1 = (z * w) % n
    u2 = (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") 
         

r= 111175281461482630465516451385666215051004681245013976528598462758289754744929
s= 70043377187322970975383334126537096260470471254635274932605589652196963378161
z= 1


x1=65484586321995029360829397682915368247978476961863225607803717802088249892660 
y1=72074870721525551148484769172216378998698581912792399280515952501346465251009 
P=E.point((x1,y1))
x2=40909554126419277592724504966829837604137845573578049527014144934973709534933 
y2=87404510172103350666497040794028294741242353586809580318994867241148928032959 
P2=E.point((x2,y2))

verify(r,s,z,P)
verify(r,s,z,P2)
print(P==-P2)

[NotATether]

What is the range of the nonce used in your example, since if the nonce range is small enough (I think less than 2^248?), it is trivial to derive a solution for the private key.

[ecdsa123]

hi,


at the moment I don't know. I suppose the nonce is less than 120 bit. - in my test program I have setup for maximum 120 bit
I will check today logs and paste here.


" if the nonce range is small enough (I think less than 2^248?), it is trivial to derive a solution for the private key"

how we can derive a solution for the private key in this example? I have no idea

[NotATether]

" if the nonce range is small enough (I think less than 2^248?), it is trivial to derive a solution for the private key"

how we can derive a solution for the private key in this example? I have no idea

I wrote some equations for the private key which you can view here. In particular, the first one which calculates the private key from r, s, and z (in the post it's called h) will be useful.

[puzzleplayer]

I try run this code (upper) on sagemath cell online
result is

signature matches
signature matches
False