ECDSA

Now for the cool part (the power of abstract algebra). Since we've just laid out an algorithm that works for the cyclic group \(\mathbb{Z}_p^{*}\) we can move the whole process over to the more secure Elliptic Curve cyclic group.

ECDSA Key Generation

1. We use an elliptic curve \(E\) with a modulus \(p\), coefficients \(A, B\), and a point \(G\) that generates a cyclic group of order \(q\).
2. Choose a random \(d\) with \(0 \lt d \lt q\).
3. Compute the point \(pub = d G\).
4. Protect your private key \(k_{pr} = d\) and publish your public key \(k_{pub} = (p, A, B, q, G, pub) \).

NOTE: To get the same security as AES-128 with DSA we needed to set the larger prime to 3072 bits and the smaller signature prime to 256-bits. For the Elliptic Curve world we want a 256-bit order for \(G\) and our modulus \(p\) will be must smaller than 3072 bits.

Generate The Keys: Use openssl ecparam -genkey -name secp384r1 -noout -param_enc explicit -out ecprivate.pem to make a private key (with curve parameters listed out) and openssl ec -in ecprivate.pem -pubout -out ecpublic.pem to make a public key.

The Signature

1. Choose a secret ephemeral key \(k_E\) with \(0 \lt k_E \lt q\).
2. Compute \(R = k_E G\).
3. Let \(r\) be the \(x\)-coordinate of \(R\).
4. Compute \(s \equiv (H(m) + d r) k_E^{-1} \pmod{q}\).

Recall that our thingtosign.txt was made with echo "andy is great" > thingtosign.txt

Generate an ECDSA signature: Use the command openssl dgst -sha256 -sign ecprivate.pem thingtosign.txt > ecsig.bin to generate a signature.

The Verification

1. Compute \(w \equiv s^{-1} \pmod{q}\).
2. Compute \(u_1 \equiv w H(m) \pmod{q}\).
3. Compute \(u_2 \equiv w r \pmod{q}\).
4. Compute \(P = u_1 G + u_2 pub\).
5. If the \(x\)-coordinate of \(P\) is \(r\) then return VALID else INVALID

Validate with openssl: Use openssl dgst -sha256 -verify ecpublic.pem -signature ecsig.bin thingtosign.txt.

Deep dive

Now let's crack open those files and reproduce the signatures and validation on our own.

Here are the steps I did to find \(k_E\) and validate the signature.

openssl asn1parse -in ecsig.bin -inform der will produce \(r\) and \(s\). Start a SAGE session and store those values. (They come out as hex so convert as needed.)

openssl ec -in ecprivate.pem -noout -text > ecpriv.txt will dump the private key data into ecpriv.txt. Now use the following script to read in those parameters:

Now in SAGE import p (params['Prime']), q (params['Order']), A, B, G (params['Gener']), pub, d (params['priv']). Create E=EllipticCurve(GF(p), [A, B]) the curve and make g = E(gener_tuple_here) and pub=E(pub_tuple_here).

Double Check Validate that q*g is zero and that d*g == pub.

Get the hash: z = int(hashlib.sha256("andy is great\n").hexdigest(), 16)

Find the ephemeral key (optional) find sinv = inverse_mod(s, q) then ke = (sinv*(z + d*r)) % q Validate that the x-coordinate of ke*g is r.

Finish the validation: w = inverse_mod(s, q) u1 = (w*z) % q u2 = (w*r) % q P = u1*g + u2*pub now validate that the x-coordinate of P is r!

Extra Credit

Create a file, a public key, and a signature. Send it to a partner. Have them validate the signature.