PROGETTO LAUREE SCIENTIFICHE
ITGS PASCAL-UNIV. PARMA
(è stato usato vario materiale di Alessandro Zaccagnini, Alessandro Languasco)
Altro materiale è stato preso dal sito:
http://avires.dimi.uniud.it/claudio/teach/sicurezza2012/lezione-02.pdf
Docenti: BAROZZI -SIMEONE
CORSO DI CRITTOGRAFIA
Secondo incontro
CRITTOGRAFIA CLASSICA
ENIGMA
Enigma era una macchina usata
dai tedeschi durante la seconda
guerra mondiale per
criptare/decriptare messaggi.
Fu violata dai crittanalisti
inglesi, in particolare Alan
Touring.
Questo permise agli alleati di
vincere la guerra.
STRUTTURA

La macchina Enigma aveva l'aspetto di una macchina per
scrivere con due tastiere: una vera inferiore, e la seconda nella
quale i tasti erano sostituiti da lettere luminose che si
accendevano ogniqualvolta veniva premuto un tasto sulla
tastiera effettiva: la sequenza delle lettere che si illuminavano
dava il messaggio cifrato (o quello in chiaro, se si batteva il
testo cifrato).
Da Wikipedia
FUNZIONAMENTO DI ENIGMA


I tedeschi erano convinti che il loro metodo per
criptare/decriptare messaggi tramite ENIGMA
fosse inviolabile.
L’elemento base di Enigma è il rotore (o
scambiatore), una ruota dentata con 26 contatti
elettrici su un lato (uno per ogni lettera
dell’alfabeto tedesco), collegati in maniera casuale
ad altri 26 contatti elettrici in uscita (ogni lettera
veniva sostituita con un’altra).
IL ROTORE
CARATTERISTICHE DEI ROTORI


Un rotore può ruotare (da cui
il nome) attorno ad un perno:
in questo modo con un singolo
rotore si possono ottenere 26
cifrature monoalfabetiche
diverse, a seconda della
posizione del rotore.
Se il rotore ruota ad ogni
carattere cifrato, allora
implementa una cifratura
polialfabetica con 26
alfabeti diversi
CARATTERISTICHE DEI ROTORI


La macchina Enigma era dotata di tre
rotori in cascata: il primo ruotava
avanzando di una posizione ad ogni
carattere cifrato, il secondo avanzava
di una posizione ad ogni giro
completo del primo, e il terzo
avanzava di una posizione ad ogni
giro completo del secondo.
Realizza una cifratura
polialfabetica basata sull’uso di
26x26x26 = 17576 alfabeti
cifranti
IL RIFLESSORE

Per far sì che la macchina possa essere usata anche per
decrittare i messaggi, viene introdotto il riflessore: in
questo modo premendo la lettera A si ottiene la lettera
C, ma anche premendo C si ottiene A.
Grazie al riflessore la stessa macchina può essere
usata sia per criptare che per decriptare un testo.
IL PANNELLO A PRESE MULTIPLE


Infine, la macchina Enigma era dotata di un
pannello a prese multiple che, mediante l’utilizzo di
6 cavi, permetteva di scambiare tra loro 6 coppie
di lettere, aggiungendo quindi un ulteriore livello di
cifratura a sostituzione.
In questo modo il numero di combinazioni possibili è
molto alto: usando 6 cavi si possono ottenere
100.391.791.500 configurazioni differenti
ROBUSTEZZA DI ENIGMA



Per forzarlo occorrerebbe testare tutte le possibili
configurazioni: queste con gli accorgimenti usati dai
nazisti erano più di 1.764.486.127.404.000.
Come detto prima i tedeschi ritenevano che Enigma
fosse inviolabile, proprio grazie all’alto numero di
configurazioni possibili.
Come fu possibile violare Enigma?
VIOLARE ENIGMA



I crittanalisti inglesi, e in particolare Alan Turing, si
basarono sull’ipotesi che alcuni messaggi riguardassero
argomenti specifici.
Per esempio i tedeschi trasmettevano sempre alla stessa
ora le previsioni del tempo, oppure quando un
sottomarino avvistava una nave ne comunicava la
posizione.
Turing costruì il primo esempio di computer, chiamato
BOMBA, per il ticchettio che produceva, che era in
grado di vagliare tutte le possibili combinazioni e di
restituire il risultato.
CRITTOGRAFIA ASIMMETRICA


Si chiama crittografia asimmetrica un sistema per
criptare/decriptare messaggi in cui anche se si
conosce il metodo usato per criptare e la chiave
pubblica, trovare la chiave privata e il metodo per
decriptare risulta molto complesso, quindi richiede
tempi molto lunghi.
Per capire la crittografia asimmetrica occorre
addentrarsi nelle proprietà dei numeri e in
particolare di numeri primi, introducendo le classi
resto modulo n.
CLASSI RESTO MODULO n (Zn)
Le classi resto modulo n sono classi di equivalenza.
Dati tre numeri interi a,b,n con n≠0, diremo che a è
congruente a b modulo n (e scriveremo ab mod n)
se e solo se n divide a-b (e scriveremo n|(a-b))
Si noti che siccome il resto della divisione di a per n è
un numero compreso tra 0 e n-1 ogni numero intero a
è congruente ad un numero compreso tra 0 e n-1.
CLASSI RESTO MODULO n (Zn)
La relazione di congruenza modulo n è una relazione di
EQUIVALENZA, infatti gode delle proprietà:


RIFLESSIVA: infatti aZ, n divide a − a = 0, quindi a  a (mod n)
SIMMETRICA: infatti a,bZ, se n divide a − b, allora n divide anche
b-a, quindi se a  b (mod n) allora anche b  a (mod n)

TRANSITIVA: infatti a,b,cZ, se n divide a-b e b-c allora n divide
anche la loro somma (a-b)+(b-c)=a-c , ovvero se a  b (mod n) e
b  c (mod n) allora a  c (mod n)
CLASSI RESTO MODULO 10
Z10 Ovvero classi resto modulo 10
E’ formato dalle classi di equivalenza di :
[0] 10, [1] 10, [2] 10, [3] 10, [4] 10, [5] 10, [6] 10, [7] 10, [8] 10, [9] 10
Ma come sono fatte queste classi?
[0] 10 è formata da tutti i multipli di 10, cioè {0, 10, -10, 20, -20,…}
[1] 10 è formata dai numeri x interi, tali che x-1 sia multiplo di 10,
cioè: {1, 11, -9, 21, -19, 31, ….}
Analogamente:
[2] 10={2, 12, -8, 22, -18, 32, ….}
[3] 10={3, 13, -7, 23, -17, 33, ….}
[4] 10={4, 14, -6, 24, -16, 34, ….}
[5] 10={5, 15, -5, 25, -15, 35, ….}
[6] 10={6, 16, -4, 26, -14, 36, ….}
[7] 10={7, 17, -3, 27, -13, 37, ….}
[8] 10={8, 18, -2, 28, -12, 38, ….}
[9] 10={9, 19, -1, 29, -11, 39, ….}
CLASSI RESTO MODULO 10

Come si eseguono le operazioni in Z
10
?
+ 0
1
2
3
4
5
6
7
8
9
*
0
1
2
3
4
5
6
7
8
9
0
0
1
2
3
4
5
6
7
8
9
0
0
0
0
0
0
0
0
0
0
0
1
1
2
3
4
5
6
7
8
9
0
1
0
1
2
3
4
5
6
7
8
9
2
2
3
4
5
6
7
8
9
0
1
2
0
2
4
6
8
0
2
4
6
8
3
3
4
5
6
7
8
9
0
1
2
3
0
3
6
9
2
5
8
1
4
7
4
4
5
6
7
8
9
0
1
2
3
4
0
4
8
2
6
0
4
8
2
6
5
5
6
7
8
9
0
1
2
3
4
5
0
5
0
5
0
5
0
5
0
5
6
6
7
8
9
0
1
2
3
4
5
6
0
6
2
8
4
0
6
2
8
4
7
7
8
9
0
1
2
3
4
5
6
7
0
7
4
1
8
5
2
9
6
3
8
8
9
0
1
2
3
4
5
6
7
8
0
8
6
4
2
0
8
6
4
2
9
9
0
1
2
3
4
5
6
7
8
9
0
9
8
7
6
5
4
3
2
1
CLASSI RESTO MODULO 11
Z11 Ovvero classi resto modulo 11
E’ formato dalle classi di equivalenza di :
[0] 11, [1] 11, [2] 11, [3] 11, [4] 11, [5] 11, [6] 11, [7] 11, [8] 11, [9] 11, [10]11
Ove:
[0] 11 = {0, 11, -11, 22, -22,…}
[1] 11 = {1, 12, -10, 23, -21, 34 ….}
[2] 11 = {2, 13, -9, 24, -20, 35, ….}
[3] 11 = {3, 14, -8, 25, -19, 36, ….}
…………….
[10] 11 = {10, 21, -1, 32, -12, 43, ….}
CLASSI RESTO MODULO 11

Come si eseguono le operazioni in Z
11
?
+
0
1
2
3
4
5
6
7
8
9
10
*
0
1
2
3
4
5
6
7
8
9
10
0
0
1
2
3
4
5
6
7
8
9
10
0
0
0
0
0
0
0
0
0
0
0
0
1
1
2
3
4
5
6
7
8
9
10
0
1
0
1
2
3
4
5
6
7
8
9
10
2
2
3
4
5
6
7
8
9
10
0
1
2
0
2
4
6
8
10
1
3
5
7
9
3
3
4
5
6
7
8
9
10
0
1
2
3
0
3
6
9
1
4
7
10
2
5
8
4
4
5
6
7
8
9
10
0
1
2
3
4
0
4
8
1
5
9
2
6
10
3
7
5
5
6
7
8
9
10
0
1
2
3
4
5
0
5
10
4
9
3
8
2
7
1
6
6
6
7
8
9
10
0
1
2
3
4
5
6
0
6
1
7
2
8
3
9
4
10
5
7
7
8
9
10
0
1
2
3
4
5
6
7
0
7
3
10
6
2
9
5
1
8
4
8
8
9
10
0
1
2
3
4
5
6
7
8
0
8
5
2
10
7
4
1
9
6
3
9
9
10
0
1
2
3
4
5
6
7
8
9
0
9
7
5
3
1
10
8
6
4
2
10
10
0
1
2
3
4
5
6
7
8
9
10
0
10
9
8
7
6
5
4
3
2
1
Somiglianze tra Z10 e Z11
Per quanto riguarda le proprietà dell’addizione sia
Z10 che Z11 godono delle seguenti proprietà:
 Esiste l’elemento neutro 0, tale che 0+a=a+0=a
 Ogni elemento a ammette opposto, ovvero esiste un
elemento b tale che: a+b=b+a=0
 Vale la proprietà associativa: (a+b)+c=a+(b+c)
 Vale la proprietà commutativa: a+b=b+a
Ovvero Z10 e Z11 sono un GRUPPO COMMUTATIVO
rispetto all’addizione

Somiglianze tra Z10 e Z11



Per quanto riguarda la moltiplicazione sia Z10 che
Z11 godono delle seguenti proprietà:
Comunque presi a,b,c a* (b*c)=(a*b)*c
(PROPRIETA’ ASSOCIATIVA di *)
Comunque presi a,b,c
a*(b+c)=a*b+a*c e (b+c)*a=b*a+c*a
PROPRIETA’ DISTRIBUTIVA di * rispetto +
Quindi sia Z10 che Z11 sono ANELLI
Differenze tra Z10 e Z11
Sia in Z10 che in Z11 esiste un elemento neutro della
moltiplicazione 1, infatti comunque preso un
elemento a, a*1=1*a=a
 Infine sia in Z10 che in Z11 vale la proprietà
commutativa della moltiplicazione
Quindi sono anelli con unità commutativi, ma a
differenza di Z10 in Z11 ogni elemento diverso da 0
ammette un inverso moltiplicativo, cioè Z11 è un
CAMPO

INVERTIBILITA’ IN Zn



Un elemento aZn, è INVERTIBILE se esiste bZn
tale che a*b=1
Osserviamo, quali elementi sono invertibili in Z10?
1, 3, 7, 9
E quali elementi sono invertibili in Z11?
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Perché c’è questa differenza?
ALGORITMO EUCLIDEO
ALGORITMO EUCLIDEO PER CALCOLO MCD TRA
DUE NUMERI:
Dati due numeri a,bN, con a>b e b≠0 vogliamo
calcolare il massimo comun divisore tra a e b:
 Divido a per b: ottengo a=bq1+r1 con 0≤r1<b
 Divido b per r1: ottengo b=r1q2+r2 con 0≤r2<r1
 Divido r1 per r2: ottengo r1=r2q3+r3 con 0≤r3<r2
 E così via ottenendo all’ultimo passo: rk-2=rk-1qk ossia
rk=0, in questo caso rk-1 è l’MCD tra a e b.
ESEMPIO CALCOLO MCD
Voglio calcolare l’MCD tra 1547 e 560 utilizzando
l’algoritmo euclideo:
 1547/560=2 con resto 427
 560/427=1 con resto 133
 427/133=3 con resto 28
 133/28=4 con resto 21
 28/21=1 con resto 7
 21/7=3 con resto 0
Quindi 7 è il massimo comun divisore tra 1547 e 560

FORMULA DI BEZOUT


Sia d il massimo comun divisore tra a e b, con a>b e
b≠0. Allora esistono u,vZ, tali che d=ua+vb.
ESEMPIO: prendiamo i dati dell’esempio
precedente MCD(1547;560)=7
7=281-21 ma 21=133-4 28, quindi
7=28 1-133+4 28=5 28-133 1
analogamente:
7=5 427-16 133=21 427-16 560=
=21 1547-58 560 da cui segue u=21 e v=-58
INVERTIBILITA’ IN Zn


TEOREMA: Gli elementi a di Zn che hanno inverso
moltiplicativo sono tutti e soli quelli primi con n.
DIMOSTRAZIONE: Sia d il massimo comun divisore
tra a ed n, se d>1 non può esistere b tale che
ab1 (mod n) perché se così fosse d dovrebbe
dividere ab-1, ma siccome d divide a, d dovrebbe
dividere anche 1 e questo è impossibile.
Supponiamo ora che d=1, grazie alla formula di
Bezout esistono u,vZ, tali che d=au+nv, cioè
au+nv=1, quindi l’inverso di a è b=u