RSA

Da Wikipedia, l'enciclopedia libera.

Disambiguazione – Se stai cercando altri significati di RSA, vedi RSA (disambigua).

In crittografia l'acronimo RSA indica un algoritmo di crittografia asimmetrica, utilizzabile per cifrare o firmare informazioni.

Nel 1976 Whitfield Diffie e Martin Hellman, crittologi americani, hanno ipotizzato la creazione di un cifrario "asimmetrico" composto da "chiavi pubbliche". Il sistema di crittografia si basa sull'esistenza di due chiavi distinte, che vengono usate per cifrare e decifrare. Se la prima chiave viene usata per la cifratura, la seconda deve necessariamente essere utilizzata per la decifratura e viceversa. La questione fondamentale è che le due chiavi siano indipendenti l'una dall'altra, in modo che se anche si è a conoscenza di una delle due chiavi, non si possa risalire all'altra, garantendo in questo modo l'integrità della crittografia.

Per poter realizzare con il cifrario asimmetrico un sistema crittografico pubblico è importante che un utente si crei autonomamente entrambe le chiavi, denominate "diretta" ed "inversa", e ne renda pubblica una soltanto. Così facendo si viene a creare una sorta di "elenco telefonico" a disposizione di tutti gli utenti, che raggruppa tutte le chiavi dirette, mentre quelle inverse saranno tenute segrete dagli utenti che le hanno create, ottenendo in questo modo i presupposti necessari alla sicurezza del sistema.

Indice

1 Esempi pratici
2 L'implementazione tramite algoritmo RSA
3 Funzionamento
4 Operazioni
5 Fondamenti matematici
6 Esempio
7 Algoritmo in Java
8 Voci correlate
9 Collegamenti esterni

[modifica] Esempi pratici

Facendo un esempio pratico, se Alice vuole spedire un messaggio a Bob e non vuole che altri all'infuori di Bob possano leggerlo, Alice cercherà sull'elenco la chiave pubblica di Bob e con quella potrà cifrare il messaggio. Essendo Bob l'unico a possedere la chiave inversa, sarà anche l'unico a poter decifrare il messaggio, che rimarrà così segreto per tutti gli altri, compresa Alice, che non disponendo della chiave inversa non sarà in grado di decifrare il messaggio da lei stessa creato. Ovviamente il successo di questo sistema si basa sull'assoluta necessità che Bob sia l'unico ad essere in possesso della chiave inversa. In caso contrario, avendo entrambe le chiavi, chiunque potrebbe decifrare agevolmente il messaggio.

Con questo metodo di cifratura è possibile anche garantire la provenienza di un messaggio. Riprendiamo l'esempio precedente: Alice questa volta, prima di cifrare il messaggio usando la chiave pubblica di Bob, lo cifrerà usando la propria chiave inversa e solo in un secondo momento lo ri-cripterà utilizzando la chiave pubblica di Bob. Quando Bob riceverà il messaggio e lo decifrerà usando la propria chiave inversa, otterrà ancora un messaggio criptato. Quel dato messaggio necessiterà poi della chiave pubblica di Alice per essere decifrato, garantendo in questo modo che il messaggio è stato spedito solo e soltanto da Alice, unica a possedere la chiave inversa con la quale era stato criptato il messaggio.

Più semplicemente, utilizzando questo metodo di cifratura, Alice può mandare messaggi a tutti, garantendo la provenienza. Infatti criptando il messaggio con la propria chiave inversa, chiunque sarà in grado di leggere il messaggio, decriptandolo con la sua chiave pubblica, assicurandosi in tal modo che il mittente sia proprio Alice.

[modifica] L'implementazione tramite algoritmo RSA

È nel 1978 che questo sistema trova la sua applicazione reale. Infatti sono 3 ricercatori del MIT (Ronald Rivest, Adi Shamir e Leonard Adleman) che hanno saputo implementare tale logica utilizzando particolari proprietà formali dei numeri primi con alcune centinaia di cifre. L'algoritmo da loro inventato, denominato RSA per via delle iniziali dei loro cognomi, non è sicuro da un punto di vista matematico teorico, in quanto esiste la possibilità che tramite la conoscenza della chiave pubblica si possa decriptare un messaggio, ma l'enorme mole di calcoli e l'enorme dispendio in termini di tempo necessario per trovare la soluzione, fa di questo algoritmo un sistema di affidabilità pressoché assoluta.

Ronald Rivest, Adi Shamir e Leonard Adleman nel 1983 hanno brevettato l'algoritmo negli Stati Uniti dal MIT (brevetto 4.405.829, scaduto il 21 settembre 2000); inoltre hanno dato vita alla società RSA Data Security, tutelando così i propri interessi commerciali. In seguito la Security Dynamics acquisì la società e vendette l'utilizzo degli algoritmi a società come Netscape, Microsoft ed altri. Una variante del sistema RSA è utilizzato nel pacchetto di crittografia Pretty Good Privacy (PGP). L'algoritmo RSA costituisce la base dei sistemi crittografici su cui si fondano i sistemi di sicurezza informatici utilizzati sulla rete internet per autentificare gli utenti.

Clifford Cocks, un matematico britannico che lavorava per un dipartimento di spionaggio, il GCHQ, descrisse un sistema equivalente in un documento interno nel 1973. I documenti furono posti sotto segreto e, visto il costo relativamente alto delle macchine necessario a quel tempo per implementarlo, non ci furono ulteriori indagini né prove pratiche e la cosa fu considerata come una curiosità, per quanto se ne sa. La scoperta di Cocks fu resa pubblica solo nel 1997.

Nel 2005 un gruppo di ricerca riuscì a scomporre un numero di 640 bit (193 decimali) in due numeri primi da 320 bit, impiegando per cinque mesi un cluster Opteron con 80 processori da 2,2 GHz, potenzialmente decifrando un messaggio codificato con RSA-640.

Fatto abbastanza rilevante è che RSA è computazionalmente impegnativo, soprattutto per quanto riguarda una eventuale realizzazione hardware. Di conseguenza un attuale buon utilizzo è quello di sfruttare RSA per codificare un unico messaggio contenente una chiave segreta, tale chiave verrà poi utilizzata per scambiarsi messaggi tramite un algoritmo a chiave segreta (ad esempio AES).

Oggi, insieme a DSS, RSA è uno degli algoritmi più usati per la cifratura di firme digitali.

[modifica] Funzionamento

Per semplificare il funzionamento immaginiamo che A debba spedire un messaggio segreto a B. Occorrono i seguenti passaggi:

B sceglie due numeri primi molto grandi (per esempio da 300 cifre) e li moltiplica con il suo computer (impiegando meno di un secondo).
B invia il numero che ha ottenuto ad A. Chiunque può vedere questo numero.
A usa questo numero per cifrare il messaggio
A manda il messaggio cifrato a B, chiunque può vederlo ma non decifrarlo
B riceve il messaggio e utilizzando i due fattori primi che solo lui conosceva lo decifra.

A e B hanno impiegato pochi secondi a cifrare e decifrare, ma chiunque avesse intercettato le loro comunicazioni impiegherebbe troppo tempo per scoprire i due fattori primi, con cui si può decifrare il messaggio.

In realtà questo sistema non è così semplice, come si può notare dai calcoli descritti nel paragrafo successivo, e per trasmettere grandi quantità di dati occorre tanto tempo, quindi A e B si scambieranno con questo sistema una chiave segreta (che non occupa molto spazio), che poi useranno per comunicare tra loro usando un sistema a crittografia simmetrica, più semplice e veloce.

[modifica] Operazioni

RSA è basato sull'elevata complessità computazionale della fattorizzazione in numeri primi. Il suo funzionamento base è il seguente:

si scelgono a caso due numeri primi, $p \,$ e $q \,$ , l'uno indipendentemente dall'altro, abbastanza grandi da garantire la sicurezza dell'algoritmo
si calcola il loro prodotto $n = p q \,$ , chiamato modulo (dato che tutta l'aritmetica seguente è modulo n)
si sceglie poi un numero $d \,$ (chiamato esponente privato), coprimo e più piccolo di $(p-1)(q-1) \,$
si calcola il numero $e \,$ (chiamato esponente pubblico) tale che $e * d \equiv 1 \pmod{(p-1)(q-1)} \,$

La chiave pubblica è $(n, e) \,$ , mentre la chiave privata è $(n, d) \,$ . I fattori $p \,$ e $q \,$ possono essere distrutti, anche se spesso vengono mantenuti all'interno della chiave privata.

La forza dell'algoritmo sta nel fatto che per calcolare $d \,$ da $e \,$ o viceversa, non basta la conoscenza di $n \,$ , ma serve il numero $(p-1)(q-1) \,$ , infatti fattorizzare (cioè scomporre un numero nei suoi divisori) è un'operazione molto lenta, ma soprattutto l'operazione di modulo non è invertibile, dunque anche conoscendo $n$ non si può risalire al prodotto modulo $n$ di $p$ e $q$ .

Un messaggio $m \,$ viene cifrato attraverso l'operazione $m^e \pmod{n} \,$ , mentre il messaggio $c \,$ viene decifrato con $c^d = m^{e d} = m^1 \pmod{n} \,$ . Il procedimento funziona solo se la chiave $e \,$ utilizzata per cifrare e la chiave $d \,$ utilizzata per decifrare sono legate tra loro dalla relazione $e * d \equiv 1 \pmod{(p-1)(q-1)} \,$ , e quindi quando un messaggio viene cifrato con una delle due chiavi può essere decifrato solo utilizzando l'altra. Tuttavia proprio qui si vede la debolezza dell'algoritmo: si basa sull'assunzione mai dimostrata (nota come assunzione RSA, o RSA assumption in inglese) che il problema di calcolare $\sqrt[e]{c}\mod n$ con $n \,$ numero composto di cui non si conoscono i fattori sia computazionalmente non trattabile.

La firma digitale non è altro che l'inverso: il messaggio viene crittato con la chiave privata, in modo che chiunque possa, utilizzando la chiave pubblica conosciuta da tutti, decifrarlo e, oltre a poterlo leggere in chiaro, essere certo che il messaggio è stato mandato dal possessore della chiave privata corrispondente a quella pubblica utilizzata per leggerlo.

Per motivi di efficienza e comodità normalmente viene inviato il messaggio in chiaro con allegata la firma digitale di un hash del messaggio stesso; in questo modo il ricevente può direttamente leggere il messaggio (che è in chiaro) e può comunque utilizzare la chiave pubblica per verificare che l'hash ricevuto sia uguale a quello calcolato localmente sul messaggio ricevuto. Se i due hash corrispondono anche il messaggio completo corrisponde (questo, ovviamente, solo se l'hash utilizzato è crittograficamente sicuro).

[modifica] Fondamenti matematici

La decrittazione del messaggio è assicurata grazie ad alcuni teoremi matematici, infatti dal calcolo noi otteniamo

$c^d=(m^e)^d=m^{ed} \pmod{n} \,$

Ma sappiamo che $ed \equiv 1 \pmod{(p-1)(q-1)} \,$ , di conseguenza abbiamo che $ed\equiv 1 \pmod{p-1}$ e che $ed\equiv 1 \pmod{q-1}$ .

Quindi, per il piccolo teorema di Fermat:

$m^{ed}\equiv m \pmod{p} \,$ e $m^{ed}\equiv m \pmod{q} \,$

Siccome $p \,$ e $q \,$ sono numeri diversi e primi, possiamo applicare il teorema cinese del resto, ottenendo che

$m^{ed}\equiv m \pmod{p*q} \,$

e quindi che

$c^{d}\equiv m \pmod{n} \,$

[modifica] Esempio

Ecco un esempio di cifratura e decifratura RSA. I numeri scelti sono volutamente primi piccoli, ma nella realtà sono usati numeri dell'ordine di $10100$ .

[modifica] Generazione delle chiavi

$p=3 \,$ e $q=11 \,$ , quindi $(p-1)(q-1)=2*10=20 \,$
$n=p*q=3*11=33 \,$
prendo $d=7 \,$ , dato che $d<n \,$ e $d \,$ è coprimo di $20 \,$ (non è necessario che $d \,$ sia primo)
$e=3 \,$ , infatti $e*d=3*7=21 \equiv 1 \pmod{(p-1)(q-1)} \equiv 1 \pmod{20} \,$ poiché $21/20=1 \,$ con resto $1 \,$

Quindi abbiamo la chiave privata $(33,7) \,$ e la chiave pubblica $(33,3) \,$ .

[modifica] Cifratura e decifratura

Prendiamo ora in considerazione il messaggio $m = 15 \,$ e cifriamolo per ottenere il messaggio cifrato $c \,$ , ovviamente possiamo usare i 33 e 3, ma non 7 che fa parte della chiave privata.

$c = m^e \pmod{n}=15^{3} \pmod{33}=9 \,$

E ora decifriamo $c = 9 \,$ per ottenere $m \,$ ; qui utilizzeremo 7, componente essenziale della chiave privata.

$m=c^d \pmod{n}=9^{7} \pmod{33}=15 \,$

Quindi alla fine abbiamo decriptato il messaggio.

[modifica] Algoritmo RSA in JAVA

Semplice implementazione Java sfruttando le librerie java.math.BigInteger e java.security.SecureRandom.

BigInteger p = BigInteger.probablePrime( 512, new SecureRandom() ); //Nuovo numero primo a 512 bit
BigInteger q = BigInteger.probablePrime( 512, new SecureRandom() ); //Nuovo numero primo a 512 bit
 
BigInteger n = p.multiply( q ); // n = p*q
 
BigInteger one = new BigInteger("1");
 
BigInteger pMin1 = p.subtract( one ); // p-1
BigInteger qMin1 = q.subtract(one); // q-1
 
BigInteger fi = pMin1.multiply( qMin1 );
 
BigInteger e = p.nextProbablePrime(); //Public
 
//		while( !e.gcd( fi ).equals(one) )  //Se è primo "e" è anche coprimo con fi
//		{
//			System.out.println( "....." );
//			e = e.nextProbablePrime();
//		}
 
BigInteger d = e.modInverse(fi); //Esegue (1/e) % ((p-1)-(q-1))
 
BigInteger value = new BigInteger( "41" );
BigInteger crypto = value.modPow(d, n); //Esegue ((value)^d) % n  ---> Cifratura
BigInteger result = crypto.modPow(e, n); //Esegue ((crypto)^e) % n --> Decifratura
 
System.out.println( "Private Key: "+d);
System.out.println( "Public Key: "+e);
System.out.println( "Modulus: "+n);
 
System.out.println( "Orginal: "+value );
System.out.println( "Crypto: "+crypto );
System.out.println( "DeCrypto: "+result );

[modifica] Blind signature

Esiste un formato di firma digitale basato anche su RSA, in cui il contenuto di un messaggio viene nascosto prima di essere firmato, detto appunto blind signature.

[modifica] Algoritmo in Java

/**Implementa la suddivisione in blocco di un messaggio.
 * @param byte[] msg, rappresenta il messaggio;
 * @param int blockSize, rappresenta la lunghezza del pacchetto.
 * Determina il numero di blocchi utilizzando lo schema PKCS#5, ovvero:
 * Supponiamo che la grandezza del blocco sia di 64 bytes ed il messaggio sia di 125 bytes. 
 * In condizioni normali avremmo un blocco completo da 64 bytes, più uno
 * incompleto composto da soli 61 byte, facendo rimanere scoperti 3 bytes. 
 * Per far fronte a questo inconveniente aggiungeremo in coda tre volte il numero 3 
 * (in binario ovviamente).
 * Es.
 *      Messaggio      Padding
 *      ... ... ... 00000011 00000011 00000011
 *  
 * Con questa tecnica il messaggio risulta essere suddiviso perfettamente in blocchi.
 * Inoltre ciò significa che ogni cifrario che usa tale metodo risulta essere efficace
 * limitatamente ad un numero di blocchi di grandezza massima di 255 bytes.
 * @return un valore byte[], rappresentate il messaggio impacchettato.
 * */
private static byte[] pad(byte[] msg,int blockSize) {
	//Verifica che il messaggio sia adeguato per lo schema PKCS#5
	if (blockSize<1||blockSize>255) 
		throw new IllegalArgumentException("La grandezza dei blocchi deve essere compresa tra 1 e 255.");
	//Padding del messaggio
	int numberToPad=blockSize-msg.length%blockSize;
	byte[] paddedMsg=new byte[msg.length+numberToPad];
	System.arraycopy(msg,0,paddedMsg,0,msg.length);
	for (int i=msg.length;i<paddedMsg.length;i++) 
		paddedMsg[i]=(byte)numberToPad;
 
	return paddedMsg;
}//pad
 
/**Questo metodo prende in messaggio sottoposto a padding,
 * e lo converte in un array bidimensionale di byte.
 * 	Ogni riga in questa matrice è un blocco.
 * Il metodo di decriptaggio lavorerarà con questi due array.
 * @param byte[] msg, rappresenta il messaggio già sottoposto alla tecnica del padding;
 * @param int blockSize, rappresenta la lunghezza del pacchetto.
 * @return una matrice byte[][], rappresentate il messaggio in due blocchi.
 * */
private static byte[][] block(byte[] msg,int blockSize) {
	//Crea un array di bytes 2D sottoposto alla tecnica del padding
	int numberOfBlocks=msg.length/blockSize;
	byte[][] ba=new byte[numberOfBlocks][blockSize];
	for (int i=0;i<numberOfBlocks;i++)
		for (int j=0;j<blockSize;j++)
			ba[i][j]=msg[i*blockSize+j];
 
	return ba;
}//block
 
/**Questo metodo spacchetta il messaggio; Ciò avviene dopo l'operazione di criptaggio o decriptaggio.
 * Questi riceve in input un array 2D di bytes e lo riconverte in un array lineare di bytes.
 * Nell'applicare tale metodo bisogna avere accortenza nel verificare che
 * la trasformazione di cifratura o decifratura possa produrre un numero intero inferiore alla 
 * dimensione del blocco stesso.
 * In tal caso, si provvederà a riempire la parte finale del blocco.
 * @param byte[][] ba, rappresenta una matrice nella quale è memorizzato il messaggio n due blocchi.
 * @param int blockSize, rappresenta la lunghezza del pacchetto.
 * @return un array byte[], dove memorizzare il codice decrifrato
 * */
private static byte[] unBlock(byte[][] ba,int blockSize) {
 
	//Crea un array byte[], dove memorizzare il codice decrifrato
	byte[] m2=new byte[ba.length*blockSize];
	//Pone i blocchi in un array 1D
	for (int i=0;i<ba.length;i++) {
		int j=blockSize-1;
		int k=ba[i].length-1;
		while (k>=0) {
			m2[i*blockSize+j]=ba[i][k];
			k--;
			j--;
		}//while
	}//for
 
	return m2;
}//unBlock
 
/**
 * Questo metodo rimuove il padding dal messaggio. 
 * Esamina il valore numerico dell'ultimo blocco ed in base
 * a tale valore ne elimina una quantità pari di blocchi 
 * aggiunti durante la fase di padding.
 * 
 * @param byte[] msg, rappresenta il messaggio con padding.
 * @param int blockSize, rappresenta la lunghezza del pacchetto.
 * @return un array byte[], sprovvisto di blocchi di padding.
 * */
private static byte[] unPad(byte[] msg,int blockSize) {
	/*Determina la quantità di blocchi, testando il valore memorizzato
	nell'ultimo blocco*/
	int numberOfPads=(msg[msg.length-1]+256)%256;
	//Elimina i blocchi di padding
	byte[] answer=new byte[msg.length-numberOfPads];
	System.arraycopy(msg,0,answer,0,answer.length);
	return answer;
}//unPad
 
/**
 * Cripta secondo il sistema RSA
 * @param msg di tipo byte[], rappresenta il messaggio in chiaro espresso in byte
 * @param e di tipo BigInteger, rappresenta la chiave pubblica
 * @param n di tipo BigInteger, rappresenta il modulo
 * @return un array di byte
 * */
public static byte[] RSAEncipher(byte[] msg,BigInteger e,BigInteger n) {
 
	//Determina la grandezza in blocchi del testo in chiaro
	int blockSize=(n.bitLength()-1)/8;
	byte[][] ba=block(pad(msg,blockSize),blockSize);
	//Avvia il processo di crittazione
	for (int i=0;i<ba.length;i++) 
		ba[i]=getBytes(new BigInteger(1,ba[i]).modPow(e,n));
 
	//il blocco cifrato è di una dimensione maggiore di byte rispetto al testo in chiaro.
	return unBlock(ba,blockSize+1);
}//RSAEncipher
 
/**
 * Decripta secondo il sistema RSA
 * @param msg di tipo byte[], rappresenta il messaggio criptato espresso in byte
 * @param d di tipo BigInteger, rappresenta la chiave privata
 * @param n di tipo BigInteger, rappresenta il modulo
 * @return un array di byte
 * */
public static byte[] RSADecipher(byte[] msg,BigInteger d,BigInteger n) {
 
	//Calcola la grandezza del blocchi criptati
	int blockSize=(n.bitLength()-1)/8+1;
	byte[][] ba=block(msg,blockSize);
	//Avvia la decrittazione
	for (int i=0;i<ba.length;i++) 
		ba[i]=getBytes(new BigInteger(1,ba[i]).modPow(d,n));
 
	//spacchetta il testo
	return unPad(unBlock(ba,blockSize-1),blockSize-1);
}//RSADecipher

[modifica] Voci correlate

[modifica] Collegamenti esterni

Sito della società commerciante l'RSA

Portale Crittografia
Portale Sicurezza informatica

RSA

Da Wikipedia, l'enciclopedia libera.

Indice

[modifica] Esempi pratici

[modifica] L'implementazione tramite algoritmo RSA

[modifica] Funzionamento

[modifica] Operazioni

[modifica] Fondamenti matematici

[modifica] Esempio

[modifica] Generazione delle chiavi

[modifica] Cifratura e decifratura

[modifica] Algoritmo RSA in JAVA

[modifica] Blind signature

[modifica] Algoritmo in Java

[modifica] Voci correlate

[modifica] Collegamenti esterni

Visite

Strumenti personali

Navigazione

comunità

Ricerca

Strumenti

Altre lingue