La codificazione con RSA

Novembre 2016
RSA, dal nome degli inventori, è un algoritmo di cifratura appartenente alla famiglia crittografia asimmetrica.


Algoritmo di crittografia Rivest, Shamir, Adleman (RSA)

RSA può essere utilizzato per garantire:


La confidenzialità, solo il proprietario della chiave privata può leggere il messaggio cifrato con la corrispondente chiave pubblica;

La non-alterazione e il non-ripudio, solo il proprietario della chiave privata può firmare un messaggio (con la chiave privata). Una firma decifrati con la chiave pubblica così dimostrerà l'autenticità del messaggio. La sua forza sta nella difficoltà di fattorizzare un gran numero.

Eventi Importanti

1978, Ronald L. Rivest, Adi Shamir et Leonard Adleman pubblicano "Un metodo per ottenere delle firme digitali e delle chiave pubbliche di criptosistemi". Nella rivista mensile della Association for Computing Machinery (ACM);

1982, Rivest, Shamir e Adleman fondano la società "RSA Data Security" (ribattezzata nel 2006 "RSA, The Security Division of EMC"). "Un sistema di crittografia delle comunicazioni e di metodo." È brevettata nel 1983 presso il Massachusetts Institute of Technology (MIT ), è scaduto nel settembre 2000;

1991, pubblicazione dei primi «Standard di crittografia a chiave pubblica» (PKCS), e apertura delle «competizione della fattorizzazione RSA» (chiusa nel 2007), spingendo il mondo della ricerca ad elaborare dei metodi per il factoring delle chiave pubbliche (e quindi decifrare qualsiasi messaggio);

1994, «L'algoritmo in tempo polinomiale per il factoring in quantum computer» di Peter Shor, può teoricamente rompere qualsiasi chiave RSA. Tuttavia, l'attuazione richiede un computer quantistico. Nel 2001, IBM ha riuscito una fattorizzazione quantistica di una chiave RSA di 15 bit (esperienza ripetuta nel 2012).

2000, pubblicazione dei standard PKCS #15, i più recenti fino ad oggi (in versione 1.1);

2010, la chiave RSA di 768 bit del concorso del 1991 è craccata, è finora il miglior risultato (noto pubblicamente) di fattorizzazione di una chiave RSA.

Attuazione della RSA

Esonero di responsabilità: questo articolo stabilisce il principio di base dell'algoritmo pubblicato nel 1978. Per una rigorosa attuazione, una serie di precauzioni devono essere prese in considerazione per evitare alcune vulnerabilità (fare riferimento alle più recenti normative).

Alice e Bob

Bob ha un messaggio confidenziale da inviare ad Alice. Alice costruisce due chiavi:


Una chiave di cifratura pubblica la quale invia a Bob;

Una chiave di decifratura privata che conserva con cura.

Bob utilizza la chiave pubblica per crittografare il messaggio e lo trasmette ad Alice;

Alice utilizza la chiave privata per decifrare il messaggio ricevuto.

Generare delle chiavi

Consideriamo due numeri primi scelti a caso, p e q.

Si nota: n = p*q e ? = (p-1)*(q-1). Consideriamo d un grande numero intero scelto "a caso", primo con ?. E e l'inversione di d modulo ?. La chiave di cifratura pubblica è la coppia (n, e), la chiave privata per decifrare la coppia (n, d).

Crittografia/decrittografia

Crittografia

Prima di essere criptato, il messaggio originale deve essere suddiviso in una serie di numeri interi M di valori compresi tra 0 e n-1. Per ogni intero M si deve calcolare C?M^e [n]. Il messaggio cifrato è costituito dal succedersi degli interi C</ ital>.

Decrittografia

In base al modo in cui è stato criptato, il messaggio ricevuto deve essere composto da una successione di numeri interi <ital>C
di valori compresi tra 0 e ital>n-1</ital>. Per ogni intero C si deve calcolare M?C^d [n]. Il messaggio originale può quindi essere ricostruito dalla serie di interi M.

Affidabilità

La sicurezza dell'algoritmo RSA risiede nella difficoltà di fattorizzare n. Per decifrare il messaggio, è necessario trovare d sapendo e, che richiede il ricalcolo di ?, e quindi di sapere p e q, i primi due fattori n.

Tuttavia, la fattorizzazione di un intero (molto grande) in fattori primi è estremamente difficile, questa operazione richiede un'elevata capacità di calcolo. Per esempio: nel 2010, l'INRIA e suoi partner sono stati in grado di fattorizzare una chiave a 768 bit. Ci sono voluti due anni e mezzo di ricerca e più di 10^20 calcoli. Questo è finora il miglior risultato di fattorizzazione noto. Per difendersi contro il crescente potere dei calcoli, si raccomanda regolarmente di usare le chiavi di dimensioni sempre più grandi (attualmente 2048 bit).

Potrebbe anche interessarti :

Encryption with RSA
Encryption with RSA
Cifrado por medio de RSA
Cifrado por medio de RSA
Algorithme de chiffrement RSA
Algorithme de chiffrement RSA
A codificação com RSA
A codificação com RSA
Il documento intitolato « La codificazione con RSA » da CCM (it.ccm.net) è reso disponibile sotto i termini della licenza Creative Commons. È possibile copiare, modificare delle copie di questa pagina, nelle condizioni previste dalla licenza, finché questa nota appaia chiaramente.