### 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.