Crittografia quantistica

Preambolo
1
Volli, sempre volli, fortissimamente volli!
In uno dei famosi libri del ciclo della Fondazione scritto da Isaac
Asimovèraccontatounepisodiochecolpìmoltolamiaimmaginazio-
nediadolescente. UncittadinodellaFondazione,invisitasullaTerra
di un lontano futuro, veniva a conoscenza dell’esistenza di un’elite di
tecnici impegnati a fare funzionare ininterrottamente mastodontici
generatori di energia. Il loro incarico di supervisione assumeva un
aspetto sempre più religioso a mano a mano che la loro stessa casta
perdeva ogni cognizione scientificica del principio di funzionamento
degli impianti stessi.
Il visitatore, allibito, scoprì insomma che sulla Terra non resta-
va più nessuno in grado di comprendere la loro stessa tecnologia:
anche i cosiddetti tecnici non avrebbero saputo saputo intervenire
nell’eventualità di qualsiasi malfunzionamento.
Agli inizi dell’era dei personal computer, quando la massima
espressione tecnologica consentita dalla mia esperienza adolescen-
ziale si concretizzava in un arcaico VIC20, rimasi molto colpito da
quest’episodio di fantascienza e mi chiesi come fosse possibile, anche
solo immaginare, che la Conoscenza potesse fare dei passi indietro
anzichè in avanti.
Dopotutto, pensai allora, anche durante i peggiori conflitti che la
Storia ricordi Essa non si è mai fermata nel suo inesorabile cammino
se non della sua diffusione quanto meno del suo approfondimento. Si
è sempre arricchita di nuove scoperte e invenzioni che hanno segnato
spessoilcamminodell’Umanità. Unfamososcrittoredifantascienza,
invece, azzardava un futuro in cui la tecnologia si sarebbe ripiegata
su se stessa a causa della sua stessa mole.
Questa visione di Asimov, che all’epoca si scontrò con la mia en-
tusiastica percezione della tecnologia, oggi emerge in molti momenti
della nostra vita quotidiana di cittadini del XXI secolo. Non solo
vengono fagocitate ogni giorno nuove applicazioni tecnologiche il cui
funzionamento rasenta a volte il trucco di un prestigiatore occulto,
ma si perde traccia anche delle applicazioni già familiari nella loro
sfrenata corsa evolutiva.
La crittografia è una di queste. Le sue radici affondano nello stes-
so terreno che ha dato origine alla scrittura. Nel medesimo momento
in cui l’Uomo ha sviluppato un metodo per trasmettere e divulgare
il suo pensiero, con una potenza e una precisione irrangiungibili da
qualsiasi disegno rupestre, un metodo che gli consentiva di superare
i propri confini umani spazio-temporali, in quell’attimo ha fatto la
sua comparsa anche la necessità di limitare, all’occorrenza, l’aspetto
1
Vittorio alfieri
iii
divulgativo della scrittura. E, come in una sorta di Big Ben socio-
culturale, in quei primi istanti avvenne subito la separazione tra
crittografia e crittoanalisi: da una parte l’arte di occultare il signi-
ficato contenuto in un messaggio e dall’altra lo studio per violarne
gli stratagemmi e carpire il senso nascosto in una comunicazione
altrimenti incomprensibile.
Dopo un lungo periodo in cui la crittografia fu un’arte di nicchia
con un retaggio politico-militare e qualche sporadica comparsa in
ogni tempo in divertenti vicessitudini scolastiche, negli ultimi decen-
ni è fuoriuscita dalle stanze del potere, dalle aule accademiche e dai
giochi innocenti di fantasiose giovani spie in erba e ha cominciato
lentamente a colonizzare alcuni aspetti della nostra vita quotidia-
na senza che alcuno, a meno non fosse un addetto ai lavori, se ne
accorgesse. Oggi milioni di ignari utenti effettuano acquisti on-line,
aprono pagine web o quant’altro ancora senza immaginare nemmeno
cosa ci sia dietro quel semplice gesto.
Quando è capitato che mi venisse chiesto da conoscenti di parlare
della mia tesi, l’espressione iniziale corrugata di perplessità si rilas-
sava di fronte a semplici esempi di crittografia classica. Esempi che
costruivano un primitivo e fragile ponte tra la loro esperienza quo-
tidiana di cittadini del XXI secolo e le loro conoscenze appena suf-
ficienti a edulcorare l’argomento della tesi dall’ermeticità semantica
del suo stesso titolo.
Se nell’entusiasmo delle spiegazioni mi avventuravo nel territorio
misterioso dei quanti e dei numeri primi veniva a mancare il terreno
di qualsiasi esperienza quotidiana da cui lanciare anche un semplice
ponte tibetano.
Oggi si usano protocolli crittografici in diversi gesti comuni, ap-
punto, non solo senza conoscerne i principi di funzionamento ma
addirittura senza rendersene conto. Era perciò doveroso che il pri-
mo capitolo aprisse quanto meno uno spiraglio sul panorama della
crittografia ancora oggi in uso e assogettata alle leggi della fisica
classica.
La crittografia classica è quasi un vecchio continente che, pur
avendo scoperto da poco il nuovo mondo quantistico, non è rima-
sto dietro nè dimenticato, tutt’altro. Gli studi e le ricerche che la
riguardano sono ancora vivi e numerosi e tutti vanno ad arricchi-
re una complessa eredità teorica-pratica del ramo quantistico. Non
inganni perciò la sua qui modesta trattazione da intendersi non co-
me un semplice contributo a qualcosa ormai superato, bensì come
un’occhiata al dietro alle quinte di alcuni di quei trucchi sopra men-
zionati senza desiderio di soffermarsi troppo: dopotutto il titolo è
Crittografia quantistica.
Prima ancora di approdare del tutto al nuovo mondo dei quanti,
la crittoanalisi quantistica avvistò nuove opportunità contro i pro-
tocolli descritti nella crittografia classica. Veicolata dall’eccezionale
fenomeno fisico dell’entanglement, che ha richiesto un intero capitolo
a sè per poterla descrivere con strumenti più affinati, la crittoana-
lisi quantistica ha iniziato ad abbordare minacciosamente i sistemi
crittografici classici tuttora in uso. Tuttavia si tratta ancora di una
iv
minaccia fantasma, puramente teorica, che attende di condurre il
proprio assalto armata di protocolli e algoritmi, i più importanti dei
quali qui descritti, pericolosi solo sulla carta. Protocolli già svilup-
pati da tempo assieme ai circuiti quantistici che qui sono spiegati
nei loro dettagli più fondamentali; circuiti resi necessari dalla im-
plementazione fisica di questi protocolli su un computer quantistico
ancora da venire.
Nonostante la stretta correlazione con l’argomento, alla tratta-
zione della realizzazione del computer quantistico del futuro è stata
preferita un approfondimento della teoria dell’informazione quanti-
stica e a quanto ne concerne: dall’informazione quantistica vera e
propria alla teoria della correzione quantistica dell’errore. Capito-
li che potrebbero sembrare inizialmente completamente avulsi dal
contesto o quanto meno distanti dal cuore della tesi, semplicemen-
te per tornare poi utili alla comprensione di alcuni protocolli della
crittografia quantistica.
Ancoraprimadiaffrontarequestonocciolo, infatti, èemersapoco
alla volta la vastità e la complessità in cui si articolano le sue radi-
ci. Il rischio d’indossare le vesti del tecnico specializzato descritto
da Asimov con una conoscenza settoriale e superficiale, unicamente
di tipo funzionale, che non raggiungesse gli strati più vicini a una
comprensione con cognizione di causa era molto grande.
Se la trattazione della crittoanalisi quantistica si era avvicina-
ta il più possibile alle sue radici, quella della sua controparte, la
crittografia, rischiava una stesura dalle fondamenta farraginose. La
crittografiaquantisticaavevaapertoilmiopersonalevasodiPandora
della conoscenza. Per quanto mi è stato consentito ho approfondito
gli argomenti laddove una sincera comprensione degli stessi non si
allontanava troppo dal cuore della tesi. La crittografia in generale
poggia su numerosi contributi di altrettante numerose branche della
conoscenza, la crittografia quantistica nel dettaglio credo non abbia
collegamenti giusto con la filosofia.
Con questo spirito, in fondo alla tesi si trovano appendici che
potrebbero a buon diritto reclamare ognuna gli onori di capitoli a sè:
il teorema di Bell e l’entropia e informazione forniscono strumenti
indispensabili a portare in superficie le radici sopra citate, mentre
l’articolo EPR..beh è semplicemente una pietra miliare nella fisica
quantistica nonchè un punto di partenza.
Queste le ragioni per cui questa tesi non è esaustiva nella direzio-
ne assiomatica: la vastità e la complessità degli argomenti chiamati
ogni volta in causa, per quanto abbia tentato di arginarli e al tempo
stesso di approfondirli, è tale da non consentire uno svisceramen-
to oltre a quanto già fatto e che non sfociasse in un puro interesse
accademico delle origini. Ritengo che pur non essendo un punto di
partenza in senso assoluto, la trattazione fornisca un buon punto di
appoggio per lanciare il ponte a cui ho accennato precedentemente.
Sempre per le stesse ragioni, l’argomento della crittografia quan-
tistica tracima di articoli, di ricerche e di studi in continuo sviluppo
che rendono proibitivo un qualsiasi tentativo di trattazione di tipo
enciclopedico. Nonostante l’interesse puramente accademico o solo
v
per l’attualità dello stato dell’arte, sono stato costretto alla trat-
tazione dei cosiddetti fondamentali: i protocolli e le tecniche che
costituiscono ancora il nerbo degli studi e delle ricerche per le quali
è impossibile ritenersi aggiornato un qualsiasi lavoro sull’argomento.
La crittografia quantistica sta abbandonando a piccoli passi le
aule di ricerca per imporsi al mondo e se ancora non sembra portare
con sè tutta la forza dirompente e rivoluzionaria con cui il transistor
soppiantòlavalvola,mipiaceimmaginarecheforsesaràunoscrittore
di fantascienza che potrà mostrarci un futuro che oggi non possiamo
nemmeno immaginare.
vi
Capitolo 1
Crittologia classica
1
2
Se Gauss fosse vivo oggi, sarebbe un hacker.
Lacrittologiaèunascienzacheaccorpaduetecnichelegateindissolubilmente
tra loro: la crittografia e la crittoanalisi. La prima comprende tutti quei metodi
dicifraturavoltiaoccultareilcontenutodiunmessaggio; lacrittoanalisi, invece,
ha il ruolo di violare i cifrari e di ottenere così il testo di un messaggio il cui
significato era stato nascosto.
La situazione che si presenta di solito, perciò, consiste di due fazioni antago-
niste. La prima ha come obiettivo la realizzazione di una comunicazione segreta
tra due o più soggetti attraverso un canale di trasmissione insicuro, cioè tale
che altri possano intercettare i messaggi che transitano; l’altra fazione, invece,
vuole scoprire il contenuto dei messaggi criptati ed eventualmente alterarli o
sostituirli senza che nessuno si accorga dell’intercettazione.
La protezione della comunicazione avviene adottando un metodo di cifra-
tura che consenta a un mittente, tradizionalmente chiamato Alice, di spedire
un messaggio in chiaro m sottoforma di crittogramma c, incomprensibile a un
eventuale crittoanalista, chiamato di solito Eve, ma di facile decifratura da parte
del destinatario Bob.
Eve può avere diversi obiettivi: scoprire semplicemente il contenuto della
comunicazione, disturbare la comunicazione modificando c in modo che Bob
non sia in grado di risalire a m; o ancora modificare c affinché Bob riceva
un’informazione diversa da m. A seconda delle intenzioni di Eve, quindi, saremo
in presenza diversi tipi d’intercettazione.
L’attacco ad un sistema crittografico, perciò, ha l’obiettivo di forzare il ci-
frario; le tecniche scelte e il livello di pericolosità dipendono dall’informazione
inizialmente già in possesso di Eve e dalle sue potenzialità di computazione. Il
caso più semplice è l’attacco al testo cifrato in cui il crittoanalista ha raccol-
to una serie di crittogrammi che può analizzare per acquisire informazioni sul
metodo di cifratura.
1
Gli argomenti trattati in questo capitolo possono essere approfonditi nei seguenti
riferimenti [27, 75, 109, 119, 123, 130, 133, 134, 161, 162]
2
P.Sarnak, professore della Princeton University
1
Un altro schema è quello conosciuto come Known Plain-text Attack in cui
Eve è in possesso di una serie di crittogrammi e dei loro corrispondenti messaggi
in chiaro, lo s’incontrerà più avanti nel testo quando si descriverà in modo più
specifico le tecniche d’intercettazione. Infine, l’attacco più pericoloso è quello in
cui il crittoanalista riesce a procurarsi coppie m=c come nel Known Plain-text
Attack, con la differenza che Eve ha potuto effettuare una scelta opportuna e
non casuale di queste coppie.
L’attacco al sistema ha successo se si scopre la funzione di decifratura che
consente di decifrare il crittogramma c e di ottenere quindi l’intero contenuto del
messaggio. Anche un’informazione parziale può essere sufficiente per compren-
dereilsignificatodelmessaggio, soprattuttosescrittoconunlinguaggionaturale
in cui la struttura delle parole e delle frasi è obbligata da regole che facilitano la
crittoanalisi in questo caso chiamata crittoanalisi. Per questa ragione, a volte
sui messaggi si eliminano spazi, punteggiatura e tutti quegli elementi non indi-
spensabili alla comprensione del messaggio ma facilmente identificabili da chi
conosce la lingua usata. Naturalmente queste azioni non sono sufficienti per as-
sicurarsi la sicurezza del metodo di cifratura usato, non di meno contribuiscono
allo scopo finale di rendere inintelligibile il messaggio cifrato.
1.1 Cenni storici
Una prima distinzione nella crittografia è quella tra i codici ed i cifrari. In
linea generale un codice è un modo di assegnare convenzionalmente a parole o
frasi , un numero, una parola o una breve frase. Un codice rappresenta perciò
un concetto, un’informazione rappresentato da un simbolo specifico. Un codice
potrebbe assegnare alla parola giorno il significato entra nella costruzione e alla
parola notte, invece, esci dalla costruzione.
Un cifrario, invece, è completamente indipendente dal contesto, dalle infor-
mazionichesivoglionocomunicareeagiscedirettamentesuisingolisimboliscelti
(disolitoleletteredell’alfabeto). Unqualunquesimbolodell’alfabetocifratonon
ha un significato particolare, è solamente un simbolo in un altro alfabeto in cui
è stata rappresentata l’informazione. In un cifrario ogni simbolo del testo da
cifrare viene trasformato in un altro simbolo nello stesso o in un altro alfabeto
utilizzando una procedura matematica detta algoritmo crittografico. Da questo
momento saranno trattati solo cifrari.
Il metodo più antico di cui si ha notizia è lo scitale, risalente al V secolo
a.C.; questi era un’asta cilindrica su cui era avvolta ad elica una fettuccia di
cuoio. Il messaggio era scritto sulla fettuccia di modo che si potesse leggere
correttamente quando avvolta su una copia esatta dello scitale del mittente. In
questo caso il sistema era basato sulla totale segretezza del metodo e non solo
della chiave costituita dal diametro dell’asta. Un cifrario che si avvicina a una
concezione più moderna fu quello di Giulio Cesare. Esso consisteva nell’ottenere
il crittogramma dal messaggio in chiaro semplicemente sostituendo ogni lettera
con quella che la segue tre posizioni più avanti nell’alfabeto.
Questo cifrario molto elementare si sarebbe potuto generalizzare variando la
chiave che indica il numero di posizioni tra le lettere del messaggio in chiaro e il
crittogramma. Così facendo il cifrario di G.Cesare avrebbe avuto a disposizione
26 - 1 = 25 chiavi, un numero certamente troppo basso, sopratutto se un eve-
nutale crittoanalista conoscesse la struttura del cifrario. Il cifrario di G.Cesare
2
costituisce un esempio di cifrario a sostituzione, in particolare del tipo monoal-
fabetica. La funzione di cifratura è facile riconoscerla, si tratta dell’addizione in
modulo e nel caso di Cesare si ha mod =26 naturalmente.
Per aumentare lo spazio delle chiavi si possono impiegare funzioni più com-
plesse come la funzione affine, in cui una lettera in chiaro x viene sostituita con
la lettera cifrata y che occupa la posizione
pos(y)=[a£pos(x)+b] (mod 26)
dove a e b sono parametri del cifrario e ne costituiscono la chiave segreta.
Questa funzione comporta però un vincolo nell’operazione inversa sulla chia-
ve, ovvero a non deve essere primo con 26, altrimenti la cifratura non sarebbe
più iniettiva. Anche con quetsa limitazione lo spazio delle chiavi sale comunque
da 25 a 311, mettendo in effetti in difficoltà un crittoanalista manuale.
Un modo per aumentare la difficoltà è quella d’impiegare un cifrario com-
pleto, in cui si assume che la chiave segreta sia un’arbitraria permutazione delle
lettere dell’alfabeto. La lettera in chiaro che occupa la posizione i è trasformata
in quella che si trova nella stessa posizione della permutazione. Adesso le chiavi
sono 26! - 1.
Questo spazio potrebbe sembrare più che sufficiente ma le tecniche di crit-
toanalisi non seguono necessariamente gli approcci da cui ci si vuole difendere,
in questo caso l’attacco esaustivo, ovvero condotto con la pura forza bruta di
tutte le possibili combinazioni.
I cifrari a sostituzione incontrati finora sono nettamente potenziati se alla
stessa lettera in chiaro si sostituisce più di una lettera cifrata, ovvero si applica
una sostituzione polialfabetica. Esistono diversi esempi di cui il più antico risale
all’epoca di Roma imperiale per poi essere ripreso nel Cinquecento. Uno di
3
questi, il cifrario di Vigenèrefu ritenuto inattaccabile per tre secoli.
Un altro tipo di cifrario è detto a trasposizionee consente di eliminare qual-
siasi struttura linguistica nel crittogramma permutando le lettere del messaggio
in chiaro. Il più semplice è quello a permutazione semplice le cui chiavi possi-
bili sono h!¡1 dove h è un intero a scelta. Altri cifrari a trasposizione sono
quelli con permutazione di colonne e a griglia che sono in grado di rendere vano
un attacco esaustivo. Questo è dovuto alla dimensione dello spazio delle chiavi
sufficientemente ampio, ma un attacco diverso da quello esaustivo, come quello
statistico, ribalta la situazione. In questo caso, il crittoanalista sfrutta diverse
conoscenze per violare il cifrario. La prima ipotesi è che si conosca il metodo
impiegato per la cifratura/decifratura, la seconda è che il messaggio sia scritto
in un linguaggio noto. L’analisi statistica fornisce un potente strumento per
violare tutti i tipi di cifrari presentati finora.
Nei secoli successivi si alternarono cifrari non dissimili da quelli descritti
decidendo, avolte, il corso degli eventi storici. Uno dei più famosi crittogrammi
è quello che contribuì l’ingresso degli Stati Uniti nelle prima guerra mondiale:
nelmessaggiodecifratonel1917gliamericaniappresero, infatti, chelaGermania
aveva tentato di stringere un’alleanza col Messico con la promessa di spartirsi il
territorio statunitense.
Nel 1926 G.S.Vernam [96, 154], dell’American Telephone and Telegraph
Company, e il maggiore J.O.Mauborgne, dello US Army Signal Corps, realiz-
zarono il primo cifrario assolutamente sicuro, quello che verrà spesso nominato
3
Pubblicato nel Traictè de Chiffres e violato per la prima volta a metà dell’Ottocento.
3
come Cifrario Vernam o one-time pad (OTP). Come dimostrerà negli anni qua-
ranta C.E.Shannon [138], l’assoluta sicurezza di questo cifrario è dovuta all’uso
di una chiave casuale lunga quanto il messaggio e usata una sola volta. Infatti,
un eventuale intercettatore non sarebbe mai in grado di raccogliere sufficiente
informazione per decrittare il testo cifrato nonostante qualsiasi potenza compu-
tazionale possa essere in possesso. Con questa dimostrazione Shannon gettò le
basidellateoriadell’informazioneperlasicurezzacrittograficaesuccessivamente
M.Hellman ne prese il testimone [93].
Queste caratteristiche che conferivano all’OTP la resistenza a qualsiasi tipo
di violazione erano al tempo stesso un limite al suo impiego, perciò si continuò
ancora a impiegare cifrari più deboli basati su chiavi più brevi. In conseguenza
a questa scelta durante la seconda guerra mondiale gli Alleati furono in grado di
decifrare la maggior parte dei messaggi trasmessi dai tedeschi e dai giapponesi.
Naturalmente questo non significa che i cifrari impiegati in quegli anni fossero
facilmente violabili, tanto più che la necessità di forzarli costituì un impulso
determinante nello sviluppo delle macchine calcolatrici.
In particolare, merita menzione lo sforzo di A.Turing che, assieme ad altri
matematici radunati a Bletchley Park, Gran Bretagna, lavorarono in quel perio-
do non solo alla decifrazione dei codici segreti nemici, ma alla progettazione di
4
macchine per decrittare ogni tipo di modello delle macchine cifranti Enigma.
Nell’ambito accademico la crittografia subì una nuova spinta nel 1976 quan-
do W.Diffie, M.E.Hellman e R.C.Merkle, allora alla Stanford University, scopri-
5
ronoil principio della crittografia a chiave pubblica [65, 66]. Un anno dopo
R.L.Rivest, L.M.AdlemaneA.Shamir, allorapressoilM.I.T.riuscironoatrovare
un’applicazione nel tuttora usato cifrario RSA [131].
A questo punto il panorama crittografico comincia ad essere abbastanza
ampio da richiedere una certa classificazione. Ad oggi gli algoritmi crittogra-
fici usati per la sicurezza delle informazioni in formato digitale possono essere
accorpati, in linea di principio, in tre gruppi:
Algoritmi Simmetriciin cui le chiavi di cifratura e decifratura sono uguali o
si possono ricavare l’una dall’altra;
Algoritmi Asimmetrici o a chiave pubblicaappena accenati. Impiegano
due chiavi, una privata e una pubblica;
Algoritmi di Hash o Digestsono funzioni [47] tali che data una stringa di
lunghezza arbitraria generano una sequenza di lunghezza fissa con parti-
colari proprietà.
Gli algoritmi simmetrici possono implementare diverse tecniche di criptazio-
ne, quelle più antiche o storiche sono la trasposizione e la sostituzione (la quale
a sua volta può essere mono/ polialfabetica, poligrammatica o omofonica) come
già visto. Negli algoritmi moderni s’impiegano ancora queste tecniche ma con
diverse caratteristiche.
Gli algoritmi simmetrici si possono dividere in due grandi famiglie: quella
degli Algoritmi a Blocchi e quella a Caratteri o Algoritmi Stream. I primi
4
Le prime macchine a rotori furono le Koch, Hebern, Damm Hagelin e le Scherbius &
Ritter (Enigma)
5
In realtà, i veri scopritori furono Ellis, Cocks e Williamson agl’inizi degli anni settanta,
quando lavoravano al Government Communications Head Quarters (GCHQ) britannico e per
questa ragione non poterono pubblicare il loro lavoro.
4
suddividono il messaggio da cifrare in blocchi di lunghezza fissa (normalmente
pari alla lunghezza della chiave) e producono blocchi cifrati. La cifratura può
avvenire in due modi: ECB (Electronic Code Block) in cui ogni blocco è cifrato
in modo indipendente o CBC (Cipher Block Chaining) in cui nella cifratura di
ogni blocco è inserito un elemento (riporto) del blocco precedente.
Gli algoritmi Stream cifrano un bit alla volta attraverso un’operazione che in
genere è l’XOR, molto simili quindi all’OTP ma con chiavi non proprio casuali,
infatti è l’algoritmo stesso che specifica come generare la chiave a partire da
una chiave segreta più breve condivisa dai legittimi utenti. La chiave può essere
generata in modo sincrono, ovvero i bit della chiave sono generati in modo
indipendente dal crittogramma e dal messaggio in chiaro, o asincrono, in cui
ogni bit della chiave dipende da un numero fissato di bit cifrati precedenti.
Tra gli algoritmi simmetrici più comuni si hanno il DES, 3DES, AES, IDEA,
RC4, Blowfish, SERPENT,MARS,Crypton, ecc. Primadipiùdettagliatamen-
te gli algoritmi simmetrici più importanti, è interessante ritornare a parlare del
cifrario Vernam, l’unico la cui sicurezza è stata matematicamente dimostrata.
1.2 Cifrari perfetti
Lo studioso Shannon formalizzò il concetto di cifrario perfetto affermando che
il crittoanalista, esaminando un crittogramma c non doveva poter acquisire sul
messaggio alcuna conoscenza di cui non disponesse già prima. Un cifrario è
considerato perfetto, quindi, se la sua sicurezza è garantita qualunque sia l’in-
formazione carpita sul canale di trasmissione del crittogramma. In definiti-
va, l’impiego di un cifrario perfetto non cambia la conoscenza complessiva del
crittoanalista dopo che questi ha osservato un crittogramma c transitare sul
canale.
Un cifrario perfetto semplice è quello one-time pad o di Vernam. Le ope-
razioni di codifica/decodifica si basano sull’operazione binaria OR esclusivo o
XOR che vengono applicate su sequenze binarie di lunghezza fissa n.
S’immagini due utenti legittimi Alice e Bob che vogliano comunicare priva-
tamente usando questo schema e si supponga abbiano concordato in precedenza
una chiave segreta k, ovvero una stringa casuale di n bits. Allora se Alice
desidera inviare un messaggio m lungo n bit, manderà a Bob il testo cifrato
c=m›k, dove c è la somma modulo 2 di m e k. Bob potrà decrittare il testo
cifrato semplicemente eseguendo la medesima operazione m = c›k. Nel caso
d’invio di un altro messaggio verrà impiegata un’altra chiave k.
Shannon dimostrò che con l’algoritmo OTP se la chiave segreta è una stringa
veramente casuale di bit, allora anche il messaggio cifrato è una stringa casuale
di bit. Chi volesse violare il cifrario dovrebbe provare tutte le chiavi corrispon-
n
denti a2e valutare tutti i messaggi possibili che si otterrebbero. L’importanza
di usare una sola volta la chiave è dovuta al fatto che altrimenti apparirebbero
ripetizioni e somiglianze tra i diversi messaggi cifrati da imputare alla stes-
sa chiave. Perciò un numero sufficiente di crittogrammi con la stessa chiave
consentirebbero di forzare il cifrario.
L’OTP è l’unico algoritmo per cui sia stato possibile dimostrare matemati-
camente la sicurezza assoluta ma solo se la chiave è veramente casuale e usata
una sola volta. E’ possibile impiegare anche chiavi pseudo-casuali come avviene
spesso in pratica ma in tal caso decade la dimostrazione matematica. In que-
5
sta eventualità è necessario che il periodo del generatore pseudo-casuale PRG
deve essere superiore alla lunghezza della chiave richiesta e fare attenzione ad
altri accorgimenti, poichè un PRG se non utilizzato correttamente può genera-
re sequenze di numeri correlate tra loro. Inoltre, i PRG necessitano spesso di
un numero iniziale chiamato seed che genera una sequenza fissa di numeri. In
questo caso la sicurezza dell’OTP si trasferisce sulla segretezza del PRG e del
seed usati.
Un altro problema dell’OTP è che se Eve è a conoscenza di parte del testo in
chiaro, facendo l’XOR con la corrispondente parte del crittogramma è in grado
di recuperare un pezzo di chiave segreta. Se questa è stata generata da un PRG
Eve può ricostruire l’intera chiave.
L’impiego pratico di questo cifrario comporta diverse difficoltà, prima fra
tutte lo scambio delle chiavi segrete che siano veramente casuali, molto lunghe
e che comunque potranno essere riutilizzate una sola volta. Per questa ragione
l’OTP è adottata solo nel caso di comunicazioni molto importanti e sensibili. In
ogni caso si vedrà che l’OTP è ancora parte integrante anche della crittografia:
semplicemente si applica un altro metodo di cifratura non sul messaggio bensì
sulla chiave da impiegare nel cifrario di Vernam.
1.3 Il cifrario simmetrico standard
Un ulteriore contributo di Shannon alla crittografia ancora oggi tenuto in con-
siderazione nei cifrari a chiave segreta consiste nella formulazione dei criteri di
diffusione e confusione.
Per diffusione s’intende l’alterare la struttura del testo in chiaro spargendo
i caratteri su tutto il crittogramma come avviene nei cifrari a trasposizione at-
traverso le operazioni di permutazione. In questo modo si disperdono i gruppi
di lettere fissi presenti nella struttura di un qualsiasi linguaggio naturale e che
forniscono al crittoanalista un’ottima crepa dove sferrare il loro attacco al ci-
frario. Oltre alla permutazione che non risolve comunque in modo completo e
soddisfacente al problema dei gruppi di lettere, si possono combinare tra loro i
caratteri del messaggio affinché ciascun carattere del crittogramma dipenda da
molti di essi.
La confusione, invece, consiste nel fondere più possibile tra loro il messaggio
in chiaro e la chiave del crittogramma, in modo che il crittoanalista non sia in
gradodi risaliredal testo cifratoalle due sequenze originarie. Questo avvienenei
cifrari a sostituzione polialfabetica e in modo quasi perfetto nel cifrario Vernam.
Nei cifrari attuali, meno perfetti ma più economici si eseguono trasformazioni
che dipendono in un modo non lineare dalla sequenza d’ingresso del messaggio
in chiaro e della chiave.
Un esempio di cifrario simmetrico con diffusione e confusione è il Data En-
cryption Standard o DES, introdotto dalla IBM. Il DES nasce a metà degli anni
Settanta come proposta ad un bando dell’attuale National Institute for Secu-
rity and Tecnology NIST, ufficio americano per la definizione degli standard.
Fu certificato dalla National Security Agency (NSA) come cifrario ufficialmen-
te sicuro dopo avere apportato alcune modifiche, e lo rese noto pubblicamente
affinché chiunque potesse studiarlo e verificarlo [118]. Il DES è considerato si-
curo in senso computazionale piuttosto che sotto il punto di vista della teoria
dell’informazione. Questo significa che la violazione da parte di un eventua-
6
le intercettatore è computazionalmente non fattibile piuttosto che teoricamen-
te impossibile. Questo aspetto verrà approfondito parlando più avanti della
complessità computazionale.
Il DES può essere considerato il padre di tutti gli algoritmi simmetrici mo-
derni e di parte di quelli di Hash. La sua struttura nasce dall’analisi di Shannon
e dalle esperienze dei cifrari storici evoluti sino alle macchine a rotori. La sua
principale proprietà è di essere un algoritmo semplice sia dal punto di vista teo-
rico che implementativo. Questa proprietà consente di verificare la sicurezza del
cifrario nei confronti degli attacchi più noti e di potere implementare facilmente
l’algolritmo in software e hardware.
Le operazioni che consentono a un algoritmo di presentare le caratteristiche
indicate da Shannon per un buon cifrario, ovvero la confusione e la diffusione,
sono la sostituzione e la permutazione. L’idea di base è di reiterare più volte
queste operazioni per aumentarne gli effetti. La struttura di un algoritmo mo-
derno, perciò, è quella di una cifratura in cui le operazioni di sostituzione e di
permutazione sono applicate un certo numero di volte (round) congiuntamente
all’impiego della chiave segreta.
Quest’ultima di solito viene suddivisa da un appropriato algoritmo in tante
sottochiavi quanto sono i round previsti. Ognuna di queste sottochiavi verrà
usata per fare l’XOR con una parte del testo in chiaro (blocco) relativa al round
corrispondente. In definitiva l’algoritmo simmetrico a blocchi è composto da
un sottoalgoritmo che specifica il numero di round di permutazioni, sostituzioni
e XOR con la sottochiave a cui viene sottoposto ogni blocco, e da un altro
sottoalgoritmo che genera le sottochiavi a partire da quella originale per ogni
round.
Senza entrare nei dettagli della struttura dell’algoritmo, peraltro complicata
a descriversi dal ripetersi delle medesime operazioni sopracitate, un aspetto im-
portante per la sicurezza dell’algoritmo è l’operazione di sostituzione tramite le
cosiddette S-box. Le S-box sono elementi fissi dell’algoritmo e trattasi di matrici
numeriche. I bit in ingresso costituiscono l’indirizzo dell’elemento della matrice;
quest’ultimo è l’uscita della stessa, ovvero il dato impiegato per effettuare la
sostituzione. Le S-box rappresentano l’unico elemento non lineare degli algo-
ritmi con questa struttura, ovvero esse attribuiscono delle proprietà simili alla
casualità. Nel caso del DES si hanno otto S-box i cui elementi sono stati forniti
direttamente dalla NSA con un procedimento ancora tenuto segreto.
Oggi il DES non è più sicuro a causa di una lunghezza ridotta della chiave
(sotto i 100 bit) e non è possibile impiegarlo direttamente con chiavi più lunghe,
perciò lo si applica più volte con chiavi diverse (3DES).
Nel 1997 il NIST annunciò una competizione pubblica internazionale per un
algoritmo a blocchi di 128 bit e con chiavi da 128, 192 e 256 bit. Nel 2000 vinse
Rijindael e nel novembre 2001 una sua particolare implementazione divenne lo
standard pubblico col nome di AES (Advanced Encryption Standard). Infine,
nel 2003 la NSA approvò l’AES per i documenti classificati dell’amministrazione
USA. Data la sua sicurezza e le sue specifiche pubbliche si presume che in
un prossimo futuro venga utilizzato in tutto il mondo come è successo al suo
predecessore, il DES.
L’algoritmoèstatosviluppatodaduecrittografibelgi,J.DaemeneV.Rijmen,
che lo hanno presentato al processo di selezione per l’AES con il nome di
Rijndael.
7
L’AES è più efficiente e più semplice del DES anche se la struttura generale
è la stessa. La sua sicurezza si basa sulle 16 S-box da 256 elementi. Un’altra
differenza è l’algoritmo per generare le sottochiavi che è più complicato. So-
prattutto il DES impiega operazioni semplici come l’XOR mentre AES si basa
6
su matematica avanzata
La NSA segnalava che tutti i finalisti del processo di standardizzazione erano
dotatidiunasicurezzasufficienteperdiventarel’AESmachefusceltoilRijndael
per via della sua flessibilità nel trattare chiavi di lunghezza diversa, per la sua
sempliceimplementazioneinhardwareeinsoftwareeperlesuebasserichiestedi
memoria che ne consentono un implementazione anche in dispositivi con scarse
risorse come le smart card.
L’AES può essere utilizzato per proteggere le informazioni non classificate.
7
Per il livello SECRET è sufficiente una chiave a 128 bitmentre per il livello
TOP SECRET si consigliano chiavi a 192 o 256 bit. Questo significa che per la
prima volta il pubblico ha accesso a una tecnologia crittografica che NSA ritiene
adeguataperproteggereidocumentiTOPSECRET.Sièdiscussosullanecessità
di utilizzare chiavi lunghe (192 o 256 bit) per i documenti TOP SECRET.
Alcuni ritengono che questo indichi che l’NSA ha individuato un potenziale
attacco che potrebbe forzare una chiave relativamente corta (128 bit) mentre la
maggior parte degli esperti ritengono che le raccomandazioni della NSA siano
basate principalmente sul volersi garantire un elevato margine di sicurezza per
i prossimi decenni contro un potenziale attacco esaustivo.
AES è un algoritmo ancora nuovo perciò la sua sicurezza non è stata suf-
ficientemente testata come quella del DES. In particolare si ritiene che la sua
semplicità strutturale, che lo rende semplice da studiare sotto il punto di vista
matematico, possa divenire il suo punto debole. Infatti è stato possibile rappre-
sentare AES come un problema algebrico tramite il quale la chiave della cifra
potrebbe essere ottenuta dalla soluzione di un insieme di equazioni algebriche.
Questo fatto ha dato origine a una nuova famiglia di attacchi detti appunto
Algebrici; quello relativo ad AES è chiamato XSL.
Tuttavia va anche detto che, al momento, XSL non è implementabile e non si
sa se lo sarà mai. Inoltre, XSL si basa su di un sistema di moltissime equazioni
algebriche non-lineari accoppiate ed è noto che molti di questi sistemi sono
praticamente irrisolvibili. La maggior parte degli studiosi è comunque fiduciosa
nella sicurezza di AES, al più vi sono proposte di aumentare il numero di round,
la lunghezza del blocco a 256 bit e la lunghezza della chiave a 352 bit.
Nel 2002 l’attacco teorico annunciato da N.Courtois e J.Pieprzyk ha mostra-
to un potenziale punto debole dell’AES (e di altri cifrari) ma nonostante l’attac-
co sia matematicamente corretto è impraticabile nella realtà per via dell’enorme
tempo macchina richiesto per metterlo in pratica. Miglioramenti nell’attacco ne
hanno ridotto il tempo richiesto e quindi in un futuro questo attacco potrebbe
diventare attuabile. Ultimamente alcuni esperti hanno fatto delle osservazioni
agli autori dell’attacco: sembra che abbiano commesso degli errori teorici e che
in realtà le loro stime siano ottimistiche. Allo stato attuale la reale pericolo-
sità dell’attacco XSL è un punto interrogativo. Comunque attualmente l’AES
è considerato un algoritmo veloce, sicuro e gli attacchi fino a ora presentati si
sono rivelati degli interessanti studi teorici ma di scarsa utilità nella pratica.
68
Le operazioni si compiono all’interno del campo finito di Galois GF(2).
738
Una chiave a 128 bit produce 3;4£10combinazioni diverse.
8
La principale caratteristica di un cifrario asimmetrico, invece, è quella di
consentire a tutti d’inviare messaggi cifrati, ma abilita solo il ricevente di deci-
frarli. Nella crittografia a chiave segreta le operazioni di cifratura e decifratura
si svolgono con la stessa chiave; ora, invece, s’impiegano due chiavi diverse.
La prima è pubblica, la seconda è privata, cioè è nota solo al destinatario del
messaggio.
Le funzioni di cifratura/decifratura sono ancora pubbliche e impiegano cia-
scuno una chiave con parametro. La cifratura si esegue pubblica, cosicché tutti
sono in grado di cifrare un messaggio, mentre la decifrazione è accessibile solo
a chi possiede la chiave privata. Per questa ragione i sistemi a chiave pubblica
sono detti asimmetrici, mentre quelli a chiave segreta sono detti simmetrici, per
la pari funzionalità del mittente e del destinatario del messaggio.
Il sistema a chiave pubblica si basa su una proprietà che deve possedere la
funzione di cifratura C indicata come one-way trap door. Questa proprietà deve
consentire con facilità le operazioni di cifratura c = C(m;chiavepubblica), ma
al tempo stesso deve rendere difficile l’operazioni inversa di decifrazione a meno
non si conosca un meccanismo segreto, rappresentato dalla chiave privata in
questo caso.
La struttura che risulta da un simile sistema è quella di una comunicazione
molti a uno, in cui tutti possono cifrare i propri messaggi con la chiave pubblica
e inviarli al destinatario in possesso della chiave privata che ne consente la
decifrazione. Le funzioni one-way trapdoor attualmente conosciute sono legate
a congetture matematiche universalmente accettate ma non ancora dimostrate.
Queste congetture, annoverate fra i cosiddetti problemi P versus NP di cui si
parlerà fra breve, sono l’unica garanzia della difficoltà a risolvere l’operazioni
inversa della funzione one-way. Un classico esempio di queste funzioni è quella
della fattorizzazione di un numero nei suo fattori primi, e tra i cifrari basati su
questa funzione il più conosciuto è quello RSA.
Segue la descrizione del sistema asimmetrico più conosciuto.
1.4 Crittografia a chiave pubblica
Nel 1976 i cifrari a chiave pubblica furono proposti per la prima volta pub-
blicamente in un articolo scientifico intitolato New directions in cryptogtaphy
[66] da due matematici della Stanford University: Diffie e Hellman. Come già
accennato, a differenza dei cifrari simmetrici, in cui le chiavi di C eD sono iden-
tiche (o l’una può essere facilmente calcolata dall’altra), in questi nuovi cifrari
detti asimmetrici, le due chiavi sono completamente diverse tra loro. Inoltre la
chiave segreta, questa essere scambiata in modo sicuro fra coloro che intendono
servirsene e mantenuta nascosta, mentre nei cifrari asimmetrici una chiave è
addirittura pubblica e l’altra privata non necessita di essere comunicata ad al-
cuno. Si è anche detto che il cuore di questi cifrari si trova non tanto nelle chiavi
quanto nella particolare funzione di cifratura/decifratura. Questa, infatti, deve
essere del tipo one-way, cioè facile da calcolare ma difficile da invertire, a meno
di conoscere un trucco detto trapdoor che ne consenta una facile invertibilità.
L’esempio classico è la buca delle lettere in cui chiunque può depositare la cor-
rispondenza ma solo chi è in possesso della chiave della cassetta è in grado di
prelevarne il contenuto.
9
In matematica non è facile individuare funzioni con queste caratteristiche;
quelle conosciute sfruttano proprietà derivanti dalla teoria dei numeri e dall’al-
gebra modulare.
La fattorizzazione è una funzione di questo tipo ed è facile comprenderne
il motivo: mentre è facile nel senso computazionale calcolare il prodotto n di
due interi p e q, cioè l’ordine di grandezza dell’operazione è polinomiale, ancora
oggi è ritenuto difficile risalire a p e q partendo da n. Questo significa che la
fattorizzazione richiede un tempo esponenziale, a meno non si conosca uno dei
fattori.
Altre funzioni rilevanti per la crittografia sono il calcolo della radice in mo-
dulo e il calcolo del logaritmo discreto. Il primo consiste nel calcolare la potenza
z
y =x(mod s) conx,z,s interi; questa operazione richiede tempo polinomiale,
p
z
mentre l’operazione inversa x =y (mod s) richiede tempo esponenziale per
quanto è conosciuto fino ad oggi, se si sceglie s non primo.
Il calcolo del logaritmo discreto è concettualmente uguale al precedente,
z
cioè si richiede di trovare il valore di z tale che y =x(mod s). Nella normale
algebra il problema è semplice e consiste nel calcolo del logaritmo di y in basex,
ma in algebra modulare il problema è computazionalmente difficile e non sempre
ha soluzione.
I cifrari asimmetrici hanno il vantaggio di ridurre il numero complessivo di
chiavi a 2n anziché n(n¡1)=2 e non è richiesto alcun scambio segreto tra gli
utenti. D’altro canto sono esposti ad attacchi tipo chosen plain-text e sono
molto più lenti dei cifrari a chiave segreta. Per questa ragione nella pratica si
adottano cifrari ibridi in cui si usa, ad esempio, il DES per la comunicazione dei
messaggi mentre la chiavi segrete sono cifrate in modo asimmetrico.
Il cifrario asimmetrico più implementato in assoluto è quello RSA di cui si è
giàaccennato. Lesueradicimatematicheaffondanofinoalcalcolatoreaorologio
di C.F.Gauss e al cosiddetto piccolo teorema di P.de Fermat. I calcolatori di
Gauss sono detti a orologio perchè la somma che computano è la stessa di quella
cheancoraogginoifacciamoquandocalcoliamoiltemposuunnormaleorologio,
ovvero eseguiamo delle somme con modulo 12. I calcolatori di Gauss, perciò,
usano l’aritmetica modulare.
Fermat fece una scoperta fondamentale: se utilizzava un calcolatore a oro-
logio con un numero primo p di ore per computare un qualsiasi numero alla
potenza di p otteneva lo stesso numero di partenza, ovvero
p
x=x (mod p)
Fermat andò oltre alla scoperta e ne trovò la dimostrazione, il piccolo teorema,
come scrisse nel 1640 a un amico, ma come nel caso del suo ultimo teorema,
quella dimostrazione era troppo lunga per essere riportata nella stessa lettera.
Si dovette attendere il 1736 affinche L.Eulero riscoprisse la dimostrazione;
egli estese la scoperta di Fermat agli orologi con N = p£ q ore, dove p e q
sono numeri primi. Eulero scoprì che su un siffatto orologio il numero prescelto
sarebbe riapparso dopo (p¡1)(q¡1)+1 passaggi.
Rivest ebbe il lampo di genio di impiegare questa magia matematica del pic-
colo teorema quando si usano numeri primi per realizzare un codice matematico
capace di fare sparire una chiave numerica per poi farla riapparire. Semplifican-
do notevolmente, per il momento, si può paragonare la chiave numerica a una
10
carta da gioco di un mazzo composto da un numero N così grande di carte che
sarebbero necessarie più di cento cifre per scriverlo.
La carta, che nel nostro esempio corrisponde alla chiave numerica, viene
mescolata al mazzo in modo da perdere completamente conoscenza della sua
posizione. Come nel gioco dei prestigiatori, però, esiste un trucco per fare riap-
parire la carta sulla cima del mazzo dopo un certo numero di rimescolate, basta
conoscere questo numero. Il piccolo teorema è il trucco matematico che consente
di recuperare la chiave numerica e il corrispondente numero di mescolate delle
carte è legato, appunto, ai fattori primi di N come si è appena scritto parlando
della scoperta di Eulero.
Passando a una spiegazione più rigorosa, matematicamente parlando, è ne-
cessaria una breve disgressione sull’aritmetica modulare.
S’indica conZil seguente insieme degli interi non negativi
N
Z=f0;:::;N¡1g
N
Quando a Zsono associate le operazioni di addizione e di moltiplicazione
N
⁄
modulo N, esso forma un anello. ConZs’indica il seguente insieme:
N
⁄
Z=fx2Z:M:c:d:(x;N)=1g
N
N
⁄
Il numero degli elementi inZdetermina la cosiddetta funzione di Eulero:
N
⁄
’(N)=jZj
N
In particolare, se N è primo si ha:
’(N)=N¡1
Il teorema di Eulero afferma che:
’(N)
x·1 (mod N)
⁄
per N ‚2 e per qualsiasi intero x2Zovvero Mcd(x;N)=1.
N
E se N è primo [109] saràIlpiccolo
teorema di
N¡1
x·1 (mod N)Fermat
⁄
Quando a Zè associata l’operazione di moltiplicazione modulo N esso
N
⁄
forma un gruppo. Conseguentemente per ogni elemento x2Zesiste un unico
N
⁄
y2Ztale che xy·1 (mod N). A questo punto si noti che per il teorema di
N
Eulero si ha
’(N)¡1
x£x·1 (mod N)
’(N)¡1
da cui si deduce chex·y ovvero l’inverso dix (mod N). Questo implica
che nel caso di x primo con N, si può calcolare l’inverso conoscendo ’(N).
Si consideri ora l’equazione modulare
ax·b (mod N)
con coefficienti x;b;N interi. Nella normale algebra la si risolve semplicemente
¡1
calcolando a=x£b·y£b, ma nell’algebra modulare l’esistenza di y non è
¡1
garantita perchè xdeve essere intero e l’equazione può ammettere una o più
soluzioni, o può non ammetterne affatto come spiega il seguente teorema.
11