owned this note changed 4 years ago
Linked with GitHub

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
L J U B L J A N A
11 9 20 1 11 9 0 13 0
F R I F R I F R I
5 17 8 5 17 8 5 17 8
16 0 2 6 2 17 5 4 8
Q A C G C R F E I

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\)
bit square multiply
1 \(3^0 = 1\) \(3^1 = 3\)
1 \(3^2 = 9\) \(3^3 = 27 = 10\)
0 \(3^6 = 100 = 15\) \(3^6 = 15\)
Select a repo