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

LOGIN:

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.

- 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\).
- Choose a random \(d\) with \(0 \lt d \lt q\).
- Compute the point \(pub = d G\).
- 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.

- Choose a secret ephemeral key \(k_E\) with \(0 \lt k_E \lt q\).
- Compute \(R = k_E G\).
- Let \(r\) be the \(x\)-coordinate of \(R\).
- 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.

- Compute \(w \equiv s^{-1} \pmod{q}\).
- Compute \(u_1 \equiv w H(m) \pmod{q}\).
- Compute \(u_2 \equiv w r \pmod{q}\).
- Compute \(P = u_1 G + u_2 pub\).
- 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`

.

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`

!

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