Don't like this style? Click here to change it! blue.css

Welcome .... Click here to logout


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.