Section 5.2 Elgamal digital signatures
We'll begin with a scheme that derives from the Elgamal encrpytion system. Note that this scheme is not used in practice because the key sizes are enormous. We present it here as a starting point for the discussion of the DSA.
Algorithm 5.2.1.
- (public parameters) Sam chooses a large prime \(p\) and a primitive root (generator) \(g\text{.}\)
- (private) Sam chooses a private key \(a \in \F_p\) and computes \(A = g^a\text{.}\)
- (public) Sam publishes \(p, g, A\text{.}\)
- (private) Sam wishes to sign a document \(D\) where \(1 \leq D \lt p\text{.}\) She picks a random element \(k\) with \(\gcd(k, p-1) = 1\text{.}\) She computes\begin{equation*} S_1 = g^k \bmod p, \hspace{.5cm} S_2 = (D - aS_1)k\inv \bmod p-1. \end{equation*}Her signature is the pair \(D^{sig} = (S_1, S_2)\text{.}\)
- (private) Vera receives the document \(D\text{,}\) the signature \(D^{sig}\) and the public signing key \(p, g, A\text{.}\) She wants to verify that the document comes from Sam.
- Vera's verification question is:\begin{equation} \text{Is } A^{S_1}S_1^{S_2} \bmod p = g^D \bmod p \text{?}\label{eq-egds}\tag{5.2.1} \end{equation}
The proof that this verification question works is left as an exercise. One important difference with Elgamal encrpytion is that there is a number that we compute \(\bmod p -1\text{:}\) the reason for this arises in the algebraic proof that the verification question works. Fermat's little theorem is what allows us to conclude that if \(a = b \bmod p - 1\text{,}\) then \(g^a = g^b \bmod p\text{.}\)
In order for Elgamal signatures to be cryptographically secure, the prime \(p \approx 2^{4000}\) because of the existence of subexponential algorithms like the index calculus that can be used to attack the discrete log problem in \(\F_p\text{.}\) There are two possible approaches to take to make this a more usable system. The first is to choose a huge prime \(p\) to keep the problems large enough to be unsolvable, but work within a special subset of \(\F_p\) called a cyclic subgroup, discussed in the next section. The other approach is to replace \(\F_p\) with a group that isn't attackable by the index calculus, like an elliptic curve \(E(\F_p)\text{,}\) which will be discussed later in the chapter.