Elementi di
crittografia
Pierluigi Ridolfi
Università di Roma La Sapienza
1 marzo 2000
ERREsoft
1
Piano della lezione
• Inquadramento.
• Storia.
• Crittografia tradizionale:
codifica simmetrica a una
chiave.
• Tecniche moderne: codifica
asimmetrica a due chiavi.
• Riservatezza, autenticità,
integrità.
• Sicurezza informatica.
ERREsoft
2
Inquadramento della
crittografia
• “Scrittura nascosta”.
• Fa parte della classe di sistemi
per trasmettere messaggi
“riservati”:
 Sistemi per codici
es.: 15 = comprare, 16 = vendere
 Sistemi per frasi
es.: “I lunghi singhiozzi dei violini
d’autunno” sbarco in Normandia
 Scritture “simpatiche”
ERREsoft
3
La scìtala spartana (1)
Plutarco nella Vite parallele scrive che gli efori
(i magistrati di Sparta) inviarono a Lisandro
una scìtala con l'ordine di tornare in patria. E
spiega: "La scitala consiste in questo. Gli efori,
all'atto di spedire all'estero un generale,
prendono due pezzi di legno rotondi e
perfettamente uguali, sia in lunghezza sia in
larghezza, di dimensioni cioè corrispondenti.
Di questi pezzi di legno, che si chiamano
scitale, uno lo conservano loro, l'altro lo
consegnano al partente. In seguito, allorché
vogliono comunicare qualche cosa di grande
importanza e che nessuno altro deve sapere,
tagliano un rotolo di papiro lungo e stretto
come una cinghia e l'avvolgono attorno alla
scitala in loro possesso, coprendone
tutt'intorno la superficie del legno col papiro,
senza lasciare il minimo interstizio.
ERREsoft
4
La scìtala spartana (2)
Compiuta questa operazione, scrivono sul
papiro così come si trova disteso sulla scitala
ciò che vogliono, e una volta scritto, tolgono il
papiro e glielo mandano senza il bastone. Il
generale, quando lo riceve, non può leggere le
lettere di seguito, poiché non hanno alcun
legame tra loro e rimangono sconnesse, finché
anch'egli non prende la sua scitala e vi avvolge
in giro la striscia di papiro. Così la spirale
torna a disporsi nel medesimo ordine in cui fu
scritta, e le lettere si allineano via via, di modo
che l'occhio può seguire la lettura attorno al
bastone e ritrovare il senso compiuto del
messaggio. La striscia di papiro è chiamata
scitala al pari del legno".
ERREsoft
5
Schema della scìtala
Un messaggio scritto longitudinalmente
diventa illeggibile sulla cinghia svolta
H
H
H
H
H
ERREsoft
6
Il metodo di Cesare
Svetonio nella Vita del Divo Giulio:
"… se vi era qualche questione riservata
egli usava scrivere in cifra, e questa cifra
consisteva
in
una
disposizione
apparentemente caotica delle lettere,
sicché era impossibile ricostruire la
parola originale. Chi voglia scoprirne il
senso e decifrarla sappia che bisogna
sostituire a ogni lettera la terza che
segue nell'alfabeto; vale a dire dove è
scritto A bisogna leggere D e così di
seguito."
ERREsoft
7
Concetti
fondamentali
•
•
•
•
Mittente e destinatari
Alfabeto
Messaggio
Metodi di codifica e
decodifica
ERREsoft
8
Alfabeto
Varietà di caratteri
Esempio:
– le 10 cifre da 0 a 9
– le 26 lettere minuscole
– le 26 lettere maiuscole
– le 6 vocali minuscole
accentate: à è é ì ò ù
– i 17 caratteri speciali
. , : ; ’” ! ? ( ) + - = < > * /
– lo spazio
ERREsoft
9
Messaggio
• Sequenza di caratteri
• Lunghezza qualunque
• In genere è un testo,
composto da più righe
• Ogni riga viene spezzata in
messaggi elementari m,
ognuno di lunghezza fissa
ERREsoft
10
Metodi “storici” di
crittografia
• Metodo della traslazione
 Giulio Cesare
• Metodo della corrispondenza
diretta
 Mercanti fiorentini
 Rapporti riservati nell’età moderna
• Metodo della corrispondenza
indiretta
 Rapporti riservati nell’età
contemporanea
ERREsoft
11
Metodo della
traslazione
1 2 3 4 5 6 7 8 9 10 11 12 ..
A B C D E F G H I L M N ..
chiave = 2
CADE  ECFG
ERREsoft
12
Corrispondenza
diretta
A B C D E F G H I L M
C
I
R U G Z V S T B N
CADE  RCUG
ERREsoft
13
Corrispondenza
indiretta
A B C D E F G H I L M
indice
A
C I R U G Z V S T B N
B
S T U V B C N I R Z G
C
R Z G S C T U B N I V
D
……………………………………….
R
T B N I V R Z G S C U
Z
………………………………………
Chiave =
ABRACADABRA
Messaggio = BACCA
Codifica =
I S NRR
ERREsoft
14
Sistemi binari di
crittografia
• Somma
• Trasformazione indiretta
• Moltiplicazione
• Potenza
ERREsoft
15
Somma
• Il messaggio elementare m
sia di 64 bit.
• Si sceglie come “chiave”
una costante k  64 bit.
• Al valore numerico del
messaggio si somma la
chiave.
m’ = m + k
• Il metodo concettualmente
è simile a quello di
traslazione.
ERREsoft
16
Trasformazione
indiretta
Chiave
1 0 0 1 0 0 1 ...
Matrice
0
1
0
1
1
0
(1)
indice
0
1
Messaggio 1 0 1 0 0 0 ...
Codifica
ERREsoft
0 0 1 1 0 1 ...
17
Trasformazione
indiretta
Chiave
1 0 0 1 0 0 1 ...
Matrice
0
1
0
1
1
0
(2)
indice
0
1
Messaggio 1 0 1 0 0 0 ...
Codifica
ERREsoft
0 0 1 1 0 1 ...
18
DES: Data
Encryption Standard
• Sistema di codifica basato
su una chiave di 56 bit e una
complessa sequenza di
trasformazioni indirette.
• Approvato dal National
Bureau of Standard nel ‘77.
• Triplo DES: variante basata
su una triplice applicazione
del DES.
ERREsoft
19
Prodotto
• Si sceglie come “chiave”
una costante di 8 bit.
• Il valore numerico di ogni
campo (di 64 bit) viene
moltiplicato per la costante.
• La lunghezza del campo
risultante sarà di 72 bit.
ERREsoft
20
Potenza
• Si sceglie come “chiave”
una costante di 8 bit.
• Il valore numerico di ogni
campo (di 64 bit) viene
elevato alla potenza espressa
dalla costante.
• La lunghezza del campo
risultante sarà di 512 bit.
ERREsoft
21
Sistemi di codifica
simmetrici
• I sistemi sono sempre
reversibili.
• La chiave per la codifica è
la stessa utilizzata per la
decodifica.
• In genere la chiave è
diversa per ogni coppia di
persone: pertanto n persone
danno luogo a n•(n-1):2
chiavi diverse.
• Difficoltà di gestione.
ERREsoft
22
Sistemi di codifica
asimmetrici
• La chiave per la codifica è
diversa da quella utilizzata
per la decodifica.
• Ogni persona ha una coppia
di chiavi:
– una, indicata da h, viene resa
nota (chiave pubblica);
– l’altra, indicata da j, viene
tenuta segreta (chiave privata).
• Semplicità di gestione.
ERREsoft
23
Processo “ideale”
• Codifica
Il mittente, utilizzando un certo
algoritmo T, codifica m con la chiave
pubblica h del destinatario ottenendo
m’ che spedisce.
m’ = T (h,m)
• Decodifica
Il destinatario riceve m’ e lo decodifica
con lo stesso algoritmo T ma con la
propria chiave privata j, riottenendo m.
m = T (j, m’)
ERREsoft
24
Osservazioni
• T, h e j devono essere scelti in
modo tale che l’algoritmo
funzioni.
• h e j potrebbero essere assegnati
una volta per tutte da un Ente
centrale, in esclusiva per ogni
persona che ne fa richiesta.
• Deve essere praticamente
impossibile ricavare j da h.
ERREsoft
25
Sistema RSA
• Rivest, Shamir, Adleman.
• MIT, 1977.
• Algoritmo basato sul
Teorema di Fermat-Eulero.
ERREsoft
26
Teorema di Fermat
Se a e n sono due numeri primi,
con a < n, il resto della
divisione tra la potenza an e
l’esponente n è sempre uguale
alla base a.
Esempi
 a = 2 n = 5 an = 32
32 : 5 = 6 con resto 2
 a = 3 n = 7 an = 2187
2187 : 7 = 312 con resto 3
ERREsoft
27
Teorema di Eulero
E’ una rielaborazione del
Teorema di Fermat nel caso che
n non sia un numero primo ma
il prodotto di più numeri primi.
ERREsoft
28
Principio di funzionamento
del Sistema RSA
(1)
• n sia il prodotto dei due numeri
primi p e q
• a ogni persona viene assegnata
come chiave pubblica h un
numero a caso
• la corrispondente chiave privata
j viene calcolata in modo che
(h·j) : (p-1)·(q-1)
abbia per resto 1
ERREsoft
29
Principio di funzionamento
del Sistema RSA
(2)
Se:
m’ = resto della divisione
di mh per n
m’’ = resto della divisione
di m’j per n
Si dimostra che:
m’’ = m
Conseguenze:
m’ = messaggio cifrato
m’’ = messaggio decifrato
ERREsoft
30
Esempio
• h = 11, p = 3, q = 5
• n = 15 (p-1)(q-1) = 8  j = 3
• verifica: (h • j):8  resto = 1
-------------------m = 2
h
m’  m = 2
11
= 2048
 : 15  resto = 8 = m’
j
m’’  m’ = 8
3
= 512
 : 15  resto = 2 = m
ERREsoft
31
Principio di
invulnerabilità
• E’ noto n, che si sa essere il
prodotto dei due primi p e q, ma
non sono noti né p né q, né è
possibile ricavarli da n (si tratta
di scomporre in fattori un numero
grandissimo, operando per
tentativi ).
• Non è pertanto possibile
calcolare (p-1)•(q-1).
• Dunque, noto h, non è possibile
calcolare j.
ERREsoft
32
Il principio delle
due chiavi
j è la chiave privata, nota
solo all’interessato.
h è la chiave pubblica, che
tutti possono conoscere.
Non è praticamente possibile
nota j ricavare h e viceversa.
ERREsoft
33
I tre pilastri della
crittografia
• Riservatezza:
 certezza che il testo può essere
letto solo dal destinatario.
• Autenticità:
 certezza del mittente.
• Integrità:
 certezza del messaggio.
ERREsoft
34
Riservatezza
• A è il mittente.
• B è il destinatario.
• A codifica m con la chiave
pubblica di B  m’.
• B decodifica m’ con la propria
chiave privata  m.
ERREsoft
35
Garanzia della
riservatezza
A
m
hB
m'
B
ERREsoft
jB
m
36
Autenticità
• A è il mittente.
• B è il destinatario.
• A codifica m con la propria
chiave privata.
• B decodifica m’ con la chiave
pubblica di A  m.
ERREsoft
37
Garanzia
dell’autenticità
A
m
jA
m'
B
ERREsoft
hA
m
38
Riservatezza e
autenticità
• A è il mittente.
• B è il destinatario.
• A codifica m prima con la propria
chiave privata, poi con la chiave
pubblica di B  m’.
• B decodifica m’ prima con la
chiave pubblica di A, poi con la
propria chiave privata  m.
Sistema della doppia codifica
ERREsoft
39
Schema del processo di
riservatezza e autenticità
A
m
hB , j A
m'
B
ERREsoft
jB , hA
m
40
Integrità
• Il processo di autenticità non
garantisce l’integrità del messaggio
trasmesso.
• Concetto di “impronta” (“hash”):
campo di lunghezza fissa ricavato
dal messaggio secondo una precisa
formula (“funzione di hashing”).
• E’ praticamente impossibile
dall’impronta risalire al messaggio
che l’ha generata.
ERREsoft
41
Concetto di
impronta
Messaggio
m
Algoritmo
di hashing
Impronta
r
ERREsoft
42
Processo di garanzia
dell’integrità
• Il mittente prepara il messaggio
e ne calcola l’impronta.
• Messaggio e impronta vengono
codificati separatamente ma
viaggiano insieme.
• Il destinatario decodifica
messaggio e impronta; ricava
dal messaggio una nuova
impronta; confronta le due
impronte.
• Se le due impronte coincidono il
messaggio non è stato alterato.
ERREsoft
43
Garanzia
dell’integrità
A
m, r
jA
m, r’
B
ERREsoft
hA
m, r
r
44
Sicurezza
informatica
• Basata sull’algoritmo di
generazione delle chiavi.
• Lunghezza di n = p · q = 1024 bit.
• Di conseguenza p e q sono numeri
con circa 150 cifre.
• Noto n, p e q si possono ottenere
solo per tentativi, e ciò risulta
impossibile in tempi utili.
• Se non si conoscono p e q, non si
può ricostruire j (chiave privata ): il
sistema pertanto è invulnerabile.
• Naturalmente il proprietario deve
tenere j ben custodita.
ERREsoft
45