« nazaj
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.
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.