La crittografia: Algoritmi a chiave pubblica o crittografia asimmetrica

Con questo tipo di crittogafia è stato risolto il problema della gestione delle chiavi che non occorre più trasmettere al destinatario del messaggio per la decodifica. Il concetto di crittografia simmetrica è stato introdotto nel 1976 da Whitfield Diffie e Martin Hellman e si basa sul concetto fondamentale che un messaggio codificato con una precisa chiave pubblica può essere decodificato SOLO dalla corrispondente chiave privata che è unica ed associata strettamente a quella pubblica; ciò si basa anche su un dato matematico per cui, impiegando 1024 bits, per ottenere la (unica) chiave segreta da quella pubblica occorrerebbe una potenza di calcolo pari a una rete di milioni di computer al lavoro per 1000 anni! Gli algoritmi a chiave pubblica, per la loro lentezza, sono usati spesso per cifrare la chiave di sessione con cui verrà codificato il messaggio usando la crittografia simmetrica.

Diffie-Hellmann
Nel 1976 due crittologi americani, Diffie ed Hellmann, pubblicarono un fondamentale lavoro teorico nel quale, ipotizzando di poter disporre di un cifrario "asimmetrico", dimostravano la fattibilità di sistemi crittografici di nuovo tipo, adatti alla crittografia di massa mediante il concetto delle "chiavi pubbliche".
Questo algoritmo è stato sotto brevetto fino al 29/4/97. Basa la sua difficoltà di decodifica sui problemi logaritmici. E' considerato sicuro con chiavi lunghe e generatori adatti.

RSA
Nato a due anni dal Diffie-Hellman (e brevettato il 29/9/1983 , scadenza nel 2000 in USA, libero nel resto del mondo), questo algoritmo è ancora oggi molto usato (dato in licensa a 350 compagnie, conta un numero di motori di codifica installati pari a circa 300 milioni). L'acronimo individua le iniziali degli inventori, i tre ricercatori del MIT Ron Rivest, Adi Shamir e Leonard Adleman. La sua potenza si basa sull'estrema difficoltà di ricreare la chiave segreta da quella pubblica basandosi su funzioni unidirezioni e quindi invertibili ma tali che la funzione diretta sia banale, ma quella inversa sia estremamente difficoltosa. Ecco un esempio che dovrebbe chiarire e che è appunto l'idea su cui si basa l'RSA: è facilissimo trovare il prodotto di due numeri molto grandi, ma dato il prodotto sarà estremamente difficoltoso trovarne i 2 fattori primi. Illustriamo i passaggi e l'esempio (che sarà fatto con numeri piccoli per non complicare):

1) Prendiamo due numeri primi p(=3) e q(=11) molto grandi ed n(=33) sia il loro prodotto.

2) Prendiamo e(=3) che deve essere: minore di n, dispari e primo con (p-1)(q-1). [ (p-1)(q-1)=(3-1)(11-1)=2*10=20 ]

3) Calcolare d(=7) in modo che: d*e=1 MODULO (p-1)(q-1). Significa che d*e diviso (divisione intera) (p-1)(q-1) dà come risultato 1. Infatti d*e=3*7=21/20=1.

4) Cifriamo il testo con c=(t^e) MODULO p*q. t, intero positivo, è il testo in chiaro. il risultato c è il testo cifrato.

La chiave pubblica conterrà n ed e(esponente pubblico), quella privata n e d(esponente privato).

Se t sono i numeri da 0 ad 8, li cifreremo elevandoli alla terza e facendo il risultato modulo 33.

plain-text - cipher-text
0 _____________ 0
1 _____________ 1
2 _____________ 8
3 _____________ 27
4 _____________ 31 4*4*4=64 MODULO 33 = 31
5 _____________ 26 5*5*5=125 MODULO 33 = 125-(33*3)=26
6 _____________ 18 6^3=216-(33*6)=18
7 _____________ 13 7^3=343-(33*10)=13
8 _____________ 17 8^3=512-(33*15)=17

La chiave per l'RSA è il modulo n. Più è grande la chiave, più sarà sicura (ma lenta) la cifratura. Con 1024 bits si è abbastanza (molto?) sicuri. Per craccare un RSA a 256 bits basta un potente home computer; andando a 384 bits servirebbe un'organizzazione universitaria o una grande azienda; la crittografia a 512 bits può essere superata da agenzie statali. Solo chiavi a 2048 bits possono ritenersi sicure per qualche anno a ogni livello (e chissà...).
Se volessimo usare un sistema ibrido si potrebbero usare RSA e DES. Con il DES produciamo una chiave casuale (che cifreremo con l'RSA) che servirà per crittare il messaggio in maniera simmetrica. Spedisco poi il messaggio e la chiave DES cifrata con la chiave pubblica RSA al suo proprietario che con la sua chiave segreta decritterà prima la chiave che impiegherà per decodificare il messaggio. Questo si fa perchè DES è da due (a livello software) a 4/5 ordini (a livello hardware) di grandezza più veloce dell'RSA.

Fattorizzato RSA-129
Nel marzo 1994, usando 1600 computer connessi a Internet, Atkins e altri fattorizzarono un numero di 129 cifre (426 bits) in 8 mesi di lavoro. Una studio del 1997 stimava in un milione di dollari il costo per forzare un RSA con chiave a 512 bits.
Curiosità: il numero di numeri primi minori o uguali a n è asintotico a n/ln n. Quindi il numero di numeri primi di lunghezza minore o uguale a 512 bits è di circa 10^150, cioè più grande del numero degli atomi dell'universo conosciuto. Questo la dice lunga sull'enorme disponibilità di chiavi diverse.

Fattorizzato RSA-140
Notizia del marzo 1999 apparsa sul mensile Crypto-Gram: è stato fattorizzato un RSA-140. Un nuovo record è stato stabilito da Herman Riele e il suo gruppo ad Amsterdam avendo fattorizzato un numero di 140 cifre (456 bit). Questo numero è stato una delle sfide dell'RSA, era il prodotto di due numeri primi molto grandi, proprio il tipo di numeri usati nel criptosistema RSA.
La mole di lavoro è stata stimata in 2000 anni-mips (mips=milioni di istruzioni al secondo, un anno-mips corrisponde alla potenza di calcolo di una macchina che macina per un anno un milione di istruzioni al secondo. Un DEC 11/780 è una macchina mips. Un Pentium II di fascia alta è una macchina da 200 mips. Il supercomputer per simulare esplosioni nucleari installato al Sandia National Laboratory è una macchina da 1.8 milioni di mips).
Per l'impresa è stato usato un algoritmo detto "a setaccio di numeri", lo stesso usato per fattorizzare un RSA-130 impiegherebbe 1000 mips-anni, per un RSA-150 1500 mips-anni. L'algoritmo non scala come ci si aspetterebbe, ma le tecniche di fattorizzazione diventano sempre più efficienti e veloci perchè i computer diventano sempre più veloci, le macchine possono lavorare in rete, gli algoritmi migliorano continuamente di pari passo alle ricerche di matematica.
E' stato già avviato un progetto per fattorizzare un RSA-155 (512 bit) che sarà pronto a breve.

Fattorizzato RSA-155
Sono stati un pò più veloci della fine d'anno promessa e così è il 22 agosto quando il solito Herman Riele annuncia l'impresa compiuta ad Amsterdam su un numero da 155 cifre (512 bit) del tipo degli stessi usati per l'RSA in quanto prodotto di due fattori primi da 78 cifre. 300 macchine tra workstation SGI e PC Pentium hanno lavorato alacremente per sette mesi durante la notte e i weekend. Usando il solito algoritmo a setaccio si sono impiegati 8000 anni-mips in 3.7 mesi per la fase cosiddetta "di setaccio" e 224 ore-CPU e 3.2 Gigabytes di memoria per la seconda fase di riduzione matriciale su un Cray C916.
Lo sforzo è stato 50 volte più facile che craccare il DES. Fattorizzare le chiavi usate per il commercio elettronico è sempre più facile e lo sarà ancor di più in futuro. Questa impresa deve mettere in allarme perchè la maggior parte dei protocolli sicuri usati in Internet usano RSA a 512 bits. Grosse e medie società come Compaq e Microsoft usano ancora per i loro magazzini on-line l'RSA a 512 bit. Occorre inoltre riflettere sul fatto che è probabile che qualche organizzazione in segreto già forzi abitualmente comunicazioni private e/o segrete.