INTRO
La cifratura a chiave pubblica e' una delle piu' usate oggi. Il problema nel cifrare una comunicazione e' di scambiarsi una chiave da usare durante la cifratura. Normalmente viene usato un cipher (metodo di cifratura) a chiave pubblica (come RSA) per scambiare una chiave random che verra' poi usata con un altro cipher (come IDEA) per cifrare il resto della comunicazione. Il motivo perche non si usa RSA durante tutta la cifratura e' perche e' piu' lento degli altri ciphers. RSA e' quindi un buon metodo per scambiarsi chiavi che verrano usate da un altro cipher durante la sessione (scambiarsi un session key).
La cifratura a chiave pubblica consiste di due chiavi: una privata e una pubblica. La chiave pubblica serve per cifrare i messaggi e la chiave privata per decifrarli. Per comunicare, una persona pubblica la sua chiave pubblica in modo che gli altri utenti possono mandare messaggi a questa persona. Notate che gli utenti non possono decifrare cio' che cifrano perche non possiedono la chiave privata. L'utente utilizza la sua chiave privata sul messaggio cifrato e ottiene il messaggio in chiaro. E' fondamentale che non si puo' calcolare la chiave privata da quella pubblica. Infatti e' cosi'. La difficolta nel calcolare la chiave privata e' uguale alla difficolta' di fattorizzare numeri enormi come vedremo a breve.
Operazioni modulari
a e b sono congruenti modulo n se b-a e' divisibile per n. Questo si scrive
a = b(n). Un esempio e' 15 = 5 (5). 5-15 = -10 ed e' divisibile per 5. In
poche parole deve essistere un r in modo che b-a = rn. in Questo esempio r
e' -2: -10 = -2*5. Notate che 0,5,15,20 sono tutti numeri equivalenti modulo
5 (infatti si chiamano classe di equivalenza e si scrive [5]).
Il modulo puo' anche essere visto come il resto di una divisione. Ad
esempio. 13 modulo 10 e' 3. Questo perche 13/10 fa 1 con il resto di 3.
Ecco altri esempi:
5+4 (3) = 0. (3) indica modulo 3. 5+4 = 9. 9/3 = 3 con resto di 0
5*5 (3) = 1. 5*5 = 25 25/3 = 8 con resto di 1.
In C l'operatore di modulo e' %. Quindi int a = (5*5)%3 assegna 1 ad a.
Gruppi formati da operazioni modulari
Un gruppo e' un insieme di elementi che sotto un operazione binaria soddisfano certe condizioni:
Se A e' l'insieme e l'operazione e' * (x,y,z sono in A):
x*yda un altro elemento inA) (gruppo "chiuso")(x*y)*z = x*(y*z)(proprieta' associativa)- c'e' un elemento
IDchex*id = id*x = a - Ogni elemento ha un inverso:
x*x^(-1) = id
Ecco la tabella moltiplicativa di Z/5 (interi modulo 5):
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 2 | 4 | 1 | 4 |
| 3 | 0 | 3 | 1 | 4 | 2 |
| 4 | 0 | 4 | 3 | 2 | 1 |
- ogni elemento
x,yda un altro elemento inZ/5(quindi e' chiuso) - La moltiplicazione e' associativa
- L'elemnto
ide'1. 1*x = x*1 = x - NON ogni lemento ha un inverso (
0non ha un inverso0*x != 1)
Quindi Z/5 non forma un gruppo. Notate che pero' Z/5 senza lo 0 formerebbe
un gruppo (ogni elemento ha un inverso siccome c'e' un 1 (l'id) in ogni
riga). L'inverso di 1 e' 1, di 2 = 3, di 3 = 2, di 4 = 4.
(Z/n)x indica l'insieme di elementi che hanno un inverso sotto
moltiplicazione modulo n. Nel caso di Z/5, gli elementi di (Z/5)x sono
1,2,3,4.
La funzione Euler Totient
La funzione E (Euler Totient) e' definita nel seguente modo:
E(n) = #( (Z/n)x).
Questo singifica che E e' il numero di elementi che hanno un inverso sotto
moltiplicazione modulo n. Nel caso di Z/5 , E = 4 perche gli elementi che
hanno un inverso sono 1,2,3,4 (praticamente gli elementi che formerebbero
un gruppo sotto moltiplicazione modulo 5). Quindi come abbiamo visto E(5) = 4.
Ecco degli esempi:
(Z/2)x = { 1 } quindi E(2) = 1.
(Z/3)x = { 1,2 } quindi E(3) = 2.
(Z/4)x = { 1,3 } quindi E(4) = 2.
L'algoritmo di Euclide
L'algoritmo di Euclide serve per calcolare il fattore maggiore di due
numeri (hcf: highest common factor). Ad esempio hcf(5,6)=1, hcf(4,6)=2,
hcf(3,6)=3. Se hcf(x,y)=1 allora x e y sono coprimi (primi tra di loro).
Se dividiamo x per y avremo x = q*y +r dove q e' il risultato della
divisione e r il resto. hcf(x,y)=hcf(y,r). R e' un numero piu' piccolo
quindi abbiamo semplificato il problema. Procediamo finche r = 0. L'r prima
di r=0 e' il nostro risultato (l'hcf).
Ecco un esempio: hcf(24,356) :
356 = 14x24 + 20 (ora dividiamo 24 per 20)
24 = 1x20 +4 (ora dividiamo 20 per 4)
20 = 5x4 + 0
hcf(24,365) = 4 (l'r prima di r=0).
Ora possiamo procedere al contrario e scrivere l'hcf(x,y) nella forma ax+by
Vediamo:
4 = 24 -1x20
= 24 -1x(356-14x24)
= 15x24 -1x356
a = 15 e b = -1
Se ax+by=1 (se in numeri sono coprimi) allora a e' l'inverso di x modulo y e
b e' l'inverso di y modulo x.
Come calcolare la funzione Euler Totient
Lemma: Un intero x ha un inverso modulo n solo se xn.
Questo e' un modo molto semplice per calcolare la funzione Euler Totient;
ad esempio E(6) 1 ha un inverso (e' coprimo a 6), 2 no perke e' un fattore
di 6, 3 neanche (fattore di 6), 5 e' coprimo a 6 quindi si. Sono 2 quindi i
numeri che hanno un inverso nella moltiplicazione modulo 6. E(6) = 2.
Naturalmente se x e' primo allora e' coprimo a tutti i numeri minori di x. Quindi
E(x) = x-1. Ad esempio E(5) = 5-1 = 4.
Il piccolo teorema di Fermat:
Se p e' un numero primo e a non e' divisibile da p allora a^(p-1)=1(p).
In genere E(p^a) = p^a-p^(a-1) = (p-1)p^(a-1)
ad esempio E(4) = E(2^2) = (2-1)x2^(2-1) = 1x2 = 2
Lemma: se x e y sono coprimi E(xy) = E(x)E(y)
Ad esempio E(6) = E(2x3) = E(2)xE(3) = (2-1)x(3-1) = 1x2 = 2
Come risolvere congruence
Se b e' coprimo ad n, e a e' coprimo a E(n), allora la congruenza x^a = b(n)
ha la soluzione di x = b^(a^-1) (n) dove a^-1 e' l'inverso di a modulo E(n)
Ad esempio: x^53 = 3 (200)
a = 53, b = 3, n = 200
200 = 8x25= 2^3 x 5^2
E(200) = 1x2^2x4x5 = 80
Ora dobbiamo trovare l'inverso di a modulo 80 usando l'algoritmo di euclide
e poi procedendo al contrario per metterlo nella forma 1=ax+by
80 = 1x53 + 27
53 = 1x27 + 26
27 = 1x26 + 1
1 = 27-1x26
= 27-(53-27) = 2x27-53
= 2x(80 - 53) - 53
= 2x80-3x53
L'inverso di 53 (80) e' -3
x= 3^(-3) = 27^-1 (200)
Ora dobbiamo trovare l'inverso di 27 modulo 200
200 = 7x27 + 11
27 = 2x11 +5
11 = 2x5 + 1
1 = 11 -2x5
= 11 -2x(27-2x11) = 5x11-2x27
= 5x(200-7x27) -2x27
= 5x200 - 37x27
-37 e' l'inverso di 27(200)
e quindi:
x = -37 = 163(200)
Cifratura RSA (finalmente)
Ecco come generare le chiavi pubblice e private:
Prima scegliete due numeri primi grandi p e q (di cira 100 cifre l'uno).
Moltiplicateli e ottenete pq. Calcolate E(pq) (che in questo caso e'
(p-1)(q-1) perche sono numeri primi). Poi scegliete un numero a coprimo a
E(pq). Poi trovate l'inverso b di a modulo E(pq). La chiave pubblica e' la
coppia (pq,a) e quella privata (pq,b).
Per cifrare un messaggio M bisogna fare C= M^a(pq). Per decifrare occorre
fare M = C^b(pq).
Se uno ha la chiave pubblica, per calcolare la chiave privata occorre
calcolare E(pq). E quindi occorre fattorizzare pq in p e q. Siccome sono
numeri di 100 cifra ciascuno e' impossibile fattorizzarli in tempi umani.
Ecco un esempio:
p = 3 q q= 11. pq = 33. E(pq) = (3-1)(11-1) = 2x10 = 20. Scegliamo 7 come a.
Quindi (33,7) e' la chiave pubblica. Ora dobbiamo trovare l'inverso di 7 modulo 20:
20 = 2x7 + 6
7 = 1x6 + 1
1 = 7 - 1x6
= 7 - 1x(20-2x7)
= 3x7 - 1x20
3 e' l'inverso di 7 modulo 20. Quindi la chiave privata e' (33,3).
Supponiamo che il messaggio M sia 2.
Il messaggio cifrato e':
2^7 = 128 = -4(33)
Per decifrarlo:
(-4)^3 = -64 = 2(33)
Esempio di cracking RSA
Mettiamo che la chiave pubblica sia (55,27). E il messaggio cifrato C = 4.
Vediamo se riusciamo a decifrarlo.
Proviamo a calcolare la chiave privata. La chiave privata sara' (55,x) dove
x e' l'inverso di 27 modulo E(55). Fattorizzando 55 sappiamo che equivale a
11*5. Quindi E(55) = 10*4 = 40.
Ora dobbiamo trovare l'inverso di 27 modulo 40.
40 = 1x27 + 13
27 = 2x13 + 1
1 = 27-2x13
= 27-2x(40-1x27)
= 3x27 -2x40
27 modulo 40 e' 3
La chiave privata e' quindi (55,3)
Decifriamo il messaggio:
M = 4^3 = 64 = 9(55)
Conclusione
La difficolta' nel calcolare la chiave privata sta nel calcolare E(pq).
Cio' significa che la difficolta sta realmente nel fattorizzare pq in p e q.
Nel caso precedente era semplice (perche pq era un numero piccolo) Ma se sia
p e q sono numeri di attorno 100 cifre, il problema diventa grosso.