Digital Signature Algorithm and ECDSA

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?

DSA key generation

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

1. Generate a prime \(p\) with \(2^{1023} \lt p \lt 2^{1024}\)
2. Find a prime divisor \(q\) of \(p-1\) with \(2^{159} \lt q \lt 2^{160}\)
3. Find an element \(\alpha\) with order \(q\) (i.e. \(\alpha\) generates the subgroup with \(q\) elements\) )
4. Choose a random integer \(d\) with \(0 \lt d \lt q\).
5. Compute \(\beta \equiv \alpha^d \pmod{p}\).
6. 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\).

Signing something

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

1. Choose an integer as a random ephemeral key \(k_E\) with \(0 \lt k_E \lt q\).
2. Compute \(r \equiv \alpha^{k_E} \pmod{q}\).
3. 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.

Validate a Signature

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.

1. Compute auxiliary value \(w \equiv s^{-1} \pmod{q}\).
2. Compute auxiliary value \(u_1 \equiv w \cdot H(m) \pmod{q}\).
3. Compute auxiliary value \(u_2 \equiv w \cdot r \pmod{q}\).
4. Compute \(v \equiv (G^{u_1} \cdot \beta^{u_2} \pmod{p}) \pmod{q} \).
5. 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.

The math of DSA

\(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.

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 \(A\) that generates a cyclic group of order \(q\).
2. Choose a random \(d\) with \(0 \lt d \lt q\).
3. Compute the point \(B = d A\).
4. 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.

The Signature

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

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 A + u_2 B\).
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.

Extra Credit

Now crack open those files and reproduce the signatures and validation using your own arithmetic.