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.

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.