Cryptography and computer security - Tutorial 20.10.2020

--- tags: vaje, kirv, algorithms hackmd: https://hackmd.io/t3eeyB0tRTWnhqUyPFT3-Q plugins: mathjax, mermaid --- # Cryptography and computer security - Tutorial 20.10.2020 --- ## Algorithms with numbers ### Exercise 1 Calculate the following using the square-and-multiply algorithm: 1. $5^{13} \bmod{61}$ 2. $10^{34} \bmod{97}$ ---- 1. $13 = 8 + 4 + 1 = 1101_2$ | bit | square | multiply | | --- | ------ | -------- | | 1 | $5^0 = 1$ | $5^1 = 5$ | | 1 | $5^2 = 25$ | $5^3 = 125 = 3$ | | 0 | $5^6 = 9$ | | 1 | $5^{12} = 81 = 20$ | $5^{13} = 100 = 39$ $5^{13} \equiv 39 \pmod{61}$ 2. $34 = 32 + 2 = 100010_2$ | bit | square | multiply | | --- | ------ | -------- | | 1 | $1$ | $10$ | | 0 | $3$ | 0 | $9$ | 0 | $81 = -16$ | 1 | $16^2 = 256 = 62$ | $620 = 38$ | 0 | $86$ ``` 38 * 38 = 1444 = 14 * (97 + 3) + 44 = 42 + 44 = 86 114 304 1444 ``` $10^{34} \equiv 86 \pmod{97}$ --- ### Exercise 2 Calculate the following using the Euclidean algorithm: 1. $\gcd(264, 210)$ 2. $\gcd(975, 124)$ 3. $\gcd(89, 55)$ ---- ``` a, b, c = a mod b a = k*b + c b, c, d = b mod c ... x, y, z = x mod y = 0 gcd(a, b) = y ``` 1. | $a$ | $b$ | $c$ | | --- | --- | --- | | 264 | 210 | 54 | | 210 | 54 | 48 | | 54 | 48 | 6 | | 48 | 6 | 0 | $\gcd(264, 210) = 6$ 2. | $a$ | $b$ | $c$ | $a = kb + c$ | | --- | --- | --- | ------------ | | 975 | 124 | 107 | $975 = 7 \cdot 124 + 107$ | | 124 | 107 | 17 | $124 = 1 \cdot 107 + 17$ | | 107 | 17 | 5 | $107 = 6 \cdot 17 + 5$ | | 17 | 5 | 2 | $17 = 3 \cdot 5 + 2$ | | 5 | 2 | 1 | $5 = 2 \cdot 2 + 1$ | | 2 | 1 | 0 | $2 = 2 \cdot 1 + 0$ | $\gcd(975, 124) = 1$, $975 \bot 124$ (coprime) 3. | $a$ | $b$ | $c$ | $a = kb + c$ | | --- | --- | --- | ------------ | | 89 | 55 | 34 | $89 = 1 \cdot 55 + 34$ | | 55 | 34 | 21 | $55 = 1 \cdot 34 + 21$ | | 34 | 21 | 13 | $34 = 1 \cdot 21 + 13$ | | 21 | 13 | 8 | $21 = 1 \cdot 13 + 8$ | | 13 | 8 | 5 | $13 = 1 \cdot 8 + 5$ | | 8 | 5 | 3 | $8 = 1 \cdot 5 + 3$ | | 5 | 3 | 2 | $5 = 1 \cdot 3 + 2$ | | 3 | 2 | 1 | $3 = 1 \cdot 2 + 1$ | $\gcd(89, 55) = 1$ --- ### Exercise 3 Calculate the following using the extended Euclidean algorithm: 1. $3^{-1} \bmod{17}$ 2. $13^{-1} \bmod{61}$ 3. $10^{-1} \bmod{97}$ ---- ``` a = 1*a + 0*b a = k*b + c c = a - k*b b = 0*a + 1*b b = l*c + d d = b - l*c c = (1 - k*0)*a + (0 - k*1)*b d = ... * a + ... * b ... 1 = r*a + s*b a^-1 mod b = r b^-1 mod a = s ``` 1. | $k$ | $a$ | $r$ | $s$ | | --- | --- | --- | --- | | | 17 | 1 | 0 | | | 3 | 0 | 1 | | 5 | 2 | 1 | -5 | | 1 | 1 | -1 | 6 | * $1 = -1 \cdot 17 + 6 \cdot 3$ * $1 \equiv 6 \cdot 3 \pmod{17}$ * $3^{-1} \bmod{17} = 6$ * $1 \equiv -1 \cdot 17 \pmod{3}$ * $2^{-1} \bmod{3} = 17^{-1} \bmod{3} = -1 \bmod{3} = 2$ 2. | $k$ | $a$ | $s$ | | --- | --- | --- | | | 61 | 0 | | | 13 | 1 | | 4 | 9 | -4 | | 1 | 4 | 5 | | 2 | 1 | -14 | $13^{-1} \bmod{61} = 61 - 14 = 47$ 3. | $k$ | $a$ | $s$ | | --- | --- | --- | | | 97 | 0 | | | 10 | 1 | | 9 | 7 | -9 | | 1 | 3 | 10 | | 2 | 1 | -29 | $10^{-1} \bmod{97} = 68$ --- ### Exercise 4 Recall that in the Diffie-Hellman protocol, Alice and Bob first agree on a group element $\alpha$, and then generate secret integers $a$ and $b$, respectively, which they use to compute $\alpha^a$ and $\alpha^b$. After exchanging these values they can compute the shared secret $\alpha^{ab}$. Here, we used the multiplicative notation. ```mermaid sequenceDiagram participant Alice participant Bob Alice -> Bob: α Note left of Alice: Generate a Alice ->> Bob: A = α^a Note right of Bob: Generate b Bob ->> Alice: B = α^b Note left of Alice: Compute k = B^a Note right of Bob: Compute k = A^b ``` 1. Suppose that the the group they have used is $(\mathbb{Z}_n, +)$ for some integer $n$. Can an eavesdropper construct the shared secret from the publicly known data? 2. Suppose that the the group they have used is $(\mathbb{Z}^*_p, *)$ for some prime number $p$. Does a similar approach work? 3. Check that the groups $(\mathbb{Z}_{16}, +)$ and $(\mathbb{Z}^*_{17}, *)$ have the same structure -- they are both cyclic groups of the same size. Why is this true? ---- Group $(G, \circ)$ * closed for $\circ$: $\forall a, b \in G: a \circ b \in G$ * associativity: $\forall a, b, c \in G: (a \circ b) \circ c = a \circ (b \circ c)$ * unit: $\exists e \in G \ \forall a \in G: e \circ a = a \circ e = a$ * inverse: $\forall a \in G \ \exists b \in G: a \circ b = b \circ a = e$, where $e$ is the unit $\alpha^a = \alpha \circ \alpha \circ \dots \circ \alpha$ ($a$ times) Examples: $(\mathbb{Z}_n, +_n)$, $(\mathbb{Z}_p^*, *)$ 1. * $A = a \cdot \alpha \bmod{n}$, $B = b \cdot \alpha \bmod{n}$ * $a = A \cdot \alpha^{-1} \bmod{n}$, $b = B \cdot \alpha^{-1} \bmod{n}$i> * $k = ab \cdot \alpha$ 2. The attacker would need to compute $a = \log_\alpha A$ in $\mathbb{Z}_p^*$, which is thought to be a **hard problem**.

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.