Algoritmo RSA

Crittografia del messaggio

Alice dà la sua chiave pubblica ( n {displaystyle n\,} & e {displaystyle e\,} ) a Bob e tiene segreta la sua chiave privata. Bob vuole inviare il messaggio M ad Alice.

Prima trasforma M in un numero m {displaystyle m} più piccolo di n {displaystyle n} usando un protocollo reversibile concordato noto come schema di imbottitura. Poi calcola il testo cifrato c {displaystyle c\,} corrispondente a:

c = m e mod n {displaystyle c=m^{e}mod {n}}

Questo può essere fatto rapidamente usando il metodo dell'esponenziazione per quadratura. Bob invia quindi c {displaystyle c\,} ad Alice.

Decrittazione del messaggio

Alice può recuperare m {displaystyle m\,} da c {displaystyle c\,} usando la sua chiave privata d {displaystyle d\,} nella seguente procedura:

m = c d mod n {displaystyle m=c^{d}{bmod {n}}

Dato m {displaystyle m\,} , può recuperare i numeri primi distinti originali, applicando il teorema del resto cinese a queste due congruenze si ottiene

m e d ≡ m mod p q {displaystyle m^{ed}equiv m{bmod {pq}} .

Così,

c d ≡ m mod n {displaystyle c^{d}equiv m{bmod {n}} .

Un esempio di lavoro

Ecco un esempio di crittografia e decrittografia RSA. I parametri usati qui sono artificialmente piccoli, ma potete anche usare OpenSSL per generare ed esaminare un vero keypair.

1. Scegli due numeri primi a caso.
2.  : p = 61 {displaystyle p=61} e q = 53 ; {displaystyle q=53;} Calcolare n = p q {\displaystyle n=pq\,}
3.  : n = 61 ∗ 53 = 3233 {displaystyle n=61*53=3233}
4. Calcolare il totiente ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)\, }
5.  : ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {\displaystyle \phi (n)=(61-1)(53-1)=3120}
6. Scegliere e > 1 {displaystyle e>1} coprime a 3120
7.  : e = 17 {\displaystyle e=17}
8. Scegliere d {displaystyle d\,} per soddisfare d e mod ϕ ( n ) ≡ 1 {displaystyle de{bmod {\phi (n) }equiv 1\,}
9.  : d = 2753 {\displaystyle d=2753}
10.  : 17 ∗ 2753 = 46801 = 1 + 15 ∗ 3120 {\displaystyle 17*2753=46801=1+15*3120} .

La chiave pubblica è ( n = 3233 {displaystyle n=3233} , e = 17 {displaystyle e=17} ). Per un messaggio imbottito m {displaystyle m\,} la funzione di crittografia c = m e mod n {displaystyle c=m^{e}{bmod {n}} diventa:

c = m 17 mod 3 233 {displaystyle c=m^{17}{bmod {3}}233\,}

La chiave privata è ( n = 3233 {displaystyle n=3233} , d = 2753 {displaystyle d=2753} ). La funzione di decrittazione m = c d mod n {displaystyle m=c^{d}{bmod {n}} diventa:

m = c 2753 mod 3 233 {displaystyle m=c^{2753}{bmod {3}}233\,}

Per esempio, per criptare m = 123 {displaystyle m=123} calcoliamo

c = 123 17 mod 3 233 = 855 {displaystyle c=123^{17}{bmod {3}}233=855}

Per decifrare c = 855 {displaystyle c=855} , calcoliamo

m = 855 2753 mod 3 233 = 123 {displaystyle m=855^{2753}{bmod {3}233=123}

Entrambi questi calcoli possono essere calcolati in modo efficiente usando l'algoritmo square-and-multiply per l'esponenziazione modulare [it].

Derivazione dell'equazione RSA dal teorema di Eulero

RSA può essere facilmente derivato usando il teorema di Eulero e la funzione totiente di Eulero.

A partire dal teorema di Eulero,

m ϕ ( n ) ≡ 1 ( mod n ) {\displaystyle m^{\phi (n)}equiv 1{\pmod {n}}

dobbiamo dimostrare che decifrando un messaggio cifrato, con la chiave corretta, si ottiene il messaggio originale. Dato un messaggio imbottito m, il testo cifrato c è calcolato da

c ≡ m e ( mod n ) {displaystyle c\equiv m^{e}{pmod {n}}}

Sostituendo nell'algoritmo di decrittazione, abbiamo

c d ≡ ( m e ) d ≡ m e d ( mod n ) {displaystyle c^{d}equiv (m^{e})^{d}equiv m^{ed}{pmod {n}}

Vogliamo dimostrare che questo valore è anche congruente a m. I valori di e e d sono stati scelti per soddisfare,

e d ≡ 1 ( mod ϕ ( n ) ) 1{pmod {\phi (n)}}}

Vale a dire che esiste un certo numero intero k, tale che

e d = k × ϕ ( n ) + 1 {displaystyle ed=k\times \phi (n)+1}

Ora sostituiamo nel messaggio criptato e poi decriptato,

m e d ≡ m k ϕ ( n ) + 1 ≡ m × m k ϕ ( n ) ≡ m × ( m ϕ ( n ) ) k ( mod n ) {\displaystyle {begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}&equiv m\times m^{k\phi (n)}&equiv m\times \left(m^{\phi (n)}destra)^{k}{pmod {n}}end{aligned}}}

Applichiamo il teorema di Eulero e otteniamo il risultato.

m × ( 1 ) k ≡ m ( mod n ) {displaystyle m\times (1)^{k}equiv m{pmod {n}}

Schemi di imbottitura

Quando viene usato in pratica, RSA deve essere combinato con qualche forma di schema di imbottitura, in modo che nessun valore di M risulti in testi cifrati insicuri. RSA usato senza imbottitura può avere alcuni problemi:

• I valori m = 0 o m = 1 producono sempre cifrari uguali a 0 o 1 rispettivamente, a causa delle proprietà dell'esponenziazione.
• Quando si cripta con piccoli esponenti di crittografia (ad esempio, e = 3) e piccoli valori di m, il risultato (non modulare) di m e {displaystyle m^{e}} può essere strettamente inferiore al modulo n. In questo caso, i testi cifrati possono essere facilmente decifrati prendendo la radice etica del testo cifrato senza considerare il modulo.
• La crittografia RSA è un algoritmo di crittografia deterministico. Non ha componenti casuali. Pertanto, un attaccante può lanciare con successo un attacco con testo in chiaro scelto contro il sistema crittografico. Può creare un dizionario criptando probabili testi in chiaro sotto la chiave pubblica, e memorizzando i testi cifrati risultanti. L'attaccante può quindi osservare il canale di comunicazione. Non appena vede dei testi cifrati che corrispondono a quelli del suo dizionario, l'attaccante può usare questo dizionario per imparare il contenuto del messaggio.

In pratica, i primi due problemi possono sorgere quando vengono inviati brevi messaggi ASCII. In tali messaggi, m potrebbe essere la concatenazione di uno o più caratteri codificati ASCII. Un messaggio che consiste in un singolo carattere ASCII NUL (il cui valore numerico è 0) sarebbe codificato come m = 0, che produce un testo cifrato di 0 indipendentemente dai valori di e ed N utilizzati. Allo stesso modo, un singolo carattere ASCII SOH (il cui valore numerico è 1) produrrebbe sempre un testo cifrato di 1. Per i sistemi che usano convenzionalmente piccoli valori di e, come 3, tutti i messaggi ASCII a carattere singolo codificati usando questo schema sarebbero insicuri, poiché il più grande m avrebbe un valore di 255, e 2553 è meno di qualsiasi modulo ragionevole. Tali testi in chiaro potrebbero essere recuperati semplicemente prendendo la radice del cubo del testo cifrato.

Per evitare questi problemi, le implementazioni pratiche di RSA tipicamente incorporano qualche forma di imbottitura strutturata e randomizzata nel valore m prima di cifrarlo. Questa imbottitura assicura che m non cada nella gamma dei testi in chiaro insicuri, e che un dato messaggio, una volta imbottito, verrà criptato in uno di un gran numero di diversi possibili testi cifrati. Quest'ultima proprietà può aumentare il costo di un attacco a dizionario oltre le capacità di un attaccante ragionevole.

Standard come il PKCS sono stati attentamente progettati per imbottire in modo sicuro i messaggi prima della crittografia RSA. Poiché questi schemi imbottiscono il testo in chiaro m con un certo numero di bit aggiuntivi, la dimensione del messaggio non imbottito M deve essere un po' più piccola. Gli schemi di imbottitura RSA devono essere attentamente progettati in modo da prevenire attacchi sofisticati. Questo può essere reso più facile da una struttura prevedibile del messaggio. Le prime versioni dello standard PKCS usavano costruzioni ad-hoc, che in seguito si sono rivelate vulnerabili ad un pratico attacco adattativo al cifrario scelto. Le costruzioni moderne usano tecniche sicure come l'Optimal Asymmetric Encryption Padding (OAEP) per proteggere i messaggi e prevenire questi attacchi. Lo standard PKCS ha anche schemi di elaborazione progettati per fornire ulteriore sicurezza per le firme RSA, ad esempio, lo schema di firma probabilistica per RSA (RSA-PSS).

Firma dei messaggi

Supponiamo che Alice usi la chiave pubblica di Bob per inviargli un messaggio criptato. Nel messaggio, lei può affermare di essere Alice, ma Bob non ha modo di verificare che il messaggio provenga effettivamente da Alice, poiché chiunque può usare la chiave pubblica di Bob per inviargli messaggi criptati. Quindi, per verificare l'origine di un messaggio, RSA può anche essere usato per firmare un messaggio.

Supponiamo che Alice voglia inviare un messaggio firmato a Bob. Produce un valore di hash del messaggio, lo eleva alla potenza di d mod n (proprio come quando si decifra un messaggio), e lo attacca come "firma" al messaggio. Quando Bob riceve il messaggio firmato, eleva la firma alla potenza di e mod n (proprio come quando si cripta un messaggio), e confronta il valore hash risultante con il valore hash effettivo del messaggio. Se i due concordano, egli sa che l'autore del messaggio era in possesso della chiave segreta di Alice, e che il messaggio non è stato manomesso da allora.

Si noti che gli schemi di imbottitura sicura come RSA-PSS sono essenziali per la sicurezza della firma dei messaggi come lo sono per la cifratura dei messaggi, e che la stessa chiave non dovrebbe mai essere usata sia per la cifratura che per la firma.