EsercizidiCrittografiae...
74
Esercizi di Crittografia e Sicurezza delle Comunicazioni Giacomo Verticale [email protected] http://home.dei.polimi.it/vertical/ Anno Accademico –
Transcript of EsercizidiCrittografiae...
Esercizi di Crittografia eSicurezza delle Comunicazioni
Giacomo [email protected]
http://home.dei.polimi.it/vertical/
Anno Accademico 2009–2010
Indice
Indice 3
1 Aritmetica modulare 51.1 GCD e algoritmo di Euclide . . . . . . . . . . . . . . . . . 51.2 Cifratura con matrici . . . . . . . . . . . . . . . . . . . . . 71.3 Test di primalità . . . . . . . . . . . . . . . . . . . . . . . 131.4 Campi finiti . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Cifrari a blocco e crittoanalisi 232.1 Modi d’uso . . . . . . . . . . . . . . . . . . . . . . . . . . 232.2 AES semplificato . . . . . . . . . . . . . . . . . . . . . . . 282.3 Crittoanalisi lineare . . . . . . . . . . . . . . . . . . . . . . 312.4 Crittoanalisi differenziale . . . . . . . . . . . . . . . . . . . 36
3 RSA 413.1 Uso di RSA . . . . . . . . . . . . . . . . . . . . . . . . . . 413.2 Fattorizzazione . . . . . . . . . . . . . . . . . . . . . . . . 44
4 Residui quadratici 474.1 Teorema cinese del resto . . . . . . . . . . . . . . . . . . . 474.2 Residui quadratici . . . . . . . . . . . . . . . . . . . . . . . 484.3 Estrazione di radici . . . . . . . . . . . . . . . . . . . . . . 534.4 Crittosistema di Rabin . . . . . . . . . . . . . . . . . . . . 55
5 Logaritmi discreti 595.1 Logaritmi discreti . . . . . . . . . . . . . . . . . . . . . . . 595.2 Applicazioni dei logaritmi discreti . . . . . . . . . . . . . . 63
6 Curve Ellittiche 676.1 Fattorizzazione . . . . . . . . . . . . . . . . . . . . . . . . 676.2 Rappresentazione di plaintext . . . . . . . . . . . . . . . . 686.3 Logaritmo discreto . . . . . . . . . . . . . . . . . . . . . . 696.4 Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . . . . 69
3
Indice
6.5 Firma DSA . . . . . . . . . . . . . . . . . . . . . . . . . . 706.6 Firma di ElGamal . . . . . . . . . . . . . . . . . . . . . . . 726.7 Crittosistema di ElGamal . . . . . . . . . . . . . . . . . . 74
4
1Aritmetica modulare
1.1 GCD e algoritmo di EuclideEsercizio 1.1 Calcolare d = gcd(360, 294) in due modi:
1. fattorizzando ciascuno dei numeri e poi fattorizzando d;2. usando l’algoritmo di Euclide.
Soluzione Osserviamo che
360 = 62 × 10 = 5× 32 × 23
294 = 2× 3× 72
Il gcd è il prodotto dei fattori comuni, ciascuno preso con l’esponenteminore. Quindi
d = 3× 2 = 6
Definiamo:
r0 = max(a,b)r1 = min(a,b)
Il nostro scopo è scrivere una sequenza di espressioni del tipo:
r0 = q1r1 + r2
· · ·rj−2 = qj−1rj−1 + rj
· · ·
5
1. Aritmetica modulare
Dove j è l’indice della espressione, rj e qj sono numeri interi. L’algoritmoè inizializzato con:
r0 ← a
r1 ← b
j ← 0
L’algoritmo termina quando rj = 0 e si ha d = gcd(a,b) = rj−1.
j rj0 360 −−1 294 −−2 66 360 = 1 · 294 + 663 30 294 = 4 · 66 + 304 6 66 = 2 · 30 + 65 0 30 = 5 · 6 + 0
Quindi d = gcd(360,294) = 6.
Esercizio 1.2 Trovare d = gcd(841,294) ed esprimere d come combinazio-ne lineare dei due numeri.
Soluzione L’algoritmo di Euclide esteso permette di trovare i coefficientis e t tali per cui:
gcd(a,b) = r0s+ r1t
conr0 = max(a,b)r1 = min(a,b)
Si definiscono le seguenti ricorrenze:
sj =
1 se j = 00 se j = 1sj−2 − qj−1sj−1 se j ≥ 2
e
tj =
0 se j = 01 se j = 1tj−2 − qj−1tj−1 se j ≥ 2
Per come sono definiti sj e tj, vale sempre la seguente relazione:
rj = r0sj + r1tj
6
1.2. Cifratura con matrici
Quindi i valori s, t che permettono di esprimere il gcd come combinazio-ne lineare dei due numeri sono i coefficienti sj, tj ottenuti in corrispondenzadi rj = gcd(a,b), ovvero dell’ultimo resto non nullo.
La tabella mostra tutti i passaggi dell’algoritmo mettendo in evidenzarj, qj e il calcolo dell’espressione rj = r0sj + r1tj.
j rj qj sj tj r0sj + r1tj0 841 – – 1 0 8411 294 2 – 0 1 2942 253 1 841 = 2 · 294 + 253 1 −2 2533 41 6 294 = 1 · 253 + 41 −1 3 414 7 5 253 = 6 · 41 + 7 7 −20 75 6 1 41 = 5 · 7 + 6 −36 103 66 1 6 7 = 1 · 6 + 1 43 −123 17 0 – 6 = 6 · 1 + 0 −294 841 0
Poiché l’ultimo resto non nullo si ottiene per j = 6, i due numeri sonoprimi tra loro e i coefficienti cercati sono s = 43 e t = −123.
Normalmente non scriveremo tutte le colonne della tabella (che conten-gono molte ripetizioni), ma semplicemente le espressioni rj−2 = qj−1rj−1 +rj e le colonne sj e tj.
sj tj– 1 0– 0 1
841 = 2 · 294 + 253 1 −2294 = 1 · 253 + 41 −1 3253 = 6 · 41 + 7 7 −2041 = 5 · 7 + 6 −36 1037 = 1 · 6 + 1 43 −1236 = 6 · 1 + 0 −294 841
1.2 Cifratura con matriciEsercizio 1.3 (Cifrario di Hill su Z4) Il messaggio binario in chiaro P =011000110100 viene cifrato usando un cifrario di Hill su Z4. Il cifrariousa come chiave una matrice K con dimensione 2× 2.
1. Dire che condizioni deve rispettare la chiave K.2. Cifrare il messaggio P considerando il caso
K =(
0 13 3
)
7
1. Aritmetica modulare
3. Decifrare il messaggio ottenuto al passo precedente4. Usando la coppia messaggio in chiaro / messaggio cifrato ottenuta
ai punti precedenti, effettuare un attacco di tipo known plaintext ericavare la chiave K.
Soluzione 1. La chiave K deve rispettare le seguenti due condizioni:{det(K) 6= 0gcd(det(K),4) = 1
Notare che, per convenzione, la 2 implica la 1.2. Per prima cosa convertiamo il messaggio binario in elementi di Z4.
Poiché gli elementi sono {0, 1, 2, 3} la cosa più semplice è convertireogni coppia di bit in un numero. Pertanto il messaggio diventa:
P =(1 2 0 3 1 0
)La chiave è una matrice 2× 2, quindi il testo in chiaro deve esserediviso in vettori Pi di due elementi:
P1 =(1 2
)P2 =
(0 3
)P3 =
(1 0
)Procediamo quindi applicando la formula:
Ci = Pi ·K (mod 4)
C1 =(1 2
)(0 13 3
)=(6 7
)=(2 3
)(mod 4)
C2 =(0 3
)(0 13 3
)=(9 9
)=(1 1
)(mod 4)
C3 =(1 0
)(0 13 3
)=(0 1
)(mod 4)
Quindi il testo cifrato C risulta:
C =(2 3 1 1 0 1
)che, espresso in binario, diventa C = 101101010001.
8
1.2. Cifratura con matrici
3. Occorre per prima cosa calcolare la matrice inversa della chiave:
K−1 = 1−3
(3 −1−3 0
)(mod 4)
Occorre trovare l’elemento inverso di −3 in Z4. Ma −3 ≡ 1 (mod 4),e l’inverso di 1 è ancora 1, quindi:
K−1 =(
3 31 0
)(mod 4)
Calcoliamo il testo in chiaro:
P1 =(2 3
)(3 31 0
)=(9 6
)=(1 2
)(mod 4)
P2 =(1 1
)(3 31 0
)=(4 3
)=(0 3
)(mod 4)
P3 =(0 1
)(3 31 0
)=(1 0
)(mod 4)
Quindi il testo in chiaro è:
P =(1 2 0 3 1 0
)4. Dobbiamo costruire una equazione del tipo:(
PiPj
)K =
(CiCj
)
dove le righe Pi, Ci e Pj, Cj sono due coppie testo in chiaro / testocifrato di lunghezza due.Risolvendo rispetto alla matrice delle incognite otterremo la chiave.Per risolvere l’equazione la matrice del testo in chiaro deve essereinvertibile; dovremo tenere presente questo fatto nello scegliere lerighe della matrice.Fortunatamente la matrice costruita usando P1 e P2 va bene, infatti:
det(
1 20 3
)= 3
che non è né nullo né multiplo di 2.
9
1. Aritmetica modulare
Quindi possiamo scrivere:
K =(
1 20 3
)−1
·(
2 31 1
)= 1
3
(3 −20 1
)·(
2 31 1
)
= 3(
4 71 1
)=(
0 13 3
)(mod 4) (1.1)
Nella equazione precedente si è posto 1/3 ≡ 3 (mod 4), per calcolarel’inverso di 3 è possibile usare l’algoritmo di Euclide esteso, oppuresi può osservare che 3 · 3 = 9 ≡ 1 (mod 4).
Esercizio 1.4 Alice e Bob usano una tecnica di cifratura affine basatasull’aritmetica in Z10. L’algoritmo di cifratura è la espressione:
Ci = Pi ·K +B (mod 10)
I vettori riga 1×2 Ci e PI contengono rispettivamente la coppia i-esimadi numeri cifrata e in chiaro, mentre la chiave è composta dalla matriceK e dal vettore B.
La chiave condivisa è:
K =(
3 72 7
)B =
(4 9
)1. Verificare che K sia una chiave valida.
2. Cifrare il messaggio:
P =(6 7 3 9 3 6
)3. Decifrare il messaggio cifrato.
4. Portare un attacco di tipo known-plaintext e trovare la chiave (K eB).
Soluzione Perché K sia valida devono essere rispettate le seguenti condi-zioni: {
det(K) 6= 0gcd(det(K),10) = 1
Nel nostro caso abbiamo che det(K) = 7 e le due condizioni sono rispettate.
10
1.2. Cifratura con matrici
Scomponiamo il messaggio P in 3 vettori riga:
P1 =(6 7
)P2 =
(3 9
)P3 =
(3 6
)
Calcoliamo i testi cifrati:
C1 =(6 7
)(3 72 7
)+(4 9
)=(6 0
)C2 =
(3 9
)(3 72 7
)+(4 9
)=(1 3
)C3 =
(3 6
)(3 72 7
)+(4 9
)=(5 2
)Il testo cifrato è quindi:
C =(6 0 1 3 5 2
)Per decifrare il messaggio occorre invertire la matrice K. L’algoritmo
di decifratura è l’espressione:
P = CK−1 −BK−1
K−1 = 17
(7 −7−2 3
)mod 10
L’inverso di 7 (mod 10) si può trovare usando l’algoritmo esteso diEuclide:
rj qj sj tj10 – – 1 07 1 – 0 13 2 10 = 1 · 7 + 3 1 −11 3 7 = 2 · 3 + 1 −2 30 – 3 = 3 · 1 + 0 7 −10
L’inverso di 7 è 3, infatti:
7 · 3 mod 10 = 21 mod 10 = 1
11
1. Aritmetica modulare
Quindi:
K−1 = 3(
7 38 3
)mod 10 =
(1 94 9
)
−BK−1 = −(4 9
)(1 94 9
)=(0 3
)Calcoliamo i testi in chiaro:
P1 =(6 0
)(1 94 9
)+(0 3
)=(6 7
)P2 =
(1 3
)(1 94 9
)+(0 3
)=(3 9
)P3 =
(5 2
)(1 94 9
)+(0 3
)=(3 6
)Per scoprire la chiave dato un insieme di coppie Pi, Ci, occorre scrivere
un sistema di equazioni:C1 = P1K +B (1.2)C2 = P2K +B (1.3)C3 = P3K +B (1.4)
Sottraendo la (1.4) alla (1.3) e alla (1.2), si ottiene una nuova equazionein cui la costante B non è presente e da cui si può ricavare la matrice K:(
C1 − C3C2 − C3
)=(P1 − P3P2 − P3
)K (1.5)
K =(P1 − P3P2 − P3
)−1 (C1 − C3C2 − C3
)(1.6)
K =(
3 10 3
)−1 ( 1 −2−4 1
)(1.7)
Perché l’attacco abbia successo è necessario che la matrice dei testi inchiaro sia invertibile. Poiché:
det(
3 10 3
)= 9
la matrice è invertibile e non ci sono fattori comuni con 10, pertantol’inversa è unica:
K = 19
(3 −10 3
)(1 −2−4 1
)= 9
(7 −7−12 3
)=(
63 −63−108 27
)
K ≡(
3 72 7
)(mod 10)
12
1.3. Test di primalità
Da notare che 9−1 ≡ 9 (mod 10) = 9, infatti 9 · 9 mod 10 = 1.Trovato K si può usare la (1.2) per trovare B:
B = C1 − P1K =(6 0
)−(2 1
)=(4 −1
)B ≡
(4 9
)(mod 10)
1.3 Test di primalità1.3.1 Test di Fermat
Il teorema di Fermat dice che se n > 1 è primo, allora an−1 ≡ 1(mod n) per ∀a < n− 1.
Possiamo quindi definire un test di Fermat per verificare se n è primo.Scegliamo un insieme di basi 1 < ai < n− 1, se esiste un ai tale che:
an−1i 6≡ 1 (mod n)
possiamo dire con certezza che n non è primo. Se invece non troviamoquesto ai dobbiamo concludere che n probabilmente è primo. Ovviamentequesta probabilità è tanto più alta quante più basi abbiamo provato.
Esercizio 1.5 Usando il test di Fermat, trovare un numero primo maggioreo uguale a 27.
Soluzione Proviamo usando la base 2:
226 mod 27 = 13 non è primo228 mod 29 = 1
Il numero 29 forse è primo. Proviamo con altre basi:
328 mod 29 = 1528 mod 29 = 1728 mod 29 = 1
Concludiamo che probabilmente 29 è primo.
1.3.2 Test di Miller-RabinDato il numero n candidato primo, definiamo due numeri k e m tali
che:n− 1 = 2km
13
1. Aritmetica modulare
con m dispari. Scegliamo poi una base a, 1 ≤ a ≤ n− 1.Calcoliamo b0 = am mod n.Se b0 = ±1, allora n è probabilmente primo.Altrimenti calcoliamo bi = b2
i−1 mod n con 1 ≤ i ≤ k − 1.Se bi = −1, n è probabilmente primo.Se bi = 1, n è composto e gcd (bi−1 − 1,n) è un fattore.Se bi 6= ±1, i← i+ 1 e si procede con il test.Se si raggiunge i = k − 1 e bi 6= −1 allora n è composto.
Esercizio 1.6 Verificare se il numero 341 è primo usando il test di Fermate il test di Miller-Rabin.
Soluzione Test di Fermat
2340 mod 341 = 13340 mod 341 = 56
Quindi 341 non è primo, ma è pseudoprimo relativamente alla base 2.Test di Miller-Rabin Calcoliamo k e m:
340 = 22 · 85
da cui ricaviamo k = 2 e m = 85.Usiamo la base a = 2
b0 = am mod n = 285 mod 341 = 32 6= ±1b1 = b2
0 mod n = 322 mod 341 = 1
Quindi il numero 341 è composto. Inoltre possiamo calcolare un fattorep1:
p1 = gcd(b0 − 1,n) = gcd(31,341) = 31Infatti 341 = 11× 31.
Esercizio 1.7 Verificare se il numero 313 è primo usando il test di Miller-Rabin sulle basi 2 e 3.
Soluzione Calcoliamo k e m:
312 = 23 · 39
da cui ricaviamo k = 3 e m = 39.Usiamo la base a = 2
b0 = am mod n = 239 mod 313 = 25 6= ±1b1 = b2
0 mod n = 252 mod 313 = 312 = −1
14
1.4. Campi finiti
Proviamo con la base a = 3
b0 = am mod n = 339 mod 313 = 1
Concludiamo che probabilmente il numero è primo.
Esercizio 1.8 Verificare se il numero 17 è primo usando il test di Miller-Rabin sulle basi 2 e 3.
Soluzione Calcoliamo k e m:
16 = 24 · 1
da cui ricaviamo k = 4 e m = 1. Usiamo la base a = 2
b0 = am mod n = 21 mod 17 = 2 6= ±1b1 = b2
0 mod n = 22 mod 17 = 4b2 = b2
0 mod n = 42 mod 17 = 16 = −1
Usiamo la base a = 3
b0 = am mod n = 31 mod 17 = 3 6= ±1b1 = b2
0 mod n = 32 mod 17 = 9b2 = b2
0 mod n = 92 mod 17 = 13b3 = b2
0 mod n = 132 mod 17 = 16 = −1
Il numero è probabilmente primo.
1.4 Campi finitiEsercizio 1.9 Si consideri lo spazio dei polinomi f(x) con coefficienti realiin cui il coefficiente di grado massimo è unitario. Due polinomi f(x) eg(x) si dicono primi fra loro se gcd (f(x),g(x)) = 1.
Trovare d(x) = gcd(x4 + x2 + 1,x2 + 1) e trovare i polinomi s(x) e t(x)tali per cui d(x) = s(x)f(x) + t(x)g(x).
Soluzione .sj(x) tj(x)
– 1 0– 0 1
x4 + x2 + 1 = x2 · (x2 + 1) + 1 1 −x2
x2 + 1 = (x2 + 1) · 1 + 0 −(x2 + 1) x4 + x2 + 1
15
1. Aritmetica modulare
d(x) = 1s(x) = 1t(x) = −x2
Infatti 1 = 1 · (x4 + x2 + 1)− x2 · (x2 + 1).
Esercizio 1.10 Calcolare d(x) = gcd(x4−4x3+6x2−4x+1,x3−x2+x−1).
Soluzione .
sj(x) tj(x)−− 1 0−− 0 1
x4 − 4x3 + 6x2 − 4x + 1 == (x− 3)(x3 − x2 + x− 1) + (2x2 − 2)
1 −(x− 3)
x3 − x2 + x− 1 = (12x− 1
2)(2x2 − 2) + (2x− 2) −12(x− 1) 1
2(x2 − 4x + 5)2x2 − 2 = (x + 1)(2x− 2) + 0 1
2(x2 + 1) −12(x3 − 3x2 + 3x + 1)
L’ultimo resto non nullo è 2x − 2 = 2(x − 1). Prendiamo come gcd ilpolinomio monico x− 1.
d(x) = x− 1
u(x) = −14x+ 1
4v(x) = 1
4x2 − x+ 5
4Esercizio 1.11 Se un polinomio f(x) ha radici multiple, esse sono radicidi gcd (f(x),f ′(x)).
Trovare la radice multipla del polinomio x4 − 2x3 − x2 + 2x+ 1.
Soluzionef ′(x) = 4x3 − 6x2 − 2x+ 2
x4 − 2x3 − x2 + 2x+ 1 =(1
4x−18
) (4x3 − 6x2 − 2x+ 2
)+(−5
4x2 + 5
4x+ 54
)4x3 − 6x2 − 2x+ 2 =
(−16
5 x+ 85
)(−5
4x2 + 5
4x+ 54
)+ 0
Quindi la radice multipla è x2 − x− 1. Infatti
x4 − 2x3 − x2 + 2x+ 1 = (x2 − x− 1)2
16
1.4. Campi finiti
Esercizio 1.12 Siano f(x) = x4 + x3 + x2 + 1 e g(x) = x3 + 1 polinomicon coefficienti in Z2. Trovare d(x) = gcd(f(x),g(x)) ed esprimelo comecombinazione lineare di f e g.
Soluzioner(x) s(x) t(x)
x4 + x3 + x2 + 1 1 0x3 + 1 0 1x2 + x x4 + x3 + x2 + 1 = (x + 1)(x3 + 1) + x2 + x 1 −(x + 1)x + 1 x3 + 1 = (x + 1)(x2 + x) + (x + 1) −(x + 1) x2
0 x2 + x = x(x + 1) + 0 · · · · · ·
Per effettuare le divisioni tra polinomi ricordiamo che si applica lalunga divisione e che siamo in algebra modulo 2 (quindi 1 + 1 = 0).
x4 +x3 +x2 +1 x3 + 1x4 x x+ 1
x3 +x2 +x +1x3 1
x2 +x
x3 +1 x2 + xx3 +x2 x+ 1
x2 1x2 +x
x +1Il gcd è d(x) = x+ 1 e può essere scritto come:
x+ 1 = (x+ 1)(x4 + x3 + x2 + 1) + x2(x3 + 1)
Esercizio 1.13 Trovare il fattore multiplo in f(x) = x4 − x2 + 1 ∈ Z3[x].
Soluzione Se un fattore è multiplo, è presente sia in f(x) che in f ′(x),pertanto comparirà nel gcd(f,f ′).
Nel caso in esame f ′(x) = 4x3 − 2x = x3 + x.
r(x) q(x)x4 − x2 + 1 −−
x3 + x xx2 + 1 x
0 −−· · ·
Quindi gcd(f,f ′) = x2 + 1.
17
1. Aritmetica modulare
Esercizio 1.14 Mostrare che r(x) = x2 + 1 ∈ Z3[x] è irriducibile. Trovarel’inverso moltiplicativo di (2x+ 1) mod r(x).
Soluzione Se r(x) fosse riducibile, sarebbe divisibile per un polinomiod(x) di grado inferiore (grado uno). I polinomi di grado 1 sono:
x
x+ 1x+ 2
2x = 2 · x2x+ 1 = 2(x+ 2)2x+ 2 = 2(x+ 1)
Non considerando i polinomi che sono uguali a meno di una costantemoltiplicativa, restano tra polinomi: x, x+ 1,x+ 2:
x2 + 1 = x · x+ 1 (1.8)x2 + 1 = (x+ 2)(x+ 1) + 2 (1.9)
(1.10)
Quindi (x2 + 1) non è riducibile.Per calcolare (2x+ 1)−1 usiamo l’algoritmo di Euclide:
r(x) q(x) s(x) t(x)x2 + 1 −− 1 02x+ 1 2x+ 2 0 1
2 · · · x2 + 1 = (2x+ 2)(2x+ 1) + 2 1 x+ 1· · ·
Per comodità si riporta la divisione x2+12x+1 . Nello svolgimento ricordiamo
sempre che x2 = −1 = 2.
x2 +1 −x+ 1x2 −x −x− 1
x +1x −1
2
Quindi possiamo scrivere che
(2x+ 1)(x+ 1) mod (x2 + 1) = 2
e l’inverso di 2x+ 1 sarà (−x− 1) ≡ (2x+ 2).
18
1.4. Campi finiti
Alternativamente potevamo calcolare l’inverso come (2x+ 1)9−2 mod(x2 + 1) usando Square-and-Multiply.
1 12 × (2x + 1) = (2x + 1)1 (2x + 1)2 × (2x + 1) = (−x + 1)3 = −x3 + 1 = −x(−1) + 1 = x + 11 (x + 1)2 × (2x + 1) = (x2 + 2x + 1)(2x + 1) = 2x(2x + 1) = 4x2 + x = 2x + 2
Esercizio 1.15 (Cifrario di Hill su GF (4)) Il messaggio binario in chia-ro P = 011000110100 viene cifrato usando un cifrario di Hill su GF (4).Come usale, gli elementi del campo sono la classe dei resti modulor(x) = x2+x+1. Il cifrario usa come chiave una matrice K con dimensione2× 2.
1. Dire che condizioni deve rispettare la chiave K.2. Cifrare il messaggio P considerando il caso
K =(
0 1x+ 1 x+ 1
)
3. Decifrare il messaggio ottenuto al passo precedente4. Usando la coppia messaggio in chiaro / messaggio cifrato ottenuta
ai punti precedenti, effettuare un attacco di tipo known plaintext ericavare la chiave K.
Soluzione 1. La chiave K deve rispettare le seguenti condizioni:{det(K) 6= 0gcd(det(K),x2 + x+ 1) = 1
Notare che, poiché operiamo in un campo, la seconda è sempre veraper qualunque K che rispetti la 1.
2. Per prima cosa convertiamo il messaggio binario in elementi diGF (4). Poiché gli elementi sono {0, 1, x, x+ 1} la cosa più sempliceè convertire ogni coppia di bit in un polinomio. Pertanto il messaggiodiventa:
P =(1 x 0 x+ 1 1 0
)La chiave è una matrice 2× 2, quindi il testo in chiaro deve esserediviso in vettori Pi di due elementi:
P1 =(1 x
)P2 =
(0 x+ 1
)P3 =
(1 0
)
19
1. Aritmetica modulare
Procediamo quindi applicando la formula:
Ci = Pi ·M (mod 4) (1.11)
C1 =(1 x
)( 0 1x+ 1 x+ 1
)=(x2 + x x2 + x+ 1
)=
(1 0
)(mod x2 + x+ 1)
C2 =(0 x+ 1
)( 0 1x+ 1 x+ 1
)=(x2 + 2x+ 1 x2 + 2x+ 1
)=
(x x
)(mod x2 + x+ 1)
C3 =(1 0
)( 0 1x+ 1 x+ 1
)=(0 1
)(mod x2 + x+ 1)
Quindi il testo cifrato C risulta:
C =(1 0 x x 0 1
)che, espresso in binario, diventa C = 010010100001.
3. Occorre per prima cosa calcolare la matrice inversa della chiave:
K−1 = 1−(x+ 1)
(x+ 1 −1−(x+ 1) 0
)= x
(x+ 1 1x+ 1 0
)=(
1 x1 0
)(mod x2+x+1)
Nel fare questo calcolo si consideri che 1x+1 ≡ x, infatti x(x+ 1) =
x2 + x = x+ 1 + 1 = x.Calcoliamo il testo in chiaro:
P1 =(1 0
)(1 x1 0
)=(1 x
)(mod x2 + x+ 1)
P2 =(x x
)(1 x1 0
)=(2x x2
)=(0 x+ 1
)(mod x2 + x+ 1)
P3 =(0 1
)(1 x1 0
)=(1 0
)(mod x2 + x+ 1)
Quindi il testo in chiaro è:
P =(1 x 0 x+ 1 1 0
)
20
1.4. Campi finiti
4. Dobbiamo costruire una equazione del tipo:(PiPj
)K =
(CiCj
)
dove le righe Pi, Ci e Pj, Cj sono due coppie testo in chiaro / testocifrato di lunghezza due.Risolvendo rispetto alla matrice delle incognite otterremo la chiave.Per risolvere l’equazione la matrice del testo in chiaro deve essereinvertibile; dovremo tenere presente questo fatto nello scegliere lerighe della matrice.Fortunatamente la matrice costruita usando P1 e P2 va bene, infatti:
det(
1 x0 x+ 1
)= x+ 1
che non è nullo.Quindi possiamo scrivere:
K =(
1 x0 x+ 1
)−1
·(
1 0x x
)= 1x+ 1
(x+ 1 −x
0 1
)·(
1 0x x
)
= x
(x+ 1 x
0 1
)·(
1 0x x
)=(x+ 1 x
0 1
)·(
1 0x x
)
=(
1 x+ 10 x
)·(
1 0x x+ 1
)=(x2 + x+ 1 x2 + x
x2 x2
)
=(
0 1x+ 1 x+ 1
)(mod x2 + x+ 1)
21
2Cifrari a blocco e crittoanalisi
2.1 Modi d’usoEsercizio 2.1 Si consideri il seguente crittosistema operante in modalitàcontatore (counter mode).
CTR
Hill
R′L′
‖
R′′L′′
⊕K
P
C
Il cifrario di Hill opera su Z2[x]/g(x)con
g(x) = x2 + x+ 1ed è definito dalla equazione:(L′′ R′′
)=(L′ R′
)M mod g(x)
La chiave è:
M =(x x+ 10 1
)
Il valore iniziale del contatore è IV =9.
1. Verificare che la chiave del cifrario di Hill è valida.2. Trovare la chiave inversa e verificare.3. Cifrare il messaggio 1100 0101.4. Sapendo che per IV = 3 al messaggio in chiaro P=0100 0010
corrisponde al testo cifrato C=0101 1011, trovare la chiave.
23
2. Cifrari a blocco e crittoanalisi
Soluzione Siccome det(M) = x è non nullo e primo con g(x), la chiave èvalida.
M−1 = x−1(
1 x+ 10 x
)=(x+ 1 x
0 1
)
Come verifica calcoliamo MM−1 = I:(x x+ 10 1
)(x+ 1 x
0 1
)=(x2 + x x2 + x+ 1
0 1
)mod g(x) =
(1 00 1
)= I
Al passo 1 il contatore vale
CTR1 = 9 = 1001 =(x 1
)In questo calcolo abbiamo espresso il valore del contatore in forma binariae poi come vettore di polinomi di grado massimo 1.
L’uscita del cifrario di Hill sarà:(x 1
)(x x+ 10 1
)=(x+ 1 0
)I primi 4 bit del keystream, K1, saranno:
K1 =(x+ 1 0
)= 1100
Quindi il testo cifrato sarà:
C1 = P1 ⊕K1 = 1100⊕ 1100 = 0000
Il calcolo per il secondo blocco è simile ma con CTR2 = IV + 1 = 10.
CTR2 = 10 = 1010 =(x x
)L’uscita del cifrario di Hill sarà:
(x x
)(x x+ 10 1
)=(x+ 1 x+ 1
)Quindi
C2 = P2 ⊕K2 = 1010
Per trovare la chiave, cioè la matriceM , occorre ricordare che il cifrariodi Hill non agisce sul testo in chiaro, ma sul contatore e dà in uscita ilkeystream. Nel nostro caso il keystream è K = C ⊕ P = 0001 1001,mentre i corrispondenti bit del contatore sono CTR = 3||4 = 0011 0100.
24
2.1. Modi d’uso
I bit del keystream e del contatore devono essere espressi come elementiin GF (22) e posti in matrice per ottenere la equazione:
M = CTR−1K =(
0 x+ 11 0
)−1 (0 1x 1
)= (x+ 1)−1
(0 x+ 11 0
)(0 1x 1
)
= x
(1 x+ 11 0
)=(
0 10 x
)
Esercizio 2.2 Si consideri il seguente crittosistema in modelità CFM.IV (2 bit)
⊕K ′
S
A
⊕B
K ′′
⊕P1
C1
⊕
S
⊕
⊕
C2
⊕
· · ·
Sia:
IV = 10K ′ = 01K ′′ = 10
Lo S-boxB = S(A) opera unainversione in:
Z2[x]/x2 + x+ 1
La sequenza di bit 00 èinalterata.
1. Cifrare il messaggio 1101
2. Tabulare la permutazione realizzata dal S-box3. Calcolare la probabilità che sia vera la equazione lineare (la numera-
zione assegna indice 0 al bit più significativo) :
a0 ⊕ a1 ⊕ b0 = 1
4. Calcolare la probabilità che sia vera la equazione differenziale:
A⊕ A′ = 01→ B ⊕B′ = 01
Soluzione Consideriamo il primo blocco di testo:
A1 = IV ⊕K ′ = 11 = x+ 1B1 = (x+ 1)−1 mod x2 + x+ 1 = x = 10C1 = B1 ⊕K ′′ ⊕ P1 = 11
25
2. Cifrari a blocco e crittoanalisi
Per il secondo blocco partiamo da C1:
A2 = C1 ⊕K ′ = 10 = x
B2 = x−1 mod x2 + x+ 1 = x+ 1 = 11C2 = B2 ⊕K ′′ ⊕ P2 = 00
Quindi C = 1100.Lo S-box realizza la seguente permutazione:
A B a0 ⊕ a1 ⊕ b000 00 001 01 110 11 011 10 1
L’equazione lineare proposta è vera al 50%.Verifichiamo l’equazione differenziale:
A A′ = A⊕ 01 B = S(A) B′ = S(A′) B ⊕B′00 01 00 01 0101 00 01 00 0110 11 11 10 0111 10 10 11 01
L’equazione differenziale proposta è sempre vera.
Esercizio 2.3 Si consideri il seguente crittosistema in modelità CBC.P1
⊕C0
⊕K ′
S
⊕K ′
C1
P2
⊕
· · ·
Sia:
C0 = 010K ′ = 011K ′′ = 110
Il blocco B = S(A) opera unainversione in Z2[x]/x2 + x +1. La sequenza di bit 000 èinalterata.
26
2.1. Modi d’uso
1. Cifrare il messaggio 100011
2. Tabulare la permutazione realizzata dal S-box3. Calcolare la probabilità che l’equazione lineare seguente sia vera:
a0 + b0 + b1 = 0
4. Calcolare la probabilità che la seguente equazione differenziale siavera:
A⊕ A′ = 001→ B ⊕B′ = 101
Soluzione Primo blocco:A1 = C0 ⊕ P1 ⊕K ′ = 101 = x2 + 1B1 = (x2 + 1)−1 mod x3 + x+ 1 = x = 010C1 = B1 ⊕K ′′ = 100
Secondo blocco:A2 = C1 ⊕ P2 ⊕K ′ = 100 = x2
B2 = (x2)−1 mod x3 + x+ 1 = x2 + x+ 1 = 111C2 = B2 ⊕K ′′ = 001
Lo S-box realizza la seguente permutazione:A B a0 ⊕ b0 ⊕ b1
000 000 0001 001 0010 101 1011 110 0100 111 1101 010 0110 011 0111 100 0
L’equazione lineare proposta è vera con probabilità 3/4.Verifichiamo l’equazione differenziale:
A A′ = A⊕ 01 B = S(A) B′ = S(A′) B ⊕B′000 001 000 001 001001 000 idem010 011 101 110 011011 010 idem100 101 111 010 101101 100 idem110 111 011 100 111111 110 idem
27
2. Cifrari a blocco e crittoanalisi
L’equazione differenziale proposta è vera con probabilità 1/4.
2.2 AES semplificatoEsercizio 2.4 (S-box AES semplificato) Un S-box opera come segue:
• i 4 bit in ingresso (b0b1b2b3) sono convertiti in un polinomio N(x) digrado 3 con coefficienti in Z2;
• il polinomio N(x) viene considerato un elemento di GF (16) =Z2[x]/(x4 +x+ 1) e invertito, ottenendo l’elemento N−1(x); l’inversodi 0 è convenzionalmente posto a 0;
• i coefficienti di N−1(x) sono usati per formare un nuovo polinomioN(y) ∈ Z2[y]/(y4 + 1);
• l’output del S-box sono i coefficienti del polinomio M(y) costruitocome segue:
M(y) = N(y) · a(y) + b(y) mod (y4 + 1) (2.1)cona(y) = y3 + y2 + 1 (2.2)b(y) = y3 + 1 (2.3)
(2.4)
1. Dati i bit in ingresso 1000, calcolare l’output del S-box.2. Verificare che Z2[y]/(y4 + 1) non forma un campo.3. Verificare che a(y) è invertibile in Z2[y]/(y4 + 1) e trovare a−1(y).4. Trovare lo S-box inverso a quello dato.5. Decifrare la sequenza di bit 1000.
Soluzione La sequenza di bit 1000 corrisponde al polinomio N(x) = x3.Occorre trovare l’inverso di x3 (mod x4 + x+ 1). Usiamo l’algoritmo diEuclide per i polinomi e otteniamo:
r(x) q(x) s(x) t(x)x4 + x+ 1 −− 1 0
x3 x 0 1x+ 1 x2 + x+ 1 x4 + x+ 1 = x · x3 + (x+ 1) 1 x
1 x+ 1 x3 = (x2 + x+ 1)(x+ 1) + 1 x2 + x+ 1 x3 + x2 + x+ 10 · · ·
28
2.2. AES semplificato
Quindi N−1(x) = x3 + x2 + x + 1. Tenendo presente che x4 = x + 1verifichiamo che N(x)N−1(x) = 1:
(x3 + x2 + x+ 1)x3 = (x3 + x2 + x+ 1)xxx(x3 + x2 + x+ 1)x = x4 + x3 + x2 + x = x3 + x2 + 1
(x3 + x2 + 1)x = x4 + x3 + x = x3 + 1(x3 + 1)x = x4 + x = 1
Definiamo il polinomio N(y) = y3 + y2 + y + 1 e calcoliamo M(y):
M(y) = (y3 + y2 + y + 1)(y3 + y2 + 1) + (y3 + 1) mod (y4 + 1) == (y6 + y3 + y + 1) + (y3 + 1) mod (y4 + 1) == y6 + y mod (y4 + 1) == y2 + y
L’output del S-box è 0110.Il polinomio y4 + 1 è riducibile, infatti y4 + 1 = (y + 1)4. Quindi
Z2[y]/(y4 + 1) non forma un campo.Il polinomio a(y) è invertibile (mod y4 + 1) se gcd(a(y),y4 + 1) = 1.
Al solito procediamo con l’algoritmo di Euclide
r(x) q(x) s(x) t(x)y4 + 1 −− 1 0
y3 + y2 + 1 y + 1 0 1y2 + y y y4 + 1 = (y3 + y2 + 1)(y + 1) + (y2 + y) 1 y + 1
1 y2 + y (y3 + y2 + 1)y + 1 y y2 + y + 10 · · ·
Come è facile verificare, a−1(y) = y2 + y + 1.Noto M(y), lo S-box inverso è composto dai seguenti passi.• Si calcola
N(y) = M(y)a−1(y) + a−1(y)b(y) mod (y4 + 1) == M(y)(y2 + y + 1) + (y3 + y2) mod (y4 + 1)
• A partire da N(y) si costruisce il polinomio N−1(x) ∈ GF (16).• Si calcola l’inverso N(x).La sequenza 1000 corrisponde al polinomio M(y) = y3. Il polinomio
N(y) vale:
N(y) = y3(y2 + y + 1) + (y3 + y2) mod (y4 + 1) == y5 + y4 + y2 mod (y4 + 1) == y + 1 + y2 = y2 + y + 1
29
2. Cifrari a blocco e crittoanalisi
Il polinomio da invertire in GF(16) è N−1(x)x2 + x+ 1 che ha comeinverso (x2 + x). Infatti:
(x2 + x+ 1)(x2 + x) = x4 + x3 + x2 + x3 + x2 + x = x4 + x (mod x4 + x+ 1)= (x+ 1) + x = 1
2.2.1 Commenti sul S-box AES semplificatoIn questo capitolo si farà spesso riferimento al S-box AES semplificato,
cioè una funzione B = S(A) che opera su blocchi di 4 bit.
B = S(A)
a0
b0
a1
b1
a2
b2
a3
b3
La trasformazione B = S(A) è definitamatematicamente come:
Y = (a0x3 + a1x
2 + a2x+ a3)−1 (mod x4 + x+ 1)B = (x3 + x2 + 1)Y + (x3 + 1) (mod x4 + 1)B = b0x
3 + b1x2 + b2x+ b3
Lo S-box può anche essere definito, usando la notazione esadecimale,come tabella:
IN (A) 0 1 2 3 4 5 6 7 8 9 A B C D E FOUT (B) 9 4 A B D 1 8 5 6 2 0 3 C E F 7
Del S-box è noto che le seguenti equazioni lineari sono vere conprobabilità 3/4:
a3 ⊕ b0 = 1 (2.5)a0 ⊕ a1 ⊕ b0 = 1 (2.6)
a1 ⊕ b1 = 0 (2.7)a0 ⊕ a1 ⊕ a2 ⊕ a3 ⊕ b1 = 0 (2.8)
a1 ⊕ a2 ⊕ b0 ⊕ b1 = 1 (2.9)a0 ⊕ b0 ⊕ b1 = 1 (2.10)
Inoltre è noto che le seguenti relazioni differenziali sono vere con
30
2.3. Crittoanalisi lineare
probabilità 1/4:
A⊕ A′ = 0001→ B ⊕B′ = 1011 (2.11)A⊕ A′ = 0010→ B ⊕B′ = 1100 (2.12)A⊕ A′ = 0100→ B ⊕B′ = 0010 (2.13)A⊕ A′ = 1000→ B ⊕B′ = 1111 (2.14)
2.3 Crittoanalisi lineareEsercizio 2.5 Si consideri il seguente cifrario a blocco operante su un testoin chiaro P = p0‖p1‖p2‖p3 di 4 bit e che usa una chiave K = k0‖k1‖k2‖k3anch’essa di 4 bit.
P
⊕K
S
A
⊕
B
C
Matematicamente, possiamo scrivereche, per 0 ≤ i ≤ 3:
ai = pi ⊕ ki (2.15)B = S(A) (2.16)ci = bi ⊕ ki (2.17)
La funzione B = S(A) è lo S-boxdi AES semplificato, mentre C =c0‖c1‖c2‖c3 è il testo cifrato.
Si conoscono le seguenti coppie di testo in chiaro / testo cifrato:
Coppia P C(I) 0000 1110(II) 0110 1111(III) 0101 1101(IV) 1111 0101
Usando la tecnica della crittoanalisi lineare, trovare la chiave K.Calcolare il numero di coppie (P,C) necessarie per avere una confidenza
al 95% di riuscire ad identificare la chiave.
31
2. Cifrari a blocco e crittoanalisi
Soluzione Il nostro scopo è ottenere delle equazioni del tipo:
z ⊕∑
pi ⊕∑
cj =∑
kl
Dove:• z è un termine noto (0 oppure 1),• ∑
pi è la somma di un sottoinsieme dei bit del testo in chiaro,• ∑
cj è la somma di un sottoinsieme dei bit del testo cifrato,• ∑
kl è la somma di un sottoinsieme dei bit della chiave.Sostituendo le equazioni (2.15) e (2.17) nelle equazioni (2.5)–(2.10),
otteniamo le seguenti equazioni:
1⊕ p3 ⊕ c0 = k0 ⊕ k3 (2.18)1⊕ p0 ⊕ p1 ⊕ c0 = k1 (2.19)
p1 ⊕ c1 = 0 (2.20)p0 ⊕ p1 ⊕ p2 ⊕ p3 ⊕ c1 = k0 ⊕ k2 ⊕ k3 (2.21)1⊕ p1 ⊕ p2 ⊕ c0 ⊕ c1 = k0 ⊕ k2 (2.22)
1⊕ p0 ⊕ c0 ⊕ c1 = k1 (2.23)
Per ognuna delle equazioni (2.18)–(2.23) calcoliamo la parte a sinistradell’uguale per ogni coppia (Pi,Ci). Il valore che ricorre più spesso vieneassunto come valore della parte sinistra. In caso di pareggio si sceglie acaso.
Coppia (Pi,Ci)equazione (I) (II) (III) (IV) equazione risultante
(2.18) 0 0 1 0 k0 ⊕ k3 = 0(2.19) 0 1 1 1 k1 = 1(2.20) 1 0 0 0 0 = 0(2.21) 1 1 1 1 k0 ⊕ k2 ⊕ k3 = 1(2.22) 1 1 0 0 k2 ⊕ k0 = 1 (scelto a caso)(2.23) 1 1 1 1 k1 = 1
Scartando le equazioni ripetute o prive dell’incognita, otteniamo unsistema lineare di 4 equazioni con quattro incognite:
k0 ⊕ k3 = 0 (2.24)k1 = 1 (2.25)
k0 ⊕ k2 ⊕ k3 = 1 (2.26)k0 ⊕ k2 = 1 (2.27)
32
2.3. Crittoanalisi lineare
Da cui ricaviamo
k0 = 0k1 = 1k2 = 1k3 = 0
Quindi K = 0110, che, come è facile verificare, è la soluzione corretta.Supponiamo di avere a disposizione n coppie (P,C). Le sei equazioni
(2.18)–(2.23) danno luogo a quattro equazioni linearmente indipendenti.Ciascuna di esse è verificata per il 75% delle coppie (P,C).
Indichiamo con Πi la v.c. che identifica il numero di coppie per cui laequazione i-esima è verificata. Chiaramente Πi è binomiale con:
E[Π] = 0,75n (2.28)var[Π] = 0,75(1− 0,75)n = 0,1875n (2.29)
Supponendo n grande, possiamo approssimare Πi con una distribuzionenormale.
L’attacco ha successo se: Πi > 0,5n per tutte le quattro equazioniindipendenti. Questo evento ha probabilità:
Pr {Πi > 0,5n}4 = Pr{
Πi − 0,75n√0,1875n >
0,5n− 0,75n√0,1875n
}4
= Pr{Z > −0,577
√n}4
Imponendo l’uguaglianza con la confidenza cercata, otteniamo:
Pr{Z > −0,577
√n}4
= 0,95
Pr{Z > −0,577
√n}
= 4√
0,95 = 0,987
Pr{Z < −0,577
√n}
= 1− 0,987 = 0,013−0,577
√n < −2,226n > 14,88
Arrotondando si ottiene n ≥ 15.
Esercizio 2.6 Si consideri il seguente cifrario a blocco operante su untesto in chiaro P di 4 bit e che usa una chiave K di 8 bit. Si definiscono:
K0,3 = k0‖k1‖k2‖k3 (2.30)K4,7 = k4‖k5‖k6‖k7 (2.31)
33
2. Cifrari a blocco e crittoanalisi
P
⊕K0,3
S
A
⊕
M
K4,7
S
N
⊕
B
K0,3
C
Per 0 ≤ i ≤ 3, siano pi i bitdel testo in chiaro, ki i bit del-la chiave e ci i bit del testocifrato.
ai = pi ⊕ ki (2.32)M = S(A) (2.33)ni = mi ⊕ ki+4 (2.34)B = S(N) (2.35)ci = bi ⊕ ki (2.36)
La funzione Y = S(X) è loS-box di AES semplificato.
Si conoscono le seguenti coppie di testo in chiaro / testo cifrato:
Coppia P C(I) 0010 0010(II) 0011 1111(III) 0100 1010(IV) 0111 1100(V) 1000 1000
Usando la crittoanalisi lineare trovare k5. Stimare il numero di coppiedi testi in chiaro / testi cifrati necessari per avere una confidenza del 95%di trovare k5.
Soluzione Possiamo scrivere le equazioni (2.5)–(2.10) per ciascuno deidue round del cifrario. Per semplicità ignoriamo la (2.8).
34
2.3. Crittoanalisi lineare
Per il primo round abbiamo:
p3 ⊕ k3 ⊕m0 = 1 (2.37)p0 ⊕ k0 ⊕ p1 ⊕ k1 ⊕m0 = 1 (2.38)
p1 ⊕ k1 ⊕m1 = 0 (2.39)p1 ⊕ k1 ⊕ p2 ⊕ k2 ⊕m0 ⊕m1 = 1 (2.40)
p0 ⊕ k0 ⊕m0 ⊕m1 = 1 (2.41)
Mentre per il secondo round abbiamo:
m3 ⊕ k7 ⊕ c0 ⊕ k0 = 1 (2.42)m0 ⊕ k4 ⊕m1 ⊕ k5 ⊕ c0 ⊕ k0 = 1 (2.43)
m1 ⊕ k5 ⊕ c1 ⊕ k1 = 0 (2.44)m1 ⊕ k5 ⊕m2 ⊕ k6 ⊕ c0 ⊕ k0 ⊕ c1 ⊕ k1 = 1 (2.45)
m0 ⊕ k4 ⊕ c0 ⊕ k0 ⊕ c1 ⊕ k1 = 1 (2.46)
Sommando la (2.39) e la (2.44) otteniamo:
p1 ⊕ k1 ⊕m1 ⊕m1 ⊕ k5 ⊕ c1 ⊕ k1 = 0p1 ⊕ c1 = k5
Questa equazione è vera se la (2.39) e la (2.44) sono entrambe falseoppure entrambe vere, quindi con probabilità:
(0,75)2 + (0,25)2 = 0,625
Applicando le coppie (Pi,Ci) note si ottiene:
Coppia (Pi,Ci)(I) (II) (III) (IV) (V) equazione risultante0 1 1 0 0 k5 = 0
Quindi k5 = 0.Nota: la chiave usata per generare le coppie è: K = 01011010.Abbiamo visto che l’equazione è vera con probabilità 0,625. Quindi
L’attacco ha successo se:
Pr {Πi > 0,5n} = Pr{Z >
0,5n− 0,625n√0,234n
}= Pr
{Z > −0,258
√n}
Imponendo l’uguaglianza con la confidenza cercata, otteniamo:
Pr{Z < −0,258
√n}
= 1− 0,95 = 0,05−0,258
√n < −1,644n ≥ 41
35
2. Cifrari a blocco e crittoanalisi
Il requisito che occorrono più plaintext di quelli possibili possiamointerpretarlo dicendo che, in questo cifrario, anche avendo tutte le coppie,è possibile che la chiave dedotta non sia corretta. In altre parole, l’attaccodi crittoanalisi lineare potrebbe non avere successo.
2.4 Crittoanalisi differenzialeEsercizio 2.7 Si consideri il seguente cifrario a blocco operante su untesto in chiaro P di 4 bit e che usa una chiave K di 8 bit.
P
⊕K0,3
S
A
⊕
B
K4,7
C
Per 0 ≤ i ≤ 3, siano pi i bit del testoin chiaro, ki i bit della chiave e ci ibit del testo cifrato. Allora:
ai = pi ⊕ ki 0 ≤ i ≤ 3 (2.47)B = S(A) (2.48)ci = bi ⊕ ki+4 0 ≤ i ≤ 3 (2.49)
La funzione B = S(A) è lo S-box diAES semplificato.
Usando la crittoanalisi differenziale trovare un insieme ridotto di pos-sibili K. Si supponga di avere scelto come testi in chiaro P = 1000 eP ′ = 0000 e di avere ottenuto C = 0011 e C ′ = 0001.
Soluzione Con una notazione compatta possiamo scrivere che:
C = S(P ⊕K0,3)⊕K4,7 (2.50)C ′ = S(P ′ ⊕K0,3)⊕K4,7 (2.51)
Sommando le due equazioni si ottiene una equazione che non contienegli ultimi 4 bit della chiave.
S(P ⊕K0,3)⊕ S(P ′ ⊕K0,3) = C ⊕ C ′ = 0010.
36
2.4. Crittoanalisi differenziale
Lavorando sulla definizione del S-box è possibile concludere che gliinput al Sbox devono essere:
P ⊕K0,3 = 1111 (2.52)P ′ ⊕K0,3 = 0111 (2.53)
(2.54)
Oppure scambiati tra loro:
P ⊕K0,3 = 0111 (2.55)P ′ ⊕K0,3 = 1111 (2.56)
(2.57)
Nel primo caso l’output del S-box è:
S(P ⊕K0,3) = S(1111) = 0111
E la chiave sarà:
K4,7 = S(P ⊕K0,3)⊕ C = 0111⊕ 0011 = 0100
Nel secondo caso la chiave sarà:
K4,7 = S(0111)⊕ C = 0101⊕ 0011 = 0110
Per conoscere quale dei due casi è quello corretto occorrono altre coppiedi testi. Partendo dalla (2.52) e dalla (2.55) si possono formulare ipotesiper K0,3; infatti:
K0,3 = 1111⊕ 1000 = 0111
oppureK0,3 = 0111⊕ 1000 = 1111
Quindi abbiamo due possibilità:
K = 01110100 (2.58)K = 11110110 (2.59)
Come già detto, per scegliere occorre almeno un’altra coppia di testi.
Esercizio 2.8 Si consideri il seguente cifrario a blocco operante su untesto in chiaro P di 8 bit e che usa una chiave K di 24 bit.
37
2. Cifrari a blocco e crittoanalisi
p0
⊕a0
⊕n0
⊕b0
c0
p1
⊕a1
⊕n1
⊕b1
c1
p2
⊕a2
⊕n2
⊕b2
c2
p3
⊕a3
⊕n3
⊕b3
c3
p4
⊕a4
⊕n4
⊕b4
c4
p5
⊕a5
⊕n5
⊕b5
c5
p6
⊕a6
⊕n6
⊕b6
c6
p7
⊕a7
⊕n7
⊕b7
c7
K0,7
S S
m0 m1 m2 m3m4 m5 m6 m7
K8,15
S S
K16,23
Matematicamente:
ai = pi ⊕ ki 0 ≤ i ≤ 7 (2.60)M1,3 = S(A1,3) (2.61)M4,7 = S(A4,7) (2.62)n2i = mi ⊕ k2i+7 0 ≤ i ≤ 3 (2.63)
n2i+1 = mi+4 ⊕ k2i+1+7 0 ≤ i ≤ 3 (2.64)B1,3 = S(N1,3) (2.65)B4,7 = S(N4,7) (2.66)ci = bi ⊕ ki+15 0 ≤ i ≤ 7 (2.67)
La funzione Y = S(X) è lo S-box di AES semplificato.Costruire un attacco di crittoanalisi differenziale basato sulla cono-
scenza che P = 00000000, C = 11100001, P ′ = 10000000 e C ′ =10011101.
Soluzione Poiché A4,7 = A′4,7 possiamo subito concludere cheM4,7 = M ′4,7.
Inoltre per la equazione (2.14) ci aspettiamo che M1,3 ⊕M ′1,3 = 1111.
All’ingresso del secondo round avremo che:
N1,3 ⊕N ′1,3 = 1010 (2.68)N4,7 ⊕N ′4,7 = 1010 (2.69)
(2.70)
38
2.4. Crittoanalisi differenziale
Ottenendo le equazioni:
S(N1,3)⊕ S(N ′1,3) = C1,3 ⊕ C ′1,3 = 0111 (2.71)S(N4,7)⊕ S(N ′4,7) = C4,7 ⊕ C ′4,7 = 0100 (2.72)
Lavorando sulla funzione Y = S(X) scopriamo che gli ingressi agliS-box del secondo round devono essere:
N1,3 ⊕K8,11 = 0001 oppure 1011N4,7 ⊕K12,15 = 0010 oppure 1000
Questo attacco ci porterà 4 possibili scelte per K16,23. Scegliamo unadelle combinazioni per trovare una chiave candidata:
N1,3 ⊕K8,11 = 0001 (2.73)N4,7 ⊕K12,15 = 0010 (2.74)
K16,19 = S(0001)⊕ 1110 = 0100⊕ 1110 = 1010 (2.75)K20,23 = S(0010)⊕ 0001 = 1010⊕ 0001 = 1011 (2.76)
Quindi una chiave candidata è K16,23 = 10101011. Per trovare altreparti della chiave si assumeK16,23 = 10101011 per buona, si decifra l’ultimoround e si porta un attacco al round precedente.
Altre quattro chiavi candidate si trovano scegliendo altre soluzioni alla(2.73) e alla (2.74). Inoltre bisogna ricordare che questo risultato è verose la (2.14) è vera per il caso considerato, e lo è al 25%.
39
3RSA
3.1 Uso di RSAEsercizio 3.1 (Cifratura) Alice usa l’algoritmo RSA per ricevere messaggida Bob. Alice sceglie i due numeri primi p = 13 e q = 23. Inoltre sceglieun esponente di cifratura e = 35.
Alice pubblica il prodotto N = pq = 299 e l’esponente di cifratura,mentre tiene segreti i due numeri p e q.
Domande:1. verificare che l’esponente e rispetta i requisiti dell’algoritmo RSA;
2. calcolare l’esponente di decifratura d;
3. cifrare il numero P = 15 e verificare che viene decifrato correttamenteusando l’esponente d calcolato.
Soluzione Innanzitutto calcoliamo φ(N) = (p− 1)(q − 1) = 264. L’espo-nente e deve essere primo rispetto a φ(N):
gcd(35,264) = gcd(5× 7,23 × 3× 11) = 1
L’esponente e è valido, e l’esponente di decifratura risulta:
d = e−1 mod φ(N)d = 35−1 mod 264d = 83
41
3. RSA
L’inverso di 35 si può calcolare sia con l’algoritmo di Euclide esteso,oppure come:
d = 35φ(264)−1 = 35φ(23)φ(3)φ(11)−1 == 35(2−1)22(3−1)(11−1)−1 = 3579 mod 264 = 83 (3.1)
L’elevamento a potenza può essere effettuato con la tecnica delloSquare-&-Multiply.
Dato P = 15, possiamo calcolare:
C = P e mod N = 1535 mod 299 = 189
Decifrando si ha:
P = Cd mod N = 18983 mod 299 = 15
Esercizio 3.2 (Firma digitale RSA) Alice pubblica i seguenti dati: N =pq = 221 e e = 13. Bob riceve il messaggio P = 65 e la relativa firmadigitale F = 182.
Verificare la firma.
Soluzione La firma è valida se P = F e mod N . Nel nostro caso:
F e mod N = 18213 mod 221 = 65
Esercizio 3.3 Alice pubblica la seguente chiave pubblica RSA: Kpub =(e,n) = (93, 17947).
1. Cifrare il messaggio m = 7 usando l’algoritmo S & M.2. Usando la tecnica di fattorizzazione di Fermat, trovare p, q.3. Usando l’algoritmo di fattorizzazione p − 1 trovare p,q. (Usarea = 100 e B = 3, B = 4).
4. Verificare che n non è primo usando l’algoritmo di Miller-Rabin.5. Calcolare la chiave privata (d,n).
Soluzione Il testo cifrato è c = me mod n = 793 mod 17947. Per usareS & M si parte dalla rappresentazione binaria di 93 = 1011101.
1 70 72 = 491 492 × 7 = 16807 = −11401 11402 × 7 = 16018 = −19291 19292 × 7 = 61900 61902 = 17202 = −7451 7452 = 8623
Quindi c = 8623.
42
3.1. Uso di RSA
Fattorizzazione di Fermat Per la fattorizzazione di Fermat si parteconsiderando che:
t = p+ q
2 '√n = 133,96
Ipotizziamo t = 134, da cui
s2 = t2 − n = 1342 − 17947 = 9 = 32
Scriviamo le equazioni:
t = p+ q
2 = 134
s = p− q2 = 3
Da cui si ottiene p = 137, q = 131.
Fattorizzazione p−1 Partiamo da a = 100 e calcoliamo la successioneb1, b2, . . . :
b1 = a = 100b2 = b2
1 mod n = 10000b3 = b2
2 mod n = 15754b4 = b3
3 mod n = 12057
Per b3 otteniamo che gcd(b3 − 1,n) = gcd(15753, 17947) = 1, infatti:
gcd(15753, 17947) = gcd(17947 mod 15753, 17947) = gcd(2194, 17947) = · · · = 1
Invece, per b4 otteniamo gcd(b4 − 1,n) = 137.
Miller-Rabin Scegliamo a = 2.
n− 1 = 17946 = 2× 8973
Da cui k = 1, m = 8973. Calcoliamo
b0 = am mod n = 28973 mod n = 3545
per cui il numero è composto.Per trovare la chiave privata occorre calcolare
d = e−1 mod φ(n) = e−1 mod (p−1)(q−1) = 93−1 mod 17680 = 12357
43
3. RSA
3.2 Fattorizzazione3.2.1 Fattorizzazione di FermatEsercizio 3.4 Alice pubblica i seguenti dati: N = 6557, e = 131. Trovarel’esponente di decifratura d.
Soluzione Assumendo p > q possiamo sempre scrivere che:
N = t2 − s2 =(p+ q
2
)2−(p− q
2
)2
La fattorizzazione di Fermat è efficiente se p ' q. In questo caso si hat '√n e s ' 0.
Proviamo nell’ordine tutti i numeri interi t >√N e calcoliamo:
s2 = t2 −N
Procediamo finché s2 non è un quadrato perfetto.Nel caso in esame deve essere t > 80,9.Proviamo t = 81. Per t = 81 si ha s2 = 6561− 6557 = 4. Quindi:
p+ q = 162p− q = 4
Otteniamo p = 83 e q = 79.L’esponente di decifratura sarà:
d = e−1 mod φ(N) = 131−1 mod (p− 1)(q − 1) = 131−1 mod 6396
L’inverso di 131 modulo 6478 si trova usando l’algoritmo di Euclideesteso:
r q s t6396 − 1 0131 48 0 1108 1 1 −4823 4 −1 4916 1 5 −2447 2 −6 2932 3 17 −8301 2 −57 27830 − 131 −6396
L’inverso di 131 è d = 2783 (mod 6369).
44
3.2. Fattorizzazione
3.2.2 Algoritmo p – 1Si supponga di voler fattorizzare n. Si scelgano un intero a > 1 ad
esempio a = 2 e un limite B.Si calcolino b = aB! mod n e d = gcd(b − 1,n). Il risultato d è un
fattore di n; l’algoritmo ha successo e abbiamo un fattore non banale sed 6= 1 o d 6= n.
Esercizio 3.5 Fattorizzare il numero 1001, usando la base a = 2.
Soluzione Fissiamo B = 3. Allora:b = aB! mod n = 23! mod 1001 = 26 mod 1001 = 64d = gcd(b− 1,n) = gcd(63,1001) = 7
Quindi 7 è un fattore. Infatti 1001/7 = 143. Poiché 143 non è primo,occorre procedere nella fattorizzazione.
Proviamo a incrementare B.b = 24! mod 143 = 644 mod 143 = 27d = gcd(26,143) = 13
Quindi 13 è un altro fattore. Concludiamo che:1001 = 7× 11× 13
3.2.3 Setaccio quadratico semplificatoSupponiamo di avere una relazione del tipo:
x2 ≡ y2 (mod n) x 6≡ ±y (mod n) (3.2)Allora gcd(x− y,n) è un fattore non banale di n.
Esercizio 3.6 Fattorizzare 1001.
Soluzione La parte difficile è trovare delle relazioni tipo la (3.2). Ge-neralmente si parte da un insieme di interi vicini a
√kn, si elevano al
quadrato modulo n e si fattorizzano. Il procedimento è utile se questafattorizzazione è facile.
Ad esempio otteniamo le seguenti relazioni352 mod 1001 = 224 = 25 × 7362 mod 1001 = 295 = 5× 59372 mod 1001 = 368 = 24 × 23452 mod 1001 = 23462 mod 1001 = 114 = 2× 3× 19472 mod 1001 = 207 = 3× 3× 23
45
3. RSA
Selezioniamo poi dei gruppi di relazioni in modo da avere i fattori adestra un numero pari di volte.
Ad esempio abbiamo:
(37× 45)2 ≡ 24 × 232 ≡ (22 × 23)2 (mod 1001) (3.3)(47× 45)2 ≡ (3× 23)2 (mod 1001) (3.4)
Alcune di queste relazioni daranno luogo ad una fattorizzazione banale,altre no. Ad esempio la (3.3) dà luogo a:
gcd(37× 45− 22 × 23, 1001) = gcd(1665− 92,1001) = 143 = 11× 13
Mentre la (3.4) dà luogo a:
gcd(47× 45− 3× 23) = gcd(2115− 69,1001) = 11
Quindi 1001 = 7× 11× 13.
46
4Residui quadratici
4.1 Teorema cinese del restoEsercizio 4.1 Trovare le soluzioni della seguente congruenza:
3x ≡ 4 (mod 7)
Soluzione Si consideri che
3−1 · 3x ≡ 3−1 · 4 (mod 7)
Usando l’algoritmo di Euclide possiamo ricavare che
3 · 5 = 15 = 7 · 2 + 1 ≡ 1 (mod 7)
Quindi l’inverso di 3 è 5. Possiamo scrivere:
5 · 3x ≡ 5 · 4 (mod 7)x ≡ 20 mod 7 ≡ 6 (mod 7)
La soluzione è quindi:
x = 6 + 7k, ∀k ∈ Z
Esercizio 4.2 Trovare le soluzioni del seguente sistema di congruenze:x ≡ 2 (mod 3)x ≡ 3 (mod 5)x ≡ 4 (mod 11)x ≡ 5 (mod 16)
47
4. Residui quadratici
Soluzione Il teorema cinese del resto garantisce che la soluzione esiste semi = {3, 5, 11, 16} sono primi tra loro a coppie. È facile verificare che 3, 5e 11 sono primi e che 16 = 24, quindi non esistono fattori in comune.
Si definiscono quindi:
ai = {2, 3, 4, 5}mi = {3, 5, 11, 16}
M =4∏i=1
mi = 3 · 5 · 11 · 16 = 2640
zi = M
mi
yi = z−1i (mod mi)
x =4∑i=1
aiyizi mod M
Nel caso in esame:i ai mi zi yi1 2 3 880 12 3 5 528 23 4 11 240 54 5 16 165 13
Quindi:
x = 2 · 1 · 880 + 3 · 2 · 528 + 4 · 5 · 240 + 5 · 13 · 165 ≡ 1973 (mod 2640)
4.2 Residui quadraticiEsercizio 4.3 Calcolare
(91167
).
Soluzione Osserviamo che 167 è primo, quindi si può usare la definizionedi simbolo di Legendre:(
a
p
)=+1 se a è un quadrato (mod p)−1 altrimenti
Inoltre a è un quadrato modp se e solo se:
ap−1
2 ≡ 1 (mod p)
Nel nostro caso dobbiamo calcolare (9183 mod 167). Per svolgere ilcalcolo usiamo l’algoritmo Square-and-Multiply.
48
4.2. Residui quadratici
i ci z (mod 167)6 1 12 × 91 = 915 0 912 = 984 1 982 × 91 = 533 0 532 = 1372 0 1372 = 651 1 652 × 91 = 410 1 412 × 91 = 166
Quindi9183 ≡ 166 ≡ −1 (mod 167)
allora 91 non è un quadrato e il simbolo di Legendre vale −1:( 91167
)= −1
Esercizio 4.4 Calcolare(
91167
)usando la legge di reciprocità quadratica.
Soluzione Osserviamo che 91 = 7× 13, quindi:( 91167
)=( 7
167
)( 13167
)La legge di reciprocità dice che:
(m
n
)=−
(nm
)se m ≡ n ≡ 3 (mod 4)(
nm
)altrimenti
Nel nostro caso:
167 mod 4 = 37 mod 4 = 3
13 mod 4 = 1
Quindi: ( 91167
)= −
(1677
)(16713
)Applichiamo la proprietà per cui, se a ≡ b (mod p) e gcd(a,p) = 1:(
a
p
)=(b
p
)
e otteniamo ( 91167
)= −
(67
)(1113
)
49
4. Residui quadratici
Osserviamo che 6 ≡ −1 (mod 7), quindi:(67
)=(−1
7
)= (−1)(7−1)/2 = (−1)3 = −1
Osserviamo che 11 ≡ −2 (mod 13) e che 13 ≡ 5 (mod 8), quindi:(1113
)=(−1
13
)( 213
)= (−1)(13−1)/2 · (−1) = −1
Quindi il risultato è:( 91167
)= −(−1)(−1) = −1
Esercizio 4.5 Valutare il simbolo di Legendre(
18018191
)fattorizzando solo i
numeri pari.
Soluzione Calcoliamo innanzitutto gcd(1801,8191).
j rj0 8191 –1 1801 –2 987 8191 = 4 · 1801 + 9873 814 1801 = 1 · 987 + 8144 173 987 = 1 · 814 + 1735 122 814 = 4 · 173 + 1226 51 173 = 1 · 122 + 517 20 122 = 2 · 51 + 208 11 51 = 2 · 20 + 119 9 20 = 1 · 11 + 910 2 11 = 1 · 9 + 211 1 9 = 4 · 2 + 112 0 2 = 2 · 1 + 1
Osserviamo che:
1801 mod 4 = 18191 mod 4 = 3
8191 mod 1801 = 987gcd(8191,1801) = 1
Applicando la legge di reciprocità:(18018191
)=(8191
1801
)=( 987
1801
)
50
4.2. Residui quadratici
Osserviamo ancora che:
1801 mod 4 = 1987 mod 4 = 3
1801 mod 987 = 814gcd(987,1801) = gcd(8191 mod 1801,1801) = 1
987 mod 8 = 3
Quindi: ( 9871801
)=(814
987
)=( 2
987
)(407987
)= −
(407987
)Osserviamo ancora che:
407 mod 4 = 3987 mod 4 = 3
987 mod 407 = 173gcd(407,987) = 1
Quindi:−(407
987
)=(173
407
)Osserviamo ancora che:
407 mod 4 = 3173 mod 4 = 1
987 mod 407 = 61gcd(407,173) = 1
Quindi: (173407
)=( 61
173
)Osserviamo ancora che:
61 mod 4 = 1173 mod 4 = 1
173 mod 61 = 51gcd(61,173) = 1
Quindi: ( 61173
)=(51
61
)
51
4. Residui quadratici
Osserviamo ancora che:61 mod 4 = 151 mod 4 = 3
61 mod 51 = 10gcd(61,51) = 1
51 mod 8 = 3Quindi: (51
61
)=( 2
51
)( 551
)= −
( 551
)Osserviamo ancora che:
5 mod 4 = 151 mod 4 = 351 mod 5 = 1gcd(5,51) = 1
Quindi:−( 5
51
)= −
(15
)= −1
4.2.1 Test di Solovay-StrassenDato un n candidato primo, scegliamo un insieme di basi 1 < ai < n−1,
se esiste un ai tale che: (a
n
)6≡ a
n−12 (mod n)
possiamo dire con certezza che n non è primo. Se invece non troviamoquesto ai dobbiamo concludere che n probabilmente è primo.
Esercizio 4.6 Verificare se il numero 17 è primo usando il test di Solovay-Strassen sulle basi 2 e 3.
Soluzione Proviamo la base 2.( 217
)= 1 Il risultato è noto perché 17 ≡ 1 (mod 8)
28 mod 17 = 256 mod 17 = 1Proviamo la base 3.( 3
17
)=(17
3
)=(2
3
)= −1
38 mod 17 = 6561 mod 17 = 16 = −1Il numero è probabilmente primo.
52
4.3. Estrazione di radici
Esercizio 4.7 Verificare se il numero 341 è primo usando il test di Solovay-Strassen sulle basi 2 e 3.
Soluzione Proviamo la base 2.( 2341
)= −1 Il risultato è noto perché 341 ≡ 5 (mod 8)
2170 mod 341 = 1
Il numero è composto.
4.3 Estrazione di radiciEsercizio 4.8 Calcolare x tale che x2 ≡ 76 (mod 167).
Soluzione Prima di tutto verifichiamo se l’equazione ha soluzione. Sicco-me 167 è primo, 76 è un quadrato se
76 167−12 = 7683 ≡ 1 (mod 167)
Per verificare che 7683 mod 167 = 1 si può usare l’algoritmo Square-and-Multiply:
i ci z (mod 167)6 1 12 × 76 = 765 0 762 = 984 1 982 × 76 = 1143 0 1142 = 1372 0 1372 = 651 1 652 × 76 = 1260 1 1262 × 76 = 1
Siccome 167 ≡ 3 (mod 4), si può usare la formula veloce per estrarrele radici:
x = ±76 167+14 mod 167 = ±7642 mod 167
Anche qui possiamo usare l’algoritmo Square-and-Multiply:
i ci z (mod 167)5 1 12 × 76 = 764 0 762 = 983 1 982 × 76 = 1142 0 1142 = 1371 1 1372 × 76 = 970 0 972 = 57
53
4. Residui quadratici
Come è facile verificare, x = ±57.
Esercizio 4.9 Calcolare x tale che x2 ≡ 100 (mod 231).
Soluzione Poiché 231 = 3× 7× 11, il problema si riconduce a trovare lasoluzione del sistema:
x2 ≡ 100 ≡ 1 (mod 3)x2 ≡ 100 ≡ 2 (mod 7)x2 ≡ 100 ≡ 1 (mod 11)
Per verificare che la soluzione esista, calcoliamo i numeri di Legendre:(13
)= 1(2
7
)= 2 7−1
2 mod 7 = 1(27
)= 1
Quindi la soluzione esiste. Osservando poi che 3 ≡ 7 ≡ 11 (mod 4), sipuò usare la formula per calcolare velocemente le radici:
x ≡ ±1 (mod 3)x ≡ ±2 7+1
4 ≡ 4 (mod 7)x ≡ ±1 (mod 11)
Il teorema del resto cinese ci permette di trovare la x cercata. Definia-mo:
z1 = 231/3 = 77 y1 ≡ 77−1 ≡ 2−1 ≡ 2 (mod 3)z2 = 231/7 = 33 y2 ≡ 33−1 ≡ 5−1 ≡ 3 (mod 7)z3 = 231/11 = 21 y3 ≡ 21−1 ≡ 10−1 ≡ 10 (mod 11)
Per trovare gli inversi possiamo osservare che z1 ≡ −1 (mod 3) ez3 ≡ −1 (mod 11), quindi y1 e y3 sono gli inversi di se stessi. Per y2 usarel’algoritmo di Euclide esteso:
ri qi si ti7 −− 1 05 1 0 12 2 1 −11 2 −2 3
54
4.4. Crittosistema di Rabin
Combinando le soluzioni negli 23 = 8 casi otteniamo le 8 radici:
x ≡ 1 · 77 · 2 + 4 · 33 · 3 + 1 · 21 · 10 ≡ 67 (mod 231)x ≡ −1 · 77 · 2 + 4 · 33 · 3 + 1 · 21 · 10 ≡ 221 (mod 231)x ≡ 1 · 77 · 2− 4 · 33 · 3 + 1 · 21 · 10 ≡ 199 (mod 231)x ≡ −1 · 77 · 2− 4 · 33 · 3 + 1 · 21 · 10 ≡ 122 (mod 231)x ≡ 1 · 77 · 2 + 4 · 33 · 3− 1 · 21 · 10 ≡ 109 (mod 231)x ≡ −1 · 77 · 2 + 4 · 33 · 3− 1 · 21 · 10 ≡ 32 (mod 231)x ≡ 1 · 77 · 2− 4 · 33 · 3− 1 · 21 · 10 ≡ 10 (mod 231)x ≡ −1 · 77 · 2− 4 · 33 · 3− 1 · 21 · 10 ≡ 164 (mod 231)
4.4 Crittosistema di RabinEsercizio 4.10 (Crittosistema di Rabin) Si consideri un testo compostodalle sole 26 lettere maiuscole codificate con numeri interi progressivi. Siconsideri ‘A’ = 65, ‘B’ = 66 e così via fino a ‘Z’ = 90.
Alice e Bob comunicano usando un crittosistema di Rabin. La chiavepubblica di Alice è
m = p · q = 209
La chiave privata (ovvero la coppia p,q) è tenuta segreta.Bob cifra, lettera per lettera, il seguente messaggio: “WADE” e lo
invia ad Alice. Eve, che conosce le prime due lettere del messaggio inchiaro ma ignora le ultime due, ottiene una copia del messaggio cifrato.
1. Cifrare il messaggio2. Spiegare come può Eve ricavare la chiave privata di Alice.3. Decifrare la parte restante del messaggio.
Soluzione 1. Il messaggio in chiaro P è la sequenza:
P =(87 65 68 69
)Il messaggio cifrato M si ottiene elevando al quadrato modulo m.
Ci = P 2i mod 209
C =(45 45 26 163
)
55
4. Residui quadratici
2. Ricordiamo che ad ogniMi corrispondono 4 possibili Pi. Supponiamoche le quattro radici di Mi siano ±r e ±s, allora gcd(r + s,pq) saràuguale a p oppure a q. Nel caso in esame notiamo che i numeri 87 e65 vengono entrambi cifrati con 45. Calcoliamo quindi il massimocomune denominatore:
gcd(87 + 65, 209) = gcd(152, 209) = 19.
Per cui i due fattori di m sono q = 19 e p = 209/19 = 11.3. Per decifrare sfruttiamo il Teorema Cinese del Resto. Partiamo
da M3 = 26. Dobbiamo prima risolvere le equazioni modulo p e q.Definiamo m1 = p e m2 = q. Dopodiché risolviamo il sistema diequazioni:
a2i = 26 mod mi
{a2
1 = 26 mod 11 = 4a2
2 = 26 mod 19 = 7
Usando le regole per risolvere i quadrati modulo k con k ≡ 3 (mod 4)otteniamo:
{a1 = 4 11+1
4 mod 11 = 43 mod 11 = 9a2 = 7 19+1
4 mod 19 = 75 mod 19 = 11
Si verifica facilmente che le radici cercate esistono e coincidonocon i valori trovati. Ora bisogna combinare tra loro le soluzioni.L’algoritmo prevede che si calcoli:
zi = 209/mi
yi = z−1i mod mi
x =∑i
(±ai)yizi mod 209
Calcoliamo:
z1 = 19z2 = 11
y1 = 19−1 mod 11y2 = 11−1 mod 19
56
4.4. Crittosistema di Rabin
Per trovare y1 e y2 possiamo usare il teorema di euclide esteso oppureil teorema di Fermat. Risulta:
y1 = 7 mod 11 = 7y2 = 7 mod 19 = 7
x =
9 · 19 · 7 + 11 · 11 · 7 mod 209 = 1639 · 19 · 7− 11 · 11 · 7 mod 209 = 141−9 · 19 · 7 + 11 · 11 · 7 mod 209 = 68−9 · 19 · 7− 11 · 11 · 7 mod 209 = 46
Delle quattro soluzioni ottenute teniamo solo x = 68 = ‘D’ perché lealtre soluzioni non corrispondono a lettere del nostro alfabeto.Per M4 = 163 procediamo allo stesso modo, ottenendo x = 69 = ‘E’.
57
5Logaritmi discreti
5.1 Logaritmi discreti5.1.1 Pohlig-HellmanEsercizio 5.1 Sapendo che 4 ≡ 3x (mod 7), calcolare x.
Soluzione L’algoritmo di Pohlig-Hellman è utile se p− 1 è composto dafattori primi piccoli. Nel nostro caso p− 1 = 6 = 3× 2.
Il nostro scopo è arrivare a scrivere un sistema di equazioni del tipo:
x mod 2 = . . .
x mod 3 = . . .
Troviamo prima x mod 2. Sappiamo che x0 = x mod 2 è soluzionedella equazione:
β(p−1)/q ≡ αx0(p−1)/q (mod p)con β = 4, α = 3, p = 7, q = 2. Inoltre sappiamo che 0 ≤ x0 ≤ q − 1.
Quindi dobbiamo trovare la soluzione della equazione:
43 ≡ 33x0 (mod 7)1 ≡ 33x0 (mod 7)x0 = 0
A questo punto troviamo x0 = x mod 3, soluzione di:
42 ≡ 32x0 (mod 7)2 ≡ 32x0 (mod 7)
59
5. Logaritmi discreti
Provando nell’ordine x0 = 0,1,2, troviamo che x0 = 1.Il sistema di equazioni da risolvere usando il teorema del resto cinese
sarà:
x mod 2 ≡ 0x mod 3 ≡ 1
che dà x = 4.
Esercizio 5.2 Sapendo che 5 ≡ 7x (mod 13) calcolare x.
Soluzione Il nostro obiettivo è un sistema del tipo:
x mod 4 = . . .
x mod 3 = . . .
Calcoliamo prima il valore di x mod 4 = x0 + 2x1.Il termine x0 è soluzione della equazione:
β(p−1)/q ≡ αx0(p−1)/q (mod 13)56 ≡ 76x0 (mod 13)12 ≡ 76x0 (mod 13)
che ha soluzione x0 = 1.Noto x0 possiamo calcolare:
β1 ≡ βα−x0 ≡ 5× 7−1 ≡ 5× 2 ≡ 10 mod 13 (5.1)
Il termine x1 è soluzione della equazione:
β(p−1)/q2
1 ≡ αx1(p−1)/q (mod 13)103 ≡ 76x1 (mod 13)12 ≡ 76x1 (mod 13)
che ha soluzione x1 = 1.Quindi:
x mod 4 = 1 + 2 = 3Per calcolare x mod 3 = x0, risolviamo l’equazione:
54 ≡ 74x0 (mod 13)1 ≡ 74x0
60
5.1. Logaritmi discreti
che ha soluzione x0 = 0.Il sistema da risolvere diventa:
x mod 4 = 3x mod 3 = 0
Che ha soluzione x = 3.
5.1.2 Baby step, giant stepEsercizio 5.3 Sapendo che 11x ≡ 5 (mod 31). Trovare x.
Soluzione Scegliamo N = d√
31e+ 1 = 7. Calcoliamo
α−N ≡ 11−7 ≡ (11−1)7 ≡ 177 ≡ 12 (mod 31)
e costruiamo la tabella:j,k αj ≡ 11j βα−Nk ≡ 5× 12k
0 1 5× 1 ≡ 51 11 5× 12 ≡ 292 11× 11 ≡ 28 29× 12 ≡ 73 28× 11 ≡ 29 7× 12 ≡ 226 . . . . . .
Scopriamo che113 ≡ 5× 11−7
Quindi x = 10.
Esercizio 5.4 Sapendo che 5x ≡ 27 (mod 103). Trovare x.
Soluzione Scegliamo N = d√
103e+ 1 = 12 e calcoliamo:
α−N ≡ 5−12 ≡ (5−1)12 ≡ 6212 ≡ 100 (mod 103)
Costruiamo la tabella:j,k αj ≡ 5j βα−Nk ≡ 27× 100k
0 1 271 5 27× 100 ≡ 222 5× 5 ≡ 25 22× 100 ≡ 373 25× 5 ≡ 22 . . .
Scopriamo che:
53 ≡ 27× 5−12×1
53+12 ≡ 27
Quindi x = 15.
61
5. Logaritmi discreti
5.1.3 Index CalculusEsercizio 5.5 Sapendo che 5x ≡ 27 (mod 103). Trovare x.
Soluzione La prima fase è la precomputation; definiamo un bound B ecostruiamo una base di fattori composta da tutti i primi minori di B. Adesempio scegliamo B = 8 e la base risulta composta da: {2, 3, 5, 7}.
A questo punto calcoliamo un po’ di potenze di 5 e vediamo se possonoessere espresse come prodotto di elementi della base di fattori:
51 ≡ 5 (mod 103) 1 ≡ L5(5) (mod 102) (5.2)52 ≡ 25 ≡ 52 2 ≡ 2L5(5) (5.3)
53 ≡ 22 ≡ 2× 11 (5.4)54 ≡ 7 4 ≡ L5(7) (5.5)
55 ≡ 35 ≡ 5× 7 5 ≡ L5(5) + L5(7) (5.6)56 ≡ 72 ≡ 23 × 32 6 = 3L5(2) + 2L5(3) (5.7)
58 ≡ 49 ≡ 72 8 = 2L5(7) (5.8)59 ≡ 39 ≡ 13× 3 (5.9)
510 ≡ 92 ≡ 22 × 23 (5.10)511 ≡ 48 = 24 × 3 11 = 4L5(2) + L5(3) (5.11)
Abbiamo abbastanza equazioni per risolvere il sistema lineare nelleincognite L5(i). Troviamo subito che:
L5(5) = 1L5(7) = 4
Sottraendo la (5.7) da due volte la (5.11) otteniamo che:
16 ≡ 5L5(2) (mod 102)L5(2) ≡ 16× 5−1 ≡ 16× 41 ≡ 44 (mod 102)
Sostituendo nella (5.7) otteniamo che:
2L5(3) ≡ 78 (mod 102)L5(3) ≡ 39 (mod 51)
Abbiamo due possibili soluzioni per L5(3), e cioè L5(3) = 39 oppureL5(3) = 39 + 51 = 90. Da una verifica scopriamo che solo la primasoluzione è corretta.
Nella seconda fase calcoliamo 27×5r per un po’ di r finché non troviamoun numero prodotto dei fattori nella base già definita. Proviamo r = 1 eotteniamo:
27× 5 ≡ 32 ≡ 25 (mod 103)
62
5.2. Applicazioni dei logaritmi discreti
Abbiamo trovato subito una equazione che ci permette di scrivere:
L5(27) + L5(5) ≡ 5L5(2) (mod 102)L5(27) ≡ 5× 44− 1 ≡ 15 (mod 102)
La soluzione è quindi x = 15.
5.2 Applicazioni dei logaritmi discreti5.2.1 Scambio di chiavi di Diffie-HellmanEsercizio 5.6 Alice e Bob usano il protocollo di Diffie-Hellman per loscambio delle chiavi e pubblicano i numeri α = 45 e p = 113. Eveintercetta il messaggio da Alice a Bob:
A→ B. αx ≡ 29 (mod p)
e il messaggio da Bob a Alice:
B → A. αy ≡ 10 (mod p)
Domande:1. usando un algoritmo per il calcolo del logaritmo discreto, calcolarex;
2. calcolare la chiave K.
Soluzione Dobbiamo risolvere l’equazione:
45x ≡ 29 (mod 113)
Poiché p − 1 = 112 = 24 × 7 possiamo usare l’algoritmo di Pohlig-Hellman.
Scopriamo che x = 5.A questo punto calcoliamo:
K = 105 mod 113 = 108
5.2.2 Crittosistema di ElGamalEsercizio 5.7 Alice usa un crittosistema di ElGamal eK(x,k) = (r,t) con:
r = αk mod p (5.12)t = xβk mod p (5.13)
63
5. Logaritmi discreti
Alice sceglie un valore a che tiene segreto e Alice pubblica i seguenti dati:p = 107, α = 8, β = αa mod p = 30.
Bob invia ad Alice il seguente messaggio cifrato con modo di operazioneECB in cui si è erroneamente usato lo stesso nonce k per tutte le operazionidi cifratura.
(84,15)(84,68)Eve sa che il testo in chiaro del primo blocco cifrato è il numero x1 = 45.
Calcolare:1. il valore del testo in chiaro relativo al secondo blocco;2. il testo cifrato corrispondente al testo in chiaro x3 = 88;3. sapendo che a = 4, scrivere le operazioni che compie Alice per
decifrare quest’ultimo blocco ricevuto.
Soluzione Eve sa che xβk ≡ t, quindi:
45βk ≡ 15 (mod 107)x2β
k ≡ 68 (mod 107)
Da cui si ottiene facilmente che:
βk ≡ 15× 45−1 ≡ 15× 39 (mod 107) = 50 (mod 107)x2 ≡ 45× 68× 15−1 ≡ 45× 68× 50 ≡ 97 (mod 107)
Per cifrare x3 = 88 usando lo stesso k di prima calcoliamo:
r = αk mod p = 84t = x3β
k mod p = 88× 36 mod 107 = 65
L’operazione di decifratura è:
x = tr−a mod p = 65× 84−4 mod 107 = 65× 934 mod 107 = 88
5.2.3 Firma digitale di ElGamalEsercizio 5.8 Alice usa un sistema di firma digitale di ElGamal. Alicesceglie un numero segreto a e pubblica i numeri p = 313, α = 55, β =αa mod p = 28. Successivamente Alice firma i due documenti m1 =45,m2 = 255. Erroneamente Alice sceglie lo stesso nonce per entrambi imessaggi e calcola:
r1 = r2 = αk mod p = 146s1 = k−1(m1 − ar1) mod (p− 1) = 5s2 = k−1(m2 − ar2) mod (p− 1) = 35
64
5.2. Applicazioni dei logaritmi discreti
Quindi pubblica le firme:
(m1,r1,s1) = (45,146,5)(m2,r2,s2) = (255,146,35)
1. Verificare la firma del messaggio m1.2. Sfruttando il riuso di k, ottenere la chiave privata a.
Soluzione La verifica della firma messaggio m1 si ottiene calcolando:
v = βrrs1 mod p = 28146 × 1465 mod 313 = 72× 203 mod 313 = 218w = αm mod p = 5545 mod 313 = 218
Siccome v = w la firma è valida.Eve sa che:
s1k −m1 ≡ −ar ≡ s2k −m2 (mod p− 1)(s1 − s2)k ≡ m1 −m1 (mod p− 1)
Nel nostro caso:282k ≡ 102 (mod 312)
Siccome gcd(312,282) = 6 scriveremo:
47k ≡ 17 (mod 52)k ≡ 31× 17 ≡ 7 (mod 52)
Le possibili soluzioni per k sono:
k = 7, 59, 111, 163, 215, 267
Calcolando r1 per questi candidati valori di k si ottiene la soluzioencorretta k = 7.
Noto k Eve risolve l’equazione:
ar ≡ m1 − ks1 (mod p− 1)146a ≡ 45− 7× 5 ≡ 10 (mod 312)73a ≡ 5 (mod 156)
Da cui si ottengono due possibili valori a = 77, a = 233. Calcolando βsi verifica che la soluzione corretta è a = 77.
65
6Curve Ellittiche
6.1 FattorizzazioneEsercizio 6.1 Fattorizzare il numero n = 35 usando le curve ellittiche.
Soluzione Occorre definire una curva E : y2 ≡ x3 + bx+ c (mod n) e unpunto P ∈ E.
Scegliamo arbitrariamente un punto P = (1,1) e un valore b = 4,imponendo il passaggi di E per P otteniamo:
12 ≡ 1 + 4 + c (mod 35)c ≡ −4 (mod 35)
quindi:E : y2 ≡ x3 + 4x− 4 (mod 35)
Verifichiamo se la curva è singolare:
4b3 + 27c2 ≡ 25 6≡ 0 (mod 35)
Partiamo da P = (1,1) e calcoliamo 2!P , 3!P . . . .Calcoliamo R = 2!P = 2P . Le coordinate del punto sono:
m ≡ (3x21 + b)(2y1)−1 ≡ 7 · 2−1 ≡ 7 · 18 ≡ 21
x3 ≡ m2 − 2x1 ≡ 212 − 2 ≡ 19y3 ≡ m(x1 − x3)− y1 ≡ 21(−18)− 1 ≡ 6
Quindi R = 2!P = (19,6).
67
6. Curve Ellittiche
Calcoliamo S = 3!P = 3R = 2R +R. Iniziamo con T = 2R = 2(19,6):
m ≡ (3 · 192 + 4)(12)−1 ≡ 2 · 3 ≡ 6xT ≡ 62 − 2 · 19 ≡ 33yT ≡ 6(19− 33)− 6 ≡ 15
Quindi T = (33,15).Calcoliamo S = T +R = (33,15) + (19,6).
m ≡ (y2 − y1)(x2 − x1)−1 ≡ (−9) · (−14)−1
Calcolando l’inverso di −14 ≡ 21 scopriamo che gcd(35,21) = 7, che èun fattore.
6.2 Rappresentazione di plaintextEsercizio 6.2 Si vogliono rappresentare la cifre da 0 a 9 come punti dellacurva ellittica E : y2 ≡ x3 + 2x+ 1 (mod 31) usando il metodo di Koblitzcon K = 3. Scegliere un punto per rappresentare il messaggio m = 2.
Soluzione I messaggi m sono rappresentati come punti con ascissa x =mK + j dove 0 ≤ j < K è scelto in modo che la curva abbia un punto incorrispondenza di x.
Nal caso m = 2 dobbiamo provare x = 6, x = 7, x = 8.Se x = 6, otteniamo y2 ≡ 12 (mod 31). Occorre verificare se 12 è un
residuo quadratico mod31:
(1231
)=( 2
31
)2 ( 331
)= −
(13
)= −1
Proviamo con x = 7, otteniamo y2 ≡ 17. Verifichiamo se è un residuo:(17
31
)=(14
17
)=( 2
17
)( 717
)=(3
7
)= −
(13
)= −1
Proviamo con x = 8, otteniamo y2 ≡ 2, che è un residuo. Inoltre:
y = 232/4 mod 31 = 8
Il punto P = (8,8) rappresenta il messaggio m = 2.
68
6.3. Logaritmo discreto
6.3 Logaritmo discretoEsercizio 6.3 Si consideri la curva E di equazione: y2 ≡ x3 + 3 (mod 31).La curva E ha 43 punti.
Sia A = (1,2) e B = (17,24). Calcolare il numero a tale che B = aA.
Soluzione Usiamo la tecnica baby step, giant step. Scegliamo N =d√
43e = 7. Calcoliamo
−NA = 7(−A) = 7(1,− 2) = (25,2)
e costruiamo la tabella:
j,k jA B −NkA = B + k(−NA)0 O (17,24)1 (1,2) (17,24) + (25,2) = (14,22)2 (1,2) + (1,2) = (16,10) (14,22) + (25,2) = (24,30)3 (16,10) + (1,2) = (22,24) (24,30) + (25,2) = (22,7)4 (22,24) + (1,2) = (24,30) . . .5 . . .
Scopriamo che 4A = B − 7 · 2A, quindi B = (14 + 4)A = 18A, quindia = 18.
Nota: per calcolare 7(1, − 2) possiamo usare la tecnica Double-&-Add:
1 2O + (1,− 2) = (1,− 2)1 2(1,− 2) + (1,− 2) = (16,21) + (1,− 2) = (22,7)1 2(22,7) + (1,− 2) = (5,29) + (1,− 2) = (25,2)
6.4 Diffie-HellmanAlice e Bob scambiano una chiave di sessione usando il protocollo di
Diffie-Hellman. Pubblicano una curva ellittica E : y2 ≡ x3 + 18x + 2(mod 29). Questa curva ha n = 27 punti. Pubblicano anche un puntoP = (4,14).
Alice invia il messaggio A = aP = (7,6) e riceve il messaggio B =bP = (9,9).
1. Verificare che P è un generatore primitivo.2. Calcolare b usando l’algoritmo di Pohlig-Hellman.3. Calcolare la chiave di sessione.
69
6. Curve Ellittiche
Soluzione Il numero di punti n = 27 = 33 non è primo, alcuni elementiavranno ordine 3 oppure 9. Se P è primitivo, ha ordine 27. Quindi27/3P 6≡ O. Nel nostro caso:
9P = 9(4,14) = 23P + P = (10,14)
P è primitivo.Chiamando x = b Dobbiamo risolvere l’equazione β = xα:
(9,9) = x(4,14)
L’algoritmo di Pohlig-Helamn ci permette di calcolare facilmente:
x (mod 27) = x0 + 3x1 + 9x2
Il termine x0 è soluzione dell’equazione:
9(9,9) = 9x0(4,14)(10,14) = x0(10,14)
x0 = 1
Per calcolare il termine successivo occorre calcolare prima β1 = β −x0α = (7,6). Il termine x1 è soluzione della equazione:
3(7,6) = 9x1(4,14)(10,14) = x1(10,14)
x1 = 1
Per l’ultimo termine abbiamo β2 = β1 − 3x1α = O.
O = 9x2(4,14)x2 = 0
Quindi b = x = 1 + 3 = 4.La chiave di sessione è il punto K = bA = 4(7,6) = (3,24).
6.5 Firma DSAEsercizio 6.4 Alice firma usando la tecnica DSA. Pubblica la curva E :y2 ≡ x3 +2x+2 (mod 13) e un basepoint A = (2,1). Alice verifica l’ordinedi A e ottiene q = 5, sceglie un segreto a. Calcola B = aA = (2,− 1) e lopubblica.
70
6.5. Firma DSA
Alice firma il messaggio m = 4, sceglie un k casuale segreto e calcola:
R = kA = (6,− 3) = (xR,yR)s ≡ k−1(m+ axR) ≡ 4 (mod 5)
La firma è: (m,R,s) = (4,(6,− 3),4).Successivamente Alice firma anche il messaggio m = 2 e ottiene:
(m,R,s) = (2,(6,− 3),3).Domande:1. Verificare che l’ordine di A è q.2. Verificare la firma di Alice.3. Sfruttando un errore di Alice, calcolare la chiave segreta a.
Soluzione Calcoliamo:
5A = 22(2,1) + (2,1) = 2(6,− 3) + (2,1) = (2,12) + (2,1) = O
L’ordine di A è 5.Verifichiamo la firma:
u1 ≡ s−1m ≡ 4 · 4 ≡ 1 (mod 5)u2 ≡ s−1xR ≡ 4 · 6 ≡ 4 (mod 5)V = u1A+ u2B = A+ 4B = (2,1) + 4(2,− 1) =
= (2,1) + (2,1) = (6,− 3) = R
La firma è valida.Alice ha usato due volte lo stesso k, possiamo scrivere la seguente
equazione:
s1k −m1 ≡ axR ≡ s2k −m2 (mod q)(s1 − s2)k ≡ m1 −m2 (mod q)
k = 2
A questo punto sostituiamo il valore di k nella equazione sk−m ≡ axRe otteniamo:
a ≡ x−1R (sk −m) (mod q)
a ≡ 6−1(4 · 2− 4) ≡ 4 (mod 5)
Esercizio 6.5 Alice usa un sistema di firma DSA. Pubblica la curva diequazione:
E : y2 ≡ x3 + 3 mod 31;la curva ha q = 43 punti. Alice sceglie un punto A = (11,1) e un segretoa = 7, quindi pubblica B = aA. Quindi firma un messaggio m = 10usando il nonce k = 17.
71
6. Curve Ellittiche
1. Verificare se P rispetta le condizioni per la firma DSA.2. Calcolare B.3. Firmare il messaggio m.4. Verificare la firma.
Soluzione L’ordine di P deve essere primo. In questo caso il numero dipunti è primo, quindi tutti i punti hanno ordine q.
B = aA = 7(11,1) = 8(11,1) + (11,− 1) = (9,22) + (11,− 1) = (27,− 1)
Firma:
R = kA = 17A = 2(9,22) + (11,1) = (22,24)s ≡ k−1(m+ axR) = 38(10 + 7 · 22) = 40 (mod 43)
Verifica:
u1 ≡ s−1m = 14 · 10 = 11 (mod 43)u2 ≡ s−1xR = 14 · 22 = 7 (mod 43)V = u1A+ u2B = 11A+ 7B = 8A+ 2A+ A+ 8B −B =
= (9,22) + (6,23) + (11,1) + (8,9) + (27,1) == (23,24) + (26,8) + (27,1) = (22,24)
Siccome V = R, la firma è verificata.
6.6 Firma di ElGamalEsercizio 6.6 Alice usa il seguente sistema di firma di ElGamal su curveellittiche. Alice sceglie la curva:
E : y2 ≡ x3 + 3 (mod 31)
Il numero p = 31 è primo. Quindi Alice calcola il numero di punti nche appartengono alla curva e ottiene n = 43. Sulla curva E sceglie ilpunto A = (1,2) e il numero a = 18, segreto. Calcola quindi la posizionedel punto B = aA e ottiene:
B = aA = (17,24)
Alice pubblica la curva E, il numero p e le posizione dei punti A e B.Il numero a è tenuto segreto.
72
6.6. Firma di ElGamal
Per firmare un messaggio m, Alice sceglie un numero casuale k ∈ Z∗ncon gcd(k,n) = 1 e calcola:
R = kA = (x,y)s ≡ k−1(m− ax) (mod n)
La verifica della firma da parte di Bob avviene calcolando:
V1 = xB + sR
V2 = mA
Se V1 = V2, il messaggio è autentico.1. Alice vuole inviare il messaggio m = 7 e sceglie il numero casualek = 3. Calcolare la firma di Alice.
2. Verificare la firma.
Soluzione Per calcolare le somme sulla curva E ricordiamo che:
x1 + x2 + x3 = m2
y1 + y3 = m(x1 − x3)
dove m è il coefficiente angolare della retta che unisce i due punti noti. Sei punti sono distinti, allora:
m = (y2 − y1)(x2 − x1)−1 mod 31
altrimentim = (3x2
1)(2y1)−1 mod 31
Alice deve calcolare:
R = kA = 3 · (1,2) = (1,2) + (1,2) + (1,2)
Calcoliamo prima (1,2) + (1,2), otteniamo:
m = 3 · 4−1 mod 31 = 3 · 8 = 24
Per calcolare l’inverso di 25 modulo 31 possiamo usare l’algoritmo diEuclide esteso. Risolvendo le equazioni per x3 e y3 otteniamo:
x3 = m2 − x1 − x2 = 242 − 2 · 1 mod 31 = 16y3 = m(x1 − x3)− y1 = 24(1− 16)− 2 = 10
73
6. Curve Ellittiche
Sommiamo quindi (1,2) + (16,10) e otteniamo:m = 8 · 15−1 mod 31 = 8 · (−2) = 15x3 = 152 − 1− 16 mod 31 = 22y3 = 15 · (1− 22)− 2 mod 31 = 24
Per cui R = (22,24).Calcoliamo s:
s = k−1(m− axR) = 3−1(7− 18 · 22) mod 43 == 29 · (−389) mod 43 = 28
Alice pubblica il messaggio m, e la firma (m,R,s).
V1 = xRB + sR = 22 · (17,24) + 28 · (22,24) = (9,22) + (16,21) = (25,29)V2 = mA = 7 · (1,2) = (25,29)La firma è verificata.
6.7 Crittosistema di ElGamalEsercizio 6.7 Alice usa il crittosistema a chiave pubblica di ElGamal.Pubblica la curva E : y2 ≡ x3 + 2x+ 2 (mod 13) e il punto A = (3,3) diordine 15. Inoltre sceglie un numero segreto a = 7 e pubblica il puntoB = aA. Bob vuole inviare ad Alice un mesaggio codificato con il puntoPm = (8,6).
Domande:1. Calcolare B.2. Cifrare il messaggio usando k = 3.3. Decifrare il messaggio.
Soluzione
B = 7A = 23A− A = 22(4,3)− (3,3) == 2(8,7) + (3,− 3) = (11,9) + (3,− 3) = (11,4)
Bob calcola:Y1 = kA = 3(3,3) = 2(3,3) + (3,3) = (4,3) + (3,3) = (6,− 3)Y2 = Pm + kB = (8,6) + 3(11,4) = (8,6) + (3,− 3) + (11,4) = (4,3)Alice decifra:
Pm = Y2 − aY1 = (4,3)− 7(6,− 3) = (4,3) + 8(6,3) + (6,− 3) == 4(2,1) + (12,8) = (2,12) + (12,8) = (8,6)
74
![[slides] Crittografia Quantistica](https://static.fdocumenti.com/doc/165x107/577dae4a1a28ab223f9040af/slides-crittografia-quantistica.jpg)
