# Crittografia/RSA

Crittografia
Copertina Tutti i moduli · Sviluppo
    Copertina
Parte I: Introduzione alla Crittografia
* Introduzione alla crittografia
* Storia della crittografia
** Crittografia classica
** Crittografia medievale
** Crittografia dal 1800 alla seconda guerra mondiale
** Crittografia durante la seconda guerra mondiale
** Crittografia contemporanea
** Crittografia nella cultura popolare
** Linea temporale degli eventi importanti
* Concetti fondamentali
** Principio di Kerckhoffs
** Obiettivi della crittografia
** Obiettivi della crittanalisi
** Il ruolo della crittografia nella sicurezza informatica
** Cifrature simmetriche
** Cifrature asimmetriche
** Funzioni Hash
** Distribuzione e autenticazione della chiave
** Difetti e debolezze comuni
Parte II: Progettare cifrari
* Principi base nella progettazione
* Piccoli segreti nascondono segreti più grandi
* algoritmi aperti e il valore del Peer-Review
* Pensa come un crittoanalista
* La matematica che devi conoscere
* La sicurezza informatica non è solo la cifratura
* Un codice non violato non è necessariamente non violabile
Parte III: Violare cifrature
* I principi base nel violare cifrari
* Debolezze
** La proporzionalità della segretezza
*** La lunghezza della chiave
*** Qualità della sorgente casuale
*** Gli effetti del testo in chiaro sul testo cifrato
** Debolezze statistiche
** Implementazioni errate
** Peer-review non adeguato
** Ingegneria sociale e coercizione
* Attacchi
** Attacco di forza bruta
** Analisi della frequenza
** Indice delle coincidenze
** Crittanalisi lineare
** Crittanalisi differenziale
** Attacco incontro nel mezzo
* Come furono violate le cifrature storiche
** Violare i cifrari a trasposizione
** Violare il cifrario di Cesare
** Violare la macchina Enigma
** Violare il cifrario a permutazione
** Violare il cifrario di Vigenère
Parte IV: Usare cifrature
* Applicazioni della crittografia
** Firma elettronica
*** Firma elettronica
*** DSA
** Moneta elettronica
** Voto elettronico
** DRM
** Anonimato
* Cifrature classiche
** Cifrario di Beale
** Cifrari a trasposizione
** Cifrario di Cesare
** Cifrario Atbash
** Cifrario a chiave autocifrante
** Cifrario di Playfair
** Sostituzione polialfabetica
** S-box
** Scytale
** Cifrario a sostituzione
** Cifrario a permutazione
** Cifrario di Vernam
** Cifrario di Vigenère
* Cifrature contemporanee
** Cifrature simmetriche
*** Macchina Enigma
*** One-time pads
*** Data Encryption Standard (DES)
*** Advanced Encryption Standard
** Cifrature asimmetriche
*** Introduzione alla cifratura a chiave pubblica
*** RSA
*** ElGamal
*** Curva ellittica
** Funzioni di hash
*** MD5
*** SHA-1
*** RIPEMD-160
*** Tiger
* Protocolli
** Protocolli di autentificazione
*** Kerberos
** Protocolli per lo scambio chiave
*** Diffie-Hellman
** Comunicazioni sicure
*** SSL, SSH
Parte V: La crittografia e la società
* La natura mutevole dell'uso della crittografia
* Crittografia, governi e leggi
* Aspettative dell'utente normale
* Snake Oil
Parte VI: Miscellanea
* Possibilità future
** Crittografia quantistica
** Miglioramento del calcolo parallelo dei computer
* Glossario dei termini
* Letture addizionali
* Appendice A: background matematico
** Crittografia/Teoria dei numeri
** Crittografia/Teoria dei gruppi
** Crittografia/Complessità computazionale
Modifica il sommario
In crittografia l'acronimo RSA indica un algoritmo di crittografia asimmetrica, utilizzabile per cifrare o firmare informazioni.

## Storia

L'algoritmo RSA è stato descritto nel 1977 da Ronald Rivest, Adi Shamir e Len Adleman al Massachusetts Institute of Technology; le lettere RSA vengono proprio dalle iniziali dei cognomi.
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 1983 l'algoritmo fu brevettato negli Stati Uniti dal MIT (brevetto 4.405.829). Il brevetto è scaduto il 21 settembre 2000.
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 contentene una chiave segreta, tale chiave verrà poi utilizzata per scambiarsi messaggi tramite un algoritmo a chiave segreta (ad esempio AES).
Oggi, insieme a DES, RSA è uno degli algoritmi più usati per la cifratura di firme digitali.

## Operazioni

RSA è basato sul problema complesso 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=pq\,$, chiamato modulo (dato che tutta l'aritmetica seguente è modulo n)
* si sceglie poi un numero $e\,$ (chiamato esponente pubblico), più piccolo di $(p-1)(q-1)\,$ e suo coprimo
* si calcola il numero $d\,$ (chiamato esponente privato) 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 è che per calcolare $d\,$ da $e\,$ (così come il contrario) 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, soprattutto se $n\,$ è un numero grande a sufficienza, poiché non si conoscono algoritmi efficienti.
Un messaggio $m\,$ viene cifrato attraverso l'operazione $m^{e}{\pmod {n}}\,$, mentre il messaggio $c\,$ viene decifrato con $c^{d}=m^{ed}=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 $ed\equiv 1{\pmod {n}}\,$, 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).

## 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}}$ 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}}\,$

## Esempio

Ecco un esempio di criptazione e decriptazione RSA. I numeri scelti sono volutamente primi piccoli, ma nella realtà sono usati numeri dell'ordine di $10^{100}$.

### Generazione delle chiavi

* $p=61\,$ e $q=53\,$, $(p-1)(q-1)=3120\,$
* $n=p*q=61*53=3233\,$
* $e=17\,$, $e<n\,$ ed è coprimo per 3120 (in questo caso è primo, ma in generale non è necessario)
* $d=2753\,$ infatti $e*d=2753*17=46801\equiv 1{\pmod {(p-1)(q-1)}}\equiv 1{\pmod {3120}}\,$ poiché $46801/3120=15\,$ con resto $1\,$
Quindi abbiamo la chiave pubblica $(3233,17)\,$ e la chiave privata $(3233,2753)\,$.

### Cifratura e decifratura

Prendiamo ora in considerazione il messaggio $m=123\,$ e cifriamolo per ottenere il messaggio cifrato $c\,$, ovviamente possiamo usare i 3233 e 17, ma non 2753 che fa parte della chiave privata.
$c=m^{e}{\pmod {n}}=123^{17}{\pmod {3233}}=855\,$
E ora decifriamo $c=855\,$ per ottenere $m\,$; qui utilizzeremo 2753, componente essenziale della chiave privata.
$m=c^{d}{\pmod {n}}=855^{2753}{\pmod {3233}}=123\,$