________________________________________
L'RSA è un cifrario a chiave pubblica che permette di cifrare un messaggio attraverso un procedimento che sfrutta le proprietà dei numeri primi.
In termini molto semplici: fissati due numeri h ed n, che costituiscono la chiave pubblica, si considera un terzo numero d che costituisce la chiave privata (i dettagli sul calcolo di questi parametri sono esposti più giù). Sia m il messaggio da cifrare. L'operazione da compiere è la seguente:
c=mh mod n.
La chiave di decifrazione è costituita dal numero intero d, segreto, che permette di recuperare m grazie alla formula:
m=cd mod n.
L'RSA viene considerato oggi uno dei sistemi di crittografia più sicuri perchè, essendo violabile solo mediante attacchi di forza bruta, la rottura del codice richiederebbe tempi e risorse economiche elevatissimi. Ma i supercomputer di cui dispongono i grandi governi e le continue ricerche matematiche non ci garantiscono, chiaramente, la massima sicurezza.
Esporrò adesso, in termini più tecnici, i principi di funzionamento dell'RSA.
________________________________________
• Si determini la prima chiave n, prodotto di p e q, due numeri primi molto elevati, tali che la fattorizzazione di n sia estremamente difficile;
• Si calcoli dunque il valore della funzione di Eulero di n: b=phi(n)=(p-1)*(q-1) il cui valore rimane segreto; si scelga ancora un intero d tale che d e phi(n) siano primi tra loro (d non risulterà necessariamente primo, ma deve essere minore di phi(n)). Infine si trovi h che è il più piccolo x (intero) per cui (dx-1)/phi(n) é un numero intero.
In questo modo abbiamo determinato i numeri n, h e d di cui abbiamo già parlato.
Se chiamo k la quantità (dx-1)/phi(n), ottengo dx=dh=kphi(n)+1. Posso allora dimostrare perchè m=cd mod n:
Il codice RSA viene considerato sicuro perchè, essendo la formula di decifrazione basata su phi(n) calcolabile solo se a conoscenza di p e q, non esiste (o perlomeno non è noto) un algoritmo per scomporre n nei suoi fattori primi p e q in tempi accettabili. Bisognerebbe effettuare attacchi di forza bruta, provando cioè tutti i possibili casi. Fattorizzare un numero di 664 bit richiede almeno 1023 passi usando gli algoritmi più efficienti; per cui ipotizzando di avere una rete costituita da un milione di computer con ciascuno di loro che esegue un milione di passi al secondo, il tempo impiegato per fattorizzare n sarebbe dell'ordine dei 4000 anni. Se poi n fosse un numero a 1024 bit la stessa rete impiegherebbe 1010 anni per fattorizzarlo . Potrebbe sorgere il dubbio che esista un modo di calcolare phi(n) senza passare per p e q: questa ipotesi in effetti è verificabile ed è uno dei tanti motivi per non dare massima fiducia a questo algoritmo di cifratura.
________________________________________
Esempio
• n=p*q=5*7=35
• b=phi(35)=(5-1)(7-1)=24
• d=7 (primo con 24)
• k=(7x-1)/24 da cui: x=(k*24+1)/7
• Fisso k=2 in modo da ottenere un numero x intero. Quindi k=2 e x=h=7.
Ho trovato tutti i parametri che mi servivano e, a questo punto, suppongo che il messaggio da cifrare sia m=3. Procedo e calcolo:
c=mh mod n=37mod 35=2187 mod 35=17
Se adesso volessi decifrare il messaggio, essendo a conoscenza della chiave segreta d, procedo in questo modo:
m=cd mod n=177mod 35=3
________________________________________
Elevazione a potenza modulare
L’operazione dell’elevazione a potenza modulare consiste nel calcolare xy mod z dove x, y e z sono interi. Ma, lavorando con numeri estremamente grandi, gli elaboratori non sono in grado di eseguire da soli questi calcoli. E'allora necessario fare uso di algoritmi di calcolo che, benchè laboriosi, ci consentono di raggiungere il nostro scopo. Al momento, per la realizzazione del mio programma di crittografia a chiave pubblica basato sull'RSA, sto utilizzando il metodo naive, sotto illustrato. Ma ritenendolo poco efficiente (richiede un enorme lavoro della CPU) penso che lo sostituirò con un altro più veloce.
Metodo naive
Si può schematizzare questo metodo con il seguente algoritmo:
a=1
for i=1 to y do
a=(a*x)mod z
next
In pratica si calcola a=(a*x)mod z ripetendo l'operazione y volte. A questo punto il valore finale di a sarà il risultato di xy mod z, che abbiamo ottenuto evitando di lavorare con numeri troppo grandi. Tale algoritmo non è comunque molto efficiente, essendo il numero di cicli da eseguire uguale ad y. I metodi realmente utilizzati sono 2: il metodo "Left to right" e il metodo "Right to left". Ma parlerò in seguito di questi algoritmi, essendo ancora miei attuali argomenti di studio.
________________________________________
Attacchi RSA
Osserviamo che per un crittoanalista rompere l'RSA equivale a calcolare (n). Infatti, se n e (n) sono conosciuti ed n è il prodotto di due primi p e q, n può essere facilmente fattorizzato risolvendo il seguente sistema di 2 equazioni in 2 incognite: n = p q e (n)= (p - 1)(q - 1). Nelle due incognite p e q. Sostituendo q = n / p nella seconda equazione se ne ottiene un’unica di secondo grado nella sola incognita p:
p2 - (n - (n) + 1)p + n = 0.
Le due radici di questa equazione sono i fattori p e q. Quindi se un crittoanalista conosce il valore di (n) può fattorizzare n e rompere il sistema.
Esempio Supponiamo che il crittoanalista conosca (n) = 84754668 e n = 84773093.Queste informazioni gli permettono di scrivere l'equazione: p2 - 18426p + 84773093 = 0. Risolvendo l’equazione si ottengono le due radici 9539 e 8887 che rappresentano i fattori p e q di n.
Blowfish
________________________________________
Blowfish è un cifrario a blocchi sviluppato da Bruce Schneier, autore del famoso libro Applied Cryptography. Blowfish opera su blocchi di 64 bits con chiavi di lunghezza variabile fino a 448 bits. Questo algoritmo utilizza varie tecniche tra le quali la rete Feistel, le S-box dipendenti da chiavi e funzioni non invertibili che lo rendono, forse, l’algoritmo più sicuro attualmente disponibile. Non si conoscono al momento attacchi nei suoi confronti.
Il cifrario DES
________________________________________
DES sta per Data Encryption Standard ed e' un cifratore a blocco iterativo sviluppato alla IBM e definito dal governo degli Stati Uniti come standard ufficiale nel 1977. La dimensione dei blocchi DES e' di 64 bit, ed usa una chiave a 56 bit (16 cicli) durante la cifratura (gli altri 8 bit servono per la correzione degli errori). Questo algoritmo è stato violato soltanto grazie all’enorme potenza di calcolo dei moderni elaboratori. Il 17 luglio 1998, l’EFF (Electronic Frontier Foundation) ha realizzato una scheda multiprocessore in grado di violare un sistema DES a 64 bit in meno di tre giorni, generando tutte le 2^56 chiavi possibili. Questa scheda è basata sull’utilizzo di alcuni chip chiamati "Deep Crack", estremamente veloci perchè presentano tutte le operazioni da eseguire già implementate sull'hardware.
Crittoanalisi
________________________________________
Analisi delle frequenze
Nel caso dei cifrari monoalfabetici, ad ogni lettera se ne sostituisce un'altra secondo opportune regole. Se ad esempio sostituissimo la c con la x, la i con la y, poi a=r e o=b, potremmo scrivere la parola "ciao" come "xyrb". Sembra trattarsi di un sistema di crittografia estremamente sicuro e, in primo luogo, piuttosto difficile da violare. In realtà è molto facile attaccarlo e violarlo: basta conoscere le proprietà statistiche del linguaggio con cui il testo è stato scritto. In questo modo non bisogna fare molta fatica per rivelare esattamente tutto il contenuto reale del crittogramma. Tonycrypt ha creato un programma che consente di effettuare automaticamente e rapidamente l'analisi delle frequenze di un testo. Si tratta di un programma gratuito disponibile nella sezione download o scaricabile cliccando qui. Per realizzare lo schema delle frequenze con cui si presentano le lettere della lingua italiana, abbiamo pensato di analizzare un testo sufficientemente lungo: la Convenzione di Ginevra relativa al trattamento dei prigionieri di guerra. Ecco dunque uno schema della ricorrenza delle lettere della lingua italiana:
Ecco i valori non approssimati (nel grafico dobbiamo tener conto anche dell'estetica, dunque riportiamo solo i valori interi) delle frequenze letterarie in lingua italiana: Lettera a: 9,651 %; Lettera b: 0,481 %; Lettera c: 3,469 %; Lettera d: 4,142 %; Lettera e: 12,791 %; Lettera f: 0,929 %; Lettera g: 1,9984 %; Lettera h: 0,517 %; Lettera i: 12,730 %; Lettera j: 1,584E-03 %; Lettera k: 7,921E-04 %; Lettera l: 5,809 %; Lettera m: 2,031 %; Lettera n: 7,690 %; Lettera o: 8,760 %; Lettera p: 3,018 %; Lettera q: 0,350 %; Lettera r: 8,140 %; Lettera s: 4,835 %; Lettera t: 7,290 %; Lettera u: 2,685 %; Lettera v: 1,283 %; Lettera w: 0 %; Lettera x: 0 %; Lettera y: 0 %; Lettera z: 1,387 %;
Supponiamo adesso di trovarci davanti ad un testo cifrato in cui si è deciso di sostituire la a con la x, la e con la y e così via. E supponiamo che il testo originale, in chiaro, fosse scritto in italiano. Sottoponiamo tale testo ad un'analisi delle frequenze. Troveremo che la x presenta una ricorrenza vicina al 9%, la y intorno al 12% e così via. Confrontando tali risultati con la soprastante tabella delle ricorrenze tipiche della lingua italiana, immediatamente ci si accorge della sostituzione effettuata.
Vediamo un esempio pratico di quanto appena esposto: supponiamo di trovarci davanti al seguente testo:
YHUVRODPHWDGHJOLDQQLXQILVLFRLQJOHVHGDYLGGHXWVFKGXUDQWHXQDFRQIHUHQCD VXOODILVLFDTXDQWLVWLFDHEEHOLGHDGLFUHDUHXQFDOFRODWRUHTXDQWLVWLFRTXHV WDHXQDLGHDULYROXCLRQDULDLQTXDQWRLFDOFRODWRULWUDGLCLRQDOLVLFRPSRUWDQ RVHFRQGROHOHJJLGHOODILVLFDFODVVLFDHTXLQGLFRQOHOLPLWDCLRQLFKHQRLWXWW LFRQRVFLDPRPDXQFDOFRODWRUHTXDQWLVWLFRDYUHEEHXQDSRWHQCDGLFDOFRORWHRU LFDPHQWHLQILQLWDWDOHGDSRWHULQYHUWLUHXQDOJRULWPRDIDWWRULCCDCLRQHFRPH OUVDSUHVVRFKHLVWDQWDQHDPHQWHUHQGHQGRTXLQGLDVVROXWDPHQWHLQXWLOLLVLVW HPLGLFULWWRJUDILDDOJRULWPLFDODVSLHJDCLRQHGHOIXQCLRQDPHQWRGLXQFDOFRO DWRUHTXDQWLVWLFRHFRVDDVVDLFRPSOHVVDHQRQHGHWWRFKHVLSRVVDUHDOLCCDUHLQ SUDWLFDDOPHQRLQWHPSLEUHYLDQFKHVHVLVRVSHWWDFKHJOLXVDQHDEELDQRJLUHDOL CCDWRHVHPSODULPDDQFKHVROROLSRWHVLGLXQDVXDIXWXUDUHDOLCCDCLRQHSRQHGHL VHULLQWHUURJDWLYLVXOOXWLOLCCRGHOODFULWWRJUDILDDOJRULWPLFDVSHFLDOPHQ WHSHUTXHLGRFXPHQWLFKHGHYRQRULPDQHUHULVHUYDWLSHUXQSHULRGRGLWHPSRDEED VWDQCDOXQJRTXLQGLDOODOXFHGLTXHVWRIDWWRVLLPSRQHXQUDGLFDOHFDPELDPHQWR GLVWUDWHJLDQHOODFULWWRJUDILDDWWXDOHQRQEDVWDSLXDXPHQWDUHODOXQJKHCCDG HOOHFKLDYLSHUUHQGHUHVLFXURXQGRFXPHQWRSHULSURVVLPLDQQLVHPSUHQHOOLSRW HVLGLDYYHQWRGHOFDOFRODWRUHTXDQWLVWLFRPDELVRJQDULFRUUHUHDTXDOFRVDGLF RPSOHWDPHQWHQXRYR
Effettuiamo un'analisi di frequenze di tale testo mediante il programma Frequency che ho sviluppato per Tonycrypt:
A questo punto non è necessaria grande intelligenza per capire cosa sta succedendo. Tutto l'andamento delle frequenze risulta traslato di 3 lettere. Chi ha cifrato il testo si è limitato ad effettuare un offset di 3 posti, utilizzando il codice di Cesare. La lettera d presenta una frequenza di 11 %, confrontabile, nella tabella della lingua italiana, a quella della a=9 %. Nel testo cifrato h=10 % mentre in lingua italiana e=12 %. Nel testo cifrato l=11 % mentre in lingua italiana i=12 %. E così via: tutto il testo originale è stato sottoposto ad un offset di 3 posti. A questo punto non ci resta che procedere inversamente. Decifriamo applicando il codice di Cesare al contrario, cioè con un offset di 26-3=23 posti (potete provare voi stessi dalla pagina dedicata al codice di Cesare). Risultato:
VERSOLAMETADEGLIANNIUNFISICOINGLESEDAVIDDEUTSCHDURANTEUNACONFERENZASULLAFIS ICAQUANTISTICAEBBELIDEADICREAREUNCALCOLATOREQUANTISTICOQUESTAEUNAIDEARIVOLU ZIONARIAINQUANTOICALCOLATORITRADIZIONALISICOMPORTANOSECONDOLELEGGIDELLAFISI CACLASSICAEQUINDICONLELIMITAZIONICHENOITUTTICONOSCIAMOMAUNCALCOLATOREQUANTI STICOAVREBBEUNAPOTENZADICALCOLOTEORICAMENTEINFINITATALEDAPOTERINVERTIREUNAL GORITMOAFATTORIZZAZIONECOMELRSAPRESSOCHEISTANTANEAMENTERENDENDOQUINDIASSOLU TAMENTEINUTILIISISTEMIDICRITTOGRAFIAALGORITMICALASPIEGAZIONEDELFUNZIONAMENT ODIUNCALCOLATOREQUANTISTICOECOSAASSAICOMPLESSAENONEDETTOCHESIPOSSAREALIZZAR EINPRATICAALMENOINTEMPIBREVIANCHESESISOSPETTACHEGLIUSANEABBIANOGIREALIZZATO ESEMPLARIMAANCHESOLOLIPOTESIDIUNASUAFUTURAREALIZZAZIONEPONEDEISERIINTERROGA TIVISULLUTILIZZODELLACRITTOGRAFIAALGORITMICASPECIALMENTEPERQUEIDOCUMENTICHE DEVONORIMANERERISERVATIPERUNPERIODODITEMPOABBASTANZALUNGOQUINDIALLALUCEDIQU ESTOFATTOSIIMPONEUNRADICALECAMBIAMENTODISTRATEGIANELLACRITTOGRAFIAATTUALENO NBASTAPIUAUMENTARELALUNGHEZZADELLECHIAVIPERRENDERESICUROUNDOCUMENTOPERIPROS SIMIANNISEMPRENELLIPOTESIDIAVVENTODELCALCOLATOREQUANTISTICOMABISOGNARICORRE REAQUALCOSADICOMPLETAMENTENUOVO
Naturalmente il sistema di analisi delle frequenze è applicabile al caso più generale in cui ad ogni lettera se ne sostituisce arbitrariamente un'altra, senza nessun tipo di regola. Il caso appena citato, dell'algoritmo di Cesare, è solo un esempio particolare di sostituzione monoalfabetica. Il programma Frequency è gratuito
Semplicissimo: basta andare sul sito ufficiale di Nero 9 Lite, inserire l’email nel campo proposto e cliccare sul pulsante Download con la freccia posto sulla destra del monitor.
Semplicissimo: basta andare sul sito ufficiale di Nero 9 Lite, inserire l’email nel campo proposto e cliccare sul pulsante Download con la freccia posto sulla destra del monitor.
