Cryptography and computer security - Tutorial 13.10.2020

--- tags: vaje, kirv, classical, algorithms hackmd: https://hackmd.io/epD0n8kwRFqWIqfKcOEk9A plugins: mathjax --- # 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](https://en.wikipedia.org/wiki/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](https://nbviewer.jupyter.org/github/jaanos/kirv/blob/master/notebooks/VigenereCipher.ipynb#The-Vigen%C3%A8re-cipher) --- ### 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](https://nbviewer.jupyter.org/github/jaanos/kirv/blob/master/notebooks/VigenereCipher.ipynb#Sample-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$ |

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.