Cryptography and computer security - Tutorial 13.10.2020

Cryptanalysis of classical ciphers

Hill cipher:

• \(\mathcal{P} = \mathcal{C} = \mathbb{Z}_{26}^t\)
• \(\mathcal{K} = \lbrace M \in \mathbb{Z}_{26}^{t \times t} \mid M\) is invertible\(\rbrace\)
• \(E_M(x) = Mx\)
• \(D_M(y) = M^{-1} y\)

Vigenère cipher:

• \(\mathcal{P} = \mathcal{C} = \mathcal{K} = \mathbb{Z}_{26}^t\)
• \(E_k(x) = (x + k) \bmod{26}\)
• \(D_k(x) = (x - k) \bmod{26}\)

Exercise 1

One reasonable idea for enhancing the security of a cryptosystem is to use double encryption. Is double encryption with the Hill cipher any safer than simple encryption? Justify your answer.

• \(M, N \in \mathbb{Z}_{26}^{t \times t}\) invertible matrices
• \(E_N(E_M(x)) = NMx = E_{NM}(x)\)
• Suppose we have some algorithm which "breaks" the cryptosystem (in reasonable time)
  • known plaintext attack: given plaintexts \(x_1, x_2, \dots\) and corresponding ciphertexts \(y_1, y_2, \dots\), find the key
  • known ciphertext attack: given ciphertexts \(y_1, y_2, \dots\), find the key
• Use the same algorithm to "break" the double Hill encryption (in the same time)

Exercise 2

Encrypt the message LJUBLJANA using the Vigenère cipher with the key FRI. Compute the index of coincidence of the obtained ciphertext.

          1         2
01234567890123456789012345
ABCDEFGHIJKLMNOPQRSTUVWXYZ

Computation of the index of coincidence

Exercise 3

The following ciphertext has been encrypted with the Vigenère cipher. Find the possible key lengths with the Kasiski test. Word divisions have not been preserved.

            1           2           3           4
01234 56789 01234 56789 01234 56789 01234 56789 012
NKASF BBYIY PWZCW TBIYK PFKUF KBJIA NKABY IYPWZ JMJ

Repetitions:

• NKA: 0, 30, offset: 30
• BYIYPWZ: 6, 33, offset: 27

Key length candidates: divisors of \(\gcd(30, 27) = 3\)

Decrypting the ciphertext

Algorithms with numbers

\(a, b \in \mathbb{Z}_p\), \(n\) digits long (in an \(\alpha\)-based system), \(n \approx \log_\alpha(a)\)

• \(a + b\), \(a - b\): \(O(n)\)
• \(a \cdot b\): \(O(n^2)\)
  • \(a + a + a + \dots\): \(O(bn)\)
  • \(b = \sum_{i=0}^{n-1} b_i 2^i\) (\(b_i \in \{0, 1\}\)), \(ab = \sum_{i=0}^{n-1} ab_i 2^i\)
  • \(c\) is \(m > n\) digits long, \(c/a\): \(O((m-n)n)\)
  • \(a^b \bmod{p}\): \(O(n^3)\)

Exercise 4

Calculate \(3^6 \bmod{17}\) using the square-and-multiply algorithm.

• \(6 = 4 + 2 = 1 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0 = 110_2\)