Quanti e Segreti Un invito alla crittologia quantistica

Quanti e Segreti

Un invito alla crittologia quantistica

Università di

Camerino

Stefano Mancini

Comunicazioni…

 Tutti i partecipanti possono stampare direttamente un attestato di partecipazione compilando il modulo presente su:

http://darwin.unicam.it/formazione/

 La Password è: k99X6%xp

 Il modulo va compilato durante il webinar

 I docenti iscritti su SOFIA potranno scaricare l’attestato completo di tutto il percorso una volta terminati i laboratori

 Per i docenti non iscritti su SOFIA sarà predisposto un modulo dove inserire i propri dati al fine di ottenere poi una certificazione

Per iniziare…

• krupto, ma no steganografia

• utenti legittimi, mittente e ricevente (Alice & Bob)

• utente illegittimo, eavesdropper (Eve)

• messaggio in chiaro (plain-text), messaggio cifrato (cipher-text o crittogramma), chiave

• cifrario, codice

• crittografia, crittoanalisi, crittologia

“Il desiderio di svelare segreti è profondamente radicato nella mente umana; la possibilità di partecipare a conoscenze negate ad altri eccita infatti anche la mente meno curiosa”

- John Chadwick, The Decipherment of Linear B

Sommario

 Uno sguardo storico

 Un codice inviolabile

 La crittografia a chiave pubblica

 Un salto nel futuro

 La distribuzione quantistica delle chiavi (QKD)

 Oltre la QKD, il bit commitment

 Conclusioni

Atbash ebraico

L’atbash è un codice di sostituzione monoalfabetica, che viene utilizzato alcune volte anche nella Bibbia, per esempio nel libro di Geremia (25:26) si trova Sheshakh invece di Babel:

“Insomma, feci bere da quella coppa tutti i regni che sono sulla terra e lasciai per ultimo il re di Sheshakh”

Sostituzione Monoalfabetica

Chiamiamo Alfabeto l’insieme dei simboli che intendiamo utilizzare. Esempio di alfabeto con 26 simboli:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Uno dei primi codici a sostituzione monoalfabetica, è quello di Giulio Cesare (50 AC), che spostava semplicemente di tre

passi l’alfabeto in modo ciclico:

ABCDEFGHIJKLMNOPQRSTUVWXYZ DEFGHIJKLMNOPQRSTUVWXYZABC Per decifrare si sposta indietro di tre.

Solo gli utenti legittimi sanno di quanto spostare (chiave).

Esempio

In questo modo l’incipit della Divina Commedia:

NEL MEZZO DEL CAMMIN DI NOSTRA VITA MI RITROVAI PER UNA SELVA OSCURA

diventa:

QHO PHCCR GHO FDPPLQ GL QRVWUD YLWD PL ULWURYDL SHU XQD VHOYD RVFXUD

Se spostiamo di 6 invece di 3 otteniamo:

TKR SKFFU JKR IGSSOT JO TUYZXG BOZG SO XOZXUBGO VKX ATG YKRBG UYIAXG

Un po’ di matematica

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Ad ogni simbolo si associa un numero intero x (nel nostro caso da 0 a 25 dove 0-A e 25-Z), quindi un messaggio risulta

M = x₁ x₂ . . . x_n

Lo spazio K delle chiavi contiene 25 elementi, gli interi 1, ... 25.

Per ogni chiave k c’è una funzione di cifratura:

y=_k (x) = x + k (mod 26) Nel codice di Cesare k = 3.

Per ogni chiave k c’è anche una funzione che decifra D_k che è:

D_k (y) = y -k (mod 26)

Esempio: la parola ‘GATTO’ diventa M = 06 00 19 19 14.

Se scegliamo k = 15 si ha: ₁₅(M) = 21 15 08 08 03 V P I I D

Il metodo di esaustione

Ci sono poche chiavi. Soltanto i numeri da 1 a 25.

Quando le chiavi sono poche, per scoprire il messaggio è sufficiente provarle tutte una dopo l’altra!

Finora abbiamo considerato soltanto 25 permutazioni cicliche dei numeri 0 ... 25. Nessuno ci impedisce di utilizzare una

generica permutazione :

_(M) = (x₁) (x₂) . . . (x_n) Lo spazio delle chiavi diviene immenso!

Ci sono 26!=26x25x24x….x3x2x1 permutazioni su 26 simboli.

L’ordine dello spazio delle chiavi è circa 4.03x10²⁶.

Non è più possibile violare il codice con la sola forza bruta!

Le origini della crittoanalisi

Baghdad, al-Kindi (800-873)

Sulla decifratura di messaggi crittografici

L’indagine statistica

The Gold Bug, 1843. Un esempio di applicazione di questa tecnica si trova nel racconto di Edgar Allan Poe ‘Lo scarabeo d’oro’.

Sostituzione polialfabetica

Si può dire che la crittografia moderna sia nata nel 1586, quando il diplomatico francese Blaise de Vigenère (1523-1596) pubblicò il cifrario che porta il suo nome.

L’idea di Vigenere è quella di utilizzare più di una permutazione dell’alfabeto. Se abbiamo k permutazioni ₁ ₂ . . . _k :

Esempio con permutazioni cicliche e parola chiave: MELA = 12 04 11 00

_(M) = ₁(x₁) ₂(x₂) . . . _k(x_k) ₁(x_k+1) ₂(x_k+2) . . .

C I V E D I A M O D O M A N I

M E L A M E L A M E L A M E L

O M U E P M L M B H A M M R T

02 08 09 04 03 08 00 12 14 03 14 12 00 13 08 12 04 11 00 12 04 11 00 12 04 11 00 12 04 11 14 12 20 04 15 12 11 12 00 07 25 12 12 17 19

Come violare i codici

di sostituzione polialfabetica

Nel 1863 Friedrich Kasiski comprese che, se è nota la lunghezza k della parola chiave, il problema di rompere un codice di sostituzione polialfabetica si può ridurre a quello di decifrare k codici monoalfabetici.

Infatti i simboli x₁, x_k+1, x_2k+1, . . . , x_hk+1 saranno cifrati dalla permutazione

₁, i simboli x₂, x_k+2, x_2k+2, . . . , x_hk+2 saranno cifrati dalla permutazione ₂, e così via.

Si tratta di una idea veramente algebrica: un codice complesso viene spezzato nella somma di k codici semplici.

Metodo di Kasiski: Se la parola chiave ha lunghezza k, si costruiscono (prendendo una lettera ogni k) k messaggi, ognuno dei quali è stato codificato con una singola permutazione _i .

Su ognuno dei k messaggi trovati si utilizza la indagine statistica.

La chiave deve essere lunga

Kasiski stesso descrisse un metodo per trovare la lunghezza della parola chiave, basato sulla distanza tra segmenti uguali nel messaggio cifrato.

Se, per esempio, xyz appare più volte a distanze 10 e 15, è probabile che la lunghezza sia 5.

Esistono metodi molto efficienti per trovare la lunghezza, come l’indice di coincidenza I di Friedman (1922).

I è la probabilità di trovare due simboli identici scegliendo a caso la loro posizione; è tipico di ogni lingua I_L=Σ_i=0²⁵ p_i²

I=I_L sostituzione monoalfabetica I<I_L sostituzione polialfabetica

La macchina Enigma

Macchina a rotori Enigma usata dai Tedeschi durante la Seconda Guerra Mondiale

I rotori

Premendo un tasto un rotore si spostava di uno scatto, e la permutazione cambiava.

Le permutazioni si ripetevano, con tre rotori, soltanto dopo 26 x 26 x 26 = 15.756 lettere. Dunque la lunghezza della parola chiave, ovvero il numero delle permutazioni utilizzate in sequenza, era pressoché uguale alla lunghezza del messaggio, se il messaggio non era lunghissimo.

Le ‘bombe’ di Turing

La correlazione esistente tra le permutazioni successive e altri errori fatti dai Tedeschi permisero al team diretto dal grande matematico Alan Turing e da Gordon Welchman di rompere il codice Enigma. Furono usati i primi calcolatori elettrici, particolari macchine dette ‘bombe’, ognuna delle quali simulava il lavoro di dodici macchine Enigma.

La rottura del codice Enigma fu di capitale importanza per le sorti della guerra.

Crittografi vs Crittoanalisti

Esiste un codice perfetto?

Il cifrario One Time Pad

01011100 11001010 10010110

plaintext KEY

cryptogram

10010110 11001010 01011100

1 0 0 1 0 1 1 0

KEY cryptogram

plaintext

I numeri interi che costituiscono plaintext, key e cryptogram possono essere rappresentati nella forma binaria

One Time Pad è inviolabile a patto che il materiale di chiave sia random, lungo quanto il messaggio e utilizzato una sola volta (Shannon, 1949).

Problema della

distributione delle chiavi

KEY 0 0 1 0 1 1 0

?

KEY 0 0 1 0 1 1 0

Prima di scambiarsi un segreto, Alice e Bob

debbono condividere un segreto!

Possibili soluzioni

 Crittografia a chiave pubblica

sicurezza basata sulla complessità computazionale

 Crittografia quantistica

sicurezza basata su principi fondamentali della fisica

Crittosistemi a chiave pubblica

Alice utilizza la chiave

pubblicata da Bob per cifrare

Bob decifra con la chiave privata (legata matematicamente a

quella pubblica)

 Scelti N primo e g<N, essi vengono resi pubblici

 Alice sceglie random x<N ed invia a Bob u=g^x (mod N)

 Bob sceglie random y<N ed invia ad Alice v=g^y (mod N)

 Alice calcola v^x (mod N) = g^xy (mod N)

 Bob calcola u^y (mod N) = g^xy (mod N)

 Eve dovrebbe calcolare x=log_g u (mod N) e y=log_g v (mod N), ma non è facile!

Crittosistema di Diffie & Hellman (1976)

La sicurezza

Con la chiave privata la decifratura deve essere facile.

Con la sola chiave pubblica la decifratura deve essere difficile.

Ricorrere a funzioni a senso unico.

Facile e difficile

L

) exp(L

INPUT SIZE

Execution Time

P NP EXP

BPP

Discrete log and factoring

Moltiplicare e Fattorizzare

 fattorizzare un numero con L cifre decimali N=10^L

 # divisioni richieste (approsimativamente) N =10^L/2

 Fattorizzare un numero con L=100 cifre decimali con metodo delle divisioni supponendo 10¹⁰ divisioni/sec richiederebbe 10⁴⁰ sec

 10¹⁷ sec ?

Un piccolo problema….

La sicurezza dipende da proposizioni matematiche non dimostrate, quali la difficoltà di fattorizzare.

Qualcuno potrebbe inventare algoritmi più veloci ed efficienti per risolvere il problema della fattorizzazione e ciò porterebbe al crollo di tutti gli attuali sistemi di sicurezza!

Un ‘salto’ nel futuro

1m 1nm

faster smaller shrinking computer

Every 18 months microprocessors double in speed

FASTER = SMALLER Moore’s Law

Un esperimento mentale

L’origine di un nuovo ‘credo’

 Possiamo avere una sovrapposizione coerente di due o più stati di un singolo sistema in differenti punti dello spazio allo stesso istante di tempo

 Mentre misuriamo una grandezza fisica alteriamo lo stato del sistema forzandolo a ‘collassare’ in uno dei suoi possibili autostati. Lo stato nel quale il sistema

‘collassa’ dipende dalla probabilità di occorrenza di tale stato

Neils Bohr & Albert Einstein

Dal bit al quantum bit

Come avere sovrapposizioni coerenti ?

Þ y = c

y

+ c

y

^{, c}

^,c

Î C

Esempio (matematico):

y

= 1

2 ( y

± y

) ^{; y}

1

= 1

2 ( y

± y

)

Esempio (fisico):

y

^Pr = c

y

^Pr = c

Come descrivere la misura ?

y = c

y

+ c

y

y = c

y

+ c

y

Proiezioni

y

^Pr = c

y

^Pr = c

osservabile X

osservabile Z

Una tabella riassuntiva

y

^Z y

y

^Z y

y

^X y

^Pr = 1 2; y

^Pr = 1 2 y

^X y

^Pr = 1 2; y

^Pr = 1 2 y

^Z y

^Pr = 1 2; y

^Pr = 1 2 y

^Z y

^Pr = 1 2; y

^Pr = 1 2 y

^X y

y

^X y

Stato a priori

Stato a posteriori Osservabile

Spingiamo il là l’immaginazione….

0 or 1 0 or 1 or 0 1

Classical Bit Quantum Bit

Classical register Quantum register

101 000 001 010 011

100 101 110 111

Il computer quantistico

000 001 010 011 100 101 110 111

F(000) F(001) F(010) F(011) F(100) F(101) F(110) F(111)

F (x)

Quantum

Processor

Verso il trionfo dei crittoanalisti?

 Nel 1994 Peter Shor propose un algoritmo che sfruttava il

parallelismo quantistico per risolvere efficientemente il problema della fattorizzazione

 Implementando tale algoritmo, la fattorizzazione di un numero di 100 cifre richiederebbe solo qualche secondo!

 Questo significa la possibile crisi degli attuali sistemi crittografici!

La vendetta dei crittografi….

Canale quantistico

Un protocollo quantistico per la distribuzione delle chiavi (BB84 QKD)

Canale classico pubblico

0 1 1 0 1 1 0 0 1 0 0 1



0 Z



Z 0



1 X



Z

0 1

Z 



X 



Z X X Z X Z Z Z X X Z Z

Riconciliazione delle basi:

Controllo del QBER:

Dei restanti bits, N vengono confrontati pubblicamente per stabilire il tasso di errore nella stringa finale (chiave)

0 1 1 0 1 1 0 0 1 0 0 1

Z X X Z X Z Z Z X X Z Z

Sicurezza QKD

Z (







Z (



Z (p=1/2) X (p=1/2)

Probabilità che N bits di controllo coincidano nonostante l’azione di eavesdropping:







Ancora sulla QKD

 La QKD non può impedire l’intrusione, ma la sua

sicurezza sta nella possibilità di scroprire l’intrusione!

 Il guadagno di informazione da parte di Eve implica un disturbo (relazione di indeterminazione)

 E’ dimostrabile la sicurezza assoluta della QKD con un quantum bit error rate >0 (max 11%).

 Dalla prima dimostrazione in laboratorio nel 1992 su di una distanza di 32 cm all’esperimento su 7600 Km tra Austria-Cina nel 2018.

 QKD è oramai una tecnologia affermata!

Ancora sulla QKD

Oltre la QKD

 Nella computazione a due parti Alice (Bob) ha un input privato x (y) e vorrebbe aiutare Bob a calcolare una prescritta funzione f(x,y) senza rivelare x

 Il bit commitment è una primitiva di calcolo distribuito sicuro

 Non esistono protocolli classici che garantiscono sicurezza assoluta per il bit commitment. Può la

meccanica quantistica risolvere anche questo problema?

“The spooky action at distance”

y

( )

( ) ^y

^; ( ) ^y

( ) ^y

stati separabili

Un’azione di Alice sul suo quantum bit ha un effetto istantaneo a distanza anche sul quantum bit di Bob!

y

( )

( ) ^y

⁺ ( ) ^y

( ) ^y

2 stato 'entangled'

y

( )

( ) ^y

⁺ ( ) ^y

( ) ^y

2

Un approccio informatico alla fisica ?

La fisica quantistica può essere vista non come una teoria meccanica delle onde e delle particelle, ma come una teoria circa le possibilità (o impossibilità) nell’elaborare informazione:

 Impossibilità di segnali superluminali

 Impossibilità di perfetto broadcasting (cloning) dell’informazione contenuta in uno stato sconosciuto

 Impossibilità di bit commitment assolutamente sicuro

Conclusioni

Crittologia quantistica:

Un’arena per apprendere Matematica, Fisica, Informatica

Utili letture:

“Codici e segreti”, Simon Singh, BUR 2006

“Crittografia: dai bit ai qubit”, S. Mancini e C. Toffalori, XlaTangente n° 2, pag.25 (2015) online

Ulteriori informazioni:

stefano.mancini@unicam.it http://qmit.phys.unicam.it