Crittografia

&

Aritmetica modulare

 

 

 

Massimo Santini

Cosa

Come

Perché

Queste note sono generate a partire da un notebook Jupyter disponibile su GitHub. In particolare, molto del materiale qui visualizzato è prodotto da del codice in Python sviluppato appositamente e distribuito in modalità open source e che quindi potete liberamente studiare, modificare e distribuire. Se vi piace programmare, date una occhiata!

Crittografia

A chiave simmetrica

$$\Huge C(p, k) = c \qquad\text{e}\qquad D(c, k) = p$$

$$\Huge D(C(p, k), k) = p$$

$$\Huge D(c) = p$$

Monoalfabetica

┌───────────┬───┬───┬───┬───┬───┬───┬───┬────┬────┬────┬────┬────┬────┐
│ lettera   │ A │ B │ C │ D │ E │ F │ … │ W  │ X  │ Y  │ Z  │ ␢  │ ↩  │
├───────────┼───┼───┼───┼───┼───┼───┼───┼────┼────┼────┼────┼────┼────┤
│ posizione │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ … │ 22 │ 23 │ 24 │ 25 │ 26 │ 27 │
└───────────┴───┴───┴───┴───┴───┴───┴───┴────┴────┴────┴────┴────┴────┘

┌───────────┬───┬───┬────┬────┬───┬────┬────┬───┬────┐
│ testo     │ B │ E │ L  │ L  │ A │    │ Z  │ I │ O  │
├───────────┼───┼───┼────┼────┼───┼────┼────┼───┼────┤
│ posizioni │ 1 │ 4 │ 11 │ 11 │ 0 │ 26 │ 25 │ 8 │ 14 │
└───────────┴───┴───┴────┴────┴───┴────┴────┴───┴────┘

┌───────┬───┬───┬────┬────┬───┬────┬────┬────┬────┐
│ a     │ 1 │ 4 │ 11 │ 11 │ 0 │ 26 │ 25 │  8 │ 14 │
├───────┼───┼───┼────┼────┼───┼────┼────┼────┼────┤
│ b     │ 3 │ 3 │  3 │  3 │ 3 │  3 │  3 │  3 │  3 │
├───────┼───┼───┼────┼────┼───┼────┼────┼────┼────┤
│ a + b │ 4 │ 7 │ 14 │ 14 │ 3 │  1 │  0 │ 11 │ 17 │
└───────┴───┴───┴────┴────┴───┴────┴────┴────┴────┘

┌───┬─────┬─────┬──────┬──────┬─────┬─────┬──────┬──────┬──────┐
│ p │ B:1 │ E:4 │ L:11 │ L:11 │ A:0 │ :26 │ Z:25 │ I:8  │ O:14 │
├───┼─────┼─────┼──────┼──────┼─────┼─────┼──────┼──────┼──────┤
│ k │ D:3 │ D:3 │ D:3  │ D:3  │ D:3 │ D:3 │ D:3  │ D:3  │ D:3  │
├───┼─────┼─────┼──────┼──────┼─────┼─────┼──────┼──────┼──────┤
│ c │ E:4 │ H:7 │ O:14 │ O:14 │ D:3 │ B:1 │ A:0  │ L:11 │ R:17 │
└───┴─────┴─────┴──────┴──────┴─────┴─────┴──────┴──────┴──────┘

EHOODBALR

┌───┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│ c │ E:4  │ H:7  │ O:14 │ O:14 │ D:3  │ B:1  │ A:0  │ L:11 │ R:17 │
├───┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ k │ Z:25 │ Z:25 │ Z:25 │ Z:25 │ Z:25 │ Z:25 │ Z:25 │ Z:25 │ Z:25 │
├───┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ p │ B:1  │ E:4  │ L:11 │ L:11 │ A:0  │ :26  │ Z:25 │ I:8  │ O:14 │
└───┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘

BELLA ZIO

def C(p, k):
  return da_posizioni(
    orologio_somma(
      a_posizioni(p), 
      a_posizioni(k)
    )
  )

def D(c, k):
  return da_posizioni(
    orologio_somma(
      a_posizioni(c), 
      a_posizioni(
        inverti(k)
      )
    )
  )

p = 'BELLA ZIO'
k = 'D'

c = C(p, k)
print(c)

EHOODBALR

d = D(c, k)
print(d)

BELLA ZIO

Crittoanalisi

Forza bruta

┌─────┬───────────┐
│ k   │ D(c, k)   │
├─────┼───────────┤
│ A   │ EHOODBALR │
├─────┼───────────┤
│ B   │ DGNNCA↩KQ │
├─────┼───────────┤
│ C   │ CFMMB↩␢JP │
├─────┼───────────┤
│ D   │ BELLA␢ZIO │
├─────┼───────────┤
│ E   │ ADKK↩ZYHN │
├─────┼───────────┤
│ …   │ …         │
├─────┼───────────┤
│ ␢   │ GJQQFDCNT │
├─────┼───────────┤
│ ↩   │ FIPPECBMS │
└─────┴───────────┘

for k in SEMPLICI[:10]:
  print(a_visualizzazione((D(c, k))))

EHOODBALR
DGNNCA↩KQ
CFMMB↩␢JP
BELLA␢ZIO
ADKK↩ZYHN
↩CJJ␢YXGM
␢BIIZXWFL
ZAHHYWVEK
Y↩GGXVUDJ
X␢FFWUTCI

Analisi frequenziale

Da "I promessi sposi"

TUTTE DUE SI VOLSERO A CHI NE SAPEVA PIU DI LORO E DA CUI 
ASPETTAVANO UNO SCHIARIMENTO IL QUALE NON POTEVA ESSERE CHE 
DOLOROSO TUTTE DUE LASCIANDO TRAVEDERE IN MEZZO AL DOLORE 
E CON LAMORE DIVERSO CHE OGNUN DESSI PORTAVA A LUCIA

FZ ZZKEJ KEYOE
URYKXUEGEINOETKEYGVK
GEVO EJOERUXUEKEJGEI OEFGYVKZZG
GTUE TUEYINOGXOSKTZUEOREW GRKETUTEVUZK
GEKYYKXKEINKEFJURUXUYUEZ ZZKEJ KERGYIOGTJUEZXG
KJKXKEOTESKDDUEGREJURUXKEFKEIUTERGSUXKEJO
KXYUEINKEUMT TEJKYYOEVUXZG
GEGER IOGF

print(D(c, 'G'))

TUTTE DUE SI VOLSERO A CHI NE SAPEVA PIU DI LORO E DA CUI 
ASPETTAVANO UNO SCHIARIMENTO IL QUALE NON POTEVA ESSERE CHE 
DOLOROSO TUTTE DUE LASCIANDO TRAVEDERE IN MEZZO AL DOLORE 
E CON LAMORE DIVERSO CHE OGNUN DESSI PORTAVA A LUCIA

Polialfabetica

┌───────┬───┬────┬────┬────┬───┬────┬────┬────┬────┐
│ a     │ 1 │  4 │ 11 │ 11 │ 0 │ 26 │ 25 │  8 │ 14 │
├───────┼───┼────┼────┼────┼───┼────┼────┼────┼────┤
│ b     │ 2 │  8 │  0 │ 14 │ 2 │  8 │  0 │ 14 │  2 │
├───────┼───┼────┼────┼────┼───┼────┼────┼────┼────┤
│ a + b │ 3 │ 12 │ 11 │ 25 │ 2 │  6 │ 25 │ 22 │ 16 │
└───────┴───┴────┴────┴────┴───┴────┴────┴────┴────┘

┌───┬─────┬──────┬──────┬──────┬─────┬─────┬──────┬──────┬──────┐
│ p │ B:1 │ E:4  │ L:11 │ L:11 │ A:0 │ :26 │ Z:25 │ I:8  │ O:14 │
├───┼─────┼──────┼──────┼──────┼─────┼─────┼──────┼──────┼──────┤
│ k │ C:2 │ I:8  │ A:0  │ O:14 │ C:2 │ I:8 │ A:0  │ O:14 │ C:2  │
├───┼─────┼──────┼──────┼──────┼─────┼─────┼──────┼──────┼──────┤
│ c │ D:3 │ M:12 │ L:11 │ Z:25 │ C:2 │ G:6 │ Z:25 │ W:22 │ Q:16 │
└───┴─────┴──────┴──────┴──────┴─────┴─────┴──────┴──────┴──────┘
DMLZCGZWQ

B
UFVM RWM EKGVAN EDQGAMEPIMPM ECXEHCGPWWGDWATODQGEMFI QWQ NC PSV
AHCVOMWVOMUKHWCZI GVTAAQLMSAAZGGNAPGPAVMVOAMSEGZEMEPEMBLOZQZOEQGTGV
EMFAEMNISQKINRQGTDCBERGZEMKV  GFZAAILMFWLATM NGGCAPGLOOWRSALIHGZSAAKHSAWG
WV RG SWAXODVIVOAI ZWKIOB

Perfetta!

E ora… magia!

Scambiare le chiavi senza canale sicuro

Aritmetica modulare

$$\Huge \left(\mathbb{Z}, +, \cdot\right)$$

 

$$\Huge \mod n$$

 

$$\Huge \begin{split} [r]_n & \triangleq \{z \mid z = k\cdot n + r, \quad k \in\mathbb{Z}\} \\ & = \{z \mid z \equiv r \pmod n\} \\ & = \{z \mid z \mathbin{\%} n = r\} \end{split} $$

$$\Huge [3]_7 = \{\ldots, -11, -4, 3, 10, 17,\ldots\}$$

 

$$\Huge [-4]_7 = \{\ldots, -18, -11, -4, 3, 10,\ldots\}$$

 

$$\Huge [r]_n = [r + k \cdot n]_n $$

$$\Huge \mathbb{Z}_n \triangleq \{[0]_n, [1]_n, [2]_n, \ldots, [n-1]_n\}$$

 

$$\Huge (\mathbb{Z}_n, +, \cdot)$$

$$\Huge [r] + [s] \triangleq [r + s]$$

┌─────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐
│ +   │ [0]   │ [1]   │ [2]   │ [3]   │ [4]   │ [5]   │ [6]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [0] │ [0]   │ [1]   │ [2]   │ [3]   │ [4]   │ [5]   │ [6]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [1] │ [1]   │ [2]   │ [3]   │ [4]   │ [5]   │ [6]   │ [0]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [2] │ [2]   │ [3]   │ [4]   │ [5]   │ [6]   │ [0]   │ [1]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [3] │ [3]   │ [4]   │ [5]   │ [6]   │ [0]   │ [1]   │ [2]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [4] │ [4]   │ [5]   │ [6]   │ [0]   │ [1]   │ [2]   │ [3]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [5] │ [5]   │ [6]   │ [0]   │ [1]   │ [2]   │ [3]   │ [4]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [6] │ [6]   │ [0]   │ [1]   │ [2]   │ [3]   │ [4]   │ [5]   │
└─────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┘

$$\Huge [r] \cdot [s] \triangleq [r \cdot s]$$

┌─────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐
│ *   │ [0]   │ [1]   │ [2]   │ [3]   │ [4]   │ [5]   │ [6]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [0] │ [0]   │ [0]   │ [0]   │ [0]   │ [0]   │ [0]   │ [0]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [1] │ [0]   │ [1]   │ [2]   │ [3]   │ [4]   │ [5]   │ [6]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [2] │ [0]   │ [2]   │ [4]   │ [6]   │ [1]   │ [3]   │ [5]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [3] │ [0]   │ [3]   │ [6]   │ [2]   │ [5]   │ [1]   │ [4]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [4] │ [0]   │ [4]   │ [1]   │ [5]   │ [2]   │ [6]   │ [3]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [5] │ [0]   │ [5]   │ [3]   │ [1]   │ [6]   │ [4]   │ [2]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [6] │ [0]   │ [6]   │ [5]   │ [4]   │ [3]   │ [2]   │ [1]   │
└─────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┘

┌─────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┬───────┐
│ *   │ [0]   │ [1]   │ [2]   │ [3]   │ [4]   │ [5]   │ [6]   │ [7]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [0] │ [0]   │ [0]   │ [0]   │ [0]   │ [0]   │ [0]   │ [0]   │ [0]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [1] │ [0]   │ [1]   │ [2]   │ [3]   │ [4]   │ [5]   │ [6]   │ [7]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [2] │ [0]   │ [2]   │ [4]   │ [6]   │ [0]   │ [2]   │ [4]   │ [6]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [3] │ [0]   │ [3]   │ [6]   │ [1]   │ [4]   │ [7]   │ [2]   │ [5]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [4] │ [0]   │ [4]   │ [0]   │ [4]   │ [0]   │ [4]   │ [0]   │ [4]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [5] │ [0]   │ [5]   │ [2]   │ [7]   │ [4]   │ [1]   │ [6]   │ [3]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [6] │ [0]   │ [6]   │ [4]   │ [2]   │ [0]   │ [6]   │ [4]   │ [2]   │
├─────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┼───────┤
│ [7] │ [0]   │ [7]   │ [6]   │ [5]   │ [4]   │ [3]   │ [2]   │ [1]   │
└─────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┴───────┘

┌─────┬───────┬───────┬───────┬───────┐
│ *   │ [1]   │ [3]   │ [5]   │ [7]   │
├─────┼───────┼───────┼───────┼───────┤
│ [1] │ [1]   │ [3]   │ [5]   │ [7]   │
├─────┼───────┼───────┼───────┼───────┤
│ [3] │ [3]   │ [1]   │ [7]   │ [5]   │
├─────┼───────┼───────┼───────┼───────┤
│ [5] │ [5]   │ [7]   │ [1]   │ [3]   │
├─────┼───────┼───────┼───────┼───────┤
│ [7] │ [7]   │ [5]   │ [3]   │ [1]   │
└─────┴───────┴───────┴───────┴───────┘

$$\Huge [r] \cdot [s] = [1]$$

 

$$\Huge [s] = [r]^{-1}$$

$$\Huge r \cdot s + k\cdot n = \operatorname{MCD}(r, n)$$

 

$$\Huge \operatorname{EG}(r, n) \to s, k$$

def EG(r, n):
  s0, s1, k0, k1 = 1, 0, 0, 1
  while n != 0:
    q, r, n = r // n, n, r % b
    s0, s1 = s1, s0 - q * s1
    k0, k1 = k1, k0 - q * k1
  return r, s0, k0

$$\Huge \operatorname{MCD}(r, n) = 1 \quad\Rightarrow\quad r \cdot s + k\cdot n = 1$$

 

$$\Huge r\cdot s = 1 - k\cdot n$$

 

$$\Huge [r\cdot s]_n = [1]_n$$

 

$$\Huge [s]_n = [r]^{-1}_n$$

$$\Huge [r]^e \triangleq [r^e]$$

┌──────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ **   │ 1   │ 2   │ 3   │ 4   │ 5   │ 6   │
├──────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ [1]  │ [1] │     │     │     │     │     │
├──────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ [2]  │ [2] │ [4] │ [1] │     │     │     │
├──────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ [3]  │ [3] │ [2] │ [6] │ [4] │ [5] │ [1] │
├──────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ [4]  │ [4] │ [2] │ [1] │     │     │     │
├──────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ [5]  │ [5] │ [4] │ [6] │ [2] │ [3] │ [1] │
├──────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ [6]  │ [6] │ [1] │     │     │     │     │
└──────┴─────┴─────┴─────┴─────┴─────┴─────┘

$$\Huge [y]_p = [g]_p^x$$

 

$$\Huge \widehat\exp: x \to [y]_p$$

 

$$\Huge \widehat\log: [y]_p \to x$$

def expm(b, e, m):
  r = 1
  while e > 0:
    if e % 2 == 1: r = (r * b) % m
    b = (b * b) % m
    e = e // 2
  return r

$$\Huge \begin{split} a \quad \Rightarrow \quad A = [g^a]_p \\ b \quad \Rightarrow \quad B = [g^b]_p \end{split} $$

 

$$\Huge \begin{split} B^a &= [g^b]^a = \left([g]^b\right)^a = [g]^{ba} \\ A^b &= [g^a]^b = \left([g]^a\right)^b = [g]^{ab} \end{split} $$

 

$$\Huge [g]^{ba} = [g]^{ab}$$

p = 2963
g = 51

M = Mod(p)

len(M[g].potenze()) == p - 1

True

a = 123
A = M[g] ** a
A

[2149]

b = 345
B = M[g] ** b
B

[2940]

B ** a, B ** a 

([2413], [2413])

Ancora più magia!

Crittografia asimmetrica

$$\Huge F_n(m, x) \triangleq [m]_n^x$$

 

$$\Huge p, q, e \mapsto n, d$$

 

$$\Large (i) \Huge \qquad F_n(F_n(m, e), d) = [m]_n$$

 

$$\Large (ii) \Huge \qquad n, d \not\mapsto p, q, e$$

$$\Huge F(F(m, e), d) = [m]$$

 

$$\Huge D(C(m, k), k) = m$$

 

$$\Huge D(C(m, e), d) = m$$

 

$$\Huge D = C = F$$

$$\Large \Huge \qquad n \triangleq p \cdot q$$

$$\Large (ii) \qquad \Huge F_n(F_n(m, e), d) = [m]_n$$

 

$$\Huge \qquad [m]^{ed}_n = [m]_n$$

$$\Huge \varphi(n) \triangleq |\{i \in\mathbb{N} \mid i < n, i \perp n\}|$$

 

$$\Huge m \perp n \Rightarrow [m]^{\varphi(n)}_n = [1]_n$$

 

$$\Huge \left([m]^{\varphi(n)}\right)^k = [1]^k$$

 

$$\Huge [m] \cdot [m]^{k\cdot \varphi(n)} = [m] \cdot [1]$$

 

$$\Huge [m]^{1 + k\cdot \varphi(n)} = [m]$$

$$\Huge ed = 1 + k\cdot \varphi(n)$$

 

$$\Huge [ed]_{\varphi(n)} = [1]_{\varphi(n)}$$

 

$$\Huge [d]_{\varphi(n)} \triangleq [e]^{-1}_{\varphi(n)}$$

$$\Huge \varphi(p) = p - 1$$

$$\Huge a \perp b \Rightarrow \varphi(a\cdot b) = \varphi(a) \cdot \varphi(b)$$

$$\Huge \qquad p, q, e \mapsto n, d$$

 

$$\Huge \begin{cases} n \triangleq p \cdot q\\ [d]_{(p - 1)(q - 1)} \triangleq [e]^{-1}_{(p - 1)(q - 1)} \end{cases} $$

$$\Huge \qquad n, d \not\mapsto p, q, e$$

 

$$\Huge \begin{cases} n \not\mapsto p, q, \varphi(n) \\ d \not\mapsto [d]^{-1}_{\varphi(n)} = [e]_{\varphi(n)} \end{cases} $$

$$\Huge F_n(m, x)$$

 

def f(m, n, x):
  M = Mod(n)
  return (M[m] ** x).rappresentante()

p = 55202166624234742076825422018198552545568721350927
q = 43045972142075202331028535612422134545369845034403
e = 65537

n = p * q
n

2376230926689002221115550421319780616625277750859317861401351698336471050024330021446449316950941581

M = Mod((p - 1) * (q - 1))
d = (M[e] ** (-1)).rappresentante()
d

701154365630284037290881701138012383299504419581543080721910924221824588942701573338487759909677721

prv = (n, e)
pub = (n, d)

m = a_numero('Bella lì!')
m

313547121747086721395745

MCD(m, n) == 1, m < n

(True, True)

c = f(m, *pub)
c

1538783477976996928634014774512899410342179052487146901742256323416866179187484958304791756168895087

da_numero(f(c, *prv))

'Bella lì!'

Firma digitale

s = f(m, *prv)
s

889083638752155628545502045048817268794357067783608461028896573341592978755168396208918521167789527

da_numero(f(s, *pub))

'Bella lì!'

Bibliografia e sitografia

• Libri

  David Kahn, "The Codebreakers: The Story of Secret Writing", Macmillan, 1967;

  Simon Singh, "The code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography", 2000.

• YouTube

  Diffie-Hellman Key Exchange e RSA Encryption Algorithm.

• Wikipedia

  Modular arithmetic, Extended Euclidean algorithm, Euler's totient function, Euler's theorem, Bezout's identity, Diffie-Hellman key exchange, RSA).

• Altro

  Big Ideas of Cryptography in K-12.