cerca
Domande di Crittografia
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Uni.CrittoDomande History

Hide minor edits - Show changes to output

Changed line 1 from:
(:title Domande e Esercizi di Crittografia:)
to:
(:title Domande di Crittografia:)
Deleted lines 97-210:


%sottotitolo%''':: Esercizi di Crittografia ::'''

Esercizi svolti by Licia

>>left bgcolor=#f5f9fc width=215px border='2px solid #cccccc' padding=5px<<
%center%'''Indice'''

# [[#s1|Cifratura classica]]
# [[#s2|Cifratura simmetrica]]
# [[#s3|Cifratura asimmetrica]]
# [[#s4|Funzioni MAC]]
# [[#s5|Funzioni HASH]]
# [[#s6|Firme digitali]]
# [[#s7|Certificati digitali]]
# [[#s8|Scambio di chiavi: Diffie-Hellman]]
# [[#s9|Secret Sharing]]
>><<

[[#s4]]
!!Funzioni MAC


''APPELLO DEL 21/06/2005''

[[http://ananke.crema.unimi.it/Crittografia/Appello-050621.pdf]]

'''FATTO IN AULA'''

'''b) Si consideri la seguente funzione hash h(M) definita per messaggi M {0,1}*. Sia W0(M) (risp, w1(M)) il numero di 0 (risp, di 1) presenti nel messaggio M. La funzione h(M) restituisce''':

| 1 se w0(M) < w1(M)

h(M) = | 0 se w0(M) > w1(M)

| m1 se w0(M) = w1(M) (dove M=m1m2m3…..)'''

'''i) Si calcoli il digest dei seguenti messaggi M1 = {00011}, M2 = {100101}, M3 = {00111}, M4 = {0101010101}.'''

W0 indica gli zeri, mentre w1 indica gli uni. Se guardiamo i bit di ogni singolo messaggio, per es. M1 vediamo che M1 ha 3 zeri e 2 uni, quindi gli zeri sono maggiori degli uni, di conseguenza ci troviamo nel secondo caso: h(M1) = 0, idem per gli altri messaggi. Per M2 invece possiamo vedere che gli uni e gli zeri sono uguali, quindi siamo nel caso 3: h(M2) = m1, cioè è uguale al primo bit del messaggio M2 che è 1 (h(M) = 1), ecc….

'''ii) Si discutano le proprietà di sicurezza della funzione h(M) precedentemente descritta'''

''monodirezionalità'': è soddisfatta perché dal valore dell’hash non è possibile risalire al messaggio
''sicurezza debole'': non soddisfatta perché si può trovare un altro messaggio M che genera uno stesso hash
''sicurezza forte'': non soddisfatta perché si può trovare una coppia di messaggi M e M’ che generano lo stesso hash


[[#s5]]
!!Funzioni HASH


''APPELLO DEL 20/01/2011''

[[http://ananke.crema.unimi.it/Crittografia/Appello-110215.pdf]]

'''CHIESTO AL PROF.'''

'''a) Si consideri la seguente funzione hash che opera su messaggi M lunghi 2m bit:'''
'''H0:{0,1}2m -> {0,1}m e si costruisca la funzione hash H1:{0,1}4m -> {0,1}m''' '''tale che se x è una stringa di bit x € {0,1}4m con x = (x1||x2) e x1, x2 € {0,1}2m''' '''allora'''
'''H1(x) = H0(H0(x1)||H0(x2))'''

'''i. Se m = 4 e H0 è la funzione che somma in modulo le coppie di bit successive, calcolare l’output di H1 se x = 0110 1100 0001 1000'''

'''ii. Si discutano le proprietà di sicurezza della funzione H1'''

'''iii. Si provi in generale che se H0 è collision resistant, lo è anche H1'''

Riassunto dati:
* x1 e x2 €{0,1}2m così che la loro concatenazione da ({0,1}2m || {0,1}2m) ={0,1}4m , che corrisponde infatti alla x che € a {0,1}4m
* x = 0110 1100 0001 1000, quindi x1 = 0110 1100 mentre x2 = 0001 1000
* H0 è la funzione che somma in modulo le coppie di bit successive: cioè si considerano le coppie di bit della x (di x1 e x2) e si sommano in modulo:
es. 01 = 1, 00 = 0, 11 = 0, 10 = 1

i)
Quindi se proviamo a sostituire tali valori nella funzione hash H1:
H1(x) = H0(H0(x1)||H0(x2))
= H0(H0(0110 1100)||H0(0001 1000))
= H0[(1100)|| (0110)]
= 0011

ii) - La proprietà One-wayness è soddisfatta perché dall’output H1 = 0011 non sono in grado di risalire all’input dato dai due valori x1 e x2
- La proprietà di sicurezza debole alle collisioni non è soddisfatta perché posso generare un altro input che mi dia lo stesso valore di ouput; questo è possibile perché se inserisco per es. un input formato dalla seguenza 1001 al posto di 0110 mi darà lo stesso output per come è costruita la funzione hash H0
- La proprietà di sicurezza forte alle collisioni non è soddisfatta perché, come detto per la sicurezza debole, posso trovare una coppia di input che mi dia lo stesso output, sfruttando la costruzione della funzione di hash H0

iii) Se assumiamo che la funzione H0 sia collision resistance e per assurdo assumiamo che H1 non lo sia, per non soddisfare la proprietà di collision resistance dovremmo avere un input x’ che genera uno stesso output y’, ma, per avere uno stesso output, anche gli argomenti della funzione H1 non devono essere collision resistance, e ciò non corrisponde perché noi abbiamo detto inizialmente che H0 era collision resistance; di conseguenza abbiamo dimostrato che, se H0 è collision resistance, lo è anche H1.

''APPELLO DEL 14/09/2010''

[[http://ananke.crema.unimi.it/Crittografia/Appello-100914.pdf]]

'''CHIESTO AL PROF.'''

2.
'''a) Si consideri la seguente funzione hash che fa uso di un robusto algoritmo di cifratura simmetrica Ek(m). Per un messaggio arbitrario m=(m1,….,mn), l’hash d è calcolato come d=Em1(IV) XOR Emn(IV), dove indica lo XOR i IV è un valore fissato.'''

'''i) Discutere le proprietà di sicurezza della funzione indicata. In particolare la one-wayness (sugg. Si consideri un messaggio con n=1) e la collision resistance (sugg. Si consideri un messaggio con n=3 dove m2=m3).'''

''Proprietà di One-wayness'': se n=1 si ha un solo blocco, cioè M = m1, quindi l’hash d = Em1(IV) e da questa funzione non si è in grado di risalire al messaggio in chiaro perché m1 è la chiave e quindi l’unico modo sarebbe rompere il cifrario e risalire alla chiave (cioè il blocco).

''Proprietà di collsion resistance'': se n=3 e m2=m3 l’hash è il seguente:

d=Em1(IV) XOR Em2(IV) XOR Em3(IV) = Em1(IV)

Poichè i blocchi m2 ed m3 sono uguali, per la proprietà dello XOR si eliminano e rimane solo la cifratura con chiave il blocco 1

Quindi un messaggio M formato da 3 blocchi è come se corrispondesse ad un solo blocco, e di conseguenza è possibile calcolare un M’ formato da un solo blocco tale da poter trovare una collisione:

M = m1m2m3 -> h(M) = Em1(IV)
M’ = m1 -> h(M’) = Em2(IV)

Quindi questa proprietà non è soddisfatta
Changed lines 7-8 from:
# [[#s1|Esercizi svolti by Licia]]
to:
Changed lines 99-104 from:
[[#s1]]
!!Esercizi svolti
di Licia

!!funzioni MAC
to:
%sottotitolo%''':: Esercizi di Crittografia ::'''

Esercizi svolti by
Licia

>>left bgcolor=#f5f9fc width=215px border='2px solid #cccccc' padding=5px<<
%center%'''Indice'''

# [[#s1|Cifratura classica]]
# [[#s2|Cifratura simmetrica]]
# [[#s3|Cifratura asimmetrica]]
# [[#s4|Funzioni MAC]]
# [[#s5|Funzioni HASH]]
# [[#s6|Firme digitali]]
# [[#s7|Certificati digitali]]
# [[#s8|Scambio di chiavi: Diffie-Hellman]]
# [[#s9|Secret Sharing]]
>><<

[[#s4]]
!!Funzioni
MAC
Changed lines 147-150 from:
!!funzioni HASH
to:
[[#s5]]
!!Funzioni HASH
Changed lines 186-195 from:
APPELLO DEL 14/09/2010

2
. FUNZIONI HASH
a)
Si consideri la seguente funzione hash che fa uso di un robusto algoritmo di cifratura simmetrica Ek(m). Per un messaggio arbitrario m=(m1,….,mn), l’hash d è calcolato come d=Em1(IV) XOR Emn(IV), dove indica lo XOR i IV è un valore fissato.

i) Discutere le proprietà di sicurezza della funzione indicata. In particolare la one-wayness (sugg. Si consideri un messaggio con n=1) e la collision resistance (sugg. Si consideri un messaggio con n=3 dove m2=m3).

Proprietà di One-wayness: se n=1 si ha un solo blocco, cioè M = m1, quindi l’hash d = Em1(IV) e da questa funzione non si è in grado di risalire al messaggio in chiaro perché m1 è la chiave e quindi l’unico modo sarebbe rompere il cifrario e risalire alla chiave (cioè il blocco).

Proprietà di collsion resistance: se n=3 e m2=m3 l’hash è il seguente:
to:
''APPELLO DEL 14/09/2010''

[[http://ananke
.crema.unimi.it/Crittografia/Appello-100914.pdf]]

'''CHIESTO AL PROF.'''

2.
'''a)
Si consideri la seguente funzione hash che fa uso di un robusto algoritmo di cifratura simmetrica Ek(m). Per un messaggio arbitrario m=(m1,….,mn), l’hash d è calcolato come d=Em1(IV) XOR Emn(IV), dove indica lo XOR i IV è un valore fissato.'''

'''
i) Discutere le proprietà di sicurezza della funzione indicata. In particolare la one-wayness (sugg. Si consideri un messaggio con n=1) e la collision resistance (sugg. Si consideri un messaggio con n=3 dove m2=m3).'''

''
Proprietà di One-wayness'': se n=1 si ha un solo blocco, cioè M = m1, quindi l’hash d = Em1(IV) e da questa funzione non si è in grado di risalire al messaggio in chiaro perché m1 è la chiave e quindi l’unico modo sarebbe rompere il cifrario e risalire alla chiave (cioè il blocco).

''Proprietà di collsion resistance'': se n=3 e m2=m3 l’hash è il seguente:
Changed lines 203-206 from:
un messaggio M formato da 3 blocchi è come se corrispondesse ad un solo blocco, quindi è possibile calcolare un M’ formato da un solo blocco tale da poter trovare una collisione:
to:
Poichè i blocchi m2 ed m3 sono uguali, per la proprietà dello XOR si eliminano e rimane solo la cifratura con chiave il blocco 1

Quindi un messaggio M formato da 3 blocchi è come se corrispondesse ad un solo blocco, e di conseguenza è possibile calcolare un M’ formato da un solo blocco tale da poter trovare una collisione:
Added line 209:
Added line 157:
i)
Changed line 159 from:
i) H1(x) = H0(H0(x1)||H0(x2))
to:
H1(x) = H0(H0(x1)||H0(x2))
Changed line 168 from:
iii) Se assumiamo che la funzione H0 sia collision resistance e per assurdo assumiamo che H1 non lo sia, per non soddisfare la proprietà di collision resistance dovremmo avere un input x’ che genera uno stesso output y’, ma, per avere uno stesso output, gli argomenti della funzione H1 devono essere uguali, e ciò non corrisponde perché noi abbiamo detto inizialmente che H0 era collision resistance; di conseguenza abbiamo dimostrato che, se H0 è collision resistance, lo è anche H1.
to:
iii) Se assumiamo che la funzione H0 sia collision resistance e per assurdo assumiamo che H1 non lo sia, per non soddisfare la proprietà di collision resistance dovremmo avere un input x’ che genera uno stesso output y’, ma, per avere uno stesso output, anche gli argomenti della funzione H1 non devono essere collision resistance, e ciò non corrisponde perché noi abbiamo detto inizialmente che H0 era collision resistance; di conseguenza abbiamo dimostrato che, se H0 è collision resistance, lo è anche H1.
Changed lines 135-144 from:
APPELLO DEL 20/01/2011

CHIESTO AL PROF
.
a) Si consideri la seguente funzione hash che opera su messaggi M lunghi 2m
bit:
H0:{0,1}2m -> {0,1}m e si costruisca la funzione hash H1:{0,1}4m -> {0,1}m tale che se x è una stringa di bit x € {0,1}4m con x = (x1||x2) e x1, x2 € {0,1}2m allora
H1(x) = H0(H0(x1)||H0(x2))

ii
. Se m = 4 e H0 è la funzione che somma in modulo le coppie di bit successive, calcolare l’output di H1 se x = 0110 1100 0001 1000
iii. Si discutano le proprietà di sicurezza della funzione H1
iv. Si provi in generale che se H0 è collision resistant, lo è anche H1
to:
''APPELLO DEL 20/01/2011''

[[http://ananke
.crema.unimi.it/Crittografia/Appello-110215.pdf]]

'''CHIESTO AL PROF.'''

'''a) Si consideri la seguente funzione hash che opera su messaggi M lunghi 2m
bit:'''
'''
H0:{0,1}2m -> {0,1}m e si costruisca la funzione hash H1:{0,1}4m -> {0,1}m''' '''tale che se x è una stringa di bit x € {0,1}4m con x = (x1||x2) e x1, x2 € {0,1}2m''' '''allora'''
'''H1(x) = H0(H0(x1)||H0(x2))'''

'''i
. Se m = 4 e H0 è la funzione che somma in modulo le coppie di bit successive, calcolare l’output di H1 se x = 0110 1100 0001 1000'''

'''ii
. Si discutano le proprietà di sicurezza della funzione H1'''

'''iii
. Si provi in generale che se H0 è collision resistant, lo è anche H1'''
Added line 105:
Added lines 108-109:
[[http://ananke.crema.unimi.it/Crittografia/Appello-050621.pdf]]
Changed lines 114-118 from:
| 1 se w0(M) < w1(M)

h(M) =
| 0 se w0(M) > w1(M)

| m1 se w0(M) = w1(M) (dove M=m1m2m3…..)'''
to:
| 1 se w0(M) < w1(M)

h(M) =
| 0 se w0(M) > w1(M)

| m1
se w0(M) = w1(M) (dove M=m1m2m3…..)'''
Changed line 111 from:
| 1 se w0(M) < w1(M)
to:
| 1 se w0(M) < w1(M)
Changed line 111 from:
| 1 se w0(M) < w1(M)
to:
| 1 se w0(M) < w1(M)
Changed line 111 from:
''' | 1 se w0(M) < w1(M)
to:
| 1 se w0(M) < w1(M)
Changed lines 111-112 from:
''' | 1 se w0(M) < w1(M)
to:
''' | 1 se w0(M) < w1(M)
Changed line 115 from:
| m1 se w0(M) = w1(M) (dove M=m1m2m3…..)'''
to:
| m1 se w0(M) = w1(M) (dove M=m1m2m3…..)'''
Added line 112:
Added line 114:
Changed lines 110-111 from:
''' | 1 se w0(M) < w1(M)
to:
''' | 1 se w0(M) < w1(M)
Changed line 113 from:
| m1 se w0(M) = w1(M) (dove M=m1m2m3…..)'''
to:
| m1 se w0(M) = w1(M) (dove M=m1m2m3…..)'''
Changed lines 108-113 from:
'''b) Si consideri la seguente funzione hash h(M) definita per messaggi M {0,1}*. Sia W0(M) (risp, w1(M)) il numero di 0 (risp, di 1) presenti nel messaggio M. La funzione h(M) restituisce:
| 1 se w0(M) < w1(M)
h(M) = | 0 se w0(M) > w1(M)
| m1 se w0(M) = w1(M) (dove M=m1m2m3…..)

i) Si calcoli il digest dei seguenti messaggi M1 = {00011}, M2 = {100101}, M3 = {00111}, M4 = {0101010101}.'''
to:
'''b) Si consideri la seguente funzione hash h(M) definita per messaggi M {0,1}*. Sia W0(M) (risp, w1(M)) il numero di 0 (risp, di 1) presenti nel messaggio M. La funzione h(M) restituisce''':
''' | 1 se w0(M) < w1(M)
h(M) = | 0 se w0(M) > w1(M)
| m1 se w0(M) = w1(M) (dove M=m1m2m3…..)'''

'''
i) Si calcoli il digest dei seguenti messaggi M1 = {00011}, M2 = {100101}, M3 = {00111}, M4 = {0101010101}.'''
Changed lines 105-110 from:
Dei seguenti esercizi posso garantirne la correttezza solo per quelli fatti in aula e per quelli corretti dal prof...

APPELLO DEL 21/06/2005

FATTO IN AULA

b) Si consideri la seguente funzione hash h(M) definita per messaggi M {0,1}*. Sia W0(M) (risp, w1(M)) il numero di 0 (risp, di 1) presenti nel messaggio M. La funzione h(M) restituisce:
to:
''APPELLO DEL 21/06/2005''

'''FATTO IN AULA'''
'''b)
Si consideri la seguente funzione hash h(M) definita per messaggi M {0,1}*. Sia W0(M) (risp, w1(M)) il numero di 0 (risp, di 1) presenti nel messaggio M. La funzione h(M) restituisce:
Changed line 110 from:
h(M) = | 0 se w0(M) > w1(M)
to:
h(M) = | 0 se w0(M) > w1(M)
Changed lines 113-114 from:
i) Si calcoli il digest dei seguenti messaggi M1 = {00011}, M2 = {100101}, M3 = {00111}, M4 = {0101010101}.
to:
i) Si calcoli il digest dei seguenti messaggi M1 = {00011}, M2 = {100101}, M3 = {00111}, M4 = {0101010101}.'''
Changed lines 117-120 from:
ii) Si discutano le proprietà di sicurezza della funzione h(M) precedentemente descritta
monodirezionalità: è soddisfatta perché dal valore dell’hash non è possibile risalire al messaggio
sicurezza debole: non soddisfatta perché si può trovare un altro messaggio M che genera uno stesso hash
sicurezza forte: non soddisfatta perché si può trovare una coppia di messaggi M e M’ che generano lo stesso hash
to:
'''ii) Si discutano le proprietà di sicurezza della funzione h(M) precedentemente descritta'''

''
monodirezionalità'': è soddisfatta perché dal valore dell’hash non è possibile risalire al messaggio
''sicurezza debole'': non soddisfatta perché si può trovare un altro messaggio M che genera uno stesso hash
''sicurezza forte'': non soddisfatta perché si può trovare una coppia di messaggi M e M’ che generano lo stesso hash
Changed line 7 from:
# [[#s1|Esercizi svolti di Licia]]
to:
# [[#s1|Esercizi svolti by Licia]]
Added line 100:
[[#s1]]
Changed line 100 from:
to:
!!Esercizi svolti di Licia
Changed line 100 from:
!!Esercizi svolti di [['''Licia'''->Utenti.Licia]]
to:
Added lines 7-8:
# [[#s1|Esercizi svolti di Licia]]
Added lines 99-100:

!!Esercizi svolti di [['''Licia'''->Utenti.Licia]]
Deleted lines 117-148:


APPELLO DEL 16/04/2009

Si consideri la seguente funzione MAC
M(a,b) = ax+b mod 3
che ha come chiave una coppia di valori a e b e si applica ai messaggi x, con a, b, x € Z3.
a) Si costruisca la matrice di autenticazione che calcola tutti i valori considerando per ogni riga le possibili coppie di valori della chiave e come colonne i possibili messaggi input x. Le celle della matrice avranno il valore del MAC.
Esempio:
Chiave
0 1 2
(0,0) 0 0 0

Se a,b,x € Z3, allora possono assumere valori 0, 1, 2; quindi la matrice di autenticazione sarà:


Chiave MAC(x) Calcolo Funzione MAC
(a,b) (ax+b mod 3)
0 1 2 X = 0 X = 1 X = 2

(0,0) 0 0 0 0*0 + 0 mod 3 0*1 + 0 mod 3 0*2 + 0 mod 3
(0,1) 1 1 1 0*0 + 1 mod 3 0*1 + 1 mod 3 0*2 + 1 mod 3
(1,0) 0 1 2 1*0 + 0 mod 3 1*1 + 0 mod 3 1*2 + 0 mod 3
(1,1) 1 2 0 1*0 + 1 mod 3 1*1 + 1 mod 3 1*2 + 1 mod 3
(0,2) 2 2 2 0*0 + 2 mod 3 0*1 + 2 mod 3 0*2 + 2 mod 3
(2,0) 0 2 1 2*0 + 0 mod 3 2*1 + 0 mod 3 2*2 + 0 mod 3
(2,2) 2 1 0 2*0 + 2 mod 3 2*1 + 2 mod 3 2*2 + 2 mod 3
(1,2) 2 0 0 1*0 + 2 mod 3 1*1 + 2 mod 3 1*2 + 2 mod 3
(2,1) 1 0 2 2*0 + 1 mod 3 2*1 + 1 mod 3 2*2 + 1 mod 3

b) Si consideri un attacco di selective forgery. Si spieghi in cosa consiste l’attacco e rispetto alla matrice costituita si discuta la sicurezza del MAC proposto.
L’attacco selective forgery prevede che: dato un messaggio M l’attaccante cerca di determinare y tale che y = MAC(M,K); cioè l’avversario sarà in grado di calcolare, per alcuni messaggi, il MAC corretto anche senza conoscere la chiave. Considerando il MAC proposto l’attaccante sarà in grado di calcolare il MAC con una certa facilità poiché è una semplice funzione lineare in Z3.
Changed lines 96-201 from:
[[Torna alla pagina di Crittografia -> Crittografia]]
to:
[[Torna alla pagina di Crittografia -> Crittografia]]

!!funzioni MAC

Dei seguenti esercizi posso garantirne la correttezza solo per quelli fatti in aula e per quelli corretti dal prof...

APPELLO DEL 21/06/2005

FATTO IN AULA
b) Si consideri la seguente funzione hash h(M) definita per messaggi M {0,1}*. Sia W0(M) (risp, w1(M)) il numero di 0 (risp, di 1) presenti nel messaggio M. La funzione h(M) restituisce:
| 1 se w0(M) < w1(M)
h(M) = | 0 se w0(M) > w1(M)
| m1 se w0(M) = w1(M) (dove M=m1m2m3…..)

i) Si calcoli il digest dei seguenti messaggi M1 = {00011}, M2 = {100101}, M3 = {00111}, M4 = {0101010101}.

W0 indica gli zeri, mentre w1 indica gli uni. Se guardiamo i bit di ogni singolo messaggio, per es. M1 vediamo che M1 ha 3 zeri e 2 uni, quindi gli zeri sono maggiori degli uni, di conseguenza ci troviamo nel secondo caso: h(M1) = 0, idem per gli altri messaggi. Per M2 invece possiamo vedere che gli uni e gli zeri sono uguali, quindi siamo nel caso 3: h(M2) = m1, cioè è uguale al primo bit del messaggio M2 che è 1 (h(M) = 1), ecc….

ii) Si discutano le proprietà di sicurezza della funzione h(M) precedentemente descritta
monodirezionalità: è soddisfatta perché dal valore dell’hash non è possibile risalire al messaggio
sicurezza debole: non soddisfatta perché si può trovare un altro messaggio M che genera uno stesso hash
sicurezza forte: non soddisfatta perché si può trovare una coppia di messaggi M e M’ che generano lo stesso hash


APPELLO DEL 16/04/2009

Si consideri la seguente funzione MAC
M(a,b) = ax+b mod 3
che ha come chiave una coppia di valori a e b e si applica ai messaggi x, con a, b, x € Z3.
a) Si costruisca la matrice di autenticazione che calcola tutti i valori considerando per ogni riga le possibili coppie di valori della chiave e come colonne i possibili messaggi input x. Le celle della matrice avranno il valore del MAC.
Esempio:
Chiave
0 1 2
(0,0) 0 0 0

Se a,b,x € Z3, allora possono assumere valori 0, 1, 2; quindi la matrice di autenticazione sarà:


Chiave MAC(x) Calcolo Funzione MAC
(a,b) (ax+b mod 3)
0 1 2 X = 0 X = 1 X = 2

(0,0) 0 0 0 0*0 + 0 mod 3 0*1 + 0 mod 3 0*2 + 0 mod 3
(0,1) 1 1 1 0*0 + 1 mod 3 0*1 + 1 mod 3 0*2 + 1 mod 3
(1,0) 0 1 2 1*0 + 0 mod 3 1*1 + 0 mod 3 1*2 + 0 mod 3
(1,1) 1 2 0 1*0 + 1 mod 3 1*1 + 1 mod 3 1*2 + 1 mod 3
(0,2) 2 2 2 0*0 + 2 mod 3 0*1 + 2 mod 3 0*2 + 2 mod 3
(2,0) 0 2 1 2*0 + 0 mod 3 2*1 + 0 mod 3 2*2 + 0 mod 3
(2,2) 2 1 0 2*0 + 2 mod 3 2*1 + 2 mod 3 2*2 + 2 mod 3
(1,2) 2 0 0 1*0 + 2 mod 3 1*1 + 2 mod 3 1*2 + 2 mod 3
(2,1) 1 0 2 2*0 + 1 mod 3 2*1 + 1 mod 3 2*2 + 1 mod 3

b) Si consideri un attacco di selective forgery. Si spieghi in cosa consiste l’attacco e rispetto alla matrice costituita si discuta la sicurezza del MAC proposto.
L’attacco selective forgery prevede che: dato un messaggio M l’attaccante cerca di determinare y tale che y = MAC(M,K); cioè l’avversario sarà in grado di calcolare, per alcuni messaggi, il MAC corretto anche senza conoscere la chiave. Considerando il MAC proposto l’attaccante sarà in grado di calcolare il MAC con una certa facilità poiché è una semplice funzione lineare in Z3.



!!funzioni HASH


APPELLO DEL 20/01/2011

CHIESTO AL PROF.
a) Si consideri la seguente funzione hash che opera su messaggi M lunghi 2m bit:
H0:{0,1}2m -> {0,1}m e si costruisca la funzione hash H1:{0,1}4m -> {0,1}m tale che se x è una stringa di bit x € {0,1}4m con x = (x1||x2) e x1, x2 € {0,1}2m allora
H1(x) = H0(H0(x1)||H0(x2))

ii. Se m = 4 e H0 è la funzione che somma in modulo le coppie di bit successive, calcolare l’output di H1 se x = 0110 1100 0001 1000
iii. Si discutano le proprietà di sicurezza della funzione H1
iv. Si provi in generale che se H0 è collision resistant, lo è anche H1

Riassunto dati:
* x1 e x2 €{0,1}2m così che la loro concatenazione da ({0,1}2m || {0,1}2m) ={0,1}4m , che corrisponde infatti alla x che € a {0,1}4m
* x = 0110 1100 0001 1000, quindi x1 = 0110 1100 mentre x2 = 0001 1000
* H0 è la funzione che somma in modulo le coppie di bit successive: cioè si considerano le coppie di bit della x (di x1 e x2) e si sommano in modulo:
es. 01 = 1, 00 = 0, 11 = 0, 10 = 1

Quindi se proviamo a sostituire tali valori nella funzione hash H1:
i) H1(x) = H0(H0(x1)||H0(x2))
= H0(H0(0110 1100)||H0(0001 1000))
= H0[(1100)|| (0110)]
= 0011

ii) - La proprietà One-wayness è soddisfatta perché dall’output H1 = 0011 non sono in grado di risalire all’input dato dai due valori x1 e x2
- La proprietà di sicurezza debole alle collisioni non è soddisfatta perché posso generare un altro input che mi dia lo stesso valore di ouput; questo è possibile perché se inserisco per es. un input formato dalla seguenza 1001 al posto di 0110 mi darà lo stesso output per come è costruita la funzione hash H0
- La proprietà di sicurezza forte alle collisioni non è soddisfatta perché, come detto per la sicurezza debole, posso trovare una coppia di input che mi dia lo stesso output, sfruttando la costruzione della funzione di hash H0

iii) Se assumiamo che la funzione H0 sia collision resistance e per assurdo assumiamo che H1 non lo sia, per non soddisfare la proprietà di collision resistance dovremmo avere un input x’ che genera uno stesso output y’, ma, per avere uno stesso output, gli argomenti della funzione H1 devono essere uguali, e ciò non corrisponde perché noi abbiamo detto inizialmente che H0 era collision resistance; di conseguenza abbiamo dimostrato che, se H0 è collision resistance, lo è anche H1.

APPELLO DEL 14/09/2010

2. FUNZIONI HASH
a) Si consideri la seguente funzione hash che fa uso di un robusto algoritmo di cifratura simmetrica Ek(m). Per un messaggio arbitrario m=(m1,….,mn), l’hash d è calcolato come d=Em1(IV) XOR Emn(IV), dove indica lo XOR i IV è un valore fissato.

i) Discutere le proprietà di sicurezza della funzione indicata. In particolare la one-wayness (sugg. Si consideri un messaggio con n=1) e la collision resistance (sugg. Si consideri un messaggio con n=3 dove m2=m3).

Proprietà di One-wayness: se n=1 si ha un solo blocco, cioè M = m1, quindi l’hash d = Em1(IV) e da questa funzione non si è in grado di risalire al messaggio in chiaro perché m1 è la chiave e quindi l’unico modo sarebbe rompere il cifrario e risalire alla chiave (cioè il blocco).

Proprietà di collsion resistance: se n=3 e m2=m3 l’hash è il seguente:
d=Em1(IV) XOR Em2(IV) XOR Em3(IV) = Em1(IV)

un messaggio M formato da 3 blocchi è come se corrispondesse ad un solo blocco, quindi è possibile calcolare un M’ formato da un solo blocco tale da poter trovare una collisione:
M = m1m2m3 -> h(M) = Em1(IV)
M’ = m1 -> h(M’) = Em2(IV)
Quindi questa proprietà non è soddisfatta
Changed line 42 from:
** Schema (non è Feistel)
to:
** Schema (è Feistel-confermato dalle slide)
Changed lines 1-2 from:
(:title Domande di Crittografia:)
to:
(:title Domande e Esercizi di Crittografia:)
Changed line 11 from:
* Playfair: come si usa, che vantaggi ha
to:
* Playfair: come si usa, che vantaggi ha, attacchi a Playfair
Changed lines 19-20 from:
to:
* Possibili attacchi in base alla conoscenza dell'avversario
Changed line 90 from:
* Diffie Hellman
to:
* Diffie Hellman (di solito con esercizio annesso)
Added line 94:
Added line 68:
** HMAC
Deleted line 15:
* Playfair
Changed line 45 from:
** b = lunghezza in BYTE della password
to:
** b = lunghezza in BYTE della password (0 - 255)
Added line 62:
* Utilizzo delle funzioni hash: firma digitale, integrità, certificazione del tempo
Added lines 74-78:
* Equivalente alla firma normale
* Caratteristiche
** facile da generare
** facile da verificare
** impossibile da falsificare
Changed line 85 from:
** certification path (stessa CA, CA differenti)
to:
** certification path (stessa CA; CA differenti)
Added lines 2-4:

[[Torna alla pagina di Crittografia -> Crittografia]]
Changed lines 86-88 from:
* (n,n)
to:
* (n,n)

[[Torna alla pagina di Crittografia -> Crittografia]]
Added lines 1-83:
(:title Domande di Crittografia:)
%sottotitolo%''':: Domande di Crittografia ::'''

!!Teoria teorica
* algoritmo di cifratura incondizionatamente sicuro (One Time Pad) e computazionalmente sicuro

!!Crittografia classica
* Playfair: come si usa, che vantaggi ha
* Vigenere: come si usa
** Kasiski
** Indice di Coincidenza (IC)
** Indice Mutuo di Coincidenza (IMC)
* Playfair
* Cifrario Affine
* Hill
* Autokey

!!Crittografia simmetrica
* cifratura ideale: blocco di n bit => 2'^n^' valori => 2'^n^' mappaggi
* confusione e diffusione
* caratteristiche dei cifrari simmetrici moderni
* rete di Feistel
* DES
** descrizione
** prova del funzionamento
** sicurezza
** Modalità: ECB, CBC, CFB, OFB, COUNTER
** Double DES
*** Meet in the middle
** Triple DES
*** Meet in the middle
* AES
** Blocco: 128, 192, 256 bit
** Round: 10, 12, 14
** Crittografia e Decrittografia (non è Feistel)
* Blowfish
** Blocco: 64 bit
** chiave: 32 - 448 bit
** Schema (non è Feistel)
* RC5 w/r/b
** w = lunghezza della word (16, 32, 64)
** r = numero di round (0 - 255)
** b = lunghezza in BYTE della password
* RC4

!!Crittografia asimmetrica
* RSA
** Teoremi di Fermat ed Eulero
** Ottimizzazioni: left-to-right, right-to-left
** Sicurezza
*** Sicurezza della chiave
*** Sicurezza della cifratura: Chosen Ciphertext, Common Modulus, Low Exponent
*** Sicurezza dell'implementazione: power, timing
*** Malleabilità
* El Gamal
** Come stabilire se un g è generatore di Z'_p_''^*^'

!!Hash, MAC
* Funzioni hash: proprietà (one-way, weak collision resistance e strong collision resistance)
* Paradosso del compleanno
* MD4
* MD5
* SHA-1
* MAC: caratteristiche e applicazioni
** Sicurezza
*** Total Break = recupero la chiave
*** Selective Forgery = dato M, trovarne il MAC senza chiave
*** Existential Forgery = trovare una coppia M, y tale che y è MAC(M, k)

!!Firme digitali e certificati
* DSS: parametri, utilizzo
* Differenza tra firma RSA e DSS usati con lo stesso messaggio in due occasioni
* Certificati digitali
** scopo
** CA
** caratteristiche
** certification path (stessa CA, CA differenti)

!!Secret Sharing
* Diffie Hellman
** Man in the middle
* (k,n)
* (n,n)