Codici e segreti storie e matematica intorno alla crittografia 21 dicembre 2010 Prof. Fabio Bonoli.

Codici e segretistorie 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.


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


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.


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.


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.


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.


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.


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...


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.


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.


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 Beale71, 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 Beale115, 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.


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.


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.


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):

A B C D E F G H I L M N O P Q R S T U V Z

C D E F G H I L M N O P Q R S T U V Z A B

Metodi di questo genere sono noti come cifrari di Cesare.


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 .


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


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:

A B C D E F G H I L M N O P Q R S T U V Z

U V Z L I C E O R G H A B D F M N P Q S T

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 …


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 nascosteStudiando 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.


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).


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.


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.


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:


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:

N E L M E Z Z O D E L C A M M I N D I N O S T R A V I T AL I C E O R I G H I L I C E O R I G H I L I C E O R I G H

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!

Z O N Q S Q H U M O U…….


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).


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.


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.

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.



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ì:


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 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 .


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, ……


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.


(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.


(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 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 numeriN=27997833911221327870829467638722601621070446786955428537560

009929326128400107609345671052955360856061822351910951365788637105954482006576775098580557613579098734950144178863178946295187237869221823983

p=3532461934402770121272604978198464368671197400197625023649303468776121253679423200058547956528088349

q=7925869954478333033347085841480059687737975857364219960734330341455767872818152135381409304740185467


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.

ConclusioniLa 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

Codici e segreti storie e matematica intorno alla crittografia 21 dicembre 2010 Prof. Fabio Bonoli.

Documents

Transcript of Codici e segreti storie e matematica intorno alla crittografia 21 dicembre 2010 Prof. Fabio Bonoli.