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.