ERREsoft1 Elementi di crittografia Pierluigi Ridolfi Università di Roma La Sapienza 1 marzo 2000.
-
Upload
tiziano-berti -
Category
Documents
-
view
215 -
download
1
Transcript of ERREsoft1 Elementi di crittografia Pierluigi Ridolfi Università di Roma La Sapienza 1 marzo 2000.
ERREsoft 1
Elementi di crittografia
Pierluigi Ridolfi
Università di Roma La Sapienza
1 marzo 2000
ERREsoft 2
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 3
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 4
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 5
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 6
Schema della scìtala
Un messaggio scritto longitudinalmente diventa illeggibile sulla cinghia svolta
HHHHH
ERREsoft 7
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 8
Concetti fondamentali
• Mittente e destinatari
• Alfabeto
• Messaggio
• Metodi di codifica e decodifica
ERREsoft 9
Alfabeto
Varietà di caratteriEsempio:
– 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 10
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 11
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 12
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 ..
CADE ECFG
chiave = 2
ERREsoft 13
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 14
Corrispondenza indiretta
A B C D E F G H I L Mindice 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 = ABRACADABRAMessaggio = BACCACodifica = I S NRR
ERREsoft 15
Sistemi binari di crittografia
• Somma
• Trasformazione indiretta
• Moltiplicazione
• Potenza
ERREsoft 16
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 17
Trasformazione indiretta (1)
Chiave 1 0 0 1 0 0 1 ...
Matrice 0 1 indice
0 0 1 1 1 0
Messaggio 1 0 1 0 0 0 ...
Codifica 0 0 1 1 0 1 ...
ERREsoft 18
Trasformazione indiretta (2)
Chiave 1 0 0 1 0 0 1 ...
Matrice 0 1 indice
0 0 1 1 1 0
Messaggio 1 0 1 0 0 0 ...
Codifica 0 0 1 1 0 1 ...
ERREsoft 19
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 20
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 21
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 22
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 23
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 24
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 25
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 26
Sistema RSA
• Rivest, Shamir, Adleman.
• MIT, 1977.
• Algoritmo basato sul Teorema di Fermat-Eulero.
ERREsoft 27
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 28
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 29
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 30
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 31
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 11m’ m = 2 = 2048
: 15 resto = 8 = m’
j 3m’’ m’ = 8 = 512
: 15 resto = 2 = m
ERREsoft 32
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 33
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 34
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 35
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 36
Garanzia della riservatezza
A
B
m hB
m'
jB m
ERREsoft 37
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 38
Garanzia dell’autenticità
A
B
m jA
m'
hA m
ERREsoft 39
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 40
Schema del processo di riservatezza e autenticità
A
B
m hB , jA
m'
jB , hA m
ERREsoft 41
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 42
Concetto di impronta
Messaggio m
Impronta r
Algoritmodi hashing
ERREsoft 43
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 44
Garanzia dell’integrità
A
B
m, r jA
hA
m, r’
m, r r
ERREsoft 45
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.