Introduzione Alla Crittografia
Sistemi crittografici
simmetrici e
asimmetrici.
© Gianni Antini, 2000
Crittografia
© Antini Gianni, 2000
Definizioni Generali
Si parla di testo in chiaro (plain-text) riferendosi al
messaggio originale.
Il testo in chiaro viene crittografato mediante l’uso di una
apposita chiave, a questo punto il messaggio prende il nome
di testo cifrato (cipher-text).
La stessa chiave usata per la cifratura viene normalmente
usata per la decifratura del messaggio e si parla di
crittografia simmetrica (o chiave privata). Quando invece la
chiave usata per la decifrazione è diversa da quella usata per
la cifratura si parla di crittografia asimmetrica (o a chiave
pubblica).
La crittografia asimmetrica necessita di complesse tecniche
matematiche ed è stata sviluppata solo recentemente.
Crittografia
© Antini Gianni, 2000
Crittografia Teorica
Nel 1949 C. Shannon pubblica un articolo che da l’inizio a quella
che oggi viene chiamata la Teoria dell’Informazione.
L’unione di questa nuova scienza, della Teoria della Probabilità,
della Teoria della Complessità e della Teoria dei Numeri da vita
alla Crittografia Moderna.
Definizione: Un crittosistema è una quintupla (P,C,K,FC,FD)
dove,
P: insieme finito dei testi in chiaro
C: insieme finito dei testi cifrati
K: insieme delle possibili chiavi
FC: funzione di cifratura (è una FC(k1) con k1∈K)
FD: funzione di decifratura (è una FD(k2) con k2∈K)
Crittografia
© Antini Gianni, 2000
Se k1=k2 si parla di crittosistema simmetrico, altrimenti di
crittosistema asimmetrico
Definizione: Un cifrario si dice perfetto se ∀x*,y* si ha:
P(x=x*)=P(x=x*|y=y*) dove x è chiaro e y è cifrato
In altre parole l’indecisione di sapere il plaintext senza
conoscere il testo cifrato è la stessa che si ha conoscendo il
ciphertest.
I cifrari perfetti sono stati realmente costruiti e sono stati
utilizzati per molti anni per la protezione della hot-line USAURSS durante la guerra fredda.
Crittografia
© Antini Gianni, 2000
A fronte dei cifrari perfetti (o dimostrabilmente sicuri) esistono
anche cifrari:
• Computazionalmente sicuri – La Teoria dell’informazione ci
dice che essi non possono essere sicuri (vedi oltre), ma il
problema crittoanalitico è intrattabile.
• Condizionalemente sicuri – Sono cifrari di cui è stata
dimostrata l’inattaccabilità, a patto che non si verifichino alcuni
eventi probabilistacamente improbabili.
Tutti i cifrari moderni realmente utilizzati appartengono alla
classe dei computazionalmente sicuri.
Alcuni autori hanno creato cifrari condizionalemente sicuri ma
essi sono del tutto inutilizzabili a causa dell’utilizzo di tabelle
casuali (e non pseudocasuali) sterminate (Ueli Mauer – Moon
Cipher).
Crittografia
© Antini Gianni, 2000
Esempio di cifrario perfetto (One-time pad – 1917 Gilbert
Verman AT&T):
1. Si costruisce una grande chiave casuale (e non
pseudocasuale) ad esempio utilizzando un rivelatore di
raggi cosmici.
2. Il cipher text è costruito tramite un ⊕ bit a bit fra il
messaggio in chiaro e la chiave casuale.
3. La chiave NON deve mai essere riutilizzata (one-time
pad).
Come è facilmente immaginabile una spia non ha nessun
appiglio a cui aggrapparsi per crittoanalizzare il
messaggio.
Crittografia
© Antini Gianni, 2000
Teorema: P(X=x|Y=y)=P(X=x)
Dimostrazione:
Siano X e Y di n bit dal T. di Bayes si ha:
P(X=x|Y=y)=P(X=x,Y=y)/P(Y=y)
dove:
P(X=x,Y=y)=P(X=x,k=x⊕y)=P(X=x)P(k=x⊕y)=P(X=x)2-n
mentre:
P(Y=y)=∑xP(X=x,Y=y)=∑xP(X=x)2-n=2-n∑xP(X=x)=2-n
Î
P(X=x|Y=y)=P(X=x)2-n/2-n=P(X=x)
Purtroppo one-time pad è molto scomodo da usare.
Crittografia
© Antini Gianni, 2000
Definizione (Entropia): Sia x una v.a. con distribuzione di
probabilità p1,…,pn si ha:
H(x)=-∑i=1,npiln(pi) [binit]
Definizione (Sicurezza perfetta secondo Shannon): La
sicurezza perfetta equivale a:
H(x)=H(x|y)
Teorema (Shannon): In un sistema crittografico perfetto la
lunghezza della chiave deve essere almeno uguale a quella
del plain text
Il Teorema di Shannon fu una vera e propria mina su ogni
speranza di costruzione di un cifrario perfetto utilizzando una
chiave piccola e quindi maneggevole.
Crittografia
© Antini Gianni, 2000
“Alla ricerca della perfezion perduta”
L’idea che sta alla base di questa classe di cifrari è riassunta
nello schema:
pseudorandom stream
generator
cipher text
key
plain text
Generare sequenze pseudocasuali che abbiano adeguate
probrietà di randomicità è uno dei problemi attuali della
crittografia.
Crittografia
© Antini Gianni, 2000
Generatore pseudocasuale lineare
Il sequenze generatore fornisce sequenze pseudocasuali:
Sn-1
S2
S1
S0
output
αn-1
α1
α2
α0
⊕
I valori di S0, S1,…,Sn rappresentano i bit della chiave che
“innescano” in generatore. Solo la sequenza 00…0 non si può
esare. Si ha:
Sn-1(t+1)=α0S0(t)+α1S1(t)+…+αn-1Sn-1(t)
Crittografia
© Antini Gianni, 2000
Una prima proprietà che deve soddisfare il registro è la
seguente:
Definizione: Il registro si dice a periodo massimo se la
sequenza si ripete dopo 2n-1 cicli.
Se si associa al generatore il suo polinomio caratteristico si ha:
p(x)=α0+α1x+…+αn-1xn-1+xn
dove x è una variabile binaria.
Teorema: Si ha periodo massimo se il polinomio caratteristico è
un polinomio primitivo (o di Marsenne).
Il polinomi di Marsenne sono tabulati, ad esempio si ha:
(a) x17+x12+1
Æ Periodo 13072
(b) x607+x273+1
ÆPeriodo 10183
Il numero di atomi
dell’universo è stimato 1080
Crittografia
© Antini Gianni, 2000
Crittoanalisi
Un sistema di questo tipo è del tutto inadeguato alle esigenze
della crittografia moderna. Supponiamo infatti che la spia
abbia la possibilità di accedere al registro e utilizzi un suo
plain text e valuti il corrispondente cipher text. Si ha:
S0(t+n)=α0S0(t)+α1S0(t+1)+…+αn-1S0(t+n-1) [#]
Se la spia una un certo mi vede come è fatto ci, ma:
So(i)=mi⊕ci
Usando la [#] è possibile scrivere un sistema lineare di n
equazioni in n incognite che può essere facilmente risolto.
La spia ha calcolato la chiave segreta, il cifrario è rotto!
Crittografia
© Antini Gianni, 2000
L’uso di generatori non lineari mette al sicuro da questo tipo di
attacchi. Ad esempio:
R1
R1
Output
R1
R1
Dove R1,…,R4 sono registri lineari.
Tuttavia il background matematico sui registri non lineari (o
caotici) è ancora troppo piccolo per “fidarsi” troppo. La storia
della crittografia suggerisce di procedere con i piedi di
piombo!
Crittografia
© Antini Gianni, 2000
CRITTOSISTEMI SIMMETRICI
Gli utenti che utilizzano tale cifrari devono condividere un
segreto, rappresentato dalla chiave di cifratura / decifratura.
Le lingue scritte sono un esempio di cifrario simmetrico; in
questo caso le persone coinvolte condividono il segreto della
cultura che ha portato a imparare quella certa lingua.
E’ prassi comune che la comunità sappia tutto sul cifrario, in
modo che la sicurezza dipenda SOLO dalla chiave.
In ambiente militare, tuttora, si aggiunge a questa sicurezza la
non diffusione del cifrario.
Crittografia
© Antini Gianni, 2000
Alice e Bob sono diventati e personaggi più famosi in campo
crittografico, Tom è invece la migliore spia del mondo.
Si ha:
Alice
ek(M)
Canale non
sicuro
Bob
dk(M)
Canale sicuro
k
La prima critica che si può fare è questa:
Se Alice e Bob hanno ha disposizione un “canale sicuro” che
bisogno hanno di usare un canale insicuro? La crittografia
asimmetrica è la risposta a questo quesito.
Crittografia
© Antini Gianni, 2000
DES
Il DES è uno standard crittografico del NBS (diventato NIST).
Inventato dall’IBM è stato poi modificato dall’NSA prima di
diventare standard. Questo ha causato molte critiche per il
fatto che le S-Box usate sembrano contenere trap-door che
permettono facilmente all’NSA di forzare qualsiasi
comunicazione. Nessuno tuttora ha dimostrato questa
congettura.
Esso utilizza chiavi a 64 bit, ma 8 di essi non dei pariry bit,
quindi lo spazio delle chiavi ha cardinalità 256.
Il DES è già stato forzato molte volte con attacchi brute force,
ad esempio mediante l’uso di programmi per distribuire in rete
l’enorme calcolo.
Crittografia
© Antini Gianni, 2000
RC5 (Rivest, 1994)
Progettato da Rivest è un © della RSA. E’ un cifrario a blocchi
parametrico in cui si ha:
•
w - Lunghezza della parola, w>0
•
r - Numero di iterazioni, ∈[0,255]
•
t - Lunghezza della chiave, ∈[0,255]
La parte non lineare del cifrario consiste in rotazioni datadepending e non da S-Box (non molto amate da Rivest).
Vengono usate come operazioni fondamentali le seguenti:
•
+
Addizione mod 2w (senza riporto).
•
⊕
XOR bitwise
•
<<<
Rotazione ciclica a sinistra.
Crittografia
© Antini Gianni, 2000
Fase 1- Espansione della chiave:
Viene costruita una tabella di 2(r+1) parole binarie. Nel fare
ciò vengono usate due costanti “magiche”:
Pw=Odd[(e-2)2w]
Qw=Odd[(Φ-1)2w]
dove Odd(x) è l’intero più vicino a x, e è la base dei logaritmi
naturali e Φ è il numero aureo (1+√5)/2=1.6180…
Nota:
•
a Φ sono legati i numeri di Fibonacci.
•
Φ interviene nella Teoria del Caos, dove sembra essere il numero più caotico che
esista.
•
Φ è il rapporto fra la diagonale e il lato del pentagono regolare.
Crittografia
© Antini Gianni, 2000
1. La chiave k[0…b-1] di b byte viene convertita in parole di w
bit Æ L[0…c-1] dove c= 8b/w
2. Esegui la procedura:
for i=b-i downto 0 do L[i/u]=(L[i/u]<<<8)+k[i]
inizializzazione
3. Creazione di una tabella S:
s[0]=Pw
for i=1 to t=2(r+1) do S[i]=S[i-1]+Qw
i=j=A=B=0
per 3*max(t,c) fai
A=S[i]=(S[i]+A+B) <<< 3
espansione
vera e propria
B=L[j]=(L[j]+A+B) <<< (A+B)
i=(i+1) mod t
j=(j+1) mod c
Crittografia
© Antini Gianni, 2000
L’input consiste in due registri A e B di w bit, l’output consiste nei medesimi
due registri.
Cifratura:
A = A+S[0]
B = B+S[1]
for i=1 to r do
A = ( (A⊕B)<<<B ) + S[2*i]
B = ( (B⊕A)<<<A ) + S[2*i+1]
Decifratura:
for i=r downto 1 do
B = ( (B-S[2*i+1]>>>A)⊕A
A = ( (A-S[2*i])>>>B)⊕B
B = B-S[1]
A = A-S[0]
Crittografia
© Antini Gianni, 2000
BlowFish (Bruce Schneier, 1994)
Il cifrario consiste in una Feistel Network che itera una
funzione di codifica 16 volte. Il blocco è di 64 bit e la chiave
può arrivare a 448 bit.
Si hanno due fasi:
1-
Espansione della chiave:
Si passa da 448 bit a 4168 bit. Una particolarità di
questo algoritmo è che l’espansione è effettuata
usando BlowFish stesso.
2-
Codifica vera e propria.
Crittografia
© Antini Gianni, 2000
Codifica. Può essere schematizzata da:
Plain Text
Funzione F
64
P1
Addizione mod 232
32
F
S1
32
8
S2
32
8
S3
32
S4
32
8
P2
32
F
32
8
32
P16
32
P18
F
32
P17
64
Cipher Text
+
+
32
Le S-Box sono composte
Da 256 parole di 32 bit ciascuna
Crittografia
© Antini Gianni, 2000
Decodifica: La fase di decodifica è identica a quella di
codifica, eccetto che per l’uso inverso delle sottochiavi.
Espansione della chiave: Viene fatta utilizzando l’algoritmo
BlowFish stesso, opportunamente inizializzato.
1. P1=0x243f6a88 P2=0x85a308d3 P3=0x13198a2e P4=0x03707344 e così
via per tutti i Pi e tutte le entrate delle S-Box. Schneier non vincola ad usare
necessariamente le cifre di π (come in questo caso) ma consiglia di usare una
stringa costante indipendente da BlowFish e possibilmente calcolabile “in
loco”.
2. Fare lo xor fra i primi 32 bit della chiave k e P1, i secondi 32 bit con P2, …
continuare, eventualmente fino a P14. Ripetere il passo 2 con i restanti Pi.
3. Codificare 64 “0” con BlowFish e gli attuali Pi e Sj.
4. Sostituire P1 e P2 con l’output di BlowFish del passo 3.
5. Codificare l’output del passo 3 con BlowFish.
6. Sostituire P3 e P4 con l’output di BlowFish del passo 5.
7. Continuare fino alla modifica di tutti i Pi e di tutte le S-Box.
Crittografia
© Antini Gianni, 2000
Schneier consiglia i crittoanalisti di utilizzare versioni ridotte di
BlowFish, ad esempio con meno round, al fine di valutarne
l’affidabilità crittografica.
La CounterPane (società di Schneier) e Dr. Jobbs hanno
offerto diverse migliaia di dollari a chi rompe BlowFish. Tuttora
nessuno è stato in grado di forzare versioni con più di 3 round.
Crittografia
© Antini Gianni, 2000
AES
Il NIST ha dichiarato che lo standard DES (anche nella
versione Triple-DES) non potrà più essere rinnovato dopo
il Dicembre 1998. A tale scopo è stato istituito un concorso
internazionale con lo scopo di trovare un nuovo algoritmo
non coperto da copyright che dovrà diventare il nuovo
standard.
Anche al fine di non suscitare sospetti la NSA non è stata
coinvolta nel concorso e tutte le valutazioni sono “alla luce
del sole”.
www.nist.gov/aes
Il NIST è stato molto esigente riguardo i requisiti di
candidatura. Fra di essi troviamo:
Crittografia
© Antini Gianni, 2000
1. L’algoritmo deve essere di tipo Block-cipher.
2. L’algoritmo deve implementare un cifrario a chiave
simmetrica
3. La chiave deve essere compresa fra 128 e 256 bit.
4. Deve essere possibile l’implementazione su smart card
(quindi deve accedere a risorse di calcolo limitate).
Molti fra i più grandi esperti mondiali si sono cimentati nella
sfida, ma solo 15 algoritmi sono stati accettati per il 1°
Round di prove. Fra di essi sono usciti i seguenti finalisti.
MARS
IBM
RIJNDAEL
J. Daemen, V. Rijmen
RC6
Rivest – RSA Laboratories
SERPENT
R. Anderson, E. Biham, L. Knudsen
TwoFish
B. Schneier e altri.
Crittografia
© Antini Gianni, 2000
Crittografia ASIMMETRICA
Whitfield Diffie e Martin Hellman nel 1976 introdussero un
nuovo concetto di crittografia in un articolo che è diventato
storico. Praticamente la loro intuizione andavo contro tutti i
canoni della crittografia stessa: cifrare con una chiave
conosciuta da tutti. La loro idea si basava sulle funzioni oneway trapdoor.
Crittografia
© Antini Gianni, 2000
Definizione: Una funzione f si dice one-way se
∀x il calcolo computazionale di y=f(x) è
semplice (∈P) mentre il calcolo di x=f-1(y) è
computazionalmente difficile (∈NP).
Definizione: Una funzione one-way è detta
trapdoor se il calcolo x=f-1(y) può essere reso
facile qualora si conoscano informazioni
aggiuntive (private).
Crittografia
© Antini Gianni, 2000
Formalmente in un sistema crittografico a chiave pubblica è
composto da due chiavi, una pubblica, nota a chiunque e una
privata, nota solo al suo possessore. In tal modo la fase di
cifratura avviene utilizzando la chiave pubblica mentre la
decifratura avviene utilizzando la chiave privata.
Se un sistema critt. Asimmetrico soddisfa la seguente
proprietà:
dk(ek(M))=M
Si dice sicuro mentre se soddisfa la seguente:
ek(dk(M))=M
Si dice che garantisce autenticità.
Crittografia
© Antini Gianni, 2000
Sicurezza: Alice vuole comunicare con Bob in modo sicuro.
1. Alice ottiene la chiave pubblica di Bob, ad esempio su
appositi server container.
2. Alice calcola il cipher text y=ekBob(M) e lo spedisce a Bob.
3. Bob legge il messaggio di Alice calcolando M=dkBob(y).
4. Nel caso in cui Tom sia in ascolto non ha alcun modo di
decifrare il messaggio y, in quanto per farlo dovrebbe
avere accesso a dkBob(), che però è privata e quindi non
transita sulla rete.
Crittografia
© Antini Gianni, 2000
Autenticità: Alice vuole spedire un messaggio M a Bob in
modo che Bob sia sicuro che lo abbia spedito Alice.
1. Alice calcola la firma digitale del messaggio M usando una
hash-funcion, H=h(M).
2. Alice calcola F=dkAlice(H) e spedisce a Bob la coppia (F,M)
3. Bob legge il messaggio M, calcola il suo digest H*=h(M).
4. Bob verifica che il messaggio sia stato spedito
effettivamente da Alice verificando che ekAlice(H*)=F. Se la
verifica ha successo Bob è sicuro che il messaggio sia
stato spedito da Alice in quanto nessun altro avrebbe
potuto calcolare F.
Naturalmente è possibile unire sicurezza ad autenticità. Lo
schema che segue chiarisce meglio questo fatto.
Crittografia
© Antini Gianni, 2000
Chiave pubblica
Messaggio falso
(non di Alice)
Chiave privata
No
Alice
M
Bob
ekBob(M)
HF
Alice
Alice
Yes
F
ekBob(M)
F
=
Bob
HF
M
Bob
Messaggio
di Alice
Crittografia
© Antini Gianni, 2000
Nonostante l’intuizione di Diffie e Helman, tutti i loro sforzi per
cercare una funzione one-way trapdoor furono vani. Furono
infatti tre ricercatori del MIT a trovarne una.
Di essi uno era un matematico puro (Adlemann), laureato
sulla Teoria dei Numeri, l’altro un crittoanalista (Shamir) e
infine un algoritmico (Rivest) dalla mente veramente feconda.
Rivest sfornava quasi quotidianamente funzioni candidate, ma
puntualmente Adlemann e Shamir trovavano pecche che le
rendevano inutilizzabili. Infine un notte del 1977 Rivest pensò
ad una funzione in cui Adlemann e Shamir non trovarono
nessun difetto.
Era nato il cifrario RSA. Era nata la crittografia a chiave
pubblica moderna.
Crittografia
© Antini Gianni, 2000
Il cifrario RSA (1977)
Progettato da Ron Rivest, Adi Shanir e Leonard Adlemann il
cifrario è stato brevettato e quindi non può essere utilizzato
senza il permesso della RSA inc.
Idea base: Dati due numeri primi p e q (molto grandi) p facile
calcolare il prodotto n=pq, mentre è molto difficile calcolare la
fattorizzazione di n (NP). Per avere sicurezza occorre che p e
q siano almeno di 200 cifre decimali.
I migliori algoritmi di fattorizzazione attualmente disponibili
(Quadratic Sieve, Elliptic Curve Method, Euristica ρ di Pollard,
ecc.) hanno tutti una complessità dell’ordine di:
(
Oe
ln( n ) ln(ln( n ))
)
Crittografia
© Antini Gianni, 2000
Se p e q sono di 200 cifre decimali ciascuno allora n=pq è di
400 digit, cioè dell’ordine di 10400, da cui:
O(.)=e79=1034
Da cui l’intrattabilità.
Algoritmo (RSA):
1.
Calcola due primi grandi p e q e quindi n=pq.
2.
Calcola la funzione toziente di Eulero ϕ(n)=(p-1)(q-1)
3.
Scegli un numero 0<e<ϕ(n) t.c. MCD(e,ϕ(n))=1, ed esempio prendi e primo
come il 4° numero di Fermat (e=10001)
4.
Calcola d t.c. ed=1 mod ϕ(n) Ù d=e-1 mod ϕ(n).
5.
Definisci la chiave pubblica come (e,n).
6.
Definisci la chiave privata come (d,n).
7.
La funzione di cifratura è ek(x)=xe mod n.
8.
La funzione di decifratura è dk(x)=yd mod n.
Crittografia
© Antini Gianni, 2000
Fatti (Correttezza di RSA):
• Un Teorema di Teoria dei Numeri assicura che le
congruenze della forma x=y-1 mod ϕ(n) hanno un’unica
soluzione quindi ∃! d t.c. ed=1 mod ϕ(n).
• Occorre provare che dk(ek(M))=M:
dk(ek(M))=(Me)d mod n = Med mod n = M mod n = M
Si noti che RSA gode della notevole proprietà:
dk(ek(M))=ek(dk(M))
E quindi può essere usato come sistema che garantisce
sicurezza ed autenticità.
Crittografia
© Antini Gianni, 2000
RSA è particolarmente lento (circa 6000 volte rispetto a
BlowFish) quindi viene usato in un modo particolare.
M
Cifrario
Simmetrico
Ck(M)
Output
(Ck(M), eBob(k))
eBob(k)
Chiave di cifratura
k
Generatore di
numeri casuali
RSA
Chiave pubblica
di Bob
Praticamente RSA critta solamente la chiave di cifratura
utilizzata dal cifrario simmetrico. Tale chiave viene generata in
modo random OGNI volta che si cifra un messaggio.
Crittografia
© Antini Gianni, 2000
Come trova numeri primi grandi
Un problema relativamente facile è quello di trovare numeri
primi molto grandi, come richiesto da RSA.
I test di primalità utilizzati sono tutti di tipo probabilistico in
quanto quelli deterministici sono troppo lenti.
Definizione (Alg. Monte Carlo): Un alg. Monte Carlo “yesbiased” è un alg. Probabilistico per un problema di decisione
in cui la risposta “si” è sempre corretta mentre la risposta “no”
può essere inesatta con probabilità fissata ε. Analogamente
sono definiti gli algortmi Monte Carlo “no-biased”.
Sia A un alg. Monte Carlo “no-biased” con ε=1/2 e sia x un numero candidato.
Quello che si fa è eseguire A(x) n volte. Se l’algoritmo risponde “no” anche una
sola volta il numero è sicuramente composto, mentre se risponde sempre “si”, la
probabilità che il numero sia primo è:
P=1-2-n
Se n=100 si ha P=1-8•10-31.
Crittografia
© Antini Gianni, 2000
Algoritmo di Miller-Rabin
E’ l’algoritmo probabilistico di test di primalità migliore finora
conosciuto. Esso ha una complessità si O(log n)3.
Miller-Rabin(n,t) // t=parametro di sicurezza.
1.
Set n-1=2sr con r dispari
2.
For i=1 to t do
2.1 scegli a caso a t.c. 2≤a≤n-2
2.2 calcola y=ar mod n
2.3 if y≠1 and y≠n-1 esegui
2.3.1 j=1
2.3.2 while ( (j≤s-1) and (y≠n-1) )
y=y2 mod n
se y=1 ritorna “composito”
j++
se y≠n-1 ritorna “composito”
3. Ritorna “PRIMO”
Crittografia
© Antini Gianni, 2000
E’ facile trovare numeri primi?
Nonostante l’efficienza nel testare se un numero sia primo o
meno resta l’incognita che i numeri primi siano “pochi” e
quindi difficili da scovare.
Teorema (dei numeri primi):
Sia π(n) la funzione di distribuzione dei numeri primi, cioè il
numero di numeri primi che precedono n. Allora essa soddisfa
il seguente:
π ( n)
=1
lim
n →∞ n
ln n
Quindi se si cerca un numero primo di 100 cifre occorre
verificare “solo” ln(10100)=230 numeri consecutivi.
Crittografia
© Antini Gianni, 2000
Scambio di chiavi di DIFFIE-HELLMAN
Qualora due utenti di una rete necessitino di un modo sicuro
per scambiarsi una chiave privata di cifratura, possono
usare il protocollo di Diffie-Hellman.
Vengono stabiliti, per tutti, i numeri n e g tali che 1<g<n.
1.
Alice sceglie un grande numero x e calcola:
X = gx mod n
2.
Bob sceglie un grande numero y e calcola:
Y = gy mod n
•
Alice spedisce a Bob X, mentre Bob spedisce ad Alice Y.
•
Alice calcola K = Yx mod n = (gy)x mod n = gxy mod n
•
Bob calcola K’ = Xy mod n = (gx)y mod n = gxy mod n
•
Se tutto è andato bene K=K’. Questa chiave K può essere usata in uno
schema di cifratura simmetrico.
Crittografia
© Antini Gianni, 2000
Sicurezza dello schema di Diffie-Hellman
• Se Tom è in ascolto non vede mai transitare la chiave di
cifratura K. L’unico modo che ha di calcolarla è conoscere o x
o y che però vengono tenute segrete.
• In via teorica è possibile calcolare x da X, come x=loggX e
y=loggY. Tuttavia questo calcolo è computazionalmente
intrattabile sui campi finiti.
• La scelta di n e di g è abbastanza delicata. Infatti nonostante
il calcolo di un logaritmo discreto sia difficile nel caso generale
nessuno ci assicura che non esistano classi in cui tale calcolo
diventa polinomiale. Tali classi sono state trovate anche dove
non ce ne dovrebbe essere. Il calcolo rimane difficile se:
n deve essere un numero primo (di almeno 1024 bits), così come (n-1)/2.
g deve essere una radice primitiva modulo n.
Crittografia
© Antini Gianni, 2000
Diffie-Hellman di conferenza
Lo schema di Diffie-Hellman può essere esteso per
permettere a più utenti di condividere una stessa chiave di
cifratura. Facciamo un esempio con tre persone:
1.
Alice sceglie un grande x e calcola: X = gx mod n
2.
Bob sceglie un grande y e calcola: Y = gy mod n
3.
Carol sceglie un grande z e calcola: Z = gz mod n
4.
Alice spedisce X a Bob, Bob spedisce Y a Carol, Carol spedisce Z a Alice.
5.
Alice calcola Z’=Zx mod n, Bob calcola X’=Xy mod n,Carol calcola Y’=Yz mod n
6.
Alice spedisce Y’ a Bob, Bob spedisce X’ a Carol e Carol spedisce Y’ a Alice
7.
Alice calcola k = Y’x mod n
8.
Bob calcola k = Z’y mod n
9.
Carol calcola k = X’z mod n
10. La chiave k può essere usata fra Alice, Bob e Carol come chiave di
cifratura/decifratura in un crittosistema simmetrico.
Crittografia
© Antini Gianni, 2000
Crittosistema di ElGamal
Può essere considerato una variante di Diffie-Hellman ed è
tutt’oggi molto utilizzato; ad esempio le ultime versioni di PGP
usano questo schema.
E’ stato dimostrato formalmente che la rottura di ElGamal
equivale alla rottura di Diffie-Hellman, in quanto si basa sulla
difficoltà di calcolo del logaritmo discreto su campi finiti.
In aggiunta a Diffie-Hellman, lo schema di ElGamal può
essere utilizzato anche per la cifratura/decifratura e per
garantire autenticità.
Crittografia
© Antini Gianni, 2000
Creazione delle chiavi. Ogni utente del sistema deve:
1. Genera un numero primo molto grande p e un
generatore α del campo finito moltiplicativo Zp*.
2. Scegli un numero casuale a, con 1≤a≤p-2 e calcola
αa mod p
3. La chiave pubblica è la tripla (p,α,αa), la chiave privata
è a.
Si noti che se i valori p e α sono comuni e fissati per gli utenti,
la chiave privata diventa più maneggevole, essendo
composta dal solo αa.
Crittografia
© Antini Gianni, 2000
Nota (sui gruppi finiti moltiplicativi):
Un gruppo (S,⊕) è un insieme S con un operazione binaria ⊕,
definita su S che ha le seguenti proprietà:
1. Chiusura: ∀a,b∈S si ha a⊕b∈S.
2. Identità: ∃e∈S t.c. e⊕a=a⊕e=a ∀a∈S.
3. Associatività: ∀a,b,c∈S si ha (a⊕b)⊕c=a⊕(b⊕c)
4. Reciproco o opposto: ∀a∈S ∃! b∈S t.c. a⊕b=b⊕a=e
Se vale anche la proprietà commutativa il gruppo si dice
abeliano.
Teorema: Il gruppo finito (Zp,.) o Zp* è un gruppo abeliano.
I gruppi finiti Zp* in cui p è primo sono detti anche gruppi di
Galois e sono importantissimi in crittografia.
Crittografia
© Antini Gianni, 2000
Un generatore (o elemento primitivo) α per il gruppo di Galois
Zp* è un numero ∈Zp* t.c. applicando ricorsivamente
l’operazione di moltiplicazione (mod p) si ottengono tutti gli
elementi del campo.
In altre parole per un generatore α accade:
<α>={αk mod p , k>0}=Zp*
Teorema 1: Un campo Zn* ammette generatori sse n=2, 4, pk,
2pk dove p è primo ≥1.
Si noti che i campi di Galois ammettono generatori.
Teorema 2: Sia α un genratore di Zn*. Allora b=αi mod n è
ancora un generatore sse MCD(i,ϕ(i))=1. Inoltre in numero di
generatori è ϕ(ϕ(i)).
Esistono efficienti algoritmi per il calcolo dei generatori di Zp*.
Crittografia
© Antini Gianni, 2000
Cifratura:
1. Trasforma il messaggio M come un numero da 0 a p-1
2. Genera un numero casuale k t.c. 1≤k≤p-2
3. Calcola x=αk mod p e y=M(αa)k mod p
4. Spedisci il testo cifrato (x,y).
Decifratura:
1. Usa la chiave privata “a” per calcolare xp-1-a=x-a=α-ak
2. Ricostruisci il messaggio M tramite il calcolo (x-a)y mod p,
infatti (x-a)y=α-akMα-ak=M.
Si noti che un evidente difetto dello schema di ElGamal è il
raddoppio del ciphertext rispetto al plaintext.
Crittografia
© Antini Gianni, 2000
Esempio: p=2357 α=2 a=1751.
αa mod p = 21751 mop 2357 = 1185
La chiave pubblica è (2357,2,1185)
Sia M=2035 il messaggio e k=1520 il numero casuale, si ha:
x=21520 mod 2357 = 1430, y=2035 11851520 mod 2357=697
Il messaggio spedito è quindi (1430,697).
Per ricostruire il messaggio originale si calcola:
xp-1-a=1430605 mod 2357 = 872
M=872 697 mod 2357 = 2035.
Crittografia
© Antini Gianni, 2000
Crittografia PROBABILISTICA (Cenni)
Dovuta a Silvio Micali e Shafi Goldwasser (entrambi del MIT),
la crittografia probabilistica è uno dei campi attuali di ricerca.
La definizione di sicurezza alla Shannon è troppo stringente,
infatti essa presuppone che l’avversario non sia in grado di
trarre informazioni sul plaintext, dato il ciphertext, avendo a
disposizione una macchina infinita. Come primo corollario di
ciò si ha che la lunghezza della chiave deve essere almeno
quella del plaintext.
La crittografia probabilistica introduce nuovi concetti di
sicurezza.
Crittografia
© Antini Gianni, 2000
Definizione: Un crittosistema a chiave pubblica si dice
polinomialmente sicuro se dati due plaintext m1 e m2 ed i
rispettivi ciphertext c(m1) e c(m2), non è possibile distinguere,
in tempo polinomiale:
m1
m2
?
C(m)1
C(m)2
con probabilità maggiore di ½.
Intuitivamente il ciphertext non fornisce nessuna informazione
parziale sul plaintext se si fanno calcoli polinomiali. In altre
parole è una riformulazione polinomiale della sicurezza alla
Shannon.
Nota: Tutti i calcolatori moderni lavorano in tempo
polinomiale. Anche i calcolatori paralleli non possono essere
assimilati ad una macchina di Turing non deterministica.
Crittografia
© Antini Gianni, 2000
I due migliori algoritmi di crittografia probabilistica sono:
ÎAlgoritmo di Goldwasser-Micali, basato sull’intrattabilità dei
residui quadratici.
ÎAlgoritmo di Blum-Goldwasser, basato sull’intrattabilità della
fattorizzazione. Esso utilizza, fra l’altro, il generatore di bit
pseudocasuali Blum-Blum-Shub, considerato il migliore per
ora conosciuto, i cui bit vengono messi a ⊕ con i bit del
plaintext.
Maggiori dettagli possono essere trovati in:
ÆHandbook of Applied Cryptography – A. Menezes, P. van
Oorschot, S. Vanstone.
ÆArticoli originali degli autori.
Funzioni HASH
Teoria e utilizzo nei
sistemi crittografici
© Gianni Antini, 2000
Hash Funcion
© Antini Gianni, 2000
Definizioni Generali
h
X
Z
Una funzione Hash h calcola il valore z=h(x) per x in X. Di
solito card(X)>>card(Z), ad esempio si ha X a 1024 bit
e Z a 128 bit. Il valore z=h(x) prende il nome di digest.
Addirittura l’insieme X può essere un intero file di cui
viene calcolato il digest. In tal caso quindi si ha una
card(X)=8*file_length.
2
Hash Funcion
© Antini Gianni, 2000
Def. Dati due x e x’ t.c. x≠x’. Se h(x)=h(x’) si dice che la
coppia (x,x’) è una collisione per h.
Def. (Sicurezza debole): h è debolmente priva di collisioni
se, dato un messaggio x, è computazionalmente
inammissibile trovare un x’ t.c. x≠x’ e h(x)=h( x’).
Def. (Sicurezza forte): h è fortemente sicura se è
computazionalmente inammissibile trovare due x e x’
t.c. x≠x’ e h(x)=h( x’).
Def. (One-way): h è one-way se, dato un digest z e’
computazionalmente inammissibile trovare x t.c.
z=h(x).
3
Hash Funcion
Teorema:
Sicurezza forte
© Antini Gianni, 2000
Î one-way
Î Sicurezza debole
Nonostante il background matematico sulle funzioni hash,
è molto difficile dimostrare analiticamente che una data
funzione h() soddisfi le proprietà enunciate. Quello che
accade è che una funzione hash è considerata sicura
finché qualcuno non trova un meccanismo per
produrre collisioni (MD4).
La scelta della cardinalità dell’insieme Z è un fattore
molto importante nella progettazione di una funzione
hash. Infatti se essa è troppo piccola si corre il pericolo
di cadere vittime dell’attacco del compleanno.
Viceversa una cardinalità grande può rendere vana la
motivazione per cui è stata costruita la funzione hash.
4
Hash Funcion
© Antini Gianni, 2000
Attacco del compleanno
Sia h:XÆZ e sia |X|=m, |Z|=n. Si fa l’ipotesi che |X|≥2|Z|.
Si noti che questa ipotesi non è affatto restrittiva, infatti
basta che il digest sia più piccolo di almeno un bit
rispetto a |X|.
Si scelgono a caso k elementi di X e vi valuta la
probabilità di avere collisioni.
z1 : arbitraria
z2 : P(z2≠z1)=1-P(z2=z1)1-1/n
z3 : P(z3≠z2, z3≠z1 | z1≠z2)=…=1-2/n
:
:
5
Hash Funcion
© Antini Gianni, 2000
P(non avere collisioni) =
k −1
i
−
(
1
)
∏
k
i =1
Tenendo conto che e-x≈1-x (Taylor) si ha:
k −1
= ∏e
i
−
n
=e
−
1
n
k −1
∏i
i =1
=e
−
k ( k −1)
2n
i =1
Da cui:
k ( k −1)
−
P(avere almeno 1 collisione)=ε= 1-e 2 n
 1 
≈
Î k

2n ln
1− ε 
6
Hash Funcion
© Antini Gianni, 2000
Nel paradosso del compleanno si ha:
ε=0.5 n=365 k=22.3
da cui la formulazione.
Esempio:
Sia |Z|=240, ε=0.5. Sia ha k≈1.000.000
Æ Si ha probabilità ½ di trovare almeno una
collisione scegliendo 106 valori casuali (limite
computazionale facilmente raggiungibile).
Sia |Z|=2128, ε=0.5. Sia ha k≈2 1019 da cui la
sicurezza computazionale.
7
Hash Funcion
© Antini Gianni, 2000
Si noti che la sicurezza computazionale menzionata non
implica che non sia possibile trovare usa strategia per
provocare facilmente collisioni. Ad esempio:
Hans Dobbertin – MD4 is not collision free
1995
Ha mostrato una ingegnosa tecnica che, di fatto, ha rotto
tale funzione.
Rivest, il progettista di MD4, intravedendone
la debolezza aveva già pubblicato una nuova
hash-function, chiamata MD5,
computazionalmente molto più sicura.
8
Ron Rivest - MIT
Hash Funcion
© Antini Gianni, 2000
SHS
(Secure Hash Standard)
Nel 1992 il NIST (Nation Institute of Standard
and Tecnology) ha introdotto una nuova
funzione hash chiamata SHS/0,
successivamente modificata, nel 1994, con il
nome di SHS/1.
Si tratta di una hash-function standardizzata e
libera (non protetta da copyright).
9
Hash Funcion
© Antini Gianni, 2000
La principali caratteristiche sono:
–
–
–
–
Progettata per architetture Big-Endian (vedi
processori SPARC).
Produce un digest di 160 bit.
Lavora su blocchi di 512 bit.
Nonostante sia più lenta di MD5, essa viene
considerata più sicura.
Il modello di lavoro su blocchi di 512 bit (introdotto da
Rivest) è diventato una consuetudine per quasi tutte
le hash-function.
10
Hash Funcion
© Antini Gianni, 2000
1 0 0
Messaggio x
………
0
64 bit = |x|
|M| = 0 mod 512 [1]
Si crea un buffer in cui si mette il messaggio di cui si vuole
calcolare il digest, quindi un singolo 1. Seguono un numero
di zeri tali che l’equazione [1] sia soddisfatta. Per finire
vengono accodati 64 bit rappresentativi della lunghezza del
messaggio x. Se |x|>264 vengono considerati i primi 264 bit.
Il blocco M viene diviso in sottoblocchi di 512 bit ciascuno.
Ognuno di questi sottoblocchi viene elaborato
separatamente.
11
Hash Funcion
© Antini Gianni, 2000
Elaborazioni di un singolo sottoblocco (SHS/0)
Il sottoblocco viene suddiviso in 16 word da 32 bit.
(2) Queste 16 word sono le prime di un array x di 80
word da 32 bit ciascuna.
(3) Si ha una espansione da 16 a 80 word, tramite la
seguente procedura:
for k=16 to 79
x[k]=x[k-3] ⊕ x[k-8] ⊕ x[k-14] ⊕ x[k-16]
(4) Inizializza 5 word H0, H1, H2, H3, H4 e H5 tramite le
seguenti costanti:
H0=0x67452301 H1=0xefcdab89 H2=0x98badcfe
H3=0x10325476 H4=0xcbd2e1f0
Si noti che l’inizializzazione viene fatta solo per il
primo sottoblocco, per gli altri vengono utilizzati gli
Hi in uscita.
(1)
12
Hash Funcion
© Antini Gianni, 2000
(5) Esegui:
A=H0, B=H1, C=H2, D=H3, E=H4, F=H5
for t=0 to 79
temp = (A <<5)+ft(B,C,D)+E+x[t]+kt
E=D, D=C, C=B<<30, B=A, A=temp
H0=H0+A, H1=H1+B, H2=H2+C, H3=H3+D
H4=H4+E, H5=H5+F
(6) Finito l’ultimo sottoblocco, il valore a 160 bit:
H0H1H2H3H4H5
è il digest.
13
Hash Funcion
© Antini Gianni, 2000
Le funzioni citate sono:
ft(B,C,D) =
kt =
14
(B & C) | (!B) & D)
B^C^D
(B & C) | (B & D) | (C & D)
B^C^D
0x5a827999
0x6ed9eba1
0x8f1bbcdc
0xca62c1d6
0≤t≤19
20≤t≤39
40≤t≤59
69≤t≤79
0≤t≤19
20≤t≤39
40≤t≤59
69≤t≤79
Hash Funcion
© Antini Gianni, 2000
SHS/1
Nel 1994 il NIST ha attuato una modifica dello
standard, facendo proprie varie segnalazioni
apportate dai crittoanalisti e dall’NSA.
Fu modificata la fase di espansione del sottoblocco,
Introducendo una rotazione circolare a sinistra,
praticamente:
for k=16 to 79
x[k]=( x[k-3] ⊕ x[k-8] ⊕ x[k-14] ⊕ x[k-16] ) <<< 1
Nota: Nei linguaggi (Java), o processori (smart card),
in cui non esiste tale operazione è possibile
sostituirla da:
(x<<<n) Ù (x<<n)|(x>>32-n)
15
Shift semplice
Rotazione
Hash Funcion
© Antini Gianni, 2000
TIGER
Progettata da Ross Anderson e Eli Biham, Tiger è una
hash-function ottimizzata per i processori di nuova
generazione (64 bit), ma discretamente veloce
anche su processori da 32 e 16 bit.
Anderson e Biham sostengono che le hash-function
MD5-type, fra cui anche SHS, mal si adattano ai
nuovi processori. Inoltre, essendo tutte strutturate in
maniera analoga, non dovrebbe mancare molto alla
loro crittoanalisi definitiva utilizzando, ad esempio,
attacchi Dobbertin-Type. A sostegno di ciò, c’è da
dire che alcuni autori hanno crittoanalizzato MD5
con meno round.
16
Hash Funcion
© Antini Gianni, 2000
La principali caratteristiche sono:
–
–
–
–
Progettata per architetture Little-Endian (vedi DEC
ALPHA) a 64 bit.
Produce un digest di 192 bit in modo da essere
considerata sicura verso gli attacchi del compleanno
ancora per molti anni.
Lavora su blocchi di 512 bit in modo analogo a
SHS.
Vengono utilizzate 4 S-Box di espansione altamente
non lineari e sicuramente prive di trapdoor, in
quanto viene fornito l’algoritmo per calcolarle*.
(*) Critiche al DES.
17
Hash Funcion
© Antini Gianni, 2000
La struttura del blocco è la stessa di SHS, ma è più comodo
vedere il buffer come da destra a sinistra*.
0
………
0 0 1
64 bit = |x|
Messaggio x
|M| = 0 mod 512
(*) Questo risolve un problema implementativo che ho incontrato.
Dato che normalmente si lavora con i byte, quando si
introduce il singolo “1”, occorre fare un append del valore
0x01, mentre in SHS del valore 0x80.
18
Hash Funcion
© Antini Gianni, 2000
Dato che la hash-function è ottimizzata per processori
a 64 bit, tutti i risultati parziali sono di questa
lunghezza. Questo può provocare inefficienze nei
linguaggi privi di dati predefiniti a 64 bit. In Java si
usano i “long”.
Tiger esegue le seguenti istruzioni per ogni blocco di
512 bit (8 word).
i.
Inizializza:
a = 0x0123456789abcdef
b = 0xfedcba9876543210
c = 0xf096a5b4c3b2e187
ii.
Suddividi il blocco in 8 word da 64 bit ciascuna:
x[i] per i=0,…,7 (ricordarsi dell’architettura LE)
19
Hash Funcion
iii.
© Antini Gianni, 2000
Esegui quindi
save(a,b,c)
pass(a,b,c,5)
key_schedule
pass(c,a,b,7)
key_schedule
pass(b,c,a,9)
feed_forward
dove:
Æ save(a,b,c)
aa=a, bb=b, cc=c
20
Hash Funcion
© Antini Gianni, 2000
Æ pass(a,b,c,mul)
round(a,b,c,x[0],mul)
round(b,c,a,x[1],mul)
round(c,a,b,x[2],mul)
round(a,b,c,x[3],mul)
round(b,c,a,x[1],mul)
round(c,a,b,x[2],mul)
round(a,b,c,x[0],mul)
round(b,c,a,x[1],mul)
Æ round(a,b,c,x,mul)
c^=x
a-=t1[c_0]^ t2[c_2]^ t3[c_4]^ t4[c_6]
b-=t4[c_1]^ t5[c_3]^ t2[c_5]^ t1[c_7]
b*=mul
C_i è l’i-esimo byte di c (sono 8 i byte di c)
21
Hash Funcion
© Antini Gianni, 2000
key_schedule
x[0]-=x[7]^0xa5a5a5a5a5a5a5a5
x[1]^=x[0]
x[2]+=x[1]
x[3]-=x[2]^( !x[1] << 19 ) x[4]^=x[3]
x[5]+=x[4]
x[6]-=x[5]^( !x[4] >>23 )
x[7]^=x[6]
x[0]+=x[7]
x[1]-=x[0]^( !x[7] << 19 ) x[2]^=x[1]
x[3]+=x[2]
x[4]-=x[3]^( !x[2] >>23 )
x[5]^=x[4]
x[6]+=x[5]
x[7]-=x[6]^0x0123456789abcdef
feed_forward
a^=aa
22
b-=bb
c+=cc
Hash Funcion
© Antini Gianni, 2000
A questo punto se ci sono altri 512 bit da trattare si
riesegue l’algoritmo (senza inizializzazione delle
variabili) altrimenti il digest è formato dalla
giustapposizione di:
a||b||c
Nota:
Nel passo round() vengono utilizzate le 4 S-Box, t1,
t2, t3 e t4. Esse sono 4 tabelle di 256 long ognuna:
0
1
2
:
:
Il byte c_i viene usato per selezionare
la riga della tabella. Il valore di uscita
è la word di 64 bit contenuta nella
cella.
255
Complessivamente si è realizzata una
espansione di un fattore 4.
64 bit
23
Hash Funcion
© Antini Gianni, 2000
Note conclusive sulla sicurezza di Tiger:
Gli autori congetturano le seguenti:
1. La non linearità è dovuta essenzialmente alle SBox. Questo dovrebbe aiutare a resistere ad
attacchi di crittoanalisi differenziale di tipo BihamShamir.
2. Tiger dovrebbe resistere bene ad attacchi
Dobbertin’s differential.
3. La complessità minima per trovare una
retroimmagine dovrebbe aggirarsi su O(296).
24
Riferimenti bibliografici
Riferimenti cartacei e
elettronici sugli
argomenti trattati.
© Gianni Antini, 2000
© Antini Gianni, 2000
• Una trattazione a carattere algoritmico può essere trovata in:
ÆApplied Cryptography – Bruce Schneier – John Wiley e Son
ÆHandbook of Applied Cryptography – A. Menezes, P. van
Oorschot and S. Vanstone, CRC Press
• Di carattere decisamente più teorico:
ÆDoug R. Stinson – Cryptography: Theory and Pratice –
CRC Press, 1995
• Ancora più teoriche sono le seguenti dispense della Prof.sa
Goldwasser del MIT
ÆLecture Notes on Cryptography – Shafi Goldwasser, Mihir
Bellare – June 1997
© Antini Gianni, 2000
•Fra i siti in cui trovare informazioni cito
Æhttp://theory.lcs.mit.edu/
ed in particolare:
http://theory.lcs.mit.edu/~rivest/
in cui è possibile trovare anche una enorme pagina di link.