Cryptography and Computer Security

« nazaj

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)$

$\alpha^a = \alpha \circ \alpha \circ \dots \circ \alpha$ ($a$ times)

Examples: $(\mathbb{Z}_n, +_n)$, $(\mathbb{Z}_p^*, *)$

    • $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.
Ta stran je odprtokodna. Izboljšaj to stran.
Ta zapisek je dostopen tudi na HackMD.