« nazaj
Cryptography and computer security - Tutorial 8.12.2020
ElGamal encryption system
Key generation:
- Choose a large prime $p$ and $\alpha \in \mathbb{Z}_p^*$ such that $\langle \alpha \rangle = \mathbb{Z}_p^*$
- Choose the private key $a \stackrel{R}{\in} \mathbb{Z}_{p-1} \setminus \lbrace 0 \rbrace$
- Compute $\beta = \alpha^a \bmod{p}$
- Publish $(p, \alpha, \beta)$ as the public key
Encryption of $m \in \mathbb{Z}_p^*$:
- Choose $k \stackrel{R}{\in} \mathbb{Z}_{p-1} \setminus \lbrace 0 \rbrace$
- Compute $\gamma = \alpha^k \bmod{p}$ and $\delta = m \beta^k \bmod{p}$
- The ciphertext is $c = (\gamma, \delta)$
Decryption of $c = (\gamma, \delta) \in (\mathbb{Z}_p^*)^2$:
- Compute $m = \gamma^{-a} \delta \bmod{p}$
Exercise 1
Show that the ElGamal encryption and decryption functions are indeed each other’s inverses.
\[\gamma^{-a} \delta \equiv (\alpha^k)^{-a} m \beta^k \equiv m \alpha^{-ka} \alpha^{ak} \equiv m \alpha^{ak - ak} \equiv m \pmod{p}\]
Exercise 2
Let $p = 101$, $\alpha = 2$, $\beta = 14$ be the public key for the ElGamal cryptosystem, with $a = 10$ being the private key. Encrypt the plaintext $m = 10$ using $k = 7$ as the random number, and then decrypt the resulting ciphertext.
- order of $\alpha$: should be $100 = 2^2 \cdot 5^2$ (in general, $p-1 = \prod_{i=1}^t p_i^{e_i}$)
- check $\alpha^{(p-1)/p_i} \not\equiv 1 \pmod{p}$
- $\beta = 2^{10} \bmod{101} = 14$
Encryption:
- $\gamma = 2^7 \bmod{101} = 27$
- $\delta = 10 \cdot 14^7 \bmod{101} = 60$
Decryption:
| $k$ |
$a$ |
$s$ |
| |
101 |
0 |
| |
27 |
1 |
| 3 |
20 |
-3 |
| 1 |
7 |
4 |
| 2 |
6 |
-11 |
| 1 |
1 |
15 |
- $\gamma^{-a} \delta \bmod{p} = 17 \cdot 60 \bmod{101} = 10$
Exercise 3
Suppose that we use the same random number $k$ to encrypt two distinct plaintexts $m_1$ and $m_2$. Can you reveal $m_2$ if you know $m_1$ and both ciphertexts?
- Public parameters: $p, \alpha, \beta$
- $(\gamma_1, \delta_1) = (\alpha^k, m_1 \beta^k)$
- $(\gamma_2, \delta_2) = (\alpha^k, m_2 \beta^k)$
- We also know $m_1$.
- Since the same $k$ has been used, we have $\gamma_1 = \gamma_2$.
- $m_2 \equiv \delta_2 \delta_1^{-1} m_1 \equiv m_2 \beta^k m_1^{-1} \beta^{-k} m_1 \pmod{p}$
Exercise 4
Show that distinguishing ElGamal encryptions is equivalent to solving the decision Diffie-Hellman problem.
- Distinguishing ElGamal encryptions:
- given $(\gamma_1, \delta_1)$, $(\gamma_2, \delta_2)$ and $(p, \alpha, \beta)$, decide if they both encrypt the same plaintext
- Decision Diffie-Hellman problem (DDH):
- given a prime $p$ and $(\alpha, \beta, \gamma, \delta)$ such that $\langle \alpha \rangle = \mathbb{Z}_p^*$, decide if there exist $u, v$ such that $\beta \equiv \alpha^u \pmod{p}$, $\gamma \equiv \alpha^v \pmod{p}$, $\delta \equiv \alpha^{uv} \pmod{p}$
- assume that we can solve DDH
- we are given an input $(\gamma_1, \delta_1)$, $(\gamma_2, \delta_2)$ and $(p, \alpha, \beta)$ for distinguishing ElGamal encryptions
- $\beta \equiv \alpha^a \pmod{p}$
- $\gamma_i \equiv \alpha^{k_i} \pmod{p}$ ($k = 1, 2$)
- $\delta_i \equiv m_i \beta^{k_i} \pmod{p}$ ($k = 1, 2$)
- we want to decide whether $m_1 = m_2$
- construct an input for DDH: $(\alpha, \beta, \gamma_1 \gamma_2^{-1}, \delta_1 \delta_2^{-1}) = (\alpha, \alpha^a, \alpha^{k_1-k_2}, m_1 m_2^{-1} \alpha^{a (k_1 - k_2)})$
- we solve DDH, if the answer is yes, then we have $m_1 = m_2$, otherwise not
- assume we can distinguish ElGamal encryptions
- we are given an input $p$, $(\alpha, \beta, \gamma, \delta)$ for DDH
- $\beta \equiv \alpha^u \pmod{p}$
- $\gamma \equiv \alpha^v \pmod{p}$
- $\delta \equiv m \alpha^{uv} \pmod{p}$
- we want to decide whether $m = 1$
- construct the ciphertexts $(\alpha, \beta)$ (encrypting the plaintext $1$) and $(\gamma, \delta)$ (encrypting the plaintext $m$)
- we solve the distinguishing problem, if the two ciphertexts encrypt the same message, then output yes, otherwise output no