Elgamal Signature Scheme

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.

Differences from RSA Signature Scheme

• 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

Two Conditions for Public Key Cryptosystem to be a Digital Signature Scheme:

1. It has to be an endomorphic cryptosystem.
2. Decrypting and then encrypting should return the original message.

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

Setup

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

Key Generation

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

Spaces

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

Signing Algorithm (Alice signs message x to Bob)

1. Select a random number $k$ from $Z<em>{p-1}^*$. This means $k$ has an inverse in $Z</em>{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.
2. Compute $\gamma = \alpha^k \mod p$.
3. Compute $\delta = (x - a\gamma)k^{-1} \mod (p-1)$.

• The signature is $\left(\gamma, \delta\right)$.
• Alice sends $(x, \gamma, \delta)$ to Bob.

Efficiency

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

Verification Algorithm

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

Correctness of the Algorithm

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

Security of Elgamal Signature Scheme

• Security means that an opponent (Oscar) cannot forge Alice's signature.
• Kirchhoff's principle: Oscar knows the scheme, but not Alice's private key ($a$).

Forging a Message

1. Oscar picks a message $x$.
2. 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^*$.

Picking Delta First

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

Forging a Random Message

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

Simultaneous Construction of x, gamma, and delta

1. Oscar selects two integers $i$ and $j$.
   • $i \in Z_{p-1}$.
   • $j \in Z_{p-1}^*$. (i.e., $\gcd(j, p-1) = 1$).
2. Compute $\gamma = \alpha^i \cdot \beta^j \mod p$.
3. Compute $\delta = -\gamma j^{-1} \mod (p-1)$.
4. 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$

Revealing the Random Number

• 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$.

Reusing the Random Number

1. Alice uses the same random number $k$ to sign two different messages, $x<em>1$ and $x</em>2$.
2. $(\gamma, \delta<em>1)$ is the signature for $x</em>1$, and $(\gamma, \delta<em>2)$ is the signature for $x</em>2$, where $\gamma = \alpha^k \mod p$.
3. Oscar observes both messages.
4. Since signatures are valid, $\beta^{\gamma} \cdot \gamma^{\delta<em>1} \equiv \alpha^{x</em>1} \mod p$ and $\beta^{\gamma} \cdot \gamma^{\delta<em>2} \equiv \alpha^{x</em>2} \mod p$.
5. Dividing the two equations: $\gamma^{\delta<em>1 - \delta</em>2} \equiv \alpha^{x<em>1 - x</em>2} \mod p$.
6. Substituting $\gamma = \alpha^k \mod p$: $\alpha^{k(\delta<em>1 - \delta</em>2)} \equiv \alpha^{x<em>1 - x</em>2} \mod p$.
7. Therefore, $k(\delta<em>1 - \delta</em>2) \equiv x<em>1 - x</em>2 \mod (p-1)$.

Lucky Day Scenario

• If $(\delta<em>1 - \delta</em>2)$ has an inverse modulo $(p-1)$, then $k = (x<em>1 - x</em>2)(\delta<em>1 - \delta</em>2)^{-1} \mod (p-1)$.

Unlucky Day Scenario

1. If \gcd(\delta1 - \delta2, p-1) = d > 1, then there's a new equation by dividing with gcd as follows
2. $\delta' = (\delta<em>1 - \delta</em>2) / d, x' = (x<em>1 - x</em>2) / d, p' = (p - 1) / d$
3. $k*\delta' = x' mod p'$
4. Thus, $\delta'$ has an inverse $\epsilon$ modulo $p'$.
5. Multiplying by $\epsilon$ gives $k = x' \epsilon mod p'$.
6. Lifting to $k = x' \epsilon + i p'$ for some $i$ between 0 and $d-1$
7. 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.