Torniamo al primo problema.
Come fare acquisti sicuri via Internet?
Come trasmettere informazioni in modo
riservato?
Per salvaguardare la sicurezza dei
pagamenti via Internet o delle procedure
Bancomat, si utilizza spesso il
sistema crittografico RSA.
Rivest - Shamir - Adelman
RSA
è un moderno sistema di crittografia
basato sull’aritmetica modulare...
Occorre un breve riassunto
degli ingredienti-base!
Indichiamo con
N = {0,1,2, ...} l’insieme dei numeri naturali
e con
Z = {... -2,-1,0,1,2, ...} quello dei numeri interi.
Se p  N, diciamo che due interi x e y sono
congrui modulo p se hanno lo stesso resto dalla
divisione per p, cioè se:
x = ap + r e y = bp + r
o, equivalentemente, se la loro differenza è un
multiplo di p:
x-y = kp, per qualche k  Z.
Scriveremo: xy (mod p)
che si legge: “x è congruo a y modulo p”.
Ad esempio, se p=2, due numeri sono congrui
modulo 2 se sono entrambi pari o entrambi dispari.
Se x=4 e y=10, poiché x-y= -6 = (-3) 2, allora
410 (mod 2).
Altro esempio:
9  23 (mod 7), poiché 9-23 = -14 = (-2) 7.
E ora raggruppiamo gli interi!
Lavoriamo con gli interi modulo p.
Fissiamo x  Z e raggruppiamo tutti gli interi
congrui ad x. Questi formano la cosiddetta
classe di x modulo p, cioè:
[x] = {y  Z tali che xy (mod p)}=
{... x-3p, x-2p, x-p, x, x+p, x+2p, ...}.
Ovviamente (basta riflettere un po’) due interi
congrui tra loro hanno la stessa classe:
xy (mod p) se e solo se [x]=[y] (mod p).
In questo modo si ottiene una
partizione di Z.
• Infatti ogni intero appartiene ad una ed una
sola classe: x  [x] !
• Inoltre l’unione di tutte le classi è Z.
• Vediamo graficamente:
partizione di Z modulo 2
[0]={...-2,0,2,4,...}
partizione di Z modulo 3
[0]
[1]={...-3,1,3,5,...}
[1]
[2]
In generale: Zp è l’insieme
di tutte le classi modulo p
cioè Zp = {[0],[1],[2], ... , [p-1]}.
Infatti: [p] = [0], [p+1]=[1], ecc., quindi non occorre ripeterle!
Ad esempio, in Z6 l’elemento [10] coincide con [4], [-2], [16], ...
Utilizzeremo sempre il “rappresentante” più piccolo di 6 e positivo. In
questo caso: [4].
Zp
partizione di Z modulo p
[0]
[0]
[1]
[2]
...
[1]
[2]
[p-1]
[p-1]
Facciamo un po’ di esercizio...
• Il detto “facile come 2 e 2 fa 4” non è sempre
vero! Calcoliamo [2] + [2] in Z4.
[2] + [2] = [2+2] = [4] = [0] in Z4.
• Calcoliamo il più piccolo rappresentante positivo
di [213] in Z5. Cioè troviamo x tale che [x] =
[213] e x è il più piccolo intero positivo con tale
proprietà.
Dividiamo 213 per 5... 213 = 5 · 42 + 3. Quindi
[213] = [5 · 42] + [3] = [3] in Z5.
E ora il problema della sicurezza.
Supponiamo di voler proteggere delle
informazioni da un uso non autorizzato.
Per prima cosa trasformiamo i dati in numeri
(ad esempio il PIN del Bancomat).
Il sistema RSA codifica un numero in un
numero segreto e può decodificarlo in quello
iniziale.
Ingredienti del sistema RSA:
(in rosso quelli segreti, in blu quelli pubblici)
• Due numeri primi p e q (segreti);
(nella pratica: molto grandi, più del numero da criptare)
• un “modulo” m = pq (pubblico);
• una chiave codificatrice v  N (pubblica);
• una chiave decodificatrice w  N (segreta)
in modo che
vw  1 (mod (p-1)(q-1))
Sia x il numero che si vuole trasmettere.
v
• Trasmettiamo y=x (via Internet o ...)
• Il ricevente conosce w ed m.
• Il ricevente divide yw per m: il resto è x!!!
Perché?
Consideriamo Zm = {[0],[1],[2], ... , [m-1]}
• Abbiamo scelto x << p e x << q, quindi
sarà anche x << m=pq.
• Quindi (questa è l’idea-chiave!), l’elemento
[x] compare tra quelli “canonici” di Zm!
Per maggior chiarezza, usiamo questa notazione
(stiamo per lavorare con vari Zm, con m diversi...):
Zm = {[0]m,[1]m,[2]m, ... , [m-1]m}
Vogliamo provare che dividendo
yw per m si ha x come resto...
...cioè che [yw]m = [x]m.
Facciamo i conti: ricordiamo che abbiamo trasmesso
y=xv , quindi yw = xvw.
Ma abbiamo scelto v e w in modo che
vw  1 (mod (p-1)(q-1))
cioè vw-1 = h(p-1)(q-1) per qualche intero h.
Allora:
[yw]m = [xvw]m = [xh(p-1)(q-1) +1]m = [xh(p-1)(q-1)]m · [x]m.
deve essere [1]!!!
Quindi la nostra procedura funziona se
proviamo che
[x(p-1)(q-1)]m =[1]m.
Qui ci vuole
un po’ più di matematica!
Spostiamoci in Zp e Zq
(p e q sono i primi “grandi” scelti all’inizio)
• Piccolo teorema di Fermat
Sia p un numero primo.
Allora, per ogni intero a, risulta:
a p  a (mod p), cioè [a p ]p=[a]p in Zp.
In particolare, se [a]p [0]p , allora:
a p-1 1 (mod p), cioè [ap -1]p=[1]p in Zp.
Applichiamo questo teorema:
• l’intero a dell’enunciato è, per noi, xq-1.
• Se fosse [xq-1]p [0]p , potremmo applicare il
teorema, ottenendo:
[x(q-1)(p-1)]p=[1]p .
• Vediamo perché [xq-1]p [0]p . Per assurdo, se fosse
[xq-1]p = [0]p, allora xq-1 sarebbe multiplo di p. Ma p
è primo, quindi x sarebbe multiplo di p: impossibile
perché abbiamo scelto x << p!
• Quindi il teorema si può applicare, provando che…
[x(q-1)(p-1)]p=[1]p .
(*)
Se facciamo lo stesso ragionamento, scambiando i
ruoli di p e q, ovviamente troviamo che:
[x(q-1)(p-1)]q=[1]q .
(**)
Le relazioni (*) e (**) significano che: x(q-1)(p-1)-1 è
un multiplo sia di p che di q, dunque di m=pq, cioè
[x(p-1)(q-1)]m =[1]m,
come volevamo.
Non manca che un esempio
“concreto”
cioè
NUMERICO.
•
•
•
•
•
Riassumiamo gli ingredienti:
Siano:
il numero x (da trasmettere);
due numeri primi p e q (segreti);
il “modulo” m = pq (pubblico);
chiave codificatrice v (pubblica);
chiave decodificatrice w (segreta)
x = 123
p = 127
q = 251
m = 31877
in modo che
vw  1 (mod (p-1)(q-1)),
cioè
Scelgo h=1 e calcolo
(p-1)(q-1)+1 =31501.
vw = h (p-1)(q-1) + 1.
Fattorizzo:
31501= 172 109
v
w
Quindi i dati sono:
x = 123
p = 127
q = 251
m = 31877
v = 289
w = 109
PROCEDIAMO!
• Invio y=xv = 123289 =...
• Il ricevente conosce w ed m.
• Il ricevente divide yw = ...
per m = 31877.
• Il resto è 123 !!!
E la sicurezza?
• Viene trasmesso y=xv
• Il ricevente conosce w ed m.
• Il ricevente divide yw per m: il resto è x.
Domande:
1. Se y e v sono pubblici, si potrebbe calcolare x = vy.
2. Oppure, visto che m=pq è pubblico, si potrebbe fattorizzare e
trovare p e q. Poiché vw  1 (mod (p-1)(q-1)), si potrebbe poi
cercare di trovare w.
In pratica, è impossibile!
1. In realtà, y e v sono molto grandi: quindi
vy non si riesce a calcolare .
2. Anche l’altro metodo risulta impossibile: ciò
è dovuto alla grandezza di p e q. Infatti sono
stati scelti dei numeri “enormi” e quindi
m=pq non può essere fattorizzato con i
computer disponibili…
Conclusione:
I grandi numeri primi
proteggono la segretezza!