[Cryptography] In ECDSA, without knowing priv. key and any signature one can sign random garbage
Georgi Guninski
guninski at guninski.com
Mon Mar 6 08:22:21 EST 2017
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.
-------------- next part --------------
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()
More information about the cryptography
mailing list