Codici e segreti - fabiobonoli .it

Codici e segreti
storie e matematica intorno alla crittografia
21 dicembre 2010
Prof. Fabio Bonoli
Introduzione
Negli anni Sessanta e Settanta dello scorso secolo, in
pieno sviluppo informatico, le vecchie macchine cifranti
elettromeccaniche usate per scopi di crittografia – vale a
dire per trasmettere messaggi al riparo da possibili,
indesiderate, intercettazioni – vennero progressivamente
sostituite da dispositivi elettronici che, oltretutto,
garantivano maggiore velocità, maggiore sicurezza e
risparmio economico.
Introduzione
Allo stesso tempo, il grande pubblico venne a conoscenza
di alcuni successi crittografici di notevole rilievo che, fino
ad allora, erano ancora sotto segreto.
L’immaginazione fu colpita soprattutto da vicende belliche
relative alla Seconda Guerra Mondiale, nella quale si
intrecciano spionaggio, cultura meccanica e capacità di
addentrarsi nelle strutture logiche e combinatorie più
intricate, come nel caso della macchina Enigma, da
parte delle forze alleate in Europa.
Introduzione
Fu in questo contesto particolare che, nel 1976, due
scienziati americani, Whitfield Diffie e Martin Hellman
diedero vita al nuovo settore della crittografia a chiave
pubblica.
Questa idea, solo due anni più tardi ricevette una concreta
implementazione nel sistema detto RSA dal nome dei
suoi ideatori: Ronald Rivest, Adi Shamir e Leonard
Adleman.
Introduzione
La chiave pubblica ha trasformato la crittografia da
un’antica ‘arte’ in una scienza moderna.
Ciò è avvenuto grazie all’incontro della pratica millenaria
della crittografia, dotata soprattutto di regole empiriche,
con una scienza formale rigorosa – la teoria dei numeri –
che, nella concezione di Gauss è la “regina della
matematica” (che a sua volta, sempre nella sua
concezione, è la “regina della scienza”).
Vi racconto 3 storie
1. Gennaio 1917: prima guerra
mondiale, U-boot e un certo
ministro Zimmermann…
2. Ottobre 1586: Maria Stuarda sta
per essere giustiziata…
3. 1820: i crittogrammi Beale e una
caccia al tesoro non ancora
conclusa…
Prima guerra mondiale
• Il presidente USA Wilson non vuole mandare
truppe in Europa, nonostante le forti pressioni
britanniche.
• 1916: Berlino, viene nominato ministro degli Esteri
Arthur Zimmermann
• 1915: un U-Boot tedesco aveva affondato il
transatlantico Louisiana, causando più di 1500
morti. Gli Usa non intervengono, la Germania
assicura di far emergere i sottomarini, prima di
attaccare.
Prima guerra mondiale
• 1917: Zimmermann decide di
intensificare la guerra navale,
sperando in una fine rapida della
guerra… e gli Stati Uniti?
Ecco il piano Zimmermann:
alleanza con il Messico, che
avrebbe dovuto invadere gli USA
reclamando vecchi territori; il
presidente messicano doveva
poi mediare per convincere il
Giappone ad attaccare gli Stati
Uniti.
Prima guerra mondiale
Intendiamo iniziare una guerra sottomarina senza restrizioni a partire dal
primo febbraio. Tenteremo, nonostante ciò, di far restare neutrali gli Stati
Uniti. Qualora risultasse impossibile, intendiamo rivolgere al Messico
una proposta di alleanza sulle basi seguenti: muovere guerra insieme,
ottenere la pace insieme, generoso sostegno finanziario e nostro
assenso alla riconquista da parte del Messico dei territori perduti in
Texas, Nuovo Messico e Arizona. A lei la definizione dei particolari.
Informerete il Presidente (della Repubblica Messicana) di quanto sopra,
nella massima segretezza, non appena lo scoppio della guerra con gli
Stati Uniti sia certo, aggiungendo il suggerimento che egli, di sua
iniziativa, inviti il Giappone ad aderire immediatamente, e nel contempo
funga da intermediario tra noi e il Giappone.
Vi prego di richiamare l'attenzione del Presidente sul fatto che l'impiego
senza restrizioni dei nostri sottomarini schiude la possibilità di
costringere l'Inghilterra alla pace entro pochi mesi. Accusare ricevuta.
Zimmermann
Prima guerra mondiale
Prima guerra mondiale
Gli inglesi intercettano e decifrano il messaggio, che
giunse così agli americani, ma non in modo diretto.
Gli inglesi non volevano far capire di essere in grado
di decifrare i messaggi tedeschi. Con l’aiuto dei
servizi segreti riuscirono ad intercettare la copia del
telegramma giunta in Messico.
Wilson chiede al congresso degli Stati Uniti d’America
di considerare il telegramma come un atto di
guerra.
La corrispondenza segreta di Maria Stuarda
15 ottobre 1586: Maria Stuarda entra nell’affollata aula
di giustizia del castello di Fotheringhay.
Maria, regina degli scozzesi, è accusata di tradimento:
avrebbe partecipato ad un complotto mirante ad
uccidere la regina Elisabetta.
Sir Francis Walshingham intende dimostrare che la
Stuarda merita la morte perché partecipe alla
congiura.
Solo così Elisabetta firmerà la sua condanna.
La corrispondenza segreta di Maria Stuarda
Gradirei sapere i nomi e i meriti dei sei gentiluomini che
devono attuare il disegno; potrei infatti, conoscendo le
parti interessate, dare al riguardo ulteriori consigli cui
sarà necessario attenersi, e indicazioni su come
procedere in taluni frangenti: e appena potete, per la
stessa ragione [fatemi sapere] chi sia già stato, e in che
misura, messo a parte di ciò.
La corrispondenza cifrata di Maria di Scozia dimostra che
crittare in modo debole può esser peggio che non crittare.
Infatti la regina e Babington si espressero senza perifrasi
perché contavano sulla cifratura; se i biglietti fossero stati in
inglese ordinario, avrebbero alluso ai loro piani con
maggiore discrezione.
La caccia al tesoro Beale
Tra la gente comune il secondo Ottocento vide un
grande aumento della curiosità per le scritture
segrete.
La nascita del telegrafo aveva aumentato l'interesse
commerciale per la crittografia.
Anche i privati cittadini presero coscienza della
necessità di proteggere i loro messaggi, quando
riguardavano questioni delicate e strettamente
personali. Per farlo erano disposti a crittarli, anche
a costo di pagare una tariffa più elevata.
La caccia al tesoro Beale
Per esempio, nell'Inghilterra vittoriana i giovani
innamorati spesso non erano liberi di manifestare i
loro sentimenti.
Così finirono per ricorrere agli spazi a pagamento dei
quotidiani, ai quali inviavano romantici messaggi
cifrati dopo aver concordato la chiave con l'anima
gemella.
Queste «colonne dei sospiri» <agony columns>,
diventarono una ghiotta riserva di caccia per i
crittoanalisti, che le sottoponevano ad analisi
statistica e cercavano di ricostruirne il contenuto.
La caccia al tesoro Beale
II crescente interesse della gente comune per la crittografia
fece sì che codici trovassero posto nella letteratura del
secondo Ottocento.
Nel Viaggio al centro della Terra, di Jules Verne, vi è la
decifrazione di una pergamena coperta di caratteri
misteriosi.
In Gran Bretagna Sherlock Holmes era esperto di crittografia.
Sull'altra sponda dell'Atlantico, Edgar Allan Poe si occupò
anch'egli di crittoanalisi. Scrivendo per l’Alexander Weekly
Messenger di Philadelphia, il celebre autore sfidò i lettori a
sottoporgli qualunque tipo di cifratura. I crittogrammi inviati
alla rivista furono centinaia, ed egli li tradusse tutti.
La caccia al tesoro Beale
Nel 1843, Poe scrisse un racconto sui codici segreti che per
parere dei crittografi professionisti è la miglior opera
letteraria sull'argomento.
Lo scarabeo d'oro narra l'immaginaria avventura di William
Legrande, che s'imbatte in uno strano coleottero - uno
scarabeo di colore dorato - e lo raccoglie con un foglio di
carta trovato nei pressi. La sera stessa Legrande usa il
foglio per tracciare uno schizzo dell'insetto; ma quando lo
avvicina al focolare, il calore fa comparire una serie di segni,
invisibili fino a quel momento perché tracciati con l'inchiostro
simpatico. Studiando i segni Legrande si convince di essere
di fronte a un crittogramma, che custodisce l'ubicazione del
tesoro del capitano Kidd.
La caccia al tesoro Beale
Il racconto di Poe è pura invenzione, ma c'è una storia vera del
XIX secolo che lo ricorda da vicino.
Il caso dei crittogrammi Beale ha per protagonisti avventurieri
del selvaggio West, un cowboy che aveva accumulato
un'ingente fortuna, un tesoro sepolto del valore di 20 milioni
di dollari, e una serie di fogli coperti di simboli crittografici.
Molto di quanto sappiamo della vicenda, crittogrammi compresi,
è esposto in un libretto edito nel 1885 nella cittadina di
Lynchburg, in Virginia.
Solo 23 pagine che hanno frustrato generazioni di crittoanalisti
e sedotto molti cacciatori di tesori.
La caccia al tesoro Beale: i fatti
Nel gennaio del 1823, un forestiero di nome Thomas J. Beale
arrivò a Lynchburg e varcò il portone dell'Hotel Washington.
Uomo dagli occhi neri e capelli corvini, più lunghi di quanto
si usasse a quel tempo. Era robusto e in eccellente forma
fisica. Tuttavia, spiccava la sua carnagione scura, come se
avesse passato molto tempo esposto al sole.
Beale passò il resto dell'inverno da Morriss, e sebbene la sua
compagnia fosse “gradita a tutti, e in special modo alle
signore", egli non parlò mai del suo passato, della sua
famiglia o della ragione che l'aveva condotto lì.
Poi, alla fine di marzo, se ne andò. La sua partenza fu
improvvisa e inspiegata come il suo arrivo.
La caccia al tesoro Beale: i fatti
Due anni dopo, nel gennaio 1825, Beale tornò all'Hotel
Washington "più corvino e abbronzato che mai». Di nuovo
passò l'inverno a Lynchburg e scomparve in primavera; non
prima, però, di aver affidato a Morriss una scatola metallica
chiusa a chiave.
L'albergatore mise la scatola in cassaforte e non vi pensò più,
finché ricevette una lettera dal misterioso cliente.
Beale svelò la vera funzione della scatola metallica.
Contiene carte di importanza vitale per le mie fortune e per
quelle di diverse persone con cui sono in affari, e
nell'eventualità della mia morte la sua perdita sarebbe
irreparabile. Comprenderete, quindi, la necessità di fare
ogni sforzo perché un simile disastro non si verifichi...
La caccia al tesoro Beale: i fatti
Morriss custodì la scatola con zelo, aspettando che il
proprietario venisse a recuperarla, ma Beale non tornò mai
più a Lynchburg. Alla fine, nel 1845, la curiosità ebbe la
meglio e la serratura fu forzata. Nella scatola c'erano 3 fogli
coperti di numeri, e un biglietto scritto a mano da Beale, che
spiegava parecchie cose.
Nel 1817, Beale aveva iniziato un viaggio attraverso l'America
con altre persone. La brigata,inseguendo mandrie di bufali,
un giorno si accampò in un burrone, 400-500 Km a nord di
Santa Fé. Scoprirono in una fenditura della roccia qualcosa
che a un primo sguardo sembrava oro. Nei successivi
diciotto mesi Beale e i suoi uomini sfruttarono il giacimento
e accumularono un'ingente quantità di oro.
La caccia al tesoro Beale: i fatti
Nel 1823 Beale raggiunse Lynchburg con l'oro e l'argento, e lo
seppellì. Fu in quell'occasione che prese alloggio all'Hotel
Washington e conobbe Morriss. Quando, alla fine
dell'inverno, aveva lasciato l'albergo, Beale aveva raggiunto
i suoi amici, che durante la sua assenza avevano continuato
a sfruttare la miniera.
Dopo un anno e mezzo Beale tornò a Lynchburg, con un
ulteriore carico da aggiungere al tesoro. Questa volta, però,
la sua permanenza in città aveva anche un altro scopo:
Beale, convinto che Morriss fosse un uomo onesto decise di
affidare a lui la scatola di metallo coi 3 documenti cifrati, i
cosiddetti crittogrammi Beale.
La caccia al tesoro Beale: i fatti
Ogni crittogramma consisteva in una serie di numeri.
Il primo foglio chiariva l'ubicazione del tesoro; il secondo
descriveva il tesoro stesso; il terzo indicava gli eredi degli
uomini che l'avevano accumulato.
Nel 1862, Morriss vecchio si confida ad un amico.
Sappiamo solo che fu questo amico a pubblicare, nel 1885, il
famoso libretto usando uno pseudonimo.
Tutto quello che conosciamo di questa storia singolare deriva
dal libretto; esso è l'unica fonte sia dei crittogrammi sia degli
antefatti che Morriss avrebbe narrato.
Inoltre, è da attribuire all'autore la decifrazione del secondo
crittogramma.
La caccia al tesoro Beale
71, 194,38,1701,89,76,11,83, 1629,48,94,63, 132, 16, 11 Ì, 95, 84, 34Ì, 975, 14,40,64,27,81, 139,213.63,90,
1120,8, 15,3, 126,2018,40,74,758,485, 604,230,436,664,582,150,251,284,308,231,124, 211, 486, 225,
401,370, 11, 101,305, 139, 189,17,33,88,208,193, Ì45, 1,94,73,416,918,263,28,500, 538, 356, 117, 136.
219, 27, 176, 130, 10, 460, 25, 485, 18, 436, 65, 84. 200, 283, 118,320,138,36,416,280,
15,71,224,961,44, 16,401,39,88,61,304, 12,21, 24, 283, 134, 92, 63, 246, 486,682,7, 219. 184, 360,
780, 18, 64,463,474,131, 160,79,73,440,95, 18,64,581,34,69, 128,367,460, 17,81, 12, 103,820,62, 116,
97, 103, 862, 70, 60, 1317, 471, 540, 208, 121, 890, 346, 36, 150, 59, 568, 614,13,
120,63,219,812,2160, 1780,99.35,18,21,136,872,15,28,170,88,4, 30,44, 112,18, 147,436, 195,320,37,
122, 113,6,140,8, 120,305,42,58,461, 44, 106,301, 13,408,680,93,86, 116,530,82,568,9,
102,38,416.89,71,216, 728,965,818,2,38, 121, 195, 14,326, 148,234,18,55, 131,234,361,824,5,
81,623,48.961,19,26,33,10,1101,365,92,88,181,275,346,201,206,86,
36, 219, 324, 829, 840, 64,326,19, 48, 122, 85, 216, 284, 919, 861, 326, 985, 233, 64, 68, 232, 431,
960,50,29,81, 216, 321, 603,14, 612, 81, 360, 36, 51, 62, 194,78,60,200,314,676, 112,4,28, 18,61,
136,247,819,921, 1060,464,895, 10,6,66, 119,38,41,49,602,423,962,302,294,875,78, 14,23, 111,
109,62, 31,501,823,216,280,34,24,150, 1000,162,286, 19,21, 17,340, 19,242.31, 86,234, 140,607,
115,33, 191,67,104,86,52,88,16,80, 121,67,95, 122,216, 548,96, 11 ,201,77,364,218,65,667,890,236,
154,211, 10,98,34, 119,56, 216, 119,71,218,1164,1496,1817,51,39,210,36,3,19,540,232,22,141,617, 84,
290, 80, 46, 207, 411, 150, 29, 38, 46, 172, 85, 194, 39, 261, 543, 897, 624, 18, 212,416, 127,931,
19,4,63,96. 12, 101.418, 16. 140,230,460,538, 19,27,88, 612, 1431,90,716.275,74,83, 11,426,89,72,84,
1300, 1706,814,221,132, 40, 102, 34, 868,975, 1101, 84,16,79, 23, 16, 61, 122, 324, 403,912,227, 936,
447, 55, 86, 34, 43, 212. 107, 96, 314, 264, 1065, 323, 428, 601, 203, 124, 95, 216, 814, 2906, 654,
820, 2, 301, 112, 176, 215, 71, 87, 96, 202, 35, 10, 2, 41,17, 64, 221,736,820,214, 11,60,760.
il primo crittogramma Beale.
La caccia al tesoro Beale
115, 75, 24, 807, 37, 52/ 49, T 7, 31, 62, 647, 22, 7, 15, 1 40, 47, 29, ] 07, 79, 84, 56, 239, 10, 26, 8] 1,5, 196,308,85,52, 160,
136, 59, 211, 36, 9, 46, 316, 554, 122, 106,95,53,58,2,42,7,35, 122,53,31,82, 77.250, 196,56,96, 118,71, 140, 287, 28,
353, 37, 1005, 65, 147, 807, 24, 3, 8, 12, 47, 43, 59, 807, 45, 316, 101, 41, 78, 154, 1005,122, 138,191,16,77, 49,
102,57, 72, 34, 73, 85, 35,37),59,196, 81, 92, 191, 106, 273, 60, 394, 620, 270, 220, 106, 388, 287, 63, 3, 6, 191, 122,
43, 234, 400, 106, 290, 314, 47, 48, 81, 96, 26, 115. 92, 158, 191, 110, 77, 85, 197, 46, 10, 113, 140,353,48, 120, 106, 2,
607, 61,420,811, 29, 125, 14.20,37, 105, 28, 248, 16, 159,7,35, 19,301, 125, 110,486,287,98, 117,511,62,51,220,37, 113,
140, 807, 138, 540, 8, 44, 287, 388, 117, 18, 79, 344, 34, 20, 59, 511, 548,107, 603, 220,7, 66, 154, 41, 20, 50, 6,575,
122, 154, 248, 110, 61, 52, 33, 30, 5, 38, 8, 14,84,57,540,217, 115,71,29,84,63,43, 131,29, 138,47, 73,239,540,52,53,
79, 118,51,44,65, 196, 12,239, 112,3,49,79,353, 105,56,371,557,211,515, 125.360, 133, 143, 101, 15,284,540,252,
14,205, 140,344,26,811, 138, 115, 48, 73, 34, 205, 316, 607, 63, 220, 7, 52, 150, 44, 52, 16, 40, 37, 158, 807, 37, 121,
12,95, 10, 15,35, 12, 131,62, 115, 102,807,49.53, 135, 138,30,31,62,67,41, 85, 63, 10, 106, 807, 138, 8, 113, 20, 32, 33,
37, 353, 287, 140, 47, 85, 50, 37, 49. 47, 64,6,7, 71, 33, 4, 43, 47, 63, 1,27, 600, 208,230, 15, 191, 246, 85,94,511,2,
270,20. 39, 7, 33, 44, 22, 40, 7, 10, 3, 811, 106, 44, 486, 230, 353, 211, 200, 31, 10, 38, 140,297, 61, 603, 320, 302,
666,287, 2, 44, 33, 32, 511, 548, 10, 6, 250, 557, 246, 53, 37, 52, 83, 47, 320, 38, 33, 807, 7, 44, 30, 31, 250, 10, 15, 35,
106, 160, 113,31, 102,406,230,540,320,29,66,33, 101,807, 138,301,316,353, 320, 220, 37, 52, 28, 540, 320, 33, 8, 48,
107, 50, 811, 7, 2, 113, 73, 16, 125, 11, 110, 67, 102, 807, 33, 59, 81, 158, 38, 43, 581, 138, 19, 85, 400, 38, 43, 77, 14,
27, 8, 47, 138,63, 140, 44, 35,22, 177, 106, 250,314,217, 2, 10,7, 1005, 4, 20, 25, 44,48,7,26,46, 110,230,807, 191,34,
112, 147,44, 110, 121, 125,96,41,51, 50, 140, 56. 47, 152, 540, 63,807, 28, 42, 250, 138, 582, 98, 643,32,107, 140, 112,
26,85, 138, 540,53, 20, 125, 371, 38, 36, 10, 52, 118, 136, 102, 420, 150, 112,71, 14,20.7,24, 18, 12,807,37,67,
110,62,33,21,95,220,511, 102,811, 30, 83. 84, 305, 620, 15,2,108, 220,106,353,105,106, 60, 275, 72, 8, 50, 205, 185,
112,125, 540. 65.106, 807, 188, 96,110, 16, 73, 33, 807, 150, 409, 400, 50, 154,285,96, 106,316,270,205,
101,811,400,8,44,37,52,40,241,34,205, 38, 16, 46,47, 85, 24, 44, 15. 64, 73, 138,807, 85, 78, 110, 33, 420,505,53,37,
38, 22,31, 10, 110, 106, 101, 140, 15,38,3, 5,44, 7,98,287, 135, 150,96, 33,84, 125,807, 191,96,511,
118,440,370,643,466, 106,41, 107,603,220,275,30, 150, 105,49,53,287,250,208, 134, 7, 53, 12,47,85,63, 138, 110,21,
112, 140, 485, 486, 505,14,73, 84, 575, 1005,150, 200, 16, 42, 5, 4, 25, 42,8, 16, 811, 125, 160, 32, 205, 603,807, 81,
96, 405, 41, 600, 136, 14, 20, 28, 26, 353, 302, 246,8, 131, 160, 140,84,440,42, 16,8)1,40,67, 10), 102, 194, ) 38, 205,
51, 63, 241, 540, 122, 8, 10, 63, 140, 47,48, 140, 288.
il secondo crittogramma Beale.
La caccia al tesoro Beale
Per esempio, se mittente e destinatario convengono che questa
frase sia il testo chiave, ogni parola viene contrassegnata
numericamente come mostrato.
Dopo di che si compila un elenco, che associa il numero alla
lettera iniziale della parola corrispondente.
1=p 8=c 15=o 2=e 9=q 16=p 3=s 10=f 17=v 4=m
11 =s 18=c 5= e 12=i 19 =n 6=d 13 = t 20 = c 7=c
14=c 21 =m
A questo punto, cifrare un messaggio sostituendo alle lettere
del testo chiaro i numeri corrispondenti dell'elenco. P
corrisponderebbe ai numeri 1 e 16, e ai numeri 2 e 5,
mentre f potrebbe essere sostituita solo dai numero 10.
La caccia al tesoro Beale
Poiché il testo chiave è breve, molte lettere
dell'alfabeto non vi compaiono, e sono prive dì
numeri corrispondenti.
Per cifrare l'intero alfabeto, basterebbe ricorrere a una
chiave più lunga. Il destinatario, che dovrebbe aver
accesso a una copia del testo-chiave, decifrerà il
crittogramma con facilità.
Ma una terza parte che avesse intercettato il
messaggio, per decrittarlo dovrebbe scoprire quale
testo abbia fatto da chiave.
Fu la Dichiarazione di Indipendenza che permise di
decifrare il secondo dei crittogrammi Beale.
Le prime scritture nascoste
Il modo più istintivo è quello di nascondere il
messaggio: in questo caso si parla propriamente
di steganografia.
Mentre quando non si nasconde il messaggio,
bensì il suo contenuto allora si ha a che fare con
la crittografia, termine usato per la prima volta, a
quanto sembra, nel 1641 da John Wilkins, uno
dei fondatori della Royal Society, ma pratica
antica quanto l’uomo.
Le prime scritture nascoste
Uno dei primi esempi documentati di messaggio cifrato
viene fatto risalire a Giulio Cesare, che era solito
ricorrervi nella guerra contro i Galli.
Il sistema cifrante consisteva nel “traslare circolarmente”
l’alfabeto, sostituendo di conseguenza tutte le lettere del
messaggio in chiaro. Ad esempio, con una traslazione di
2 unità dall’alfabeto in chiaro (riga superiore) si ottiene
quello cifrato (riga inferiore):
ABCDEFGHILMNOPQRSTUVZ
CDEFGHILMNOPQRSTUVZAB
Metodi di questo genere sono noti come cifrari di Cesare.
Le prime scritture nascoste
Si hanno a disposizione solo 20 cifrari distinti di questo
tipo, e la chiave cifrante, il segreto speciale, è il numero
n (compreso fra 1 e 20) che specifica di quanto è
necessario traslare l’alfabeto in chiaro per ottenere
quello cifrato.
Un numero molto esiguo di cifrari che si presta ad essere
eluso con pochi tentativi.
Una variazione che aumenta enormemente il numero di
cifrari distinti consisterebbe nell’assumere una
qualunque permutazione delle 21 lettere dell’alfabeto in
chiaro invece di eseguire una semplice traslazione.
I cifrari distinti diventano in questo caso 21! – un numero
altissimo, dell’ordine di 1018 .
Le prime scritture nascoste
Un possibile compromesso allo scopo di generare
una permutazione con un meccanismo
semplice, efficiente e facile da memorizzare:
• si può usare una parola chiave che non abbia
lettere ripetute, come “liceo”, oppure
• eliminare le ripetizioni da un termine scelto (ad
esempio “liceorighi” diventa “liceorgh”)
• e utilizzare la parola per indicizzare le
permutazioni partendo da una posizione
convenuta
Le prime scritture nascoste
la parola chiave viene usata a partire da quella posizione e,
poi, si procede alfabeticamente, saltando ovviamente le
lettere già usate.
Ad esempio, la permutazione che si ottiene con la parola
chiave “liceorgh” a partire dalla posizione 4 è quella che
segue:
ABCDEFGHILMNOPQRSTUVZ
UVZLICEORGHABDFMNPQST
La memorizzazione della chiave (liceorgh, 4) è agevole per
tutti e un cifrario di questo genere sembra al riparo da
attacchi basati su tentativi ripetuti. Ma …
Le prime scritture nascoste
Il crittoanalista, cioè colui che tenta di infrangere il
cifrario, posto di fronte ad un testo cifrato
abbastanza lungo, è a conoscenza del fatto che
il testo in chiaro è scritto in italiano (o in inglese,
o in russo …) e che riguarda affari (o problemi
diplomatici, militari,commerciali, sentimentali …)
e, soprattutto, conosce il dizionario delle
frequenze con cui si ripetono le lettere nei
discorsi del dato argomento.
Le prime scritture nascoste
Studiando le frequenze con cui compaiono le varie lettere
nel testo trasmesso – che deve essere abbastanza
lungo e significativo – si possono fare delle ipotesi
attendibili riguardo al loro significato in chiaro. Altre
informazioni si ottengono ad esempio dalla frequenza
delle lettere ripetute, da particolari associazioni o dalla
loro mancanza
I cifrari polialfabetici
Come rendere uniformi le frequenze nel testo cifrato?
L’idea è quella di ricorrere ad un cifrario polialfabetico, vale
a dire di associare ad ogni lettera in chiaro un simbolo
cifrato in maniera dipendente dal contesto nel quale
avviene la cifratura.
Ad esempio, visto che in italiano la frequenza della lettera
“a” è quasi del 12%, si potrebbero usare 12 simboli
diversi X1,X2,…,X12: il primo viene usato la prima volta
che compare la lettera “a” nel testo in chiaro, il secondo
la seconda volta e così via, circolarmente.
È chiaro, che in questo modo, tutti i simboli cifranti
ricorrono con la stessa frequenza, ma si tratta di un’idea
impraticabile.
I cifrari polialfabetici
Uno dei primi esempi è legato al nome di Leon Battista
Alberti, nella seconda metà del Quattrocento.
L’idea dell’Alberti è quella di usare due dischi concentrici, in
grado di ruotare l’uno rispetto all’altro, e contenenti
l’alfabeto in chiaro (il disco esterno) e quello in cifra (il
disco interno).
I cifrari polialfabetici
Dopo la cifratura di una lettera, ottenuta facendo
corrispondere le lettere dei due dischi che sono
una sopra l’altra, il disco esterno viene ruotato di
una tacca,e la corrispondenza fra le lettere
cambia e cambia tutto l’alfabeto cifrante, che si
ripete dopo un periodo lungo quanto sono le
lettere che compaiono nei dischi.
È chiaro che il congegno può cadere in mano
nemica senza danno: la chiave crittografica in
questo caso è data dall’assetto iniziale dei due
dischi.
I cifrari polialfabetici
Il cifrario che, dal Rinascimento, rimase in uso per
molti secoli e che costituì il paradigma di ogni
metodo di cifratura polialfabetica è legato al
nome del diplomatico francese Blaise de
Vigenère (1523-1596).
L’idea è quella di utilizzare per ogni lettera un
diverso alfabeto cifrante, il quale viene
indicizzato da una parola chiave.
Non è più necessario che la parola chiave sia priva
di lettere ripetute.
I cifrari polialfabetici
Nell’esempio seguente
riprendiamo la
chiave “liceorighi”,
senza modifiche.
Tutti i possibili 20 cifrari
vengono riportati
sotto l’alfabeto in
chiaro come nello
schema che segue:
I cifrari polialfabetici
Il testo da cifrare sia “NEL MEZZO DEL CAMMIN
DI NOSTRA VITA….”.
Per mantenerlo segreto lo cifriamo con la chiave
“LICEORIGHI”.
Sovrapponiamo la chiave tanto quanto basta:
NELMEZZODELCAMMINDINOSTRAVITA
LI CEORI GH I LI CE ORIGHILI CEORIGH
Z O N Q S Q H U M O U…….
I cifrari polialfabetici
Z O N Q S Q H U M O U…….
Si osserva che le prime due lettere “E” sono cifrate
ordinatamente con “O”e “Q”, le due lettere “Z”
sono cifrate ordinatamente con “Q”e “H”.
Viceversa, due “U” del messaggio cifrato
corrispondono rispettivamente ad “O” ed “L”.
Ecco in funzione un cifrario polialfabetico!
I cifrari polialfabetici
Sembra di essere al riparo degli attacchi statistici.
Inizialmente ci furono attacchi sporadici, spesso legati a
conoscenze degli autori e dei possibili messaggi.
Il primo attacco sistematico venne portato alla lunghezza
della chiave, trovata la quale tutto si ripete e si può
considerare di lavorare con spezzoni monoalfabetici.
Un metodo generale per attaccare i cifrari polialfabetici fu
trovato da un ufficiale dell’esercito prussiano, Friedrich
W. Kasiski, il quale trovò una regola per determinare la
lunghezza della chiave.
Intorno all’inizio del Novecento era ormai generalmente
accettata la vulnerabilità dei sistemi polialfabetici ed i
sistemi à la Vigènere persero di interesse.
I cifrari perfetti
Nel contesto dei sistemi meccanici di calcolo, nel
Novecento, sorge l’idea che si possa costruire un cifrario
perfetto, vale a dire un cifrario che non possa essere
infranto.
Il messaggio, ormai, è diventato una successione di bit,
una stringa numerica binaria, e la chiave è un’altrettanto
lunga sequenza di bit generata in modo casuale e
custodita in un libro delle chiavi – da usare una sola
volta.
Il sistema non è decrittabile con metodi statistici, poiché
ogni carattere in chiaro può essere rappresentato con la
stessa probabilità da un qualunque carattere cifrato, e
non esistono più modelli perché la scelta della chiave
avviene in modo casuale.
I cifrari perfetti
Lo schema è il seguente:
Qui, k rappresenta la chiave e le operazioni di somma e
sottrazione sulle cifre binarie del messaggio e della
chiave sono proprio, almeno nella prima applicazione, le
operazioni di somma e sottrazione binarie, con il
vantaggio che il meccanismo per cifrare coincide con
quello per decifrare.
I cifrari perfetti
I due esempi che seguono dimostrano la
sostanziale semplicità della cifratura
computerizzata.
Innanzitutto, supponiamo che il messaggio che
vogliamo cifrare sia CESENA, e che intendiamo
servirci di una semplice versione computerizzata
di una cifratura per trasposizione. Prima di
crittarlo, dobbiamo convertire il messaggio in
codice ASCII.
Testo chiaro: CESENA = 1000011 1000101
1010011 1000101 1001110 1000001
I cifrari perfetti
Una delle forme più semplici di cifratura per trasposizione
comporta Io scambio della prima e della seconda cifra
binaria, poi della terza e della quarta cifra binaria, e cosi
via.
Testo chiaro
1000001110001011010011100010110011101000001
Testo cifrato
0100001101000111100011010001110011010100010
Il messaggio crittato è una singola stringa di 42 cifre
binarie, che può essere trasmessa al destinatario.
Quest'ultimo può ripristinare il testo chiaro effettuando di
nuovo la trasposizione delle cifre binarie, dividendo la
stringa in elementi del codice ASCII da sette bit, e
trovando la lettera alfabetica corrispondente.
I cifrari perfetti
Supponiamo ora di voler crittare lo stesso
messaggio, CESENA, impiegando una semplice
versione computerizzata di una cifratura per
sostituzione.
Di nuovo, prima di crittare il messaggio dovremo
convertirlo in codice ASCII.
La sostituzione si avvale di una chiave concordata
dal mittente e dal destinatario.
Es: chiave: SERIEA. Tradotta in codice ASCII,
essa si potrà usare sommando ogni elemento
del testo chiaro al corrispondente elemento della
chiave.
I cifrari perfetti
• Messaggio CESENA
• Messaggio ASCII
100001110001011010011100010110011101000001
• Chiave SERIEA
• Chiave ASCII
111001111001011110010110100111001011100001
Testo cifrato
011000001000000100001010110001010110100000
II crittogramma così generato è una singola stringa di 42
cifre binarie, che può essere trasmessa al destinatario.
Quest'ultimo, usando la chiave per invertire la
sostituzione, può ricreare la stringa originaria, e da
questa, tramite il codice ASCII, risalire al testo chiaro.
I cifrari perfetti
Nei primi anni Settanta negli USA si mise a punto il sistema
Lucifer.
Lucifer critta i messaggi tramite le seguenti operazioni:
1. il testo è convertito in una lunga stringa di cifre binarie.
2. la stringa è divisa in blocchi di 64 bit, ciascuno dei quali
sarà crittato separatamente.
3. si modificano i 64 bit del blocco: nella divisione di
quest'ultimo in due mezzi blocchi da 32 bit, chiamati
Sinistra0 e Destra0.
4. I bit di Destra0 sono poi introdotti in una funzione
«deformante», che trasforma le cifre binarie tramite un
complesso procedimento di sostituzione.
I cifrari perfetti
Il mezzo blocco Destra0 deformato è sommato a Sinistra0
per produrre un nuovo mezzo blocco da 32 bit chiamato
Destra1, mentre l'originario Destra0 diventa Sinistra1.
Questa serie di operazioni è chiamata «giro».
La cifratura completa di un blocco da 64 bit prevede un
totale di sedici giri.
Il testo in cifra può quindi essere inviato al destinatario,che
lo volgerà in chiaro invertendo il processo.
I particolari della funzione deformante possono mutare a
ogni messaggio, in quanto dipendono dalla chiave
concordata dal mittente e dal destinatario.
I cifrari perfetti
In altre parole, Io stesso messaggio può essere cifrato in
un'infinità di modi a seconda della chiave scelta. Nella
crittografìa computerizzata le chiavi sono
essenzialmente numeri.
Nell'insieme, Lucifer era considerato uno dei migliori
programmi crittografici presenti sul mercato.
La versione a 56 bit della cifratura - numero di chiavi
intorno ai cento milioni di miliardi - Lucifer di Horst
Feistel fu ufficialmente adottata il 23 novembre 1976 col
nome di Data Encryption Standard (Standard di
codifica dei dati), o DES. Fino alla fine degli anni
novanta il DES è stato lo standard ufficiale americano
per la codifica delle informazioni.
I cifrari perfetti
Il sistema è sicuro.
Ma la gestione dei libri delle chiavi condivise, spesso
ingombranti, rappresentano punti critici che invitano a
cercare nuove modalità per la sicurezza dei sistemi.
I problemi precedenti vengono accresciuti di molto dagli usi
moderni.
Il problema di distribuire a ciascuno una chiave particolare
pone enormi problemi gestionali.
L’idea della chiave pubblica
L’idea è di mettere a disposizione di ogni utente una chiave
personale, segreta, che lo identifica e che, solo a lui,
permette di decifrare i messaggi a lui indirizzati.
Questa è l’idea della chiave pubblica,opposta all’idea della
chiave condivisa, segreta, da sempre utilizzata nei
cifrari.
La chiave pubblica sarà nota a tutti, perché è utile per
cifrare i messaggi… ma non per decifrarli.
Sarà a conoscenza anche del famigerato intercettatore.
Neppure il trasmettitore, che usa la funzione cifrante
sarebbe in grado di decifrare il messaggio che ha
mandato (ma peraltro non ne ha bisogno).
L’idea della chiave pubblica
La sicurezza di questi sistemi dipende dall’uso di funzioni
‘un po’ strane’, che sono funzioni invertibili – devono
servire sia per cifrare che per decifrare – facili da
calcolare in una direzione ma estremamente difficili da
calcolare in senso inverso...a meno che non sia nota
qualche informazione in più.
La cifratura del messaggio avviene con una di queste
funzioni, la decifratura con la funzione inversa (che è
nota solo a chi riceve il messaggio).
Si tratta di un canale asimmetrico – contrariamente alla
simmetria implicita fra trasmettitore e ricevitore che si ha
nel caso della chiave condivisa.
L’idea della chiave pubblica
Fra le funzioni che sono state escogitate, quella più nota –
e utilizzata nel sistema RSA – si basa sulla difficoltà
pratica nella scomposizione di un intero in fattori primi:
se il numero dato ha molte cifre decimali, anche le
tecniche più raffinate e i calcolatori più veloci risultano
inefficaci.
Una stima attendibile, che mette il tempo di fattorizzazione
in dipendenza dal numero di cifre, è la seguente
Alice, Bob … e Eva
Come funziona?
Il messaggio M viene ‘chiuso’ in un recipiente mediante
una chiave a e spedito al ricevitore R
durante il trasferimento è al sicuro, ma R non può entrarne
in possesso perché non conosce la chiave. Allora, a sua
volta, R applica una propria chiave b al recipiente
e lo rispedisce al trasmettitore T.
Alice, Bob … e Eva
A questo punto, neanche T è in grado di aprire il
contenitore (ma non gli interessa,conosce già il
contenuto).
Però può togliere la propria chiave, rispedirlo e, questa
volta, mettere in condizione R di aprire il contenitore:
Sono occorsi tre passaggi, però in ogni caso il messaggio è
transitato ogni volta al sicuro dalle intercettazioni.
Alice, Bob … e Eva
L'ordine è fondamentale perfino in una semplice sostituzione.
Se l'ordine è scorretto, iI risultato è senza senso.
Se Bob decifrasse prima di Alice, il risultato avrebbe coinciso
col messaggio iniziale
L’aritmetica dell’orologio
Il crittosistema RSA implementa le idee della chiave
pubblica mediante alcuni teoremi elementari di teoria dei
numeri.
Ecco gli elementi fondamentali, i quali costituiscono la base
della cosiddetta aritmetica modulare, la quale riguarda
essenzialmente le operazioni aritmetiche, rese modulari
rispetto ad un intero assoluto n.
Definizione. Due interi (relativi) a e b si dicono congruenti
modulo n (intero assoluto) se la loro differenza è un
multiplo intero di n.
Si scrive così:
L’aritmetica dell’orologio
Due interi sono congruenti modulo n esattamente quando
hanno lo stesso resto rispetto alla divisione per n.
Inoltre, la relazione di congruenza modulo n è una
relazione di equivalenza (vale a dire soddisfa le
proprietà: riflessiva, simmetrica e transitiva) dunque
permette di suddividere l’insieme Z degli interi relativi in
classi di equivalenza, rappresentate, ciascuna dal resto
rispetto alla divisione per n. Con Zn indichiamo l’insieme
delle classi di resti modulo n:
Zn = {0,1,2,…, n-1}
È chiaro che ogni intero relativo appartiene ad una ed una
sola classe di resti.
L’aritmetica dell’orologio
L’aritmetica modulare è l’aritmetica di Zn, un aritmetica fatta
più che con i numeri in sé, con i loro resti della divisione
per n; essa è possibile grazie al fatto che la relazione di
congruenza è stabile rispetto alle operazioni di somma e
prodotto:
Teorema.
In Zn l’equazione di primo grado ax = 1 ha un’unica
soluzione se e solo se MCD(a,n) = 1.
Così, per gli interi modulo n, ammettono inverso solo
quelli che sono primi con n .
L’aritmetica dell’orologio
Teorema (piccolo teorema di Fermat).
Se p è un numero primo che non divide a,
allora a p−1 ≡ 1 (mod p) .
In realtà, per implementare il metodo RSA, occorre una
generalizzazione del piccolo teorema di Fermat, ottenuta
un secolo dopo da Eulero e che utilizza una funzione
particolare: la Φ di Eulero:
Definizione. Φ (n) è il numero di interi minori di n e primi
con n.
I primi valori della Φ sono facili da calcolare:
Φ(1) = 1, Φ(2) = 1, Φ(3) = 2, Φ(4) = 2, Φ(5) = 4, Φ(6) = 2,
Φ(7) = 6, ……
L’aritmetica dell’orologio
ma in generale il calcolo di Φ(n) ha la stessa complessità di
calcolo della scomposizione di n in fattori primi.
Infatti, è immediato calcolare Φ(p) quando p è un numero
primo (Φ(p) = p-1) ed è facile il calcolo di Φ(n) quando si
conosce la scomposizione di n in fattori, questo risulta
dal teorema che afferma:
Se MCD(m, n) = 1, allora Φ(m·n) = Φ(m)·Φ(n).
Ecco ora la generalizzazione necessaria del piccolo
teorema di Fermat:
Teorema (di Eulero-Fermat).
Se MCD (a, Φ (n)) = 1 allora a Φ (n) ≡ 1 (mod n).
I passaggi matematici della RSA
(1) Alice sceglie due numeri primi molto grandi, p e q. Per
semplificare p = 17 e q =11. Questi numeri dovranno
essere tenuti segreti.
(2) Alice moltiplica p e q, e ottiene N.
In questo caso, N = 187. Poi, Alice deve scegliere un
altro numero, e; supponiamo che scelga e = 7
(3) A questo punto, Alice è libera di pubblicare e e N in un
elenco accessibile a tutti.
e e N sono le «chiavi pubbliche» dì Alice.
I passaggi matematici della RSA
(4) Bob vuole cifrare un messaggio per Alice, questo deve
innanzitutto essere trasformato in un numero, M. Per
esempio, una parola viene trasformata in cifre binarie
ASCII. M è quindi cifrato in modo da originare C, il
crittogramma, secondo la formula:
C=Me(modN)
(5) Supponiamo che Bob voglia mandare ad Alice una
semplice lettera X, in codice ASCII, 1011000, cioè 88 in
notazione decimale. Quindi, M = 88.
I passaggi matematici della RSA
(6) Per crittare il messaggio, Bob comincia col procurarsi la
chiave pubblica di Alice, e constata che N= 187 e e= 7.
Così egli può utilizzare la formula necessaria a crittare il
messaggio di Alice.
Per M = 88, la formula da:C=887(mod187)
887(mod 187) = 894.432 (mod 187)= 11 (mod 187)
Bob può quindi inviare ad Alice il testo cifrato, C = 11.
(7) Le funzioni esponenziali in aritmetica dei moduli sono
unidirezionali; è quindi molto difficile ritrovare M,
partendo da C = 11. Perciò, Eva non è in grado di
decifrare il messaggio.
I passaggi matematici della RSA
(8) Alice, al contrario, può decifrare il messaggio perché
conosce i valori di p e q. Alice calcola un numero
speciale, d, la sua personale chiave per la decifrazione,
nota anche come chiave privata.
ex=1mod Φ(n)  ex=1[mod (p - 1)(q-1)]
7x=1(mod 16x10) 7x=1 (mod 160)  d=23
1123=(887)23=887x23=88 k·Φ(n) + 1=(88 Φ(n) )k88=88(mod 187)
Essendo m Φ(n) ≡ 1 per il teorema di Eulero-Fermat si ha
che (m Φ(n) )k ≡ 1(mod n).
La sicurezza della RSA
Per violare il codice RSA è necessario ottenere d, la chiave
privata; è quindi necessario conoscere Φ (n).
Osserviamo che da Φ (n) e n si ricavano facilmente p e q:
Φ(n) = (p-1)(q-1) = n-(p+q)+1 =) quindi p e q sono le
soluzioni dell'equazione x2 -(p + q)x + pq = 0
Dal punto di vista della complessita computazionale trovare
Φ(n) senza la fattorizzazione n = pq è equivalente alla
fattorizzazione, ma la fattorizzazione è un problema difficile
per i numeri grandi e questa è la sicurezza di RSA.
La sicurezza della RSA
La RSA Security pubblica sfide per rompere il codice RSA.
RSA-129 -129 cifre decimali (prima sfida, 1977) fattorizzato
nel 1994 in 8 mesi con 600 computer in rete;
RSA-200 -200 cifre decimali: fattorizzato nel 2005 in 3 mesi
su un cluster di 80 CPU di 2.2 GHz, ecco i numeri
N=279978339112213278708294676387226016210704467869554285
375600099293261284001076093456710529553608560618223519
109513657886371059544820065767750985805576135790987349
50144178863178946295187237869221823983
p=3532461934402770121272604978198464368671197400197625023
649303468776121253679423200058547956528088349
q=792586995447833303334708584148005968773797585736421996
0734330341455767872818152135381409304740185467
La sicurezza della RSA
Il solo punto debole della crittografia RSA è che in
futuro potrebbe essere disponibile un algoritmo
più veloce per scomporre N in fattori primi.
Una scoperta simile renderebbe inutilizzabile la
RSA, tuttavia i matematici la cercano invano da
più di duemila anni. La maggior parte dei
matematici ritiene che ciò non sia casuale, ma
dipenda dalle proprietà dei numeri interi.
Comunque, vedremo … per il momento la cifratura
RSA resta affidabile.
Applicazioni della RSA
La crittografia RSA può essere utilizzata come firma
digitale.
Sia M il messaggio, il mittente firma M grazie alla sua
chiave privata
C=Md(modN)
Il destinatario decifra C grazie alla chiave pubblica
M=Ce(modN) del mittente M.
Tutti possono decifrare C ma vi è la garanzia che il mittente
è uno solo, infatti solo il mittente autentico possiede la
chiave privata d associata a quella pubblica e utilizzata
per decifrare.
Conclusioni
Ormai la crittografia non si occupa più soltanto di
spie e di generali, ma riguarda tutti noi, quando
compiamo operazioni a distanza che vogliamo
mantenere riservate, ad esempio transazioni on
line o altre comunicazioni.
Attualmente, la crittografia è un potente settore di
ricerca nel quale si intrecciano la teoria dei
numeri, statistica e probabilità e le tecniche più
raffinate dell’informatica moderna.
Conclusioni
La battaglia tra crittografi e crittoanalisti continua. Nella
storia le vittorie degli uni hanno stimolato la rivincita degli
altri. Quindi confidiamo nel RSA, nella crittografia
moderna, sicuramente più scienza che arte, ma con
prudenza.
Mi resta, infatti, la convinzione che, alla fine, il fattore
umano riuscirà a sorprendere, anche nelle future
evoluzioni.
In fondo, nel corso della seconda guerra mondiale, un
sistema crittografico particolare non è stato decrittato:
il linguaggio naturale della tribù navajo.
Bibliografia
•
•
•
•
•
Simon Singh Codici & segreti, BUR
PC Professionale 07/09 pp. 86 -97
R. Betti Codici segreti: l’antica arte della crittografia
diventa una scienza moderna
Ferragina, Luccio Crittografia. Principi, algoritmi,
applicazioni Bollati Boringhieri
M.du Sautoy L'Enigma dei numeri primi Rizzoli