Algoritmo RSA

Dopo una breve introduzione ai crittosistemi asimmetrici, passiamo a vedere in modo particolareggiato uno degli algoritmi asimmetrici più conosciuti ed utilizzati: l'algoritmo RSA.

Il nome dell’algoritmo deriva dalla prima lettera dei cognomi di coloro che lo inventarono nell’Aprile del 1977: Ronald L. Rivest, Adi Shamir e Leonard M. Adleman.

I campi di impiego dell'algoritmo sono diversi e variano passando dall'uso all'interno di programmi fino ad arrivare a costituire l'elemento portante di vere e proprie tecnologie di rete. Fra le varie applicazioni possiamo sicuramente ricordare:

• PGP;
• Secure Socket Layer (SSL)
• Secure Electronic Transactions (SET);

Analisi dell'algoritmo

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:

• vengono scelti due numeri primi p, q molto grandi;
• viene calcolato n=pq, e la funzione di Eulero Φ(n) = (p - 1)(q - 1) dopo di che i due primi p, q vengono eliminati;
• si sceglie un intero e minore di Φ(n) e primo con esso;
• utilizzando la versione estesa dell'algoritmo di Euclide viene calcolato l'intero d così da avere e * d = 1 mod Φ(n);
• vengono resi pubblici i valori e,n che costituiscono la chiave pubblica e mantenuto segreto d che, utilizzato con n rappresenta la chiave privata.

Sicuramente vi starete chiedendo su cosa viene basata l'inviolabilità dell'algoritmo. La risposta è molto semplice e coinvolge l'impiego di diversi principi matematici.

Una volta generata la coppia di chiavi, vediamo insieme le operazioni effettuabili, immaginando di avere due utenti, l'Utente A e l'Utente B, entrambi con la propria coppia di chiavi, pubblica e privata, più la chiave pubblica della controparte:

Clic per ingrandire

Cifratura

L'Utente A deve inviare del materiale cifrato all'Utente B. Per fare questo utilizzerà la chiave pubblica dell'Utente B effettuando queste operazioni:

Clic per ingrandire

Decifratura

Ricevuto i dati cifrati, l'Utente B utilizzerà la sua chiave privata per eseguire l'operazione opposta di decifratura.

Clic per ingrandire

Firma

L'operazione di firma prevede l'utilizzo della chiave privata dell'Utente A sui dati, come riportato di seguito:

Clic per ingrandire

Verifica

Per verificare i dati ricevuti, l'Utente B utilizzerà la chiave pubblica dell'utente A:

Clic per ingrandire

Velocità dell'algoritmo

Si stima che il rapporto tra la velocità di un cifrario simmetrico e quella di un cifrario asimmetrico sia indicativamente un millesimo nelle realizzazioni hardware e un centesimo in quelle software. A titolo puramente indicativo, ecco quanto riportato sulla rivista Byte Italia del Maggio 1998. La tabella si riferisce ai tempi in secondi necessari all'elaborazione di un messaggio di un singolo carattere su un sistema Pentium 133.

Riferimenti

• Ferragina P., Luccio F., Crittografia, Bollati Boringhieri, Torino, 2001.

• Meltzer C., Baker D., Cryptography Decrypted, Addison-Wesley, 2001.