document

Crittografia  I cifrari storici
Monica Bianchini
[email protected]
Crittografia  1
 La crittografia (dal greco kryptos, nascosto, e graphein,
scrivere) è la scrittura segreta, ovvero l’arte di scrivere
messaggi che possano essere letti e compresi solo dal
legittimo destinatario
 Le sue origini risalgono alla più remota antichità, se già
la Bibbia parla di un codice segreto per scrivere il nome,
innominabile e sacrilego, di Babele  il codice Atbash
 Nel
libro di Geremia, infatti, viene usato un
semplicissimo codice monoalfabetico per cifrare la parola
Babele; la prima lettera dell’alfabeto ebraico (‫א‬, Aleph)
viene cifrata con l’ultima (‫ת‬, Taw), la seconda (‫ב‬, Beth)
viene cifrata con la penultima (‫ש‬, Shin) e così via; da
queste quattro lettere è derivato il nome di Atbash (A
con T, B con SH) per questo codice
Crittografia  2
 La scitala lacedemonica è un antico esempio di
un sistema per cifrare messaggi tramite
l’utilizzo di un bastone cilindrico, che opera
come un cifrario a trasposizione (secondo gli
scritti di Plutarco, in uso dai tempi di Licurgo,
IX sec a.C.)
 Una sottile striscia di carta veniva avvolta su
un bastone di diametro ben definito, misura di
cui era a conoscenza anche il destinatario;
sulle spire di papiro affiancate veniva scritto il
messaggio da criptare
 Terminata la scrittura, il papiro veniva svolto e inviato al
destinatario
 Il destinatario poteva ricomporre il messaggio, avvolgendo la
striscia di papiro sul suo bastone di diametro identico a quello
usato per crittografare il testo
Crittografia  3
 Per secoli la crittografia è stata appannaggio quasi
esclusivo dei militari e dei diplomatici, e i metodi
crittografici erano specifici per l’invio di messaggi affidati
a corrieri
 Nel XX secolo però, prima l’invenzione della radio, poi
quella del computer hanno cambiato in modo radicale lo
scenario
 Il periodo d’oro della crittografia coincide con la seconda
guerra mondiale, quando Alan Turing, il padre
dell’informatica teorica, insieme al gruppo di ricerca di
Bletchley Park, formalizzò la teoria necessaria per uno
studio sistematico dei cifrari
 Nel 1918, infatti, Arthur Scherbius aveva inventato la
macchina Enigma, una macchina cifrante che i tedeschi
impiegarono per le loro comunicazioni segrete durante la
seconda guerra mondiale
Crittografia  4
 La macchina Enigma consentiva di cifrare un testo
scegliendo tra 1757661003917915001016, 10 milioni
di miliardi, di combinazioni distinte
Crittografia  5
 Dal gruppo di Bletchley Park,
nel 1943, nasce il primo
calcolatore
elettronico,
il
computer Colossus, utilizzato
per decifrare le comunicazioni
“segrete” dei tedeschi, e che
permise la violazione del codice
Enigma e la vittoria anglo
americana sull’Atlantico
 Nel 1949, Claude Shannon, l’ideatore della moderna
teoria dell’informazione, pubblicò un articolo rimasto
nella storia della crittografia “Communication theory of
secrecy systems”
Crittografia  6
 Con l’avvento del computer, che ha di colpo resi
inaffidabili e superati quasi tutti i metodi classici,
nascono i metodi specifici per l’uso informatico come il
DES (Data Encryption Standard, 1975) della IBM, e il
rivoluzionario RSA (Rivest, Shamir, Adelman, 1977),
capostipite dei cifrari a chiave pubblica
 I cifrari a chiave pubblica sono intrinsecamente sicuri
poiché si basano sulla soluzione di problemi matematici
“difficili”, derivati dalla teoria dei numeri, dalla teoria
delle curve ellittiche, etc.
Crittografia  7
 Negli attuali sistemi informativi distribuiti, e più in
generale nel settore delle telecomunicazioni, la
crittografia ha assunto un rilievo ed un interesse
crescenti nelle infrastrutture di sicurezza
 La ragione è evidente: un numero considerevole di
messaggi viaggia sui canali più disparati, dalla posta al
telefono, alle comunicazioni via etere, al telex, fino alle
linee di trasmissione dati
 Altrettanto enorme è l’informazione immagazzinata nelle
memorie di massa dei calcolatori e nelle banche dati
 Se da un lato il progresso tecnologico agevola la
manipolazione (e l’intercettazione) dei dati, dall’altro
facilita anche l’applicazione della crittografia per
proteggere l’informazione stessa
Terminologia  1
 In un sistema crittografico, il testo in chiaro viene
trasformato, secondo regole, nel testo in cifra o
crittogramma; tale operazione si chiama cifratura
 Il testo cifrato viene quindi trasmesso al destinatario
attraverso un opportuno canale di comunicazione
• Il canale non sarà completamente affidabile: lungo il
percorso può trovarsi una spia che può intercettare il
crittogramma e tentare di decriptarlo
 Il destinatario legittimo decifra il crittogramma e riottiene
il testo in chiaro: se il sistema di cifra, o cifrario, è ben
congegnato, l’operazione di decifrazione o decifratura
deve risultare semplice al destinatario legittimo, ma di
complessità proibitiva alla spia
 possibile in quanto gli interlocutori legittimi possiedono
un’informazione che deve rimanere inaccessibile alla
spia, la chiave del cifrario
Terminologia  2
 Il modello delineato è schematizzato in figura:
Cifratura (C), decifrazione (D1) e decrittazione (D2)
 Si noti la distinzione tra decifrazione e decrittazione :
quest’ultima è l’operazione illegittima in cui non ci si può
avvalere della chiave
Terminologia  3
 Il problema della distribuzione delle chiavi è un punto di
importanza cruciale in qualsiasi cifrario: si dice che la
chiave è comunicata al destinatario tramite un corriere
 Per rendere nota la chiave segreta ci si può affidare ad
un canale speciale assolutamente fidato; ma se così è,
esso potrebbe essere usato per trasmettere il
crittogramma o il messaggio in chiaro
 In realtà, l’uso di un canale speciale è costoso ed inoltre
esso potrebbe essere disponibile solo per brevi intervalli
di tempo e/o in determinati momenti
Terminologia  4
 I metodi di costruzione di un cifrario non possono essere
disgiunti dallo studio degli eventuali metodi per
demolirlo, ovvero non ci si può occupare di crittografia
(la parte costruttiva) senza occuparsi di crittoanalisi (la
parte distruttiva): insieme esse costituiscono una
disciplina unitaria detta crittologia
 Nell’uso corrente si usa crittografia là dove si dovrebbe
parlare di crittologia
Terminologia  5
 Alcuni sistemi crittografici si affidano esclusivamente alla
segretezza degli algoritmi utilizzati  solo di interesse
storico, inadeguati per le applicazioni reali
 Tutti i moderni algoritmi utilizzano una chiave per
controllare sia cifratura che decifratura; un messaggio
può cioè essere letto solo se la chiave di decifrazione
“corrisponde in qualche modo” a quella di cifratura
 Esistono due classi di algoritmi:
• Simmetrici, o a chiave segreta  utilizzano la stessa chiave
per cifrare e decifrare (o la chiave di decifrazione è
facilmente ottenibile a partire da quella di cifratura)
• Asimmetrici, o a chiave pubblica  utilizzano due chiavi
diverse e la chiave di decifrazione non può essere ricavata
a partire dalle informazioni contenute nella chiave di
cifratura
Terminologia  6
 Gli algoritmi simmetrici possono essere suddivisi in cifrari
di blocco e cifrari di flusso
• I cifrari di flusso codificano un singolo carattere del
messaggio alla volta, mentre i cifrari di blocco trasformano
l’informazione a blocchi (di varia granularità)
 I cifrari asimmetrici permettono la pubblicazione della
chiave di cifratura, consentendo a chiunque di cifrare
messaggi con tale chiave, mentre solo il legittimo
destinatario (colui che conosce la chiave di decifrazione)
può decifrare il messaggio
• La chiave di cifratura è anche detta chiave pubblica e la
chiave di decifrazione chiave privata
Crittografia classica  1
 Scopo della crittografia è permettere a due persone,
Alice e Bob, di comunicare attraverso un canale insicuro,
in modo tale che una spia, Oscar, non possa
comprendere il contenuto del messaggio
 Il canale può essere una normale linea telefonica, la
rete, etc.
 L’informazione che Alice invia a Bob, il plaintext, o testo
in chiaro, può essere testuale, numerica, etc.
 Alice
“cripta” il plaintext, utilizzando una
predefinita, ed invia il testo cifrato sul canale
chiave
 Oscar non può determinare il contenuto del messaggio,
ma Bob, che conosce la chiave, può decifrare il testo
cifrato e ricostruire il plaintext
Crittografia classica  2
 Formalmente…
o
Definizione 1
Un crittosistema è una quintupla (P,C,K,E,D) per cui
valgono le seguenti condizioni
1. P è un insieme finito di plaintext
2. C è un insieme finito di testi cifrati
3. K, lo spazio delle chiavi, è un insieme finito di
possibili chiavi
4. Per ogni kK, esiste una regola di codifica ekE
ed una corrispondente regola di decodifica
dkD; per ogni funzione ek: PC e dk: CP,
dk(ek(x))=x, per ogni xP
Crittografia classica  3
 Alice e Bob impiegheranno il seguente protocollo per
realizzare uno specifico crittosistema
a)
Scelta di una chiave k: deve avvenire quando Alice e Bob
sono nello stesso posto e non osservati da Oscar, ovvero
quando possono utilizzare un canale sicuro
b)
Se Alice vuole comunicare a Bob il messaggio,
rappresentato dalla stringa x=x1x2…xn, n  1, ciascun xi
viene codificato per mezzo della regola ek, cioè yi=ek(xi),
ed il testo cifrato trasmesso è rappresentato dalla stringa
y=y1y2…yn
c)
Quando Bob riceve il messaggio y, lo decifra usando la
funzione di decodifica dk, ricostruendo il plaintext x
Crittografia classica  4
Oscar
Alice
x
Codifica
k
y
Decodifica
x
Bob
Canale sicuro
Chiave
 Note
1. Le funzioni di codifica sono iniettive: se esistessero x1x2
tali che y=ek(x1)=ek(x2), Bob non potrebbe decodificare
univocamente il messaggio
2. Se P=C, il testo cifrato viene composto utilizzando
caratteri tratti dallo stesso alfabeto del plaintext x,
organizzati diversamente a formare la stringa y
I gruppi  1
 Un gruppo è un insieme G munito di un’operazione
binaria che ad ogni coppia di elementi a,b di G associa
un elemento ab, e che gode delle seguenti proprietà:
• proprietà associativa: dati a,b,cG, vale
(ab)c = a(bc)
• esistenza dell’elemento neutro: esiste in G un (unico)
elemento neutro rispetto a , cioè tale che
ae = ea = a
per ogni a G
• esistenza dell’inverso: ad ogni elemento a di G è associato
un elemento b, detto inverso di a, tale che
ab = ba = e
I gruppi  2
 Esempi:
• I numeri interi sono un gruppo rispetto all’addizione
• Le potenze di un qualsiasi numero costituiscono un gruppo
rispetto alla moltiplicazione (l’elemento neutro è 1)
 Un gruppo si dice commutativo, o abeliano, se vale
anche la proprietà commutativa
ab = ba
per ogni coppia a,b di elementi di G
Aritmetica modulare  1
o Definizione 2
Siano a e b interi ed m intero positivo; ab (mod m), se
m divide ba, cioè a è congruo b modulo m; l’intero m è
il modulo
o Definizione 3
L’aritmetica modulo m è costituita dall’insieme Zm degli
interi {0,1,…,m1} dotato delle operazioni di somma e
moltiplicazione; le operazioni producono risultati ridotti
modulo m
o Esempio 1
In Z16, l’operazione 1113 produce come risultato il
numero 143 (mod 16)=15
Aritmetica modulare  2
 Proprietà delle operazioni modulari
1. L’insieme Zm è chiuso rispetto all’addizione ed alla
moltiplicazione, cioè per ogni a,b Zm, ab, ab  Zm
2. L’addizione e la moltiplicazione godono delle proprietà
commutativa e associativa
3. 0 è l’elemento neutro per l’operazione di addizione, 1 è
l’elemento neutro per la moltiplicazione
4. Per ogni a  Zm, ma è l’opposto di a, cioè vale la
relazione a(ma)=(ma)a=0
5. La moltiplicazione gode della proprietà distributiva
(destra e sinistra) rispetto all’addizione, cioè per ogni
a,b,cZm, (ab)c=acbc, a(bc)=abac
 Zm è un gruppo abeliano rispetto all’operazione di
somma e, grazie alla presenza della moltiplicazione, con
le proprietà sopra descritte, è un anello
Aritmetica modulare  3
 Dato che Zm contiene l’opposto, rispetto alla somma, di
ogni elemento dell’insieme,
l’operazione di sottrazione
è
ivi
definita
anche
ab = amb (mod m )
o Esempio 2
Per calcolare 1118 in Z31, si esegue l’operazione di
somma 1113 (mod 31), ottenendo 24
o Teorema 1 (Piccolo teorema di Fermat)
Sia p un numero primo t.c. xp = x mod(p); se x non è
divisibile per p, allora xp1 = 1 mod(p)
Esempio:
23 = 2 (mod 3)  8 = 2 (mod 3)
22 = 1 (mod 3)  4 = 1 (mod 3)
Shift cipher  1
 Il crittosistema SHIFT cipher è definito in Z26, poiché 26
sono le lettere che compongono l’alfabeto inglese
 Per k=3, il crittosistema a shift è il Cifrario di Cesare, che
lo utilizzava per comunicare con i generali delle sue
legioni e per le comunicazioni familiari
Siano P=C=K=Z26. Per 0  k  25,
ek(x) = x  k (mod 26)
dk(y) = y  k (mod 26)
x,yZ26
Shift cipher  2
 Per utilizzare Shift cipher per codificare testo, occorre
stabilire una corrispondenza biunivoca fra le lettere
dell’alfabeto ed il relativo numero d’ordine; quindi è
necessario scegliere la chiave k
o Esempio 3
Sia k=11; la stringa plaintext
we will meet at midnight
può essere convertita nella sequenza di numeri
22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19
cui deve essere sommato il numero 11 (mod 26)
7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4
La sequenza di numeri ottenuta, nuovamente tradotta in
caratteri, fornisce
hphtwwxppelextoytrse
Shift cipher  3
 Per
decodificare il testo cifrato, Bob deve prima
convertirlo nella corrispondente sequenza di interi, quindi
sottrarre 11 (mod 26) da ognuno di essi, ed infine
convertire gli interi così ottenuti nelle lettere
corrispondenti
 Perché un crittosistema sia operativo, deve soddisfare
certe proprietà:
• Le funzioni di codifica, ek, e di decodifica, dk, devono essere
computazionalmente poco onerose
• Una eventuale spia non deve essere in grado di risalire alla
chiave k né al plaintext x dall’osservazione del testo cifrato y
 La seconda proprietà esprime l’idea di “sicurezza”
Shift cipher  4
 Il tentativo di determinare la chiave k, dato il testo
cifrato y, costituisce la crittoanalisi : se Oscar può risalire
a k, può anche decrittare y, come Bob, utilizzando dk
 Il problema di determinare k deve essere almeno
difficile quanto quello di decifrare x a partire da y
 Shift cipher è un crittosistema che non garantisce la
sicurezza, poiché può essere crittoanalizzato attraverso
il metodo ovvio di ricerca esaustiva della chiave (su solo
26 possibili…)
Shift cipher  5
o Esempio 4
Dato il testo cifrato jbcrclqrwcrvnbjenbwrwn, provando
in successione le chiavi k=1,2,… si ottiene
iabqbkpqvbqumaidmavqvm
hzapajopuaptlzhclzupul
gyzozinotzoskygbkytotk
fxynyhmnsynrjxfajxsnsj
ewxmxglmrxmqiweziwrmri
dvwlwfklqwlphvdyhvqlqh
cuvkvejpkvkogucxgupkpg
btujudijoujnftbwftojof
a stitch in time saves nine
Un punto a
tempo ne
risparmia
cento
 il plaintext è decifrato e k=9
In media, occorrono 26/2=13 tentativi per violare il
crittosistema
Sicurezza
 Una condizione necessaria affinché il crittosistema
sia sicuro è costituita dall’impossibilità di eseguire
una ricerca esaustiva nello spazio delle chiavi
 Tuttavia, anche per |K| molto grande, la sicurezza
non è garantita
Substitution cipher  1
Siano P=C=Z26
Sia K l’insieme delle permutazioni di {0,1,…,25}
Per ogni K
e(x) = (x)
d(y) = 1 (y)
x,yZ26 e 1 permutazione inversa di 
o Esempio 5
abcdefghijklmnopqrstuvwxyz
e(a)=x, e(b)=n, etc.
d(a)=d, d(b)=l, etc.
xnyahpogzqwbtsflrcvmuekjdi
Substitution cipher  2
 Una chiave per SUBSTITUTION cipher è una delle
possibili permutazioni dei 26 caratteri dell’alfabeto
 Il numero di tali permutazioni è 26! > 4.01026
 la ricerca esaustiva nello spazio delle chiavi è
computazionalmente troppo onerosa anche per un
computer
 Tuttavia,
Substitution cipher può essere facilmente
crittoanalizzato utilizzando metodi statistici (basati sulla
frequenza delle lettere, dei digrammi, etc.)
 Nota
Shift cipher è un caso speciale di Substitution cipher in
cui vengono selezionate soltanto 26 delle 26! possibili
permutazioni
Affine cipher  1
 Per AFFINE cipher, l’insieme delle funzioni di codifica è
ristretto alla classe delle trasformazioni affini (in
aritmetica modulare)
e(x)=axb (mod 26)
a,bZ26
 Per a=1, Affine cipher coincide con Shift cipher
 Per poter decifrare un testo cifrato mediante Affine
cipher è necessario che la funzione e() sia iniettiva, cioè
che la congruenza
axb  y (mod 26)
ammetta un’unica soluzione
o Teorema 2
La congruenza axb (mod m) ha un’unica soluzione in
Zm, per ogni bZm, se e solo se MCD(a,m)=1
Affine cipher  2
 Infatti, in Z26…
1. Supponiamo che MCD(a,26)=d>1, allora la congruenza
ax0 (mod 26) ammette almeno due soluzioni distinte in
Z26, cioè x=0 e x=26/d  la funzione di codifica
e(x)=axb (mod 26) non è iniettiva
Esempio 6: Se a=4, MCD(4,26)=2 e, per e(x)=4x7,
e(3)=19, e(16)=71=19, ovvero x, x e x13 producono
lo stesso valore per e(x)
2. Viceversa, sia MCD(a,26)=1 e siano x1x2, tali che
ax1ax2 (mod 26); allora a(x1x2)0 (mod 26); in base
alle proprietà della divisione, se il MCD(a,26)=1 e
a(x1x2) è divisibile per 26, (x1x2) è divisibile per 26,
cioè x1x2 (mod 26)
 Poiché 26=213, possibili valori per aZ26 sono
1,3,5,7,9,11,15,17,19,21,23,25, mentre b può assumere
qualsiasi valore in Z26  Affine cipher dispone di
1226=312 chiavi possibili (…è sicuramente insicuro!)
Affine cipher  3
o Definizione 4
Siano a ed m interi tali che a1 e m2; se MCD(a,m)=1
allora a ed m sono relativamente primi fra loro. Il
numero degli interi in Zm che sono primi rispetto ad m è
rappresentato dalla funzione di Eulero (m)
o Teorema n3
Sia m =  pei i con pi fattori primi distinti di m ed ei>0.
i=1
Allora
n
e
e 1
(m)=  (pii  pii )
i=1
 Il numero di chiavi per Affine cipher in Zm è m(m)
o Esempio 7
Per m=60=2235, (m)=224=16 e |K|=960
Affine cipher  4
 Per decifrare il testo codificato tramite Affine cipher
occorre risolvere la congruenza yaxb(mod 26) rispetto
ad x, che ha soluzione unica quando MCD(a,26)=1
o Definizione 5
Sia aZm; l’inverso di a, a1 Zm, è tale che
aa1  a1a  1
 a ha un inverso modulo m se e solo MCD(a,m)=1 e, se
un inverso esiste, è unico
 Se p è un numero primo, allora ogni elemento 0 di Zp
ammette un inverso; un anello con questa proprietà è un
campo
 Esistono algoritmi efficienti per il calcolo dell’inverso;
tuttavia, in Z26 l’inverso può essere calcolato per tentativi
 Ad esempio, 71=15, 111=19, 251=25; infatti
715=1051 (mod 26), 1119=2091, 2525=6251
Affine cipher  5
 Sia yaxb (mod 26), da cui axyb (mod 26); poiché
MCD(a,26)=1, a ammette un inverso modulo 26;
pertanto, moltiplicando entrambi i membri della
congruenza, per a1…
a1(ax)a1(yb) (mod 26)  xa1(yb) (mod 26)
Siano P=C=Z26, K ={(a,b)Z26Z26: MCD(a,26)=1}
Per k=(a,b)K, siano
ek(x) = axb (mod 26)
dk(y) = a1 (yb) (mod 26)
x,yZ26
Affine cipher  6
o Esempio 8
Sia k=(7,3); 71 (mod 26)=15; la funzione di codifica è
ek(x)=7x3
mentre la corrispondente funzione di decodifica risulta
dk(y)=15(y3)=15y19
Si può verificare che dk(ek(x))=x, xZ26, infatti…
dk(ek(x))=dk(7x3)=15(7x3)19=x4519=x
o Esempio 9
Supponiamo di dover convertire il plaintext hot, che
corrisponde alla sequenza di cifre 7 14 19; la funzione di
codifica restituisce
773 (mod 26)=52 (mod 26)=0
7143 (mod 26)=101 (mod 26)=23
7193 (mod 26)=136 (mod 26)=6
da cui il testo cifrato axg
Vigenere cipher  1
 Sia Substitution che Affine cipher, una volta selezionata
la chiave, mappano in modo univoco ciascuna lettera
dell’alfabeto  sono crittosistemi monoalfabetici
 VIGENERE cipher, da Blaise de Vigenere (15231596), è
invece un crittosistema polialfabetico
Sia m un intero fissato e siano P=C=K=(Z26)m
Per k=(k1,k2,…,km)K, definiamo
ek(x1,x2,…,xm) = (x1k1,x2k2,…,xmkm)
dk(y1,y2,…,ym) = (y1k1,y2k2,…,ymkm)
dove tutte le operazioni sono eseguite modulo 26
Vigenere cipher  2
o Esempio 10
Sia m=6 e sia k=CIPHER o, in maniera equivalente,
k=(2,8,15,7,4,17); supponiamo che il plaintext sia
costituito dalla stringa this cryptosystem is not secure,
corrispondente a…
19 7 8 18 2 17 24 15 19 14 18 24 18 19 4 12 8 18 13 14 19 18 4 2 20 17 4
19
2
7 8 18
8 15 7
2 17
4 17
24 15 19 14 18 24
2 8 15 7 4 17
18 19 4 12
2 8 15 7
8 18
4 17
13 14 19 18
2 8 15 7
4 2
4 17
20 17 4 
2 8 15 =
_______________________________________________________________________
21 15 23 25
6
8
0 23
8 21 22 15
20
1 19 19 12
9
15 22
vpxzgiaxivwpubttmjpwizitwzt
8 25
8 19
22 25 19
Vigenere cipher  3
 Il numero complessivo di chiavi di lunghezza m è 26m
 anche per m piccolo
computazionalmente onerosa
la
ricerca
esaustiva
è
 Ad esempio, per m=5, |K|>107: la ricerca a mano è
preclusa, ma il computer può ragionevolmente realizzarla
 In Vigenere cipher, con chiave di m caratteri, ciascuna
lettera dell’alfabeto può essere mappata in base ad uno
qualsiasi degli m caratteri possibili (se la chiave è
costituita da tutti caratteri distinti)
 La crittoanalisi di sistemi polialfabetici è generalmente
molto più difficile
Hill cipher  1
 HILL cipher fu inventato nel 1929 da Lester S. Hill ed è un
crittosistema polialfabetico
 Sia m un intero e siano P=C=(Z26)m; l’operazione di
codifica avviene considerando m combinazioni lineari di m
caratteri consecutivi nel plaintext, e producendo gli m
caratteri corrispondenti del testo cifrato
o Esempio 11
Sia m=2; una sezione elementare del plaintext può essere
rappresentata da (x1,x2), ed il corrispondente testo cifrato
da (y1,y2), dove
y1=11x13x2
y2= 8x17x2
o, in notazione matriciale…
11 8
(y1,y2)T=(x1,x2)
3 7
( )
Hill cipher  2
 In generale, si considera una matrice K, mm, quale
chiave per Hill cipher, e la funzione ek(x) viene calcolata
come
( )
k11 k12 … k1m
ek(x)=(y1,y2,…,ym)T=(x1,x2,…,xm)
k21 k22 … k2m
……
km1 km2 … kmm
In altre parole y=xTK: il testo cifrato è ottenuto dal
plaintext attraverso una trasformazione lineare
 Se l’inversa della matrice K esiste in Z26, per decifrare il
testo cifrato e ricostruire il plaintext, si applica la
trasformazione xT=yK1
o Esempio 12
1
( ) ( )
11 8
3
7
=
7 18
23 11
Hill cipher  3
o Esempio 13
Supponiamo di voler codificare il plaintext july, cui
corrisponde la sequenza di numeri (9,20,11,24)
( )
( )
(9,20)
(11,24)
11 8
3 7
11 8
3 7
=(9960,72140)=(3,4)
=(12172,88168)=(11,22)
 Il testo cifrato è delw
Hill cipher  4
 Una matrice reale K possiede l’inversa se e solo se
det(K)0
 In Z26, K ammette un’inversa
MCD(det(K),26)=1; infatti…
se
e
solo
se
1) Sia MCD(det(K),26)=1; per 1im, 1jm, sia Kij la
matrice ottenuta da K eliminando la riga iesima e la
colonna jesima; sia K* tale K*ij=(1)i+j det(Kji)  K* è
l’aggiunta di K; si può dimostrare che
K1=(det(K))1 K*
 K è invertibile
2) Viceversa, se K ammette l’inversa K1, si ha
1=det(I)=det(KK1)=det(K) det(K1)
 det(K) è invertibile in Z26  MCD(det(K),26)=1
Hill cipher  5
o Esempio 14
Nel caso particolare m=2,
A1=(det(A))1
(
a22 a12
a21
a11
)
Considerando la matrice degli esempi precedenti…
det
11 8
( )
=11783 (mod 26)=7724 (mod 26)
3 7
=53 (mod 26)=1
Inoltre 11 (mod 26)=1 e quindi
1
( ) ( )
11 8
3 7
=
7 18
23 11
Hill cipher  6
Sia m un intero positivo fissato
Siano P=C=(Z26)m
Sia K={matrici invertibili mm in Z26}
Per ogni AK
eK(x) = xTA
dK(y) = yA1
dove tutte le operazioni sono eseguite modulo 26
Permutation cipher  1
 Tutti
i crittosistemi descritti finora presuppongono la
sostituzione dei caratteri del plaintext con caratteri differenti
che costituiscono il testo cifrato
 L’idea sottesa a PERMUTATION cipher è quella di mantenere i
caratteri del plaintext inalterati, cambiandoli di posizione
 Permutation (o Transposition) cipher è stato usato per oltre
400 anni: già nel 1536, G. B. Porta ne evidenziò le differenze
rispetto ai cifrari per sostituzione
Sia m un intero positivo fissato. Siano P=C=(Z26)m
K insieme delle permutazioni di {0,1,…,m1}. Per ogni K
e(x1,x2,…,xm) = (x(1),x(2),…x(m))
d(y1,y2,…,ym) = (y 1 (1), y1 (2),… y1 (m))
1 permutazione inversa di 
Permutation cipher  2
o Esempio 15
Sia m=6 e sia k= la permutazione:
1
3
2
6
3
1
4
5
5
2
6
1
1
 :
3
4
2
5
3
1
4
6
5
4
6
2
Se dunque il plaintext è rappresentato dalla stringa she
sells sea shells by the sea shore…
shesel lsseas hellsb ythese ashore

eeslsh salses lshble hsyeet hraeos
cioè eeslshsalseslshblehsyeethraeos
Il testo cifrato può essere decifrato applicando la
permutazione inversa
Permutation cipher  3
 Permutation cipher è un caso particolare di Hill cipher;
infatti, ad ogni permutazione , può essere associata
una matrice di permutazione K  definita come

Kij =
{
1 se i=(j)
0 altrimenti
 Una matrice di permutazione è ottenuta permutando
 per righe o per colonne  la matrice identità I
 Hill cipher realizzato attraverso una matrice di
permutazione K  produce esattamente Permutation
-1
cipher con permutazione ; inoltre (K  )1=K  , cioè

l’inversa della matrice K è la matrice di permutazione
definita da 1
Permutation cipher  4
o Esempio 16
Alla permutazione :
ed alla sua inversa 1:
1
3
2
6
3
1
4
5
5
2
6
4
1
3
2
5
3
1
4
6
5
4
6
2
corrispondono, rispettivamente, le matrici

K =
001000
000001
100000
000010
010000
000100
( )
K

-1
=
001000
000010
100000
000001
000100
010000
( )
Stream cipher  1
 Nei crittosistemi visti finora, i caratteri (o le stringhe)
successivi che costituiscono il plaintext vengono
codificati utilizzando la stessa chiave k, cioè il testo
cifrato viene ottenuto come
y=y1y2…=ek(x1)ek(x2)…
 Crittosistemi di questo tipo sono detti cifrari a blocchi
 Un approccio alternativo presuppone l’utilizzo di STREAM
cipher, in cui un flusso di chiavi z=z1,z2… viene
progressivamente generato ed utilizzato per codificare il
plaintext
 Fissata una chiave kK, Stream cipher genera la
successione di chiavi
zi=fi (k,x1,…,xi1)
che vengono impiegate per ottenere il testo cifrato
y=y1y2…=ez (x1)ez (x2)…
1
2
Stream cipher  2

Formalmente...
o
Definizione 6
Un cifrario di flusso è rappresentato da una tupla
(P,C,K,L,F,E,D) per cui valgono le seguenti condizioni
1. P è un insieme finito di plaintext
2. C è un insieme finito di testi cifrati
3. K, lo spazio delle chiavi, è un insieme finito di
possibili chiavi
4. L è l’alfabeto finito del flusso di chiavi
5. F=(f1, f2,…) è il generatore del flusso di chiavi
fi: KPi1  L
6. Per ogni zL, esiste una regola di codifica ezE ed
una corrispondente regola di decodifica dzD; per
ogni funzione ez: PC e dz: CP, dz(ez(x))=x, per
ogni xP
Stream cipher  3
 Un cifrario a blocchi è un caso particolare di Stream
cipher in cui il flusso di chiavi è costante, zi=k, i1
 Stream cipher è sincrono se il flusso di chiavi è
indipendente dal plaintext, cioè la funzione f dipende
solo da k; k è il “seme” che viene espanso in un flusso di
chiavi
 Stream cipher è periodico, con periodo d, se zid=zi, i1
 Vigenere cipher, con chiave di lunghezza m, è uno
Stream cipher periodico con periodo m e con
z=(z1,z2,…zm); in quest’ottica, le funzioni di codifica e di
decodifica di Vigenere cipher corrispondono con quelle di
Shift cipher
ez(x) = x  z
dz(y) = y  z
Stream cipher  4
 Gli Stream cipher sono spesso descritti per mezzo
dell’alfabeto binario, cioè P=C=L=Z2, con funzioni di
codifica/decodifica date da
ez(x) = x  z (mod 2)
dz(y) = y  z (mod 2)
 L’addizione modulo 2 realizza l’operazione di XOR, quindi
le funzioni di codifica/decodifica possono essere
implementate in hardware in modo molto efficiente
Stream cipher  5
 Un altro metodo per generare il flusso di chiavi consiste,
a partire dal seme (k1,k2,…,km), nell’utilizzare una
relazione di ricorrenza lineare
m1
zim=  cjzij (mod 2)
j=0
con c0,c1,…,cm1Z2 costanti predefinite; senza perdita di
generalità, c0=1
• La chiave k consiste dei 2m valori (k1,k2,…,km,c0,c1,…,cm1)
• Se
(k1,k2,…,km)=(0,0,…,0) il flusso di chiavi
completamente costituito da 0: situazione da evitare!
è
 Viceversa, mediante un’opportuna scelta delle costanti
c0,c1,…,cm 1, per qualsiasi altro valore del vettore di
inizializzazione (k1,k2,…,km), si ottiene un flusso
periodico, con periodo 2m 1
 Un “seme breve” produce uno Stream cipher con
periodo lungo… difficile da violare
Stream cipher  6
o Esempio 17
Sia m=4 e (k1,k2,k3,k4)=(1,0,0,0); utilizzando la regola di
ricorsione lineare
zi4=zi+zi1 (mod 2)
con (c0,c1,c2,c3)=(1,1,0,0), si ottiene il flusso di chiavi, di
periodo 15,
1,0,0,0,1,0,0,1,1,0,1,0,1,1,1,…
Qualsiasi altro vettore di inizializzazione diverso da 0, a
parità di ci, i=0,…,3, produrrà una permutazione ciclica
dello stesso flusso di chiavi
La crittoanalisi  1
 Analizzando il contenuto di un testo cifrato, e non
conoscendo l’algoritmo di cifratura, attraverso tecniche
statistico/matematiche si possono comunque ottenere
informazioni sul testo in chiaro
 Per fortuna ciò non è sempre possibile: la maggior parte
dei cifrari moderni è ancora al sicuro da tecniche di
crittoanalisi
 La storia ci insegna però che non esistono cifrari
inviolabili
La crittoanalisi  2
 I tipi di attacco alla sicurezza dei crittosistemi si
distinguono in…
• Ciphertextonly  l’intruso è venuto a conoscenza di una
stringa di testo cifrato y
• Known plaintext  l’intruso conosce una stringa di
plaintext x, ed il corrispondente testo cifrato y
• Chosen plaintext  l’intruso ha ottenuto accesso
temporaneo al meccanismo di cifratura: può quindi
scegliere un plaintext x e costruire il corrispondente testo
cifrato y
• Chosen ciphertext  l’intruso ha ottenuto accesso
temporaneo al meccanismo di decifratura: può quindi
scegliere un testo cifrato y e costruire il corrispondente
plaintext x
Un esempio di crittoanalisi  1
o Crittoanalisi statistica del cifrario di Cesare
Il cifrario di Cesare, come la maggior parte dei cifrari
storici basati su trasposizioni e traslazioni, 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
Un esempio di crittoanalisi  2
o Esempio
Testo in chiaro: prova di trasmissione
Crittogramma: surbdgnzudvpnvvnrqh
• Le frequenze relative al testo cifrato risultano s(1/19),
u(2/19), r(2/19), b(1/19), d(2/19), g(2/19), n(3/19),
z(1/19), v(3/19), p(1/19), h(1/19)
• Si confrontano tali frequenze con quelle delle singole
lettere nella lingua italiana: a(0.114), e(0.111), i(0.104),
o(0.099), t(0.068), r(0.065),...
Un esempio di crittoanalisi  3
• Con
queste informazioni si ottiene, in prima
approssimazione, la stringa srobagizravpivvioqh, a partire
dalla quale si può reiterare il procedimento