Cryptography and computer security - Tutorial 6.10.2020

--- tags: vaje, kirv, classical hackmd: https://hackmd.io/bHFTSlfYSregNEaunFK-Og plugins: mathjax --- # Cryptography and computer security - Tutorial 6.10.2020 --- ## Modular arithmetic $$ \begin{aligned} a \equiv b \pmod{n} &\Leftrightarrow \exists k \in \mathbb{Z}: a - b = kn \\ a \bmod{n} &= \text{the remainder when dividing $a$ by $n$} \\ a \bmod{n} = b &\Leftrightarrow a \equiv b \pmod{n} \ \land \ 0 \le b \le n-1 \\ a \equiv b \pmod{n} &\Leftrightarrow a \bmod{n} = b \bmod{n} \end{aligned} $$ * $\mathbb{Z}_n = \{0, 1, 2, \dots, n-1\}$ * $x^{-1} = y =$ inverse of $x \in \mathbb{Z}_n \Leftrightarrow xy \equiv 1 \pmod{n}$ * $\mathbb{Z}_n^* = \{x \in \mathbb{Z}_n \mid x \text{ is invertible}\}$ * $|\mathbb{Z}_n^*| = \phi(n)$ + $\phi(p^k) = (p-1) p^{k-1}$ ($p$ is a prime) + $\phi(mn) = \phi(m) \phi(n)$ ($m \bot n$) ### Exercise 1 Evaluate $2020 \bmod{13}$ and $(-2020) \bmod{13}$. ``` 2020 / 13 = 155 - 13 72 - 65 70 - 65 5 ``` * $2020 \bmod{13} = 5$ * $(-2020) \bmod{13} = (-5) \bmod{13} = 8$ --- ### Exercise 2 Solve $x + 4 \equiv 2 \pmod{7}$ and $3x - 4 \equiv 4 \pmod{7}$. $$ \begin{aligned} x + 4 &\equiv 2 \pmod{7} \\ \exists k \in \mathbb{Z}: x + 4 - 2 &= 7k \\ \exists k \in \mathbb{Z}: x - (-2) &= 7k \\ x &\equiv -2 \pmod{7} \end{aligned} $$ $$ \begin{aligned} 3x - 4 &\equiv 4 \pmod{7} \\ 3x &\equiv 8 \pmod{7} \\ 3x &\equiv 1 \pmod{7} \\ \exists k \in \mathbb{Z}: 3x - 1 &= 7k \\ \exists k \in \mathbb{Z}: 3x &= 7k + 1 & k = 2 + 3t &\quad (k \equiv 2 \pmod{3}) \\ \exists t \in \mathbb{Z}: 3x &= 7(2 + 3t) + 1 \\ \exists t \in \mathbb{Z}: 3x &= 15 + 21t \\ \exists t \in \mathbb{Z}: x &= 5 + 7t \\ \exists t \in \mathbb{Z}: x - 5 &= 7t \\ x &\equiv 5 \pmod{7} \end{aligned} $$ $3 \bot 7$ ... $3$ and $7$ are *coprime* ($\gcd(3, 7) = 1$) --- ### Exercise 3 List all the invertible elements in $\mathbb{Z}_{26}$ and determine their inverses. * $\mathbb{Z}_{26} = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25\}$ * $26 = 2 \cdot 13$ * $\mathbb{Z}_{26}^* = \{1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25\}$ * $\phi(26) = \phi(2) \phi(13) = 1 \cdot 12 = 12$ $$ \begin{aligned} 1^{-1} &\equiv 1 \pmod{26} & 25^{-1} &\equiv 25 \pmod{26} \\ 3^{-1} &\equiv 9 \pmod{26} & 23^{-1} &\equiv 17 \pmod{26} \\ 9^{-1} &\equiv 3 \pmod{26} & 17^{-1} &\equiv 23 \pmod{26} \\ 5^{-1} &\equiv 21 \pmod{26} & 21^{-1} &\equiv 5 \pmod{26} \\ 7^{-1} &\equiv 15 \pmod{26} & 19^{-1} &\equiv 11 \pmod{26} \\ 15^{-1} &\equiv 7 \pmod{26} & 11^{-1} &\equiv 19 \pmod{26} \end{aligned} $$ --- ### Exercise 4 Prove that $a \bmod{n} = b \bmod{n}$ if and only if $a \equiv b \pmod{n}$. --- ## Classical ciphers Cryptosystem: $(\mathcal{P}, \mathcal{C}, \mathcal{K}, \mathcal{E}, \mathcal{D})$ * $\mathcal{P}$: set of plaintexts * $\mathcal{C}$: set of ciphertexts * $\mathcal{K}$: set of keys * $\mathcal{E}$: set of encryption functions $E : \mathcal{P} \times \mathcal{K} \to \mathcal{C}$, $E_k(x) = y$ * $\mathcal{D}$: set of decryption functions $D : \mathcal{C} \times \mathcal{K} \to \mathcal{P}$, $D_k(y) = x$ * $\forall x \in \mathcal{P} \ \forall k \in \mathcal{K}: D_k(E_k(x)) = x$ Caesar cipher: * $\mathcal{P} = \mathcal{C} = \mathcal{K} = \mathbb{Z}_{26}$ * $E_k(x) = (x+k) \bmod{26}$ * $D_k(x) = (x-k) \bmod{26}$ Substitution cipher: * $\mathcal{P} = \mathcal{C} = \mathbb{Z}_{26}$ * $\mathcal{K} = S_{26}$ (all permutations on 26 elements) * $E_\pi(x) = \pi(x)$ * $D_\pi(x) = \pi^{-1}(x)$ ### Exercise 5 If an encryption function $E_k$ is identical to the decryption function $D_k$, then the key $k$ is said to be an *involutory key*. Find all involutory keys for the Caesar cipher over $\mathbb{Z}_{26}$. $$ \begin{aligned} k &\equiv -k \pmod{26} \\ 2k &\equiv 0 \pmod{26} \\ k &\equiv 0 \pmod{13} \\ k &\in \{0, 13\} \end{aligned} $$ --- ### Exercise 6 An affine cipher has $E_k(x) = 5x+1 \bmod{26}$ as its encryption function. What is its decryption function? Affine cipher: * $\mathcal{P} = \mathcal{C} = \mathbb{Z}_{26}$ * $\mathcal{K} = \mathbb{Z}_{26}^* \times \mathbb{Z}_{26}$ * $E_{(a, b)}(x) = (ax + b) \bmod{26}$ * $D_{(a, b)}(x) = ?$ --- ### Exercise 7 Suppose that $k = (a, b)$ is a key for the affine cipher over $\mathbb{Z}_n$. Prove that $k$ is involutory if and only if $a^{-1} \bmod{n} = a$ and $b(a+1) \equiv 0 \pmod{n}$. --- ### Exercise 8 Determine all involutory keys for the affine cipher over $\mathbb{Z}_{26}$. --- ### Exercise 9 Is it possible that an affine cipher over $\mathbb{Z}_{26}$ encrypts *H* to *N* and *I* to *R*? --- ### Exercise 10 Decrypt the following ciphertext, which has been obtained from a substitution cipher, with word division preserved. Help yourself with [this website](https://www.boxentriq.com/code-breaking/cryptogram). ``` YI QCLJMXNCTJEL, T QTFPTC QYJEFC YP XIF XW MEF PYBJUFPM TIO BXPM DYOFUL ZIXDI FIQCLJMYXI MFQEIYGAFP. YM YP T MLJF XW PASPMYMAMYXI QYJEFC YI DEYQE FTQE UFMMFC YI MEF JUTYIMFKM YP CFJUTQFO SL T UFMMFC PXBF WYKFO IABSFC XW JXPYMYXIP OXDI MEF TUJETSFM. ```

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.