Last update Ottobre 17, 2018 10:59 AM

 

drmlog  


Personal Website


Articoli / Articles
     

Pagina Iniziale Home Page

Informazioni About Me

Curriculum Vitae Resume
Didattica Teaching
Guide Tutorials
Articoli Articles
Libri Books

Contatti Contacts
     
 
     
 

Dalla teoria dei numeri primi alla crittografia quantistica
di Roberto Saia

[Versione italiana dell'articolo "From the Theory of Prime Numbers to Quantum Cryptography" pubblicato sul numero di gennaio 2012 di Hakin9 Extra]

Sebbene siano davvero in pochi a conoscere gli assiomi che ne regolano il funzionamento, milioni di persone di avvalgono ogni giorno delle tecniche crittografiche per compiere in sicurezza quelle attività informatiche caratterizzate dallo scambio di informazioni sensibili, attività che in modo trasversale interessano ogni ambito, dalla semplice posta elettronica ai sofisticati servizi di carattere finanziario.

Il tipico “modus operandi" che contraddistingue la comunità informatica dei nostri tempi è certamente più orientato verso il pragmatismo piuttosto che, come accadeva qualche tempo addietro, verso una adeguata conoscenza di ciò che sta alla base delle tecniche e degli strumenti adoperati: ciò si concretizza nella pratica in un modo di procedere alquanto meccanico, dove l’unica conoscenza preliminare si riduce all’obiettivo da conseguire.
Tale scenario non è sempre imputabile alla mera superficialità di chi opera ma anzi, nella quasi totalità dei casi, esso è da attribuire esclusivamente al costante ed esponenziale sviluppo che caratterizza il settore informatico negli ultimi decenni, qualcosa di enormemente più marcato di ciò che si ravvisava in un passato appena più remoto e che, “de facto”, rende estremamente difficile per chi opera il conseguimento di una piena conoscenza delle tecniche e degli strumenti utilizzati, proprio per questo ininterrotto e rapido evolversi che li caratterizza.
Questo articolo vorrebbe colmare uno di questi gap, mostrando al lettore lo stretto legame che intercorre tra la matematica e i sistemi di crittografia allo stato dell'arte; pur senza la pretesa di raggiungere la piena esaustività nella trattazione, l’obiettivo che si desidera conseguire è quello di esporre, seppure talvolta in chiave esemplificata, alcune delle più importanti teorie matematiche che regolano il funzionamento della moderna crittografia, iniziando con l’introdurre i cosiddetti “numeri primi”, importantissimo fulcro sul quale ruotano tutte le moderne tecniche crittografiche a chiave pubblica, tecniche che rappresentano oggi uno standard a livello planetario.

Il fascino dei numeri primi
I numeri primi sono un argomento che da centinaia di anni affascina schiere di matematici, ispirando romanzi e film d’effetto, un ambito talmente vasto e complesso che per certi aspetti può ancora essere definito quasi inesplorato, ragione per cui ciò che diremo in questa sede deve essere considerato un semplice spunto per futuri approfondimenti da parte del lettore interessato a tale argomento.
Molti di noi ricorderanno dai tempi della scuola come per essere definito primo un numero debba soddisfare alcuni particolari requisiti che, nella fattispecie, consistono nell’essere divisibile solo per se stesso e per 1; più formalmente, un certo numero n viene considerato primo se, e solo se, esso risulta esclusivamente divisibile per ±n e ±1.
Convenzionalmente, per motivi che comprenderemo chiaramente più avanti, il numero 1 non viene incluso nell’insieme dei numeri primi anche se, in realtà, esso soddisfa perfettamente le cosiddette “condizioni di primalità”, descrizione formale che in letteratura matematica indica le verifiche volte a determinare se un certo numero è annoverabile nell’insieme dei “numeri primi”: ciò avviene nel caso del numero 1, in quanto ponendo n=1, abbiamo che n è divisibile soltanto per ±n e ±1.
Prima di descrivere le motivazioni di questa esclusione è opportuno aprire una breve parentesi per sottolineare come nonostante da centinaia di anni si sia cercato un metodo (presupponendo, a torto o a ragione, che questo esista!) di individuazione di tutti i numeri primi, si è oggi ancora molto lontani da questo traguardo: nonostante le attuali prestazioni degli elaboratori e il loro utilizzo spesso congiunto, l’unico risultato a oggi conseguito è stato quello di isolare un numero enorme di questi numeri, operando, quindi, sempre in modo alquanto empirico, senza alcun preciso metodo di individuazione.
Nel procedere con l’attività di isolamento di nuovi numeri primi, ha iniziato a delinearsi uno dei misteri che li accompagna: la loro distribuzione.


Figura 1 – Distribuzione dei numeri primi da 1 a 100.

Gli studi compiuti in questo particolare settore della matematica hanno mostrato come quest’ultima sia alquanto irregolare, come è possibile osservare in Figura 1, dove viene evidenziata la distribuzione dei numeri primi nell’intervallo da 1 a 100.

Legge di rarefazione dei numeri primi
L’irregolarità nella distribuzione dei numeri primi non è comunque molto evidente nel precedente esempio di Figura 1, in quanto essa inizia a delinearsi in modo più marcato soltanto in seguito: basti pensare che prima del numero 10 esistono soltanto 4 numeri primi, che diventano 24 prima di giungere a 100 e 168 prima del numero 1000 e soltanto 10 numeri nel primo centinaio che segue 10 milioni.
Da questo scaturisce quella che in matematica viene definita “legge di rarefazione dei numeri primi”, la quale asserisce che al crescere del numero preso in esame decresce la frequenza dei numeri primi che, quindi, diventano sempre più rari quando si tende all’infinito.
Secondo tale legge si potrebbe essere indotti a pensare che, al crescere del numero preso in esame, si giunga a un punto nel quale non siano più presenti numeri primi e che essi, quindi, differentemente dai numeri naturali, non siano di numero infinito.
In questo specifico frangente si colloca Euclide, il quale, a suo tempo, peraltro in modo molto elegante, dimostrò l’infinità dei numeri primi.
Si tratta di una dimostrazione del tipo “reductio ad absurdum“, locuzione latina traducibile in “dimostrazione per assurdo” che viene impiegata in ambito matematico per identificare un procedimento logico nel quale inizialmente si assume una certa ipotesi che poi, procedendo, conduce a delle conclusioni assurde che mostrano l’inesattezza dell'assunto originale, dimostrando indirettamente quel che si desiderava.

Il principio del terzo escluso
Tale tipo di dimostrazione logica si avvale del cosiddetto principio del “tertium non datur” (del terzo escluso), principio secondo il quale un qualunque enunciato che non può essere falso, deve necessariamente essere assunto come vero, in quanto non esiste una terza possibilità; preferito dai grandi pensatori del passato al metodo di dimostrazione mediante esaustione che, invece, doveva prendere in considerazione tutti i possibili casi, esso è divenuto poi il metodo d’elezione in epoca moderna, specialmente in ambito matematico.


Nel nostro caso Euclide, che tanto adorava questo genere di dimostrazione, procedette in questo modo:

  1. ipotizzò che i numeri primi fossero finiti;
  2. da questo discese che allora deve esistere un numero primo M più grande di tutti gli altri;
  3. eseguendo il prodotto tra M e i rimanenti numeri che lo precedono, e aumentando di 1 il risultato, si ottiene un nuovo numero primo N più grande di M, in quanto dividendo N per ogni numero primo si ottiene come resto sempre 1;

Questa ultima considerazione configura un assurdo, in quanto M è il numero primo più grande, dimostrando, quindi, che i numeri primi sono infiniti.
Quindi, riepilogando il tutto più formalmente: dato insieme di tutti i numeri primi P={2, 3, ..., pn}, con pn che rappresenta più grande tra questi; poniamo che aN sia il prodotto degli n numeri primi e prendiamo in considerazione a+1; questo ultimo non risulta divisibile per il primo numero primo 2, perché lo è a (in quanto prodotto di tutti i numeri primi) e quindi produce come resto 1; tale situazione si ripresenta per tutti i rimanenti numeri primi, cioè ponendo sia pi l'i-esimo numero primo, la divisione (a + 1)/pi produce sempre un resto pari a 1.
A questo punto viene anche chiamato in causa il “teorema fondamentale dell'aritmetica”, nel quale si afferma che “ogni numero naturale maggiore di 1 o è un numero primo o si può esprimere come prodotto di numeri primi; tale rappresentazione è unica, se si prescinde dall'ordine in cui compaiono i fattori“.
Alla luce di questo teorema, rimangono quindi valide soltanto due alternative:

  1. il numero a+1 è primo e, ovviamente, è anche più grande di pn;
  2. il numero a+1 non è primo ed è quindi il prodotto di numeri primi diversi dagli n ipotizzati, dato che (a+1) > a e quindi anche maggiori di pn; anche in questa circostanza esso è più grande di pn.

In entrambi i casi però si giunge a una palese contraddizione, in quanto non può esistere un numero primo più grande pn, deducendo da questo che i numeri primi sono infiniti.

Il processo di fattorizzazione
Formalizzando ulteriormente quanto detto in precedenza riguardo al processo di fattorizzazione, possiamo affermare che: ogni numero intero N maggiore di 1 può essere fattorizzato (ridotto in fattori), cioè per ciascun numero intero N è possibile individuare un determinato insieme di numeri il quale prodotto fornisce come risultato il numero stesso.
Essendo il processo di fattorizzazione non univoco, cioè essendo possibile operare differenti fatttorizzazioni di un determinato numero che però riconducono sempre a esso, affinché si possa giungere a una condizione di unicità che consenta una sola fattorizzazione possibile per ciascun numero, è indispensabile restringere il campo dei possibili fattori ai soli numeri primi: questo stratagemma consente di raggiungere l’obiettivo, in quanto per ciascun numero naturale esiste una sola fattorizzazione in numeri primi.
Si è fatto accenno in precedenza alla convenzionale non inclusione di 1 nell’insieme dei numeri primi.
Ciò si è reso necessario, in quanto, non escludendolo, pur restringendo il campo dei possibili fattori ai soli numeri primi, ogni numero naturale potrebbe comunque ricondurre a infinite fattorizzazione, dato che è sempre possibile aggiungere al prodotto di numeri primi che lo rappresenta una qualunque sequenza di 1 senza per questo alterare il risultato finale, infatti:

N = A x B x C x 1
N = A x B x C x 1 x 1
N = A x B x C x 1 x 1 x 1

sono fattorizzazioni di N assolutamente equivalenti (dove A, B e C sono i fattori primi che lo scompongono).
Riepilogando, al fine di garantire l’univocità nelle fattorizzazioni operate è quindi indispensabile sia includere soltanto i fattori che sono numeri primi, sia escludere da questi ultimi il numero 1.
Operando tali restrizioni, come è possibile osservare nel successivo esempio, ciascun numero sarà legato in modo univoco all’insieme di numeri che rappresenta la sua fattorizzazione:

132 = 2 x 2 x 3 x 11
3900 = 2 x 2 x 3 x 5 x 5 x 13
66300 = 2 x 2 x 3 x 5 x 5 x 13 x 17

Fattorizzazione che può essere espressa in modo più leggibile e compatto, rappresentando i prodotti per mezzo delle potenze,

132 = 22 x 31 x 111
3900 = 22 x 31 x 52 x 131
66300 = 22 x 31 x 52 x 131 x 171

Esistono differenti metodi, più o meno complessi, per ricavare i numeri primi, uno dei più noti e certamente il cosiddetto Crivello di Eratostene.
Si tratta di un procedimento algoritmico (cioè in grado di giungere al risultato in un numero finito di passi) che consente di individuare tutti i numeri primi inferiori a un certo numero massimo M prefissato: il primo passo di tale algoritmo consiste nella preparazione di una lista dei numeri interi compresi tra 2 e M; segue quindi la rimozione di tutti i numeri multipli di 2 tranne il 2 stesso, muovendosi poi sul primo numero non rimosso (quindi 3) ed eliminando dalla lista tutti i suoi multipli, escludendo sempre il 3 stesso; si prosegue quindi in questo modo fino a raggiungere la parte intera della radice quadrata di M; al termine delle operazioni di rimozione, rimarranno soltanto i numeri primi compresi nell’intervallo tra 2 a M.


Figura 2 – Crivello di Eratostene.

Nell’esempio di Figura 2, presupponendo il limite massimo M uguale a 25, la parte intera della sua radice quadrata è 5: procedendo con il metodo prima descritto, applicato a tutti i numeri fino a 5, otterremo i numeri primi compresi nell’intervallo da 2 a 25.
Da osservare come, sulla base delle precedenti considerazioni, il numero 1 non è stato incluso in tale procedimento.

Fattorizzazione e crittografia asimmetrica
L’applicazione pratica in ambito crittografico di quanto appena visto discende dal fatto che, relativamente a numeri sufficientemente grandi, risulta molto difficile individuarne i fattori primi che rappresentano la sua fattorizzazione, talmente difficile che oltre un certo valore numerico le tecniche e gli strumenti oggi disponibili si rivelano inadeguati, rendendo di fatto impossibile l’operazione: allo stato attuale, infatti, differentemente per come visto in precedenza per le verifiche di primalità, non esistono metodi in grado di compiere questo tipo di operazione in tempi ragionevoli; a titolo di esempio basti pensare che per individuare i fattori di un intero di 100 cifre occorre orientativamente 1 secondo, per un numero di 200 cifre il tempo sale a circa 1 anno e mezzo e per 300 cifre pressappoco a 2 milioni di anni.
Alla luce di quanto appena detto e in considerazione che gli odierni algoritmi di crittografia asimmetrici a chiave pubblica utilizzano, tipicamente, chiavi di crittografia sull’ordine dei 1024 bit, cioè l’equivalente di circa 300 cifre decimali, è facile intuire come allo stato attuale la cifratura dei dati operata con tali metodi sia da considerare inviolabile nella pratica.
Da osservare che diversi anni addietro la quasi totalità degli algoritmi di crittografia impiegati era di tipo simmetrico, cioè basava il suo funzionamento su un’unica chiave crittografica, assolutamente indispensabile sia per la crittografia che per la successiva decifratura.
Il tallone d’Achille di tale sistema era chiaramente rappresentato proprio da questa chiave unica, in quanto era assolutamente necessario che essa circolasse tra gli utenti autorizzati, con le ovvie ripercussioni per quel che concerne la sicurezza.
La vera rivoluzione in questo settore è stata l’adozione di un meccanismo completamente differente da quello fino ad allora utilizzato, diverso in quanto operante in modo asimmetrico, cioè impiegando differenti chiavi per le operazioni di codifica e decodifica dei dati, un metodo semplice ma incredibilmente efficace che in ambito crittografia ha rappresentato il classico uovo di Colombo.
Quel che in pratica accade in questo caso è che le informazioni vengono cifrate con una chiave pubblica ma possono essere decifrate soltanto impiegando una chiave privata, chiave posseduta soltanto dai legittimi destinatari delle informazioni.
Proprio per questo suo modo di operare, la crittografia asimmetrica viene anche definita crittografia a chiave pubblica, in contrapposizione alla crittografia simmetrica, che viene invece definita crittografia a chiave privata.
Un elemento che comunque accomuna qualunque meccanismo di crittografia, simmetrico o asimmetrico che esso sia, è certamente la bontà della chiave impiegata (pubblica o privata): una chiave semplice potrebbe infatti rendere vulnerabile anche un meccanismo potenzialmente robusto come quello asimmetrico.
L’adozione di chiavi di complessità inadeguata (lunghezza, caratteri utilizzati, ecc.) consente una loro decifratura mediante delle banali tecniche di brute-force, cioè attraverso reiterati tentativi di indovinare la chiave basandosi sulle lettere dell’alfabeto, sui dizionari o su particolari liste contenenti le chiavi più frequentemente adoperate dagli utenti.
Il funzionamento degli algoritmi asimmetrici, come anticipato in precedenza, è basato su due elementi primari, la chiave pubblica e la chiave privata: il particolare meccanismo adoperato per la generazione di queste chiavi non consente in alcun modo di risalire a una chiave privata partendo dalla corrispettiva chiave pubblica, in quanto tale operazione è caratterizzata dall’enorme difficoltà di risalire ai fattori primi che determinano un certo numero, difficoltà precedentemente evidenziata discutendo del processo di fattorizzazione.


Figura 3 – Algoritmo asimmetrico di cifratura.

Gli algoritmi di questo tipo più noti sono RSA (acronimo derivante dalle prime lettere dei cognomi degli sviluppatori Ronald L. Rivest, Adi Shamir e Leonard M. Adleman) e DSS (Digital Signature Standard).
Per comprendere il funzionamento di tali algoritmi, ipotizziamo l’esistenza di due sistemi informatici che desiderano scambiarsi delle informazioni in modo sicuro, sistemi che denomineremo Alfa e Beta.
Il procedimento, graficamente rappresentato in Figura 3, può essere così riassunto: Alfa e Beta possiedono una coppia di chiavi ciascuno (una pubblica e una privata); Alfa richiede a Beta la sua chiave pubblica e con quella cifra i dati che successivamente gli invia; i dati cifrati con una chiave pubblica possono essere decifrati solo mediante la corrispettiva chiave privata; Beta utilizza la sua chiave privata e decodifica i dati inviati da Alfa; il processo si ripete in modo speculare nella direzione inversa.
Appare chiaro come nell’ambito dell’intero processo l’unica chiave che rimane segreta è quella privata, in quanto quella pubblica può essere tranquillamente diffusa: a tal proposito è opportuno evidenziare come, nella realtà, il primo passaggio (quello nel quale viene richiesta la chiave pubblica dell’interlocutore) non avvenga, dato che tale richiesta è solitamente indirizzata a una apposita struttura che ha il compito di accentrare in un unico punto le chiavi pubbliche degli utenti.
Diverso tempo addietro si è voluta verificare la robustezza di un algoritmo di questo genere e, nella fattispecie, di RSA. Per fare questo furono impiegati in modo congiunto le risorse computazionali di 1600 elaboratori e gli sforzi di 600 gruppi di studio localizzati in oltre 25 paesi differenti: l’obiettivo era quello di violare una chiave RSA della lunghezza di 129 bit.
La violazione è stata conseguita dopo oltre 8 mesi di lavoro ininterrotto di tutti gli elaboratori, le quali risorse, sfruttate in modo congiunto, hanno dato vita a una sorta di supercalcolatore parallelo.
Tale esperimento ha dimostrato l’inviolabilità “pratica” dell’algoritmo crittografico, in quanto le chiavi oggi adoperate si attestano su ordini di grandezza di molto superiori ai 129 bit impiegati nel corso dell’esperimento.

Inviolabilità teorica del sistema
Da osservare come l’inviolabilità degli odierni sistemi di crittografia a chiave pubblica sia soltanto uno “status” di carattere prettamente “pratico”, in quanto sotto il profilo “teorico” essa è soltanto una diretta conseguenza dell’inefficienza degli attuali metodi di fattorizzazione dei numeri primi (almeno di quelli molto grandi); si tratta quindi di uno scenario che potrebbe mutare in futuro, invalidando completamente gli algoritmi attualmente utilizzati.

Il cifrario di Vernam
Riguardo alla non attuale disponibilità di un sistema inviolabile di crittografia, occorre dire che questa affermazione può essere considerata in parte falsa, in quanto è stata matematicamente dimostrata l’esistenza di un sistema di crittografia inviolabile: il cosiddetto “Cifrario di Vernam“ o, come viene spesso definito, il “Cifrario perfetto”; si tratta dell’unico meccanismo di crittografia che può essere definito “matematicamente sicuro”, un meccanismo per il quale esistono delle formali e verificate dimostrazioni circa la sua inviolabilità sin dalla fine degli anni Quaranta.
Sinteticamente riepilogato nel suo funzionamento in Figura 4, tale cifrario ha origine nell’anno 1918, anno nel quale Gilbert Vernam, tecnico della società AT&T Bell, nonché Maggiore dell’Esercito degli Stati Uniti, riprese il metodo di cifratura denominato “Metodo di Vigenère“ (uno dei più semplici cifrari esistenti, basato sull'utilizzo di un versetto per controllare l’alternanza degli alfabeti di sostituzione) e lo estese con delle chiavi di cifratura di tipo random (casuali) della stessa dimensione del messaggio da cifrare, dando vita, appunto, a quello che in seguito fu definito “cifrario di Vernam”.


Figura 4 – Cifrario di Vernam.

Negli anni successivi, precisamente nel 1949, Claude Shannon, padre indiscusso della teoria dell'informazione, pubblica un documento dal titolo “La teoria della comunicazione nei sistemi crittografici”, documento con il quale dimostra, in modo rigoroso, come il “Cifrario di Vernam” possa essere considerato un meccanismo di crittografia del tutto sicuro.

Cifratura a chiave infinita
L’inviolabilità del Cifrario di Vernam nasconde in realtà una complicazione pratica, in quanto è necessario che la chiave di cifratura, CAILNBR nella precedente Figura 4, sia adoperata una sola volta, pena la perdita dei presupposti che stanno alla base della sicurezza del cifrario.
Per questa ragione, il “Cifrario di Vernam“ viene annoverato nella categoria dei sistemi crittografici che adoperano chiavi non riutilizzabili, sistemi che in letteratura informatica vengono classificati come “con cifratura a chiave infinita” o “One Time Pad” (cioè utilizzabile una sola volta).
Pur tenendo conto di questa complicazione è logico chiedersi come mai, pur esistendo un sistema di crittografia la quale inviolabilità è stata formalmente dimostrata, non ci si avvale di esso ai giorni nostri.
La risposta a questo quesito è di una semplicità disarmante e si basa sulla consequenzialità di tre considerazioni:

  1. la chiave di crittografia che occorre adoperare per cifrare il messaggio è lunga quanto il messaggio stesso;
  2. la chiave deve necessariamente essere comunicata al destinatario delle informazioni cifrate affinché questo possa decifrarle;
  3. occorre trovare un canale sicuro per operare il trasferimento della chiave.

Alla luce di queste considerazioni viene logico domandarsi perché invece di adoperare il canale sicuro per scambiarsi la chiave non lo si adopera direttamente per veicolare il messaggio, messaggio che, tra l’altro, ha le sue stesse dimensioni: ciò rappresenta la dimostrazione che non sempre i metodi teoricamente validi possiedono poi dei corrispondenti riscontri nelle applicazioni pratiche.

Diffie-Hellman vs Man-in-the-middle
Quanto fin qui detto, a prescindere dal tipo di sistema crittografico, lascia evincere chiaramente come l’ingranaggio debole sia sempre lo scambio della chiave, operazione che nel migliore dei casi implica un rischio di decodifica soltanto potenziale da parte del malintenzionato di turno (come nel caso della crittografia asimmetrica a chiave pubblica), mentre nel peggiore dei casi, quando essa non è stata scelta secondo degli adeguati standard di complessità, conduce alla completa compromissione delle informazioni veicolate.
A tal proposito è opportuno introdurre il cosiddetto protocollo “Diffie-Hellman”, un protocollo formalizzato pubblicamente verso la metà degli anni Settanta che, come lascia intendere il suo nome, rappresenta il risultato di un lavoro congiunto, quello di Whitfield Diffie e Martin Hellman ; esso consente a due interlocutori di giungere a una chiave di crittografia comune sfruttando un canale di comunicazione ordinario (quindi non protetto); chiave che verrà poi impiegata nell’ambito di un sistema crittografico di tipo simmetrico, il quale funzionamento si riassume in Figura 5.



Figura 5 – Algoritmo simmetrico di cifratura.

Conosciuto con il nome di “Diffie-Hellman key exchange”, anche questo protocollo si basa sui numeri primi e, nel dettaglio, ipotizzando che le parti in causa siano Alfa e Beta, il suo funzionamento è il seguente:

  1. Alfa e Beta concordano di impiegare un numero primo p=19 e una base g=2;
  2. Alfa sceglie un numero segreto a=5 e invia a Beta A = ga mod p, cioè 13;
  3. Beta seleziona un numero intero segreto b=10 e invia ad Alfa B = gb mod p, cioè 17;
  4. Alfa calcola KEYA = (gb mod p)a mod p, cioè 6;
  5. Beta calcola KEYB = (ga mod p)b mod p, cioè 6.

Il termine “mod” identifica una operazione di modulo, cioè un’operazione che fornisce come risultato il resto di una divisione (per esempio, l’operazione 5 mod 3 produce come risultato 2). Come è possibile osservare, al termine del procedimento Alfa e Beta giungono al medesimo risultato, KEYA e KEYB, unici elementi che insieme ad “a” e “b” rimangono segreti, in quanto i rimanenti valori vengono veicolati in chiaro; il risultato comunemente raggiunto rappresenta la chiave segreta.
Da sottolineare che i valori iniziali da utilizzare nelle applicazioni reali dovranno essere ben più grandi di quelli impiegati nel precedente esempio a scopo esemplificativo, eccezione fatta per il valore g che, solitamente, anche nelle applicazioni reali assume un valore di 2 o 5: a tal proposito si può dire che quando a e b sono dei numeri di almeno un centinaio di cifre e p un numero primo di almeno 300 cifre, la ricerca del numero segreto a partire dagli unici valori noti (g, p, ga mod p) risulta impraticabile per qualunque sistema di calcolo odierno, anche ipotizzando un lavoro congiunto di tutti gli elaboratori oggi esistenti.
La ragione di questa inviolabilità riconduce al concetto di “logaritmo discreto”, operazione che presenta un ordine di complessità simile a quello della fattorizzazione dei numeri interi.


Logaritmi discreti
Il logaritmo rappresenta un’operazione matematica speculare alla “potenza” e, parallelamente, il “logaritmo discreto” esprime l’operazione inversa alla “potenza discreta”; ipotizzando di avere un insieme N contenente i numeri interi da 0 a m-1, dove m rappresenta un numero primo, possiamo definire con a(PD)b = ab mod p l’operazione di “potenza discreta” di due numeri a,b appartenenti all’insieme N, e da qui definire come “logaritmo discreto” di un numero x in base a quel numero b per cui a(PD)b = x, cioè ab mod p = x.


Anche in questo caso, seppure per differenti ragioni, le confortanti garanzie teoriche di inviolabilità cozzano con la loro implementazione pratica, in quanto tale procedimento si rivela altamente vulnerabile nei confronti di un attacco condotto secondo la consolidata tecnica del "Man in the middle”, che vede un malintenzionato interporsi tra gli interlocutori al fine di scambiare la chiave pubblica originale con una di sua creazione, operazione possibile considerando che per la definizione della chiave simmetrica e comunque necessario uno scambio di informazioni tra mittente e destinatario.

La crittografia quantistica
Uno dei settori scientifici che più degli altri promette di sconvolgere lo “status quo” nelle tecniche di protezione delle informazioni è, senza alcuna ombra di dubbio, quello afferente alla cosiddetta “crittografia quantistica”, un ambizioso progetto che mira a coniugare alcuni aspetti peculiari della “meccanica quantistica“ con i sistemi di crittografia, stravolgendo lo scenario esistente con l’introduzione di nuove tecniche e applicazioni oggi impossibili.
Per questa ragione, oltre che il canonico interesse degli addetti ai lavori, questa tecnologia ha destato l’interesse di numerose altre realtà come, per esempio, le strutture militari e governative.
Una delle prime applicazioni pratiche della crittografia quantistica prende il nome di QKD (Quantum Key Distribution) e mira a risolvere l’annoso problema della sicurezza legato alla distribuzione delle chiavi crittografiche attraverso i canali trasmissivi convenzionali, quindi non sicuri: tale tecnica sfrutta alcune proprietà delle particelle elementari e delle leggi della fisica quantistica al fine di garantire uno scambio assolutamente sicuro di tali informazioni, consentendo di operare tranquillamente all’interno di uno scenario crittografico di tipo simmetrico, una configurazione con caratteristiche prestazionali molto elevate che viene poco utilizzata in quanto afflitta dal problema dello scambio sicuro della necessaria chiave crittografica, momento che presenta un elevatissimo fattore di rischio.

Algoritmo BB84
Il successivo esempio di applicazione della “Quantum Key Distribution” è riferito all’implementazione dell’algoritmo denominato BB84, algoritmo formalizzato nella prima metà degli anni Ottanta da Charles Bennett e Gilles Brassard.

Affinché si possano sfruttare le possibilità offerte dalla QKD è indispensabile che gli interlocutori condividano un canale di comunicazione di tipo quantistico che può essere, indifferentemente, di tipo simplex (monodirezionale) oppure duplex (bidirezionale); essi devono inoltre possedere degli opportuni strumenti in grado di inviare e ricevere delle particelle.
Ipotizzando i soliti interlocutori Alfa e Beta, estesi in questa occasione da un attaccante Gamma, e presupponendo l’esistenza di un canale trasmissivo in fibra ottica (canale di comunicazione quantistico) capace di veicolare singoli fotoni (particelle neutre caratterizzate da una velocità di propagazione nel vuoto di circa 300.000 km/s che, nella pratica, sono generate da una luce Laser), la cronologia reale delle operazioni è di seguito riepilogata:

  1. Alfa invia dei singoli fotoni a Beta attraverso la fibra ottica; tali fotoni sono orientati da Alfa in modo random, utilizzando un insieme di quattro possibili angolazioni (0, 45, 90 o 135 gradi);
  2. Beta verificherà la polarizzazione dei fotoni ricevuti utilizzando un filtro in grado di identificare le differenti angolazioni, per fare questo userà una base di riferimento, assi (0 e 90 gradi) oppure diagonali (45 e 135 gradi) scelta in modo arbitrario;
  3. Beta, utilizzando un ordinario canale di comunicazione, informerà Alfa del metodo impiegato, senza però informarlo del risultato da lui ottenuto;
  4. Alfa comunicherà a Beta gli orientamenti per lui corretti, consentendo a quest’ultimo di eliminare tutti i fotoni segnalati come non corretti e convertire i rimanenti in valori binari (quindi 1 oppure 0), sulla base del loro orientamento, valori binari che una volta accorpati costituiranno la chiave crittografica da utilizzare;
  5. una eventuale attività di intercettazione della chiave condotta da Gamma dovrà essere seguita da una misurazione dell’orientamento dei fotoni, misurazione che non potrà essere in questo caso confermata, dando luogo all’impossibilità di interpretare la chiave adoperata.



Figura 6 – Quantum Key Distribution.

All’interno del processo appena descritto, brevemente sintetizzato in Figura 6 (dove i numeri riportati di fianco agli orientamenti rappresentano il valore binario da attribuire alla particella), concretizzano, di fatto, uno scenario di tipo “One Time Pad”: da osservare che i legittimi interlocutori (Alfa e Beta) non sono in grado di conoscere in anticipo quale chiave verrà poi adoperata, in quanto essa rappresenta il risultato delle loro scelte arbitrarie; un ulteriore aspetto che vale la pena di evidenziare riguarda l’invulnerabilità di sistema del genere, invulnerabilità che non deriva dall’impossibilità per un malintenzionato di intercettare le comunicazioni, bensì dall’inutilità pratica di tale attività.

Lo Spazio di Hilbert
Una brevissima parentesi matematica in relazione agli orientamenti di riferimento scelti da Beta, in quanto essi concretizzano una base del cosiddetto “Spazio di Hilbert”, una generalizzazione mediante uno “spazio vettoriale” della nozione di “spazio euclideo” introdotta dal matematico David Hilbert agli inizi del Novecento: una generalizzazione degna di nota, considerando il ruolo cruciale che essa ricopre nell’ambito della meccanica quantistica.

Principio di indeterminazione di Heisenberg
Non è possibile esaurire questo articolo senza aver citato uno dei pilastri portanti della fisica quantistica applicata alla crittografia: “il principio di indeterminazione di Heisenberg” eunciato nella seconda metà degli anni Venti da Werner Karl Heisenberg, Premio Nobel per la fisica onché fondatore della meccanica quantistica.
Tale principio, riassunto in modo quanto più esemplificativo, stabilisce che non è possibile conoscere contemporaneamente coppie di proprietà quantistiche delle particelle elementari (come, per esempio, nel caso di un fotone, la sua velocità e posizione).
Sebbene numerosi illustri scienziati, tra cui anche Albert Einstein, abbiano cercato con i loro studi di confutare tale principio, attribuendo l’impossibilità di compiere questa operazione ai limiti delle tecniche e degli strumenti di misurazione correnti, negli anni a seguire si è giunti alla conclusione che tali limitazioni esistono, a prescindere dalla bontà delle tecniche e degli strumenti di misura adoperati, rivelandosi quindi un limite non valicabile.
Dal “principio di indeterminazione di Heisenberg” discende direttamente una proprietà di importanza fondamentale per la sicurezza delle informazioni veicolate mediante i sistemi di crittografia quantistica, considerando che qualunque tentativo di intercettazione, quindi di rilevazione di una certa proprietà delle particelle che costituiscono l’informazione, condurrà inevitabilmente a un’alterazione permanente del loro stato quantistico, oltre che all’impossibilità per chi opera di effettuare ulteriori misurazioni: in tale scenario risulta evidente come i legittimi interlocutori siano in grado di accertare un’eventuale compromissione delle informazioni da loro veicolate.
Relativamente al protocollo BB84 descritto in precedenza, la sicurezza che la comunicazione tra le parti legittime non è stata intercettata da terzi (nel caso dell’esempio da Gamma) deriva dalla constatazione che se Gamma avesse intercettato i fotoni veicolati tra Alfa e Beta, in virtù del “Principio di indeterminazione di Heisenberg”, questi sarebbero stati inevitabilmente modificati, introducendo così degli errori sia nelle misurazioni di Beta, sia, conseguentemente, nei valori binari che costituiscono la chiave: per tale ragione, nel momento di eliminare tutti i fotoni segnalati come non corretti da Alfa e convertire i rimanenti in valori binari e quindi nella chiave di crittografia da impiegare, Beta genererà una chiave differente da quella di Alfa; tale differenza segnala in modo inequivocabile un’avvenuta intercettazione.

Hacking del protocollo BB84
Quel che è stato detto fin qui potrebbe indurre il lettore a pensare che il protocollo BB84 rappresenti oggi il “deus ex machina” in ambito crittografia e ciò è in parte vero, almeno relativamente alle implicazioni di carattere teorico.
Uno dei problema che inficia la sua sicurezza delle applicazioni pratiche deriva dalla attuale impossibilità di schermare completamente il sistema di comunicazione adoperato, così da renderlo immune a ogni disturbo: questo si traduce in una sistematica e consistente percentuale di errori che affligge il sistema, percentuale oggi stimata nell’ordine del venti per cento.
Sfruttando questo assunto e, in particolare, approfittando della necessaria tolleranza agli errori che tali sistemi devono possedere, un gruppo di fisici dell’Università di Toronto è riuscita a violare un sistema di produzione basato sulla “Quantum Key Distribution”, quindi sul protocollo BB84.
In relazione alla cronologia delle operazioni citata in precedenza, essi hanno violato il sistema intervenendo all’interno del processo di orientamento dei fotoni, cioè nel momento in cui Alfa invia i fotoni a Beta; per ottenere che la chiave crittografica intercettata fosse valida, il sistema è stato “confuso” introducendo in modo artificiale un’alta percentuale di errori, errori indotti ma del tutto indistinguibili da quelli endemici al sistema in uso.

Conclusioni
In modo assolutamente speculare ai risvolti pratici cui prima si è fatto accenno, univocamente mirati alla protezione delle informazioni mediante tecniche di crittografia sempre più difficili da violare, si profilano in futuro ulteriori applicazioni delle leggi della “meccanica quantica“ orientate alla realizzazione di “elaboratori quantici”, sistemi di calcolo in grado di operare con logiche assolutamente rivoluzionarie e per questo capaci di compiere operazioni oggi ritenute impossibili, come l’esecuzione di enormi computazioni in pochi attimi.
Elaboratori del genere, per i quali comunque si stimano tempi di realizzazione nell’ordine di parecchi decenni, potrebbero ricavare, in modo pressoché istantaneo, una chiave privata a partire da quella pubblica, compromettendo totalmente la sicurezza di qualunque algoritmo crittografico a chiave pubblica.
A prescindere da ogni cosa, comunque, nel momento che applicazioni del genere diverranno concretamente disponibili, si dovrà radicalmente cambiare il modo di intendere la crittografia, rivedendo il tutto alla luce dei nuovi mezzi disponibili, mezzi che potrebbero un giorno concretizzare il sogno di chi opera in questo settore: la realizzazione di un sistema inviolabile sul piano teorico ma, questa volta, anche su quello pratico.

Ritorna all'indice degli articoli Index


 
Roberto Saia  -  All Rights Reserved