Algoritmo RSA

Algoritmo RSA

Guzzo Antonio

Versione PDF del documento

Indichiamo con kpriB e kpubB la chiave privata e pubblica di Bob rispettivamente e con kpriA e kpubA la chiave privata e pubblica di Alice. Bob e Alice per comunicare devono entrambi rendere disponibili le loro chiave pubbliche. Se Bob deve mandare un messaggio ad Alice, cifra il messaggio M con la sua chiave privata e lo cifra di nuovo con la chiave pubblica di Alice: kpubA(kpriB(M)). Alice in ricezione applica la sua chiave privata per capire se il messaggio era proprio indirizzato a lei (annullando così l’effetto della sua chiave pubblica) dopodichè per verificare se il messaggio è stato inviato da Bob, applica la chiave pubblica di Bob (annullando così l’ effetto della chiave privata di Bob): kpubB(kpriA(kpubA(kpriB(M)))).
Con RSA la cifratura equivale ad un elevamento a potenza del tipo:
 
C = Me mod n
 
essendo (e,n) la chiave pubblica. Esistono i seguenti vincoli:
 
         M > n: non si può decifrare il messaggio. Infatti in decifratura si avrà M = Cd mod n che è un risultato compreso tra 0 e n – 1: in tale situazione il messaggio deve essere frammentato in messaggi più piccoli al più n -1.
         M < n: generalmente i messaggi sulla rete sono di 1024 bit cioè 128 byte (2048 per forme più importanti di cifratura). La grande maggioranza delle smart card oggi hanno chiavi di queste dimensioni.
 
Per esempio supponendo che il messaggio da inviare sia M = 30, il messaggio cifrato che Bob deve inviare ad Alice è:
 
C = (30dB mod mB)eA mod mA
 
Mentre alice in ricezione decodifica nel seguente modo:
 
M = (CdA mod mA)eB mod mB
 
essendo (eA,mA) e dA la chiave pubblica e privata di Alice rispettivamente e (eB,mB) e dB la chiave pubblica e privata di Bob rispettivamente.
Ovviamente la lunghezza delle chiavi deve essere uguale per entrambe le parti.
Un possibile attacco fa leva sul fatto che Alice non sa a priori che tipo di messaggio Bob le sta inviando: un attaccante può inviare ad Alice un messaggio spacciandosi per Bob, cioè può mandare un numero qualsiasi, cifrare con la sua chiave privata e poi ancora cifrare con la chiave pubblica di Alice. Alice in ricezione decifra con la sua chiave privata e poi con la chiave pubblica di Bob perché lei pensa che sia Bob a mandarle un messaggio: Alice riceverà così un numero senza senso pensando che questo si effettivamente il messaggio inviatole da Bob e non può stabilire a priori se è questo il valore che Bob voleva comunicarle. Per evitare ciò i soggetti che comunicano devono chiarirsi sul tipo di informazioni che si stanno inviando e sulla loro natura (ad esempio se si sta dando una riposta ad una interrogazione del tipo si o no).
 
Se Alice e Bob hanno una chiave di 128 byte, il messaggio più lungo che si può mandare per convenzione è di 100 byte (poi diventata una norma). Ciò evita un certo tipo di attacchi basati sul forzare il ricevente ad inviare risposte di un solo bit. Gli altri 28 byte si riempiono con una procedura detta di padding, che possono essere bit scelti secondo un certo criterio accodati dopo i 100 byte oppure mescolati all’ interno di essi. In ogni caso il messaggio non è mai diverso da 128 byte: se è più lungo con il trunking si frammenta in pacchetti più piccoli, se è più corto viene riempito di bit che implementano una certa struttura.
Nel caso di padding, l’ algoritmo RSA prevede che venga passato in input anche il valore del padding, cioè la cifratura è una funzione con due valori in ingresso, il messaggio M e il tipo di padding utilizzato: CYP_RSA(M,PADDING).
Quindi riassumendo, Bob e Alice devono utilizzare la stessa lunghezza delle chiavi e la tecnica di padding deve essere compatibile per entrambi.
 
I messaggi non si scambiano nella pratica utilizzando solo RSA ma attraverso una tecnica mista di crittografia simmetrica e asimmetrica, perché è molto dispendioso in termini di tempo macchina (si parla anche di decimi di secondo) implementare operazioni di elevamento a potenza: le comunicazioni SSL e HTTPS caricano molto i server sulla rete e a tale scopo sono state implementate tecniche di caching che riducono le comunicazioni di questo tipo a scapito comunque della sicurezza.
Più specificatamente se Bob vuole mandare un messaggio ad Alice genera un numero casuale kS di 128 bit che rappresenta la chiave simmetrica della sessione di comunicazione. Quindi Bob invia ad Alice la chiave simmetrica della sessione cifrata con la sua chiave privata e la chiave pubblica di Alice più il messaggio cifrato con la chiave simmetrica che le ha inviato:
 
C = kpubA(kpriB(kS)) + kS(M)
 
Alice per decifrare applica la sua chiave privata, successivamente la chiave pubblica di Bob, ottiene così la chiave simmetrica di sessione e con questa può decifrare il messaggio:
 
kS = kpubB(kpriA(kpubA(kpriB(kS))))→ M = kS(MC)
 
essendo MC la parte di C relativa alla cifratura di M (cioè MC = kS(M) ). Algoritmi più usati per la cifratura simmetrica sono AES o 3DES. In questo modo è possibile mandare messaggi molto lunghi sulla rete mantenendo la sicurezza della cifratura asimmetrica con l’aggiunta che la chiave di sessione varia da messaggio a messaggio e quindi un eventuale attaccante dovrebbe rompere la chiave ad ogni messaggio. La forza della cifratura asimmetrica risiede nella complessità dell’ aritmetica modulare e nella difficoltà della scomposizione di un numero sufficientemente grande in fattori.
 
 
a cura del Dottor Antonio Guzzo
Responsabile CED – Sistemi Informativi del Comune di Praia a Mare

© RIPRODUZIONE RISERVATA


Per la tua pubblicità sui nostri Media:
maggioliadv@maggioli.it  |  www.maggioliadv.it

Gruppo Maggioli
www.maggioli.it