11. Digital Signatures

MACs allow entities with shared secrets to generate valid tags, providing data integrity and authentication.

Digital signatures use public key cryptography to provide additional properties: only the owner of a private signing key can generate a valid signature.

Non-repudiation: the signer cannot deny they have signed a message.

Properties

Algorithms: Key & signature generation, signature verification.

Key generation algorithm outputs a private signing key, $K_S$ and public verification key, $K_V$ .

Signature generation: $s = \mathrm{Sig}(M, K_S)$ , where $M$ is a message of any length to sign. Only the owner should be able to generate a valid signature. The signature is usually a fixed size (and if there are multiple possible signatures for the same message, they will all be the same length).

Signature verification: $\mathrm{Ver}(M, s, K_V)$ outputs true or false.

Correctness: if $s = \mathrm{Sig}(M, K_S)$ , then $\mathrm{Ver}(M, s, K_V) = \mathrm{true}$ (for matching $K_S$ and $K_V$ ).

Unforgeability: computationally infeasible to generate signature for any message without key. Note that the signing algorithm may be randomized - many possible signatures for a message.

Stronger security definition: forging a new signature should be difficult even if they can obtain signatures for messages of their choice (chosen message oracle).

Security Goals

Key recovery: recovering the private signing key $K_S$ fom the public verification key $K_V$ and some known signatures.

Selective forgery: choosing a message and obtaining a signature for that message.

Existential forgery: forging a signature on any message not previously signed (even a meaningless message).

Modern digital signatures should be able to resist existential forgery under a chosen message attack.

RSA Signatures

Key Generation

Key generation is the same as for encryption keys:

Public verification key: $n$ , $e$ where $n$ is the product of two large primes $p$ and $q$
Private signing key: $p$ , $q$ , $d$ such that $ed \bmod \phi(n) = 1$

A fixed public parameter, the hash function $h$ , is also required (e.g. SHA-256).

Signature Generation and Verification

Given message $M$ , modulus $n$ and private exponent $d$ , the signature is $s = h(M)^d \bmod n$ . $(M, s)$ is the signature.

Given claimed signature $(M, s)$ , modulus $n$ and public exponent $e$ , check if $s^e \bmod n = h(M)$

Discrete Logarithm Signatures

Three versions:

Original Elgamal signatures in $\mathbb{Z}_p^*$ (1985)
Digital signature algorithm (DSA) standardized by NIST
DSA based on elliptic curve groups: ECDSA

Elgamal Elements in $\mathbb{Z}_p^*$

$p$ is a large prime
$g$ is a generator of $\mathbb{Z}_p^*$
$x$ is the private signing key, where $0 < x < p - 1$
$y = g^x \bmod p$ is part of the public key
A message $m$ in $0 < M < p - 1$

$p$ , $g$ and $y$ form the public verification key.

Signature generation:

Pick random $k$ such that $\mathrm{gcd}(k, p - 1) = 1$
Compute $r = g^k \bmod p$
Solve $M = xr + ks \bmod(p - 1)$ for $s$ :

$s = k^{-1}(M - xr) \bmod(p - 1)$
Output the tuple $(M, r, s)$

Signature verification: check if

g^M \equiv y^r r^s \pmod p

Correctness

Fermat’s Little Theorem

Fermat’s little theorem: given a prime $p$ , for any integer $a < p$ :

\begin{aligned} a^p - a &= np \\ a(a^{p - 1} - 1) &= np \end{aligned}

if $\mathrm{gcd}(a, p) = 1$ , $a \neq np$ and hence:

\begin{aligned} a^{p - 1} - 1 &= np \\ \therefore a^{p - 1} &\equiv 1 \pmod p \end{aligned}

Proving Correctness

Let $M \equiv y \pmod{p - 1}$ :

\begin{aligned} a^M &\equiv a^M \cdot a^{n(p - 1)} &\pmod{p} \\ &\equiv a^{M + n(p - 1)} &\pmod{p} \\ &\equiv a^{M \,\bmod{(p - 1)}} &\pmod{p} \\ &\equiv a^y &\pmod{p} \end{aligned}

Hence, coming back to the Elgamal signature verification equation (and noting that $g$ is a generator and hence relatively prime to $p$ :

\begin{aligned} g^M &\equiv g^{sk + xr} &\pmod p \\ &\equiv g^{sk}g^{xr} &\pmod p \\ &\equiv g^{sk}g^{xr} &\pmod p \\ &\equiv (g^k)^s(g^x)^r &\pmod p \\ &\equiv r^s y^r &\pmod p\\ \end{aligned}

as required.

Digital Signature Algorithm (DSA)

Published by NIST in 1994. Based on Elgamal signatures but calculations are simpler and signatures shorter: done in a subgroup of $\mathbb{Z}_p^*$ or an elliptic curve group. Also prevents attacks Elgamal signatures were vulnerable to.

Prime $p$ chosen such that $p - 1$ has a prime divisor $q$ that is much smaller.

Generator $g$ from Elgamal signatures is replaced by:

g = h^{\frac{p - 1}{q}} \bmod p

where $h$ is a generator.

$g$ has order $q$ as $g^q \bmod p = 1$ (by Fermat’s theorem, $g^q \bmod p = \left(h^\frac{p - 1}{q}\right)^q \bmod p = h^{p - 1} \bmod p = 1$ ). Hence, all exponents can be reduced modulo $q$ before exponentiation.

Let $H$ be a standard SHA hash algorithm such that the output is $N$ bits long (the same size as $q$ ).

$g^{H(M)} \equiv y^r r^s \bmod p$ so rearranged, we get the verification equation:

\left(g^{H(M)}\right)^{s^{-1}} \left(y^{-r}\right)^{s^{-1}} \equiv r \pmod p

Both sides of the equation are reduced modulo $q$ .

$p$ is a $L$ -bit long prime modulus, $q$ a $N$ bit long a prime divisor of $p - 1$ . There are several approved combinations for $(L, N, \text{Hash fn})$ : $(1024, 160, \text{SHA-1})$ , $(2048, 224, \text{SHA-224})$ , $(2048, 256, \text{SHA-256})$ , $(3072, 256, \text{SHA-256})$ . The first option may be insecure.

Key generation:

Choose secret key $0 < x < q$
Compute the public key, $y = g^x \bmod p$ .

Signature generation:

Message $M$
Pick $0 < k < q$
Compute $r = \left(g^k \bmod p \right) \bmod q$
- Why $\bmod q$ ?
Compute $s = k^{-1}(H(M) - xr) \bmod q$
Set the signature as $(M, r, s)$

Signature verification:

Check if $0 < r < q$ , $0 < s < q$
Compute $w = s^{-1} \bmod q$
Compute $u_1 = H(M)w \bmod q$
Compute $u_2 = rw \bmod q$
Check that $\left(g^{u_1} y^{-u_2} \bmod p \right) \bmod q = r$

Verification equation is the same as with Elgamal except that all exponents and the final result is reduced modulo $q$ . Signature size is also smaller at $2N$ bits.

Correctness

Fermat’s Little Theorem

Where $p$ and $q$ are primes and $\text{gcd}(p - 1, q) = m \neq 1$ , let $n$ be any integer.

\begin{aligned} & a^{b + nq} &\bmod p \\ =& a^{b + n \cdot \frac{p - 1}{m}} &\bmod p \\ =& a^{b} \left(a^{p - 1}\right)^{\frac{n}{m}} &\bmod p \\ =& a^{b} \cdot 1^{\frac{n}{m}} &\bmod p \\ =& a^b &\bmod p \end{aligned}

Hence $a^{b \,\bmod q} \bmod p \equiv a^b \bmod p$

Proving Correctness

Let $M \equiv y \pmod{p - 1}$ :

\begin{aligned} a^M &\equiv a^M \cdot a^{n(p - 1)} &\pmod{p} \\ &\equiv a^{M + n(p - 1)} &\pmod{p} \\ &\equiv a^{M \,\bmod{(p - 1)}} &\pmod{p} \\ &\equiv a^y &\pmod{p} \end{aligned}

Hence, coming back to the Elgamal signature verification equation (and noting that $g$ is a generator and hence relatively prime to $p$ :

\begin{aligned} g^M &\equiv g^{sk + xr} &\pmod p \\ &\equiv g^{sk}g^{xr} &\pmod p \\ &\equiv g^{sk}g^{xr} &\pmod p \\ &\equiv (g^k)^s(g^x)^r &\pmod p \\ &\equiv r^s y^r &\pmod p\\ \end{aligned}

as required.

Elliptic Curve DSA (ECDSA)

Similar to DSA except that:

$q$ becomes the order of the elliptic curve group
Multiplication modulo $p$ is replaced by the elliptic curve group operation
After operations on group elements, only the $x$ coordinate is kept from the pair $(x, y)$

Compared to DSA, public keys are shorter but signatures are not (326 to 1142 bits).