RelCodici_Segreti

PROBLEMA
Come possiamo trasmettere informazioni ed
essere certi che solo persone autorizzate
possano capirle?
ERODOTO V Secolo A.C.
TAVOLETTA DI CERA
Tavoletta di cera
• Demarato per avvertire gli Spartani
dell’arrivo dei Persiani raschiò la cera su
una tavoletta, incise il messaggio sul
legno, rimise la cera e la inviò a Sparta.
Gli Spartani trovarono molte difficoltà a
capire il significato di quella tavoletta
(apparentemente)senza messaggio. Fu
una donna, Gorgo, moglie di Leonida, che
intuì che bisognava raschiare la cera.
Steganografia
• Procedura utilizzata per tenere nascosta
l’esistenza del messaggio (non il suo significato)
• Acrostico: componimento poetico ( o un’altra
espressione linguistica) in cui le lettere o le
sillabe o le parole iniziali di ciascun verso
formano il messaggio
• Aurore invernali
• Immaginate con te
• Umide notti
• Trascorse al buio in attesa di
• Ondate di felicità
MESSAGGIO: AIUTO
•
•
•
•
•
Aurore invernali
Immaginate con te
Umide notti
Trascorse al buio in attesa di
Ondate di felicità
Le Griglie di Cardano
• il matematico Cardano (1501- 1576) ideò
un metodo alquanto originale per l’epoca.
• Consiste nel praticare, in un foglio, dei
buchi delle dimensioni di uno o più
caratteri e fatti in modo irregolari. Chi
riceve possiede una griglia uguale che gli
consente di leggere il messaggio nascosto
nel foglio.
Le griglie di Cardano
• Gli inchiostri invisibili (o inchiostri
simpatici)
• Micropunti fotografici: La tecnica fu
inventata dal direttore dell’ F.B.I. Edgar
Hoover durante la seconda guerra
mondiale. Si tratta di fotografie della
dimensione di un punto dattiloscritto.
• Ingrandite rivelano il messaggio.
Ingrandimento dell’occhio
CRITTOGRAFIA
• nascondere il significato del messaggio.
• Caio Giulio Cesare 100-44 a.C.
Primo esempio di crittografia
• Alfabeto Chiaro
• Alfabeto Cifrato
•
•
•
•
•
•
ABCDEFGHILMNOPQRSTUVZ
DEFGHILMNOPQRSTUVZABC
INVIARE RINFORZI
NQBNDUH UNQIRUFN
INVIARE RINFORZI
Possiamo realizzare 20 alfabeti cifrati.
Con X=n si intende spostare la lettera A al posto n
Es. X=5, A=E, B=F,…
Frase Chiave
• nel mezzo del cammin di nostra
vita
•
•
•
•
nelmzodcaistrv BFGHPQU
abcdefghilmnop QRSTUVZ
INVIARE RINFORZI
ATQANFB FATORFUA
Quanti Alfabeti?
• In quanti modi si possono associare le
lettere?
• 21! Alfabeti diversi cioè
• 51.090.942.171.709.440.000
• Essi sono più di
•
51x1018
A
E
I
O
N
L
R
11.7%
11.7%
11.2%
9.8%
6.8%
6.5%
6.3%
FREQUENZE
T
S
C
D
P
U
M
5.6%
4.9%
4.5%
3.7%
3.1%
3.0%
2.5%
V
2.1%
G
1.6%
H
1.5%
F
0.9%
B
0.8%
Q
0.5%
Z
0.4%
Sistemi Monoalfabetici e
Polialfabetici
• SISTEMA MONOALFABETICO= Si
utilizza un sol alfabeto
• SISTEMA POLIALFABETICO= Si
utilizzano più alfabeti
POLIALFABETICI
• DISCO DI LEON BATTISTA ALBERTI
(1404-1472)
Messaggio da Leon
Riferimento la lettera C
Messaggio:YXHTTETSSRV
Da = CETQ
Leon = DGZNF
• Messaggio da Leon = YXHTTETSSRV
CETQ DGZNF
Cifrario di Vigénère
• Blaise de Vigénère (1523 – 1596)
• Diplomatico, alchimista e crittografo.
• Nel 1586 Perfeziona il Disco ruotante di
Leon Battista Alberti
• ESEMPIO
Parola Chiave o Verme
• Parola chiave (Verme)=ESEMPIO
• Messaggio in Chiaro: Mancano le
munizioni
• esempioesempioesem
• mancanolemunizioni
• QSROPVCPWQGCQNMGRU
• QSR OPV CPW QGC QNM GRU
•
•
•
•
•
QSR OPV CPW QGC QNM GRU
QSROPVCPWQGCQNMGRU
esempioesempioesem
mancanolemunizioni
Mancano le munizioni
Evoluzione:Macchine
Nel 1918 Arthur Scherbius e Richard Ritter
brevettarono una macchina cifratrice
"Enigma "
ENIGMA
La Crittografia nella seconda
guerra mondiale
• Quante vittorie alleate avevano
alla
base
la
superiorità
crittografica?
Battaglia di capo Matapan
 la disfatta della flotta italiana (marzo 1941)
pare abbia avuto origine dal fatto che gli
inglesi
avessero
decrittato
alcuni
messaggi cifrati della marina tedesca che
fornivano l'esatta posizione della flotta
italiana.
Sbarco in Normandia
 Gli Americani erano in grado di leggere i
messaggi degli alti comandi tedeschi,
ebbero così conferma che Hitler aveva
creduto alla falsa notizia di un imminente
sbarco alleato nei pressi di Calais, e aveva
concentrato le sue migliori truppe in quella
zona.
Battaglia delle Midway
• L'ammiraglio Yamamoto, comandante della
flotta giapponese, nel maggio 1942 aveva
preparato un piano per attaccare a sorpresa le
isole Midway a est delle Haway.
Gli Americani intercettarono i piani di Yamamoto
e l'Ammiraglio Nimitz, comandante della flotta
USA, fu in grado di preparare la battaglia
conoscendo già fin nei dettagli i piani del
nemico; fece inoltre trasmettere falsi piani
americani usando un cifrario che sapeva essere
stato forzato dai giapponesi.
Steganografia+Crittografia
• “Mio zio è andato a Zurigo non per incontrare
Silvia e nemmeno la Katia, quindi domani si farà
il solito giretto nel centro storico. Dovrebbe
mandarmi un kimono per sabato, e allora...”,
considerando la prima lettera di una parola no e
una si, nasconde il messaggio incomprensibile,
“zazpsnkdfsnsmksa”, che per mezzo della
sostituzione di Cesare con X=13 (che quindi
sostituisce le ‘a’ in ‘o’, le ‘b’ in ‘p’, le ‘c’ in ‘q’,
ecc...) si trasforma in “nonfidartidicaio”.
Sviluppi ulteriori
• CRITTOLOGIA: Scienza della cifratura dei
messaggi
• Al contrario
• CRITTOANALISI: Scienza
dell’interpretazione ABUSIVA dei
messaggi cifrati
Sistemi crittografici
• Sistemi simmetrici o a chiave privata:
Chiave per criptare coincidente con la
chiave per decriptare.
• Sistemi asimmetrici o a chiave pubblica:
Chiave per criptare diversa dalla chiave
per decriptare.
Sistemi a chiave pubblica:
Il metodo RSA
• Ronald Rivest
Adi Shamir
Len Adleman
Gli ingredienti matematici:
•
•
•
•
Numeri primi
Aritmetica modulare
Invertibilità
Teorema di Fermat
NUMERI PRIMI
• Sia p un intero maggiore di 1 allora:
• P è Primo se e solo se i divisori di P sono
solo 1 e P
• TEOREMA (EUCLIDE): I numeri primi
sono infiniti
Coprimi (Primi tra loro)
MCD(a;b) è il più grande tra i divisori
comuni.
• Coprimi (primi tra loro) se e solo se
MCD(a;b)=1.
• Esempio
• MCD(3;7)=1, MCD(4;15)=1.
Congruenze
• P e Q sono congrui modulo m se il resto
della divisione tra P e m e Q e m è lo
stesso.
• 7 e 12 sono congrui modulo 5 poiché il
resto della divisione con 5 è 2 per
entrambi.
• 6 e 8 non sono congrui modulo 5 poiché il
resto è 1 per il primo e 3 per il secondo
CLASSI DI CONGRUENZA
• Fissato m i resti possibili sono solo
0,1,2,….,m-1
• Un qualsiasi P è congruo ad uno ( e solo
ad uno) dei resti.
• Esempio
• m=3, si ha 0,1,2
m=7, si ha 0,1,2,3,4,5,6
INVERTIBILITA’
• Ricordiamo che due numeri sono uno
l’inverso dell’altro se il loro prodotto è 1.
• Esempio: 2/3 e 3/2.
• Due numeri P e Q sono uno l’inverso
dell’altro modulo m se il loro prodotto è
congruo a 1 modulo m cioè se il loro
prodotto diviso per m dà resto 1
Esempi di numeri invertibili
• Esempio P=7 e Q=4 sono l’uno l’inverso
dell’altro modulo m=9 infatti 7X4=28 e il
resto della divisione tra 28 e 9 è 1.
• Se P=3 allora P non è invertibile
• infatti per nessuno delle classi di
equivalenza modulo 9 (0,1,2,3,4,5,6,7 e 8)
si otterrà resto 1
• Dunque P è invertibile modulo m se e solo
se esiste Q tale che PxQ dà resto 1 nella
divisione con m.
• Se P è invertibile allora il suo inverso Q è
unico
CONDIZIONI PER
L’INVERTIBILITA’
• TEOREMA: fissato m, P è invertibile
rispetto a m se e solo se m e P sono
coprimi.
• Per m=9 allora i numeri invertibili sono
P=1,2,4, 5, 7 e 8.
• Gli inversi sono rispettivamente: 1,5,7,2,4
e 8.
• Non lo sono 3 e 6
COROLLARIO:
• se m è primo allora ogni numero
0,1,2,…,m-1 è invertibile rispetto
am
Operazioni invertibili
• Dati 3 e 2 l’operazione 32 dà un unico
risultato infatti 32=9. Al contrario:
• Dati 3 e 9 l’equazione
•
3X=9
• ha come unico risultato X=2
• 2=log39
• Il Logaritmo e la funzione Esponenziale
sono una l’inversa dell’altra
• 32 modulo 5 ha un unico risultato infatti 32
modulo 5 è uguale a 4 (32 =9 e 9 diviso 5 dà
resto 4). Vale il viceversa, cioè dati 3, 4 e 5
l’equazione
•
3X=4 modulo 5
•
ha come unica soluzione X=2?
• Notiamo che 36=729, quindi 36=4 modulo 5
• Quindi X=2,6,10,….
• LA SOLUZIONE NON E’ UNICA
Teorema (piccolo) di Fermat
• Se p è un numero primo allora, per
qualsiasi X,
•
Xp è congruo a X modulo p
• Corollario: se p e q sono due numeri primi
distinti allora per qualsiasi valore di X e k,
si ha:
• Xk(p-1)(q-1)+1 è congruo a X modulo pq
ESEMPIO
• p=3, q=5.
• Scegliamo X=2 e k=4
• Dobbiamo verificare che Xk(p-1)(q-1)+1 è
congruo a X modulo pq cioè:
• 24(3-1)(5-1)+1 -2 è divisibile per 15.
• Ciò è vero poiché:
• 24(3-1)(5-1)+1 -2=8589934590
• E 8589934590:15=572662306
Metodo RSA
A cripta, B decripta
• B sceglie due numeri primi p e q molto grandi e
calcola m=pq e n=(p-1)(q-1)
• Poi sceglie un intero a piacere minore di n ma
primo con esso, sia esso v e calcola d, inverso
di v modulo n (d esiste poiché v e n sono
coprimi)
• Comunica ad A i numeri m e v che
rappresentano la chiave pubblica (per criptare)
• Tiene segreto d che rappresenta la chiave
privata ( per decriptare)
• Se A vuole criptare il numero X allora
calcola il resto della divisione tra
X
• e m, sia esso Y
v
• Per tornare a X B calcola il resto della
divisione tra
d
• em
Y
•
•
•
•
Infatti Yd = (Xv)d =Xvd
v e d sono uno l’inverso dell’altro modulo
n=(p-1)(q-1) cioè n=k(p-1)(q-1)+1 quindi:
Yd =Xk(p-1)(q-1)+1 e per la conseguenza del
teorema di Fermat =X, dunque
• Yd =Xk(p-1)(q-1)+1 =X
Esempio:
• B: sceglie p=11 e q=13
• calcola m=143, n=(11-1)(13-1)=120
• Sceglie v=7 tale che MCD(7;120)=1 quindi 7 è
invertibile modulo 120.
• calcola d<143 tale che 7d-1 è divisibile per 120
cioè calcola l’inverso di 7 modulo 120. Si ha
d=103.
• Comunica ad A m=143 e v=7 (chiave pubblica)
• A non conosce d=103 (chiave privata)
SICUREZZA DEL METODO
• Un “Intruso” per poter decriptare cioè
risalire al messaggio in chiaro dovrebbe
conoscere l’inverso di 7 modulo 120 e
quindi dovrebbe conoscere p e q, ma
conosce 143=pxq, quindi dovrebbe
riuscire a scomporre 143 il che è
semplicissimo, ma…..
NUMERI PRIMI GRANDISSIMI
• …..se p e q avessero…centinaia di cifre?
• Sarebbe MOLTO IMPROBABLE ( IMPOSSIBILE
da risolvere in tempo reale)
• Per intenderci se perdessimo in una discarica i
numeri p e q sarebbe più facile trovarli
(nell’immondizia) che ricostruirli
• Ultimo numero primo scoperto (2008)
• Le sue cifre sono 12
978 189
Per Criptare
L’utente A vuole criptare il messaggio CIAO.
Utilizza la chiave pubblica : m=143 e v=7
• In codice ASCII C=67, I=73, A=65, O=79
• A calcola il resto della divisione tra 677 e
m=143, ottiene 89
• 737=83, 657=65, 797=40,
• Quindi il messaggio in cifre diventa 89 83
65 40
Quindi il messaggio
•
•
•
•
in chiaro in lettere CIAO
Diventa in cifre 67 73 65 79
Criptato in cifre diventa 89 83 65 40
Criptato in lettere Y S A (
Per Decriptare
• l’utente B (d=103 chiave privata)
• Calcola il resto della divisione tra 89103 e
143 che è 67, 83103 che è 73 e così via,
• Ottiene:
•
67 73 65 79 cioè
•
CIAO
Qualche Osservazione
• 1) Il Metodo RSA trae la sua sicurezza
dalla notevole difficoltà nel fattorizzare
numeri con molte cifre:A non conosce d
poiché non conosce p e q che
rappresentano la fattorizzazione di m
• 2) Richiede,tuttavia, calcoli molto laboriosi
CONCLUDENDO
• Il metodo RSA si usa in genere:
• 1) Per messaggi brevi
• 2) Quando l’invio è unidirezionale cioè uno
codifica e l’altro decodifica
• 3) In combinazione con un sistema
polialfabetico nel senso che si invia la
chiave con il RSA e il messaggio lo si
codifica con il polialfabetico