Cryptography and Computer Security

« nazaj

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$

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.