UNIVERSITA DEGLI STUDI DI PERUGIA1x 2:::::x n per ogni intero n 1, dove ogni simbolo in chiaro x i2P...

UNIVERSITA DEGLI STUDI DI PERUGIA

Facolta di Scienze Matematiche, Fisiche e Naturali

Corso di laurea specialistica in Informatica

Appunti di Crittografia

Studente: Professore:

Davide Tortoioli Prof. Massimo Giulietti

Anno Accademico 2009/2010

Indice

1 Crittografia Classica 4

1.1 Block Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.1.1 Shift Cipher (Cifrario di Cesare) . . . . . . . . . . . . . . . . . . 5

1.1.2 Substitution Cipher . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.1.3 Affine Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.1.4 Vigenere Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.1.5 Hill Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.1.6 Permutation Cipher . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2 Stream Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.2.1 LFSR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.3 Crittoanalisi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.3.1 Crittoanalisi del Substitution Cipher . . . . . . . . . . . . . . . . 17

1.3.2 Crittoanalisi dell’Affine Cipher . . . . . . . . . . . . . . . . . . . 18

1.3.3 Crittoanalisi di Vigenere . . . . . . . . . . . . . . . . . . . . . . . 20

1.3.4 Crittoanalisi di Hill . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1.3.5 Crittoanalisi di LFSR . . . . . . . . . . . . . . . . . . . . . . . . 24

2 Teoria di Shannon 26

2.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.2 Richiami di Probabilita . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.3 Segretezza Perfetta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.4 One-Time Pad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.5 Crittosistemi Prodotto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.5.1 Crittosistemi Prodotto Idempotente . . . . . . . . . . . . . . . . 35

3 Crittografia Simmetrica 37

3.1 Substitution-Permutation Network (SPN) . . . . . . . . . . . . . . . . . 37

3.1.1 Considerazione sulle S-box . . . . . . . . . . . . . . . . . . . . . . 40

1

Indice Indice

3.2 Crittoanalisi Lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.2.1 Piling-Up Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.2.2 Approssimazione lineare di un S-box . . . . . . . . . . . . . . . . 44

3.2.3 Attacco lineare ad un SPN . . . . . . . . . . . . . . . . . . . . . 46

3.3 Campi Finiti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.3.1 Costruzione di un campo finito . . . . . . . . . . . . . . . . . . . 52

3.4 DES (Data Encryption Standard) . . . . . . . . . . . . . . . . . . . . . . 56

3.4.1 Descrizione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.4.2 Analisi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

3.4.3 Varianti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.5 AES (Advanced Encryption Standard) . . . . . . . . . . . . . . . . . . . 63

3.5.1 Caratteristiche Generali . . . . . . . . . . . . . . . . . . . . . . . 63

3.5.2 Struttura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

3.5.3 Substitution Bytes . . . . . . . . . . . . . . . . . . . . . . . . . . 64

3.5.4 Shift Rows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.5.5 Mix Columns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.5.6 Key Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.6 Modi Operativi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

4 Funzioni Hash Crittografiche 70

4.1 Funzioni Hash e Data Integrity . . . . . . . . . . . . . . . . . . . . . . . 70

4.2 Sicurezza di una funzione hash . . . . . . . . . . . . . . . . . . . . . . . 71

4.2.1 Random Oracle Model . . . . . . . . . . . . . . . . . . . . . . . . 72

4.2.2 Algoritmi nel Random Oracle Model . . . . . . . . . . . . . . . . 73

4.2.3 Comparazione dei criteri di sicurezza . . . . . . . . . . . . . . . . 76

4.3 Funzioni Hash Iterative . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

4.3.1 Costruzione Merkle-Damgard (MD) . . . . . . . . . . . . . . . . 78

4.3.2 SHA-1 (Secure Hash Algorithm) . . . . . . . . . . . . . . . . . . 80

4.3.3 MAC (Message Authentication Codes) . . . . . . . . . . . . . . . 82

4.3.4 Un po di storia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

5 Crittografia Asimmetrica 89

5.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

5.2 Ulteriore teoria dei numeri . . . . . . . . . . . . . . . . . . . . . . . . . . 93

5.2.1 Algoritmo Euclideo . . . . . . . . . . . . . . . . . . . . . . . . . . 93

5.2.2 Metodo dell’elemento primitivo . . . . . . . . . . . . . . . . . . . 97

5.2.3 Teorema Cinese dei Resti . . . . . . . . . . . . . . . . . . . . . . 100

2

Indice Indice

5.2.4 Teorema di Eulero . . . . . . . . . . . . . . . . . . . . . . . . . . 102

5.3 RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

5.3.1 Complessita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

5.3.2 Test Probabilistici di primalita . . . . . . . . . . . . . . . . . . . 106

5.3.3 Algoritmi di Fattorizzazione . . . . . . . . . . . . . . . . . . . . . 110

5.4 Crittosistema ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

5.4.1 Algoritmi di risoluzione del DL-Problem . . . . . . . . . . . . . . 123

6 Firma Digitale 129

6.1 Schema SHA1WithRSA . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

6.2 Schema Elgamal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

6.3 Schema SHA1WithDSA . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

6.4 Funzionamento Pratico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

7 Elliptic Curve Cryptography (ECC) 137

7.1 Curve Ellittiche nei Reali . . . . . . . . . . . . . . . . . . . . . . . . . . 137

7.2 Curve Ellittiche in Fp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

7.3 Curve Ellittiche in F2m . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

7.4 Applicazione in Crittografia . . . . . . . . . . . . . . . . . . . . . . . . . 145

7.4.1 Generazione Chiavi . . . . . . . . . . . . . . . . . . . . . . . . . . 147

7.4.2 ECDSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

7.5 Vantaggi e Svantaggi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

7.5.1 Vantaggi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

7.5.2 Svantaggi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

3

Capitolo 1

Crittografia Classica

L’obiettivo fondamentale della crittografia e far si che due persone, comunemente

chiamate Alice e Bob, possano comunicare attraverso un canale insicuro, in un modo

tale da non permettere a Oscar (intruso o opponent) di capire cio che i due si stanno

dicendo. Per fare questo Alice cifra, con una funzione, il messaggio, usando una chi-

ave predeterminata, e trasmette il risultato attraverso il canale insicuro. Oscar puo

ascoltare la comunicazione, quindi conosce il testo cifrato ma non deve essere in grado

di risalire, tramite di esso, al testo in chiaro. Quando Bob riceve il messaggio cifrato gli

applica una funzione di decodifica, utilizzando la stessa chiave, e ottiene il messaggio

in chiaro.

Quest’idea e formalmente descritta usando la seguente notazione matematica.

Definizione 1 (Crittosistema). Un crittosistema e una 5-tupla (P, C,K, E ,D)dove le seguenti condizioni sono soddisfatte:

1. P e un insieme finito dei possibili plain text

2. C e un insieme finito dei possibili cipher text

3. K e un insieme finito delle possibili chiavi

4. ∀k ∈ K c’e una funzione di cifratura ek ∈ E e una corrispondente fun-zione di de-cifratura dk ∈ D dove ek : P → C e dk : C → P e ∀x ∈ P siha che dk(ek(x)) = x

4

1.1. Block Cipher Capitolo 1. Crittografia Classica

La proprieta piu importante e la 4. Essa specifica che, se un plaintext x viene cifrato

tramite ek e il risultante ciphertext viene decifrato tramite dk, allora il risultato di dk

deve essere x.

Questo proprieta (formale), pero, non basta noi vogliamo anche che:

1. Le funzioni ek e dk siano computazionalmente facili da calcolare

2. Sia computazionalmente difficile ricavare k da ek(m)

Alice e Bob devono seguire uno specifico protocollo per usare uno specifico crittosis-

tema. Per prima cosa, devono scegliere in maniera random una chiave k ∈ K. Questo

viene fatto o quando entrambi sono nello stesso luogo e senza nessuno che li osserva, o

mediante l’utilizzo di un canale sicuro.

Successivamente supponiamo che Alice voglia inviare un messaggio a Bob. Il mes-

saggio e rappresentato dalla stringa

x = x1x2.....xn

per ogni intero n ≥ 1, dove ogni simbolo in chiaro xi ∈ P con 1 ≤ i ≤ n. Ogni xi

viene cifrato ottenendo yi = ek(xi) e il risultato

y = y1y2.....yn

viene inviato nel canale. Quando Bob riceve la stringa decifra ogni yi con la funzione

dk ottenendo xi = dk(yi) con 1 ≤ i ≤ n.

1.1 Block Cipher

Sono quei tipi di cifrari per i quali la chiave di cifratura rimane costante nel tempo.

La lunghezza della chiave determina la lunghezza del blocco.

x1 → ek(x1)

x2 → ek(x2)...

xm → ek(xm)

1.1.1 Shift Cipher (Cifrario di Cesare)

E un cifrario che si basa sull’aritmetica modulare.

5


Definizione 2 (Congruenza). Siano a e b due interi e m un intero positivo.Diciamo che a ≡ b (mod m) se m | b − a. Si dice quindi che a e congruo bmodulo m. Due interi sono congrui modulo m sse divisi per m danno lo stessoresto.

Definizione 3 (Aritmetica Modulare). L’aritmetica modulare e definita dal-l’insieme Zm = {0, 1, 2, ....,m− 1} e dalle operazioni + e · che sono identichea quelle dell’aritmetica normale, quindi godono anche delle stesse proprieta,con la differenza che il risultato viene ridotto modulo m.

Il cifrario e cosı definito:

1. P = {A,B,C,D, ....,W,X, Y, Z} = {0, 1, 2, 3, 4, ...25} = Z26

2. C = Z26

3. K = Z26

4. ek(x) = x+ k (mod 26)

5. dk(y) = y − k (mod 26)

La proprieta formale e soddisfatta, come la proprieta sulla complessita computazionale

ma la 2 no; infatti con un semplice attacco di forza bruta e possibile determinare la

chiave.

Il problema e dovuto al fatto che il numero delle chiavi e molto piccolo, e quindi in

poco tempo posso provarle tutte.

1.1.2 Substitution Cipher

Questo crittosistema risolve il problema dovuto al fatto di avere poche chiavi ma

comunque non garantisce la sicurezza. E cosı definito:

1. P = {A,B,C,D, ....,W,X, Y, Z} = {0, 1, 2, 3, 4, ...25} = Z26

2. C = Z26

3. K = S26

4. ek(x) = eπ(x) = π(x) con π ∈ Sn

5. dk(y) = dπ(y) = π−1(y)

6


Definizione 4 (Sn). E l’insieme delle funzioni biiettive.

Sn = {π : {1, 2, 3, ..., n} → {1, 2, 3, ..., n}| π BIIETTIV A}

La cardinalita e: |Sn| = n! perche il primo elemento del dominio posso diassociarlo a n elementi, il secondo a n− 1.... l’n-esimo a 1.

Nel nostro caso, quindi, |S26| ∼ 4 · 1026. Questo significa che un attacco di forza

bruta diventa difficile da portare a termine, ma il cifrario e comunque soggetto ad altri

attacchi di tipo statistico, ossia posso basarmi sulle frequenze delle lettere dell’alfabeto

o sulle doppie o sulle regole semantiche del linguaggio (esempio se c’e la q c’e anche la

u vicino).

Quindi non e sufficiente avere un gran numero di chiavi per essere sicuri.

1.1.3 Affine Cipher

E una generalizzazione dello Shift Cipher ed e cosı definito:

1. P = {A,B,C,D, ....,W,X, Y, Z} = {0, 1, 2, 3, 4, ...25} = Z26

2. C = Z26

3. K = {(a, b) ∈ Z226 | gcd(a, 26) = 1} a

4. ek(x) = e(a,b)(x) = ax+ b (mod 26)

5. dk(y) = d(a,b)(y) = a−1(y − b) (mod 26)

agcd: Significa Greatest Common Divisor, ossia il massimo comune divisore

La funzione ek e detta funzione affine; con a = 1 otteniamo lo Shift Cipher.

Affinche questo sistema funzioni, pero, bisogna garantire che ek sia INIETTIVA, cioe

due elementi del dominio devono avere due immagini diverse nel codominio altrimenti

la fase di decodifica e impossibile, perche non ho piu la certezza di riottenere il testo in

chiaro.

Teorema 1 (F. INIETTIVA). Sia e(a,b) : Zm → Zm, x 7−→ ax+ b (mod m).

e(a,b) INIETTIV A⇐⇒ gcd(a,m) = 1

Dimostrazione. =⇒Supponiamo f INIETTIVA e mostriamo che gcd(a,m) = 1.ASSURDO: gcd(a,m) = d > 1

a · md

+ b ≡ b (mod m)

7


Se d > 1 significa che divide a e quindi posso semplificare ottenendo

a′ ·m+ b ≡ b (mod m)

Poiche m ≡ 0 (mod m) l’espressione diventa

b ≡ b (mod m)

Questo significa che ho x = md e x = 0 che mi danno lo stesso risultato, quin-

di la funzione non e INIETTIVA ma poiche e stato supposto vero, si e arrivati allacontraddizione e si e dimostrata l’implicazione.

⇐=Supponiamo che gcd(a,m) = 1 e mostriamo che f e INIETTIVA .ASSURDO: f NON INIETTIVA

ax+ b ≡ ax′ + b (mod m) con x 6≡ x′ (mod m)

ax ≡ ax′ (mod m)

ax− ax′ ≡ 0 (mod m)

a(x− x′) ≡ 0 (mod m)⇐⇒ m | a(x− x′)

Siccome gcd(a,m) = 1 si ha che

m | (x− x′)

e quindi

x ≡ x′ (mod m)

Definizione 5 (Inverso Moltiplicativo). L’inverso moltiplicativo e quel-l’elemento a−1 tale che a−1a ≡ 1 (mod m). Si puo calcolare sse f eINIETTIVA.

La cardinalita di K e |K| = 12 · 26 dove 26 sono i valori che puo assumere b e 12 i

valori plausibili per a (cioe quelli primi con m). Il numero di valori che puo assumere

a dipende da m ed e definito da φ(m), la funzione di eulero.

Definizione 6 (Funzione Toziente di Eulero). Sia m ≥ 2, m ∈ Z

φ(m) = #{a | 1 ≤ a < m ∧ gcd(a,m) = 1}

8


Teorema 2 (Funzione Toziente di Eulero). Fattorizziamo m con pi primidistinti

m = P r11 · Pr22 · ..... · P

rnn

φ(m) = Πni=1(P rii − P

ri−1i )

1.1.4 Vigenere Cipher

Sia nello Shift Cipher che nel Substitution Cipher ogni carattere viene mappato in

un unico carattere. Per questa ragione questi crittosistemi appartengono alla categoria

dei crittosistemi a sostituzione Mono alfabetica. Il cifrario di Vigenere invece adotta

una sostituzione Poli alfabetica ossia in punti diversi del testo, una stessa lettera puo

essere associata a due lettere diverse.

Questo cifrario e cosı definito:

1. P = Zm26 x = (x1, x2, ....., xm)

2. C = Zm26 y = (y1, y2, ....., ym)

3. K = Zm26 k = (k1, k2, ....., km)

4. ek(x) = e(k1,k2,....,km)(x1, x2, ....., xm) = (x1+k1 (mod 26), ......, xm+km

(mod 26))

5. dk(y) = d(k1,k2,....,km)(y1, y2, ....., ym) = (y1−k1 (mod 26), ......, ym−km(mod 26))

Il problema di questo cifrario e che la sostituzione dipende dalla posizione del plin-

text rispetto alla chiave, ossia se una lettera compare piu volte nella stessa posizione

rispetto alla chiave, avra la stessa codifica.

9


1.1.5 Hill Cipher

Questo crittosistema e un’altro esempio di cifrario poli alfabetico. Esso e cosı

definito:

1. P = Zm26 x = (x1, x2, ....., xm)

2. C = Zm26 y = (y1, y2, ....., ym)

3. K = {K ∈Mmxm| det(K) 6= 0 ∧ det(K) INV ERTIBILE in Z26}

4. eK(x) = (x1, x2, ....., xm) ·K (mod 26)

5. dK(y) = (y1, y2, ....., ym) ·K−1 (mod 26)

Bisogna garantire l’iniettivita di eK , affinche non sia possibile che due caratteri

ricevano la stessa codifica; questo e possibile verificando che la matrice K sia invertibile.

In R eK e invertibile o iniettiva se det(M) 6= 0. In Zn questa condizione non e sufficiente.

Teorema 3 (Funzione Invertibile). eK e invertibile/iniettiva ⇐⇒ det(K) 6= 0e e anche un elemento invertibile in Zn

Ossia la funzione e invertibile sse la matrice K e invertibile, cioe

KK−1 = K−1K = In

Per la fase di decodifica bisogna calcolare la matrice inversa K−1. Esistono due

metodi:

• Metodo della matrice dei cofattori

• Algoritmo Jordan-Gauss

Metodo della matrice dei cofattori

Sia A la matrice da invertire

A =

x1,1 · · · x1,j

.... . .

...

xi,1 · · · xi,j

la sua inversa e la seguente:

10


A−1 =1

det(A)

cof(A, x1,1) · · · cof(A, x1,j)...

. . ....

cof(A, xi,1) · · · cof(A, xi,j)

T

dove la notazione det(A) indica il determinante di A e l’esponente T indica l’oper-

azione di trasposizione. Il cofattore in posizione (i, j) e definito come:

cof(i, j) = (−1)i+j · det(minor(A, i, j))

dove minor(A, i, j) rappresenta la matrice ottenuta da A cancellando la riga i-esima

e la colonna j-esima.

Algoritmo Jordan-Gauss

Funziona nel modo seguente: sia A una matrice invertibile. Costruiamo la matrice

B = (A | I) con n righe e 2n colonne, costruita affiancando A e la matrice identita

I. A questo punto applichiamo l’algoritmo di Gauss-Jordan alla nuova B. Poiche A e

invertibile, le sue colonne sono indipendenti, e quindi conterranno tutte dei pivot alla

fine dell’algoritmo. Quindi il risultato sara una matrice del tipo (I | C). Ebbene la

matrice C e proprio l’inversa di A.

L’esempio seguente mostra che l’inversa di A e C

A =

(1 2

2 3

)

C =

(−3 2

2 −1

)

(A | I) =

(1 2‖1 0

2 3‖0 1

)=

(−2 −4‖ − 2 0

2 3‖0 1

)=

(−2 −4‖ − 2 0

0 −1‖ − 2 1

)=

(−2 −4‖ − 2 0

0 4‖8 −4

)=

(−2 0‖6 −4

0 4‖8 −4

)=

(1 0‖ − 3 2

0 1‖ − 2 1

)= (I | C)

Nel primo passaggio si e moltiplicata la prima riga per -2 e la si e sommata alla

seconda riga. Nel secondo passaggio si e moltiplicata la seconda riga per -4 e la si e

sommata alla prima riga. Infine nell’ultimo passaggio si e divisa la prima riga per -2 e

la seconda per 4.

11


1.1.6 Permutation Cipher

Il cifrario si basa sull’anagrammare le lettere di un blocco, seguendo una certa

funzione ∈ Sm. E possibile ridurlo ad un Hill Cipher.

1. P = Zm26 x = (x1, x2, ....., xm)

2. C = Zm26 y = (y1, y2, ....., ym)

3. K = Sm

4. ek(x) = eπ(x1, x2, ....., xm) = (xπ(1), xπ(2), ....., xπ(m))

5. dk(y) = dπ(y1, y2, ....., ym) = (yπ−1(1), yπ−1(2), ....., yπ−1(m))

E un cifrario debole perche il numero di chiavi non e eccessivamente elevato: m!.

ESEMPIO:

Scegliamo m = 6

Vogliamo codificare OGGI E MARTEDI

Prendiamo la chiave k = (135624)

OGGIEM → IMOGGE

Riduzione all’Hill Cipher

Questa trasformazione puo essere vista come una moltiplicazione tra il vettore e

un’opportuna matrice invertibile.

(14 6 6 8 4 12) ·

0 0 1 0 0 0

0 0 0 1 0 0

0 0 0 0 1 0

1 0 0 0 0 0

0 0 0 0 0 1

0 1 0 0 0 0

= (8 12 14 6 6 4)

k = (135624)

La chiave k dipende dalle posizioni degli uno nelle colonne.

Una matrice cosı fatta riduce enormemente il numero di chiavi, perche si usano solo

1 e 0 secondo un certo criterio mentre potrei scegliere da 0 a 25 in maniera del tutto

casuale, purche la funzione risulti una biiezione.

12

1.2. Stream Cipher Capitolo 1. Crittografia Classica

1.2 Stream Cipher

Gli Stream Cipher si differiscono dai Block Cipher per i fatto che la chiave cambia

nel tempo.

x1 → ez1(x1)

x2 → ez2(x2)...

xm → ezm(xm)

Stream Cipher Sincroni: La successione z1, z2, ..., zn, che costituisce la chiave, non

dipende dai testi in chiaro ma soltanto da una “master key”. Esso e definito dalla

7-tupla (P, C,K,L, E ,D,G) dove

• P: Insieme dei plaintext

• C: Insieme dei ciphertext

• K: Insieme delle possibili “master key”

• L: Insieme delle possibili chiavi “parziali”

• E : Insieme delle funzioni di cifratura

∀z ∈ L, ∃ez : P → C

• D: Insieme delle funzioni di de-cifratura

∀z ∈ L, ∃dz : C → P

• G: Insieme delle possibili successioni

g : K → LN

k 7−→ (z1, z2, ...., zn)

13


1.2.1 LFSR

L’acronimo sta per Linear Feedback Shift Register, ed e cosı definito:

• P = C = L = Z2 = {0, 1}

• ez(x) = x+ z (mod 2)→ x⊗ z

• dz(y) = y + z (mod 2)→ y ⊗ z

• K = Z2m2 con m ∈ Z,m > 0

k = (k1, k2, ..., km | c0, c1, ..., cm−1) con c0 obbligatoriamente 1, altrimenti

non considero le m posizioni precedenti ma le m− 1.

• g : K → LN

(k1, k2, ..., km | c0, c1, ..., cm−1) 7−→ (z1, z2, ..., zm)

g =

{zi = ki se i ≤ mzi+m =

∑m−1j=0 (cj · zi+j) (mod 2) else

N.B.: Le funzioni ez ed dz sono di facile implementazione hardware. Per quanto

riguarda g la prima parte della chiave mi serve per inizializzare la successione.

ESEMPIO:

m = 4

k = (1, 0, 0, 0 | 1, 1, 0, 0)

zi+4 = c0 · zi + c1 · z(i+1) + c2 · z(i+2) + c3 · z(i+3) → zi + z(i+1)

g =

z1 = 1

z2 = 0

z3 = 0

z4 = 0

zi+4 = zi + z(i+1) (mod 2)

Successione: 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 | 1 0 0 0

Mi fermo nel costruire la successione quando ripeto la sequenza iniziale. Nel caso

preso in esempio ho trasformato una chiave da 8 in una da 15.

14


Osservazione 1. La sequenza iniziale z1, z2, ..., zm si ripete al piu dopo 2m−1passi, perche le possibili sequenze binarie lunghe m sono 2m; il −1 indica lachiave con tutti gli ci = 0, che non posso usare altrimenti la successione saracomposta da tutti 0.

Per raggiungere il periodo massimo bisogna impostare adeguatamente gli ci.

Come si fa a capire quando una g e buona?

Definizione 7 (Polinomio caratteristico di un LFSR). Il POLINOMIOCARATTERISTICO di un LFSR e cosı definito:

f(x) = c0 + c1 · x+ c2 · x2 + · · ·+ cm−1 · xm−1 + xm ∈ Z2[X]

Teorema 4 (Polinomio Caratteristico). Se il Polinomio Caratteristico e ir-riducibile (cioe non si puo scrivere come il prodotto di due o piu polinomi)allora la sequenza iniziale si ripete dopo i passi con i | 2m − 1

ESEMPIO:

m = 4

k = (1, 0, 0, 1 | 1, 0, 1, 1)

Successione: 1 0 0 1 0 1 1 | 1 0 0 1→ PERIODO 7

7 6 | 24 − 1→ POLINOMIO RIDUCIBILE

f(x) = 1 + x2 + x3 + x4

———————–

m = 4

k = (1, 0, 0, 1 | 1, 1, 1, 1)

Successione: 1 0 0 1 0 | 1 0 0 1→ PERIODO 5

5 | 24 − 1→ POLINOMIO IRRIDUCIBILE

f(x) = 1 + x+ x2 + x3 + x4

Quando il periodo e il piu lungo possibile?

Definizione 8 (Divisione fra Polinomi). Dati due polinomi f e g con g 6= 0esistono e sono unici q e r tali che

f = g · q + r

con deg(r) < deg(g) .

15


ESEMPIO:

x4 + x2 + x x2 + 1

−x4 − x2 x2

x

x4 + x2 + x ≡ x (mod x2 + 1)

Definizione 9 (Polinomio Primitivo). Sia f(x) un polinomio a coefficientibinari (Z2[x]) se i monomi 1, x, x2, x3, · · · , x2m−2 sono distinti modulo f(x).

ESEMPIO: f(x) = 1 + x+ x2 + x3 + x4 e primitivo?

1 (mod f(x)) = 1

x (mod f(x)) = x

x2 (mod f(x)) = x2

x3 (mod f(x)) = x3

x4 (mod f(x)) = 1 + x2 + x3

x5 (mod f(x)) = 1

Questo polinomio non e primitivo, infatti come si puo vedere, il periodo e minore

di 2m − 1

Teorema 5 (Periodo massimo). Il periodo di LFSR e 2m − 1 ⇐⇒ il suopolinomio caratteristico e primitivo.

Teorema 6 (Esistenza Polinomio Primitivo). ∀m,∃ almeno un polinomioprimitivo di grado m.

Semplificazione Hardware

E molto semplice costruire un dispositivo hardware che implementa tale cifrario.

Infatti basta utilizzare uno Shift Register e delle porte logiche XOR.

ESEMPIO:

k = (1, 0, 1, 0, 1, 1, 0 | 1, 0, 1, 0, 1, 0, 1)

Utilizzo uno shift register da 7 bit e 4 porte.

16

1.3. Crittoanalisi Capitolo 1. Crittografia Classica

1.3 Crittoanalisi

Con il termine crittoanalisi si intende lo studio dei metodi per ottenere il significato

di informazioni cifrate senza avere accesso all’informazione segreta che e di solito richi-

esta per effettuare l’operazione. Tipicamente si tratta di trovare una chiave segreta.

La crittoanalisi e la controparte della crittografia.

Definizione 10 (Principio di Kerkoffs). Un crittosistema deve essere sicuroanche se il suo funzionamento e di pubblico dominio, con l’eccezione dellachiave. La sicurezza di un crittosistema dipende solo dalla segretezza dellachiave.

Esistono 4 tipologie di attacchi ad un crittosistema (attack model):

• Cipher Text Only : L’hacker dispone soltanto di ek(x)

• Known Plaintext : L’hacker dispone di x e di ek(x)

• Chosen Plaintext : L’hacker puo inviare un messaggio cifrato a bob. Puo quindi

scegliere x e ricavarne ek(x)

• Chosen Ciphertext : L’hacker puo scegliere il testo cifrato y e ricavarne dk(y)

Se il sistema e sicuro per la soluzione piu facile per l’hacker (Chosen Ciphertext) lo

sara ancora di piu per quelle piu difficili.

1.3.1 Crittoanalisi del Substitution Cipher

Esso e fragile all’attacco Cipher Text Only.

Assumiamo che il testo in chiaro sia un testo in Inglese senza spazi. Molte tecniche

di crittoanalisi usano proprieta statistiche della lingua Inglese. Questo perche una

sostituzione mono alfabetica non altera queste proprieta che sono:

• Frequenze delle lettere

Le lettere possono essere divise, in base alle frequenza, in 5 gruppi:

1. E : La lettera con frequenza maggiore

2. T,A,O,I,N,S,H,R: Con frequenza compresa tra 0.06 e 0.09

3. D,L: Con frequenza intorno a 0.04

4. C,U,M,W,F,G,Y,P,B: Con frequenza compresa tra 0.015 e 0.028

17


5. V,K,J,X,Q,Z : Che hanno frequenza minore di 0.01

• Digrams e Trigrams

Sono sequenze di 2-3 lettere, tipo TO, ON, THE, AND ecc...

Quando si riceve un testo si calcolano le frequenze delle lettere nel testo cifrato.

Poiche le frequenze non vengono alterate siamo sicuri che la lettera che compare con il

maggior numero di frequenze e sicuramente la E. Successivamente si cerca di trovare un

assegnamento per il secondo gruppo procedendo per tentativi. Si ripete il procedimento

fino alla fine.

Chiaramente una cosa del genere e possibile se il testo cifrato che riusciamo a

recuperare e ragionevolmente lungo; infatti se il testo e corto e possibile che le frequenze

risultino sballate.

Un’analisi del genere ci permette di ridurre di molto il tempo di decrittazione

ottenuto con un algoritmo di forza bruta.

1.3.2 Crittoanalisi dell’Affine Cipher

Esso, come il precedente, e fragile all’attacco Cipher Text Only, pero l’Affine e piu

fragile in quanto basta indovinare due lettere e si riesce a trovare la chiave.

Esso effettua una sostituzione mono alfabetica, quindi si presta bene anche ad un

attacco di tipo Cipher Text Only. In realta e piu facile rompere l’Affine piuttosto che il

Substitution; siccome la chiave e fatta di due incognite mi basta azzeccare due lettere

per avere un sistema di due equazione e due incognite e quindi anche una sua soluzione,

che sara la chiave.

Supponiamo di voler decifrare il seguente testo

18


FMXV EDKAPHFERBN...

Per prima cosa calcoliamo le frequenze:

D = 7

E = 5

H = 5

K = 5

R = 8

IPOTESI:

E → R cioe 4→ 17

T → D cioe 19→ 3

Quindi otteniamo il sistema seguente:{17 = 4a+ b (mod 26)

3 = 19a+ b (mod 26)

Dato che ho due uguaglianze per il momento tralascio b ed eseguo la differenza tra

le due

{−14 = 15a (mod 26)

−−−−−−−

{a = 12 · 15−1 (mod 26)

−−−−−−−{a = 12 · 7 (mod 26) = 84 (mod 26) = 6

−−−−−−−

Il metodo per trovare l’inverso di un numero (a−1) verra presentato piu avanti.

a = 6 non e un valore accettabile perche deve essere primo con 26 (gcd(6, 26) 6= 1).

IPOTESI:

E → R cioe 4→ 17

T → K cioe 19→ 10

19


Quindi otteniamo il sistema seguente:{17 = 4a+ b (mod 26)

10 = 19a+ b (mod 26)

Dato che ho due uguaglianze per il momento tralascio b ed eseguo la differenza tra

le due {−7 = 15a (mod 26)

−−−−

{a = 19 · 15−1 (mod 26)

−−−−−−−{a = 19 · 7 (mod 26) = 133 (mod 26) = 3

−−−−−−−

a = 3 e accettabile quindi calcoliamo b per sostituzione da una delle due uguaglianze

17 = 4 · 3 + b→ b = 5

Quindi si ha che

dk(y) = (y − 5) · 3−1 → (y − 5) · 9

1.3.3 Crittoanalisi di Vigenere

Anch’esso e fragile ad un attacco Cipher Text Only, ma poiche adotta una sosti-

tuzione poli alfabetica il procedimento di crittoanalisi e leggermente piu complicato ma

comunque computazionalmente leggero.

La fragilita di vigenere e dovuta al fatto che se si riesce ad individuare m poi, il

problema, si riconduce ad una sostituzione mono alfabetica di tipo shift, cioe la piu

semplice da rompere.

Osservazione 2 (Kasiski). Se nel testo cifrato compare piu volte una stessasequenza di 3 o piu lettere questo probabilmente non e casuale ma indica chela sequenza occupa la stessa posizione nell’ambito del proprio blocco. Quindipossiamo affermare che m divide la distanza tra le posizioni delle due sequenzeidentiche.

Test di Kasiski: Si considerano nel ciphertext tutte le distanze δ1, δ2, · · · , δn fra

sequenze di lettere uguali e lunghe almeno 3. Si ipotizza che m = gcd(δ1, δ2, · · · , δn)

20


Osservazione 3 (Friedman). Se m e la lunghezza della chiave allora lesequenze cosı ottenute

s1 = y1, ym+1, y2m+1 · · ·

s2 = y2, ym+2, y2m+2 · · ·...

sm = ym, y2m, y3m · · ·

prese singolarmente sono il risultato di una sostituzione mono alfabetica, ditipo shift, perche ad ogni posizione nella sequenza aggiungo sempre la stessaquantita.

Ora bisogna capire quando una sostituzione e mono alfabetica.

Una sostituzione e mono alfabetica quando la distribuzione delle frequenze “somigli-

a” a quella del linguaggio naturale, oppure quando l’ indice di coincidenza del linguag-

gio naturale e molto vicino a quello del testo cifrato.

Indice di coincidenza: Probabilita che prese due lettere a caso, queste siano uguali

(dipende dal linguaggio).

Calcolo dell’indice per il linguaggio naturale

Ind.co. = Prob. 2 A+ Prob. 2 B + · · ·+ Prob. 2 Z =

P 2A + P 2

B + · · ·+ P 2Z =

(0, 082)2 + (0, 015)2 + · · ·+ (0, 001)2 = 0, 065

Calcolo dell’indice per il Ciphertext

Ricordiamo:(nk

)= n!

k!·(n−k)! e di conseguenza(n2

)= n(n−1)

2 che indica il numero di

modi per scegliere due caratteri.

Ind.co. =

(PA2

)(n2

) +

(PB2

)(n2

) + · · ·+(PZ2

)(n2

)Ind.co. =

1n(n−1)

2

·∑x∈Z26

fx · (fx − 1)

Se questo numero e molto vicino a 0.065 allora la sostituzione e mono alfabetica.

Test di Friedman: Si cerca m andando per tentativi. Si considerano le sequenze

21


s1, s2, · · · , sm. Si calcola l’indice di coincidenza di ciascuna sequenza si. Se tale indice

∀i e vicino a 0,065 allora si accetta m come lunghezza della chiave.

A questo punto il gioco e fatto, perche in questo caso per rompere il cifrario basta

indovinare una sola lettera.

Sia α la lettera piu frequente nella sequenza i-esima, allora ipotizzo

E → α

4→ nα

nα = 4 + ki

ki = nα − 4

Ripeto il procedimento ∀i cioe per ogni sequenza.

1.3.4 Crittoanalisi di Hill

Effettuare un attacco di tipo Cipher Text Only e impraticabile, in quanto questo

cifrario somiglia molto a Vigenere ma usa una trasformazione piu complicata. E invece

vulnerabile ad un attacco Known Plaintext.

ESEMPIO:

m=2

friday → PQCFKU

(5, 17, 8, 3, 0, 24)→ (15, 16, 2, 5, 10, 20)

Conoscendo queste poche informazioni l’hacker puo impostare un sistema di 4

equazioni e 4 incognite e risolvere il problema.

Sappiamo che:

(5, 17) ·

(a b

c d

)= (15, 16)

(8, 3) ·

(a b

c d

)= (2, 5)

Da qui costruiamo il seguente sistema:

22


5a+ 17c = 15

5b+ 17d = 16

8a+ 3c = 2

8b+ 3d = 5

Otteniamo due sistemi piu piccoli:{5a+ 17c = 15

8a+ 3c = 2

{5b+ 17d = 16

8b+ 3d = 5

Risolviamo il primo:

{5a+ 17c = 15

8a+ 3c = 2={

13a+ 20c = 17 ={

2 · (13a+ 20c = 17) ={

26a+ 40c = 34

Poiche 26 ≡ 0 (mod 26)

{40c = 34 =

{14c = 8 =

{7c = 4 =

{c = 4 · 7−1 = 4 · 15 = 8

Quindi

{c = 8

5a+ 17 · 8 = 15=

{c = 8

5a = 9=

{c = 8

a = 9 · 5−1 = 9 · 21=

{c = 8

a = 7

Risolviamo il secondo:

{5b+ 17d = 16

8b+ 3d = 5=

{−−−−−−−3d = 5− 8b

=

{−−−−−d = (5− 8b) · 9 = 45− 72b

=

{5b+ 17 · (45− 72b) = 16

−−−−−=

{5b+ 11− 2b = 16

−−−−−=

{3b = 5

−−−−−=

{b = 19

d = 45− 72 · 19=

{b = 19

d = 3

Ora conosciamo la matrice chiave e per verifica controlliamo che

(0, 24) ·

(7 19

8 3

)= (10, 20)

23


1.3.5 Crittoanalisi di LFSR

Il cifrario e fragile ad un attacco di tipo Known Plaintext.

Supponiamo di intercettare il seguente testo cifrato

y = 101101011110010

Non esiste un metodo semplice per effettuare un attacco Cipher Text Only spe-

cialmente se il periodo e molto grande, mentre invece e molto semplice effettuare un

attacco Known Plaintext.

m = 5

x = 011001111111000 ⊗y = 101101011110010

z = 110100100001010

Gia abbiamo recuperato meta chiave, infatti

k = (1, 1, 0, 1, 0 | c0, c1, c2, c3, c4)

Poiche

(zm+1, zm+2, · · · , z2m) = (c0, c1, · · · , cm−1) ·

z1, z2, · · · , zmz2, z2, · · · , zm+1

...

zm, zm+1, · · · , z2m

Applicato all’esempio diventa

(0, 1, 0, 0, 0) = (c0, c1, c2, c3, c4) ·

1 1 0 1 0

1 0 1 0 0

0 1 0 0 1

1 0 0 1 0

0 0 1 0 0

Per ricavare gli ci, ho troviamo la matrice inversa e la moltiplichiamo per il (0, 1, 0, 0, 0)

oppure risolviamo il seguente sistema:

24


0 = c0 + c1 + c3

1 = c0 + c2

0 = c1 + c4

0 = c0 + c3

0 = c2

0 = c0 + c1 + c3

1 = c0

0 = c1 + c4

0 = 1 + c3

0 = c2

0 = 1 + c1 + c3

1 = c0

0 = c1 + c4

1 = c3

0 = c2

0 = 1 + c1 + 1

1 = c0

0 = c1 + c4

1 = c3

0 = c2

0 = c1

1 = c0

0 = c4

1 = c3

0 = c2

k = (1, 1, 0, 1, 0 | 1, 0, 0, 1, 0)

Teorema 7. Dato un LFSR di ordine m i valori z1, z2, · · · , z2m danno luogoad un sistema lineare in c0, c1, · · · , cm−1 avente un’unica soluzione.

25

Capitolo 2

Teoria di Shannon

2.1 Introduzione

Nel 1949, Claude Shannon pubblico un articolo chiamato “Comunication Theory of

Secret System”. Questo articolo ebbe un’enorme influenza nel campo della crittografia.

In questo capitolo verranno presentate molte delle idee di Shannon. Per prima cosa

consideriamo alcuni approcci per valutare la sicurezza di un crittosistema. I criteri di

valutazioni piu comuni sono:

Computational Security . Un crittosistema viene definito computazionalmente si-

curo se il miglior algoritmo conosciuto, per rompere il crittosistema, richiede un

numero esponenziale di operazioni.

Provable Security . Un altro approccio e provare matematicamente la sicurezza uti-

lizzando la tecnica della riduzione, che ci permette di accostare questo problema

ad un problema NP-Complete.

Unconditional Security . Un crittosistema e definito sicuro se non puo essere rotto

con una quantita infinita di risorse.

Shift Cipher, Substitution Cipher e Vigenere sono computazionalmente sicuri contro

un attacco Ciphertext Only, ma sono insicuri contro un attacco Known Plaintext;

One-Time Pad e unconditional security..

2.2 Richiami di Probabilita

Variabile Aleatoria Discreta . E una coppia (X , p) tale che

• Dominio: X = {x1, x2, · · · , xn}

• Distribuzione di Probabilita: p : X → [0, 1] con∑n

i=1 p(xi) = 1

26

2.2. Richiami di Probabilita Capitolo 2. Teoria di Shannon

Prodotto di Var. Aleatorie Discrete : Date due variabili aleatorie X e Y il prodot-

to e

X · Y = {(xi, yj)} → prodotto cartesiano dei domini.

Ogni coppia ha una p(xi, yj) che e il prodotto delle due prob. se le variabili sono

indipendenti.

Definizione 11 (Variabili Indipendenti). X e Y sono INDIPENDENTI se

p(X = xi ∧ Y = yi) = p(X = xi) · p(Y = yi)

ESEMPIO (Non Indipendenti):

X = {1, 2, 3, 4, 5, 6}

p(X = xi) = 16

Y = {PARI, DISPARI}

p(Y = yi) = 12

p(X = 2 ∧ Y = DISPARI) = 0 6= 16 ·

12

Probabilita Condizionata .

p(X = xi | Y = yi) =p(X = xi ∧ Y = yi)

p(Y = yi)

con p(Y = yi) > 0

E l’intersezione

27

2.3. Segretezza Perfetta Capitolo 2. Teoria di Shannon

Teorema di Bayes .

p(Y = yi) · p(X = xi | Y = yi) = p(X = xi ∧ Y = yi)

p(X = xi) · p(Y = yi | X = xi) = p(Y = yi ∧ X = xi)

Poiche le due quantita sono uguali otteniamo:

p(X = xi | Y = yi) =p(X = xi) · p(Y = yi | X = xi)

p(Y = yi)

p(Y = yi | X = xi) =p(Y = yi) · p(X = xi | Y = yi)

p(X = xi)

2.3 Segretezza Perfetta

Le variabili aleatorie di un crittosistema sono:

• X = {x1, x2, · · · , xn} → possibili testi in chiaro

• K = {k1, k2, · · · , kh} → possibili chiavi

• Y = {y1, y2, · · · , yn} → possibili testi cifrati

Chiaramente X e Y sono indipendenti tra loro, mentre Y e dipendente proprio da

X e Y.

p(Y = yi) =∑

(xj ,kl)|ekl (xj)=yi

p(X = xj ,K = kl) =∑

(xj ,kl)|ekl (xj)=yi

p(X = xj) · p(K = kl)

Definizione 12 (Segretezza Perfetta). Un crittosistema realizza segretezzaperfetta se ∀i, j

p(X = xi | Y = yj) = p(X = xi)

Cioe la conoscenza del cipher text non mi da nessuna informazione aggiuntiva.

Conoscerla o meno e indifferente.

Introduciamo il concetto di Matrice di Codifica che ci servira a trovare le probabilita.

28


Definizione 13 (Matrice di codifica). E una matrice le cui colonne corrispon-dono a testi in chiaro e le righe alle possibili chiavi. La cella (xi, kj) contienela codifica ekj (xi).

Osservazione 4 (Cardinalita di P e C). Su ogni riga una y ∈ Y puo comparireal massimo una volta, altrimenti ek non e invertibile/iniettiva. Ne consegueche |P| ≤ |C|

Consideriamo

p1 = p(X = x1) p1 = p(K = k1)

p1 = p(X = x2) p2 = p(K = k2)...

pn = p(X = xn) pk = p(K = kh)

Sappiamo che :

p(X = xi | Y = yj) = p(X = xi)→p(X = xi ∧ Y = yj)

p(Y = yj)= p(X = xi)

p(X = xi ∧ Y = yj)→ Nella colonna di xi considero le caselle dove compare yj

e sommo le probabilita′ corrispondenti

p(Y = yj)→ Sommo le probabilita′ di tutte le caselle dove compare yj

ESEMPIO (Shift Cipher con alfabeto ∈ Z4):

p1, p2, p3, p4 dipendono dal linguaggio

p1, p2, p3, p4 = 14

p(X = 2 | Y = 3) =p(X = 2 ∧ Y = 3)

p(Y = 3)=

p34

p14 + p2

4 + p34p44

=p3414

= p3 = p(X = 2)

Bisogna fare questo controlla ∀x, y; comunque lo shift cipher realizza la segretezza

perfetta. La Figura 2.3 mostra la matrice di codifica dell’esempio appena descritto.

ESEMPIO 2:

P = {0, 1}K = {k1, k2, k3}C = {A,B,C,D}Se vedo passare A o D capisco gia qual e la chiave.

29


p(X = 0 | Y = A) =1818

= 1 6= p(X = 0)

p(X = 1 | Y = A) =018

= 0 6= p(X = 1)

Questo cifrario non realizza la segretezza perfetta.

Osservazione 5. Se c’e segretezza perfetta allora:

• Ogni y ∈ C compare in ogni colonna almeno una volta. Se per assurdonon comparisse mai si avrebbe

p(X = xi | Y = yi) = 0

Ossia l’hacker in fase di decodifica puo scartare la xi

• Ne segue che |C| ≤ |K|

Teorema 8 (Segretezza Perfetta). Per semplicita supporremo che |P| = |C| =|K|.

SEGRETEZZA PERFETTA ⇐⇒

p(K = kl) = 1

|K|

∀x ∈ P,∀y ∈ C ∃k ∈ K | y = ek(x)

30


La prima affermazione significa che le chiavi sono equiprobabili.

La seconda affermazione significa che ∀y ∈ C y compare esattamente una volta in

ogni colonna. Poiche |P| = |C| compare solo una volta anche su ogni riga.

Dimostrazione. ⇐=

Calcoliamo p(X = xi | Y = yj)

p(X = xi | Y = yj) =p(X = xi ∧ Y = yj)

p(Y = yi)=

pi · 1|K|

p(Y = yj)=

pi · 1|K|

p1|K| + p2

|K| + · · ·+ pn|K|

=

pi · 1|K|

1|K|

= pi = p(X = xi)

=⇒

Gia sappiamo dall’Osservazione 5 che su ciascuna colonna ogni y compare almenouna volta. In realta compare esattamente una volta in quanto abbiamo supposto|C| = |K|. Inoltre sappiamo dall’Osservazione 4 che ogni y ∈ C compare in ogni rigaesattamente una volta in quanto |P| = |C|. Quindi abbiamo gia dimostrato la secondaaffermazione; ora mostriamo la seconda:

IPOTESI: p(X = xi | Y = yj) = pi

p(X = xi | Y = yj) = pi →p(X = xi ∧ Y = yj)

p(Y = yi)= pi →

pi · plp(Y = yj)

= pi

plp(Y = yj)

= 1→ pl = p(Y = yj)

Siamo arrivati ad una conclusione che non dipende da xi. Quindi p(Y = yj) ecostante e ripartito per tutti gli elementi di |C|, cioe

pl =1

|C|=

1

|K|perche abbiamo supposto |C| = |K|.

31

2.4. One-Time Pad Capitolo 2. Teoria di Shannon

2.4 One-Time Pad

E un cifrario che realizza la segretezza perfetta. E identico a vigenere soltanto che

usa una chiave grande quanto il messaggio da inviare.

E cosı definito:

• P = ZM2

• C = ZM2

• K = ZM2

• ek(x) = (x1 ⊗ k1, · · · , xn ⊗ kn)

• dk(x) = (y1 ⊗ k1, · · · , yn ⊗ kn)

Teorema 9. Il One-Time Pad realizza segretezza perfetta se ogni chiavecompare con la stessa probabilita, cioe

pl =1

2M

Dimostrazione. Fisso X = (x1, x2, · · · , xM ) e Y = (y1, y2, · · · , yM ).

Mi chiedo, quante chiavi K = (k1, k2, ·, kM ) sono tali che ek(x) = y?

(x1 ⊗ k1, · · · , xn ⊗ kn) = (y1, y2, · · · , yM )→

x1 ⊗ k1 = y1

x2 ⊗ k2 = y2...xn ⊗ kn = yn

=

k1 = y1 ⊗ x1

k2 = y2 ⊗ x2...kn = yn ⊗ xn

Quindi k esiste ed e unica.

Vantaggio: Segretezza Perfetta

Svantaggio 1: Scambio della chiave di grande dimensione. Qui si crea un parados-

so perche se io sono in grado di comunicare in modo sicuro la chiave tanto vale che

comunico il messaggio

Svantaggio 2: Una volta utilizzata la chiave deve essere cambiata in quanto la

lunghezza del testo e variabile e in piu il cifrario e vulnerabile ad un attacco known

plaintext.

32

2.5. Crittosistemi Prodotto Capitolo 2. Teoria di Shannon

Per questi motivi viene usato solo in ambito militare, ma non ha senso usarlo in am-

bito commerciale. La nuova frontiera della Crittografia Quantistica potrebbe risolvere

lo svantaggio 1.

2.5 Crittosistemi Prodotto

L’obiettivo e tentare di aumentare la sicurezza usando crittosistemi diversi o anche

sempre lo stesso e ripeterlo piu volte.

Supponiamo |P| = |C| e siano S1 e S2 due crittosistemi cosı definiti:

S1 = (P,P,K1, E1,D1)

S2 = (P,P,K2, E2,D2)

S1xS2 = (P,P,K1xK2, E ,D)

con

K1xK2 = {(k1, k2) | k1 ∈ K1 ∧ k2 ∈ K2}

ek(x) = e(k1,k2)(x) = ek2(ek1(x))

dk(y) = d(k1,k2)(y) = dk1(dk2(y))

ESEMPIO:

S1 = Vigenere

S2 = Hill

S1 = (Zm26, Zm26, Z

m26, E1,D1)

con ek(x) = e(k1,···,km)(x1, · · · , xm) = (x1+k1 (mod 26), · · · , xm+km (mod 26))

S2 = (Zm26, Zm26, {K ∈Mmm | gcd(det(K), 26) = 1}, E1,D2)

con eK(x) = eK(x1, · · · , xm) = (x1, · · · , xm) ·K

S1xS2 = (Zm26, Zm26, {(k,K) | k ∈ Zm26 ∧K ∈Mmxm : gcd(det(K), 26) = 1}, E ,D)

con ek(x) = e(k,K)(x1, · · · , xm) = (x1 + k1, · · · , xm + km) ·K

33


Proprieta dei Crittosistemi Prodotto

• Associativa: (S1xS2)xS3 = S1x(S2xS3)

• No Commutativa: S1xS2 6= S2xS1 come la composizione di funzioni

Definizione 14 (Sn). Dato un crittosistema S si pone

Sn = S · S · S · S︸︷︷︸n volte

AES e DES sono di tipo Sn. In generale puo accadere che applicare n volte lo stesso

crittosistema non aumenti la sicurezza. Non e detto che prendendo un S qualunque Sn

risulti piu sicuro.

Definizione 15 (Crittosistema Idempotente). S si dice idempotente se S2 =S e quindi anche se Sn = S.

Definizione 16 (Crittosistemi Uguali). Due crittosistemi si consideranouguali se hanno uguali |P|, |C| e FUNZIONI DI CODIFICA e inoltre le proba-bilita su P e su C sono le stesse (cioe la probabilita che dato un testo in chiarox ∈ P si ottenga un determinato y ∈ C, e la probabilita che dato un testocifrato y ∈ C si ottenga un determinato x ∈ P, siano le stesse in entrambi icrittosistemi ∀x ∈ P e ∀y ∈ C).

Teorema 10 (Cifrari Idempotenti). I cifrari Shift, Vigenere, Hill,Permutazione e Sostituzione sono idempotenti.

Dimostrazione. Hill:

S2 = (Zm26, Zm26, {(A,B) |A,B ∈Mmxm ∧ gcd(det(A), 26) = 1 e gcd(det(B), 26) = 1}, E ,D)

ek(x) = e(A,B)(x1, · · · , xm) = ((x1, · · · , xm)·A)·B = (x1, · · · , xm)·(AB) = (x1, · · · , xm)·K

La funzione codifica si riduce ad una moltiplicazione di un vettore per una matrice.

Qual e la probabilita della funzione (y1, · · · , ym)→ (x1, · · · , xm) ·K?

Prob. =|{A | gcd(det(A), 26) = 1|}{|A | gcd(det(A), 26) = 1|}2

=1

{|A | gcd(det(A), 26) = 1|}= p(K = k) in S

34


2.5.1 Crittosistemi Prodotto Idempotente

Molti dei block cipher moderni sono dei product cipher. Questi product cipher,

spesso, incorporano una sequenza di permutazioni e sostituzioni. Uno schema di uso

comune e l’iterated cipher, cioe la stessa sequenza di operazioni viene ripetuta un certo

numero di volte (round) con la possibilita di variare la round function e la chiave (key

schedule).

Il problema e: Come posso trovare S : S 6= Sn?

Provo ad utilizzare come S un crittosistemi prodotto S = S1xS2, in modo tale da

avere (S1xS2)2 6= S1xS2.

Osservazione 6 (Crittosistema Prodotto Idempotente). Un crittosistemaprodotto e idempotente se:

• Se S1xS2 = S2xS1

• Se S21 = S1, S

22 = S2

Perche in tal caso:

(S1xS2)2 = S1xS2xS1xS2 = S1xS1xS2xS2 = S21xS2

2 = S1xS2

Proposizione 1. Il prodotto di due crittosistemi idempotenti che commutanofra di loro e anch’esso idempotente.

ESEMPIO:

S1 = VIGENERE

S2 =HILL

S1xS2 e idempotente?

S1 e S2 sono idempotenti. Quindi devo controllare se commutano.

S1xS2 : x→ x+ k (mod 26)→ A · (x+ k (mod 26)) = Ax+Ak

S2xS1 : x→ Ax→ Ax+ k

Anche se formalmente sono diversi bisognera controllare le probabilita, e vedremmo

che in realta le due funzioni di codifica sono uguali.

35


ESEMPIO DI CRITTOSISTEMI CHE NON COMMUTANO:

S1 = VIGENERE con m=2

S2 =PERMUTATION con chiave fissa (123) e m=3

Proviamo con le matrici di codifica che S1xS2 6= S2xS1, prendendo in considerazione

solo parole lunghe 3 per questioni di tempo e spazio.

Come possiamo vedere i due cifrari hanno funzioni diverse quindi S1xS2 non e

IDEMPOTENTE. Come controprova occorrerebbe costruire la matrice di codifica di

(S1xS2)2 e verificare effettivamente che e diversa da quella di S1xS2. La matrice e

composta da 16 chiavi che e il prodotto del numero di chiavi del primo cifrario per il

numero di chiavi del secondo:

(123), 00, (123), 00

(123), 01, (123), 00

(123), 10, (123), 00...

(123), 11, (123), 11

Il trucco della permutazione a chiave fissa, che e apparentemente banale, e quello

che viene usato nei crittosistemi simmetrici moderni.

36

Capitolo 3

Crittografia Simmetrica

3.1 Substitution-Permutation Network (SPN)

Un SPN e uno speciale tipo di iterated cipher. L’idea che sta alla base dell’SPN e

quella di considerare un crittosistema di tipo Sn dove S = S1xS2xS3 con

• S1 = VIGENERE

• S2 = SUBSTITUTION (a chiave fissa)

• S3 = PERMUTATION (a chiave fissa)

Supponiamo di lavorare con un alfabeto binario (Z2) e che i blocchi siano lunghi n

con n = lm dove n, l,m sono interi.

Un SPN e creato mediante due operazioni:

• πS : {0, 1}l → {0, 1}l

• πP : {1, 2, · · · , lm} → {1, 2, · · · , lm}

La permutazione πS viene anche detta S-box ; la “S” indica che e una sostituzione e

per di piu e a chiave fissa. Essa viene usata per sostituire l bit con un differente insieme

di l bit. πP e un’altra funzione usata per permutare lm bit.

Definizione 17 (Substitution-Permutation Network). Siano l,m e Nr interipositivi, sia πS : {0, 1}l → {0, 1}l una permutazione e sia πP : {1, 2, · · · , lm} →{1, 2, · · · , lm} un’altra permutazione. Siano P = C = {0, 1}lm, e siaK ⊆ ({0, 1}lm)Nr+1 che consiste nei possibili key schedule che possono es-sere derivati da una chiave iniziale K usando un algoritmo per generare unkey schedule.

Data una stringa di lm bit x = (x1, x2, · · · , xlm), puo essere vista come una con-

catenazione di m stringhe di lunghezza l indicati con i simboli x<1>, · · · , x<m> dove

37

3.1. Substitution-Permutation Network (SPN) Capitolo 3. Crittografia Simmetrica

x<i> = (x(i−1)l+1, · · · , xil)

L’SPN consiste in Nr round. In ogni round, eccetto per gli ultimi due vengono

effettuate m sostituzioni usando πS e una permutazione usando πP .

La Figura 3.1 mostra lo pseudo-codice del crittosistema.

Figura 3.1: SPN Didattico - pseudo-codice

La Figura 3.2 mostra lo schema di un SPN didattico con n = 16, m = 4, l =

4, Nr = 5 la cui funzione πS e mostrata in Figura 3.3:

Come si puo notare l’SPN non e esattamente un cifrario di tipo Sn perche:

1. Gli ultimi due round sono diversi dai precedenti

• Nel penultimo manca la permutazione

• L’ultimo e solo l’applicazione di Vigenere

Il motivo e semplice se ci fossero gli altri passaggi, essendo a chiave fissa, l’hacker li

conosce e potrebbe invertirli facilmente, mentre l’ultimo e ricavato solo in funzione

della chiave che e l’unica cosa che l’hacker non conosce.

Il penultimo e cosı perche si vuole avere simmetria tra l’inizio e la fine, in modo

tale da poter utilizzare lo stesso algoritmo sia per la codifica che per la decodifica.

2. Le chiavi dei vari round nella pratica non sono completamente indipendenti perche

se n = 128 e Nr = 16 significa che dovranno essere inviati 128 · 16 bit di chiave,

che sono troppi. E per questo che si utilizza un algoritmo apposito che genera un

key schedule a partire da una chiave di 16 bit. Si fa una cosa simile all’LFSR.

38


Figura 3.2: SPN Didattico

39


Figura 3.3: Funzione S-box

3.1.1 Considerazione sulle S-box

Il fatto che vengano prese l S-box da m bit piuttosto che una sola da n bit e dovuto

ad un problema implementativo.

Supponiamo che il sistema cifri blocchi di 128 bit e che si voglia usare una sola

S-box. La S-box e implementata tramite una tabella affinche sia una funzione molto

irregolare e non identificabile tramite una formula precisa. Questo vale a dire che la

tabella e composta da 2128 righe e 2 · 128 colonne, il che implica un enorme impiego di

memoria e una ricerca molto inefficiente.

Se invece si utilizzano, per esempio 4 S-box (l = 4) che operano su 4 bit ciascuna

(m = 4) io avro tabelle composte da 24 righe e 8 colonne. Poiche avro 4 tabelle della

stessa grandezza la quantita di memoria occupata e sempre la stessa ma la ricerca

diventa molto piu efficiente.

Questo appena descritto e il meccanismo che usa DES mentre AES utilizza sempre

la stessa S-box quindi e anche meno oneroso in termini di spazio.

40

3.2. Crittoanalisi Lineare Capitolo 3. Crittografia Simmetrica

3.2 Crittoanalisi Lineare

La crittoanalisi lineare si basa su una osservazione del tutto generale ossia:

Osservazione 7. Si consideri un cifrario a blocchi binario dove x =(x1, x2, · · · , xn), k = (k1, k2, · · · , ks) e y = (y1, y2, · · · , yn).Se ∀x si ha che sommando alcuni bit di x, alcuni di y e alcuni di k il risultatoe sempre 1 o sempre 0

xi1 ⊗ · · · ⊗ xik ⊗ yj1 ⊗ · · · ⊗ yjl ⊗ kt1 ⊗ · · · ⊗ ktv = 1/0

allora con una sola coppia (x, y) si ricostruisce la somma di alcuni bit dichiave. L’hacker si trova di fronte un sistema lineare con una sola soluzione,che e molto semplice da risolvere.

Chiaramente questo e il caso piu semplice per l’hacker in quanto il 100% delle volte

viene 0 o 1, ma in realta anche una percentuale 60-40 e rischiosa.

Supponiamo che

p(xi1 ⊗ · · · ⊗ xik ⊗ yj1 ⊗ · · · ⊗ yjl ⊗ kt1 ⊗ · · · ⊗ ktv = 1/0) LONTANA DA1

2

allora con molte coppie (x, y) e possibile ricostruire informazioni sulla chiave.

ESEMPIO:

10000 coppie (x, y)

p = 70%

Si effettua una ricerca esaustiva sui bit di chiave:

∀k = (kt1 , · · · , ktv) conto per quante delle 10000 coppie (x, y) vale

xi1 ⊗ · · · ⊗ xik ⊗ yj1 ⊗ · · · ⊗ yjl ⊗ kt1 ⊗ · · · ⊗ ktv = 0

e per quante

xi1 ⊗ · · · ⊗ xik ⊗ yj1 ⊗ · · · ⊗ yjl ⊗ kt1 ⊗ · · · ⊗ ktv = 1

Se la distribuzione di probabilita dei due valori e molto vicina a 50-50 allora posso

dire che la chiave che ho supposto non e quella che lega x a y, mentre se la distribuzione

e circa 70-30 posso ragionevolmente assumere che quella ipotizzata sia la parte di chiave

reale.

41


Puo anche succedere che ho piu k = (kt1 ⊗ · · · ⊗ ktv) che mi danno una percentuale

favorevole, in tal caso proseguo per tentativi nell’individuazione della chiave.

Quando si utilizza un SPN la cosa e leggermente diversa. Si cercano relazioni del

tipo:

xi1 ⊗ · · · ⊗ xik ⊗ uNr−1j1

⊗ · · · ⊗ uNr−1jl

= 0/1

Supponiamo che

p(xi1 ⊗ · · · ⊗ xik ⊗ uNr−1j1

⊗ · · · ⊗ uNr−1jl

= 0/1) LONTANA DA1

2

Supponiamo di avere a disposizione molte coppie (x, y).

Per ogni possibile kNr effettuo l’operazione inversa ottenendo uNr−1. Conto quante

volte il risultato e 0 e quante e 1 ottenendo una certa distribuzione di probabilita;

ritengo quindi di avere ottenuto l’uNr−1 esatto se la probabilita che ho ottenuto e

molto lontana da 12 .

Ora il problema e: Lontana quanto? Come ottenere la probabilita di cui si parla?

3.2.1 Piling-Up Lemma

Definizione 18 (Polarizzazione o Bias). Sia X una variabile aleatoria discretabinaria. Si dice polarizzazione il valore

ε(x) = p0 −1

2con p0 = p(X = 0)

Se ε(x) e vicina a −12 o 1

2 si dice che la variabile e polarizzata.

Osservazione 8. Poiche 0 ≤ p ≤ 1 =⇒ −12 ≤ ε(x) ≤ 1

2 =⇒ |ε(x)| ≤ 12

Definizione 19 (Piling-Up Lemma - lemma del tamponamento a cate-na). Siano Z1, Z2, · · · , Zn variabili aleatorie binarie indipendenti, e sianoε1, ε2, · · · , εm le rispettive polarizzazioni =⇒

ε(Z1 ⊗ Z2 ⊗ · · · ⊗ Zn) = 2n−1 ·Πni=1εi

Dimostrazione. Dimostriamolo per n = 2. Abbiamo quindi due variabili aleatoriebinarie indipendenti Z1, Z2 e

p0 = p(Z1 = 0) p1 = p(Z1 = 1) = 1− p0

42


q0 = p(Z2 = 0) q1 = p(Z2 = 1) = 1− q0

quindi

ε(Z1) = p0 −1

2

ε(Z2) = q0 −1

2

Ora calcoliamo la probabilita che Z1 ⊗ Z2 = 0

p(Z1 ⊗ Z2 = 0) = p0q0 + (1− p0)(1− q0)

ε(Z1⊗Z2) = p0q0+(1−p0)(1−q0)−1

2= p0q0+(1−q0−p0+p0q0)−1

2= 2p0q0−q0−p0+

1

2

Dobbiamo mostrare che questa quantita sia uguale a 2n−1 ·Πni=1εi, quindi

2n−1·Πni=1εi = 21·ε1·ε2 = 2(p0−

1

2)(q0−

1

2) = 2(p0q0−

1

2q0−

1

2p0+

1

4) = 2p0q0−q0−p0+

1

2

Dimostrazione. E indispensabili che le variabili siano indipendenti.

ESEMPIO:

Z1, Z2, Z3 INDIPENDENTI con ε(Z1) = ε(Z2) = ε(Z3) = 14

u1 = Z2 ⊗ Z3

u2 = Z1 ⊗ Z3

u3 = Z1 ⊗ Z2

Si ha quindi

ε(u1) = 2 · 14 ·

14 = 1

8ε(u2) = 2 · 1

4 ·14 = 1

8

43


ε(u3) = 2 · 14 ·

14 = 1

8

Poiche pero u3 = u1 ⊗ u2

ε(u3) = 2 · 1

8· 1

86= 1

8

3.2.2 Approssimazione lineare di un S-box

Osservazione 9 (Problema S-box lineare). Se la funzione fosse lineare, cioei risultati fossero, somme dei bit in ingresso, non ci sarebbe bisogno di rappre-sentarla tramite una tabella. Una funzione lineare ci permette di ottenerepolarizzazione massima per le variabili aleatorie che consideriamo; questasituazione e particolarmente vantaggiosa per l’hacker.

ESEMPIO: Supponiamo che

y1 = x1 ⊗ x3 ⊗ x4

y2 = x1 ⊗ x4

y3 = x2 ⊗ x3

y4 = x3 ⊗ x4

Succederebbe:

p(x1 ⊗ x3 ⊗ x4 ⊗ y1 = 0) = 1

cioe polarizzazione massima; significa che e molto facile da invertire. Serve che la

funzione sia il meno lineare possibile.

Per misurare il grado di linearita di una S-box si calcola la polarizzazione

ε(xi1 ⊗ · · · ⊗ xik ⊗ yj1 ⊗ · · · ⊗ yjl)

prendendo gli xi e yj tali che ai = bj = 1. La formula completa e questa:

ε(a1x1 ⊗ a2x2 ⊗ a3x3 ⊗ a4x4 ⊗ b1y1 ⊗ b2y2 ⊗ b3y3 ⊗ b4y4)

che deriva da quella generale che e:(n⊗i=1

aiXi

)⊗

(n⊗i=1

biYi

)

44


con ai, bj ∈ Z2. Nel caso in cui |ε| > 0 per qualche valore di ai e bj c’e una debolezza

dell’S-box.

Consideriamo l’S-box seguente

Figura 3.4: Funzione S-box

e consideriamo come variabile aleatoria α = x3 ⊗ x4 ⊗ y1 ⊗ y4 cioe quella ottenuta

con i vettori a = (0, 0, 1, 1) e b = (1, 0, 0, 1).

Si procede contando quante volte la variabile aleatoria ha valore 1 e quante 0,

ottenendo 2 volte lo 0 e 14 volte l’1. Dunque la probabilita

p(x3 ⊗ x4 ⊗ y1 ⊗ y4 = 0) =2

16

e

ε(α) =2

16− 1

2= −3

8

Non e difficile quindi calcolare le polarizzazioni delle 28 = 256 possibilita date dalla

scelta di ai e bj

La Figura 3.5 mostra le occorrenze del valore 0 in tutti i casi possibili.

Da notare che a e b sono rappresentati in esadecimale quindi x3 ⊗ x4 ⊗ y1 ⊗ y4 e

rappresentato da a = 3 e b = 9 perche

a = (0, 0, 1, 1)→ (0, 0, 1, 1)2 = (3)16

45


Figura 3.5: NL(a,b) cioe occorrenze dello 0

b = (1, 0, 0, 1)→ (1, 0, 0, 1)2 = (9)16

Ora, dove nella tabella compaiono valori bassi significa che la polarizzazione e lon-

tana da 12 e negativa, mentre dove sono alti e lontana ma positiva. Valori molto vicini

al valore medio ci indicano variabili non polarizzate.

Per ricavare la polarizzazione dalla tabella NL basta applicare la formula:

ε(a, b) =NL(a, b)− 8

16

L’hacker quindi prendera in considerazione quelle polarizzate per apportare il suo

attacco. In particolare cerchera un percorso nello schema che collega le variabili

polarizzate.

3.2.3 Attacco lineare ad un SPN

L’attacco si basa sul trovare un insieme di approssimazioni lineari delle S-box che

possono essere utilizzate per derivare un’approssimazione lineare dell’intero SPN.

La figura 3.6 mostra il procedimento. Da notare che le frecce corrispondono alle

variabili random che vengono coinvolte nell’approssimazione lineare, mentre le S-box

che vengono coinvolte vengono chiamate active S-box.

46


Figura 3.6: Procedimento dell’attacco all’SPN

47


Supponiamo che le variabili aleatorie con polarizzazione maggiore, ottenute con il

metodo precedente, sono

• x1 ⊗ x3 ⊗ x4 ⊗ y2 → |ε| = 14

• x2 ⊗ y2 ⊗ y4 → |ε| = 14

L’approssimazione considera 4 S-box attive:

• Nella S21 la prima variabile polar. diventa: T1 = U1

5 ⊗U17 ⊗U1

8 ⊗V 16 con ε(T1) = 1

4


6 ⊗ V 26 ⊗ V 2

8 con ε(T1) = −14


6 ⊗ V 36 ⊗ V 3

8 con ε(T1) = −14


14 ⊗ V 314 ⊗ V 3

16 con ε(T1) = −14

Calcoliamo, dunque, la polarizzazione della somma:

ε(T1 ⊗ T2 ⊗ T3 ⊗ T4) = 23 · 1

4·(−1

4

)3

= − 1

32

Ora, le variabili T1, T2, T3, T4 hanno una proprieta e cioe che il loro XOR puo essere

espresso in funzione del plaintext, ossia:

• T1 = U15 ⊗ U1

7 ⊗ U18 ⊗ V 1

6 = X5 ⊗K15 ⊗X7 ⊗K1

7 ⊗X8 ⊗K18 ⊗ V 1

6

• T2 = U26 ⊗ V 2

6 ⊗ V 28 = V 1

6 ⊗K26 ⊗ V 2

6 ⊗ V 28

• T3 = U36 ⊗ V 3

6 ⊗ V 38 = V 2

6 ⊗K36 ⊗ V 3

6 ⊗ V 38

• T4 = U314 ⊗ V 3

14 ⊗ V 316 = V 2

8 ⊗K314 ⊗ V 3

14 ⊗ V 316

Le quattro variabili T1, T2, T3, T4 hanno un valore di polarizzazione che, in valore

assoluto, e molto alto. Il che significa che se andiamo a calcolare lo XOR delle variabili

random otterremo delle cancellazioni (esempio V 16 , V 2

8 ), ottenendo

X5 ⊗X7 ⊗X8 ⊗ V 36 ⊗ V 3

8 ⊗ V 314 ⊗ V 3

16

⊗K15 ⊗K1

7 ⊗K18 ⊗K2

6 ⊗K36 ⊗K3

14

Il prossimo passo e quello di sostituire i V 3i con formule espresse in funzione di U4

i ,

e cioe:

V 36 = U4

6 ⊗K46

V 38 = U4

14 ⊗K414

48


V 314 = U4

8 ⊗K48

V 316 = U4

16 ⊗K416

la formula diventa

X5 ⊗X7 ⊗X8 ⊗ U46 ⊗ U4

8 ⊗ U414 ⊗ U4

16⊗⊗K1

5 ⊗K17 ⊗K1

8 ⊗K26 ⊗K3

6 ⊗K314 ⊗K4

6 ⊗K48 ⊗K4

14 ⊗K416

Questa espressione e espressa solo in funzione di bit del plaintext, bit di UNr−1i e bit

di chiave. Supponiamo che i bit di chiave siano fissati la somma dei vari Kji ha valore

1 o 0 fisso, cioe conosciuto. Quindi la variabile che ha come polarizzazione ε = ± 132 si

riduce ad essere

X5 ⊗X7 ⊗X8 ⊗ U46 ⊗ U4

8 ⊗ U414 ⊗ U4

16

Il fatto che tale formula ha una polarizzazione lontana da 0 consente di effet-

tuare l’attacco lineare di cui si e parlato precedentemente. Tale attacco e riportato

formalmente in pseudo-codice nella Figura 3.7

Figura 3.7: Algoritmo attacco lineare

T e il numero di coppie (x, y); T e l’insieme delle coppie (x, y); (L1, L2) gli 8 bit di

chiave espressi in esadecimale.

49


L’algoritmo calcola il massimo valore, in realta si deve cercare quella chiave che

restituisce una percentuale molto vicina a(

12 − ε

)o a

(12 + ε

).

Pero in tutto questo discorso c’e una forzatura perche le variabili aleatorie non sono

proprio del tutto indipendenti in quanto le chiavi non sono del tutto indipendenti dato

che fanno parte di un key schedule generato a partire da una chiave principale.

50

3.3. Campi Finiti Capitolo 3. Crittografia Simmetrica

3.3 Campi Finiti

Definizione 20 (Gruppo). E un insieme dove abbiamo definita un’operazione.Formalmente e una tupla (G, ◦) dove

• G: e un insieme

• ◦: e un’operazione, cioe una legge che associa a due elementi di G unterzo elemento sempre di G.

L’operazione deve avere le seguenti proprieta:

1. Associativa:(a ◦ b) ◦ c = a ◦ (b ◦ c)

2. Esistenza elemento neutro:

∃e ∈ G t.c.∀a ∈ G a ◦ e = e ◦ a = a

3. Esistenza elemento inverso:

∀a ∈ G ∃a−1 ∈ G t.c. a ◦ a−1 = a−1 ◦ a = e

Definizione 21 (Gruppo Abeliano). Un gruppo abeliano e un gruppo dovevale anche la proprieta commutativa:

a ◦ b = b ◦ a

Definizione 22 (Campo). Un campo e un insieme su quale sono definite dueoperazioni. Formalmente e una tripla (K,+, ·) dove

• K e un’insieme

• +, · sono due operazioni

con le seguenti proprieta:

1. (K,+): e un gruppo abeliano

2. Indichiamo con 0 l’elemento neutro di (K,+) allora (K \ {0}, ·) e ungruppo abeliano

3. Distributiva:a · (b+ c) = a · b+ a · c

51


ESEMPIO:

(Z,+, ·) NO. Non e un campo perche manca la proprieta 3 del gruppo per la

moltiplicazione.

(Q,+, ·) SI

(R,+, ·) SI

(C,+, ·) SI

Q, R, C sono tutti campi infiniti quindi non vanno bene per essere trattati da un

computer. A noi servirebbe (Zm,+, ·), ma non sempre Zm e un gruppo perche manca

l’inverso moltiplicativo; bisogna trovare un m che mi permette di avere tutti gli inversi

moltiplicativi di tutti gli elementi in Zm.

Gia sappiamo che ∀a ∈ Zm a INV ERTIBILE =⇒ gcd(a,m) = 1.

Teorema 11. Zm e un campo ⇐⇒ m PRIMO

Dimostrazione. La condizione gcd(a,m) = 1 ∀a < m si verifica esattamente quando me primo.

Il fatto che Zm sia un campo significa che posso fare sempre la divisione.

L’ideale sarebbe avere un campo con 2k elementi, perche cosı posso rappresentare

tutti gli elementi del campo mediante una stringa binaria di k bit. Il problema e che

Z2k non e un campo (con k > 1).

3.3.1 Costruzione di un campo finito

Un campo finito con q = pk elementi si indica con Fq o con GF (q).

PROBLEMA: Vogliamo costruire un campo che contenga pk elementi con p primo

e k > 1.

• Si parte da Zp = {0, 1, · · · , p− 1}

• Si cerca un polinomio f(x) irriducibile su Zp di grado k

• Si pone K = all’insieme dei polinomi di grado ≤ k (per comodita usiamo α non

x).

52


• |K| = pk perche generalmente i polinomi sono della forma

b0 + b1α+ b2α2, · · · , bk−1α

k−1

quindi pk possibilita di assegnamento dei valori bi.

• Somma: Per la somma non ci sono problemi, infatti e la somma naturale.

• Prodotto: Problemi perche facendo il prodotto naturale e possibile avere un poli-

nomio di grado > k e quindi si esce dal campo. Si considera, dunque, il prodotto

naturale e poi si riduce modulo f(x).

ESEMPIO: p = 2, k = 3, pk = 8

• Z2 = {0, 1}

• f(x) = x3 +x+ 1. Per vedere se e irriducibile provo tutti i valori di Z2 e nessuno

mi deve annullare il polinomio, il che significa che il polinomio non ha radici e

quindi non e fattorizzabile.

• K = {0, 1, α, α + 1, α2, α2 + 1, α2 + α, α2 + α + 1} che nel computer posso rap-

presentare come {000, 001, 010, 011, 100, 101, 110, 111} in base a come prendo i

bi

• |K| = 8 perche i polinomi sono della forma b0 + b1α+ b2α2

• Somma:

(α2 + α) + (α+ 1) = α2 + α+ α+ 1 = α2 + 1

cioe

110⊗ 011 = 101

• Prodotto:

(α2 + α) · (α+ 1) = α3 + α2 + α2 + α = α3 + α

α3 + α ≡ 1 (mod α3 + α+ 1)

N.B.: Il prodotto non e l’∧ logico.

Teorema 12. (K,+, ·) cosı costruito e un campo con pk elementi.

Per effettuare la divisione invece che farla veramente si possono calcolare preventi-

vamente tutte le potenze fino a q − 1 e fare le divisioni per sostituzione, cioe:

53


α3 + α+ 1 = 0→ α3 = α+ 1

α4 = α · α3 = α(α+ 1) = α2 + α

α5 = α · α4 = α(α2 + α) = α3 + α2 = α2 + α+ 1

α6 = α · α5 = α(α2 + α+ 1) = α3 + α2 + α = α2 + 1

α7 = α · α6 = α(α2 + 1) = α3 + α = 1

Una volta trovato 1 possiamo fermarci tanto ritroveremo sempre polinomi gia trovati.

Una volta che ho queste informazioni, dopo aver fatto il prodotto naturale, per ogni

monomio, riduco il grado a uno di questi fattorizzandolo, e poi applico le sostituzioni.

N.B.: Se cambiamo polinomio irriducibile otteniamo due campi formalmente diver-

si; questi due campi pero sono isomorfi, ossia c’e un modo univoco per associare un

elemento del primo campo ad un elemento del secondo campo.

Teorema 13. Due campi finiti con lo stesso numero di elementi sono isomorfi(hanno identiche proprieta matematiche).

Questo significa avere diversita implementative nel senso che magari un polinomio

piuttosto che un altro modifica il tempo necessario per fare i calcoli.

Teorema 14. ∀p PRIMO,∀k > 1 ∃ un polinomio irriducibile su Zp digrado k.(=⇒ ∀p PRIMO,∀k > 1 ∃ un campo finito con pk elementi)

Teorema 15. Se q non e potenza di un numero primo allora non esiste uncampo finito con q elementi.

Elemento primitivo

Sia Fq un campo finito con q = pk.

Definizione 23. Sia ω ∈ Fq si dice primitivo se

Fq = {ω, ω2, ω3, · · · , ωq−1 = 1}

cioe gli altri elementi sono tutti sue potenze (esempio α di prima).

Teorema 16. f(x) PRIMITIV O (come polinomio) ⇐⇒ α e un’ elementoprimitivo del campo finito costruito a partire da f.

Dimostrazione. L’elemento primitivo α coincide con ω.

54


Teorema 17 (Dell’elemento primitivo). Un campo finito ammette sempre unelemento primitivo ⇐⇒ (Fq \ {0}, ·) e un gruppo ciclico.

ESEMPIO:

Gli elementi primitivi di Z7 sono:

1— NO (mai)

2— 2, 4, 1, 2 NO

3— 3, 2, 6, 4, 5, 1 SI

4— 4, 2, 1 NO

5— 5, 4, 6, 2, 3, 1 SI

6— 6, 1 SI

L’inverso di un elemento lo possiamo trovare con l’algoritmo di Euclide, quello con

le divisioni successive.

ESEMPIO F9:

• q = 32 → p = 3, k = 2

• Z3 = {0, 1, 2}

• f(x) = x2 + 1

• K = {0, 1, 2, α, α+ 1, α+ 2, 2α, 2α+ 1, 2α+ 2}

1α+2 =? E l’elemento in F9 che moltiplicato per (α+ 2) da 1.

α2 + 1 = (α+ 1) · (α+ 2) + 2

55

3.4. DES (Data Encryption Standard) Capitolo 3. Crittografia Simmetrica

3.4 DES (Data Encryption Standard)

DES e stato sviluppato dell’IBM, come modifica di un precedente cifrario chiamato

Lucifer. Venne pubblica nei registri federali nel 1975. Rimase lo standard ufficiale fino

al Gennaio 1999 quando venne crackato e rimpiazzato dall’AES.

3.4.1 Descrizione

Il DES ha queste caratteristiche:

• Key: 56 bit → |K| = 256 numero che non era trattabile negli anni ’70 ma che lo

e diventato poi.

• Lunghezza Blocco: 64 bit

• N Round: 16

Funzione Round

Quello che succede in ogni round e mostrato in Figura 3.8.

Figura 3.8: Funzione Round

Si divide il blocco in ingresso (64 bit) in due blocchi da 32 bit Li e Ri, e si applica

la funzione round [Li = Ri−1

Ri = Li−1 ⊗ f(Ri−1,Ki)

]

56


La funzione round e invertibile anche se la f non lo e. Infatti[Ri−1 = Li

Li−1 = Ri ⊗ f(Ri−1,Ki)=⇒

Ri−1 = Li

Li−1 = Ri ⊗ f(Li,Ki)

]quindi il processo e globalmente invertibile. Non ho bisogno di calcolare f−1, il che

significa che puo essere anche non iniettiva; inoltre l’algoritmo di cifratura e de-cifratura

e lo stesso basta scambiare Li con Ri e viceversa.

Il DES applica per 16 round questo schema (schema di Faistel). Prima dei 16 round

viene applicata al plaintext una permutazione iniziale a chiave fissa, IP (x) = L0R0.

Di conseguenza, dopo i 16 round, viene applicata IP−1(y) = R16L16 per mantenere

la simmetria dell’algoritmo. L’applicazione di queste due permutazioni non ha nes-

sun significato crittografico, cioe sono inutili non influenzano il livello di sicurezza

dell’algoritmo.

La funzione

f : {0, 1}32 x {0, 1}48 → {0, 1}32

prende in input 32 bit e la round key. Il key schedule, (K1,K2, · · · ,K16), consiste di

16 round key di 48 bit ciascuna, derivare dai 56 della chiave master. L’output di tale

funzione viene messo in ⊗ con Li−1.

Key Schedule

Le 16 round key di 48 bit vengono generate a partire dalla master key (56 bit)

tramite una selezione permutata.

Funzione f

La Funzione 3.9 mostra come funziona la f di cui si parlava prima.

La funzione prende in ingresso un blocco di 32 bit e la raund key di 48 bit. Il blocco

viene portato a 48 bit mediante la funzione di espansione E e poi viene messo in ⊗ con

la chiave. Il tutto da origine a 48 bit che devono essere ridotti a 32. Questo viene fatto

mediante l’uso di S-Box che prendono in input 6 bit e ne restituiscono 4. I 32 bit che

ottengo li permuto con la permutazione a chiave fissa P .

Espansione E: L’espansione del blocco chiamata E, non e altro che una ripetizione

permutata dei 32 bit del blocco al quale vengono aggiunti, quindi ripetuti, 16 dei 32

bit. La tabella che regola questa funzione e la seguente:

57


Figura 3.9: Funzione f del DES

Figura 3.10: Funzione E del DES

58


Questo significa che E e una funzione a chiave fissa.

S-Box: Ogni S-Box e una funzione

f : {0, 1}6 → {0, 1}4

Essa prende in input 6 bit, b0, b1, b2, b3, b4, b5 e ne restituisce 4, secondo una regola

fissa. Ogni S-Box implementa una diversa funzione, mentre nell’AES sono identiche.

La Figura 3.11 mostra S2.

Figura 3.11: S2 - S-Box del DES

b0, b5 mi indicano la riga della tabella che devo guardare mentre b1, b2, b3, b4 mi

indicano la colonna. All’incrocio c’e il valore che deve essere restituito.

ESEMPIO:

101101→ (11)2 = (3)10 e (0110)2 = (6)10, quindi 3 riga e 6 colonna, tenendo conto

che si parte da 0, quindi sarebbero 4 riga e 7 colonna.

I 4 bit da restituire sono 0010.

Da notare che la funzione f non e iniettiva proprio perche le S-Box non sono in-

vertibili/iniettive, in quanto il condomino e piu piccolo del dominio e quindi ci saranno

valori ripetuti.

Permutazione P: In uscita dalle S-Box avremo

C = C<1>C<2>C<3>C<4>C<5>C<7>C<8>

lunga 32 bit. A questi viene applicata la permutazione, a chiave fissa, P mostrata in

Figura 3.12.

Questo significa che C = c1c2c3c4 · · · c32 diventa P (C) = c16c7c20 · · · c4c25.

P (C) e finalmente l’output della funzione f .

59


Figura 3.12: Permutazione del DES

3.4.2 Analisi

Trapdoor. Molti pensano che esista una “via d’uscita”, nel senso che chi invento

il cifrario ha previsto un metodo per decifrarlo in breve tempo avendo a dispo-

sizione certe risorse, e lo abbia detto solo al Dipartimento della Difesa Americana.

Questo per motivi di sicurezza nazionale; nel senso che un comune hacker con lim-

itate risorse e senza conoscere la trapdoor non puo riuscire a crackarlo, e quindi

poteva essere usato nelle transazioni commerciali; se pero due terroristi si scam-

biavano informazioni tramite DES il Governo Americano riusciva a decifrare la

comunicazione.

Chiave 56 bit. Il maggiore problema e che la chiave e troppo corta. In realta la

chiave e lunga 64 bit ma 8 sono usati per il controllo di parita (sinceramente

troppi due potevano anche bastare), e non si capisce il motivo. Negli anni ’70

non era possibile una ricerca esaustiva che esaminasse 256 possibili chiavi, ma dal

1999 in poi e diventato possibile. Prima sarebbero servite macchine del valore di

milioni di dollari.

Rispetto al precedente crittosistema, Lucifer, addirittura la chiave e stata ridotta

da 128 a 56.

Crittoanalisi Lineare. Di fatto e possibile. E stata studiata da Matsui (colui che

la invento) ma non ebbe grande successo perche servono 243 coppie (x, y) e sono

serviti 40 giorni per crearle e 10 per fare l’attacco. Un hacker non potra mai avere

una quantita di informazioni cosı elevata.

60


Crittoanalisi Differenziale. Attualmente, e stato detto che le S-Box furono pro-

gettate cosı proprio perche dovevano reggere ad alcuni tipi di attacchi. Quan-

do Biham e Shamir inventarono, 20 anni dopo l’invenzione del DES, la tecni-

ca della Crittoanalisi Differenziale si accorsero che questa era improponibile sul

DES proprio per via delle S-Box. Questo significa che i ricercatori dell’IBM gia

conoscevano questa tecnica e l’hanno tenuta nascosta per 20 anni.

3.4.3 Varianti

Doppio DES

Raddoppio la chiave K = K1K2 e applico il meccanismo due volte prima con K1

poi con K2. Ossia

EK2(EK1(X)) = Y

Apparentemente questo risolve il problema, perche aumenta la complessita, infatti

ora non e piu proponibile (con gli strumenti di oggi) un attacco brute-force su 256 ·256 =

2112 possibili chiavi.

In realta e fragile all’attacco Meet in the middle. Esso e un attacco Known Plaintext.

Funziona cosı: ∀(x, y) si calcolano tutti i possibili EK1(X) e tutti i possibiliDK2(Y )∀K1, K2.

Si avra che

EK1(X) = DK2(Y )

e vero per tutte le coppie (x, y) solo per una coppia K1, K2 che e la chiave.

Chiaramente una sola coppia (x, y) non basta perche ci possono essere piu K1 K2

che verificano la condizione, mentre crescendo il numero di coppie, la probabilita

p(EK1(X) = DK2(Y ))

diminuisce.

Con una coppia sola p(EK1(X) = DK2(Y )) = 264

264·264 = 1264

che sembra bassa, ma

questo valore e la probabilita che prese a caso K1 e K2 si abbia EK1(X) = DK2(Y ) e

quindi va moltiplicata per 2112 che e il numero delle possibili chiavi; si ottiene quindi:

p(EK1(X) = DK2(Y )) =1

264· 2112 = 248

che e una probabilita molto elevata.

Ma gia con due coppie la probabilita decresce di molto infatti

61


p(EK1(X) = DK2(Y )) =1

264· 1

264· 2112 = 2−16 =

1

216

3DES (Triplo DES)

Si e capito che neanche il Doppio DES basta e quindi e stato creato il 3DES che e

cosı definito

EK3(EK2(EK1(X))) = Y

Ossia ho tre chiavi da 56 bit, 168 in totale, che servono ha iterare il DES tre volte.

La complessita comincia a diventare non trascurabile in quanto in totale sono 48 i

round da fare. Se consideriamo che l’AES, che e lo standard attuale, ne effettua solo

10, capiamo che non vale la pena utilizzarlo, anche se (per il momento) non e stato

trovato un attacco che lo viola.

Dopotutto, visto che e gia successo, nessuno ci vieta di pensare che tra qualche anno

le risorse siano tali da rendere un attacco brute-force, su 2168 chiavi, proponibile.

62

3.5. AES (Advanced Encryption Standard) Capitolo 3. Crittografia Simmetrica

3.5 AES (Advanced Encryption Standard)

Ne 1997 il NIST emise un bando per scegliere un algoritmo simmetrico che sarebbe

diventato il nuovo standard e che avrebbe sostituito il precedente, cioe il DES.

Il bando termino l’anno successivo, ma fino al 2000 non si conobbe il vincitore;

servirono 2 anni per decidere quale fosse l’algoritmo migliore. Venne scelto il Rijndael

(dovuto ai nome degli inventori: Rijmen e Daemen, due ricercatori Olandesi), che

divento standard l’anno successivo. Gli algoritmi che raggiunsero la finale, oltre a

questo, furono: MARS, RC6, Serpent e Twofish.

3.5.1 Caratteristiche Generali

• Blocchi da 128 bit (16 byte)

• Tipo SPN

• Esistono 3 versioni

1. 128 bit → 10 round

2. 192 bit → 12 round

3. 256 bit → 14 round

• E un cifrario orientato al byte (non al bit); un byte e identificato come un elemento

di un campo finito, F256.

Per avere un campo di 256 elementi serve un polinomio irriducibile a coefficienti in

Z2 di grado 8, perche 256 = 28. Dal Teorema 13, sappiamo che non fa differenza

quale tra i polinomi irriducibili si sceglie; infatti gli autori ne hanno scelto uno a

caso e cioe

f(x) = x8 + x4 + x3 + 1

Di conseguenza gli elementi del campo sono i polinomi di grado < 8. In generale

al byte

a7a6 · · · a0

corrisponde

f(x) = a7x7 + a6x

6 + · · ·+ a0

• STATO: (Figura 3.13) e rappresentato mediante una matrice 4x4 che contiene 16

byte, cioe 16 elementi di F256, quindi in totale 128 bit.

63


Figura 3.13: Stato AES

3.5.2 Struttura

La struttura dell’AES e mostrata nella Figura 3.14.

Come primo passaggio c’e il cosiddetto Processo di Whitening; esso prevede che

vengano combinati i dati con porzioni della chiave mediante semplici operazioni di

XOR, prima del primo passaggio di cifratura.

Ogni round, tranne l’ultimo, prevede i seguenti passaggi:

• Substitution Bytes, ed equivale alla fase di sostituzione presente nell’SPN.

• Shift Rows, ed equivale alla permutazione.

• Mix Columns, e una parte lineare e non e presente in un SPN classico.

• XOR con la Round Key

L’ultimo round differisce dai precedenti perche non effettua Mix Columns.

3.5.3 Substitution Bytes

Questa fase e realizzata mediante S-Box. L’AES utilizza 16 S-Box uguali, ognuna

che prende in input 1 byte, quindi S −Box : Z82 → Z8

2 .

Ogni S-Box esegue questi passaggi:

1. Input: Riceve in input un byte che viene trasformato nel polinomio corrispondente

α ∈ F256.

2. Calcolo inverso: Viene calcolato 1α(operazione fortemente non lineare). Poiche 0

non ha inverso esso viene restituito identico.

3. Conversione Polinomio 1α : 1

α diventa a7a6a5a4a3a2a1a0

64


Figura 3.14: Struttura AES

65


4. Esecuzione di una parte lineare:

a7

a6

a5

a4

a3

a2

a1

a0

·

1 1 1 1 0 0 0 1

1 1 1 0 0 0 1 1

1 1 0 0 0 1 1 1

1 0 0 0 1 1 1 1

0 0 0 1 1 1 1 1

0 0 1 1 1 1 1 0

0 1 1 1 1 1 0 0

1 1 1 1 1 0 0 0

+

1

1

0

0

0

1

1

0

= OUTPUT S − box

In realta l’S-Box non svolge i calcoli ogni volta ma effettua una sostituzione avval-

endosi della tabella in Figura 3.15, che e stata calcolata dagli autori.

Figura 3.15: S-Box AES

Teorema 18. Non esistono S-Box a 8 bit migliori di questa.

Gli autori del Rijndael ha dimostrato questo teorema, e hanno mostrato che la

massima polarizzazione possibile e 0, 1625. Questa e una polarizzazione molto bassa

che non e sufficiente per portare a termine un attacco di crittoanalisi lineare. Gli autori

hanno dovuto anche evitare, che ci fosse un cammino con poche S-Box attive. Infatti

66


avendo molte S-Box attive la polarizzazione della variabile decresce notevolmente in

quanto e il prodotto delle polarizzazioni.

Questo significa che per portare a termine un attacco di crittoanalisi lineare sull’AES

servono 2150 coppie (x, y), che e un numero irragionevole.

3.5.4 Shift Rows

Questa fase realizza la permutazione. Lo fa nel modo mostrato in Figura 3.16

Figura 3.16: Shift Rows

La prima riga dello stato i-esimo rimane invariata; la seconda riga viene shiftata di

una posizione verso sinistra; la terza di 2 e la quarta di 3.

3.5.5 Mix Columns

E l’unica parte lineare. Serve per realizzare la cosiddetta diffusione, cioe fa au-

mentare il numero di S-Box attive in una crittoanalisi lineare.

La prima matrice e quella che esce dallo Shift Rows e la seconda e una matrice fissa,

rappresentata da polinomi.s0,0 s0,1 s0,2 s0,3

s1,0 s1,1 s1,2 s1,3

s2,0 s2,1 s2,2 s2,3

s3,0 s3,1 s3,2 s3,3

·

x (x+ 1) 1 1

1 x (x+ 1) 1

1 1 x (x+ 1)

(x+ 1) 1 1 x

La moltiplicazione e fatta all’interno del campo.

3.5.6 Key Schedule

Crea 11 Round Key da 128 bit a partire da una chiave master di 128 bit. La chiave

puo essere rappresentata dalla matrice

67


k0,0 k0,1 k0,2 k0,3

k1,0 k1,1 k1,2 k1,3

k2,0 k2,1 k2,2 k2,3

k3,0 k3,1 k3,2 k3,3

Ci servira anche la tabella Rcon che e la seguente e rappresenta una serie di costanti

espresse in esadecimale. 01 02 04 08 10 20 40 80 1B 36

00 00 00 00 00 00 00 00 00 00

00 00 00 00 00 00 00 00 00 00

00 00 00 00 00 00 00 00 00 00

Si lavora colonna per colonna in questo modo: indichiamo con Wi l’i-esima colonna

della matrice di chiave.

• Se Wi e la prima colonna di ogni round key allora

Wi = (S −Box(ROTL1(Wi−1))⊗Wi−4)⊗Rcon(j)

Inizialmente j = 0, poi ad ogni iterata viene incrementato di uno.

• Se Wi non e la prima colonna di ogni round key allora

Wi = Wi−1 ⊗Wi−4

68

3.6. Modi Operativi Capitolo 3. Crittografia Simmetrica

3.6 Modi Operativi

• ECB Mode (Electronic CodeBook Mode): Classica modalita, in cui data una

sequenza x1x2 · · ·xn di blocchi in chiaro, ogni xi viene cifrato con la stessa chiave

K, producendo y1y2 · · · yn.

• CBC Mode (Cipher Block Chaining): Ogni blocco cifrato yi e messo in XOR con il

blocco in chiaro successivo, prima di essere cifrato con la chiave K. Formalmente

si utilizza un initialization vector IV = y0, e si usa la seguente regola

yi = eK(yi−1 ⊗ xi)

• OFB Mode (Output FeedBack Mode):Simile ad uno stream cipher. Il keystreem

e generato a partire da un IV; si pone z0 = IV poi si segue la regola

zi = eK(zi−1)

La sequenza in chiaro viene poi cifrata seguendo la regola

yi = xi ⊗ zi

• CFB Mode (Cipher FeedBack Mode): E simile al precedente solo che IV = y0.

Il keystream segue la regola

zi = eK(yi−1)

Per cifrare si usa la regola

yi = xi ⊗ zi

69

Capitolo 4

Funzioni Hash Crittografiche

4.1 Funzioni Hash e Data Integrity

Una funzione hash crittografica e utilizzata per preservare l’integrita dei dati, aut-

enticazione e firma digitale. Essa viene usata per costruire un fingerprint o un message

digest, che e un estratto di un dato; se il dato viene alterato il fingerprint non sara piu

valido in quanto un ricalcolo della stessa funzione hash sul dato alterato produrra un

diverso fingerprint.

Sia h la funzione hash e x un dato qualsiasi. Il corrispondente fingerprint e dato da

h(x) = y. Tipicamente l’estratto della funzione hash e di lunghezza finita e minore del

dato originario: comunemente 160 bit.

Le funzioni hash ricoprono un ruolo importante in quello che e il meccanismo della

firma digitale. Esistono, anche, funzioni hash che utilizzano una chiave per effettuare il

calcolo; esse vengono dette funzioni MAC (Message Authentication Code).

Definizione 24 (Hash Family). Una hash family e una quaterna (X ,Y,K,H)dove le seguenti condizioni sono soddisfatte:

• X e l’insieme dei possibili messaggi

• Y e l’insieme finito dei possibili message digest

• K e il keyspace, cioe l’insieme finito delle possibili chiavi

• H l’insieme delle possibili funzioni hash

• ∀K ∈ K ∃hK ∈ H t.c. hK : X → Y

In questa definizione X puo essere finito o infinito, mentre Y e sempre finito. Nel ca-

so in cui X fosse finito la funzione hash e chiamata funzione di compressione. In questa

situazione assumiamo che |X | ≥ |Y|, ma nel proseguo assumeremo una condizione piu

restrittiva |X | ≥ 2|Y|.Una coppia (x, y) ∈ XxY si dice valida, sotto una chiave K, se hK(x) = y.

70

4.2. Sicurezza di una funzione hash Capitolo 4. Funzioni Hash Crittografiche

Indichiamo con FX ,Y l’insieme di tutte le possibili funzioni che vanno da X a Y.

Supponiamo che |X | = N e |Y| = M , allora |FX ,Y | = MN . Qualunque hash family

F ⊆ FX ,Y e chiamata (N,M)− hash family.

Una funzione hash keyless e una funzione h : X → Y con X , Y gli stessi della

Definizione 24; si puo vedere come una funzione hash dove c’e solo una possibile chiave,

quindi |K| = 1.

4.2 Sicurezza di una funzione hash

Supponiamo che h : X → Y sia una funzione senza chiave, dove X = Zn2 e Y = Zm2

con n > m. Sia x ∈ X e y = h(x) ∈ Y.

In molte applicazioni crittografiche delle funzioni hash, si desidera avere un solo

modo per produrre una coppia (x, y) che e quello di fissare x e calcolare y = h(x),

applicando semplicemente la funzione h su x.

Ora definiremo 3 problemi; se una funzione hash e definita sicura allora dovrebbe

essere difficile risolvere questi 3 problemi.

Problema 1 (Preimage o Controimmagine). Data una funzione hash h : X →Y e un elemento y ∈ Y trovare x ∈ X t.c. h(x) = y.

Dato un possibile message digest y, il problema Preimage chiede se x puo essere

trovato in modo tale da avere h(x) = y. Se tale problema puo essere risolto, allora e

stata trovata una coppia (x, y) valida.

Una funzione hash, tale che il problema Preimage non puo essere risolto in modo

efficiente, e detta one-way o Preimage resistant.

Problema 2 (Second Preimage o Seconda Controimmagine). Data una fun-zione hash h : X → Y e un elemento x ∈ X trovare x′ ∈ X t.c. x′ 6= x∧h(x′) =h(x).

Dato un messaggio x, il problema Second Preimage, chiede se e possibile trovare

un altro messaggio x′ 6= x tale che si abbia lo stesso message digest. Da notare che se

e possibile risolvere tale problema significa che la coppia (x′, h(x)) e valida.

Una funzione hash, per la quale non e possibile risolvere in modo efficiente il

problema Second Preimage, viene detta Second Preimage resistant.

Problema 3 (Collision). Data una funzione hash h : X → Y trovare x, x′ ∈X t.c. x′ 6= x ∧ h(x′) = h(x).

71


Il problema Collision chiede se e possibile trovare due messaggi diversi che mi danno

lo stesso message digest. La soluzione del problema genera due coppie valide (x, y) e

(x′, y).

Una funzione hash, per la quale non e possibile risolvere in modo efficiente il

problema Collision, viene detta Collision resistant.

4.2.1 Random Oracle Model

In questa sezione descriviamo un modello ideale di funzione hash.

Se una funzione h e ben formata, si dovrebbe avere che l’unico modo efficiente per

determinare h(x) sia proprio quello di valutare la funzione h in x. Chiaramente, questo

deve rimanere vero anche se molti altri valori, h(x1), h(x2), · · · , h(xm), sono gia stati

calcolati.

Vediamo un esempio dove questa proprieta non e verificata.

Supponiamo che h : ZnxZn → Zn sia la funzione lineare

h(x, y) = ax+ by (mod n)

con a, b ∈ Zn e n ≥ 2 ∈ Z (intero). Supponiamo di aver ottenuto i valori

h(x1, y1) = z1

e

h(x2, y2) = z2

Siano r, s ∈ Zn, quindi avremo che

h(rx1 + sx2 (mod n), ry1 + sy2 (mod n)) = a(rx1 + sx2) + b(ry1 + sy2) (mod n)

= r(ax1 + by1) + s(ax2 + by2) (mod n)

= rh(x1, y1) + sh(x2, y2) (mod n)

Di conseguenza accade che, conoscendo due coppie valide, possiamo conoscere i

message digest di altri messaggi senza applicare la funzione hash a tali messaggi.

Il random oracle model, che fu introdotto da Bellare e Rogaway, fornisce un modello

matematico di una funzione hash ideale. In questo modello, una funzione hash h :

X → Y viene scelta a caso da FX ,Y , e viene permesso solo all’oracolo di accedere a tale

funzione. Questo significa che non c’e un algoritmo o una formula che identifica h, e

quindi l’unico modo per conoscere h(x) e interrogare l’oracolo.

72


Chiaramente l’oracolo nella realta non esiste; si puo solo sperare che la funzione

hash si comporti come un random oracle.

Come conseguenza delle assunzioni fatte nel random oracle model, e ovvio che la

seguente proprieta sia soddisfatta:

Teorema 19. Sia h ∈ FX ,Y scelta casualmente, e sia X0 ⊆ X . Supponiamoche il valore h(x) sia gia stato determinato (consultando un oracolo), se e solose x ∈ X0. Allora p(h(x) = y) = 1

M ∀x ∈ X \ X0 e ∀y ∈ Y.

4.2.2 Algoritmi nel Random Oracle Model

Gli algoritmi che verranno descritti sono algoritmi randomizzati, ossia possono

effettuare scelte random durante la loro esecuzione.

L’algoritmo Las Vegas e uno di questi; esso puo terminare senza aver trovato una

soluzione ma se restituisce una soluzione di sicuro e corretta. Supponiamo 0 ≤ ε < 1

la probabilita che l’algoritmo restituisca la risposta corretta.

In questa sezione useremo la notazione (ε,Q)−algorithm per indicare un algoritmo

con probabilita di successo nel caso medio pari a ε che effettua al piu Q interrogazioni

all’oracolo.

Consideriamo gli Algoritmi 4.1 e 4.2 che risolvono i primi due problemi.

73


Teorema 20. Per ogni X0 ⊆ X con |X0| = Q, la probabilita di successo nelcaso medio, dell’Algoritmo 4.1, e

ε = 1−(

1− 1

M

)Q

Dimostrazione. Sia y ∈ Y fissato. Sia M−1M =

(1− 1

M

)= #casi favorevoli ( 6=y)

#casi possibili la prob-abilita che l’algoritmo fallisca, avendo effettuato una sola interrogazione all’oracolo.

Poiche faccio Q interrogazioni la probabilita diventa(1− 1

M

)Q. Quindi la probabilita

di successo e ε = 1−(1− 1

M

)Q.

Da notare che la precedente probabilita si approssima a QM .

Teorema 21. Per ogni X0 ⊆ X \x con |X0| = Q−1, la probabilita di successo,dell’Algoritmo 4.2, e

ε = 1−(

1− 1

M

)Q−1

Consideriamo l’Algoritmo 4.3 che risolve il terzo problema.

Questo algoritmo e analizzato utilizzando una probabilita analoga al paradosso del

compleanno. Questo dice che basta un gruppo di 23 persone per avere una probabilita

pari a 12 di avere due persone che sono nate lo stesso giorno. Supponiamo che la

funzione h ha come dominio l’insieme degli esseri umani viventi, e ∀x h(x) e il relativo

compleanno. Trovare due persone con lo stesso compleanno equivale a trovare una

collisione nella funzione hash. In questo caso, il paradosso del compleanno, dice che

l’Algoritmo 4.3 ha probabilita di successo pari a 12 quando Q = 23 e M = 365.

Teorema 22. Per ogni X0 ⊆ X \ x con |X0| = Q, la probabilita di successo,dell’Algoritmo 4.3, e

ε = 1−(M − 1

M

)(M − 2

M

)· · ·(M −Q+ 1

M

)

74


Dimostrazione. Sia X0 = {x1, · · · , xQ}. Per ogni 1 ≤ i ≤ Q, sia Ei l’evento

′′h(xi) /∈ {h(x1), · · · , h(xi−1)}′′

p(Ei | E1 ∧ E2 ∧ · · · ∧ Ei−1) =M − i+ 1

M

per 2 ≤ i ≤ Q. Quindi, si ha che

p(E1 ∧ E2 ∧ · · · ∧ EQ) =

(M − 1

M

)(M − 2

M

)· · ·(M −Q+ 1

M

)

La probabilita che si abbia almeno una collisione e 1− p(E1 ∧ E2 ∧ · · · ∧ EQ).

Teorema 23 (Paradosso del Compleanno). Nel modello “random oracle”

sono sufficienti Q =√

2M ln 11−ε interrogazioni per avere una collisione con

probabilita ≥ ε.

Dimostrazione. Il Teorema 22 dice che la probabilita di non trovare nessuna collisionee (

1− 1

M

)(1− 2

M

)· · ·(

1− Q− 1

M

)= ΠQ−1

i=1

(1− i

M

)Pongo x = i

M . Se x e un numero reale piccolo, allora 1− x ' e−x. Questa stima ederivata prendendo i primi due termini dell’espansione in serie

e−x = 1− x+x2

2!− x3

3!· · ·

Usando questa stima la probabilita di non trovare collisioni si approssima a

ΠQ−1i=1

(1− i

M

)' ΠQ−1

i=1 e(−iM )

Per una proprieta delle potenze, il prodotto di potenze con uguale base e identicoall’elevare la base alla la somma degli esponenti. Quindi

e−∑Q−1

i=1iM = e

−Q(Q−1)2M

Di conseguenza la probabilita di trovare almeno una collisione e

1− e−Q(Q−1)

2M

Se noi chiamiamo questa probabilita con ε, segue che

e−Q(Q−1)

2M ' 1− ε→ −Q(Q− 1)

2M' ln(1− ε)

75


Q2 −Q ' 2M ln1

1− εSe infine trascuriamo il termine −Q otteniamo

Q '√

2M ln1

1− ε

Tornando al paradosso del compleanno, se prendiamo ε = 12 avremo Q ' 1.17

√M ,

e dato che M = 365, Q ' 22.3. Quindi, come detto precedentemente, basta prendere

23 persone a caso per averne, con probabilita 12 , almeno 2 tra di loro con lo stesso

compleanno.

L’attacco compleanno impone un lower bound alla grandezza del message digest.

Un digest di 40 bit e molto insicuro, in quanto una collisione puo essere trovata, con

probabilita 12 , con solo 220 (circa un milione) di hash casuali. La grandezza minima

accettabile e 128 bit (264 hash) ma e raccomandato usare una dimensione ≥ 160.

4.2.3 Comparazione dei criteri di sicurezza

Nel random oracle model, abbiamo visto che risolvere il problema della Collision e

piu facile che risolvere gli altri problemi. La domanda successiva e vedere se esiste una

riduzione tra i tre problemi che puo essere applicata ad una funzione hash arbitraria.

E abbastanza facile vedere che si puo ridurre il problema Collision al problema

Second Preimage usando l’Algoritmo 4.4.

Supponiamo che ORACLE-2ND-PREIMAGE e un (ε,Q) − algorithm che risolve

il problema Second Preimage per una funzione hash fissata. Se ORACLE-2ND-

PREIMAGE restituisce un valore x′ dato l’input (h, x), allora si ha che x′ 6= x, perche

tale algoritmo e di tipo Las Vegas. Come conseguenza, e chiaro che COLLISION-TO-

76


2ND-PREIMAGE e un (ε,Q)−algorithm che risolve il problema Collision per la stessa

funzione hash.

Questo significa che Collision Resistant =⇒ Second Preimage Resistant.

Una domanda piu interessante e se e possibile ridurre il problema Collision al prob-

lema Preimage. Questo e possibile se un algoritmo che risolve il problema Preimage

con probabilita 1, viene usato per risolvere il problema Collision.

Questa riduzione puo essere fatta con certe assunzioni. Assumiamo che la funzione

h : X → Y abbia X e Y, due insiemi finiti e che |X | ≥ 2|Y|. Supponiamo inoltre che

ORACLE-PREIMAGE sia un (1, Q) − algorithm che risolve il problema Preimage.

ORACLE-PREIMAGE prende in input un message digest y ∈ Y, e trova sempre un el-

emento ORACLE−PREIMAGE(y) ∈ X tale che h(ORACLE−PREIMAGE(y)) =

y.

Teorema 24. Supponiamo che h : X → Y sia una funzione hash con X e Ydue insiemi finiti tale che |X | ≥ 2|Y|. Supponiamo che ORACLE-PREIMAGEsia un (1, Q)− algorithm che risolve Preimage, per una funzione fissata.Allora COLLISION-TO-PREIMAGE e un (1

2 , Q+ 1)− algorithm che risolveCollision, per la funzione fissata.

Questo significa che Collision Resistant =⇒ Preimage Resistant.

77

4.3. Funzioni Hash Iterative Capitolo 4. Funzioni Hash Crittografiche

4.3 Funzioni Hash Iterative

Il problema implementativo delle funzioni hash e che devono trattare stringhe o file

potenzialmente infiniti e comprimerli in 160 bit.

Supponiamo che compress : Zm+t2 → Zm2 e una funzione di compressione collision

resistant.

4.3.1 Costruzione Merkle-Damgard (MD)

• compress : Zm+t2 → Zm2

• Suddivido: Data una stringa x t.c.|x| ≥ m + t + 1 bit la suddivido in blocchi di

t− 1 bit con t ≥ 2.

x = x1 || x2 || x3 || · · · || xk

• Padding: Tutti gli xi sono di lunghezza t−1 tranne forse xk che puo essere |xk| ≤t − 1. In questo caso riempo xk con tanti 0 quanti ne servono per raggiungere

|xk| = t− 1.

Considero, dunque,

x = x1 || x2 || x3 || · · · || xk || xk+1

Inserisco un ulteriore blocco xk+1 che e la rappresentazione binaria di t− 1− |xk|cioe del numero di 0 che ho aggiunto.

• Esecuzione: Pongo IV = 0000 · · · 0→ m+ 1 bit

Z1 = IV || x1

Z2 = compress(Z1) || 1 || x2

...

Zi+1 = compress(Zi) || 1 || xi+1

...

Zk = compress(Zk−1) || 1 || xk

Zk+1 = compress(Zk) || 1 || xk+1

h(x) = compress(Zk+1)

78


Teorema 25 (Compress). Se compress e resistente alle collisioni, allora lo eanche h.

Dimostrazione. Se ho x 6= x′ con h(x) = h(x′) allora trovo s e s′ tali che compress(s) =compress(s′).

Supponiamo che x 6= x′ siano tali che h(x) = h(x′). Distinguiamo 3 casi:

• Caso 1 : Se |x| 6≡ |x′| (mod t− 1) (la differenza non e multiplo di t− 1).

|x| 6≡ |x′| (mod t− 1)⇐⇒ |xk| 6= |x′k| ⇐⇒ xk+1 6= x′k+1

h(x) = compress(compress(Zk) || 1 || xk+1)

h(x′) = compress(compress(Z ′k) || 1 || x′k+1)

Dato che h(x) = h(x′) allora trovo anche due sequenze lunghe m + t con stessocompress, ma invece

s = compress(Zk) || 1 || xk+1

s′ = compress(Z ′k) || 1 || x′k+1

che sono diverse; quindi ho trovato una collisione.

• Caso 2 : Se |x| ≡ |x′| (mod t− 1) e |x| = |x′| In questo caso e uguale anchel’ultimo blocco, e quindi anche il numero di passi.

Poiche x 6= x′ deve esserci almeno una volta che Zi 6= Z ′i. Quindi:

∃ Zi 6= Z ′i ∧ Zj = Z ′j ∀j > i =⇒ Zi+1 = Z ′i+1 =⇒

compress(Zi) || 1 || xi+1 = compress(Z ′i) || 1 || x′i+1 =⇒

compress(Zi) = compress(Z ′i)

Ho trovato lo stesso valore di compress per due diversi input.

• Caso 3 : Se |x| ≡ |x′| (mod t− 1) e |x| < |x′| In questo caso le due sequenzesaranno cosı fatte:

x x′

Z ′1

79


Z ′2

...

Z1 Z ′1+h

Z2 Z ′2+h

...

Zk Z ′k+h

Zk+1 Z ′k+1+h

Poiche x 6= x′ deve esserci almeno una volta che Zi 6= Z ′i+h∧Zi+1 = Z ′i+h+1 allora

Zi+1 = Z ′i+h+1 =⇒

compress(Zi) || 1 || xi+1 = compress(Z ′i+h) || 1 || xi+h+1

Ho trovato ancora una collisione per compress.

Supponiamo che Zi e Z ′i+h non siano mai diverse allora

Z2 = Z ′2+h =⇒

compress(Z1) || 1 || x2 = compress(Z ′1+h) || 1 || x2+h =⇒

compress(Z1) = compress(Z ′1+h) =⇒ compress(000 · · · 0 || x1) = compress(Z ′1+h)

Ho trovato una collisione comunque in quanto al secondo membro non siamo alprimo passo quindi non saranno tutti 0; in particolare l’ultimo della sequenza e1 di sicuro per via di come e costruito il metodo.

4.3.2 SHA-1 (Secure Hash Algorithm)

SHA e lo standard NIST per le funzioni hash. Si basa sullo schema visto preceden-

temente. Le caratteristiche sono:

• m = 160

• t = 512

• compress : Z512+1602 → Z160

2

• Limitazione: |x| ≤ 264 − 1 ' 1, 8 · 1019. Se si considera che 1Gb ' 1010, x puo

essere al massimo 2 miliardi di Gb (non e alla fine una grande limitazione).

80


Questo succede per via del padding. Infatti l’ultimo blocco e di lunghezza 448 bit

ed e composto da un 1 in prima posizione e da tutti 0. A questo viene aggiunta la

rappresentazione binaria di |x| che al massimo puo essere lunga 64 bit (512−448).

La figura seguente mostra in dettaglio l’algoritmo.

La differenza che c’e tra SHA-0 e SHA-1 e che nel secondo e stata introdotta la

rotazione dei bit.

81


4.3.3 MAC (Message Authentication Codes)

Consiste nell’uso delle funzioni hash nei processi di autenticazione.

Si fa l’hash di un file concatenato ad una chiave segreta. Solo chi conosce la chiave

corretta puo ricalcolare il giusto hash.

L’idea banale e che invece di impostare IV = 000 · · · 0, lo si imposta IV = k. Questa

soluzione pero non funziona, in quanto l’hacker senza conoscere la chiave e in grado

di mandare un secondo messaggio autentico. Se l’hacker effettua n ulteriori iterazioni

di compress sull’hash spedito al destinatario, quello che ne risulta e un hash ancora

valido; questo perche implicitamente utilizza la chiave segreta.

Formalmente questa soluzione e definita cosı

h(k, x) = SHA− 1(k || x)

Dato h(k, x) l’hacker puo calcolare h(h(k, x) || x′) = compress(h(k, x) || x′), che e

ancora un hash valido.

Una soluzione sicuramente migliore e attaccare la chiave anche in fondo. Comunque

quella definita come standard e il double hashing o HMAC. Esso e uno standard dal

2002. E cosı definito:

HMACk(x) = SHA− 1((K ⊗ opad) || SHA− 1((K ⊗ ipad) || x))

dove ipad = 3636 · · · 36 e opad = 5C5C · · · 5C

MAC Incondizionatamente Sicuri

Incondizionatamente sicuri significa sicuri dal punto di vista formale (matematico).

Un sistema di autenticazione MAC e una quaterna (X ,Y,K,H) dove:

• X : l’insieme dei possibili messaggi

• Y: l’insieme delle etichette (o tag, o digest)

• K: l’insieme delle possibili chiavi

• H: famiglia di funzioni hash. H = {hK : X → Y | k ∈ K} (C’e una funzione per

ogni chiave).

Gli attacchi ad un sistema di autenticazione sono due tipi:

82


1. Impersonification: Dal nulla l’hacker crea una coppia (x, y), la invia al desti-

natario sperando che venga accettata. y = hk0(x) l’hacker spera di aver scelto la

giusta k0.

2. Substitution: L’hacker vede passare un messaggio, quindi conosce (x, y) con y =

hk0(x), e invia un’altra coppia (x′, y′) sperando che y′ = hk0(x′).

Per descrivere un sistema del genere ci avvaliamo di una matrice di autenticazione,

simile alla matrice di codifica gia utilizzata. Le colonne sono identificate dai possibili

messaggi, mentre le righe dalle possibili chiavi; all’incrocio della riga i-esima e della

colonna j-esima c’e hki(xj) = yij , ossia l’etichetta del messaggio xj creata con la chiave

ki.

ESEMPIO 1:

X = Z3 = {0, 1, 2}Y = Z3

K = Z23

Confrontiamo due matrice di autenticazione; la prima e data dalla figura seguente,

creata dalla funzione h(a,b) = ax+ b (mod 3).

la seconda e questa creata casualmente

Vediamo quale delle due e migliore, dal punto di vista dei due attacchi:

• Impersonification: Nella prima p((x, y) ACCETTATA) = 13 ∀x ∈ X , ∀y ∈ Y.

Nella seconda varia; per esempio p((0, 0) ACCETTATA) = 1. L’hacker ha una

sola possibilita di scelta che e k = (0, 2).

La migliore delle due e senza dubbio la prima.

83


• Substitution: L’hacker vede passare la coppia (0, 1). L’obiettivo e trovare un altro

messaggio con un’altra etichetta valida.

Nella prima, le chiavi possibili sono 3, quindi la probabilita che il destinatario

accetti la nuova etichetta e 39 = 1

3 .

Nella seconda, le chiavi possibili sono 6; se l’hacker manda (1, 2) la probabilita

che il destinatario la accetti e 56 .

Quindi ancora una volta la prima e la migliore.

Formalizziamo, dunque, quando una funzione hash e ottima.

Impersonification. Definiamo PAY OFF (x, y) come la probabilita che (x, y) sia ac-

cettata. L’obiettivo e garantire che il massimo PAYOFF sia il piu basso possibile.

PAY OFF (x, y) =|{k ∈ K | hk(x) = y}|

|K|

Fissiamo y e facciamo variare solo x. Conto le chiavi che mandano le x nella y

fissata. In pratica conto tutte le chiavi.

∑y∈Y

PAY OFF (x, y) =

∑y∈Y |{k ∈ K | hk(x) = y}|

|K|=|K||K|

= 1

La somma di tutti i PAYOFF al variare di y e 1.

84


=⇒

Almeno un valore di x e tale che PAY OFF (x, y) ≥ 1|Y| . Questo perche se li

sommo, e tutti sono < 1|Y| non arrivo a 1; quindi max{PAY OFF (x, y)} ≥ 1

|Y| .

In particolare vale = quando ogni PAY OFF (x, y) = 1|Y| .

Questo e il caso migliore perche non ce n’e uno che prevale sugli altri, come

succedeva nella prima funzione dell’ESEMPIO 1.

Substitution . PAY OFF (x′, y′, x, y) e la probabilita che la coppia (x′, y′) sia accetta-

ta sapendo che (x, y) lo e. L’obiettivo e che il massimo di questi PAY OFF (x′, y′, x, y)

sia il piu piccolo possibile.

PAY OFF (x′, y, x, y) = p((x′, y′) ACCETTATA | (x, y) ACCETTATA) =

p((x′, y′) ACCETTATA) ∧ (x, y) ACCETTATA

p((x, y) ACCETTATA)=

|{k∈K | y′=hk(x′)∧y=hk(x)}||K|

|{k∈K | y=hk(x)}||K|

=

|{k ∈ K | y′ = hk(x′) ∧ y = hk(x)}|

|{k ∈ K | y = hk(x)}|

Come prima facciamo variare y′ e contiamo le chiavi che verificano il numeratore.

∑y′∈Y

PAY OFF (x′, y′, x, y) =

∑y′∈Y |{k ∈ K | y′ = hk(x

′) ∧ y = hk(x)}||{k ∈ K | y = hk(x)}|

=

|{k ∈ K | y = hk(x)}||{k ∈ K | y = hk(x)}|

= 1

Come prima, il massimo max{PAY OFF (x′, y′, x, y)} ≥ 1|Y|

Definizione 25 (Strongly Universal). Dato (X ,Y,K,H) si dice StronglyUniversal se valgono due proprieta:

a) PAY OFF (x, y) = 1|Y| ∀x ∈ X ,∀y ∈ Y

b) PAY OFF (x′, y′, x, y) = 1|Y| ∀x, x

′ ∈ X e ∀y, y′ ∈ Y

85


Teorema 26 (Condizione equivalente). Una quaterna (X ,Y,K,H) eSTRONGLY UNIVERSAL ⇐⇒ ∀x, x′ ∈ X , x 6= x′, ∀y, y′ ∈ Y

|{k ∈ K | hk(x) = y ∧ hk(x′) = y′}| = |K||Y|2

Prese comunque x 6= x′, y e y′ il numero di chiavi che mandano x in y e x′ in y′

sono |K||Y|2 .

Nell’ESEMPIO 1, k = 9 e y = 3 cioe 99 = 1 chiave. Se proviamo a controllare risulta

proprio 1 quindi la prima tabella rappresenta un sistema MAC Strongly Universal.

Dimostrazione. ⇐=

a)

PAY OFF (x, y) =|{k ∈ K | hk(x) = y}|

|K|

|{k ∈ K | hk(x) = y}||K|

=

∑y′∈Y |{k ∈ K | y′ = hk(x

′) ∧ y = hk(x)}||K|

=

∑y′∈Y |K|

|Y|2

|K|=

|Y| · |K||Y|2|K|

=

|K||Y|

|K|=|K||Y|· 1

|K|=

1

|Y|

b)

PAY OFF (x′, y′, x, y) =|{k ∈ K | hk(x) = y ∧ hk(x′) = y′}|

|{k ∈ K | hk(x) = y}|=

|K||Y|2|K||Y|

=

|K||Y|2

· |Y||K|

=1

|Y|

Generalizziamo l’ESEMPIO 1.

X = Zp con p primo.

Y = Zp

K = Z2p

h(a,b)(x) = ax+ b (mod p)

Proposizione 2. Questa famiglia e Strongly Universal.

86


Dimostrazione. Fisso x, x′, y, y′ ∈ Zp; cerco k = (a, b) ∈ Z2p tali che

h(a,b)(x) = y ∧ h(a,b)(x′) = y′ =

{ax+ b = yax′ + b = y′

Questo e un sistema lineare con 2 incognite (a e b). Si ha che

det

(x 1x′ 1

)= x− x′

x− x′ 6= 0 perche x 6= x′.

Quindi ho un sistema di Kramer a una soluzione. Ho trovato una sola chiave infatti

|K| = p2

|Y2| = p2= 1

Non ha senso applicare questo sistema, perche le possibili chiavi sono molte di piu

dei possibili messaggi.

ESEMPIO 2:

X = Z l2 \ {0}Y = Zp

K = Z lp

hk(x) = h(k1,k2,···,kl)(x1, x2, · · · , xl) = k1x1 + k2x2 + · · ·+ klxl (mod p).

Anche in questo caso abbiamo piu chiavi che messaggi, quindi non e applicabile,

comunque, calcoliamo preventivamente

|K||Y|2

=pl

p2= pl−2

Conto le chiavi (k1, · · · , kl) tali che h(k1,···,kl)(x1, · · · , xl) = y∧h(k1,···,kl)(x′1, · · · , x′l) =

y′ al variare di y e y′.

{h(k1,···,kl)(x1, · · · , xl) = y

h(k1,···,kl)(x′1, · · · , x′l) = y′

=

{k1x1 + k2x2 + · · ·+ klxl (mod p) = y

k1x′1 + k2x

′2 + · · ·+ klx

′l (mod p) = y′

La matrice dei coefficienti e (x1 x2 · · ·xlx1 x2 · · ·xl

)

87


Per il teorema di Rouche-Capelli ha rango 2 quindi pl−2 soluzioni.

Teorema 27. Un sistema (X ,Y,K,H) che si Strongly Universal non epraticabile perche

|K| ≥ |X | · |Y|

Abbiamo ottenuto lo stesso risultato del ONE-TIME-PAD; abbiamo potenzialmente

un sistema perfetto ma non lo possiamo usare. Ci dobbiamo accontentare di famiglie

ε-Strongly Universal.

Definizione 26. (X ,Y,K,H) si dice ε-Strongly Universal sePAY OFF (x, y) = PAY OFF (x′, y′, x, y) = 1

|Y| ≤ ε

E possibile costruire una famiglia che sia 1219

-Strongly Universal con

• X = 2217

• Y = 220

• K = 284

In conclusione rinunciamo ad un minimo di sicurezza per avere una maggiore prat-

icabilita. In realta ancora non ci sono gli strumenti neanche per realizzare un sistema1

219-Strongly Universal.

4.3.4 Un po di storia

• 1990→ MD4 (Rivest)

• 1992→ MD5

• Primo standard 1993→ SHA-0

• 1995→ SHA-1

• 2002→ SHA-2

SHA− 256

SHA− 384

SHA− 512

SHA− 224

• E in corso la gara per SHA-3

88

Capitolo 5

Crittografia Asimmetrica

5.1 Introduzione

La crittografia e sempre stata presente, fin dai tempi antichi, ma il suo utilizzo e

diventato indispensabile nella nostra epoca perche sono aumentate le comunicazioni.

Il problema della crittografia simmetrica e che prima che il messaggio sia trasmesso,

mittente e destinatario devono incontrarsi e mettersi d’accordo non solo sul metodo di

cifratura, ma anche e soprattutto sulla chiave segreta da utilizzare. Oggi questo non e

piu possibile. Basti pensare agli acquisti su internet; se si vuole comprare un oggetto

in America, prima si deve andare in America per accordarsi sulla chiave. E una cosa

senza senso. Supponiamo che questo non sia un problema allora dovremmo mettere

in piedi un sistema di scambio di chiavi, che non puo risultare efficiente. Prendiamo

l’esempio della chat. Se n sono i componenti della chat e, potenzialmente si vuol far

comunicare tutti con tutti, si dovrebbe creare un sistema che permetta di scambiare

N◦Chiavi = (n− 1) + (n− 2) + (n− 3) + · · ·+ 1 =

n−1∑k=1

k =n(n− 1)

2

Gia in una semplice chat il numero e grande; quando la popolazione e enorme, come

in internet, il metodo diventa impraticabile.

La crittografia asimmetrica nasce per porre rimedio a questo problema. Essa dis-

tingue il metodo di cifratura da quello della decifratura. La chiave per la fase di cri-

fratura e pubblica, cioe conosciuto da tutti quindi anche dall’hacker. La chiave per la

seconda e noto solo al destinatario.

In teoria un sistema del genere non e possibile, perche se io conosco l’algoritmo

che mi realizza la cifratura e facile leggendo il codice creare un algoritmo che e il suo

inverso. Infatti e cosı, pero esistono delle funzioni (trappola) facili da calcolare in un

senso, ma impossibili o quantomeno computazionalmente impossibili da invertire.

89

5.1. Introduzione Capitolo 5. Crittografia Asimmetrica

Facciamo due esempi banali. E facile dato un nome trovare il numero sull’elenco

telefonico; e difficile dato un numero trovare il nome. E facile dati gli ingredienti e la

ricetta, fare il dolce. E difficile mangiando il dolce risalire agli ingredienti e alla ricetta.

A noi, chiaramente, servono trappole matematiche. Una funzione trappola e

B = logAX

Il logaritmo e la funzione inversa dell’esponenziale. Mentre e molto facile calcolare

l’esponenziale (X = AB), e molto difficile calcolare l’esponente che applicato ad A mi

da X. Questa difficolta si percepisce gia dalla definizione di logaritmo.

Quindi per cifrare possiamo usare l’esponenziale, e per decifrare usiamo il logaritmo.

E scontato che la difficolta computazionale si ha quando i numeri in gioco sono molto

grandi, e ancora di piu quando gli attori in gioco sono elementi di un campo finito molto

grande. Un protocollo che si basa sulla trappola del logaritmo e il seguente Protocollo

Diffie-Hellman.

Questi due matematici furono i primo a proporre un sistema di crittografia asim-

metrica. Il protocollo e il seguente. G e S sono gli attori della comunicazione; G e un

client e S e un server. Entrambi possiedono delle informazioni segrete e non:

(A) Possiede M , cioe il messaggio che e segreto

(S) Possiede B, cioe l’esponete che e segreto, e A e AB che sono pubblici.

Il protocollo funziona se l’hacker non puo fare logAAB = B perche e computazional-

mente difficile.

G→ S : {M · (AB)C , AC}

con C un numero casuale scelto dal mittente.

S ricostruisce M dato che M = M ·(AB)C

(AC)Bperche (AB)C = (AC)B.

L’hacker non potra mai fare questa operazione semplice perche non conosce B.

Una seconda trappola e quella ottenuta moltiplicando due numeri primi. Dati p e

q primi molto grandi e facile calcolare il prodotto pq, mentre e difficile fattorizzare pq.

I numeri primi sono gli atomi dell’aritmetica. Sono un oggetto misterioso. Non ci

sono molti teoremi che regolano il loro comportamento, e questo forse e il motivo per

cui non si riesce a trovare un algoritmo efficiente per la fattorizzazione.

90


Si sa che sono infiniti. Si sa che da 0 a n sono circa nlnn .

Esistono delle congetture che non si riescono a dimostrare, come per esempio la

congettura di Goldbach, e cioe che ogni numero pari maggiore di 2 e somma di due

numeri primi.

4 = 3 + 1

6 = 3 + 3

8 = 5 + 3

10 = 7 + 3

...

n = p+ q ?

Oppure l’ipotesi di Riemann che e uno dei 7 problemi del millennio (quindi tralas-

ciamo).

Un sistema che usa questa trappola e l’RSA inventato nel 1977 da Rivest, Shamir

e Adleman, tre ricercatori del MIT. Intuitivamente N = pq fungera da chiave pubblica

mentre p e q saranno la chiave privata. Inizialmente l’opinione pubblica fu scettica

su questo metodo, allora essi pubblicarono delle sfide; invitavano (sotto ricompensa) a

fattorizzare dei numeri che loro proponevano:

• RSA 129 → 129 cifre decimali. Ci vollero 17 anni (1994).

• RSA 576 → 576 bit (174 decimali). Ci vollero 9 anni (2003).

Comincio a diventare popolare, fino ad avere l’enorme diffusione che ha attualmente,

proprio perche la gente tocco con mano la difficolta di fattorizzare tali numeri.

Un’altra applicazione della crittografia asimmetrica e la firma digitale. La firma

digitale risolve i difetti della firma autografa:

• Sempre la stessa indipendentemente dal documento.

• Inadatta a documenti elettronici, visto che l’obiettivo, specialmente della pubblica

amministrazione, e quello di eliminare il cartaceo.

• La verifica non e immediata, servono perizie calligrafiche, che hanno tempi lunghi,

sono costose e potenzialmente sbagliate poiche fatte da un uomo.

91


L’idea e, applicare al documento la cifratura con la chiave privata dell’utente che

firma, e affiancare il risultato al documento. Chiunque volesse verificare la firma applica

la cifratura con la chiave pubblica di chi a firmato, se il risultato e uguale al documento

stesso allora la firma e accettata. Questo basta a risolvere i problemi sopra citati.

Da notare la differenza con MAC: nel caso della firma digitale tutti possono verificare

la firma mentre nel MAC solo chi possiede la chiave puo accettare o rifiutare l’etichetta.

Questo ha portato alla nascita del cosiddetto PKI (Public Key Infrastructure), e

quindi alla nascita delle CA (Certification Autority), cioe enti autorizzati/certificati

che emettono sotto richiesta dei certificati, che contengono la chiave pubblica, e garan-

tiscono l’identita di colui che ha richiesto uno specifico certificato. Questo risparmia,

agli attori della comunicazione, di doversi sempre scambiare le chiavi pubbliche prima

di comunicare, che evita, tra l’altro, problemi di sicurezza.

Il problema della crittografia a chiave asimmetrica e che e molto onerosa dal punto

di vista computazionale e necessita di chiavi molto grandi (1024-2048 bit) per garantire

la “totale” sicurezza. Per essere precisi bisogna dire che essa viene utilizzata non per

cifrare un documento ma per scambiare in maniera sicura una chiave simmetrica; per

lo stesso motivo non si firmera l’intero documento ma l’hash.

Poiche la crittografia serve anche nelle comunicazioni cellulari e nelle televisioni

a pagamento e che strumenti come cellulari, appunto, e decoder hanno risorse molto

limitate, non paragonabili a un pc, serve un nuova sistema. Questa idea prende il nome

di ECC (Elliptic Curves Chryptography), realizzata mediante trappole geometriche che

sono ancora piu difficili delle aritmetiche. Funzione trappola piu difficili mi permettono

di diminuire la lunghezza della chiave. Si passa dal lavorare con i numeri a lavorare

con i punti del piano cartesiano.

Le curve ellittiche sono generalmente polinomi di grado 3. Su queste curve e possi-

bile costruire un’operazione sui punti. Un’operazione e una relazione che associa a due

elementi un terzo. Si puo, per esempio, utilizzare il prodotto tra punti, e quindi adottare

nuovamente il protocollo Diffie-Hellman (ECDH), in quanto e relativamente facile, dato

un punto P della curva calcolare PB, mentre e difficile calcolare logP PB = B).

Lo sviluppo della ECC e stato, inizialmente, ostacolato da RSA che ormai aveva

conquistato la scena. Inoltre i sui ideatori non erano ben visti dal governo americano.

Attualmente pero nei dispositivi piu sofisticati e negli strumenti militari si usa l’ECC.

92

5.2. Ulteriore teoria dei numeri Capitolo 5. Crittografia Asimmetrica

5.2 Ulteriore teoria dei numeri

5.2.1 Algoritmo Euclideo

Problema 4. Dato un elemento a ∈ Z∗m, a e invertibile in Zm ⇐⇒gcd(a,m) = 1.

Trovare l’inverso 1a (o a−1)

La soluzione e scrivere 1 come combinazione di x e y.

1− ax−my =⇒ ax ≡ 1 (mod m)

cioe (1− ax) e multiplo di m.

1− ax ≡ 0 (mod m)→ 1 ≡ ax (mod m)→ x ≡ 1

a(mod m)

Questo lo possiamo fare per via dell’identita di Bezout.

Teorema 28 (Identita di Bezout). Dati a e m ∃x, y con gcd(a,m) = ax+my

L’algoritmo Euclideo trova x e y dalle divisione successive.

1) m = q1 · a+ r2 con 0 ≤ r2 < m

2) a = q2 · r2 + r3 con 0 ≤ r3 < r2

2) r2 = q3 · r3 + r4 con 0 ≤ r4 < r3...

i) ri = qi+1 · ri+1 + ri+2 con 0 ≤ ri+2 < ri+1...

m-1) rm−1 = qm · rm + 0

L’ultimo resto non nullo e rm = gcd(a,m)

ESEMPIO: gcd(54, 360)

360 = 6 · 54 + 36

54 = 1 · 36 + 18

36 = 2 · 18 + 0

93


Quindi gcd(360, 54) = 18→ 18 = 360x+ 54y

18 = 54− 36

18 = 54− (360− 6 · 54)

18 = 7 · 54 + (−1) · 360

Quindi x = −1 e y = 7.

Questo metodo e molto piu veloce di quello che fattorizza a e m in numeri primi.

La complessita e in funzione del #bit di m.

K = #bit di m = blog2mc+ 1

Il #passi?. Male che vada il resto decresce di 1 ad ogni iterazioni, quindi al massimo

impieghera m passi. Ma m e esponenziale in K quindi detta cosı non sembra poi cosı

efficiente.

In realta il resto, nel caso peggiore, dimezza ogni 2 iterazioni.

Osservazione 10.ri+2 ≤

ri2

Dimostrazione.ri = qi+1ri+1 + ri+2 ≥ ri+1 + ri+2

poiche si ha che ri+2 < ri+1 allora

ri+1 + ri+2 > ri+2 + ri+2 = 2ri+2

e quindi

ri+2 ≤ri2

Da cio segue che

#passi ≥ 2K = 2 · blog2mc+ 1

ossia una complessita temporale polinomiale.

94


Quando pero si devono ricavare x e y, come dice l’Identita di Bezout, si deve riper-

correre all’indietro l’algoritmo euclideo, con conseguente aumento di tempo. Per fare

questo, inoltre, occorre mantenere in memoria tutti i passaggi dell’algoritmo, con un

notevole spreco di spazio.

Si usa, dunque, il cosiddetto algoritmo Euclideo Esteso, che modificato aggiungendo

alcuni parametri proprio per evitare questo inconveniente.

ESEMPIO:

Quindi 3 = m · 2 + a · (−13).

s e t sono calcolati in modo tale da avere ri = sim+ tia ∀i e cioe

si = si−2 − qi−1si−1

ti = ti−2 − qi−1ti−1

Da notare che non serve tenere tutta la tabella in memoria ma soltanto le ultime

tre righe. Questo non aumenta la complessita temporale e la complessita spaziale e

costante, quindi trascurabile.

Proposizione 3.ri = sim+ tia ∀i

Dimostrazione. Per induzione.

s0 = 1, t0 = 0s1 = 0, t1 = 1

si+1 = si−1 − siqiti+1 = ti−1 − tiqi

per i = 0

95


r0 = s0m+ t0a = m

r1 = s1m+ t1a = a

Supponiamo che ri = sim+tia sia vero e dimostriamo che e vero ri+1 = si+1m+ti+1a

ri+1 = si+1m+ ti+1a

ri+1 = (si−1 − siqi)m+ (ti−1 − tiqi)a

ri+1 = si−1m+ ti−1a− siqim− tiqia

ri+1 = si−1m+ ti−1a− qi(sim+ tia)

poiche ri−1 = si−1m+ ti−1a e ri = sim+ tia si ha

ri+1 = ri−1 − qiri

Quindiri−1 = qiri + ri+1

come succede nell’algoritmo euclideo.

Per tornare al problema originario, cioe trovare a−1 ∈ Zp il procedimento e questo:

1. Cercare x e y tali che 1 = ax+my = sm+ ta

2. Riduco l’espressione (mod m)

Poiche sm ≡ 0 (mod m) si ha che

1 = ta→ 1

a= t

di conseguenza l’ultimo t trovato e l’inverso.

Per trovare a−1 ∈ Fq, il procedimento e lo stesso.

ESEMPIO: trovare 1x2∈ F8 = Z2[x]/(x3 + x+ 1)

F8 = {0, 1, x, x+ 1, x2, x2 + 1, x2 + x, x2 + x+ 1}

p = x3 + x+ 1

a = x2

96


Quindi 1 = (x+ 1)(x3 + x+ 1) + (x2 + x+ 1)(x2), che ridotto modulo (x3 + x+ 1)

diventa 1 = (x2 + x+ 1)(x2) e quindi

1

x2= x2 + x+ 1→ 1

100= 111

5.2.2 Metodo dell’elemento primitivo

In un campo finito c’e un’alternativa per calcolare l’inverso di un elemento, che si

basa sull’elemento primitivo (Definizione 23).

Se riesco a trovare un elemento primitivo allora il calcolo dell’inverso e banale.

Infatti

(ωi)−1 =1

ωi=ωq−1

ωi= ωq−1−i

Perche 1 = ωq−1?

Sia (G, ·) un gruppo finito e g ∈ G. Si indica con 〈g〉 il gruppo ciclico generato da g

〈g〉 = {g, g2, g3, · · · , gh = 1}

Mi fermo quando incontro l’elemento neutro perche da questo momento in poi la

sequenza si rigenera identica.

Definizione 27. h si dice periodo di g, cioe il minimo intero positivo per cuigh = 1.

Osservazione 11. |〈g〉| = h

Osservazione 12. 〈g〉 e sottogruppo di G, perche (〈g〉, ·) e un gruppo ed egenerato a partire da G.

97


In conclusione

Teorema 29 (Teorema di Lagrange). Siano G un gruppo finito e H unsottogruppo di G =⇒ |H| | |G|

e quindi h | |G|

APPLICAZIONE:

• F ∗q = (G \ {0}, ·)

• ω ∈ F ∗q ⇐⇒ il periodo di ω e q − 1 perche |F ∗q | = q − 1 e non q dato che ho tolto

lo 0.

Osservazione 13. G gruppo finito e g ∈ G

g|G| = 1

Dimostrazione. Sia h il periodo di g allora

1. gh = 1

2. h | |G|

quindi

hk = |G|

=⇒

g|G| = ghk = (gh)k = 1k = 1

Applicato al campo finito, se g ∈ F ∗q

gq−1 = 1

Teorema 30 (Teorema di Fermat). Quando p 6| a

ap−1 ≡ 1 (mod p)

98


Ricerca dell’elemento primitivo

Il metodo piu semplice per trovare l’elemento primitivo e per tentativi, cioe:

for a ∈ Fq∗∀i ∈ {1, · · · , (q − 1)}CALCOLA ai

end

Se non ottengo mai 1 allora a e′ primitivo

end

In realta non e necessario calcolare tutte le potenze di a ma solo j di queste:

aq−1j ∀j divisore primo di q − 1

ESEMPIO: 2 primitivo? in Z∗17

q − 1 = 16 = 24

j puo essere solo 2; basta calcolare 2162 = 28.

Se ∃j t.c. aq−1j ≡ 1 (mod 17) =⇒ a NON PRIMITIV O

Osservazione 14. Se un elemento a non e primitivo in Zp, e sia e il suoperiodo, allora e | q − 1.

e = {1, 2, 4, 8, 16}ae = 1

Se fosse a4 = 1 anche a8 = 1.

Proposizione 4. a ∈ F ∗q , a e PRIMITIVO ⇐⇒ aq−1j 6=

1 ∀j divisore primo di q − 1e j > 1 (caso banale).

Dimostrazione. =⇒ E ovvia per definizione, perche essendo primitivo, per qualsiasi

valore di q−1j , a

q−1j non fa 1.

⇐=

Sia per assurdo a non primitivo, e che e sia il periodo di a. Per il Teorema diLagrange (Teorema 29) e | q − 1 quindi lo posso scrivere come

es = q − 1→ e =q − 1

s

99


e quindi

aq−1s = 1

Se s e primo pongo j = s e ho dimostrato, altrimenti proseguo.

Sia j divisore primo di s.

q − 1 = se = (jv)e

quindi q−1j = ve e dunque

aq−1j = ave = (ae)v = 1v = 1

5.2.3 Teorema Cinese dei Resti

Teorema 31. Siano m1,m2,m3, · · · ,mn interi a coppie primi fra loro, e siaX ∈ Z.

Se conoscoX (mod m1) = a1

X (mod m2) = a2

...

X (mod mn) = an

=⇒ posso risalire in modo univoco a X.

E lo posso fare cosı

X =n∑i=1

aiMiyi (mod M)

con Mi = Mmi

, yi = M−1i e M = Πn

i=1mi.

A cosa serve?

Se voglio conoscere X (mod M), con M molto grande posso ricavarlo sommando

i resti ottenuti dividendo X per i sui fattori. Quindi abbasso la complessita. In RSA

m1 = p e m2 = q, cioe la chiave privata.

Osservazione 15. ∃yi ⇐⇒ gcd(Mi,mi) = 1 (sono primi tra loro).

100


Dimostrazione. Per definizione se yi e inverso di Mi si ha che

yi ≡M−1i (mod mi)

ossiayiMi ≡ 1 (mod mi)

Ma questo e vero solo quando gcd(Mi,mi) = 1.

Osservazione 16.∑n

i=1 aiMiyi (mod mj) = aj (con mj un mi fissato).

Dimostrazione. Poiche Mjyj ≡ 1 (mod mj) e Mkyk ≡ 0 (mod mj) (perche in Mk,mj ci sta; visto che mj ≡ 0 (mod mj) il prodotto si azzera).

Si ha chen∑i=1

aiMiyi (mod mj) = aj

quindi, ponendo B =∑n

i=1 aiMiyi si ha

B (mod m1) = a1

B (mod m2) = a2

...

B (mod mn) = an

Ho dimostrato che B, costuito da me, si comporta come X.

Resta da provare che X e B siano lo stesso numero, ossia non esiste solo X cheverifica le condizione del teorema.

Basta elencare tutte le possibilita, ossia tutti i valori, che ho per a1, a2, · · · , an.Dato che per a1 ne ho m1, per a2 ne ho m2,· · · e per an ne ho mn, in totale ne hoM = m1m2, · · · ,mn.

Se si esplicitano tutte le M possibilita si vede che X e unico.

ESEMPIO: Trovare X sapendo che

m1 = 3, m2 = 5, m3 = 7

e che

X (mod 3) = 0

X (mod 5) = 2

X (mod 7) = 2

101


Quindi M = 3 · 5 · 7 = 105 e

M1 = m2 ·m3 = 35

M2 = m1 ·m3 = 21

M3 = m1 ·m2 = 15

y1 =1

35(mod 3) =

1

2(mod 3) = 2

y2 =1

21(mod 5) = 1

y3 =1

15(mod 7) = 1

In conclusione

X = a1M1y1 + a2M2y2 + a3M3y3 = (0 · 35 · 2) + (2 · 21 · 1) + (1 · 15 · 1) =

0 + 42 + 30 = 72

5.2.4 Teorema di Eulero

Osservazione 17. Sia Zm, m non necessariamente primo. Sia Z∗m = {a ∈Zm | a INV ERTIBILE} e un gruppo rispetto alla moltiplicazione; infatti, sea e b sono invertibili anche ab lo e. Perche se ne a ne b hanno fattori comunicon m neanche ab ce li avra.

Gli ai che compongono Z∗m sono tutti numeri primi con m e < m. Per sapere la

cardinalita di Z∗m basta applicare la Funzione Toziente di Eulero(Definizione 6).

Nel particolare caso dell’RSA φ(p · q) = (p− 1)(q − 1) dove p e q sono primi.

Teorema 32 (Versione Debole (Fermat)). a ∈ Z∗m =⇒ aφ(m) ≡ 1 (mod m).

Il Teorema di Fermat (Teorema 30) e identico se si sostituisce m con p.

102


Teorema 33 (Versione Forte (RSA)). Sia n = p · q con p e q primi distinti.Si ha

φ(n) = (p− 1)(q − 1)

Siano dati e e d tali che ed ≡ 1 (mod φ(n)).

Sia a ∈ Zn, a 6= 0 alloraaed = a (mod n)

Dimostrazione. ed ≡ 1 (mod φ(n)) quindi ed = 1 + kφ(n).

Basta provare quindi che aφ(n) ≡ 1 (mod n) perche se cosı fosse

aed = a1+kφ(n) = a · akφ(n) = a · (aφ(n))k = a · 1k = a

Possiamo dimostrarlo facendo vedere che

a) aed ≡ a (mod p)

b) aed ≡ a (mod q)

Questo implicheraaed ≡ a (mod pq)

in virtu del Teorema Cinese dei Resti. Inoltre a e l’unico numero per cui vale questo.

a) Se p | a→{a (mod p) = 0aed (mod p) = 0

Se p 6| a→

aed ≡ a1+k(p−1)(q−1) (mod p)

a+ (ap−1)k(q−1)

e in virtu del Teorema di Fermat

a+ (1)k(q−1) = a

b) La dimostrazione e identica al punto precedente; basta sostituire p con q.

103

5.3. RSA Capitolo 5. Crittografia Asimmetrica

5.3 RSA

Il crittosistema RSA si basa sul Teorema di Eulero (Teorema 33), ed e cosı descritto:

Definizione 28 (Crittosistema RSA). E definito da

• P = C = Zn

• K = {(n, p, q, e, d) | ed ≡ 1 (mod φ(n))}

• eK(x) = xe (mod n)

• eK(y) = yd (mod n)

dove (n, e) e la chiave pubblica e (p, q, d) e la chiave privata.

La proprieta fondamentale che deve valere e:

dK(eK(x)) = x→ dK(xe (mod n))→ (xe)d (mod n) = x

e viene scelto in maniera casuale tra gli interi < φ(n) e primi con φ(n); se non fosse

cosı non esisterebbe d cioe il suo inverso (e−1).

La sicurezza e basata sulla segretezza di d. Poiche n e un numero molto grande

l’hacker non riesce a risalire a p e q. Per il possessore della chiave e facile da e ricavare

d utilizzando l’algoritmo euclideo esteso. L’hacker non puo farlo perche non conosce

φ(n) e neanche p e q.

ESEMPIO:

p = 17 e q = 11

n = 187

φ(n) = (p− 1)(q − 1) = 160

e = 7

d = 23 (inverso di 7 modulo 160)

Eseguo l’algoritmo euclideo esteso:

160 = 22 · 7 + 6

7 = 1 · 6 + 1

6 = 6 · 1 + 0

Quindi si ha che 1 = 160x+ 7y → 1 = (−1)160 + (23)7.

104


Supponiamo che le chiavi appena generate siano di Alice. Ora se Bob vuole comu-

nicare in maniera segreta il messaggio 88 deve calcolare

887 (mod 187)

Per calcolare la potenza si usa l’algoritmo Square and Multiply :

88

882 (mod 187) = 77

884 (mod 187) = (882)2 (mod 187) = 772 (mod 187) = 132

887 (mod 187) = 88 · 77 · 132 (mod 187) = 11

Alice riceve 11 e lo decifra cosı calcolando

1123 (mod 187)

Si scompone 23 come somma di potenze di 2 e si calcolano tali potenze:

23 = 16 + 4 + 2 + 1→ 1123 = 1116 · 114 · 112 · 11

11

112 (mod 187) = 121

114 (mod 187) = (112)2 (mod 187) = 55

118 (mod 187) = (114)2 (mod 187) = 33

1116 (mod 187) = (118)2 (mod 187) = 154

1123 = 1116 · 114 · 112 · 11 (mod 187) = 154 · 55 · 121 · 11 (mod 187) = 88

5.3.1 Complessita

La complessita e calcolata in funzione di k = #bit necessari per rappresentare n.

k = blog2mc+ 1

Siano x, y ∈ Zn allora

• Complessita della somma (x+ y): O(k)

• Complessita del prodotto (x · y): O(k2)

• Complessita della divisione (x/y): O(k2). La divisione e intesa quella tra interi

che restituisce q e r.

105


• Complessita del calcolo dell’inverso modulo φ(n): O(k3). E la complessita

dell’algoritmo Euclideo esteso perche il costo e dato da

O(k2 ·#passi algoritmo)→ O(k2 · 2 log φ(n))

Poiche φ(n) ha lo stesso numero di bit di n si ha

O(k2 · 2 log n)→ O(k2 · k)→ O(k3)

• Complessita dell’elevamento a potenza (xy): O(k3). E la complessita dello

Square and Multiply perche

k = log y = #elevamenti al quadrato+#prodotti finali→ O(k2·k+k2·k)→ O(k3)

Contraddizione

Da un lato si assume che sia impossibile fattorizzare un numero di 1024 bit (RSA

1024).

Dall’altro lato si ritiene che Alice possa scegliere comodamente p e q primi di 1024

bit (RSA 2048).

Se non si puo fattorizzare il numero come si puo stabilire se p e primo?

Si fanno dei test probabilistici, e si assume che il numero sia primo con una certa

probabilita molto alta.

5.3.2 Test Probabilistici di primalita

Ci chiediamo: m ∈ Z e primo?

Premessa Matematica

Sia Fq un campo finito, con q dispari.

Definizione 29 (Quadrato). a ∈ Fq, a 6= 0 si dice QUADRATO se ∃b ∈Fq t.c b

2 = a.

Nei numeri reali i quadrati sono i positivi, cioe quelli che hanno le radici.

Teorema 34 (per q dispari). a QUADRATO ⇐⇒ aq−12 = 1

106


Dimostrazione. =⇒

a QUADRATO =⇒ ∃b con a = b2 per definizione

aq−12 = (b2)

q−12 = bq−1 = 1

Perche un numero elevato alla cardinalita di un gruppo fa 1.

⇐=

So che esiste l’elemento primitivo.

F ∗q = {1, ω, ω2, · · · , ωq−2} Quindi

a = ωi =⇒ (ωi)q−12 = 1 =⇒ i · (q − 1)

2≡ 0 (mod q − 1)

Questo significa che

q − 1 | i · (q − 1)

2

cioe posso scriverei · (q − 1)

2= k(q − 1)

i = 2k

a = ωi = ω2k = (ωk)2

I quadrati hanno esponenti pari.

Osservazione 18. aq−12 = ±1

Questo vale sia per i reali sia per i campi finiti.

Osservazione 19. ∀ QUADRATO ∃ 2 elementi di F ∗q che elevati al quadratodanno b2; cioe b e −b.

La conseguenza di questa osservazione e che i quadrati saranno|F ∗q |

2 = q−12 e quindi

se(a

q−12

)2= 1 allora a

q−12 ± 1

ESEMPIO: Z11 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 2 = {1, 3, 4, 5, 9}

Il concetto di quadrato ci servira poi nel Test di Soloway-Strassen e nell’algoritmo

di Dixon.

107


Test di Fermat

Se m e primo =⇒ ∀a 6= 0 (mod m) am−1 ≡ 1 (mod m) (ma non e detto il

contrario).

Il test consiste nello scegliere a 6= 0 (mod m), e calcolare am−1 (mod m)

Se am−1 ≡ 1 (mod m) il test e superato

Se am−1 6≡ 1 (mod m) il test e fallito

Sicuramente se il test fallisce m non e primo. La probabilita che il test venga

superato con un m non primo e < 12 . Basta iterare il procedimento con diversi a per

avere eventi indipendenti, e quindi una diminuzione della probabilita. Mi fermo quando

ho raggiunto una certa probabilita.

Test di Miller-Rabin

E un raffinamento del test di Fermat; si basa sulla stessa considerazione.

Se m e primo allora vale la proprieta

(∗)

{a2is ≡ −1 (mod m)

as ≡ 1 (mod m)

per qualche i.

Per ottenere questo si fattorizza m estraendo solo le potenze di due (divido per 2)

m− 1 = 2ks

am−1 ≡ 1 (mod m)

Si sceglie a 6= 0 (mod m) e si procede iterativamente cosı

a2ks (mod m)

1→ a2k−1s (mod m)

{1 · · ·−1→ FINE

−1→ FINE

alla fine otterro la proprieta (∗).

La probabilita che il test venga superato con m non primo e < 14 . Come prima itero

il procedimento per abbassare la probabilita.

108


Test Soloway-Strassen

Se m e primo allora si haa

m−12 (mod m) = 1 se a QUADRATO in Zm

am−1

2 (mod m) = −1 se a non QUADRATO in Zm

am−1

2 (mod m) = 0 se a ≡ 0 (mod m)

Utilizziamo il simbolo di Jacobi per effettuare il calcolo.

( am

)= a

m−12 (mod m)

(am

)puo essere uguale a 1,−1 o 0.

Valgono le seguenti proprieta:

1.(m1m

)=(m2m

)se m1 ≡ m2 (mod m)

2.(

2m

)=

{1 se n ≡ ±1 (mod 8)

−1 se n ≡ ±3 (mod 8)

3.(m1·m2m

)=(m1m

)·(m2m

)

4.(nm

)=

−(mn

) [m ≡ 3 (mod 4) o

n ≡ 3 (mod 4)(nm

)altrimenti

Seguendo le proprieta elencate si calcola(am

).

Se m e primo →(am

)= −1, quindi m supera il test in questo caso.

Si itera il procedimento fino al raggiungimento della probabilita desiderata.

Calcolare il simbolo di Jacobi ha complessita O(k3), quindi fattibile. La probabilita

che m non primo superi il test e < 12

109


5.3.3 Algoritmi di Fattorizzazione

Sia k = #bit per rappresentare n; 1024 ≤ k ≤ 2048 (nel caso di RSA).

Algoritmo Banale

Si procede per tentativi provando tutti i numeri minori di√n finche non trovo un

divisore.

Complessita

La complessita e esponenziale in k, come del resto per tutti gli algoritmi di fattor-

izzazione, ma questo algoritmo e il peggiore di tutti.

n ∼ 2k

√n = 2

k2

Questo e il numero di passi che compie l’algoritmo; ad ogni passo si effettua una

divisione euclidea. Si ottiene cosı

O(2k2 · k2)

Algoritmo (p-1) di Pollard

Osservazione 20. p | gcd(n, 2p−1 − 1)

L’osservazione e vera in virtu del Teorema di Fermat (Teorema 30). Il problema

si sposta da p a p − 1, che sicuramente non e primo perche e paro. Quindi lo posso

scrivere come

p− 1 = pr11 · pr22 · · · p

rnn

Algoritmo

110


B := 2

while (true)

p := gcd(n, 2B! − 1)

B := B + 1

if(1 < p < n) then return p

end

L’algoritmo si ferma quando trova un divisore non banale cioe 6= 1 e 6= n

Osservazione 21. Se prii ≤ B ∀i allora dopo al piu B iterazioni l’algoritmosi conclude.

Che tradotto significa, se i fattori di p − 1 sono primi bassi allora l’algoritmo si

conclude velocemente.

Dimostrazione. Se prii ≤ B ∀i allora posso scrivere

pr11 · pr22 · · · p

rnn | B!

p− 1 | B!

B! = (p− 1)m

quindi

2B! ≡ 1 (mod p)

2(p−1)m ≡ 1 (mod p) =⇒ (2m)p−1 ≡ 1 (mod p)

dunque, si ha che

p | 2B! − 1 =⇒ p | gcd(n, 2B! − 1)

C’e un problema pero. Puo capitare che invece di trovare p trovo q; questo si verifica

quando entrambi dividono 2B! − 1. Questo significa che otterrei una serie di 1 come

gcd e ad un certo punto n. Il problema e dovuto alla scelta di a = 2 per applicare il

Teorema di Fermat. Cambio a e ripeto il procedimento.

Complessita

Sia B t.c. P rii ≥ B allora la complessita e

O(B · (log2B! · k2 + k3)) = O(B · (k3 + k3)) = O(Bk3)

111


dove B sono il numero di iterazioni, log2B! · k2 il costo di Square and Multiply per

effettuare 2B! e k3 per calcolare gcd(n, 2B! − 1).

Per evitare l’attacco enunciato nell’Osservazione 21 si usa il seguente trucco: si

prende p1 un primo grande e si calcola p cosı

p = 2p1 + 1

cosicche

p− 1 = 2p1

e quindi B = p1 cioe il numero di iterazioni pari a p1, che e elevatissimo.

Algoritmo ρ di Pollard

Osservazione 22. x (mod p) = x′ (mod p) e x 6= x′ =⇒ p | gcd(n, x− x′)

Cioe due numeri sono uguali modulo p se p divide la differenza.

L’obiettivo e trovare x, x′ ∈ Zn t.c. x (mod p) = x′ (mod p).

Prendiamo A ⊆ Zn casuale. La probabilita che in A ci siano x e x′ con x (mod p) =

x′ (mod p) e identica alla probabilita di trovare una collisione nelle funzioni hash, e

cioe, occorre avere, grosso modo, |A| > √p affinche si abbia una probabilita di successo

del 50% (vedi Paradosso del Compleanno - Teorema 23).

Una volta scelto l’insieme devo confrontare tutte le possibili coppie. Quindi se

|A| > √p il #coppie in A =(√pk

)= p

2 .

Costruzione di A

Si sceglie x1 ∈ Zn e si calcolano

x2 = f(x1) (mod p)

x3 = f(x2) (mod p)

...

112


xi+1 = f(xi) (mod p)

con f un polinomio a coefficienti interi (es. f(x) = x2 + 1).

In questo modo si forma una successione di elementi. Ora immaginiamo di costruire

Zp a partire da questi elementi; chiaramente non lo posso fare davvero perche non

conosco p.

Zp = {x1 (mod p), x2 (mod p), · · · , xi (mod p)}

Comunque, se potessi farlo, ad un certo punto mi accorgerei, con buona probabilita,

che due di questi hanno lo stesso valore e quindi

xi (mod p) = xj (mod p)

Quando collidono si ha che p | x − x′, quindi o gcd(n, x − x′) = 1 e dunque p = 1,

oppure x− x′ | n→ p e un fattore di n poiche p | x− x′.

Osservazione 23. Se xi ≡ xj (mod p) allora xi+1 ≡ xj+1 (mod p)

Dimostrazione. Si ha che xi+1 (mod p) = xi (mod p) perche

xi+1 = f(xi) (mod n)

xi+1 (mod p) = (f(xi) (mod n)) (mod p)

Visto che p | n in realta si prende solo il resto della divisione per p, perche

xi+1 = q · n+ r e r = q · p+ s

xi+1 = q · n = q · p · q + r = q · p · q + q · p+ s

xi+1 = p(q · q + q) + s

Quindi xi+1 (mod p) = f(xi) (mod p) e per lo stesso motivo xj+1 (mod p) =f(xj) (mod p) poiche se a xi (mod p) e a xj (mod p) applico la stessa f otterroancora due valori uguali modulo p.

Se trovo una collisione ne ho trovate “tante”.

xi+t ≡ xj+t (mod p) ∀t ≥ 0

113


Con questo metodo il numero di confronti su un insieme di h elementi e h2.

Variante di Floyd

Invece di controllare tutte le possibili coppie xi, xj si controllano solo quelle di tipo

xi′ , x2i′ . Questo mi permette di diminuire i controlli da√p · √p = p a

√p. Perche?

Siano xi e xj due elementi della successione che da origine a Zp, con j > i. Allora

∃j − i | i′ con i ≤ i′ ≤ j. Quindi

x2i′ = xi′+i′ = xi′+k(j−i) =⇒ xi′ (mod p)

(j − 1 passi e fare un giro).

ESEMPIO:

Zp = {1, 2, 5, 26, 38, 25, 58, 28, 4, 17, 6, 37, 21, 16, 44, 20, 46, 58, 28, 4, 17 · · ·}xi = 58 perche e il primo che si ripete.

i = 7

j = 18

j − i = 11

i′ = 11 e il multiplo di j − i compreso tra i e j.

quindi

x11 = x22

ossia in generale valere

xi′ = xj−1 = xk(j−i) = xki′ = xk

Complessita

Usiamo il paradosso del compleanno per stimare j. j sono i passi che devo fare per

ottenere la prima collisione, e cioe j =√p, quindi

O(√p · gcd) = O(2

k4 · k3)

E pur sempre esponenziale ma l’esponente e dimezzato rispetto a prima.

In generale l’algoritmo ha successo quando p e piccolo, cosa che nell’RSA non e cosı

perche p e q hanno lo stesso numero di bit.

Con questo metodo il numero di confronti su un insieme di h elementi e h2

2 .

114


Variante di Brent

Consiste nel modificare il test come segue:

x2i′ (mod p) = x2i′+s (mod p)

dove 1 ≤ s ≤ 2i′+1 − 2i cioe 2i

′(2− 1) = 2i

′

ESEMPIO:

x1 x2 x3 x4 x5 x6 x7 x8 x9 · · ·x15 x16 x17 · · ·x32 · · ·

Confronti

i′ = 0 (x1, x2)

i′ = 1 (x2, x3) (x2, x4)

i′ = 2 (x4, x5) (x4, x6) (x4, x7) (x4, x8)...

Se confronto tutti con tutti ottengo 10242

2 contronti, mentre cosı solo 1024.

Osservazione 24. Il numero di test su un insieme di h elementi e h.

Osservazione 25. Una collisione si trova esaminando x2i′ (mod p) con x2i′+s nonappena

2i′> i ∧ 2i

′> j − i

Con il test di Brent dividiamo la sequenza in blocchi che raddoppiano ogni volta.

La collisione si verifica quando entro nel giro del ρ (2i′> i) e quando il blocco e piu

lungo del giro (2i′> j − i), di conseguenza 2i

′sono i confronti che faccio.

Complessita

La complessita teorica e la stessa ma sperimentalmente si e visto che funziona

meglio.

115


Algoritmo di Dixon (Crivello quadratico)

Si basa sull’idea di Fermat:

for s := 1 to√n{

if(n+ s2 = t2){n = t2 − s2

n = (t− s)(t+ s)

p = t− sbreak

}}

Se n+ s2 e QUADRATO posso facilmente trovare un fattore.

ESEMPIO:

n = 323

323 + 1 = 324 e un quadrato

324 = 182

323 = 182 − 1

323 = (18− 1)(18 + 1) = 17 · 19

Questa considerazione porta alla conclusione che p e q devono essere distanti tra

loro.

n = t2 − s2 = p · q

{t− s = p

t+ s = q

q − p = t+ s− t+ s

q − p = 2s

s =q − p

2

Per preservare l’RSA bisogna avere s grande e quindi p e q vanno presi distanti.

116


Dixon generalizza l’idea di Fermat. Si cercano relazioni di questo tipo in Zn.

z2 ≡ t2 (mod n)

Osservazione 26. Se trovassi una relazione z2 ≡ t2 (mod n) con z − t 6≡ 0(mod n) e z + t 6≡ 0 (mod n) allora avrei che n | z2 − t2 = (z − t)(z + t) man 6| (z − t) e n 6| (z + t)=⇒gcd(n, z − t)e un divisore proprio di n.

Significa che p · q non divide (z − t)(z + t) ma allora p ne divide uno dei due e q

l’altro.

L’obiettivo e trovare z, t con z2 ≡ t2 (mod n).

Supponiamo di trovare queste relazioni, e siano gli ai b numeri primi.

z21 = ar111 · ar122 · · · a

r1bb (mod n)

z22 = ar211 · ar222 · · · a

r2bb (mod n)

...

z2j = a

rj11 · arj22 · · · a

rjbb (mod n)

...

z2c = arc11 · arc22 · · · a

rcbb (mod n)

Se gli rij sono tutti pari allora abbiamo gia finito, perche significa che z2j e un

quadrato in quanto e un prodotto di quadrati. Se c’e almeno un esponente dispari

cerchiamo di moltiplicarli tra di loro in modo tale da ottenere esponenti pari.

117


ESEMPIO:

n = 15770708441

33409341562 = 3 · 7 (mod n)

120449429442 = 2 · 7 · 13 (mod n)

27737000112 = 2 · 3 · 13 (mod n)

(z1 · z2 · z3)2 = 22 · 32 · 72 · 132 (mod n)

(2 · 3 · 7 · 13)2 (mod n)

dopodiche calcolo

p = gcd(n, z − t)

In generale si moltiplicano alcuni zi tra di loro:

(zε11 · zε22 · · · z

εcc )2 = (z1)ε1 · (z2)ε2 · · · (zc)εc

con εi =

{0

1

(ar111 · ar122 · · · ar1bb )ε1 · (ar211 · ar222 · · · a

r2bb )ε2 · · · (arc11 · arc22 · · · a

rcbb )εc =

aε1·r11+ε2·r21+···+εc·rc11 · aε1·r12+ε2·r22+···+εc·rc2

2 · · · aε1·r1b+ε2·r2b+···+εc·rcbb = t2

Questo e quadrato quandoε1 · r11 + ε2 · r21 + · · ·+ εc · rc1 ≡ 0 (mod 2)

ε1 · r12 + ε2 · r22 + · · ·+ εc · rc2 ≡ 0 (mod 2)...

ε1 · r1b + ε2 · r2b + · · ·+ εc · rcb ≡ 0 (mod 2)

Questo e un sistema lineare omogeneo di b equazioni in c incognite sopra il campo

finito Z2. Poiche un sistema lineare ha soluzioni quando c ≥ b, mi servono piu relazioni

dei numeri primi con cui fattorizzo gli zi.

Chi mi garantisce che n 6| (z − t) e n 6| (z + t)?

Osservazione 27. Il numero di soluzioni di t2 ≡ a (mod n) in Zn sono almassimo 4 e non 2 come detto in precedenza questo perche n non e primo equindi Zn non e un campo.

118


Dimostrazione.

n | t2 − a =⇒{p | t2 − aq | t2 − a =⇒

{t2 ≡ a (mod p)t2 ≡ a (mod q)

Zn non e un campo ma Zp e Zq si, quindi al massimo ci sono 2 possibili valori di aper la prima equazione e 2 per la seconda. In totale, quindi, ci sono 4 possibilita per lacoppia

(t (mod p), t (mod q))

Per ciascuna di questa 4 possibilita, c’e esattamente un possibile valore per t, invirtu del Teorema Cinese dei Resti (Teorema 31)

ESEMPIO:

n = 15

a = 1 =⇒ sol = {1, −1(= 14)}

15 | t2 − 1 =⇒

{3 | t2 − 1

5 | t2 − 1=⇒

{t2 ≡ 1 (mod 3)

t2 ≡ 1 (mod 5)

Le quattro possibilita sono:

1. t (mod 3) = 1 ∧ t (mod 5) = 1→ t = 1

2. t (mod 3) = 2 ∧ t (mod 5) = 1→ t = 11

3. t (mod 3) = 1 ∧ t (mod 5) = 4→ t = 4

4. t (mod 3) = 2 ∧ t (mod 5) = 4→ t = 14

Qual e la probabilita che dati x, y con x2 ≡ y2 (mod n) si abbia n 6| x − y e

n 6| x+ y?

Sia a ≡ x2 ≡ y2 (mod n).

Siano t1, t2, t3, t4 le quattro radici. Tali radici sono a coppie opposte, quindi sup-

pongo che t2 = −t1 e t4 = −t3 quindi posso scrivere le quattro radici come

t1,−t1, t3,−t3

x e y sono tra queste quattro, ma non so quali sono. Costruisco quindi la tabella

con tutte le 16 possibilita per la coppia (x, y):

119


I casi possibili sono 16; quelli favorevoli sono 8 cioe quelli per cui si ha contempo-

raneamente x − y 6= 0 e x + y 6= 0. In conclusione la probabilita di successo e p = 12 .

Chiaramente ad ogni iterata dell’algoritmo di Dixon questa probabilita diminuisce.

Complessita

La complessita e

O(e(1+O(1))·√

lnn·(ln(lnn)))

cioe

O(e(1+O(1))·√k·(ln k))

che e minore dell’algoritmo di prima ma pur sempre esponenziale; per la precisione si

dice sub esponenziale. Una versione leggermente modificata di questa e detta crivello

quadratico ed ha la stessa complessita.

Altri algoritmi

• Lenstra - Curve Ellittiche O(e(1+O(1))·√

2 ln p·(ln p))→ O(e(1+O(1))·

√2 ln k

2·(ln k

2))

• Crivello “Teoria dei numeri” O(e(1,92+O(1))· 3√

lnn· 3√

ln(lnn)2) = O(e(1,92+O(1))· 3√k· 3√

ln k2)

120


Costruzione di un Numero Primo

Osservazione 28. Chiunque e in grado di costruire un numero primo arbi-trariamente grande, senza bisogno di fare nessun test. Sia h il prodotto deiprimi s numeri primi

p1 · p2 · p3 · · · ps = h

allora h+ 1 e primo.

Dimostrazione. Sia p primo che divide h + 1. Siccome p ≤ h, perche e un divisore, esicuramente un certo pi.

pi | h+ 1, pi|h =⇒ pi | h+ 1− h =⇒ pi | 1impossibile.

Il problema e che basta togliere 1 ad h + 1 e ottenere h che e fattorizzabile sem-

plicemente, con l’algoritmo (p− 1)− Pollard.

121

5.4. Crittosistema ElGamal Capitolo 5. Crittografia Asimmetrica

5.4 Crittosistema ElGamal

Sfrutta la difficolta computazionale della risoluzione del cosiddetto DL−Problem,

cioe il problema del Logaritmo Discreto; discreto perche si lavora all’interno di un

campo finito.

Definizione 30 (Crittosistema ElGamal). Il crittosistema e cosı definito:

• Zp con p primo (quindi un campo finito).

• Fissiamo un elemento primitivo α t.c < α > = Z∗p (gruppo ciclicogenerato da α)

• β = αa per def. a = logα β

• Chiave privata: (a)

• Chiave pubblica: (p, α, β)

• ek(x) = (αk mod p; x · βk mod p) = (γ1; γ2)

• dk(y) = γ2γa1

mod p

Con k un elemento del campo scelto a caso dal mittente.

Alice riceve il messaggio (αk mod p; x·βk mod p). Per decifrarlo prima deve ricavare

βk.

βk = γa1

γa1 = (αk)a (mod p) = (αa)k (mod p) = βk (mod p)

Ad Alice non interessa conoscere k. Questa operazione e facile perche Alice conosce

a. L’hacker se vuole decifrare il messaggio per ottenere βk deve ricavare a risolvendo il

Problema del Logaritmo Discreto.

La sicurezza e garantita dal fatto che computazionalmente difficile risolvere tale

problema.

ESEMPIO:

p = 2579

α = 2. E facile computazionalmente stabilire se α e primitivo in quanto occorre

fare pochi test e ogni test richiede un esponenziazione che e polinomiale con Square

and Multiply.

a = 765

β = αa = 2765 (mod 2579) = 949

122


Cifratura:

x = 1299

k = 53

γ1 = 2853 (mod 2579) = 435

γ2 = 1299 · 949853 (mod 2579) = 2396

Decifratura:

x = γ2γa2

(mod p) = 2396435765 (mod 2579)

5.4.1 Algoritmi di risoluzione del DL-Problem

Definizione 31 (DL-Problem in Zp). Dati α ∈ Zp con < α >= Z∗p e β ∈ Z∗ptrovare a t.c.

β = αa

Brute Force

Consiste nell’andare per tentativi

α1, α2, α3, · · · , αp

finche non trovo a β. Nel caso peggiore si devono fare p tentativi, quindi:

O(p) · T (Square Multiply) = O(2k) · T (Square Multiply)

Precompilazione e Ordinamento

Si effettua un fase di precomputazione, cioe si calcolano preventivamente gli αi e si

memorizzano ordinati in senso crescente. Risolvere il problema significa cercare nella

tabella se e gia stato calcolato il valore β che ci interessa, e in caso affermativo restituire

il corrispondente valore dell’esponente.

Questa soluzione e molto costosa sia in termini di spazio di memoria che di tempo.

Baby Step Giant Step (BSGS)

E stato ideato da Shank. E l’algoritmo piu veloce per gruppi generici. Per Zp ce ne

sono di piu efficienti.

L’idea deriva dal fatto che possiamo scrivere a come

a = q · d√pe+ r

123


e dato che a ≤ p − 1 e 0 ≤ r ≤ √p − 1 si ha che 0 ≤ q ≤ √p. Si sceglie√p come

divisore per bilanciare il carico computazionale; cosı facendo infatti si fanno al piu√p

passi sia per il resto che per il quoziente.

Da questo abbiamo

β = αa = αq·d√pe+r =⇒ βα−r = αq·d

√pe

Quindi otteniamo due incognite r e q che variano fra 0 e√p.

Si creano due tabelle dove si calcolano tutti i valori dei due membri. Poi si cerca

quando c’e lo stesso valore in entrambe le tabelle. La complessita e sempre esponenziale

ma e minore dei casi precedenti ed e identica in spazio e in tempo, cioe

O(√p) · T (Square Multiply) = O(2

k2 ) · T (Square Multiply)

ρ di Pollard

Il meccanismo e molto simile all’algoritmo omonimo per la fattorizzazione. L’idea

e cercare una collisione di questo tipo:

αAβB ≡ αAβB (mod p)

Si costruisce una successione casuale di elementi di Zp di questo tipo

αAβB

dopo√p passi, in virtu del Paradosso del Compleanno (Teorema 23) c’e concreta

speranza di collisione.

Ottenuta una collisione possiamo scrivere

αA(αa)B ≡ αA(αa)B (mod p)

αA+aB ≡ αA+aB (mod p)

Dato che ho una collisione vale

αA+aB

αA+aB≡ 1 (mod p)

α(A+aB)−(A+aB) ≡ 1 (mod p)

124


Quindi (A+ aB)− (A+ aB) e multiplo di p− 1 cioe

(A+ aB)− (A+ aB) ≡ 0 (mod p− 1)

A− A+ a(B − B) ≡ 0 (mod p− 1)

Ora se sono fortunato B− B e primo con p− 1 e quindi e invertibile in Z∗p e quindi

a =A− AB − B

(mod p− 1)

Se sono sfortunato ripeto il procedimento dall’inizio cercando altre collisioni. In

realta basta calcolare gcd(p − 1, B − B) e sottrarlo alla formula iniziale e procedere

come visto. Inoltre valgono gli stessi trucchi gia visti (Floyd e Brent).

La complessita e O(√p). L’unico vantaggio che ha rispetto al BSGS e la memoria.

Pohlig-Hellman

Questo algoritmo funziona, quindi e veloce, quando p− 1 e fattorizzabile con primi

piccoli.

Sia

p− 1 = qr11 · qr22 · · · q

rss

Per semplicita supponiamo ri = 1∀i.quindi

p− 1 = q1 · q2 · · · qs

IDEA: Non calcolare direttamente a ma calcolare prima

a (mod qi)∀i

dopodiche applicando il Teorema Cinese dei Resti (31) calcolo a (mod p− 1).

Calcoliamo ora a (mod qi):

a = ti · qi + aiai ≡ a (mod qi)

0 ≤ ai ≤ qi − 1

β = αa =⇒ βp−1qi = (αa)

p−1qi

βp−1qi = α

a· p−1qi

125


βp−1qi = α

(ti·qi+ai) p−1qi

βp−1qi = α

ti(p−1)+ai(p−1)

qi =

αti(p−1) · αai(p−1)

qi

Poiche αp−1 = 1 si ha

βp−1qi = α

ai(p−1)

qi = (αp−1qi )ai

E di nuovo un problema di DL su un insieme di cardinalita qi, cioe piu piccolo.

Risolvere questo nuovo problema con BSGS costa O(√qi), pertanto il costo totale e

O(√q1 +

√q2 + · · ·+√qs)

che e molto minore che risolvere il problema senza l’idea di Pohlig-Hellman cioe

O(√p) = O(

√q1 ·√q2 · · ·

√qs)

Per contro se vogliamo evitare l’attacco Pohlig-Hellman basta prendere p− 1 = 2q

con q primo grande. La complessita diventa O(√

2 +√q) anziche O(

√2 · √q); non c’e

molta differenza tra le due.

ESEMPIO:

p = 31

α = 3

β = 4

Il problema e trovare a t.c. 4 = 3a.

p− 1 = 30

30 = 2 · 3 · 5

Devo trovare

A) a (mod 2)

B) a (mod 3)

126


C) a (mod 5)

Iniziamo dalla C:

βp−1qi = (α

p−1qi )ai = 46 = (36)a3

Quindi

a3 = a (mod q3) = a (mod 5)

1 = (4)a3 → 20 = 22a3 → 1 = 22a3

Questo significa anche che 5 | 2a3; il risultato e

a3 = 5

Index Calcolus

Questo algoritmo ricorda vagamente Dixon, ed e il piu veloce tra quelli conosciuti

ma si applica solo ai campi finiti. Tuttavia questo metodo non ha un analogo su curve

ellittiche, per questo, a parita dei bit di chiave, la crittografia su curve ellittiche e piu

sicura.

IDEA:

PASSO 1: Si cerca il logaritmo discreto di un certo numero di primi

p1 = αa1

p2 = αa2

...

pB = αaB

Ora considero potenze di α in modo pseudo-casuale sperando che si fattorizzino

cosı:

αxj = pc1,j1 · pc2,j2 · · · pcB,j

B

In questo modo trovero delle relazioni che riguardano i logaritmi discreti dei numeri

primi ottenendo per sostituzione

αxj = αa1c1,j · αa2c2,j · · ·αaBcB,j =

αa1c1,j+a2c2,j+···aBcB,j

127


Essendo α primitivo, due potenze sono uguali ⇐⇒ xj − a1c1,j + a2c2,j + · · · aBcB,je multiplo di p− 1 cioe

xj ≡ a1c1,j + a2c2,j + · · · aBcB,j (mod p− 1)

Il punto e che se trovo almeno B relazioni posso creare un sistema lineare e ricavare

a1, a2, · · · , aB.

PASSO 2:

Si cerca una relazione di questo tipo

βαs = pd11 · pd22 · · · p

dBB

se ci riusciamo il problema e risolto perche sostituendo β = αa e i risultati ottenuti

prima otteniamo

αa+s = αa1d1 · αa2d2 · · ·αaBdB

e quindi

a+ s ≡ a1d1 + a2d2 + · · ·+ aBdB (mod p− 1)

gli ai li conosco perche li ho trovati prima quindi basta portare s all’altro membro

e ho risolto il problema.

COMPLESSITA

PASSO 1: O(e(1+O(1))·√

ln p·ln ln p)

PASSO 2: O(e( 12

+O(1))·√

ln p·ln ln p)

Complessita sub-esponenziale, perche compare la radice.

Funziona solo per i campi finiti, non solo quelli del tipo Z∗p ma anche per gli Fq. Tra

questi quelli importanti per l’informatica sono gli F2r , cioe quelli per cui la cardinalita

e una potenza di 2.

La sicurezza al momento sembra garantita per r ≥ 1024 e quindi per campi di

cardinalita 21024.

128

Capitolo 6

Firma Digitale

L differenza tra firma digitale e MAC e che la firma puo essere verificata da chiunque

mentre il MAC solo dal legittimo destinatario.

Definizione 32 (Schema di Firma Digitale). Uno schema di firma digitale euna 5-upla del tipo (P,A,K,S,V) dove

• P: Insieme dei possibili plaintext

• A: Insieme delle possibili firme

• K: Insieme delle possibili chiavi

• S: Insieme delle funzioni di firma

• V: Insieme delle funzioni di verifica

con

S = {sigK : P → A} dove k ∈ KV = {verK : PxA → {true, false}} dove k ∈ K e verK(x, y) = true =⇒ y =sigK(x).

Le proprieta che deve soddisfare lo schema per essere accettabile sono:

• Le funzioni di firma e di verifica sono veloci da eseguire

• difficile falsificare una firma

I tipi di attacco sono essenzialmente tre:

1. Key Only: L’hacker conosce solo le funzioni sig e ver, quindi conosce lo schema

(questo e sempre vero).

2. Known Message: L’hacker conosce alcuni x ∈ P e le corrispondenti firme (situ-

azione plausibile).

3. Chosen Message: L’hacker sceglie alcuni x ∈ P ed e in grado da farli firmare

129

6.1. Schema SHA1WithRSA Capitolo 6. Firma Digitale

Dobbiamo distinguere due tipi di successo:

• Existential Forgery: L’hacker e in grado di produrre almeno un messaggio firmato

ma che non e scelto da lui.

• Total Break: E in grado di firmare qualsiasi messaggio

6.1 Schema SHA1WithRSA

IDEA: Cifro il documento con la chiave privata. Chi vuole verificare decifra la firma

con la chiave pubblica e controlla che i due documenti coincidano.

Chiave privata: (p, q, d)

Chiave pubblica: (n, e)

Schema:

P = Zn

A = Zn

K = {(p, q, d, e, n)} | ed ≡ 1 (mod φ(n)))

sigK(x) = xd (mod n)

verK(x, y) = true⇐⇒ ye ≡ x (mod n)

Problema 5. Ci sono delle debolezze rispetto all’existential forgery.

Infatti

1. Attacco Key Only: L’hacker puo scegliere z ∈ Zn e porre

x = ze

y = z

Questa coppia e accettata perche

verK(x, y) = true =⇒ ye ≡ x (mod n)

La speranza di Alice e che z non abbia senso, e al 99,9% e cosı.

2. Attacco Known Message: L’hacker conoscendo due documenti firmati da Alice

(x1, y1) e (x2, y2), e in grado di creare un terzo messaggio valido cosı

x = x1 · x2 (mod n)

130

6.2. Schema Elgamal Capitolo 6. Firma Digitale

y = y1 · y2 (mod n)

infatti

ye ≡ x (mod n)

(y1y2)e ≡ x1x2 (mod n)

ye1ye2 ≡ x1x2 (mod n)

ye1 = x1 e ye2 = x2

La soluzione al problema e utilizzare una funzione hash e firmare l’estratto anziche

tutto il documento. Questo oltre a risolvere il problema enunciato serve anche a

velocizzare le operazioni di firma e di verifica.

I due attacchi visti prima non funzionano piu se h e buona.

1. Attacco Key Only: L’hacker avrebbe bisogno di porre h(x) = ze; poi dovrebbe

ricavare x da h(x) il che e impossibile se h e resistente al problema “controim-

magine”.

2. Attacco Known Message: Dovrebbe valere h(x1x2) = h(x1) · h(x2) ma e impos-

sibile vista l’irregolarita della funzione hash.

Osservazione 29. La funzione hash deve essere resistente al problema “sec-onda controimmagine”, altrimenti se (x, y) e firmata da Alice e Oscar trova xtale che h(x) = h(x) avra trovato anche una firma valida per x.

Osservazione 30. La funzione hash deve essere anche resistente alle colli-sioni, perche se trovo due messaggi con stesso hash, supponendo che uno deidue sia innocuo mentre l’altro no, posso indurre Alice a firmare quello innocuoe ottenere una firma valida per quello sensibile.

6.2 Schema Elgamal

Sfrutta il DL-Problem per effettuare la firma.

Chiave privata: (a, k)

Chiave pubblica: (p, α, β)

Schema:

131


P = Zp

A = ZpxZp

K = {(a, k, p, α, β)}

sigK(x) = (γ, δ) =

{γ = αk (mod p)

δ = x−aγk (mod p− 1)

verK(x, (γ, δ)) = true⇐⇒ βγ · γδ = αx

Dimostrazione. βγ · γδ = (αa)γ · (αk)δ = αx ⇐⇒ αaγ+kδ = αx

Essendo α un elemento primitivo di un campo, si ha che due potenze sono ugualise la differenza degli esponenti e multiplo di p− 1, cioe

αaγ+kδ−x = 1⇐⇒ p− 1 | aγ + kδ − x

oppure

aγ + kδ − x ≡ 0 (mod p− 1)

Da questa uguaglianza ricaviamo δ cosı

δ ≡ x− aγk

(mod p− 1)

Vediamo quanto e resistente agli attacchi total break e existential forgery.

• Total Break: L’hacker conosce x, α, β. Deve cercare γ e δ t.c. valga

βγ · γδ = αx

Ho due possibilita:

– Fisso γ e cerco δ; quindi ottengo un DL-Problem.

γδ = αx · β−γ

Quindi se si prende p sufficientemente grande t.c. il DL-Problem e intratta-

bile in quel campo allora sono sicuro che e resistente all’attacco.

– Fisso δ e cerco γ; quindi ottengo un problema considerato piu difficile del

DL-Problem in quanto la mia incognita γ compare due volte.

βγ · γδ = αx

Non esiste un algoritmo efficiente che risolva tale problema.

132


• Existential Forgery: Anche in questo caso se non si usa una funzione hash e

possibile trovare una falsificazione esistenziale. Si pone γ = αi · βj e si cercano i

e j in modo tale da verificare l’uguaglianza βγ · γδ = αx.

Sostituisco solo una volta γ e ottengo

βγ · (αi · βj)δ = αx

αiδ−x = β−γ−jδ

Poiche β = αa non posso continuare a sviluppare l’equazione perche non ho modo

di conoscere a, allora faccio in questo modo:

iδ − x = −γ − jδ ≡ 0 (mod p− 1)

Se vale questo allora sicuramente vale

αiδ−x = β−γ−jδ

perche entrambi i membri sarebbero 1.

Questo si risolve con un sistema

iδ − x ≡ 0 (mod p− 1)

−jδ =≡ γ (mod p− 1)

Le incognite sono x e δ. Il sistema ha soluzioni quando il determinante della

matrice dei coefficienti e invertibile modulo p− 1. Quindi si ha

det

(i − 1

−j 0

)= −j

e dunque basta prendere un i qualunque e j invertibile in Z∗p cosı sono sicuro di

poter risolvere il sistema. Infatti

δ =γ

−j=αiβj

−j

x = iδ =i

−jαiβj

133


Osservazione 31. k deve essere segreto, perche chi verifica conosce x e (γ, δ)se conoscesse anche k puo ricavare a cosı

kδ ≡ x− aγ (mod p− 1)

kδ − x ≡ −aγ (mod p− 1)

aγ ≡ x− kδ (mod p− 1)

a ≡ x− kδγ

(mod p− 1)

Osservazione 32. k deve essere cambiato ogni volta, perche se supponiamo che x1

e x2 venissero firmati con lo stesso k le firme sarebbero

(γ, δ1) e (γ, δ2)

δ cambia perche dipende dal messaggio x, ma γ no quindi

{βγ · γδ1 = αx1

βγ · γδ2 = αx2=

{βγ · αkδ1 = αx1

βγ · αkδ2 = αx2=⇒ βγ · αkδ1

βγ · αkδ2=αx1

αx2=⇒ αk(δ1−δ2) = αx1−x2

Poiche due potenze di α sono uguali quando gli esponenti sono uguali modulo p− 1si ha

k(δ1 − δ2) ≡ xi − x2 (mod p− 1)

A questo punto se (δ1 − δ2) e invertibile, ed e probabile che lo sia, trovo k facendo

k ≡ x1 − x2

δ1 − δ2(mod p− 1)

Dunque se Alice non cambia k l’hacker puo firmare al posto suo.

ESEMPIO:

p = 467

α = 2

a = 127

β = 2127 = 132

Supponiamo x = 100

Scelgo k invertibile modulo p− 1

k = 213 infatti gcd(466, 213) = 1

Ci calcoliamo preventivamente 1k = 431

134

6.3. Schema SHA1WithDSA Capitolo 6. Firma Digitale

FIRMA {γ = 2213 (mod 467) = 29

δ = 431 · (100− 127 · 29) (mod 467) = 51

VERIFICA

13229 · 2951 = 127100

6.3 Schema SHA1WithDSA

E molto simile allo schema Elgamal; ha qualche piccola modifica.

Generazione delle chiavi:

• Si scelga un numero primo q di 160 bit

• Si scelga un numero primo p lungo L bit, tale che p = qz + 1 per un qualche

numero intero z, con 512 < L < 1024 e 64 | L (nell’ultima revisione dello standard

si specifica che L deve corrispondere a 1024).

• Si scelga h tale che 1 < h < p− 1 e α = hz (mod p) > 1

• Si generi un numero casuale a tale che 1 < a < q

• Calcolare β = αa (mod p)

La chiave pubblica e (p, q, α, β) e la chiave privata e a.

Calcolo della firma:

• Si generi un numero casuale k tale che 0 < k < q

• Calcolare γ = (αk (mod p)) (mod q)

• Calcolare δ = H(m)+aγk (mod q)

• Nel caso in cui γ = 0 o δ = 0 bisogna ricalcolare la firma cambiando k

• La firma e (γ, δ)

135

6.4. Funzionamento Pratico Capitolo 6. Firma Digitale

Verifica della firma:

• Rifiutare firme se non sono soddisfatte le condizioni 0 < γ < q e 0 < δ < q

• Calcolare w = δ−1 (mod q)

• Calcolare u1 = H(m) · w (mod q)

• Calcolare u2 = γ · w (mod q)

• Calcolare v = (αu1 · βu2 (mod p)) (mod q)

• La firma e verificata se v = γ

6.4 Funzionamento Pratico

Creazione della coppia di chiavi:

• L’utente richiede un certificato digitale ad una CA autorizzata.

• La CA emette un certificato

• Nel certificato c’e la chiave pubblica di Alice ed e firmato dalla CA

• Il certificato viene inserito in una smart card insieme alla chiave privata di Alice

Generazione della firma:

Occorre utilizzare un software specifico. Il software prende in input il documento

da firmare e la chiave privata contenuta all’interno della smart card, e restituisce in

output un file .p7m.

Un file con estensione .p7m e composto di tre parti

1. File.doc

2. Firma

3. Certificato di Alice

Verifica della firma:

1. Il software verifica on-line la validita del certificato e la firma della CA

2. Verifica la firma di Alice prendendo la chiave pubblica dal certificato

136

Capitolo 7

Elliptic Curve Cryptography(ECC)

E un tipologia di crittografia a chiave pubblica basata su curve ellittiche definite in

campi finiti. L’utilizzo di questo metodo crittografico e stato proposto da Neal Koblitz

e Victor S. Miller nel 1985.

7.1 Curve Ellittiche nei Reali

Una curva ellittica su numeri reali puo essere definita come l’insieme di punti (x, y)

che soddisfano una equazione della forma:

y2 = x3 + ax2 + b

dove x,y, a e b sono numeri reali. Ogni diversa scelta di a e b da origine ad una curva

ellittica diversa. Ad esempio, a = −4 e b = 0, 67 fornisce la seguente curva ellittica:

137

7.1. Curve Ellittiche nei Reali Capitolo 7. Elliptic Curve Cryptography (ECC)

Se x3 +ax+ b non contiene elementi ripetuti, o equivalentemente se 4a3 + 27b2 6= 0,

allora la curva ellittica y2 = x3 + ax + b puo essere utilizzato per formare un gruppo.

Un gruppo di curva ellittica su numeri reali e costituito da i punti sulla curva ellittica

corrispondente, insieme ad un punto O, speciale, chiamato punto all’infinito.

Sul gruppo vogliamo inoltre, che ci si possa definire un’operazione, cioe una regola

per associare a due elementi un terzo elemento, che soddisfi 4 proprieta: Associativa,

Commutativa, Esistenza dell’elemento neutro ed Esistenza dell’inverso.

Gruppi di curve ellittiche sono gruppi di additivi, cioe la loro funzione di base e la

somma. L’aggiunta di due punti in una curva ellittica e definito geometricamente.

L’opposto (o il negativo) di un punto P = (Xp, Yp) e il suo riflesso in asse x: il

punto −P e (xP ,−yP ). Si noti che per ogni punto P su una curva ellittica, il punto

−P e anch’esso sulla curva.

Somma di due numeri: P +Q = R

Supponiamo che P e Q siano due punti distinti su una curva ellittica, e P 6= −Q.

Per sommare i due numeri si disegna la retta che passa per questi due punti.

Questa linea interseca la curva ellittica esattamente in un punto chiamato −R. Il

punto −R si riflette nell’asse delle x fino al punto R. Il procedimento e mostrato

in Figura 7.1.

Figura 7.1: Somma di due punti

Aritmeticamente metto a sistema l’equazione della curva con l’equazione della

retta; ottengo 3 soluzioni che sono i tre punti. Ecco il motivo del grado 3: ho

138


bisogno di un terzo punto e quindi ho bisogno del 3 grado.

Somma dello stesso numero: P + P = 2P = R

La linea passante per P e −P e una linea verticale che non si interseca con la

curva ellittica in un terzo punto, e quindi la somma non puo essere fatta come in

precedenza. Per questo motivo il gruppo generato dalla curva ellittica contiene un

punto all’infinito chiamato O. Per definizione si ha che, P + (−P ) = O, e quindi

anche P +O = P ; dunque O viene preso come l’elemento neutro del gruppo.

Per aggiungere un punto P a se stesso, si calcola la tangente alla curva passante

per P . Se yP 6= 0, la tangente interseca la curva in un altro punto −R. Infine si

riflette −R ottenendo R.

139


Se yP = 0 la tangente e sempre verticale e non interseca la curva in un altro punto.

Per definizione, 2p = O per un tale punto P . Se si volesse trovare 3P in questa

situazione, si puo aggiungere 3P = 2P + P . Questo diventa 3P = P + O = P .

Pertanto P = 3P, 4P = O, P = 5P, 6P = O, P = 7P , ecc...

Formule Algebriche

Anche se le descrizioni geometriche precedenti delle curve ellittiche forniscono un

metodo eccellente per illustrare l’aritmetica che ci sta dietro, non sono un modo pratico

per implementare calcoli aritmetici. C’e bisogno di formule che possono essere eseguite

da un calcolatore.


Quando P = (xP , yP ) e Q = (xQ, yQ) non sono uno l’opposto dell’altro la somma

si calcola cosı:

s =yP − yQxP − xQ

xR = s2 − xP − xQ

yR = −yP + s(xP − xR)

con s che rappresenta la retta passante per i punti P e Q.


Quando yP 6= 0 la somma si calcola cosı:

140

7.2. Curve Ellittiche in Fp Capitolo 7. Elliptic Curve Cryptography (ECC)

s =3x2

P + a

2yP

xR = s2 − 2xP

yR = −yP + s(xP − xR)

con s che rappresenta la retta tangente la curva ellittica nel punto P .

7.2 Curve Ellittiche in Fp

Una proprieta essenziale per la crittografia e che un gruppo deve avere un numero

finito di punti. I calcoli sui numeri reali sono lenti e imprecisi a causa di un errore di

arrotondamento. Le applicazioni crittografiche richiedono calcoli veloci e precisi, per

questo vengono utilizzati campi finiti, Fp e F2m , generati da curve ellittiche.

Una curva ellittica basata su campo Fp puo essere formata scegliendo le variabili

a e b all’interno del campo Fp. La curva ellittica comprende tutti i punti (x, y) che

soddisfano l’equazione:

y2 (mod p) = x3 + ax2 + b (mod p)

Se la curva ellittica contiene tutti elementi singolari (4a3 + 27b2 (mod p) 6= 0)

allora la curva ellittica puo essere usata per creare un gruppo.

Come esempio si consideri il campo F23, a = 1 e b = 0. L’equazione risultante

y2 = x3 + x

Il punto P = (9, 5) soddisfa l’equazione in quanto

y2 (mod p) = x3 + x (mod p)

25 (mod 23) = 729 + 9 (mod 23)

25 (mod 23) = 738 (mod 23)

2 = 2

In tutto sono casualmente 23, i punti che soddisfano l’equazione.

(0, 0)(1, 5)(1, 18)(9, 5)(9, 18)(11, 10)(11, 13)(13, 5)(13, 18)(15, 3)(15, 20)(16, 8)

141

7.2. Curve Ellittiche in Fp Capitolo 7. Elliptic Curve Cryptography (ECC)

(16, 15)(17, 10)(17, 13)(18, 10)(18, 13)(19, 1)(19, 22)(20, 4)(20, 19)(21, 6)(21, 17)

Questi punti possono essere rappresentati cosı:

Da notare che ci sono 2 valori di y per ogni x, proprio come succede nei numeri

reali. Chiaramente non ha piu senso cercare di collegare i punti per ottenere una curva.

Quello che ci interessa e che le regole che valgono per i numeri reali valgono anche

per i campi finiti Fq con l’eccezione che il calcolo e fatto modulo p.


Quando P = (xP , yP ) e Q = (xQ, yQ) non sono uno l’opposto dell’altro la somma

si calcola cosı:

s =yP − yQxP − xQ

(mod p)

xR = s2 − xP − xQ (mod p)

yR = −yP + s(xP − xR) (mod p)

con s che rappresenta la retta passante per i punti P e Q.

142

7.3. Curve Ellittiche in F2m Capitolo 7. Elliptic Curve Cryptography (ECC)


Quando yP 6= 0 la somma si calcola cosı:

s =3x2

P + a

2yP(mod p)

xR = s2 − 2xP (mod p)

yR = −yP + s(xP − xR) (mod p)

con s che rappresenta la retta tangente la curva ellittica nel punto P .

7.3 Curve Ellittiche in F2m

Gia sappiamo che gli elementi del campo F2m possono essere rappresentati da

stringhe di m bit. Dal momento che F2m opera su stringhe di bit, i computer possono

eseguire operazioni aritmetiche in questo campo in modo molto efficiente.

Una curva ellittica basata su campo F2m puo essere formata scegliendo le variabili a

e b all’interno del campo F2m . C’e una differenza rispetto a prima; poiche gli elementi

in F2m sono tutti dei quadrati, affinche il meccanismo continui a funzionare, l’equazione

va modificata cosı:

y2 + xy = x3 + ax2 + b

Un gruppo basato su curva ellittica in F2m consiste nei punti che soddisfano

y2 + xy (mod p) = x3 + ax2 + b (mod p)

insieme ad un punto all’infinito, O.

Come esempio si consideri il campo F24 definito mediante il polinomio irriducibile

f(x) = x4 + x+ 1. L’elemento g = (0010) e un generatore per il campo. Le potenze di

g sono:

g0 = (0001) − g1 = (0010) − g2 = (0100) − g3 = (1000)

g4 = (0011) − g5 = (0110) − g6 = (1100) − g7 = (1011)

g8 = (0101) − g9 = (1010) − g10 = (0111) − g11 = (1110)

g12 = (1111) − g13 = (1101) − g14 = (1001) − g15 = (0001)

143

7.3. Curve Ellittiche in F2m Capitolo 7. Elliptic Curve Cryptography (ECC)

In una vera applicazione di crittografia, il parametro m deve essere abbastan-

za grande da evitare la formazione efficiente di questa tabella altrimenti il sistema

crittografico puo essere rotto. In pratica oggi, m = 160 e una scelta opportuna.

Si consideri la curva ellittica

y2 + xy = x3 + g4x2 + 1

Il punto P = (g5, g3) soddisfa l’equazione su F2m perche

(g3)2 + g5g3 = (g5)3 + g4g10 + 1

g6 + g8 = g15 + g14 + 1

(1100) + (0101) = (0001) + (1001) + (0001)

(1001) = (1001)

I 15 punti che soddisfano tale equazione sono:

(1, g13)(g3, g13)(g5, g11)(g6, g14)(g9, g13)(g10, g8)(g12, g12)(1, g6)(g3, g8)(g5, g3)(g6, g8)

(g9, g10)(g10, g)(g12, 0)(0, 1)

Essi possono essere rappresentati cosı:


Sia P = (xP , yP ); l’opposto di P e −P = (xP , xP + yP ). Se P e Q sono punti

distinti tali che P 6= −Q, allora la somma e:

s =(yP − yQ)

(xP + xQ)

xR = s2 + s+ xP + xQ + a

yR = s(xP + xR) + xR + yP

con s la retta che passa per i due punti.


144

7.4. Applicazione in Crittografia Capitolo 7. Elliptic Curve Cryptography (ECC)

Se xP = 0, allora 2P = O quindi questo va evitato. Fatto questo la somma si

calcola cosı:

s = xP +yPxP

xR = s2 + s+ a

yR = x2P + (s+ 1) · xR

con s la retta tangente la curva nel punto P .

7.4 Applicazione in Crittografia

In crittografia si usano le curve ellittiche applicate al meccanismo di key agreement

di Diffie-Helmann o al crittosistema di El Gamal o allo schema di firma DSA. Quindi

si estende il DL-Problem ai gruppi originati da curve ellittiche.

Problema 6 (DL-Problem→ECDL-Problem). Dati β e α trovare a t.c. β =αa =⇒ Dati W e G trovare n t.c. W = nG.

145


Sotto opportune restrizione questo problema e risolubile in tempo esponenziale

O(√r) dove r e l’ordine di W , mentre il DL-Problem e la fattorizzazione sono risolu-

bili in tempo sub-esponenziale. Per questo motivo con ECC si possono usare chiavi di

dimensione minore.

Proprieta dei Gruppi

• Sia #E(Fq) il numero di punti della curva ellittica E(Fq) incluso O.

• Teorema 35 (Hasse bound). #E(Fq) = q + 1− t con t ≤ 2√q

• Il gruppo e ciclico o e il prodotto di due gruppi ciclici.

• L’operazione di moltiplicazione che serve a calcolare W viene fatta mediante

ripetute addizioni. C’e un notevole impiego di risorse nella ricerca di un metodo

piu efficiente per fare la moltiplicazione scalare.

• ∀P ∈ E(Fq) nP = O dove n = #E(Fq).

Restrizioni della Curva

• N = #E(Fq) = hn con n un numero primo molto grande e h il cofattore (h = Nn ).

Per evitare un attacco con l’algoritmo ρ di Pollard o di Pohlig-Helloman, modifi-

cati per le curve ellittiche, e necessario che N sia divisibile per un numero primo

n sufficientemente grande.

• gcd(k, n) = 1

• Condizione Anomala: n 6= q

• Condizione MOV : n 6| qi − 1con 1 ≥ i ≥ 20. Visto che e sempre possibile trasfor-

mare il campo finito generato dalla curva ellittica in un campo finito normale,

se la condizione non e verificata il campo d’arrivo sara di dimensioni parago-

nabili all’iniziale; questo mi permette risolvere il problema sul campo d’arrivo

perche il problema e piu facile. Se invece la condizione e verificata il campo di

arrivo avra dimensioni molto maggiori e quindi la risoluzione del DL-Problem e

improponibile.

Selezione della Curva

Per stabilire se la curva e buona o no mi serve solo conoscere il numero di punti che

ha. Questa non e un’operazione banale perche chiaramente si considerano campi con

cardinalita elevata.

146


I metodi sono:

• Random

• Complex multiplication

• Subfield

La bonta di un metodo dipende da due fattori: la velocita di esecuzione, e dalla

“struttura” delle curve risultanti. Meno significativa e la struttura migliore e la curva.

Purtroppo metodi lenti offrono curve molto buone e viceversa.

Random

Genera una curva a caso e poi conta il numero di punti. Questo metodo e lento ma

offre curve molto buone. Fu proposto da Schoof nel 1985.

Subfield

Esiste un teorema che dice che se si conosce il numero di punti di una curva sopra un

sotto-campo, risolvendo semplicemente una formula di secondo grado posso conoscere

il numero di punti della stessa curva su un campo qualsiasi. Questo metodo non si usa

perche si ha paura che la curva risulti avere una struttura significativa. Questo metodo

fu proposto da Koblitz.

7.4.1 Generazione Chiavi

• Selezionare un numero primo q

• Selezionare una curva ellittica E sul campo Fq che rispetti le restrizioni

• Selezionare un punto H ∈ E(Fq)

• Calcolo G = (Nn )H (con N = #E(Fq), n primo, n > 2160 e n > 4√q)

• Se G = O ricomincio

• Genero random a ∈ [1, n− 1]. chiave privata: (a)

• Calcolo W = aG. chiave pubblica: (W, n, G)

7.4.2 ECDSA

Firma

INPUT: Chiave privata a e messaggio m.

OUTPUT: firma (γ, δ)

147

7.5. Vantaggi e Svantaggi Capitolo 7. Elliptic Curve Cryptography (ECC)

• Seleziono k ∈ [1, n− 1]

• Calcolo γ = x1 (mod n) dove (x1, y1) = kG

• Calcolo δ = h(m)+aγk (mod n)

• Se γ = 0 o δ = 0 ricomincio

Verifica

INPUT: (γ, δ), chiave pubblica (W, n, G) e messaggio m.

OUTPUT: true/false

• Verificare che W 6= O

• Verificare che W appartenga alla curva (W ∈ E(Fq))

• Verificare che nG = O

• Verificare che γ, δ ∈ [1, n− 1]

Alla prima verifica fallita rifiuto la firma.

• Calcolare w = δ−1 (mod n)

• Calcolare u1 = h(m) · w (mod n)

• Calcolare u2 = γ · w (mod n)

• X = (x1, y1) = u1G+ u2W

Se X = O rifiuto la firma

• v = x1 (mod n)

Se v = γ accetto la firma.

7.5 Vantaggi e Svantaggi

7.5.1 Vantaggi

• Un’altra problema difficile

• Operazioni sono piu veloci

• Lunghezza della chiave minore

148

7.5. Vantaggi e Svantaggi Capitolo 7. Elliptic Curve Cryptography (ECC)

• Piu schemi possono essere combinati in modo efficiente. (firma + encryption -

firma/key agreement + certification).

• Molte opzioni: sono molta i parametri in gioco quindi ci possono essere numerosi

crittosistemi

7.5.2 Svantaggi

• Visto che l’ECDLP e stato studiato poco potrebbe rivelarsi un sistema fragile

• Generazione della curva e complessa

• Molte opzioni

149

UNIVERSITA DEGLI STUDI DI PERUGIA1x 2:::::x n per ogni intero n 1, dove ogni simbolo in chiaro x i2P...

Documents

Transcript of UNIVERSITA DEGLI STUDI DI PERUGIA1x 2:::::x n per ogni intero n 1, dove ogni simbolo in chiaro x i2P...