Cryptography and computer security - Tutorial 8.12.2020

--- tags: vaje, kirv, elgamal hackmd: https://hackmd.io/wqIJQIUARuijtEa3P18IoA plugins: mathjax --- # 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**

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.