Elgamal Signature Scheme

Developed by Elgamal around 1985, alongside the Elgamal cryptosystem.
The United States National Standard for Digital Signature Scheme (approved by NIST) is based upon the Elgamal Signature Scheme.
Requires closer attention due to the density of mathematics.

RSA signature scheme utilizes the RSA cryptosystem directly.
Elgamal signature scheme isn't a direct repurposing of the Elgamal cryptosystem because the Elgamal cryptosystem is not endomorphic which is a requirement to create a signature scheme

Elgamal is a randomized signature scheme.
Uses a random number as part of the signing process.
Multiple possible valid signatures exist for the same message.
The verification algorithm must accept any valid signature.
Verification algorithm must accept any valid signature because there are many valid signatures.

Select a large prime number p (e.g., 2000 bits or 600 digits).
Select \alpha, a primitive element in Z_p. (Zp is a cyclic group, meaning all elements can be generated by \alpha).
Select an exponent a from Z_{p-1} (between 0 and p-2).
Compute \beta = \alpha^a \mod p.

The key consists of four parameters: p, \alpha, a, and \beta. This process is identical to Elgamal cryptosystem key generation.
p, \alpha, and \beta are public.
a is the secret key.

Message (plaintext) space: Z_p^*.
Signature space: Zp^* \times Z{p-1}. This differs from the Elgamal cryptosystem's ciphertext space (Zp^* \times Zp^*.

Select a random number k from Z{p-1}^*. This means k has an inverse in Z{p-1}. (Note: p-1 is not prime).
- To select such a k, pick a random number from Z_{p-1} and compute \gcd(k, p-1).
  - If \gcd(k, p-1) = 1, then k \in Z_{p-1}^*.
  - If \gcd(k, p-1) > 1, discard k and try again.
Compute \gamma = \alpha^k \mod p.
Compute \delta = (x - a\gamma)k^{-1} \mod (p-1).

Gamma can be computed efficiently using modular exponentiation (square and multiply algorithm).
Delta involves: x (the message), a (Alice's private key), \gamma (computed in step 3), and k^{-1} (the inverse of the random number). The inverse exists because k was chosen from Z_{p-1}^*.
The first computation is done modulo p, the second one modulo p-1.

Bob receives message x and signature (\gamma, \delta) from Alice.
Bob checks if the following congruence holds:
\beta^{\gamma} \cdot \gamma^{\delta} \equiv \alpha^x \mod p
Bob knows \beta, \gamma, \delta, \alpha, x , p and can efficiently compute both sides of congruence and verify if it holds true or not.

If the signature is constructed properly by Alice, the verification algorithm should return true.
\beta^{\gamma} \cdot \gamma^{\delta} \equiv \alpha^x \mod p
\beta = \alpha^a, so \beta^{\gamma} = (\alpha^a)^{\gamma} = \alpha^{a\gamma}
\gamma = \alpha^k, so \gamma^{\delta} = (\alpha^k)^{\delta} = \alpha^{k\delta}
Thus, \beta^{\gamma} \cdot \gamma^{\delta} = \alpha^{a\gamma} \cdot \alpha^{k\delta} = \alpha^{a\gamma + k\delta} \mod p
Since \delta = (x - a\gamma)k^{-1} \mod (p-1), then k\delta = x - a\gamma \mod (p-1), which means k\delta + a\gamma = x \mod (p-1).
Therefore, a\gamma + k\delta = x + t(p-1) for some integer t.
Substituting back, \alpha^{a\gamma + k\delta} = \alpha^{x + t(p-1)} = \alpha^x \cdot \alpha^{t(p-1)} = \alpha^x \cdot (\alpha^{p-1})^t \mod p.
Because \alpha is a primitive element in Z_p^*, \alpha^{p-1} \equiv 1 \mod p.
Thus, \alpha^x \cdot (\alpha^{p-1})^t \equiv \alpha^x \cdot 1^t \equiv \alpha^x \mod p.
Therefore, \beta^{\gamma} \cdot \gamma^{\delta} \equiv \alpha^x \mod p if the signature was constructed correctly.

Exponents always obey modulo p-1 arithmetic. Whenever you have an equation in modulo p, the exponents obey modulo p-1 arithmetic.

Oscar picks a message x.
Oscar needs to construct a signature (\gamma, \delta) such that \beta^{\gamma} \cdot \gamma^{\delta} \equiv \alpha^x \mod p.

Oscar can choose \gamma randomly and try to construct a suitable \delta.
From \beta^{\gamma} \cdot \gamma^{\delta} \equiv \alpha^x \mod p, we get \gamma^{\delta} \equiv \alpha^x \cdot \beta^{-\gamma} \mod p.
Thus, \delta = \log_{\gamma}(\alpha^x \cdot \beta^{-\gamma}), which is a discrete log problem.
Solving the discrete log problem is computationally difficult in Z_p^*.

Oscar picks \delta and then tries to construct a suitable \gamma.
\beta^{\gamma} \cdot \gamma^{\delta} \equiv \alpha^x \mod p. Here gamma appears in the exponent and base, and finding \gamma is a difficult problem.

Oscar picks both \gamma and \delta randomly and then tries to build a message x for which (\gamma, \gamma, \delta) will be deemed as a valid signature.
x \equiv \log_{\alpha}(\beta^{\gamma} \cdot \gamma^{\delta}) \mod p. This is again a discrete log problem.

Oscar selects two integers i and j.
- i \in Z_{p-1}.
- j \in Z_{p-1}^*. (i.e., \gcd(j, p-1) = 1).
Compute \gamma = \alpha^i \cdot \beta^j \mod p.
Compute \delta = -\gamma j^{-1} \mod (p-1).
Compute x = -\gamma i j^{-1} \mod (p-1).

If Oscar builds x, \gamma, and \delta this way, Bob will consider this a valid signature.
The verification involves:
\beta^\gamma \gamma^\delta = \beta^{\alpha^i \beta^j} (\alpha^i \beta^j)^{-\gamma j^{-1}} = \beta^{\alpha^i \beta^j} (\alpha^{-i \gamma j^{-1}} \beta^{-\gamma}) = \beta^{\alpha^i \beta^j} \alpha^x = \alpha^x \mod p

If Alice accidentally reveals the random number k, it is dangerous.
The opponent can figure out Alice's private key a.
\delta = (x - a\gamma)k^{-1} \mod (p-1) becomes k\delta = x - a\gamma \mod (p-1).
a\gamma = x - k\delta \mod (p-1) becomes a = (x - \delta k)\gamma^{-1} \mod (p-1).
Oscar knows x, \gamma, \delta, k and can compute a.

Alice uses the same random number k to sign two different messages, x1 and x2.
(\gamma, \delta1) is the signature for x1, and (\gamma, \delta2) is the signature for x2, where \gamma = \alpha^k \mod p.
Oscar observes both messages.
Since signatures are valid, \beta^{\gamma} \cdot \gamma^{\delta1} \equiv \alpha^{x1} \mod p and \beta^{\gamma} \cdot \gamma^{\delta2} \equiv \alpha^{x2} \mod p.
Dividing the two equations: \gamma^{\delta1 - \delta2} \equiv \alpha^{x1 - x2} \mod p.
Substituting \gamma = \alpha^k \mod p: \alpha^{k(\delta1 - \delta2)} \equiv \alpha^{x1 - x2} \mod p.
Therefore, k(\delta1 - \delta2) \equiv x1 - x2 \mod (p-1).

If (\delta1 - \delta2) has an inverse modulo (p-1), then k = (x1 - x2)(\delta1 - \delta2)^{-1} \mod (p-1).

If \gcd(\delta1 - \delta2, p-1) = d > 1, then there's a new equation by dividing with gcd as follows
\delta' = (\delta1 - \delta2) / d, x' = (x1 - x2) / d, p' = (p - 1) / d
k*\delta' = x' mod p'
Thus, \delta' has an inverse \epsilon modulo p'.
Multiplying by \epsilon gives k = x' \epsilon mod p'.
Lifting to k = x' \epsilon + i p' for some i between 0 and d-1
Find correct k by testing the values of k that satisfy equality. Test all ks with \gamma \equiv \alpha^k \mod p

Final Concluding statement: It is very very important that Allies does not use the same random number again and again. Well, not only again and again, not even for two different messages.