L’algoritmo RSA e altri algoritmi

 

Il più conosciuto e utilizzato algoritmo a chiavi asimmetriche è stato proposto da Rivest, Shamir e Andleman nel 1978 e porta come nome la sigla dei cognomi dei suoi inventori. L’algoritmo sfrutta l’approccio di Diffie/Hellman e si basa sulla fattorizzazione di numeri interi grandi.
 
[adsense:block:adcontenuto]
 
Un destinatario Y di messaggi sicuri, per poter generare la propria coppia di chiavi, effettua i seguenti passaggi:
  • 1. Sceglie due grandi numeri interi p e q, entrambi numeri primi; il valore N = p*q verrà utilizzato per le operazioni di modulo durante la cifratura.
  • 2. Sceglie un intero e<N che sia primo rispetto al valore b = (p-1)*(q-1) (cioè e non ha fattori comuni diversi da 1 sia con (p-1) che con (q-1)).
  • 3. Trova il più piccolo intero d per il quale il valore (e*d-1) è divisibile per b, cioè (e*d) mod b = 1
  • 4. La chiave pubblica è pari a Kyp = [N, e], la chiave privata Kys = [N, d]; i fattori p e q possono essere distrutti o mantenuti segreti assieme alla chiave privata.

[adsense:block:adcontenuto]

L’algoritmo di cifratura richiede che il messaggio venga suddiviso in blocchi di m bit con m £ log2 N (cioè il valore numerico espresso da ciascun blocco deve essere £ N); detto mi un generico di questi blocchi, la versione cifrata mi’ è ottenuta come:
 
mi’ = mi
e mod N
 
Per la decifratura, si applica un calcolo analogo, ma con l’altro esponente, a ciascun blocco cifrato per riottenere quello in chiaro:
 
mi = mi’d mod N
 
Esempio (con numeri piccoli):
 
p=5, q=11 N = p*q = 55 b = 4*10 = 40
 
(poiché p e q sono sempre dispari, b è sempre divisibile per 4) e = 13 (13*d) mod 40 = 1 il più piccolo intero d che soddisfa l’eguaglianza è d = 37
 
Kyp = [55, 13] Kys = [55, 37]
 
se M = $3A90256C ($ sta per esadecimale) si può decidere di cifrare blocchi di 4 bit, corrispondenti a 1 cifra esadecimale (infatti 4 < log2 55 = 5.7; si poteva arrivare fino a 5 bit, mentre il cifrato ha necessariamente blocchi di 6 bit per rappresentare valori nell’intervallo [0,54])
 
m0’ = ($C)13 mod 55 = (12)13 mod 55 = 12 = $0C m1’ = (6)13 mod 55 = 51 = $33
m2’ = (5)13 mod 55 = 15 = $0F m3’ = (2)13 mod 55 = 52 = $34
m4’ = (0)13 mod 55 = 0 m5’ = (9)13 mod 55 = 14 = $0E
m6’ = ($A)13 mod 55 = (10)13 mod 55 = 10 = $0A m7’ = (3)13 mod 55 = 38 = $26
 
[adsense:block:adcontenuto]
 
Il valore cifrato che si ottiene è una sequenza di 6*8=48 bit ottenuti giustapponendo i blocchi di 6 bit cifrati:
 
M’ = $26 | $0A | $0E | 0 | $34 | $0F | $33 | $0C = (binario) %100110 001010 001110 000000110100 001111    110011 001100 =
= $98A380D0FCCC
 
Per la decifratura si ottiene:
 
m0 = ($0C)37 mod 55 = (12)37 mod 55 = 12 = $C m1 = ($33)37 mod 55 = (51)37 mod 55 = 6
m2 = ($0F)37 mod 55 = (15)37 mod 55 = 5 m3 = ($34)37 mod 55 = (52)37 mod 55 = 2
m4 = (0)37 mod 55 = 0 m5 = ($0E)37 mod 55 = (14)37 mod 55 = 9
m6 = ($A)37 mod 55 = (10)37 mod 55 = 10 = $A m7 = ($26)37 mod 55 = (38)37 mod 55 = 3
 
La sicurezza dell’algoritmo è basata sulla elevata difficoltà computazionale a ricavare i fattori p e q da un valore N grande, essendo quest’ultimo noto perché parte della chiave pubblica: il problema della fattorizzazione di un valore grande in due fattori primi, in particolare se questi sono grossomodo della stessa grandezza ma non così prossimi l’un l’altro, è ritenuto un problema difficile.
 
[adsense:block:adcontenuto]
 
In base a recenti ricerche che, in merito al problema della fattorizzazione con chiavi di 512 bit, hanno ottenuto risultati di quest’ordine: hardware del costo inferiore a 1 M$, 7-8 mesi di calcolo, oggi si può affermare che chiavi di 1024 o più bit sono ragionevolmente sicure per la maggior parte delle esigenze. Occorre tener però presente, come si evince dalla formula per la cifratura e decifratura, che più grandi sono le chiavi in gioco, maggiore è il tempo necessario per queste operazioni a parità di messaggio.
 
Sono stati proposti anche altri algoritmi come quello di ElGamal (1985) ancor più vicino rispetto a RSA al metodo di Deffie/Hellman, e quello delle curve ellittiche (il corpo numerico di base è in questo caso rappresentato dai punti di una curva ellittica definita su un campo finito) che ha un livello di sicurezza superiore a quello basato sulla fattorizzazione intera.

 

Risorse per sviluppo: 

Ti potrebbero anche interessare:

Crittografia moderna e avvento dei computer

 

La nascita della moderna informatica ha fatto fare un salto di qualità anche al settore crittografico: in particolare è stato possibile studiare nuove metodologie di trasformazione crittografica non più legate ai simboli del testo da trasmettere, ma riferentesi direttamente alla loro codifica binaria.
Risorse per sviluppo: 

Cifrario basato su macchinario e cifrario di Atbash

Il primo esempio di cifratura basata su un ‘macchinario’ si può far risalire ad una testimonianza tra il 360 e il 390 dovuta ad Enea il tattico, generale della lega arcadica, in un trattato di cifre il cui XXI capitolo tratta appunto di messaggi segreti. In questo viene descritto un disco sulla zona esterna del quale erano contenuti 24 fori, ciascuno corrispondente ad una lettera dell'alfabeto.

Risorse per sviluppo: