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

LOGIN:

Welcome .... Click here to logout

**Overview:** This is the primary Digital Signature Algorithm out there (DSA) and the Elliptic curve version (ECDSA). It's essential canon for any cryptographer.

The top application of ECC that I can see is certificates for the various domains serving HTTPS content (although BitCoin uses ECDSA extensively too). At the heart of this will be Key Exchange (ECDHE) and/or Digital Signature (ECDSA). We looked at RSA digital signatures, but we haven't done the cyclic group version. Let's get to it!

This is the Digital Signature Algorithm (DSA) which tries to make a Diffie-Hellman based digital signature of a message using a private key that anyone knowing your public key can verify. The same idea is used for plain DH and Elliptic Curve DH. So we can make a quick switch from DSA to ECDSA.

If you think this out you'll probably arrive at the need for making an imaginary Bob. Afterall DH is about a shared secret. So if I'm supposed to make an unforgeable signature which you can verify then what do I share?

This algorithm has slightly different key-length requirements than our typical "strong prime" setup. Digital Signatures have a smaller prime that allows smaller signatures for efficiency. The specific lengths and security equivalents are maintained by NIST in: FIPS 186-4 (section 4.2) and SP 800-57 (section 5.6.1). I'll choose weak parameters for this one (because that is what `ssh-keygen`

can handle), but as you all leave my nest be aware that there are tables of recommendations for every algorithm we've looked at (well not the historical ciphers).

- Generate a prime \(p\) with \(2^{1023} \lt p \lt 2^{1024}\)
- Find a prime divisor \(q\) of \(p-1\) with \(2^{159} \lt q \lt 2^{160}\)
- Find an element \(\alpha\) with order \(q\) (i.e. \(\alpha\) generates the subgroup with \(q\) elements\) )
- Choose a random integer \(d\) with \(0 \lt d \lt q\).
- Compute \(\beta \equiv \alpha^d \pmod{p}\).
- Protect the private key \(k_{pr} = d\). Publish the public key \(k_{pub} = (p, q, \alpha, \beta)\).

**Generate DSA parameters:** Use `openssl dsaparam 1024 > dsaparam.pem`

to create a parameters file. Use `openssl dsaparam -in dsaparam.pem -text -noout > parameters`

to dump readable data into a text file.

**Generate a private DSA key**: Now use those parameters to make a private key file: `openssl gendsa -out dsa_priv.pem dsaparam.pem`

.

**Confirm Private Parameters:** Now `openssl dsa -in dsa_priv.pem -noout -text > private_parameters`

will give you `priv, pub`

parameters in addition to the earlier \(P, G, Q\). `priv`

is \(d\) and `pub`

is \(G^d \pmod{p}\). Confirm that \(G^d \pmod{p} = \)`pub`

.

Here is a script to read the private parameters:

**Validate:** That private file has a \(P, Q, G, d, \beta = G^d \pmod{P} \). Validate that \(Q\) divides \(P-1\), that \(G^{Q} = 1 \pmod{P} \), and that \(G^d \pmod{P} = \beta \).

So far this is only slightly different than a DH setup in that we have two cyclic groups, one large one of order \(P-1\) and a smaller cyclic group of order \(Q\) generated by \(G\).

Now that we have some parameters let's go to town generating a signature for a message \(m\) using some hash algorithm \(H\).

- Choose an integer as a random ephemeral key \(k_E\) with \(0 \lt k_E \lt q\).
- Compute \(r \equiv \alpha^{k_E} \pmod{q}\).
- Compute \(s \equiv (H(m) + d \cdot r) k_E^{-1} \pmod{q}\)

**NOTE:** In the specifications of DSA if your hash algorithm puts out more bits than the bit-length of \(q\) then take the top most bits of \(H(m)\). For instance if using SHA256 and \(q\) with bit-length 160 then the top 160 bits of the SHA256 digest are what we use.

**Generate a signature:** Use `echo "andy is great" > thingtosign.txt`

to create a file we will sign. Use `openssl dgst -sha256 -sign dsa_priv.pem thingtosign.txt > signature.bin`

to generate a binary signature file.

**Generate the public key:** Use `openssl dsa -in dsa_priv.pem -pubout -out dsa_pub.pem`

**Read the signature file:** Use the command `openssl asn1parse -in signature.bin -inform der`

to read the two integers in the signature file. You should see 2 length 40 hex strings (20 bytes each for the 160 bit mod \(q\) numbers). They are \(r\) and \(s\). Save them into a script along with the above \(P, G, Q, d\).

**Check the math:** To validate we need the top 160 bits of the SHA256 of "andy is great\n" (the file adds a newline character at the end). You can do this in code using `shasum -a 256 thingtosign.txt`

or `z = int(hashlib.sha256("andy is great\n").hexdigest()[:40], 16)`

in Python. We aren't given \(k_E\) anywhere so let's reverse it using what we do know. If \(z\) is that 160-bit hash as an int, then compute \( k_E = (s^{-1} \cdot (z + d \cdot r) ) \pmod{q} \). Now compute \( (G^{k_E} \pmod{p}) \pmod{q}\) and check that it equals \(r\). Phew... we cracked a discrete log, kinda.

At this stage we want someone that ONLY knows the public key \( (P, G, Q, (\beta := G^{d} \pmod{Q}) )\) and the message \(m\) can confirm that \(r\) and \(s\) were made by someone that knows \(d\) without the validator knowing \(d\). (I'm using \(\beta\) as the public key parameter `pub`

.) Let's look at the steps before we understand the math.

- Compute auxiliary value \(w \equiv s^{-1} \pmod{q}\).
- Compute auxiliary value \(u_1 \equiv w \cdot H(m) \pmod{q}\).
- Compute auxiliary value \(u_2 \equiv w \cdot r \pmod{q}\).
- Compute \(v \equiv (G^{u_1} \cdot \beta^{u_2} \pmod{p}) \pmod{q} \).
- If \(v \equiv r\) return "VALID" else return "INVALID".

**CLI verify:** Run the line `openssl dgst -sha256 -verify dsa_pub.pem -signature signature.bin thingtosign.txt`

from the command line.

**Hand Verify:** We know \(r, s, G, \beta, Q, P, H(m)\) (the hash is truncated don't forget) so do the five steps above and recreate \(r\) in a Python/SAGE session.

\(s \equiv (H(m) + d r) k_E^{-1} \pmod{q} \)

So \(k_E = s^{-1} H(m) + d s^{-1} r \pmod{q}\) which implies that

\(k_E = u_1 + d u_2 \pmod{q}\) (just substitute).

Now raise both sides to the \(G\) modulo \(p\) to get:

\( G^{k_E} \equiv G^{u_1 + d u_2} \pmod{p} \)

\(G^{k_E} \pmod{p} \equiv G^{u_1} \cdot (G^d)^{u_2} \pmod{p} \)

But now we get the magic, because \(G^d\) is known publicly as \(\beta\) and we know that left hand side modulo \(q\).

So: \(r \equiv (G^{u_1} \beta^{u_2} \pmod{p}) \pmod{q}\).

**Convince yourself:** Convince yourself that this works.

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 \(A\) that generates a cyclic group of order \(q\).
- Choose a random \(d\) with \(0 \lt d \lt q\).
- Compute the point \(B = d A\).
- Protect your private key \(k_{pr} = d\) and publish your public key \(k_{pub} = (p, a, b, q, A, B) \).

**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 \(A\) and our modulus \(p\) will be must smaller than 3072 bits.

**Generate The Keys:** Use `openssl ecparam -genkey -name secp384r1 -noout -out ecprivate.pem`

to make a private key 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 A\).
- Let \(r\) be the \(x\)-coordinate of \(R\).
- Compute \(s \equiv (H(m) + d r) k_E^{-1} \pmod{q}\).

**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 A + u_2 B\).
- 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 crack open those files and reproduce the signatures and validation using your own arithmetic.