Crittografia
1
Francesca Benanti
Dipartimento di Matematica ed Informatica Università degli Studi di Palermo, Via Archirafi 34, 90123 Palermo
Tel.: 091-23891105
E-mail: [email protected] http://math.unipa.it/~fbenanti/
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
mailto:[email protected]://math.unipa.it/~fbenanti/http://math.unipa.it/~fbenanti/
“Il desiderio di svelare segreti è profondamente radicato nella natura
umana; la promessa di partecipare a conoscenze negate ad altri eccita
anche la mente meno curiosa. Qualcuno ha la fortuna di trovare un
lavoro che consiste nella soluzione di misteri, ma la maggior parte di
noi è spinta a soddisfare questo desiderio risolvendo enigmi artificiali
ideati per il nostro divertimento. I romanzi polizieschi o i cruciverba
sono rivolti alla maggioranza; la soluzione di codici segreti può essere
l’occupazione di pochi.”
John Chadwick
The Decipherment of Linear B
2
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Simon Singh, CODICI E SEGRETI, BUR SAGGI, 2001
La crittografia è una forma di comunicazione in ambiente ostile
Ronald Rivest, (la “R” di RSA)
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO 3
Alice Bob
Canale di comunicazione Forma tipica del messaggio
Corriere privato, Servizio postale Documento scritto
Telegrafo Sequenza di impulsi elettrici
Telefono Messaggio vocale
Radio Emissione di Onde
elettromagnetiche
Internet (World Wide Web) File binario
Canale di comunicazione a distanza
Messaggio
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO 4
Alice Bob
Oscar
1. Ruolo passivo (solo ascolto)
2. Ruolo attivo (ascolto e trasmissione)
CRITTOGRAFIA (lo “scudo” di Alice e Bob)
CRITTOANALISI (la “spada” di Oscar)
Canale insicuro
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO 5
La Crittografia tratta delle "scritture nascoste", ovvero dei metodi per rendere un messaggio "offuscato" in modo da non essere comprensibile a persone non autorizzate a leggerlo. Un tale messaggio si chiama comunemente crittogramma.
Da Wikipedia, l'enciclopedia libera.
La crittografia si occupa dei metodi e delle tecniche per rendere
sicura la trasmissione di un messaggio fra due soggetti lungo un
canale di comunicazione potenzialmente non sicuro.
6
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Le origini
Per migliaia di anni re, regine e generali hanno avuto il bisogno di comunicazioni efficienti per governare i loro paesi e comandare i loro eserciti. Nel contempo, essi compresero quali conseguenze avrebbe avuto la caduta dei loro messaggi in mano ostili: informazioni preziose sarebbero state a disposizione delle nazioni rivali e degli eserciti nemici. Fu il pericolo dell'intercettazione da parte degli avversari a promuovere lo sviluppo di codici, tecniche di alterazione del messaggio destinate a renderlo comprensibile solo alle persone autorizzate.
Il bisogno di segretezza ha indotto le nazioni a creare segreterie alle cifre e dipartimenti di crittografia. E’ stato loro compito garantire la sicurezza delle comunicazioni, escogitando e impiegando i migliori sistemi di scrittura segreta. Nello stesso tempo, i decrittatori hanno tentato di far breccia in quei sistemi e carpire i dati che custodivano. Crittografi e decrittatori sono cercatori di significati, alchimisti votati alla trasmutazione di astruse serie di segni in parole dotate di senso.
7
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
La lunga battaglia tra inventori e solutori di codici ha prodotto importanti progressi scientifici. Gli inventori hanno creato codici sempre più resistenti mentre i solutori, per farvi breccia, hanno escogitato metodi sempre più sofisticati. Nello sforzo di tutelare e, rispettivamente, violare la segretezza, gli opposti schieramenti hanno attinto a un’ampia gamma di scienze e specializzazioni, dalla matematica alla linguistica, dalla teoria dell’informazione alla fisica quantistica. A loro volta, inventori e solutori di codici hanno arricchito queste discipline, e il loro lavoro ha accelerato il progresso tecnologico, come è dimostrato nel caso dei calcolatori.
La storia dei codici è la storia dell’antica secolare battaglia tra inventori e solutori di scritture segrete; una corsa agli armamenti intellettuale il cui impatto sulle vicende umane è stato profondo.
8
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Oggi
Questa disciplina, che fino a tempi relativamente recenti, riguardava principalmente l'ambiente militare e commerciale, con le nuove forme di comunicazione ha incominciato a interessarsi di situazioni in cui facilmente tutti noi ci troviamo coinvolti.
1. telefono cellulare: le comunicazioni viaggiano, almeno in parte, via satellite, e di conseguenza possono essere intercettate facilmente;
2. pay TV: il segnale televisivo viene cifrato, e solo chi ha pagato il canone ha la possibilità di decodificare il segnale;
3. internet: i dati immessi in rete vanno protetti (numero di carta di credito, numero di conti bancari, ecc.), firma digitale e dell’autenticazione dei documenti.
9
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Scritture Segrete
Lo scopo delle scritture segrete è di nascondere un messaggio; per
questo obbiettivo nella storia si sono succedute molte tecniche, che
ancora oggi continuano ad essere usate.
STEGANOGRAFIA
steganòV = coperto
Grafein = scrivere
coprire la scrittura
CRITTOGRAFIA
kriptòV = nascosto Grafein = scrivere
nascondere la scrittura
10
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Esempi di Steganografia
11
Erodoto narra (libro V delle Storie):
“Istieo voleva dare ad Aristagora l'ordine di ribellarsi,
non aveva alcun altro modo per annunziarglielo con
sicurezza, essendo le strade sorvegliate, fatta rasare la
testa al più fido degli schiavi, vi impresse dei segni, e
aspettò che ricrescessero i capelli. Non appena
ricrebbero, lo spedì a Mileto, non comandandogli
null'altro se non che, quando giungesse a Mileto,
dicesse ad Aristagora di fargli radere i capelli e di
guardare la sua testa: i segni impressi ordinavano,
come già prima ho detto, la rivolta.”
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
La scritta veniva applicata sul capo rasato di uno schiavo, quindi si attendeva che i capelli ricrescessero e si inviava il
messaggero. All’arrivo
presso il destinatario, questi rasava nuovamente lo schiavo e leggeva il messaggio.
12
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Esempi di Steganografia
CINA:
il messaggio era scritto
su striscioline finissime di
seta, che poi venivano
ricoperte di cera (strato
protettivo) e fatte
ingerire a uno schiavo.
Arrivato a destinazione, il
messaggio veniva
espulso dallo schiavo,
scrostato e finalmente …
letto.
13
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Esempi di Steganografia
INCHIOSTRI SIMPATICI:
da Plinio il Vecchio (I dC) a Umberto Eco (Il Nome della Rosa), si narra di una
metodologia di scrittura
a base di limone o latice
di titimabo; inchiostri simpatici che appaiono invisibili, ma ricompaiono una volta che il testo venga
esposto a una fonte di calore.
14 LABORATORIO DI CRITTOGRAFIA,
LICEO CLASSICO UMBERTO LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
Esempi di Steganografia
ITALIA:
nel XVI secolo un modo
interessante di recapitare
i messaggi era di scriverli
con aceto sul guscio di
un uovo sodo; il guscio,
poroso, permetteva
all’aceto di passare e,
una volta recapitato il
messaggio, era
sufficiente sgusciare
l’uovo per leggerlo!
15
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittografia
16
La longevità della steganografia dimostra che essa garantisce una certa sicurezza, ma il suo punto debole è evidente: se il latore del messaggio è attentamente perquisito, è probabile che il messaggio sia scoperto.
Perciò in parallelo con lo sviluppo della steganografia si assistè all'evoluzione della crittografia. La crittografia non mira a nascondere il messaggio in sè, ma il suo significato. Per rendere incomprensibile un testo, lo si altera per mezzo di un procedimento concordato a suo tempo dal mittente e dal destinatario. Il vantaggio della crittografia è che, anche se il nemico intercetta il messaggio, esso risulta incomprensibile e quindi inutilizzabile.
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittografia
Non tutte le società antiche svilupparono forme di crittografia. La Cina, per esempio, l'unica civiltà antica ad usare una scrittura ideografica, non ne ha mai viste. Le ragioni, a detta degli storici, sono legate alla natura prevalentemente orale delle comunicazioni.
17
In India, invece, forme di crittografia furono concretamente praticate. In diversi testi sacri sono presenti riferimenti a forme di scritture segrete. Nell'Artha-Sastra, un testo classico sugli affari di stato, si sottolinea l'importanza delle scritture segrete nei servizi di spionaggio. Esempi di scritture segrete sono presenti anche nel Latila-Vistara, un libro che esalta le virtù di Budda.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittografia
Nel Kama-Sutra, invece, tra le 64 arti (yogas) che la donna deve conoscere e praticare c'è l'arte della scrittura segreta. La 44-esima e, in particolare, la 45-esima arte (mlecchita-vikalpa) trattano di regole di trasformazione delle parole basate essenzialmente sulla sostituzione di caratteri del messaggio originale.
18
Kamasutra Mallanga Vatsyayana Kamasutra, cap. III Delle arti e scienze da coltivare Ecco le arti da studiare assieme col Kamasutra: • Il canto, l'uso di strumenti musicali [. . . ] • Conoscenza di miniere e cave [. . . ] • L'arte di interpretare scritture cifrate e di scrivere parole in modi particolari [. . . ] • Giochi matematici
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittografia
Anche nelle scritture cuneiforme sviluppate in Mesopotamia sono stati ritrovati esempi di crittografia. Sia presso gli Assiri che i Babilonesi, le due grosse civiltà sorte sulle sponde del Tigri, è stata rinvenuta l'usanza di sostituire le parti terminali delle parole con elementi corti e stereotipati detti colofoni. In Iraq, nel periodo finale delle scritture cuneiformi, è presente per la prima volta la sostituzione di nomi con numeri.
19
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Steganografia e Crittografia
Anche se la steganografia e la crittografia sono discipline indipendenti, possono essere impiegate per alterare e occultare il medesimo testo, garantendo un livello di sicurezza molto più alto. Per esempio, il « microdot », cioè la riduzione di uno scritto alle dimensioni di un punto, è una forma di steganografia che ebbe largo impiego durante la seconda guerra mondiale. Tramite un procedimento fotografico, gli agenti tedeschi in America latina trasformavano una pagina scritta, precedentemente crittografata, in una macchia con un diametro inferiore al millimetro, che poteva essere nascosta nel puntino di una « i » in una comunicazione banale. Il primo microdot fu scoperto dall' FBI nel 1941 grazie a una soffiata.
20 LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
Che cos’è la crittografia?
E’ la scienza che studia come rendere segreta e sicura la comunicazione tra due persone o entità nascondendo il significato del messaggio
21
Se Alice e Bob, vogliono scambiarsi un messaggio in maniera sicura, dovranno adottare un linguaggio o un codice noto soltanto a loro, in modo da renderlo incomprensibile ad Eva interessata a intercettare la loro comunicazione.
Bob Alice
Eva
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
PER TRASPOSIZIONE
anagramma
PER SOSTITUZIONE
algoritmo
Crittatura
22
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Esempi di Crittatura per Trasposizione
CRITTATURA A INFERRIATA: si sceglie un numero di righe e si scrive il messaggio alternando una lettera per ogni riga. Per decifrare la frase, il destinatario deve conoscere il numero di righe scelto.
S C R I V E R E I N C O D I C E
S R V R I C D C C I E E N O I E
S R V R I C D C
C I E E N O I E
23 LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
CRITTATURA PER SOSTITUZIONE
ALGORITMO
CIFRATURA CODICE Sostituzione a livello di lettere Sostituzione a livello di parole DECIFRARE DECODIFICARE
24
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Esempi di Codici
25
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
26
Algoritmo di crittazione:
sostituire ogni lettera con quella X posti avanti.
Chiave: X=13
Messaggio in chiaro:
VENDERE TUTTI I FONDI OBBLIGAZIONARI.
Messaggio crittato :
IRAQRER GHGGV V SBAQV BOOYVTNMVBANEV.
Esempi di Cifratura
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
27
RIASSUMENDO …
28
Il processo nel quale il messaggio originale detto M o testo in chiaro viene reso incomprensibile ad altri, va sotto il nome di
cifratura
Il processo inverso, che ritrasforma il messaggio C o testo cifrato è detto
decifratura
CRITTARE/DECRITTARE
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
CRITTARE/DECRITTARE
Per realizzare il processo di cifratura e/o decifratura si utilizza una funzione matematica, detta
algoritmo crittografico o cifrario.
29
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
CRITTARE/DECRITTARE
Gli algoritmi crittografici rappresentano soltanto le modalità “generiche” attraverso cui un messaggio M viene crittato in C.
La chiave è ciò che invece definisce le modalità “specifiche”. Mentre spesso l’algoritmo è pubblico (ovvero si conoscono le operazioni “generiche” che svolge per crittografare un’informazione) e analizzabile da tutti, la chiave è personale e deve rimanere segreta
30 LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
CRITTARE/DECRITTARE
ALGORITMI SIMMETRICI
Gli algoritmi che utilizzano la stessa chiave per cifrare e decifrare il messaggio sono detti algoritmi simmetrici
31
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
CRITTARE/DECRITTARE
ALGORITMI ASIMMETRICI
Algoritmi che utilizzano chiavi diverse per la cifratura e la decifratura sono detti algoritmi asimmetrici
32 LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
Legge di Kerckhoffs
La netta separazione concettuale di chiave e algoritmo è uno
dei saldi principi della crittografia, e fu formulata in modo
definitivo nel 1883 dal linguista olandese Auguste Kerckhoffs
von Nieuwenhof, nel trattato “La Cryptographie Militaire”:
.
33 LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
Sistemi Crittografici
Le più antiche notizie sicure sono probabilmente quelle sulla scitala lacedemonica , data da Plutarco come in uso dai tempi di Licurgo (IX sec a.C.) ma più sicuramente usata ai tempi di Lisandro (verso il 400 a.C.)
Consisteva in un bastone su cui si avvolgeva ad elica un nastro di cuoio; sul nastro si scriveva per colonne parallele all'asse del bastone, lettera per lettera, il testo segreto. Tolto il nastro dal bastone, il testo vi risultava trasposto in modo regolare ma sufficiente per evitare la comprensione senza un secondo bastone uguale al primo. Esempio di crittografia per trasposizione
34 LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
35
Tra il 390 e il 360 a.C. venne compilato da Enea il tattico, generale della lega arcadica, il primo trattato di cifrari il cui XXI capitolo tratta appunto di messaggi segreti. In questo viene descritto un disco sulla zona esterna del quale erano contenuti 24 fori, ciascuno dei quali era contrassegnato da una lettera disposte in ordine alfabetico. Un filo, partendo da un foro centrale, si avvolgeva passando per i fori delle successive lettere del testo. Il destinatario del messaggio svolgeva il filo dal disco segnando le lettere da esso indicate. Il testo si doveva poi leggere a rovescio.
Disco di Enea il tattico
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
36
Fonti preziose di scritture segrete sono i testi sacri. Nel Vecchio Testamento gli storici hanno evidenziato tre tipi di trasformazione: l'Atbash, l'Albam e l'Atbah.
L'Atbash ebraico è una tecnica di trasformazione ad alfabeto capovolto: il primo carattere dell'alfabeto viene sostituito con l'ultimo, il secondo con il penultimo e così via. Infatti la prima lettera dell'alfabeto ebraico (Aleph) viene cifrata con l'ultima (Taw), la seconda (Beth) viene cifrata con la penultima (Shin); da queste quattro lettere è derivato il nome di Atbash (A con T, B con SH) per questo codice. L'Atbash viene utilizzato nel libro del profeta Geremia per cifrare il nome della città di Babilonia.
Il metodo ATBASH
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
Usando l'attuale alfabeto ordinario, l'Atbash può essere riassunto con la seguente tabella di cifratura:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Z Y X W V U T S R Q P O N M L K J I H G F E D C B A
Messaggio in chiaro: IL LIBRO DI GEREMIA. Messaggio crittato : ROORYILWRTVIVNRZ
37
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
L'Albam richiede che l'alfabeto venga diviso in due parti e che ogni lettera venga sostituita con la corrispondente dell'altra metà. Infine, l'Atbah richiede che la sostituzione soddisfi una relazione di tipo numerico. Le prime nove lettere dell'alfabeto vengono sostituite in modo tale che la somma della lettera da sostituire e della lettera sostituente risulti uguale a dieci. Quindi, per esempio, Aleph (prima lettera dell'alfabeto) viene sostituita con Teth (nona lettera dell'alfabeto). Per le restanti lettere dell'alfabeto deve valere una regola simile con somma pari a 28 in decimale (per esempio, la 13-esima lettera viene sostituita con la 15-esima, etc.).
38
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Il cifrario di Cesare
Svetonio nella Vita dei dodici Cesari racconta che Giulio Cesare usava per le sue corrispondenze riservate un codice di sostituzione molto semplice, nel quale la lettera chiara veniva sostituita dalla lettera che la segue di tre posti nell'alfabeto.
39 LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
Il cifrario di Cesare
Esempio: Messaggio in chiaro:
Auguri di buon compleanno
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
Messaggio crittato : DXJXULGLEXRQFRPSOHDQQR
40
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
E’ possibile generalizzare il sistema di Cesare usando uno spostamento di k posti, anzichè di 3. Ad esempio con k=7
Generalizzazione del cifrario di Cesare
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
Messaggio in chiaro:
Auguri di buon compleanno
Messaggio crittato : HBNBYPKPIBVUJVTWSLHUUV
41
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Sistemi Crittografici
42
ESERCIZI: Esercizio 1 Esercizio 2 Esercizio 3 Soluzioni: Esercizio1, Esercizio2, Esercizio3
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
cesare1.doccesare2.doccesare3.docSol.cesare1.docSol.cesare2.docSol.cesare3.doc
43
Limiti del cifrario di Cesare:
Numero delle chiavi: 26
Se il messaggio è intercettato e si sospetta che l’algoritmo sia la cifratura di Cesare, la decrittazione può essere effettata controllando le possibili chiavi
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
Il crittosistema di Cesare o la sua generalizzazione è un cifrario in cui la stessa lettera è codificata sempre con la stessa lettera slittata di un certo posto.
Ad esempio la lettera ‘a’ è sempre codificata con la lettera ‘D’, la ‘b’ è codificata con ‘E’, ...
44
Caso Generale
Il caso più generale è quello in cui l’alfabeto cifrato è una permutazione
di quello in chiaro. L'alfabeto cifrante viene ottenuto scegliendo, meglio
se a caso, una fra le tante permutazioni dell'alfabeto chiaro:
si può ad esempio scegliere che alla 'A' del chiaro corrisponda la 'F' nel
cifrato, alla 'B' la 'Z', alla 'C' la 'K' e così via senza un ordine regolare.
In questo caso la chiave è l’alfabeto cifrato.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Esempio:
45
a b c d e f g h i j k l m n o p q r s t u v w x y z
L P A I Q B C T R J X Z D S E G F H U O N V Y W K M
Testo Chiaro: Et tu brute?
Testo Cifrato: QO ON PHNOQ?
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
Esistono 26!=51090942171709440000 permutazioni possibili,
cioè circa 51 · 1018, ossia più di cinquanta miliardi di miliardi.
Una ricerca esaustiva per trovare la permutazione giusta è
praticamente impossibile
46
Vantaggi:
Svantaggi:
La memorizzazione dell’alfabeto cifrante può indurre il mittente
o il destinatario a conservare l’alfabeto cifrante in forma scritta
con il rischio che cada in mani ostili e ogni segretezza sia perduta
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
Supponiamo, per esempio, di voler impiegare il nome JULIUS CAESAR come frase
chiave. In primo luogo, si dovranno eliminare sia gli spazi sia le lettere ripetute; la
sequenza così ottenuta, JULISCAER, sarà l’inizio dell’alfabeto cifrante , mentre le
lettere che non fanno parte della sequenza verranno aggiunte in ordine alfabetico
partendo dall’ultima lettera della parola chiave.
47
Parola chiave
a b c d e f g h i j k l m n o p q r s t u v w x y z
J U L I S C A E R T V W X Y Z B D F G H M N O P Q T
Testo Chiaro:
Testo Cifrato:
Domani attaccheremo
IZXJYR JHHJLLESFSXZ
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Memorizzare una parola chiave è molto più facile che memorizzare una sequenza priva di senso;
Esempio: scegliere come chiave «Cifra Gennaio», cambiare ogni mese la chiave – da «Cifra Gennaio» a «Cifra Febbraio» e da questa a «Cifra Marzo», ecc.,- . Questo sistema di generazione di chiavi può essere organizzato in modo che l’errore dell’emittente e del ricevente sia improbabile ed il suo aggiornamento molto semplice.
Il numero di alfabeti cifranti generati da una parola o frase chiave è inferiore al numero di alfabeti cifranti generati per riorganizzazione generale, ma è pur sempre immenso.
48
Vantaggi:
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
Il cifrario di Polibio
Lo storico greco Polibio (~200-118 a.C.), nelle
sue Storie (Libro X) attribuisce ai suoi
contemporanei Cleoxeno e Democleito
l’introduzione di un sistema di
telecomunicazione basato su un interessante
metodo di cifratura.
L'idea è quella di cifrare una lettera con una
coppia di numeri compresi tra 1 e 5, in base
ad una scacchiera 5x5.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
La traduzione nell’attuale alfabeto si
ottiene "fondendo" k e q, due lettere
rare ma non foneticamente differenti
(nella lingua inglese), nella stessa
casella.
@ 1 2 3 4 5
1 A B C D E
2 F G H I J
3 KQ L M N O
4 P R S T U
5 V W X Y Z
Il cifrario di Polibio (Uno dei primi algoritmi di sostituzione chiamato così in onore dello storico greco Polibio (203-120 a.c.), che ci lasciò in eredità la documentazione relativa allo stesso)
Ogni lettera viene rappresentata dai due
numeri che corrispondono alla riga e alla
colonna in cui la lettera si trova.
Per esempio, a=11 e r=42.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
https://it.wikipedia.org/wiki/Polibio
Quindi la frase:
“ Attenzione agli scogli “
dopo la cifratura risulterà:
1144441534552435341511223224431335223224
| | | | | | | | | |
A t t e n z i o n e …………………………………
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Il cifrario di Polibio
1 2 3 4 5
1 A B Γ Δ Ε
2 Z H Θ I K
3 Λ M N Ξ O
4 Π Ρ Σ T Υ
5 Φ Χ Ψ Ω
La scacchiera di Polibio non nacque come sistema crittografico bensì come sistema per comunicare a distanza: era in pratica una sorta di antico telegrafo. Polibio descrive infatti nelle Storie il suo come un metodo per inviare messaggi mediante l'uso di torce. Un uomo si poneva dietro ad un riparo con 5 torce alla sua destra e 5 torce alla sua sinistra: la comunicazione avveniva mediante il sollevamento di un determinato numero di torce per lato. Il numero era dato proprio dalle coordinate (il numero di riga e quello di colonna) delle lettere del messaggio all'interno della seguente scacchiera (basata sull‘ alfabeto greco):
Per inviare ad esempio la parola CRETESI, che in greco è KΡHTEΣ (cretès), si formeranno le lettere in questo modo: K: 2 torce a sinistra, 5 torce a destra Ρ: 4 torce a sinistra, 2 torce a destra H: 2 torce a sinistra, 2 torce a destra T: 4 torce a sinistra, 4 torce a destra E: 1 torcia a sinistra, 5 torce a destra Σ: 4 torce a sinistra, 3 torce a destra
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Il cifrario di Polibio
https://it.wikipedia.org/wiki/Scacchiera_di_Polibiohttps://it.wikipedia.org/wiki/Scacchiera_di_Polibiohttps://it.wikipedia.org/wiki/Scacchiera_di_Polibiohttps://it.wikipedia.org/wiki/Scacchiera_di_Polibiohttps://it.wikipedia.org/wiki/Scacchiera_di_Polibiohttps://it.wikipedia.org/wiki/Telegrafohttps://it.wikipedia.org/wiki/Lingua_greca_antica
La scacchiera di Polibio ha alcune importanti caratteristiche:
riduzione nel numero di caratteri utilizzati
conversione in numeri
riduzione di un simbolo in due parti che sono utilizzabili separatamente
La sua importanza nella storia della crittografia sta nell'essere alla base di altri
codici di cifratura come il Playfair Cipher o il cifrario campale germanico, usato
nella prima guerra mondiale, o la cifratura ADFGVX
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
http://www.crittologia.eu/critto/playfair.phtmlhttp://www.crittologia.eu/critto/playfair.phtmlhttp://www.crittologia.eu/critto/playfair.phtmlhttp://www.crittologia.eu/critto/playfair.phtmlhttp://www.crittologia.eu/critto/campale.htmhttp://www.crittologia.eu/critto/campale.htmhttp://www.crittologia.eu/critto/campale.htmhttp://www.crittologia.eu/critto/campale.htmhttp://www.crittologia.eu/critto/campale.htmhttp://www.crittologia.eu/critto/campale.htmhttp://www.crittologia.eu/critto/adfgvx.htmlhttp://www.crittologia.eu/critto/adfgvx.htmlhttp://www.crittologia.eu/critto/adfgvx.htmlhttp://www.crittologia.eu/critto/adfgvx.html
La cifratura pigpen (recinto per maiali) era usata dai massoni del Settecento per
proteggere i loro archivi.
La cifratura pigpen
Per crittare una lettera,
si trova la sua
posizione in una delle
quattro grate, poi si fa
lo schizzo della
porzione di grata
necessaria a
rappresentare la
lettera.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
ciao diventa
Sistemi Crittografici
ESERCIZI: Esercizio 1 Esercizio 2 Esercizio 3 Soluzioni: Esercizio1, Esercizio2, Esercizio3
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Polibio1mio.docpolibio2.docparolachiave.docsol_polibio1mio.docSol_Polibio 2.docSol.parolachiave.doc
Cifrari monoalfabetici
I cifrari monoalfabetici sono cifrari di sostituzione: del testo chiaro si sostituisce ogni carattere con un altro carattere (o
numero o simbolo) secondo una tabella prestabilita, ottenendo
il testo cifrato.
Tutti i cifrari a sostituzione considerati fino ad ora (Cesare,
Polibio, Pigpen, ecc…) sono di tipo monoalfabetico.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
Semplicità ed affidabilità sono i pregi grazie ai quali la cifratura per sostituzione
dominò la crittografia per tutto il primo millennio della nostra era.
Agli arabi va attribuita l’invenzione della crittoanalisi, la scienza
dell’interpretazione di un messaggio di cui si ignora la chiave. Furono i
crittoanalisti arabi a trovare il punto debole della sostituzione monoalfabetica,
un sistema che da secoli resisteva ad ogni assalto.
Il cifrario di Cesare, come la maggior parte dei cifrari monoalfabetici, può essere facilmente violato utilizzando tecniche statistiche
(crittoanalisi statistica).
Si analizzano le frequenze relative dei caratteri nel testo cifrato e le si
confrontano con quelle di una lingua conosciuta, ad esempio l'italiano.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
Non si sa chi per primo abbia capito che la diversa
frequenza delle lettere permetteva di decifrare un
crittogramma; di certo, la più antica descrizione
del procedimento si deve allo studioso arabo del
IX secolo Abu Yusuf ibn Ishaq al-Kindi. La sua
più lunga monografia, ritrovata solo nel 1987, si
intitola Sulla decifrazione dei messaggi crittati.
Giovanni Soro (Venezia, ... – 1544) è stato
indicato come il primo crittanalista di rilievo in
Europa. Il suo lavoro è tra i più antichi nella
crittoanalisi che siano stati conservati. A partire
dal 1506 ricoprì, per primo, la carica
di Segretario alle Cifre a Venezia
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
a b c d e f g h i j k l m n o p q r s t u v w x y z
Carattere alfabetico
Fre
qu
enza
(%
)
Ita
Eng
Analisi delle Frequenze: Italiano e Inglese a confronto
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
GND ASBLLNIOE PCBCSBVBU BTNTB OBSLESZLE LSN AZMDZ B SN PCBCSZBS. DB IZDDNQGNPZIB GELLN, AZGZLE ZD SBHHEGLE UZ IB’BSQA, PZ BDVE, FBHZE ZD PQEDE UBTBGLZ B DQZ N UZPPN: “MSBG SN, ONS IZDDN N QGB GELLN TZ CE GBSSBLE DN ABTEDN UNZ LNIOZ OBPPBLZ N DN DNMMNGUN UNMDZ BGLZHCZ SN. OEPPE NPPNSN HEPZ BSUZLB UB HCZNUNSN QGABTESN B TEPLSB IBNPLB?”
Z SBHHEGLZ UNDDN IZDDN N QGB GELLN, NOZDEME
Crittoanalisi di un testo cifrato
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Lett. Occ. %
A 6 2
B 38 12,6
C 7 2,3
D 22 7,3
E 24 8
F 1 0,3
G 16 5,3
H 8 2,6
I 8 2,6
L 22 7,3
Crittoanalisi
Frequenze Lett. Occ. % M 6 2
N 40 13,3
O 7 2,3
P 16 5,3
Q 7 2,3
R 0 0
S 22 7,3
T 7 2,3
U 11 3,6
V 2 0,6
Z 31 10,6
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
1° IPOTESI cerchiamo le lettere con la frequenza maggiore e sostituiamole:
N = e, B = a, Z = i, E = o
_________________________________________
GeD ASaLLeIOo PCaCSaVaU aTeTa OaSLoSiLo LSe AiMDi a Se PCaCSiaS. Da IiDDeQGePiIa GoLLe, AiGiLo iD SaHHoGLo Ui Ia’aSQA, Pi aDVo, FaHio iD PQoDo UaTaGLi a DQi e UiPPe: “MSaG Se, OeS IiDDe e QGa GoLLe Ti Co GaSSaLo De AaToDe Uei LeIOi OaPPaLi e De DeMMeGUe UeMDi aGLiHCi Se. OoPPo ePPeSe HoPi aSUiLa Ua HCieUeSe QGAaToSe a ToPLSa IaePLa?”
i SaHHoGLi UeDDe IiDDe e QGa GoLLe, eOiDoMo
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
2° IPOTESI cerchiamo le lettere con la frequenza minore:
La V è la più rara (ci sarebbe la F ma è solo una).
Può essere o uguale a Q o a Z.
Se fosse V = q, sappiamo che la q è sempre seguita dalla u, scegliamo una stringa: BDVE, la u ha frequenza del 3%, mentre la E dell’8 %, quindi sarà
V = Z.
Si ottiene
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
GeD ASaLLeIOo PCaCSazaU aTeTa OaSLoSiLo LSe AiMDi a Se PCaCSiaS. Da IiDDeQGePiIa GoLLe, AiGiLo iD SaHHoGLo Ui Ia’aSQA, Pi aDzo, FaHio iD PQoDo UaTaGLi a DQi e UiPPe: “MSaG Se, OeS IiDDe e QGa GoLLe Ti Co GaSSaLo De AaToDe Uei LeIOi OaPPaLi e De DeMMeGUe UeMDi aGLiHCi Se. OoPPo ePPeSe HoPi aSUiLa Ua HCieUeSe QGAaToSe a ToPLSa IaePLa?”
i SaHHoGLi UeDDe IiDDe e QGa GoLLe, eOiDoMo
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
3° Ipotesi concentriamoci su aDzo:
potrebbe essere alzo, quindi ipotizziamo D = l.
Ora guardiamo le stringhe di due e di tre lettere:
Se, Da, iD, Pi, De, GeD, LSe, QGa, Uei.
Da GeD e QGa si può ipotizzare: G = n e Q = u,
ipotesi anche compatibile con le frequenze.
Si ottiene
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
nel ASaLLeIOo PCaCSazaU aTeTa OaSLoSiLo LSe AiMli a
Se PCaCSiaS. la IilleunePiIa noLLe, AiniLo il SaHHonLo Ui
Ia’aSuA, Pi alzo, FaHio il Puolo UaTanLi a lui e UiPPe: “MSan
Se, OeS Iille e una noLLe Ti Co naSSaLo le AaTole Uei LeIOi
OaPPaLi e le leMMenUe UeMli anLiHCi Se. OoPPo ePPeSe
HoPi aSUiLa Ua HCieUeSe unAaToSe a ToPLSa IaePLa?”
i SaHHonLi Uelle Iille e una noLLe, eOiloMo
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
4° ipotesi
“noLLe” potrebbe essere “notte”, ipotizziamo
L = t,
“Puolo” potrebbe essere “suolo”, ipotizziamo
P = s.
le frequenze sono compatibili e ci sono doppie. Si ottiene
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
nel ASatteIOo sCaCSazaU aTeTa OaStoSito tSe AiMli a Se
sCaCSiaS. la IilleunesiIa notte, Ainito il SaHHonto Ui
Ia’aSuA, si alzo, FaHio il suolo UaTanti a lui e Uisse:
“MSan Se, OeS Iille e una notte Ti Co naSSato le AaTole
Uei teIOi Oassati e le leMMenUe UeMli antiHCi Se. Oosso
esseSe Hosi aSUita Ua HCieUeSe unAaToSe a TostSa
Iaesta?”
i SaHHonti Uelle Iille e una notte, eOiloMo
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
5° ipotesi “Ille”, potrebbe essere “mille”, e quindi I = m.
“SaHHonto” potrebbe essere “racconto”, cioè S = r e H = c.
___________________________________________
nel ArattemOo sCaCrazaU aTeTa Oartorito tre AiMli a re sCaCriar. la milleunesima notte, Ainito il racconto Ui ma’aruA, si alzo, Facio il suolo UaTanti a lui e Uisse: “Mran re, Oer mille e una notte Ti Co narrato le AaTole Uei temOi Oassati e le leMMenUe UeMli anticCi re. Oosso essere cosi arUita Ua cCieUere unAaTore a Tostra maesta?”
i racconti Uelle mille e una notte, eOiloMo
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
6° ipotesi “ArattemOo” potrebbe essere “frattempo”, e A = f, O = p.
“Ui”, “Uei”, suggeriscono U = d
___________________________________________
nel frattempo sCaCrazad aTeTa partorito tre fiMli a re sCaCriar. la milleunesima notte, finito il racconto di ma’aruf, si alzo, Facio il suolo daTanti a lui e disse: “Mran re, per mille e una notte Ti Co narrato le faTole dei tempi passati e le leMMende deMli anticCi re. posso essere cosi ardita da cCiedere unfaTore a Tostra maesta?”
i racconti delle mille e una notte, epiloMo
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
7° ipotesi
“anticCi” e “cCiedere” suggeriscono C = h. “aTeTa” e “daTanti” suggeriscono T = v
__________________________________________
nel frattempo shahrazad aveva partorito tre fiMli a re shahriar. la milleunesima notte, finito il racconto di ma’aruf, si alzo, Facio il suolo davanti a lui e disse: “Mran re, per mille e una notte vi ho narrato le favole dei tempi passati e le leMMende deMli antichi re. posso essere cosi ardita da chiedere unfavore a vostra maesta?”
i racconti delle mille e una notte, epiloMo
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
8° ipotesi “fiMli” sarà “figli” e “Mran” sarà “Gran” e quindi M = g.
“Facio” sarà “Baciò”, e quindi F = B
nel frattempo shahrazad aveva partorito tre figli a re shahriar. la milleunesima notte, finito il racconto di ma’aruf, si alzo, bacio il suolo davanti a lui e disse: “gran re, per mille e una notte vi ho narrato le favole dei tempi passati e le leggende degli antichi re. posso essere cosi ardita da chiedere un favore a vostra maesta?”
i racconti delle mille e una notte, epilogo
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
Alfabeto
Chiaro a b c d e f g h i l m n o p q r s t u v z
cifrato B ? ? U N A M C Z D I G E O ? S P L ? T V
L’alfabeto cifrante deriva dalla frase chiave: UNAMCZDIGEORSP ottenuta
eliminando spazi e ripetizioni da UNA MANCANZA DI GEORGES PEREC; la
frase è stata inserita in corrispondenza della quarta lettera dell’alfabeto chiaro, e le
lettere non comprese in essa sono state aggiunte da sinistra a destra in ordine
alfabetico, saltando la parte occupata dalla frase chiave.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
ESERCIZI:
Esercizio 1
Esercizio 2
Soluzione: Esercizio1
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
testo_a.doctesto_a.docCryptoDelph.pdfSol_testoa.doc
Crittoanalisi
Edgar Allan Poe, “Lo scarabeo d'oro” (1843)
Il racconto “Lo scarabeo d’oro” narra l’immaginaria avventura di William Legrande che s’imbatte in uno strano coleottero, uno scarabeo d’orato, e lo raccoglie con un foglio di carta trovato nei pressi. La sera usa il foglio per tracciare uno schizzo dell’insetto. Quando lo avvicina al focolare , il calore fa comparire il disegno di un capretto e una serie di segni tracciati con l’inchiostro simpatico. Legrande si trova di fronte a un crittogramma che custodisce l’ubicazione del tesoro del capitano Kidd.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO REGINA MARGHERITA, a.a. 2017-2018
Nel 1843 Poe scrisse un racconto sui codici segreti che è la miglior opera letteraria sull’argomento.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
53++!305))6*;4826)4+.)4+);806*;48!8`60))85;]8*:+*8!83(88)5*!;46(;88*96*?;8)*+(;485);5*!2:*+(;4956*2(5*4)8`8*;4069285);)6!8)4++;1(+9;48081;8:8+1;48!85;4)485!528806*81(+9;48;88;4(+?34;48)4+;161;:188;+?;
Edgar Allan Poe, “Lo scarabeo d'oro” (1843)
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO REGINA MARGHERITA, a.a. 2017-2018
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
53++!305))6*;4826)4+.)4+);806*;48!8`60))85;]8*:+*8!83(88)5*!;46(;88*96*?;8)*+(;485);5*!2:*+(;4956*2(5*4)8`8*;4069285);)6!8)4++;1(+9;48081;8:8+1;48!85;4)485!528806*81(+9;48;88;4(+?34;48)4+;161;:188;+?;
Edgar Allan Poe, “Lo scarabeo d'oro” (1843)
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO REGINA MARGHERITA, a.a. 2017-2018
La prima cosa da fare e’ un’ipotesi sulla lingua del testo del crittogramma. L’Autore spiega che il manoscritto e’ stato rinvenuto in una zona un tempo infestata da pirati, e che uno dei piu’ famosi pirata si chiamava Kidd: poiche’ in inglese “kid” vuol dire capretto, in mancanza di altre informazioni la prima ipotesi sulla lingua del crittogramma e’ che questa sia l’inglese.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
53‡!305))6*;4826)4+.)4+);806*;48!8`60))85;]8*:+*8!83(88)5*!;46(;88*96*?;8)*+(;485);5*!2:*+(;4956*2(5*4)8`8*;4069285);)6!8)4‡;1(+9;48081;8:8+1;48!85;4)485!528806*81(+9;48;88;4(+?34;48)4+;161;:188;+?;
Edgar Allan Poe, “Lo scarabeo d'oro” (1843)
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO REGINA MARGHERITA, a.a. 2017-2018
Il secondo passo da fare è l’analisi di frequenza:
Simboli Occorrenze 8 33 ; 26 4 19 ‡ 16 ) 16 * 13 5 12 6 11 ( 10 ! 8 1 8 0 6 2 5 9 5 : 4 3 4 ? 3 . 1 – 1
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittoanalisi
(Vedi per dettaglio crittoanalisi CryptoDelph.pdf)
Edgar Allan Poe, “Lo scarabeo d'oro” (1843)
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO REGINA MARGHERITA, a.a. 2017-2018
Alla fine….
A good glass in the bishop’s hostel in the devil’s seat—forty-one degrees and thirteen minutes — northeast and by north — main branch seventh limb east side — shoot from the left eye of the death’s-head— a bee-line from the tree through the shot fifty feet out.
La sua traduzione in italiano è la seguente:
Un buon vetro nell’ostello del vescovo sulla sedia del diavolo—quarantun gradi e tredici minuti—nord-nordest—tronco principale settimo ramo lato est — cala dall’occhio sinistro del teschio — una linea retta dall’albero passando per il punto toccato lontano cinquanta piedi.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
CryptoDelph.pdfCryptoDelph.pdfCryptoDelph.pdfCryptoDelph.pdf
Sistemi Crittografici
Alla fine di questo esempio di crittoanalisi, il concetto da sottolineare è che:
Ogni lettera ha una sua identità, che consiste sia nella frequenza media, sia nella tendenza a evitare o prediligere la vicinanza di altre lettere.
La debolezza della sostituzione monoalfabetica è che cambia l’abito della lettera ma non la sua identità, un po’ come un uomo che adottasse un travestimento continuando a fare la stessa vita e a frequentare le stesse persone.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Il cifrario di L.B. Alberti
Leon Battista Alberti (Genova, 18 febbraio 1404 – Roma, 20 aprile 1472) è stato un architetto,
scrittore, matematico e umanista italiano; fu inoltre crittografo, linguista, filosofo, musicista e
archeologo: una delle figure artistiche più poliedriche del Rinascimento.
Per secoli, la semplice cifratura per sostituzione
monoalfabetica aveva garantito la segretezza; ma lo sviluppo
dell’analisi delle frequenze, prima in Arabia poi in Europa
con il rinascimento, cancellò quella garanzia.
L’onere di escogitare una cifratura nuova e più resistente
cadde sui crittografi. Anche se essa non prese forma prima
della fine del XVI secolo, le sue origini si possono far
risalire all’ingegno multiforme di Leon Battista Alberti
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
https://it.wikipedia.org/wiki/Leon_Battista_Albertihttps://it.wikipedia.org/wiki/Leon_Battista_Albertihttps://it.wikipedia.org/wiki/Leon_Battista_Albertihttps://it.wikipedia.org/wiki/Leon_Battista_Albertihttps://it.wikipedia.org/wiki/Leon_Battista_Albertihttps://it.wikipedia.org/wiki/Leon_Battista_Alberti
Alberti propose di usare due o più alfabeti cifranti e di sostituirli durante la cifratura
Il cifrario di L.B. Alberti
Esempio
a b c d e f g h i j k l m n o p q r s t u v w x y z
E U F A V 0 D N P J K H S G T M I L B R Z C X W Y Q
C M U N B I P L O K J V A T G S D R H Q F Z W Y X E
Testo Chiaro:
Testo Cifrato:
Leone
HBTTV
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Alberti creò una «macchina cifrante» composta da due ruote concentriche: Due dischi di rame di differenti diametri in modo che uno possa circondare l’altro; ambedue sono infilati in un perno in modo che siano liberi di ruotare indipendentemente. Sulla circonferenza dei dischi sono tracciati gli alfabeti così che ruotando un disco rispetto ad un altro si possono far corrispondere lettere diverse.
Il disco esterno rappresenta le lettere in chiaro; quello interno la lettera in cifra. Si deve semplicemente definire la posizione iniziale o chiave da modificare durante la cifratura.
Disco Cifrante di L.B.Alberti
Links: https://it.wikipedia.org/wiki/Disco_cifrante http://www.crittologia.eu/critto/alberti.phtml https://archeocomputing.wordpress.com/2014/01/31/il-disco-di-leon-battista-alberti/
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
discocifrante.pdfdiscocifrante.pdfdiscocifrante.pdfhttps://it.wikipedia.org/wiki/Disco_cifrantehttp://www.crittologia.eu/critto/alberti.phtmlhttp://www.crittologia.eu/critto/alberti.phtmlhttps://archeocomputing.wordpress.com/2014/01/31/il-disco-di-leon-battista-alberti/https://archeocomputing.wordpress.com/2014/01/31/il-disco-di-leon-battista-alberti/https://archeocomputing.wordpress.com/2014/01/31/il-disco-di-leon-battista-alberti/https://archeocomputing.wordpress.com/2014/01/31/il-disco-di-leon-battista-alberti/https://archeocomputing.wordpress.com/2014/01/31/il-disco-di-leon-battista-alberti/https://archeocomputing.wordpress.com/2014/01/31/il-disco-di-leon-battista-alberti/https://archeocomputing.wordpress.com/2014/01/31/il-disco-di-leon-battista-alberti/https://archeocomputing.wordpress.com/2014/01/31/il-disco-di-leon-battista-alberti/https://archeocomputing.wordpress.com/2014/01/31/il-disco-di-leon-battista-alberti/https://archeocomputing.wordpress.com/2014/01/31/il-disco-di-leon-battista-alberti/https://archeocomputing.wordpress.com/2014/01/31/il-disco-di-leon-battista-alberti/
Alberti non riuscì a trasformare la sua idea appena abbozzata in una tecnica
ben definita. Dopo Alberti molti furono i letterati che cercarono di
continuare la sua opera, dall’abate tedesco Johannes Trithemius allo
scienziato italiano Giambattista Della Porta, ma si arrivò ad una
conclusione definitiva solo con il diplomatico francese Blaise de Vigenère.
Il cifrario di Vigenère
Vigenère (1523-1596) prese confidenza con gli scritti di Alberti,
Trithemius, e Della Porta a 26 anni quando fu inviato a Roma per
due anni in missione diplomatica. All’inizio il suo interesse per la
crittografia fu esclusivamente pratico e legato alla attività
diplomatica.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
https://it.wikipedia.org/wiki/Blaise_de_Vigen%C3%A8rehttps://it.wikipedia.org/wiki/Blaise_de_Vigen%C3%A8rehttps://it.wikipedia.org/wiki/Blaise_de_Vigen%C3%A8rehttps://it.wikipedia.org/wiki/Blaise_de_Vigen%C3%A8rehttps://it.wikipedia.org/wiki/Blaise_de_Vigen%C3%A8re
Il cifrario di Vigenère
Ma a 39 anni egli giudicò di aver messo da parte
abbastanza denaro per abbandonare l’attività
diplomatica e dedicarsi esclusivamente agli studi.
Così riuscì ad ottenere una tecnica crittografica
nuova, coerente e di grande efficacia. Il suo sistema
inventato nel 1562, si meritò l’appellativo di
“indecifrabile”, data la sua complessità. La forza
della cifratura di Vigenere sta nell’utilizzare non
uno ma 26 alfabeti cifranti per criptare un solo
messaggio.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Il primo passo consiste, infatti, nella stesura della tavola di Vigenère.
Si tratta di un normale alfabeto chiaro di 26 lettere seguito da 26
alfabeti cifrati ognuno spostato a sinistra di una lettera rispetto al
precedente.
Il cifrario di Vigenère
Perciò, la riga numero 1 rappresenta un alfabeto cifrante con uno
spostamento di Cesare pari a 1. In modo analogo, la riga 2
rappresenta un alfabeto cifrante con uno spostamento di Cesare pari a
2, e così via.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
A B C D E F G H I L M N O P Q R S T U V Z
B C D E F G H I L M N O P Q R S T U V Z A
C D E F G H I L M N O P Q R S T U V Z A B
D E F G H I L M N O P Q R S T U V Z A B C
E F G H I L M N O P Q R S T U V Z A B C D
F G H I L M N O P Q R S T U V Z A B C D E
G H I L M N O P Q R S T U V Z A B C D E F
H I L M N O P Q R S T U V Z A B C D E F G
I L M N O P Q R S T U V Z A B C D E F G H
L M N O P Q R S T U V Z A B C D E F G H I
M N O P Q R S T U V Z A B C D E F G H I L
N O P Q R S T U V Z A B C D E F G H I L M
O P Q R S T U V Z A B C D E F G H I L M N
P Q R S T U V Z A B C D E F G H I L M N O
Q R S T U V Z A B C D E F G H I L M N O P
R S T U V Z A B C D E F G H I L M N O P Q
S T U V Z A B C D E F G H I L M N O P Q R
T U V Z A B C D E F G H I L M N O P Q R S
U V Z A B C D E F G H I L M N O P Q R S T
V Z A B C D E F G H I L M N O P Q R S T U
Z A B C D E F G H I L M N O P Q R S T U V
La cifratura si effettuerà come in una partita a “battaglia
navale”, ovvero basterà cercare, per ogni lettera del chiaro la
corrispondete cifrata nell’incrocio fra la colonna individuata
dalla lettera in chiaro e la riga della lettera chiave cioè del
verme.
Il cifrario di Vigenère
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Il metodo si può considerare una generalizzazione del codice
di Cesare; invece di spostare sempre dello stesso numero di
posti la lettera da cifrare, questa viene spostata di un numero
di posti variabile, determinato in base ad una parola chiave, da
concordarsi tra mittente e destinatario, e da scriversi sotto il
messaggio, carattere per carattere; la parola è detta verme, per
il motivo che, essendo in genere molto più corta del
messaggio, deve essere ripetuta molte volte sotto questo.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Il cifrario di Vigenère
Testo chiaro ARRIVANOIRINFORZI Verme VERMEVERMEVERMEVE
Esempio
Testo cifrato VVLUCVRGUVGRZBVUO
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Il cifrario di Vigenère
ESERCIZI:
Esercizio 1
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Il cifrario di Vigenère
VIGENERE1.docVIGENERE1.doc
Osservazione: 1. le prime due lettere del testo cifrato sono due “V” anche se
corrispondono ad una “A” e una “R”,
2. la seconda e la terza lettera del testo in chiaro sono due “R” ma vengono tradotte prima con la “V” e poi con la “L”,
3. Una parola chiave più lunga potrebbe coinvolgere un numero maggiore di righe aumentando la complessità della cifratura,
4. Oltre a resistere all’analisi delle frequenze ammette un numero enorme di chiavi.
Questa come si può notare è la forza del sistema di Vigenère che si basa sulla cifratura poli-alfabetica.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Cifrari polialfabetici
I cifrari polialfabetici si differenziano dai monoalfabetici in quanto un dato carattere del testo chiaro (p.es. la A) non viene cifrato sempre con lo stesso carattere, ma con caratteri diversi in base ad una qualche regola, in genere legata ad una parola segreta da concordare. In questo modo la sicurezza del codice dovrebbe aumentare in modo significativo; non è infatti più così semplice individuare le lettere del messaggio in base alla loro frequenza caratteristica in ogni lingua.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
http://critto.liceofoscarini.it/critto/monoalf0.htmhttp://critto.liceofoscarini.it/lingue/index.htmhttp://critto.liceofoscarini.it/lingue/index.htmhttp://critto.liceofoscarini.it/lingue/index.htmhttp://critto.liceofoscarini.it/lingue/index.htmhttp://critto.liceofoscarini.it/lingue/index.htmhttp://critto.liceofoscarini.it/lingue/index.htmhttp://critto.liceofoscarini.it/lingue/index.htmhttp://critto.liceofoscarini.it/lingue/index.htmhttp://critto.liceofoscarini.it/lingue/index.htmhttp://critto.liceofoscarini.it/lingue/index.htmhttp://critto.liceofoscarini.it/lingue/index.htm
La cifratura di Vigenère non suscitò alcun entusiasmo, e pur priva di punti deboli, fu pressoché ignorata per ben due secoli. La natura polialfabetica è la causa della sua resistenza ma anche della sua scarsa facilità d’uso. Nel XVIII secolo, vista la professionalità raggiunta dai loro avversari, i crittografi furono infine costretti ad adottare la cifratura di Vigenère. Oltre all’efficacia della crittoanalisi un altro evento spinse all’adozione di Vigenère: l’invenzione del telegrafo e la conseguente necessità di proteggere i telegrammi dalle intercettazioni.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
La cifratura di Vigenere è potenzialmente indecifrabile: la sua forza risiede nel
decidere una chiave lunga e casuale; tuttavia, per agevolare le operazioni di
criptazione, generalmente si tendeva a utilizzare chiavi non più lunghe di venti
lettere e questo creava dei presupposti per la sua decifrazione
Uno dei personaggi più interessanti della crittoanalisi del
XIX secolo è Charles Babbage, l'eccentrico e geniale
gentleman noto per aver progettato il precursore degli
elaboratori elettronici. Babbage, nel 1854, riuscì a creare
un metodo per decifrare la “chiffre indéchiffrable” di
Vigenère, basandosi sul fatto che una chiave non molto
lunga crea una struttura ciclica all'interno del
crittogramma, la quale può essere decifrata tramite
l'analisi delle frequenze.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
http://en.wikipedia.org/wiki/File:Charles_Babbage_-_1860.jpg
Babbage non fu l'unico ad arrivare a questa metodologia, in
modo indipendente circa dieci anni dopo Friedrich Wilhelm
Kasiski (un ufficiale in pensione dell'esercito prussiano)
pubblicò “Die Geheimschriften und die Dechiffrir-kunst” (Le
scritture segrete e l'arte della decifrazione). Per diversi motivi
Babbage non divulgò il suo metodo, e così il sistema di
decodifica della cifratura di Vigenère prese il nome di “test di
Kasiski” e il contributo di Babbage fu totalmente negletto.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Un elemento fondamentale per la
decifrazione di un codice cifrato con il
metodo di Vigenere è trovare pezzi di
stringhe uguali, trovati questi si calcola la
distanza fra essi che può essere differente
per ogni stringa, ed effettuando il MCD si
ottiene, se siamo stati fortunati, la
lunghezza della chiave.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
MCD=5.
Per esempio se la
lunghezza della chiave è
di “5” lettere il
procedimento da
svolgere è il seguente:
I. Denominare la chiave con L1 L2 L3 L4 L5.
II. Dividere il testo ogni 5 lettere
III. Raggruppare tutte le prime lettere, tutte le seconde lettere, le terze, le quarte e infine
le quinte.
IV. Effettuare per ogni raggruppamento l’analisi statistica
V. Confrontare il grafico della frequenza della lingua italiana con quello ottenuto per ogni
singola lettera.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Attacco al Codice di Vigenère (1)
Bob ha spedito ad Alice 5 messaggi cifrati col Codice di Vigenère, parola chiave K = “FORMICA”:
1) Oscar ha intercettato i crittogrammi, ed ha evidenziato le stringhe di 3 o più caratteri che si ripetono: EAV, XMBV, AQNT, GLQW, SUJ
Messaggi in chiaro:
m1 = s e n o n v e d o n o n c i c r e d o
m2 = i l g a t t o i n s e g u e l a g a t t a
m3 = e s s i s o n o f r a t e l l i g e m e l l i
m4 = s o m m a q u e s t o a q u e l l o
m5 = p e r q u e l l i c i s o n o s e m p r e
Chiave:
K = F O R M I C A F O R M I C A F O R M I C A F O
Crittogrammi:
c1 = X S E A V X E I C E A V E I H F V P W
c2 = N Z X M B V O N B J Q O W E Q O X M B V A
c3 = J G J U A Q N T T I M B G L Q W X Q U G L Q W
c4 = X C D Y I S U J G K A I S U J Z C A
c5 = U S I C C G L Q W T U A Q N T G V Y X T E
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Attacco al Codice di Vigenère (2)
2) Oscar misura le posizioni relative delle stringhe ripetute, e trova che si tratta di distanze di 7 ovvero 14 posti: deduce che la lunghezza della chiave è di 7 caratteri.
3) Scompone ora i crittogrammi a blocchi di 7 caratteri, e scrive ordinatamente tali blocchi uno sotto l’altro.
4) Applica infine l’Analisi delle Frequenze colonna per colonna (7 volte). I caratteri di ognuna delle 7 colonne sono stati infatti cifrati con lo stesso carattere della chiave.
NB. Perché l’attacco riesca, occorre disporre di un numero abbondante di crittogrammi, tutti cifrati con la stessa chiave.
Reciprocamente: per contrastare l’attacco, occorre scegliere chiavi lunghe, e cambiarle spesso.
1 2 3 4 5 6 7
X S E A V X EI C E A V E IH F V P WN Z X M B V ON B J Q O W EQ O X M B V AJ G J U A Q NT T I M B G LQ W X Q U G LQ WX C D Y I S UJ G K A I S UJ Z C AU S I C C G LQ W T U A Q NT G V Y X T E
c5
c1
c2
c3
c4
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Alla fine del XIX secolo, la crittografia era in grave difficoltà: dato che con le
innovazioni di Babbage e Kasiski anche la cifratura di Vigenère poteva essere forzata, ci
si chiedeva se esistesse davvero un sistema crittografico perfetto e immune da ogni
tentativo di crittoanalisi: la risposta arrivò da Vernam nel 1917.
Egli riuscì a dimostrare matematicamente che un sistema crittografico è perfetto (cioè
non decifrabile tramite tecniche di analisi delle frequenze) se basato su un cifrario di
Vigenère con una chiave casuale lunga quanto il messaggio, a patto che durante la
comunicazione le chiavi siano utilizzate una sola volta per ogni messaggio. Questo
sistema, chiamato Cifrario di Vernam, molto bello nella teoria, è praticamente inutilizzabile nella pratica, in quanto si pongono diversi problemi di non facile
soluzione:
– creazione di una chiave casuale;
– distribuzione sicura delle chiavi di ogni messaggio.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
https://it.wikipedia.org/wiki/Cifrario_di_Vernamhttps://it.wikipedia.org/wiki/Cifrario_di_Vernamhttps://it.wikipedia.org/wiki/Cifrario_di_Vernamhttps://it.wikipedia.org/wiki/Cifrario_di_Vernamhttps://it.wikipedia.org/wiki/Cifrario_di_Vernam
EVOLUZIONE DEI SISTEMI CRITTOGRAFICI
SISTEMI MONOALFABETICI (mondo arabo, greco e latino)
Facilmente decrittabili tramite analisi delle frequenze
SISTEMI POLIALFABETICI (Europa del XV-XVI secolo)
Troppo complessi da impostare
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
IL NOMENCLATORE
In aggiunta all’alfabeto cifrante si usa un insieme di parole in codice Svantaggi: Compilazione e trasporto del repertorio Non molto più sicuro della singola sostituzione monoalfabetica
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
IL NOMENCLATORE
La congiura di Babington
Nel 1586 Maria Stuarda, regina di Scozia, fu condannata a morte per aver cospirato contro la cugina Elisabetta. La congiura, organizzata da Anthony Babington, prevedeva la liberazione di Maria dalla prigionia in Inghilterra, l’uccisione di Elisabetta, una ribellione alla religione protestante. Sir Walsingham, segretario di stato, provò che Maria aveva preso parte alla congiura
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
IL NOMENCLATORE
Maria e Babington comunicavano grazie a un corriere (Gilbert Gifford),
un birraio, che nascondeva i messaggi dentro lo zipolo delle botti di birra
Un cifrario, costituito da
• 23 simboli che sostituivano le lettere
• 35 simboli, che sostituivano parole o frasi
• 4 nulle e un simbolo per le doppie
Gifford consegnava a Walsingham tutti i messaggi, che venivano decifrati da Thomas Phelippes Maria firmò la sua condanna a morte rispondendo alla lettera di Babington
Babington e complici furono arrestati e squartati vivi
Maria fu decapitata l’8 febbraio 1857
La congiura di Babington
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
CIFRATURA OMOFONICA
Più simboli per cifrare singoli caratteri frequenti
ESEMPIO:
testo in chiaro: E
testo cifrato: Õ Ñ ® (scelti a caso!)
Si abbassano le frequenze dei simboli del testo cifrato
12.6 per E 3.15 per Õ Ñ ®
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
CIFRATURA OMOFONICA
La Grande Cifra
Elaborata nel XVII secolo dai fratelli Rossignol, a servizio del re Sole
Le lettere sono rappresentate da numeri In proporzione alla frequenza, una lettera può essere rappresentata da più numeri Migliorano rappresentando anche le sillabe (587 combinazioni totali) Trabocchetti: numero che annulla lettera che lo precede
Decrittata nel 1890 da Etienne Bazeries, un militare che venne a capo del mistero sull’identità della Maschera di Ferro
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Oltre la cifratura Monoalfabetica
Cifrario PORTA
Cifrario di Playfair
Cifratura ADFGVX o Cifra Campale Germanica
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Due approcci: • Utilizzo di cifrature di più lettere per volta:
Playfair Porta Hill Cifratura ADFGVX
•Utilizzo di più alfabeti cifranti
Leon Battista Alberti Vigenère
Cifrario PORTA
• Cifrario PORTA
• Esercizio
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
../../PLS-crittografia/crittografia-classica_bw.pdfplayfair
Cifrario di Playfair
• Cifrario di Playfair
• Esercizio
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
../../PLS-crittografia/2-crittografia-classica.pdf../../PLS-crittografia/2-crittografia-classica.pdfplayfair.docx
Cifra Campale Germanica
• Cifra Campale Germanica
• Esercizio
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
../../PLS-crittografia/La crittografia da Atbash a RSAliceovenezia.mhthttp://www.crittologia.eu/critto/adfgvx.htmlplayfair.docxADFGVX.docx
• Aritmetica Modulare – Codice di Cesare
• Cifrari Affini
• Algoritmo Euclideo e Identita di Bezout
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
113
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Matematica e Crittografia
matematicacannizzaro/mcd.pptmatematicacannizzaro/mcd.pptmatematicacannizzaro/mcd.pptmatematicacannizzaro/mcd.pptmatematicacannizzaro/mcd.pptmatematicacannizzaro/mcd.ppt
MACCHINE CIFRANTI
ENIGMA
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Enigma
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Nel 1918 l'inventore tedesco Arthur Scherbius, che aveva studiato ingegneria elettrica ad Hannover e Monaco, mette a punto un dispositivo crittografico che in sostanza era una versione elettromeccanica del disco cifrante di Alberti. La sua invenzione è chiamata Enigma.
La versione semplificata del congegno di Scherbius consiste in 3 componenti collegati da fili elettrici: una tastiera per immettere le lettere del testo in chiaro; un'unità scambiatrice che cifra la lettera trasformandola nel corrispondente elemento del crittogramma (testo cifrato); un visore con varie lampadine, che accendendosi indicano la lettera da inserire nel testo cifrato.
Enigma
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Il passo successivo consiste nel far ruotare automaticamente il disco scambiatore di un 1/26 di
giro dopo la cifratura di ogni lettera. In altre parole, la corrispondenza tra lettere in chiaro e cifrate cambia dopo la cifratura di ogni lettera cosicché la cifratura di una stessa lettera muta continuamente. Con questa disposizione rotante, lo scambiatore definisce 26 diverse corrispondenze tra lettere in chiaro e cifrate, ed Enigma può essere usata per effettuare una cifratura polialfabetica. Tuttavia, il congegno ha un punto debole evidente: dopo 26 pressioni continue dello stesso tasto, il disco torna alla posizione iniziale, e se si continuasse a premere lo stesso tasto, lo schema di cifratura si ripeterebbe tale e quale. Per ridurre il numero di ripetizioni può essere introdotto un altro scambiatore. In questo modo, ogni volta che una lettera è cifrata, il primo disco ruota di un carattere, mentre il secondo disco invece resta immobile fin quando il primo scambiatore ha completato un giro, solo a questo punto il secondo scambiatore avanza di una posizione.
Enigma
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
L'aggiunta del secondo scambiatore comporta il vantaggio che lo schema della cifratura non si ripete finché il secondo scambiatore non è tornato al punto di partenza, il che richiede 26 giri completi del primo scambiatore, ovvero la cifratura di 26x26=676 lettere. Per una sicurezza ancora maggiore viene aggiunto un terzo rotore, per cui il numero di sostituzioni diverse è 26x25x26=16.900 (il secondo rotore effettua una rotazione in meno rispetto agli altri due, poiché dopo aver effettuato un giro completo rimane fermo una volta per far ruotare il terzo rotore). Inoltre viene aggiunto un riflessore molto simile allo scambiatore che consiste in un disco di gomma con circuiti interni che non ruotano e i fili entrano ed escono dallo stesso lato. Col riflessore installato quando si digita una lettera il segnale elettrico attraversa i 3 rotori, raggiunge il riflessore ed è mandato indietro. Quindi il segnale elettrico passa di nuovo nei rotori ma lungo un percorso diverso.
Enigma
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Enigma
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Dato che il numero di chiavi è alto ma non abbastanza per scoraggiare un crittoanalista che può disporre di più macchine e più aiutanti, per accrescere l'affidabilità si dovrebbe aumentare il numero di assetti cioè il numero di chiavi. Invece di aggiungere un altro rotore e aumentare di 26 volte le chiavi sono state introdotte due nuove caratteristiche. Innanzitutto si possono utilizzare rotori removibili e sostituibili, ad esempio il primo e il terzo rotore si possono scambiare di posto. Quindi dati tre elementi intercambiabili essi possono essere permutati in sei modi differenti; con questo accorgimento il numero di chiavi aumenta di un fattore pari a sei. La seconda caratteristica è l'inserimento di un pannello a prese multiple tra la tastiera e il primo rotore. Il pannello permette al mittente di inserire alcuni cavi muniti di spinotti, in questo modo si ha l'effetto di scambiare due lettere prima della loro immissione nel rotore. L'operatore di Enigma dispone di sei cavi che gli danno la possibilità di scambiare sei coppie di lettere simultaneamente.
Enigma
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Enigma
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Alan Mathison Turing
Londra, 23 giugno 1912 – Manchester, 7 giugno 1954
Alan Mathison Turing
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
turingRM.pptturingRM.pptturingRM.pptturingRM.ppt
BOMBE DI TURING ENIGMA
Links
COLOSSUS CIFRATURA DI LORENZ
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
Durante la II° guerra mondiale i solutori di codici britannici
prevalsero sugli inventori di codici tedeschi
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
linkenigma.docx
Films:
ENIGMA
THE IMITATION GAMES
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
COLOSSUS è stato progettato all'inizio del 1943 dal matematico Max Newman e dall'ingegnere Tommy Flowers per la decrittazione della macchina Lorenz usata dagli alti comandi tedeschi.
E’ un calcolatore elettronico con circuiti elettronici a valvole.
E’ il capostipide dei moderni elaboratori.
Per molti anni l'americano ENIAC, costruito nel 1945, è stato considerato il primo computer della storia; oggi questo primato è stato riattribuito a merito all’inglese Colossus.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Dopo aver contribuito alla nascita del computer, la crittoanalisi continuò nel dopoguerra a impiegare e migliorare la tecnologia informatica per la decodifica di qualsiasi scrittura segreta.
I crittografi sfruttarono a loro volta le risorse dei calcolatori per generare cifrature di enorme complessità (DES).
Dopo il 1945 l’informatica fu la protagonista della battaglia tra inventori e solutori di codici.
Crittografia Moderna
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Per quanto forte possa essere in teoria una cifratura, in pratica permane un problema capace di minarne le fondamenta
Anche se i calcolatori hanno profondamente influenzato la codifica dei messaggi, la vera rivoluzione crittografica del xx secolo è consistita nella comparsa di tecniche capaci di superare il problema della distribuzione delle chiavi.
DISTRIBUZIONE DELLE CHIAVI
Crittografia Moderna
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Diversi matematici di diverse epoche si sono cimentati sul versante della crittoanalisi, è famoso il caso della violazione della cifratura Enigma, il sistema crittografico usato dall’esercito nazista durante la II guerra mondiale, dovuta, in una prima fase, al matematico polacco Marian Rejewski e completata poi da un gruppo di scienziati inglesi, tra i quali ruolo prominente ebbe il celeberrimo logico Alan Turing.
È però a partire dagli anni ’70 del novecento che l’utilizzo sistematico di
idee matematiche, spesso nate in ambiti del tutto indipendenti, ha rivoluzionato teoria e tecnica della crittografia, con l’introduzione della crittografia a chiave pubblica e di altri simili protocolli.
Crittografia Moderna
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittografia Moderna
La crittografia moderna nasce nel
1975 quando Diffie, Hellman e
Merkle hanno dimostrato, in
astratto, che è possibile per due
persone comunicare in modo sicuro
senza aver preventivamente
concordato una chiave.
Il protocollo del
“doppio lucchetto”
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittografia Moderna
Il protocollo del “doppio lucchetto”
A mette il suo messaggio per B in una scatola, che chiude con un lucchetto e invia a B.
B mette il suo lucchetto alla scatola e la rispedisce ad A.
A toglie il suo lucchetto e rispedisce la scatola a B.
B toglie il suo lucchetto e legge il messaggio.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittografia Moderna
Il problema della distribuzione delle chiavi sembra risolto.
Tuttavia, la realizzazione pratica di un sistema in cui Alice
critta, Bob ricritta, Alice decritta e Bob decritta urta contro un
grave ostacolo: l’ordine delle cifrature.
Nel 1976
Metodo Diffie-Hellman-Merkle
Scambio delle Chiavi
Anche se sul piano teorico lo scambio di chiavi, che utilizza
l’aritmetica modulare, era un enorme passo avanti, non era
perfetto e sul piano pratico poteva dar adito a qualche difficoltà .
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittografia Moderna
Crittografia a chiave asimmetrica
Nel 1976 Diffie, Hellman e Merkle introdussero il
concetto di cifratura asimmetrica:
Nella crittografia a chiave asimmetrica ogni utente ha un paio di chiavi di cui una deve essere divulgata, la chiave pubblica, mentre l'altra deve essere custodita segretamente, la chiave privata.
Chiave Pubblica = funzione unidirezionale,per crittare
Chiave Privata = rende bidirezionale, per decrittare
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittografia Moderna
In questo sistema ogni utente tiene segreta la chiave privata e
divulga la sua chiave pubblica; un eventuale interlocutore
prenderà la chiave pubblica e tramite questa cripterà il
messaggio. Una volta criptato il messaggio questo potrà essere
decifrato solo dal destinatario tramite la chiave privata (neanche
chi ha codificato il messaggio può più decodificarlo).
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Crittografia Moderna
Per la realizzazione pratica di questi sistemi si ricorre a metodi matematici basati su funzioni dette a senso unico cioè facilmente calcolabili in un senso ma difficilmente invertibili, e che generalmente si basano sul problema di fattorizzare numeri grandi, oppure sul problema di determinare il logaritmo discreto nelle forme modulari o nelle curve ellittiche.
Il punto di forza di questo sistema e che gli utenti non devono
più scambiarsi le chiavi simmetriche per comunicare, ma
semplicemente cercare la chiave pubblica dell'utente con cui si
vuole avere una comunicazione riservata.
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
L'algoritmo RSA
Il più conosciuto e utilizzato algoritmo a chiavi asimmetriche è stato proposto da Ron Rivest, Adi Shamir e Leonard Adleman nel 1977 e porta un nome desunto dalle iniziali dei cognomi dei suoi inventori, RSA. L’algoritmo sfrutta l’approccio di Diffie-Hellman-Merkle e si basa sulla fattorizzazione di numeri interi grandi.
N = p x q p,q numeri primi
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
M. Gardner nel 1977 rese nota al pubblico il protocollo RSA e sfidava i lettori con un testo criptato e la chiave:
N = 114.381.625.757.888.867.669.235.779.976.146.612.010.218.296.721.242.362.562.561.842.935.706.935.245.733.897.830.597.123.563.958.705.058.989.075.147.599.290.026.879. 543.541.
Il 26 Aprile 1994 una squadra di 600 volontari annunciarono che i fattori di N sono:
p = 3.490.529.510.847.650.949.147.849.619.903.898.133.417.
764.638.493.387.843.990.820.577.
q = 32.769.132.993.266.709.549.961.988.190.834.461.413.177.
642.967. 992.942.539.798.288.533
L'algoritmo RSA
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Preliminari:
La Funzione di Eulero
Algoritmo Euclideo
Congruenze
L'algoritmo RSA
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
matematicacannizzaro/mcd.pptmatematicacannizzaro/mcd.ppt
La Funzione di Eulero
Dato un numero N, si chiama funzione di Eulero di N, e si
indica con φ(N), il numero di interi positivi< N e coprimi con
N,
φ(8) = 4, φ(6) = 2, φ(9) = 6
Se N = p primo, allora φ(N) = p – 1
Se N = pq, p e q primi, φ(N) = (p – 1)(q - 1)
L'algoritmo RSA
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
L'algoritmo RSA • p e q numeri primi, N = pq e φ(N) = (p - 1)(q - 1);
•Sceglie intero E < φ(N) e M.C.D.(E, φ(N)) = 1;
•Calcola d (chiave privata) tale che d x E ≡ 1 mod(φ(N));
•Rende pubblica la chiave (E, N);
Cifratura e Decifratura
Per inviare m, si invia C ≡ m^E mod(N)
Per decifrare C : m ≡ C^d mod(N)
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Esempio
Fissiamo due primi: p = 5 e q = 11
Calcoliamo: N =pxq= 55 e φ(N) = 40
Prendiamo: E
Calcoliamoci il M.C.D.(40, 7) facendo uso dell’algoritmo Euclideo delle divisioni successive:
40 = 7 x 5 + 5
7 = 5 x 1 + 2
5 = 2 x 2 + 1
2 = 2 x 1
Scriviamo 1 come combinazione di 7 e 40:
5 = 40 – 7 x 5
2 = 7 – 5 = 7 – (40 – 7 x 5) = 6 x 7 – 1 x 40
1 = 5 – 2 x 2 = 40 – 7 x 5 – 2 x (6 x 7 – 1 x 40) = 3 x 40 – 17 x 7.
Da cui -17 ≡ 1 (mod 40). Quindi d = - 17 ≡23 (mod 40) .
PROGETTO LAUREE SCIENTIFICHE – OTTOBRE 2019
LABORATORIO DI CRITTOGRAFIA, LICEO CLASSICO UMBERTO
Alice Bob
Chiave pubblica: (7, 55)
Chiave privata: 23
Vuole spedire ad Alice il
Messaggio M = 50
Spedisce:
C=M^7 mod55 =
50^7mod55 = 30
Decodifica C = 30
M=30^23 mod55 = 50.
Top Related