2. RSA

Il cifrario che utilizzeremo per la nostra applicazione è RSA:

RSA si basa sul prodotto di due numeri primi di grandi dimensioni, che possono superare le 300 cifre. In linea di principio, l'analisi dell'algoritmo potrebbe essere facilmente suddivisa in due parti: la generazione della coppia di chiavi e l'utilizzo delle stesse. La prima parte, la generazione della coppia di chiavi, viene solitamente effettuata in questo modo:

1.vengono scelti due numeri primi p, q molto grandi;

2.viene calcolato n=pq, e la funzione di Eulero Φ(n) = (p - 1)(q - 1) ;

3.si sceglie un intero e minore di Φ(n) e primo con esso;

4.utilizzando la versione estesa dell'algoritmo di Euclide viene calcolato l'intero d così da avere e * d = 1 mod Φ(n);

5.vengono resi pubblici i valori e,n che costituiscono la chiave pubblica e mantenuto segreto d che, utilizzato con n rappresenta la chiave privata.

Nella seconda parte, il messaggio cifrato C è uguale ad M^e mod n (con M < n) . Per risalire al messaggio originale basta elevare C^d mod n.

Ecco un piccolo esempio: dati p=47 , q=71 e Φ(n) = (p - 1)(q - 1) = 46 * 70 = 3220, la chiave privata sarà (n = 3337, d = 1019) e la chiave pubblica  (n = 3337, e = 79).
Supponiamo di voler cifrare il messaggio M = 688, avremo quindi: M^e mod n = 688⁷⁹ mod 3337 = 1570 = C.
Per effettuare la decifratura applichiamo semplicemente la formula C^d mod n = 1570¹⁰¹⁹ mod 3337 = 688 = M.

Basandoci sul Teorema Cinese del Resto possiamo applicare una procedura più efficiente per la decifratura dei messaggi:

Teorema Cinese del Resto
• Teorema:
 – Sia n=pq con gcd(p,q)=1.
 – Per ogni coppia (y,z) Î Z_p x Z_q esiste un unico x Î Z_n, t.c.
    • x=y mod p
    • x=z mod q
• Dimostrazione:
 – Con il teorema esteso di Euclide troviamo a,b t.c. ap+bq=1
 – Definiamo c = bq per cui c=1 mod p e c=0 mod q
 – Definiamo d = ap per cui d=1 mod q e d=0 mod p
 – Sia x = cy+dz mod n, allora
    • cy+dz = 1y + 0 = y mod p
    • cy+dz = 0 + 1z = z mod q
• Inoltre:
– Consideriamo l’insieme A := {y +kp : k Î {0, . . . , q -1}}.
– È evidente che x = y mod p qualunque sia x Î A. Inoltre, y +k₁p = y +k₂p mod q implica p(k₁ -k₂) = 0 mod q.
– Per il corollario (1) questo è possibile solo se k₁ = k₂ mod q, e quindi gli elementi di A sono distinti mod q.
– Dato che A ha esattamente q elementi, non resta che concludere che ne esiste uno (ed uno solo) che soddisfa la congruenza richiesta. 

Corollario del teorema di Euclide (1)
Dato a Î Z_n, se gcd(a,n) = 1 allora l’applicazione f_a : Z_n à Z_n definita da f_a(x) := ax mod n è una biiezione (corrispondenza uno a uno), con inversa f_{a-1 .}

Decifratura RSA più efficiente
     – Dati p,q calcoliamo a,b t.c. ap + bq = 1.
     – c = bq; d = ap
• Decifratura, dato C messaggio cifrato:
     – Calcoliamo y=C^{d mod p-1} mod p
     – Calcoliamo z=C^{d mod q-1} mod q
     – Calcoliamo il messaggio originale M: M = cy+ dz mod n
Così facendo abbiamo due esponenziali modulo p,q invece di uno solo modulo n, mentre gli esponenti (d mod p-1 e d mod q-1)  possono essere calcolati anche solo una volta e conservati per le successive operazioni di decifratura.

2.1 Caratteristiche RSA

Il cifrario RSA viene considerato sicuro perché si ritiene che solo individuando i fattori primi della chiave pubblica sarebbe possibile decifrare il messaggio. E la fattorizzazione di un numero enorme (si usano oggi chiavi di 1024 o 2048 bit) richiede tempi proibitivi. Non è per la verità dimostrato che sia necessaria la fattorizzazione per forzare RSA, ma d'altra parte è stato dimostrato che il calcolo della funzione di Eulero comporta una complessità paragonabile alla fattorizzazione. E fino ad ora nessun metodo del genere è stato trovato ed RSA resta a tutt'oggi un cifrario inviolato.

Un difetto di RSA è la mole dei calcoli aritmetici che per numeri grandi si traduce in una lentezza della codifica; e poiché la codifica consiste essenzialmente in un elevamento a potenza in un'aritmetica finita, diventa essenziale disporre di algoritmi veloci per il calcolo della potenza. Anche così RSA resta un metodo di cifratura molto più lento (circa mille volte!) degli algoritmi classici come DES; per questo si usano spesso soluzioni miste: p.es. RSA è utilizzato solo per trasmettere la chiave segreta di un DES e il messaggio vero e proprio viene trasmesso appunto con il DES.

2.2 Firma Digitale RSA

La firma digitale è una stringa ricavata dal messaggio applicando un particolare algoritmo, cifrata mediante la chiave privata del mittente e spedita insieme al messaggio. La decifratura della firma mediante la chiave pubblica prova che è stata cifrata dal mittente o da qualcuno in possesso della sua chiave privata. Inoltre, il confronto della stringa decifrata con una stringa ricavata ex-novo dal messaggio applicando lo stesso algoritmo, consente di verificare l’integrità: se le due stringhe coincidono il messaggio è integro.

Il paradigma è il seguente: il mittente, unico possessore della chiave privata, produce un’impronta del messaggio, detta hash o message-digest, e la cifra con la sua chiave privata. L'hash cifrato rappresenta la firma digitale. Il destinatario riceve il messaggio insieme alla firma. Dal messaggio, eventualmente cifrato, ricostruisce l'impronta, mentre dall'hash, dopo averlo decifrato con la chiave pubblica del mittente, ricava l'impronta del messaggio com’era al momento della sua spedizione. Se le due impronte così ottenute coincidono si è certi che la firma è stata apposta mediante la chiave privata del mittente e che il messaggio non è stato modificato durante la trasmissione.