Crittografia
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/
Introduzione
“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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Introduzione
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.
E’ la scienza, ma anche l’arte, di nascondere non il messaggio ma il suo
significato.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Introduzione
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 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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Introduzione
La storia dei codici è la storia dell’antichità, secolare battaglia tra inventori e solutori di
scritture segrete; una corsa agli armamenti intellettuale il cui impatto sulle vicende
umane è stato profondo.
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Introduzione
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
CRITTOGRAFIA
steganòV = coperto
Grafein = scrivere
kriptòV = nascosto
Grafein = scrivere
coprire la scrittura
nascondere la scrittura
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Esempi di Steganografia
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.”
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Esempi di Steganografia
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Esempi di Steganografia
Erodoto (libro VII delle Storie):
“Demarato per avvisare gli Spartani del prossimo
attacco del re persiano Serse alla Grecia prese una
tavoletta doppia, ne raschiò la cera e poi sul legno
della tavoletta scrisse il piano del re. Fatto ciò
versò di nuovo cera liquefatta sullo scritto, in
modo che, venendo portata vuota, la tavoletta non
procurasse nessun fastidio da parte dei custodi
delle strade”
(prima della battaglia di Salamina, 480 a.C.)
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Esempi di Steganografia
CINA:
il messaggio era scritto
su striscioline finissime di
seta, che poi venivano
rioperte di cera (strato
protettivo) e fatte
ingerire a uno schiavo.
Arrivato a destinazione, il
messaggio veniva
espulso dallo schiavo,
scrostato e finalmente …
letto.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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, che appaiono
invisibili, ma ricompaiono una
volta che il testo venga
esposto a una fonte di calore.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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!
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Crittografia
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, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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.
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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.
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
Bob
Alice
Eva
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Crittatura
PER TRASPOSIZIONE
anagramma
PER SOSTITUZIONE
algoritmo
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
conosce sia il numero di righe scelto.
SCRIVEREINCODICE
S R V R I C D C
C I
E E N O I
E
SRVRICDCCIEENOIE
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
CRITTATURA PER SOSTITUZIONE
ALGORITMO
CIFRATURA
Sostituzione a livello di lettere
DECIFRARE
CODICE
Sostituzione a livello di parole
DECODIFICARE
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Esempi di Codici
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Esempi di Cifratura
Algoritmo di crittazione:
sostituire ogni lettera con quella X posti avanti.
Chiave: X=13
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
Messaggio in chiaro:
VENDERE TUTTI I FONDI OBBLIGAZIONARI.
Messaggio crittato :
IRAQRER GHGGV V SBAQV BOOYVTNMVBANEV.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
RIASSUMENDO …
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
CRITTARE/DECRITTARE
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
CRITTARE/DECRITTARE
Per realizzare il processo di cifratura e/o decifratura si
utilizza una funzione matematica, detta
algoritmo crittografico o cifrario.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
CRITTARE/DECRITTARE
ALGORITMI
SIMMETRICI
Gli algoritmi che utilizzano la
stessa chiave per cifrare e
decifrare il messaggio sono
detti
algoritmi simmetrici
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
CRITTARE/DECRITTARE
ALGORITMI
ASIMMETRICI
Algoritmi che utilizzano chiavi diverse per la
cifratura e la decifratura sono detti
algoritmi asimmetrici
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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”:
<<Legge di Kerckhoffs: la sicurezza di un crittosistema non
deve dipendere dal tenere celato il critto-algoritmo. La
sicurezza dipenderà solo dal tener celata la chiave>>.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
Disco di Enea il tattico
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
Il metodo ATBASH
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
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 WX Y Z
Z Y X WV 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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
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.).
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
Il 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 WX Y Z
D E F G H I J K L M N O P Q R S T U V WX Y Z A B C
Esempio:
Messaggio in chiaro:
Auguri di buon compleanno
Messaggio crittato :
DXJXULGLEXRQFRPSOHDQQR
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
Generalizzazione del cifrario di Cesare
E’ possibile generalizzare il sistema di Cesare usando uno
spostamento di k posti, anzichè di 3.
Ad esempio con k=7
A B C D E F G H I J K L M N O P Q R S T U V WX Y Z
H I J K L M N O P Q R S T U V WX Y Z A B C D E F G
Messaggio in chiaro:
Auguri di buon compleanno
Messaggio crittato :
HBNBYPKPIBVUJVTWSLHUUV
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
ESERCIZI:
Esercizio 1
Esercizio 2
Esercizio 3
Soluzioni: Esercizio1, Esercizio2, Esercizio3
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
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, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
Caso Generale
Il caso più generale è quello in cui l’alfabeto cifrato è una permutazione
di quello in chiaro.
In questo caso la chiave è l’alfabeto cifrato.
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
L P A I Q B C T R J X Z D S E G F H U O N V Y WK M
Testo Chiaro:
Testo Cifrato:
Et tu brute?
QO ON PHNOQ?
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
Vantaggi:
Esistono 26!=403291461126605635584000000 permutazioni
possibili.
Una ricerca esaustiva per trovare la permutazione giusta è
praticamente impossibile
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, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
Parola chiave
Supponiamo, per esempio, di voler impiegare il nome JULIUS CAESAR come frase chiave. In
primo luogo, si dovranno 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.
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 WX Y Z B D F G H M N O P Q T
Testo Chiaro:
Testo Cifrato:
Domani attaccheremo
IZXJYR JHHJLLESFSXZ
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
Vantaggi:
 Memorizzare una parola o una frase è molto più facile che memorizzare una
sequenza priva di senso.
 Il numero degli alfabeti cifranti generati da una parola o frase chiave è
immenso.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
Il cifrario di Polibio
La traduzione nell’attuale alfabeto si
ottiene "fondendo" k e q, due lettere
rare ma non foneticamente differenti
(nella lingua inglese), nella stessa
casella.
Ogni lettera può venire quindi
rappresentata da due numeri, guardando
la riga e la colonna in cui la lettera si
trova.
Per esempio,
@
1
2
3
4
5
1
A
F
KQ
P
V
2
B
G
L
R
W
a=11 e r=42.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
3
C
H
M
S
X
4
D
I
N
T
Y
5
E
J
O
U
Z
Sistemi Crittografici
Quindi la frase:
“ Attenzione agli scogli “
dopo la cifratura risulterà:
1144441534552435341511223224431335223224
| | | | | | | | | |
A t t e n z i o n e …………………………………
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
Polibio suggeriva di mandare tanti messaggeri quanti erano i caratteri del messaggio. Questi
portavano nella mano sinistra un numero di torce pari all'indice di riga e nella mano destra un
numero pari all'indice di colonna. In effetti più che di un codice segreto, si tratta di un sistema
di telecomunicazione, di fatto un telegrafo ottico. Telegrafi a torce esistevano da molti secoli ed
erano stati descritti da Enea il tattico intorno al 350 a.C., ma erano basati su un limitato elenco
di messaggi possibili; quello di Polibio si basa invece sulla scomposizione del messaggio nelle
singole lettere ed è quindi in grado di trasmettere qualsiasi messaggio.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
La cifratura pigpen
La cifratura pigpen (recinto per maiali) era usata dai massoni del Settecento per
proteggere i loro archivi.
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.
a
b
c
d
e
g
h
f
j . k.
m. n.
.l
.o
i
p.
.r
q.
s
t
u
v
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
w.
x. .y
.z
Sistemi Crittografici
a
b
z
ciao
.
diventa
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
ESERCIZI:
Esercizio 1
Esercizio 2
Esercizio 3
Soluzioni: Esercizio1, Esercizio2, Esercizio3
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Crittoanalisi
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Crittoanalisi
Crittoanalisi di un testo cifrato
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Crittoanalisi
Frequenze
Lett.
Occ.
%
Lett.
Occ.
%
A
6
2
M
6
2
B
38
12,6
N
40
13,3
C
7
2,3
O
7
2,3
D
22
7,3
P
16
5,3
E
24
8
Q
7
2,3
F
1
0,3
R
0
0
G
16
5,3
S
22
7,3
H
8
2,6
T
7
2,3
I
8
2,6
U
11
3,6
L
22
7,3
V
2
0,6
Z
31
10,6
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Crittoanalisi
Alfabeto
Chiaro
a b c d e
f
g
h i
cifrato
B ? ? U N
A M C Z
l
m n o
D I
G E
p
q r
O ?
S
s t
u v z
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Crittoanalisi
ESERCIZI:
Esercizio 1
Esercizio 2
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
Il cifrario di L.B. Alberti
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
cadde sui crittografi. Anche se essa
della fine del XVI secolo, le sue
risalire all’ingegno multiforme di
secolo: Leon Battista Alberti
nuova e più resistente
non prese forma prima
origini si possono far
un fiorentino del XV
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
Il cifrario di L.B. Alberti
Alberti propose di usare due o più alfabeti cifranti e di sostituirli durante la cifratura
Esempio
a b
c
d e
f
g
h i
j
k l
E U F A V 0
D N P J
C M U N B I
P L O K J
Testo Chiaro:
Testo Cifrato:
m n o
p q r
K H S G T M I
s
t
u v
w x
y
z
L B R Z C X W Y Q
V A T G S D R H Q F Z W Y X E
Leone
HBTTV
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
Il cifrario di Vigenère
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.
Vigenère 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 elusivamente pratico e legato alla attività diplomatica.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
Il cifrario di Vigenère
Il primo passo consiste, in fatti, 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.
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
Sistemi Crittografici
Il cifrario di Vigenère
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 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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
Il cifrario di Vigenère
Esempio
Verme
ARRIVANOIRINFORZI
VERMEVERMEVERMEVE
Testo cifrato
VVLUCVRGUVGRZBVUO
Testo chiaro
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
ESERCIZI:
Esercizio 1
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Sistemi Crittografici
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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, vita 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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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.
MACCHINE CIFRANTI
ENIGMA
Durante la II° guerra mondiale i solutori di codici britannici
prevalsero sugli inventori di codici tedeschi
BOMBE DI TURING
COLOSSUS
ENIGMA
CIFRATURA DI LORENZ
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.
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.
Per quanto forte possa essere in teoria una cifratura, in
pratica permane un problema capace di minarne le
fondamenta
DISTRIBUZIONE DELLE CHIAVI
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.
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
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”
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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à .
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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).
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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
piu scambiarsi le chiavi simmetriche per comunicare, ma
semplicemente cercare la chiave pubblica dell'utente con cui si
vuole avere una comunicazione riservata.
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Crittografia Moderna
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=pxq
p,q numeri primi
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Crittografia Moderna
L'algoritmo RSA
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
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Crittografia Moderna
L'algoritmo RSA
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)
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Crittografia Moderna
L'algoritmo RSA
Esempio
Fissiamo due primi: p = 5 e q = 11
Calcoliamo: N =pxq= 55 e φ(N) = 40
Prendiamo: E<N e MCD(E, φ(N) )=1, E=7
Calcoliamo: d tale che d x 7 = 1 mod 40, d=23
Chiave pubblica (7, 55)
Chiave privata d = 23
Per spedire m, si spedisce c ≡ m^7 mod(55)
Per decifrare c, m ≡ c^23 mod(55)
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
Crittografia Moderna
Calcoliamoci il M.C.D.(40, 7) facendo uso dell’algoritmo Euclideo delle divisioni
successive:
40 = 7 x 5 + 5
7=5x1+2
5=2x2+1
2=2x1
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 d = - 17 mod 40 = 23
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012
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.
50^7 mod55 = (50^2)^3 mod55 x 50 mod55 = (25)^3 mod55 x 50mod55 =
________________________________________________________
50^2 mod55 = 2500 mod55 = 25
2500 = 55 x 45 + 25
________________________________________________________
= 5 x 50 mod55 = 250mod55 = 30
________________________________________________________
25^3 mod55 = 15625 = 284 x 55 + 5
250 = 4 x 55 + 30
30^23 mod55 = (30^4)^5mod55 x 30^3 mod55 =
_______________________________________________
30^3 mod55 = 27.000 mod55 = 50
27.000 = 490 x 55 + 50
_______________________________________________
= (30^4)^5mod55 x 50 mod55 =
_______________________________________________
30^4 mod55 = (30^3 mod55) (30 mod55) =
= 50x30mod55 = 1500 mod55 = 15
1500 = 27 x 55 + 15
_______________________________________________
= 15^5 mod55 x 50 mod55 = 45 x 50 mod55
= 2250 mod55 = 50
__________________________________________________
15^5 mod55 = 759375 mod55 = 45
759375 = 13806 x 55 + 45
2250 = 40 x 55 +50
Crittografia Moderna
L'algoritmo RSA
ESEMPIO
ESERCIZIO
Soluzione Esercizio
LABORATORIO DI CRITTOGRAFIA, PROGETTO LAUREE SCIENTIFICHE, LICEO SCIENTIFICO CEI, a.a. 2011-2012