In ECDSA, without knowing private key and any signature one can sign random garbage (from the Cryptography list) Taken from the Cryptography mailing list.

It is claimed that in ECDSA, without knowing the private key
and any message signed with it, one can sign:


"random garbage" (there is some complicated structure in it)
$H=0$
$H=r$
$H=s$


The attached Sagemath code works for me. It uses the bitcoin
SECP256k1 curve and public key with $x=111$ with allegedly
unknown private key.


  How is this done?


The attached Sagemath code:

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()
An ECDSA signature works the following way:


We work in a sub-group of a curve. The generator is $G$ and it has order $q$ (a prime number). With most curves, $G$ actually generates the whole curve.
Private key is $x$, and corresponding public key is $Q = xG$.
To sign a message $m$:


Hash message $m$, with result being truncated/reduced modulo $q$: $h = H(m)$.
Generate a random $k$ modulo $q$ (or a non-random one, if using deterministic ECDSA).
Compute the point $kG$ and get its $X$ coordinate. The first half of the signature is $r = X \pmod q$.
Second half of the signature is $s = (h+xr)/k \pmod q$.

To verify a signature:


Hash message $m$ again, to get $h$.
Compute $w = 1/s \pmod q$.
Compute point $whG + wrQ$ and check that its $X$ coordinate, when reduced modulo $q$, yields $r$. Indeed, if the signature was properly computed, this expression recomputes the point $kG$ that was produced during signature generation.



There is no known forgery attack on ECDSA when expressed as above. The email you quote implicitly considers the case of ECDSA without the hash function. Or, said otherwise, whether one can make a forged value with $h$ considered as "message input".

For instance, take the point $Q$ (the public key) and extract its $X$ coordinate; call that $r$. Then set $s = r$. The $(r,s)$ pair is a valid signature for a message $m$ such that $h = H(m) = 0 \pmod q$. Indeed, it fulfills the verification equations: $w$ will be equal to $1/r \pmod q$, so $wrQ$ will yield simply $Q$, and since $h = 0$, then the $whG$ component will simply vanish. So the verifier will end up with point $Q$, whose $X$ coordinate indeed yields the $r$ value from the alleged signature.

Now this is not a true forgery in that you get a value which is a valid signature for a message that you do not know: the signature is valid for message $m$ which is such that $H(m) = 0 \pmod q$. But good luck with finding a matching $m$...

None of this is new, but it highlights the important role of the hash function in the process: ultimately, the preimage resistance of the hash function is crucial for resistance against forgeries.