Matematica Discreta Lezione del 18/05/09
Abbiamo visto l’implementazione del sistema crittografico RSA (sistema a chiave pubblica).
Il soggetto destinatario sceglie 2 numeri primi distinti p,q e calcola il loro prodotto n=pq, rendendo pubblico n, ma tenendo segreti i fattori primi p,q .
Lo spazio dei messaggi in chiaro (e anche di quelli cifrati) é l’insieme {0,1,….,n-1}.
Il soggetto B sceglie un naturale c coprimo con (n) (c è la chiave pubblica di cifratura), calcola il simmetrico [d] di [c] nel monoide Z(n) (d è la chiave segreta di decifratura).
La funzione di cifratura f : {0,1,….,n-1} {0,1,….,n-1} è definita ponendo f(x)=xcmodn, quella di cifratura g : {0,1,….,n-1} {0,1,….,n-1} è definita ponendo g(y)=ydmodn .
Nel sistema crittografico RSA è “computazionalmente difficile” per un intruso ricavare dalla chiave di cifratura c (resa pubblica) quella (segreta) di decifratura d. Infatti si può notare che per calcolare la chiave di decifratura d è necessario conoscere il valore della funzione di Eulero (n)=(p-1)(q-1) (per calcolare con l’algoritmo Euclideo il simmetrico [d] di [c] nel monoide Z(n), e quindi è necessario conoscere i fattori primi p,q di n, ossia la fattorizzazione di n in prodotto di numeri primi.
Il problema è quindi equivalente a quello di fattorizzare in numeri primi il numero n, e per un generico valore n non è a tutt’oggi noto un algoritmo di fattorizzazione di complessità polinomiale.
Ciò non toglie che per particolari valori di n, alcuni algoritmi di fattorizzazione riescano in modo efficiente a calcolare i fattori primi p,q di n, e quindi a rompere il sistema RSA, per cui anche la scelta di p,q deve essere fatta con cura, per assicurare la massima sicurezza del sistema.
Possiamo ricordare il cosiddetto “RSA-129 challenge”: una sfida lanciata nel 1977 dagli inventori del sistema RSA, relativa alla fattorizzazione del numero RSA-129, di 129 cifre in base 10; tale numero (prodotto di 2 primi p,q di 64 e 65 cifre):
(1143816257578888676692357799761466120102182967212423625625618429357069352457338 978 30597123563958705058989075147599290026879543541) =
(3490529510847650949147849619903898133417764638493387843990820577) * (32769132993266709549961988190834461413177642967992942539798288533)
era alla base di un sistema RSA con cui era cifrato il messaggio testuale “the magic words are squeamish ossifrage” (letteralmente “le parole magiche sono schizzinoso avvoltoio”).
L’esponente c per la cifratura (reso pubblico insieme al valore di n) era c=9007.
Le previsioni, basate sulla efficienza degli algoritmi di fattorizzazione dell’epoca, erano che fossero necessari “milioni di anni” per calcolare i fattori primi p,q, la chiave di decifratura d, e decifrare quindi il messaggio.
Ma lo sviluppo di nuovi algoritmi (in particolare del cosiddetto “crivello quadratico” di Pomerance) e il lavoro in parallelo di più di 1000 computers messi a disposizione da utenti Internet, permise, dopo 8 mesi di lavoro, di calcolare nel 1994 la seguente chiave di decifratura (con 129 cifre):
d=106698614368578024442868771328920154780709906633937862801226224496631063125911 774470873340168597462306553968544513277109053606095
e decifrare il messaggio.
Esempio di cifratura con il sistema RSA. Supponiamo che il testo da trasmettere sia la seguente indicazione di una rotta da seguire
“15GRADISUD”.
Codifichiamo nel codice ASCII i singoli caratteri del testo:
Carattere Valore numerico In binario
1 49 (00110001)2
5 53 (00110101)2
G 71 (01000111)2
R 82 (01010010)2
A 65 (01000001)2
D 68 (01000100)2
I 73 (01001001)2
S 83 (01010011)2
U 85 (01010101)2
D 68 (01000100)2
Il testo in chiaro (come successione di 80 bits 0,1) è allora:
00110001001101010100011101010010010000010100010001001001010100110101010101000100 Il destinatario sceglie 2 numeri primi distinti, per esempio p=239, q=349 (segreti) e rende pubblico il loro prodotto n=83411. I blocchi da cifrare (e spedire) devono avere valore numerico <n; la max potenza di 2 che sia n è 216=65536, quindi si cifrano (e spediscono) blocchi di 16 bits (5 blocchi in tutto).
Il primo blocco di 16 bits da cifrare è 0011000100110101 (valore numerico x=12597).
Il destinatario calcola la funzione di Eulero (n)=(p-1)(q-1)=82824 e sceglie come chiave di cifratura c=5 (resa pubblica); infatti c è coprimo con (n)=82824 come dimostra l’algoritmo Euclideo (con 3 divisioni):
82824 = 516564+4 (q1=16564, r1=4) 5 = 41+1 (q2=1, r2=1)
4 = 14+0 (q3=4, r3=0) quindi mcd(82824, 5)=1
Per calcolare la chiave di decifratura d, il destinatario calcola il simmetrico [d] di [c] in Z(n) = Z82824, calcolando i coefficienti interi relativi che permettono di rappresentare 1 come combinazione lineare di 82824, 5 con l’algoritmo Euclideo esteso:
s0=1, s1=0, s2=s0-s1q1=1, s3=s1-s2q2= -1
t0=0, t1=1, t2=t0-t1q1= -16564, t3=t1-t2q2= 16565 ottenendo i coefficienti -1, 16565 tali che 1 = 82824(-1)+516565
Dunque [16565] è il simmetrico di [5] in Z(n) = Z82824, e la chiave di decifratura (tenuta segreta) è d=16565.
Il destinatario cifra il primo blocco di 10 bits di valore numerico x=12597 con la funzione di cifratura e la chiave di cifratura c=5:
y = f(x) = xcmodn = 125975mod83411 = 317201802686979902757mod83411 = 33084 poi rappresenta in binario il blocco cifrato y (sempre utilizzando 16 bits):
33084 = (1000000100111100)2
e spedisce i 16 bits lungo il canale di trasmissione (facendo lo stesso con gli altri 4 blocchi di 16 bits: li cifra e li spedisce di seguito al primo).
Il destinatario riceve la successione di 80 bits, e li suddivide di nuovo in 5 blocchi da 16 bits ciascuno.
Il primo blocco è appunto 1000000100111100 (di valore numerico y=33084); a tale blocco applica la funzione di decifratura con chiave di decifratura d=16565 ottenendo il valore numerico del primo blocco in chiaro x:
g(y) = ydmodn = 3308416565mod83411 = 12597 = x
Infine il destinatario rappresenta in binario il blocco x (sempre utilizzando 16 bits):
12597 = (0011000100110101)2
e (dopo avere decifrato gli altri 4 blocchi) dispone in successione i bits ottenendo il messaggio in chiaro da 80 bits (che attraverso il codice ASCII si decodificano nelle lettere del testo
“15GRADISUD”.
Problema : come calcolare 3308416565mod83411 (resto della divisione di 3308416565 per 83411): il numero 3308416565 ha più di 80000 cifre in base 10.
Esiste un algoritmo efficiente per risolvere tale problema, ed è la cosiddetta esponenziazione modulare.
