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:

• \(\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