Georgi Guninski's blog

Humor 2017-03-13

Безкофеиново кафе и безалкохолна бира водят до надуваеми жени.

===

Caffeineless coffee and non-alcoholic beer lead to inflatable women.

In ECDSA, without knowing priv. key and any signature one can sign random garbage

In ECDSA, the signature of number H is pair (r,s).
Without knowing the private key and any signature made with the key,
one can sign:

1. "random garbage" (there is some complicated structure in it)
2. H=0
3. H=r
4. H=s

Is this known and/or trivial?

Attached are some Sage example for bitcoin's curve SEC256k1.

Would someone confirm or deny the examples with X=111 and unknown
private key indeed work?

Taking challenges:  give the public key Q_A=(x,y) on the curve.

=========

def tesbitcoincurve1():
        """
        sage code:  http://sagemath.org, can be run in a browser in
        the cloud
        to run: %runfile file.sage

        experiments with bitcoin's SEC256k1 curve
        """
        p=  0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
        Gx= 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
        Gy= 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
        E=EllipticCurve(GF(p),[0,7]);G=E(Gx,Gy)
        n=115792089237316195423570985008687907852837564279074904382605163141518161494337
        #print n*G==0
        #public key
        QA=E(111,110020423816543951948138174357929621064214669117893252455581053961287533632517) # x=111, private key not known

        (r,s),H=(111, 111),0
        v1=ECDSA_verify(r,s,n,H,G,QA)
        print v1==r
        (r,s),H=(78357151550401202949332147590566221935398179112989344213812814774602295022407, 97074620393858699186451566299627064894117871696032124298208988958060228258372),0
        v1=ECDSA_verify(r,s,n,H,G,QA)
        print v1==r
        r,s=(105428374047743273196882821059891338511368444654956635403964917579221889109295, 110610231642529734310226903034289623182103004467015769893285040360370025301816)
        H=r
        v1=ECDSA_verify(r,s,n,H,G,QA)
        print v1==r
        r,s=(88726997827321435678026270701493246247383349479297427343226348386495743771888, 6369173660802749257382322127278165968358828480647562576685803871983831660923)
        H=s
        v1=ECDSA_verify(r,s,n,H,G,QA)
        print v1==r
        (r,s),H=(105238699896951558262377011680716928670929106668167672998668678863061090326385, 102286764830003424766749795690788297189374412259121264591707039647964876795035),6206150873392997599270790826086018442478461413119740184175413055321497803859
        v1=ECDSA_verify(r,s,n,H,G,QA)
        print v1==r


def ECDSA_verify(r,s,n,H,G,QA):
        K=Integers(n)
        w=K(s)**(-1)
        u1=H*w
        u2=r*w
        u1,u2=lift(u1),lift(u2)
        x1,y1=(u1*G+u2*QA).xy()
        x1=lift(x1)
        #valid if r==x1
        return x1

tesbitcoincurve1()