| Home / Indice sezione | www.icosaedro.it | |
Crittografia - Algoritmi a chiavi simmetriche
Aldo: Ciao, sapresti spiegarmi cos'è la crittografia?
Bruno: FREIR N ERAQRER VYYRTTVOVYR HA ZRFFNTTVB
Aldo: Non ho capito niente...
Bruno: Vuol dire che non hai studiato!
Aldo: Studiato cosa?
Bruno: Ma la crittografia!
(dai Dialoghi di Aldo e Bruno)
Gli algoritmi di crittazione a chiavi simmetriche sono i tradizionali sistemi di crittazione dove i due interlocutori concordano preventivamente un algoritmo e una chiave di crittazione, sicché poi possono continuare il loro dialogo scambiandosi messaggi dal contenuto incomprensibile agli eventuali intercettatori. L'unica chiave di cui hanno bisogno è l'informazione necessaria sia per crittare, sia per decrittare il messaggio. Se gli interlocutori sono più di due e utilizzano lo stesso algoritmo, allora ogni coppia dovrà concordare una chiave diversa.
In questa sezione passeremo in rassegna alcuni algoritmi crittografici elementari, in modo da familiarizzare con alcuni concetti fondamentali, per poi arrivare agli algoritmi crittografici moderni.
Questa è una tecnica buona solo per il manuale delle giovani marmotte, se impiegata da sola. L'algoritmo di crittazione si esprime facilmente così:
Dati iniziali: un messaggio e una tabella di conversione m che trasforma ogni simbolo in un altro; la particolare tabella usata è la chiave.
Algoritmo di crittazione: sostituire ogni simbolo del messaggio in chiaro con quello dato dalla tabella.
Algoritmo di decrittazione: sostituire ogni simbolo del messaggio crittato con quello della tabella inversa.
Esempio: Messaggio in chiaro:
VENDERE TUTTI I FONDI OBBLIGAZIONARI.
ACQUISTARE AZIONI AREA PAESI EUROPEI.
La tabella di conversione scelta per questo esempio, ovvero la chiave di crittazione, è la seguente: ad ogni lettera, sostituire la lettera che si trova 13 posizioni più avanti; alla lettera Z segue la lettera A:
m | |
| Indice | Valore |
|---|---|
A |
N |
Il messaggio crittato risulta essere:
IRAQRER GHGGV V SBAQV BOOYVTNMVBANEV.
NPDHVFGNER NMVBAV NERN CNRFV RHEBCRV.
Esercizio: decrittare il messaggio usando la tabella inversa.
La tabella m usata in questo esempio è la chiave di
crittazione per il popolare algoritmo noto nel mondo delle comunità
telematiche come ROT13. In questo ambito, ROT13 viene utilizzato
non per crittare (sarebbe troppo banale), ma solo per rendere un
messaggio non immediatamente leggibile; tipicamente il destinatario viene
preventivamente informato che il contenuto del messaggio potrebbe essere
greve od offensivo, per cui se vuole leggerlo dovrà fare una scelta
deliberata e poi dovrà decrittarlo. La scelta del numero 13 non
è casuale: la tabella inversa è uguale alla tabella diretta.
La Crittomacchina ROT13 qui sopra è un programma JavaScript inserito nella pagina: ricorda che l'interprete JavaScript deve essere abilitato nel tuo browser, altrimenti non funzionerà. Questo programma realizza la crittazione ROT13. Lettere maiuscole e lettere minuscole sono equivalenti. I caratteri diversi dalle lettere non vengono crittati.
| Scheda tecnica | |
|---|---|
| Denominazione: | Algoritmo di crittazione a sostituzione monoalfabetica |
| Autore: |
 Julius Caesar (Repubblica Romana, 50 a.c. circa) |
| Impieghi attuali: | Rot13, giochi enigmistici, gioco del disco combinatore. |
| Livello di sicurezza: | Nullo. |
| Spazio delle chiavi: | Considerando solo le 26 lettere dell'alfabeto, esistono 26! (26 fattoriale) combinazioni, cioè oltre 400 milioni di miliardi di miliardi di tabelle di crittazione. Si tratta di un numero immenso, ma sfortunatamente questo algoritmo non è robusto, perché il messaggio è facilmente decrittabile anche manualmente, od utilizzando il metodo dell'analisi della frequenze (qui non descritto). |
| Cenni storici: | Non è certo se l'inventore di questo algoritmo sia stato veramente Giulio Cesare, ma sicuramente il console romano lo utilizzò ampiamente per i dispacci militari durante la campagna di Gallia. A quel tempo, in cui poche persone conoscevano la scrittura, e in quei luoghi remoti, questo sistema aveva la sua efficacia. La tabella di conversione prevedeva lo scorrimento delle lettere preservandone l'ordinamento, proprio come abbiamo visto per il ROT13, con la differenza che lo scorrimento era di tre posizioni: quindi la A viene sostituita con la D, la B con la E, e così via. |
| Commenti: | Questa tecnica di crittazione elementare è però a fondamento di molte altre tecniche di crittazione più avanzate. |
Saltiamo a piè pari secoli e secoli di storia durante i quali pochi passi furono fatti per migliorare in modo decisivo le tecniche crittografiche, e veniamo a un perfezionamento della tecnica monoalfabetica noto come sostituzione polialfabetica.
Dati iniziali: il messaggio da crittare, una chiave di crittazione e una tavola di Vigenère, riprodotta qui sotto:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B B C D E F G H I J K L M N O P Q R S T U V W X Y Z A C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B D D E F G H I J K L M N O P Q R S T U V W X Y Z A B C E E F G H I J K L M N O P Q R S T U V W X Y Z A B C D F F G H I J K L M N O P Q R S T U V W X Y Z A B C D E G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F H H I J K L M N O P Q R S T U V W X Y Z A B C D E F G I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H J J K L M N O P Q R S T U V W X Y Z A B C D E F G H I K K L M N O P Q R S T U V W X Y Z A B C D E F G H I J L L M N O P Q R S T U V W X Y Z A B C D E F G H I J K M M N O P Q R S T U V W X Y Z A B C D E F G H I J K L N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M O O P Q R S T U V W X Y Z A B C D E F G H I J K L M N P P Q R S T U V W X Y Z A B C D E F G H I J K L M N O Q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U W W X Y Z A B C D E F G H I J K L M N O P Q R S T U V X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Z Z A B C D E F G H I J K L M N O P Q R S T U V W X Y |
Questa tabella quadrata si costruisce così: nella prima riga sono riprodotte le 26 lettere nel loro ordine alfabetico; le righe successive riportano lo stesso elenco spostato a sinistra di una posizione, e le lettere che "escono" dal margine sinistro vengono riportate in fondo alla stessa riga riempiendo così lo spazio vuoto che si era formato.
Algoritmo di crittazione: si considera la prima lettera del messaggio e la prima lettera della chiave; sulla tavola di Vigenère queste due lettere si usano come una sorta di coordinate cartesiane che individuano rispettivamente la riga che inizia con la prima lettera e la colonna che inizia con la seconda lettera; all'incrocio si trova la lettera da sostituire nel messaggio crittato. Per le altre lettere del messaggio si procede similmente, ma utilizzando le successive lettere della chiave; siccome in generale la chiave è più corta del messaggio, la stessa chiave verrà usata ripetutamente fino a completare la crittazione del messaggio.
Algoritmo di decrittazione: data la stessa tabella di Vigenère e la stessa chiave utilizzata per crittare, si procede similmente a prima esaminando in successione le lettere della chiave (che selezionano la riga) e le lettere del messaggio crittato (che vanno ricercate nella riga così scelta): individuata la lettera, la lettera che contrassegna quella colonna è la lettera cercata.
Esempio: parola chiave: "CIAO", messaggio in chiaro:
SI ATTACCA DOMANI.
Messaggio crittato:
UQ AHVICQC LOACVI.
Un modo semplice per ottenere il messaggio crittato è quello di scrivere tre righe: nella prima riga scrivo ripetutamente la chiave, nella seconda riga riporto il messaggio, e nella terza compongo il messaggio crittato:
CI AOCIAOC IAOCIA
SI ATTACCA DOMANI.
UQ AHVICQC LOACVI.
La prima lettera del messaggio crittato l'ho ottenuta considerando la prima lettera della chiave C e la prima lettera del messaggio in chiaro S; nella tavola di Vigenère individuo la riga che inizia con C e la colonna che inizia con S; all'incrocio trovo la lettera U. Similmente procedo con la altre lettere del messaggio.
La Crittomacchina Vigenère riprodotta qui sopra è un programma JavaScript inserito nella pagina: ricorda che l'interprete JavaScript deve essere abilitato nel tuo browser, altrimenti non funzionerà. Questo programma realizza la crittazione di Vigenère. Lettere maiuscole e lettere minuscole sono equivalenti. La chiave deve essere composta solo da lettere. Caratteri diversi dalle lettere non vengono crittati.
Osservazioni e suggerimenti utili per capire meglio l'algoritmo e i concetti della crittografia in generale:
| Scheda tecnica | |
|---|---|
| Denominazione: | Algoritmo di crittazione a sostituzione polialfabetica |
| Autore: |
 Blaise de Vigenère (Francia, 1562) |
| Impieghi attuali: | Nessuno. |
| Livello di sicurezza: | Discreto, a condizione che la chiave sia molto lunga (meglio se lunga almeno quanto il messaggio) e che il testo non contenga ridondanze interne e che i vari messaggi siano completamente diversi tra loro. Inoltre bisognerebbe cambiare spesso la chiave, meglio ancora se per ogni messaggio si usa una chiave diversa. Nella pratica sono tutte condizioni difficili da rispettare. |
| Spazio delle chiavi: | La chiave può avere lunghezza arbitraria, sicché lo spazio delle chiavi è infinito. Tuttavia non serve disporre di chiavi di grande lunghezza, perché al più vengono utilizzati solo un numero di caratteri della chiave pari alla lunghezza del messaggio, per cui i messaggi brevi sono attaccabili di forza bruta indipendentemente dalla lunghezza della chiave. |
| Cenni storici: | Vigenère basò il suo algoritmo di crittazione su vari studi precedenti, ma ebbe il merito di portare a compimento pratico la scoperta. Per secoli questo algoritmo fu ritenuto semplicemente "indecifrabile". Nel 1854 Charles Babbage trovò invece che l'algoritmo aveva almeno due debolezze: la ripetitività con la quale viene impiegata più volte la chiave, e le ricorrenze statistiche e prevedibili delle lettere. Babbage elaborò anche un algoritmo che permetteva la decrittazione dei messaggi, ma non lo divulgò mai (forse a vantaggio del suo paese). Nel 1863 e in modo indipendente, Friedrich Wilhelm Kasiski, ufficiale in pensione dell'esercito prussiano, riscoprì l'algoritmo che forzava il codice di Vigenère. Anche quando la chiave è lunga più del messaggio, è comunque possibile individuare nel messaggio crittato parole o sequenze di lettere tipiche della lingua originaria nella quale era stato scritto, che aiutano nella forzatura della crittazione. L'algoritmo di Vigenère opportunamente perfezionato, costituì la base di altre soluzioni crittografiche più complesse. |
| Commenti: | Di interesse più che altro storico, dato che venne ampiemente impiegato e resistette così a lungo agli attacchi dei crittoanalisti. |
Nel 1918 l'inventore tedesco Arthur Scherbius mise a punto una macchina
elettromeccanica che chiamò Enigma: essa si presentava con una
tastiera simile a una macchina per scrivere, e una serie di dischi
scambiatori realizzavano la combinazione cifrante. Tutto l'insieme
formava una complessa macchina crittografica di uso pratico (nella
foto a sinistra, la macchina Enigma con a corredo una scatola di
dischi scambiatori). Il governo tedesco ne commissionò migliaia
di pezzi per l'uso estensivo in ambito diplomatico e militare. I
servizi segreti Alleati, che nel corso della Prima Guerra Mondiale
riuscivano a decrittare sistematicamente tutte le comunicazioni tedesche,
improvvisamente piombarono nel buio più fitto: è da questo
periodo critico che forse origina la connotazione quasi leggendaria di
questa macchina misteriosa.
La vicenda, a questo punto, si tinge di giallo: l'approssimarsi della guerra e il successivo periodo di Guerra Fredda, hanno consentito solo molti anni dopo di fare luce su quello che avvenne realmente in quel periodo [SINGH99]. Ma il succo della questione è che già nel 1934 i servizi segreti polacchi erano in grado di decrittare i dispacci tedeschi in transito tra Mosca e Berlino, e perciò conobbero con un certo anticipo le sorti che attendevano il loro paese. Nell'agosto del 1939, appena due settimane prima dell'invasione tedesca, due delle macchine utilizzate per decrittare, dette Bombe, furono consegnate agli alleati inglese e francese, che, con loro grande stupore, vennero così a conoscenza della scoperta polacca. I tedeschi, ignari, nel corso della guerra si limitarono a pochi aggiornamenti alla loro macchina Enigma, ma nuove e più perfezionate "Bombe" dei servizi segreti inglesi erano già pronte al lavoro...
Il fatto curioso che interessa ai fini di questi documenti, è che la macchina Enigma era ancora in vendita ed ampiamente utilizzata parecchi anni dopo la fine della guerra: gli stessi servizi segreti Alleati evevano tutto l'interesse ad alimentarne il mito per sfruttarlo a loro vantaggio.
Negli ultimi decenni la scienza della crittografia è uscita almeno in parte dagli ambienti spionistici, e sono oggi disponibili tante soluzioni crittografiche diverse prodotte da soggetti indipendenti; inoltre, gli algoritmi utilizzati vengono sempre resi pubblici, così permettendo agli esperti di confrontarli e di verificarne la qualità.
Progettato da IBM nei primi anni del 197X con il nome di "Lucifer", utilizzava chiavi a 112 b, ed era concepito essenzialmente per realizzare dispositivi hardware per la crittazione. Dopo varie rielaborazioni, lo stesso algoritmo fu approvato standard federale degli USA nel 1977 con il nome di DES.
Tra le rielaborazioni fatte, la lunghezza della chiave era stata però ridotta a "soli" 56 b: tanti per i computer dell'epoca, ma pochi per resistere a macchine potenti espressamente costruite per un attacco di forza bruta. Solo molti anni dopo verrà rivelato che IBM lavorò in stretta collaborazione con l'NSA (il supersegreto ente USA che si occupa, tra l'altro, dei sistemi di crittazione) in modo che da una parte ne fosse rafforzato l'algoritmo (Lucifer soffriva di una debolezza rispetto ad una tecnica supersegreta nota come crittoanalisi differenziale di cui erano a conoscenza solo alla NSA [BIHAM]), e dall'altra facendo in modo che una chiave più corta permettesse comunque la decrittazione dei messaggi cifrati avvalendosi delle più potenti macchine di cui potevano disporre le istituzioni governative. Tutta la storia nei dettagli si può leggere in [GMZ99]. Comunque, per quello che ne sappiamo il DES rimane un algoritmo robusto, ed è rimasto in uso come standard tra gli uffici federali USA fino ai giorni nostri.
Nel 1997 l'RSA Data Security Inc. lancia una sfida all'interno della comunità crittografica internazionale per mettere alla prova vari algoritmi crittografici. Tra questi algoritmi c'è anche il DES che, con i sui 56 b, sembra essere l'osso più duro: cadrà dopo 96 giorni di calcolo da parte di un sistema di calcolo distribuito costituito da un migliaio di computer collegati in Internet, e messi a disposizione dei rispettivi proprietari desiderosi di partecipare alla sfida [DESCHALL98].
Dunque, come era stato previsto fin dal 1977, anno della sua introduzione, le chiavi del DES sono troppo corte per resistere ad un attacco di forza bruta condotto coi computer moderni, anche se l'impresa non è proprio alla portata di un singolo computer di casa. Tuttavia le critiche al DES per via della sua chiave troppo corta hanno portato alla definizione di altri algoritmi ben prima che la sfida lanciata da RSA dimostrasse ciò che tutti, nella comunità crittografica, già avevano capito. Il 3DES è solo una variante del DES, mentre l'AES si avvia a sostituire il DES per l'uso da parte delle istituzioni federali USA.
Esiste dunque un algoritmo crittografico inattaccabile, assolutamente sicuro al di là di ogni possibile dubbio? La risposta è sì ma un tale sistema ha un costo di gestione elevatissimo ed è decisamente scomodo: mi riferisco ai cifrari monouso. Ne esistono tante versioni, e qui provo a spiegarne il concetto usando come esempio un algoritmo veramente banale.
Se pensiamo a un messaggio da crittare come a un semplice numero, possiamo applicare ad esso le regole dell'aritmetica. Così avrà senso, per esempio, sommare 7 al messaggio M.
Aldo e Bruno si incontrano di persona e convengono una chiave di crittazione C e il seguente algoritmo di crittazione: X=M+C; l'algoritmo per la decrittazione è ovviamente M=X-C.
Facciamo un esempio numerico: supponiamo che i nostri due personaggi abbiano convenuto che sia C=5345, e che quindi si siano lasciati. Successivamente, Aldo ha necessità di inviare a Bruno il messaggio M=2339: l'operazione di crittazione produce il messaggio crittato X=M+C=2339+5345=7684, e poi questo numero viene inviato a Bruno attraverso un canale insicuro (magari scritto a biro dietro la cartolina di piazza S. Marco). Bruno procede alla decrittazione eseguendo M=X-C=7684-5345=2339, cioè ottiene il messaggio in chiaro.
Adesso valutiamo la sicurezza offerta da questo algoritmo. Lo spazio delle chiavi C è costituito dai numeri interi, compresi magari anche i numeri negativi, che sono infiniti: molto bene. Per quanto riguarda l'algoritmo, si tratta di una banale somma e una sottrazione, operazioni delle quali sappiamo tutto: anche qui possiamo stare tranquilli. Quali possibilità ha un intruso che abbia intercettato il messaggio X in transito, di poter ricostruire il messaggio in chiaro M? Direi proprio nessuna: l'unico modo di decrittare X è conoscere la chiave C; un attacco di forza bruta sarebbe perfettamente inutile: al variare di C sui numeri interi, si possono generare tutti gli infiniti possibili messaggi immaginabili, compresi quelli con un eventuale significato e il rispettivo contrario. Il nostro algoritmo crittografico risulta, almeno come principio, inattaccabile.
Esistono però difetti e diverse falle potenziali: io riesco a vederne almeno tre:
Un algoritmo di questo tipo e di uso più pratico, soprattutto nei
computer e nei sistemi di trasmissione digitali, consiste nell'eseguire
l'operazione logica nota come OR esclusivo (o "XOR") tra i byte del
messaggio in chiaro e i byte della chiave segreta: in pratica, i bit della
chiave segreta che valgono 1 comportano l'inversione del corrispondente
bit nel messaggio in chiaro. Un attacco di forza bruta che tentasse
di decrittare il messaggio provando tutte le possibili combinazioni di
chiavi segrete, otterrebbe solo di generare tutti i possibili messaggi
aventi la stessa lunghezza, senza possibilità di riconoscere, tra
tutti quelli generati, il messaggio in chiaro originale. Ad esempio, se il
messaggio crittato fosse lungo due byte, al variare della chiave segreta,
anch'essa a due byte, otterremmo tutti i possibili messaggi a due byte,
come SI, NO, OK, KO,
... senza alcuna possibilità di riconoscere, tra tutti questi
risultati contradditori, quello giusto. Di conseguenza questo algoritmo
è, almeno in principio, assolutamente sicuro. Soffre però
degli stessi difetti già descritti prima.
Gli algoritmi a cifrario monouso sono in assoluto i più sicuri, ma anche i meno pratici da usare, e pertanto vengono riservati solo agli ambiti in cui la sicurezza richiesta deve essere assoluta. Per tutte le altre applicazioni, si tratta semplicemente di una soluzione improponibile, e gli altri tipi di algoritmo, magari più complessi da applicare e da valutare sotto il profilo della sicurezza, restano comunque preferibili per via del rapporto costi/benefici decisamente più favorevole.
Molto prima che la debolezza della chiave DES venisse dimostrata, erano già in uso diverse soluzioni alternative. Una di queste consiste semplicemente nel riutilizzare DES crittando più volte consecutivamente il messaggio con diverse chiavi. Ad esempio, il 3DES usa tre chiavi a 56 b per un totale di 162 b per la chiave. Ovviamente, l'algoritmo 3DES diventa così tre volte più lento del DES e, sebbene più resistente ad un attacco di forza bruta, non offre lo stesso livello di sicurezza di un algoritmo di crittazione realmente in grado di supportare chiavi così lunghe. Si stima che la robustezza della chiave 3DES equivalga ad una chiave di almeno 112 b: un attacco di forza bruta richiederebbe un tempo pari a 256 volte quello necessario contro un semplice DES.
Algoritmo crittografico con chiave a 128 b ideato presso il politecnico
ETH di Zurigo da James L. Massey e Xuejia Lai e pubblicato nel 1990.
E' brevettato fino al 2007 e la licenza per l'uso deve essere richiesta a
Ascom Systec AG
(www.ascom.ch).
Algoritmo crittografico con chiave variabile da 32 b fino a 448 b progettato nel 1993 da Bruce Schneier [SCHNEIER93] come sostituto di DES o IDEA, ma senza brevetto, con licenza libera e senza diritti di sfruttamento. L'autore ha pubblicato l'algoritmo anche nel suo libro [SCHNEIER95].
Simile per funzionamento a DES, questo algoritmo crittografico è documentato nell'RFC 2144, che contiene vari riferimenti per gli approfondimenti. Creato da Carlisle Adams, supporta chiavi da 8 b fino a 128 b ed è liberamente utilizzabile.
Il NIST, l'istituto di standardizzazione USA, ha selezionato negli ultimi anni il candidato alla successione del DES, e ha infine scelto Rijndael come vincitore dopo una lunga serie di confronti e verifiche. Le specifiche tecniche del nuovo standard, che ora verrà chiamato anche AES (Advanced Encryption Standard), sono state pubblicate dal NIST nel febbraio 2001. AES può usare chiavi a 128, 192 o 256 b. Così come il DES, l'AES è un algoritmo di dominio pubblico destinato alle comunicazioni tra gli enti federali degli USA, ma sono già disponibili varie implementazioni di libreria per vari sistemi, e ci possiamo aspettare che diventerà una opzione diffusa in molte altre soluzioni crittografiche man mano che questo standard verrà riconosciuto a livello mondiale (ammesso che ciò avvenga, naturalmentre).
La home page ufficiale dei due progettisti di questo algoritmo è www.esat.kuleuven.ac.be/~rijmen/rijndael/, dove è anche reperibile una lista completa di tutte le implementazioni nei vari linguaggi.
I documenti RFC, che costituiscono la documentazione ufficiale di Internet,
sono reperibili in
www.rfc-editor.org.
www.interhack.net/projects/deschall/.
| Umberto Salsi | Commenti | Contatto | Mappa | Home / Indice sezione |
Still no comments to this page. Use the Comments link above to add your contribute.