|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.TemiDesame History
Hide minor edits - Show changes to output
Changed line 286 from:
se ho un blocco di 3 bit, ho i seguenti valori: 000, 001, 010, 011, 100, 101, 110, 111 = 23 = 8 valori. to:
se ho un blocco di 3 bit, ho i seguenti valori: 000, 001, 010, 011, 100, 101, 110, 111 = 24 = 8 valori.
Changed lines 30-31 from:
[[http://ananke.crema.unimi.it/Crittografia/Appello-110215.pdf]]
to:
Deleted lines 84-85:
[[http://ananke.crema.unimi.it/Crittografia/Appello-110120.pdf]]
Changed lines 110-111 from:
[[http://ananke.crema.unimi.it/Crittografia/Appello-100910.pdf]]
to:
Changed lines 144-145 from:
[[http://ananke.crema.unimi.it/Crittografia/Appello-100209.pdf]]
to:
Changed lines 154-155 from:
[[http://ananke.crema.unimi.it/Crittografia/Appello-100119.pdf]]
to:
Changed lines 179-180 from:
[[http://ananke.crema.unimi.it/Crittografia/Appello-090925.pdf]]
to:
Changed lines 205-206 from:
[[http://ananke.crema.unimi.it/Crittografia/Appello-090711.pdf]]
to:
Changed lines 279-280 from:
[[http://ananke.crema.unimi.it/Crittografia/Appello-100925.pdf]]
to:
Deleted lines 303-304:
[[http://ananke.crema.unimi.it/Crittografia/Appello-100209.pdf]]
Deleted lines 336-337:
[[http://ananke.crema.unimi.it/Crittografia/Appello-101104.pdf]]
Deleted lines 363-364:
[[http://ananke.crema.unimi.it/Crittografia/Appello-090925.pdf]]
Changed lines 380-381 from:
[[http://ananke.crema.unimi.it/Crittografia/Appello-100702.pdf]]
to:
Changed lines 415-416 from:
[[http://ananke.crema.unimi.it/Crittografia/Appello-050621.pdf]]
to:
Changed lines 446-447 from:
[[http://ananke.crema.unimi.it/Crittografia/Appello-110215.pdf]]
to:
Deleted lines 478-479:
[[http://ananke.crema.unimi.it/Crittografia/Appello-100914.pdf]]
Changed line 81 from:
MIC (birba, babbo)= [(1*1) + (2*3) + (1*0) + (1*0) + (1*0)]/(5*5) = 7/5 to:
MIC (birba, babbo)= [(1*1) + (2*3) + (1*0) + (1*0) + (1*0)]/(5*5) = 7/25
Changed line 65 from:
IC = [2 ( 2 – 1 ) + 3 ( 3 – 1 ) + 1 ( 1 – 1 )]/[6 ( 6 – 1)] = 2/15 to:
IC = [2 ( 2 – 1 ) + 3 ( 3 – 1 ) + 1 ( 1 – 1 )]/[6 ( 6 – 1)] = 4/15
Changed lines 262-273 from:
c)
# '''Si consideri l’usuale corrispondenza tra l’alfabeto dei numeri ed i numeri da 0 a 25:
'''sia | k11 k12 |
| la chiave usata ed “m1, m2, m3, m4” il plaintext.
Esprimere matematicamente il corrispondente testo cifrato “c1 c2 c3 c4”.'''
'''
# Sia
'''- cifrare “dito”
- decifrare “kemk”''' to:
'''c) Si consideri l’usuale corrispondenza tra l’alfabeto dei numeri ed i numeri da 0 a 25:'''
'''sia | k11 k12 |'''
''' | k21 k22 | la chiave usata ed “m1, m2, m3, m4” il plaintext.'''
'''Esprimere matematicamente il corrispondente testo cifrato “c1 c2 c3 c4”.'''
'''sia “k11 = 5, k12 = 12, k21 = 2, k22 = 5” la chiave data:'''
'''- cifrare “dito”'''
'''- decifrare “kemk”'''
Added lines 6-7:
Premetto che tra apici e pedici da sistemare sto sclerando abbastanza.. e molto probabilmente non li avrò sistemati tutti.. quindi se qualche anima pia si dovesse accorgere che qualcuno non è stato sistemato lo ringranzio..
Changed lines 401-404 from:
C1 = Ek(M1) XOR C0
C2 = Ek(M2) XOR C1 …. to:
C1 = E'_k_'(M1) XOR C0
C2 = E'_k_'(M2) XOR C1 …. Changed lines 409-412 from:
M1 = Dk (C1 XOR C0)
M2 = Dk (C2 XOR C1)…. to:
M1 = D'_k_' (C1 XOR C0)
M2 = D'_k_' (C2 XOR C1)…. Changed line 414 from:
Mi = Dk (Ci XOR C'_i-1_') per i = 1,2,3….,n to:
Mi = D'_k_' (Ci XOR C'_i-1_') per i = 1,2,3….,n
Changed line 405 from:
to:
Changed line 416 from:
[[Attach:decifratura.gif]]
to:
Added line 410:
Changed lines 412-414 from:
Quindi la funzione di decifratura è: Mi = Dk (Ci XOR C'_i-1_') per i = 1,2,3….,n to:
Quindi la funzione di decifratura è:
Mi = Dk (Ci XOR C'_i-1_') per i = 1,2,3….,n
Added line 396:
Added line 400:
Added line 402:
Added lines 404-414:
[[Attach:cifratura.gif]]
La decifratura è la seguente
M1 = Dk (C1 XOR C0)
M2 = Dk (C2 XOR C1)….
Quindi la funzione di decifratura è: Mi = Dk (Ci XOR C'_i-1_') per i = 1,2,3….,n
[[Attach:decifratura.gif]]
Added lines 319-320:
Deleted line 321:
Deleted line 322:
Added lines 325-326:
Deleted line 327:
Added lines 331-332:
Deleted line 333:
Added line 337:
Deleted line 338:
Added line 341:
Added lines 387-402:
%center%''APPELLO DEL 02/02/2010''
[[http://ananke.crema.unimi.it/Crittografia/Appello-100702.pdf]]
'''Si consideri un cifrario a blocchi che cifra un messaggio M = M1M2M3…Mn e produce un testo cifrato C = C0C1C2C3….Cn usando un numero casuale N ed una chiave K nel seguente modo:'''
'''%center%C'_0_' = N'''
'''%center%C'_i_' = Ek(Mi) XOR C'_i-1_' per i = 1,2,3…,n'''
'''a) Scrivere la funzione di decifratura'''
C0 = N
C1 = Ek(M1) XOR C0
C2 = Ek(M2) XOR C1 ….
Changed lines 315-318 from:
# La prima modalità operativa di DES è l’ ELECTRONIC CODEBOOK CHAINING: è il modello più semplice in cui ciascun blocco in chiaro viene codificato in modo indipendente, sempre con la stessa chiave. Vantaggi: è il metodo più semplice e veloce ed eventuali errori non si propagano. Svantaggi: usando sempre la stessa chiave, uno stesso blocco in chiaro viene cifrato allo stesso modo e quindi per messaggi lunghi non è sicuro perché soggetto ad attacchi di sostituzione.
# La seconda modalità è il CIPHER BLOCK CHAINING: vi è dipendenza tra i blocchi perché l’input si ottiene come XOR tra il blocco in chiaro corrente e il blocco cifrato precedente.
to:
La prima modalità operativa di DES è l’ ELECTRONIC CODEBOOK CHAINING: è il modello più semplice in cui ciascun blocco in chiaro viene codificato in modo indipendente, sempre con la stessa chiave.
''Vantaggi'': è il metodo più semplice e veloce ed eventuali errori non si propagano.
''Svantaggi'': usando sempre la stessa chiave, uno stesso blocco in chiaro viene cifrato allo stesso modo e quindi per messaggi lunghi non è sicuro perché soggetto ad attacchi di sostituzione.
La seconda modalità è il CIPHER BLOCK CHAINING: vi è dipendenza tra i blocchi perché l’input si ottiene come XOR tra il blocco in chiaro corrente e il blocco cifrato precedente. Changed lines 325-326 from:
# La terza modalità è il CIPHER FEEDBACK con s bit. Non utilizza blocchi di 64bit ma lavora con segmenti di s bit < 64. Anche in questo caso vi è dipendenza tra i blocchi poiché la cifratura del blocco precedente viene utilizzata per cifrare il blocco successivo.
to:
La terza modalità è il CIPHER FEEDBACK con s bit. Non utilizza blocchi di 64bit ma lavora con segmenti di s bit < 64. Anche in questo caso vi è dipendenza tra i blocchi poiché la cifratura del blocco precedente viene utilizzata per cifrare il blocco successivo. Changed lines 330-331 from:
# La quarta modalità è l'OUTPUT FEEDBACK. La struttura è simile al CFB, l’unica differenza è che la cifratura del blocco corrente si esegue con l’output di DES del blocco precedente (e non il blocco cifrato).
to:
La quarta modalità è l'OUTPUT FEEDBACK. La struttura è simile al CFB, l’unica differenza è che la cifratura del blocco corrente si esegue con l’output di DES del blocco precedente (e non il blocco cifrato). Deleted line 332:
Changed line 335 from:
# La quinta e ultima modalità è il COUNTER. Si impiega un contatore delle dimensioni del blocco in chiaro, e viene incrementato per ogni blocco.
to:
La quinta e ultima modalità è il COUNTER. Si impiega un contatore delle dimensioni del blocco in chiaro, e viene incrementato per ogni blocco.
Deleted lines 316-317:
Deleted lines 322-323:
Deleted lines 327-328:
Deleted lines 333-334:
Added lines 338-382:
%center%''APPELLO DEL 04/11/2010''
[[http://ananke.crema.unimi.it/Crittografia/Appello-101104.pdf]]
'''a) Discutere il vantaggio di utilizzare strutture Feistel in DES'''
I vantaggi di utilizzo delle strutture Feistel sono:
- che la cifratura e la decifratura sono processi invertibili, in quanto la decifratura usa lo stesso algoritmo per la cifratura con l’unica differenza in cui le sottochiavi vengono applicate nell’ordine inverso. Questo semplifica enormemente l’implementazione;
- l’alternanza di sostituzioni, permutazioni ed espansioni (grazie alla funzione di Feistel) che forniscono la cosiddetta diffusione e confusione, cioè rispettivamente l’espansione della struttura statistica del testo in chiaro (cioè assegnare più lettere del testo in chiaro ad una lettera di testo cifrato – es. bigrammi) e la complicazione della relazione esistente fra testo cifrato e la chiave.
'''b) Discutere il funzionamento e la sicurezza di DES doppio'''
Il DES doppio prevede che il messaggio in chiaro venga cifrato due volte (con l’algoritmo di DES) con due chiavi diverse in sequenza (una per ogni passo di cifratura).
In questo modo la lunghezza della chiave raddoppia passando da 56 a 56*2 = 112 bit, con un notevole incremento dello spazio delle chiavi. Dato in input un blocco x di 64bit del testo in chiaro e due chiavi k1 e k2 a 56bit, cifriamo x con la chiave k1 ed otteniamo un blocco A di 64bit; cifriamo poi A con la chiave k2 ed otteniamo il corrispondente testo cifrato Y:
%center%Y = DESk2(DESk1(x))
La decifratura è analoga alla cifratura, ma richiede l’applicazione delle chiavi in ordine inverso:
%center%X = DESk1'^-1^'(DESk2'^-1^'(y))
Anche se può sembrare un sistema apparentemente più resistente, il DES doppio non aumenta la sicurezza del DES a singola cifratura, anzi esiste un algoritmo che è in grado di rompere tale cifrario dimostrando che è equivalente alla cifratura dello stesso messaggio con una sola chiave, ed è l’attacco Meet in teh Middle.
Quindi utilizzando questo attacco, anche se il DES doppio utilizza una chiave di 112bit può essere rotto con uno sforzo dell’ordine di 2'^56^', come per il DES singolo. Per questo motivo il DES doppio non viene utilizzato in pratica.
'''c) Discutere l’attacco Meet in the Middle a DES doppio'''
(questo è un attacco di tipo Known Plaintext Attack)
Questo algoritmo si basa principalmente sul fatto che se Y = DESk2(DESk1(x)), allora
A = DESk1(x) = DESk2'^-1^'(y). Quindi si supponga di conoscere una particolare coppia ( P e C ) dove P è il testo in chiaro e C il testo cifrato, e di voler determinare la chiave (k1, k2) utilizzata nella cifratura di P. Per prima cosa viene cifrato P utilizzando tutte le 2'^56^' possibili chiavi k1, memorizzando i testi cifrati in una tabella ( che viene eventualmente ordinata). Successivamente viene decifrato C usando tutte le 2'^56^' possibili chiavi k2. Man mano che vengono prodotte le decrittografie, si confrontano i risultati con la tabella e si ricerca una corrispondenza. Quando viene trovata una corrispondenza, si esegue il test delle due chiavi risultanti contro una nuova coppia nota di testo in chiaro/testo cifrato (poiché non è detto che sia effettivamente la chiave corretta, in quanto vi è una probabilità di 2'^48^' collisioni). Se le due chiavi producono il testo cifrato corretto si tratta quasi sicuramente delle chiavi corrette poichè in questo caso la probabilità di collisioni è 2'^-16^'.
%center%''APPELLO DEL 12/09/2009''
[[http://ananke.crema.unimi.it/Crittografia/Appello-090925.pdf]]
'''b) Si supponga di utilizzare una funzione hash H al posto della funzione f in DES. Quali caratteristiche deve avere questa funzione? Dato che H non è invertibile, come è possibile che l’algoritmo di decrittografia funzioni?'''
La funzione hash dovrà avere le seguenti caratteristiche:
- accetta un solo input di lunghezza variabile, quindi solo un blocco e non anche la chiave, e produce un output di lunghezza fissa;
- non è una funzione invertibile
- deve essere impossibile trovare un altro input che dia lo stesso valore hash in output
Anche se H non è invertibile, è comunque possibile che l’algoritmo di decrittografia funzioni in quanto, per la decrittografia in DES, non è necessario invertire la funzione F poiché sono i blocchi (destro e sinistro) ad essere invertiti.
[[Attach:decifraturaDES.gif]]
Changed lines 285-287 from:
'''a) Discutere la seguente affermazione: “In un generico algoritmo di cifratura a sostituzione a blocchi di n bit, le dimensioni della chiave sono n • 2n”''
Sapendo che: i cifrari a blocchi operano su blocchi di n bit in input per produrre blocchi di n bit in output; con blocchi di n bit di testo in chiaro ho 2n possibili valori del blocco; ogni blocco di testo in chiaro deve produrre un blocco cifrato univoco e che questa mappatura 1 a 1 viene fatta dalla chiave, si può quindi dedurre che servono 2n mappature e che ciascuna mappatura è composta da una sequenza di n bit. Quindi il valore totale della chiave è n • 2n
La chiave di un generico algoritmo di cifratura a blocchi si esprime come una tabella di 2n righe e n colonne (grandezza della tabella n • 2n) to:
'''a) Discutere la seguente affermazione: “In un generico algoritmo di cifratura a sostituzione a blocchi di n bit, le dimensioni della chiave sono n*2'^n^'”'''
Sapendo che: i cifrari a blocchi operano su blocchi di n bit in input per produrre blocchi di n bit in output; con blocchi di n bit di testo in chiaro ho 2n possibili valori del blocco; ogni blocco di testo in chiaro deve produrre un blocco cifrato univoco e che questa mappatura 1 a 1 viene fatta dalla chiave, si può quindi dedurre che servono 2n mappature e che ciascuna mappatura è composta da una sequenza di n bit. Quindi il valore totale della chiave è n*2'^n^'
La chiave di un generico algoritmo di cifratura a blocchi si esprime come una tabella di 2n righe e n colonne (grandezza della tabella n*2'^n^') Changed lines 301-344 from:
La chiave, guardando questa tabella, è la colonna di destra. Devo infatti procedere così: il mio blocco ha valore 010, quindi prendo la 010-esima voce della tabella, e ho la sua cifratura. Si vede quindi che la colonna di destra è composta da 8 voci da 3 bit l'una: per l'appunto n * 2n to:
La chiave, guardando questa tabella, è la colonna di destra. Devo infatti procedere così: il mio blocco ha valore 010, quindi prendo la 010-esima voce della tabella, e ho la sua cifratura. Si vede quindi che la colonna di destra è composta da 8 voci da 3 bit l'una: per l'appunto n*2'^n^'
'''b) Si considerino DES e AES e si calcoli lo spazio necessario per memorizzare le funzioni da loro realizzate in forma tabellare. Discutere quindi i vantaggi di utilizzare DES e AES.'''
Per “spazio necessario per memorizzare le funzioni da loro realizzate in forma tabellare” si intende la lunghezza della chiave e considerato quanto detto al punto a) risulta essere n*2'^n^'.
Quindi sapendo che DES utilizza blocchi di 64bit la grandezza della tabella sarà 64*2'^64^' , mentre AES prevede 128bit, quindi la grandezza della tabella sarà 128*2'^128^'
%center%''APPELLO DEL 09/02/2010''
[[http://ananke.crema.unimi.it/Crittografia/Appello-100209.pdf]]
'''a) Discutere vantaggi e svantaggi delle modalità operative di DES'''
Servono per cifrare testi più lunghi di 64bit.
# La prima modalità operativa di DES è l’ ELECTRONIC CODEBOOK CHAINING: è il modello più semplice in cui ciascun blocco in chiaro viene codificato in modo indipendente, sempre con la stessa chiave. Vantaggi: è il metodo più semplice e veloce ed eventuali errori non si propagano. Svantaggi: usando sempre la stessa chiave, uno stesso blocco in chiaro viene cifrato allo stesso modo e quindi per messaggi lunghi non è sicuro perché soggetto ad attacchi di sostituzione.
# La seconda modalità è il CIPHER BLOCK CHAINING: vi è dipendenza tra i blocchi perché l’input si ottiene come XOR tra il blocco in chiaro corrente e il blocco cifrato precedente.
''Vantaggi'': a differenza dell’ECB, non si generano blocchi uguali in output grazie alla loro dipendenza; se si cambia un solo bit del messaggio originario, cambia di conseguenza tutto il rimanente messaggio; questo vincolo di dipendenza evita attacchi di sostituzioni dei blocchi.
''Svantaggi'': la dipendenza dei blocchi genera però un rallentamento del sistema e la propagazione di errori.
# La terza modalità è il CIPHER FEEDBACK con s bit. Non utilizza blocchi di 64bit ma lavora con segmenti di s bit < 64. Anche in questo caso vi è dipendenza tra i blocchi poiché la cifratura del blocco precedente viene utilizzata per cifrare il blocco successivo.
''Vantaggi'': il valore di s può essere scelto a piacimento e il valore della cifratura viene prodotto subito.
''Svantaggi'': per valori di s molto piccoli, il sistema diventa più oneroso e vengono propagati gli errori.
# La quarta modalità è l'OUTPUT FEEDBACK. La struttura è simile al CFB, l’unica differenza è che la cifratura del blocco corrente si esegue con l’output di DES del blocco precedente (e non il blocco cifrato).
''Vantaggi'': Non si propagano gli errori di trasmissione dei bit.
''Svantaggi'': E’ più vulnerabile del CFB a modifica di flusso.
# La quinta e ultima modalità è il COUNTER. Si impiega un contatore delle dimensioni del blocco in chiaro, e viene incrementato per ogni blocco.
''Vantaggi'': non vi è dipendenza tra i blocchi e quindi si possono eseguire in parallelo le cifrature di diversi blocchi. Se si conosce prima il contatore, si può pre-calcolare l’output del DES ed eseguire poi solo un’operazione di XOR; si ha un accesso causale, la sicurezza è dimostrabile ed è semplice in quanto richiede solo l'algoritmo di crittografia.
Changed lines 262-264 from:
# Si consideri l’usuale corrispondenza tra l’alfabeto dei numeri ed i numeri da 0 a 25:
sia | k11 k12 | to:
# '''Si consideri l’usuale corrispondenza tra l’alfabeto dei numeri ed i numeri da 0 a 25:
'''
'''sia | k11 k12 | Changed lines 266-272 from:
Esprimere matematicamente il corrispondente testo cifrato “c1 c2 c3 c4”.
- decifrare “kemk” to:
Esprimere matematicamente il corrispondente testo cifrato “c1 c2 c3 c4”.'''
'''
# Sia “k11 = 5, k12 = 12, k21 = 2, k22 = 5” la chiave data:'''
'''- cifrare “dito”
- decifrare “kemk”''' Added lines 276-300:
[[#s2]]
!!Cifratura simmetrica
%center%''APPELLO DEL 25/09/2010''
[[http://ananke.crema.unimi.it/Crittografia/Appello-100925.pdf]]
'''a) Discutere la seguente affermazione: “In un generico algoritmo di cifratura a sostituzione a blocchi di n bit, le dimensioni della chiave sono n • 2n”'''
Sapendo che: i cifrari a blocchi operano su blocchi di n bit in input per produrre blocchi di n bit in output; con blocchi di n bit di testo in chiaro ho 2n possibili valori del blocco; ogni blocco di testo in chiaro deve produrre un blocco cifrato univoco e che questa mappatura 1 a 1 viene fatta dalla chiave, si può quindi dedurre che servono 2n mappature e che ciascuna mappatura è composta da una sequenza di n bit. Quindi il valore totale della chiave è n • 2n
La chiave di un generico algoritmo di cifratura a blocchi si esprime come una tabella di 2n righe e n colonne (grandezza della tabella n • 2n)
ESEMPIO:
se ho un blocco di 3 bit, ho i seguenti valori: 000, 001, 010, 011, 100, 101, 110, 111 = 23 = 8 valori.
Una possibile cifratura potrebbe essere questa:
000 -> 100
001 -> 101
010 -> 000
011 -> 110
100 -> 011
101 -> 111
110 -> 001
111 -> 010
La chiave, guardando questa tabella, è la colonna di destra. Devo infatti procedere così: il mio blocco ha valore 010, quindi prendo la 010-esima voce della tabella, e ho la sua cifratura. Si vede quindi che la colonna di destra è composta da 8 voci da 3 bit l'una: per l'appunto n * 2n
Changed lines 273-275 from:
[[Attach:HILL1.jpg]]
[[Attach:HILL2.jpg]]
[[Attach:HILL3.jpg]] to:
[[Attach:HILL1.gif]]
[[Attach:HILL2.gif]]
[[Attach:HILL3.gif]]
Changed line 234 from:
to:
Decrittografia: P = CK'^-1^' Changed lines 252-254 from:
Y * X-1 = K * X * X-1 quindi essendo X * X-1 = I (identità) si può ricavare la chiave:
Y * X-1 = K * I => Y * X-1 = K to:
Y * X'^-1^' = K * X * X'^-1^' quindi essendo X * X'^-1^' = I (identità) si può ricavare la chiave:
Y * X'^-1^' = K * I => Y * X'^-1^' = K
Changed lines 260-261 from:
to:
c)
# Si consideri l’usuale corrispondenza tra l’alfabeto dei numeri ed i numeri da 0 a 25:
sia | k11 k12 |
| k21 k22 | la chiave usata ed “m1, m2, m3, m4” il plaintext.
Esprimere matematicamente il corrispondente testo cifrato “c1 c2 c3 c4”.
# Sia “k11 = 5, k12 = 12, k21 = 2, k22 = 5” la chiave data:
- cifrare “dito”
- decifrare “kemk”
[[Attach:HILL1.jpg]]
[[Attach:HILL2.jpg]]
[[Attach:HILL3.jpg]]
Added lines 236-258:
'''b) Discutere la sicurezza del cifrario di Hill rispetto a:'''
'''i. ciphertext-only attack'''
'''ii. known plaintext attack''' '''(possibilmente con un esempio)'''
i. Se prendiamo m grande allora il cifrario di Hill risulta abbastanza sicuro contro attacchi ciphertext-only perché il numero degli m-grammi possibili diventa troppo grande per fare un’analisi statistica.
ii. Risulta invece vulnerabile ad un attacco known plaintext per il seguente motivo:
- Se l’attaccante conosce la matrice X di testi in chiaro e la matrice Y di testi cifrati, sa risalire alla chiave nel modo seguente
Y = K * X (dove K * X è una moltiplicazione per matrici)
Se questo è vero, allora è sicuramente vero che:
Y * X-1 = K * X * X-1 quindi essendo X * X-1 = I (identità) si può ricavare la chiave:
Y * X-1 = K * I => Y * X-1 = K
[Quindi sfruttando le proprietà della matrice identità, che è una matrice neutra in quanto qualsiasi matrice moltiplicata per I restituisce se stessa, si riesce a risalire alla chiave K (K*I = k)]
Dalla matrice X riesce a risalire alla matrice inversa X-1 che, moltiplicata per entrambi i membri dell’equazione, da come risultato proprio la chiave K.
Added lines 206-238:
%center%''APPELLO DEL 11/07/2009''
[[http://ananke.crema.unimi.it/Crittografia/Appello-090711.pdf]]
'''a) Descrivere il funzionamento del cifrario di Hill'''
L’algoritmo del cifrario di Hill prende una sequenza di m lettere in chiaro e le sostituisce con m lettere di testo cifrato. La sostituzione è determinata da m equazioni lineari in cui a ciascun carattere viene assegnato un valore numerico ( a = 0, b = 1,… z = 25).
Crittografia: C = KP
Il testo cifrato si ricava moltiplicando la matrice con i valori della chiave k per il vettore colonna del testo in chiaro. La matrice K deve essere invertibile, altrimenti non si potrebbe eseguire la decrittografia.
Per es. per m = 2, il sistema può essere visto come:
c1 = ( k1,1p1 + k1,2p2 ) mod 26
c2 = ( k2,1p1 + k2,2p2 ) mod 26
e può essere rappresentato in forma matriciale nel seguente modo:
┌ ┐ ┌ ┐ ┌ ┐
│ k11 k12 │ │ p1 │ │ c1 │
│ │ │ │ = │ │ mod 26
│ k21 k22 │ │ p2 │ │ c2 │
└ ┘ └ ┘ └ ┘
Dove pi indica i caratteri del testo in chiaro, ki i caratteri della chiave e ci i caratteri del testo cifrato.
Decrittografia: P = CK-1
Il testo in chiaro si ricava moltiplicando la matrice inversa K-1 per il vettore colonna di testo cifrato.
Changed line 300 from:
M’ = m1 -> h(M’) = Em2(IV) to:
M’ = m1 -> h(M’) = Em1(IV)
Changed lines 181-182 from:
%center%''APPELLO DEL 25/09/2008'' to:
%center%''APPELLO DEL 25/09/2009'' Added lines 202-206:
'''c) Utilizzare la parola chiave "viva i farabutti" per cifrare il testo in chiaro "giornalisti" e decifrare il testo cifrato "qpgruatfourn'''
[[Attach:playfair.gif]]
Deleted lines 201-206:
'''c) Utilizzare la parola chiave “viva i farabutti” per cifrare il testo in chiaro “giornalisti” e decifrare il testo cifrato “qpgruatfourn”'''
Attach:
Changed line 205 from:
to:
Changed line 205 from:
to:
Changed line 205 from:
to:
Changed lines 203-205 from:
to:
'''c) Utilizzare la parola chiave “viva i farabutti” per cifrare il testo in chiaro “giornalisti” e decifrare il testo cifrato “qpgruatfourn”'''
Attach:playfair.jpg
Added lines 180-203:
%center%''APPELLO DEL 25/09/2008''
[[http://ananke.crema.unimi.it/Crittografia/Appello-090925.pdf]]
'''a) Descrivere brevemente la cifratura di Playfair'''
Il cifrario di Playfair è un cifrario a sostituzione che opera sui digrammi. I digrammi del testo in chiaro vengo tradotti in digrammi cifrati. Si usa una matrice 5x5 comprendente tutte le lettere dell’alfabeto (i e j unica casella). Si inserisce all’inizio della matrice la chiave utilizzata (senza ripetere le doppie) e poi si inseriscono tutte le lettere mancanti dell’alfabeto, in ordine (escludendo cioè quelle della chiave gia utilizzate).
Il testo in chiaro viene cifrato due lettere alla volta nel seguente modo:
- si individuano le due lettere nella tabella, esse definiscono un rettangolo in cui ciascuna lettera sta in un angolo e l’altra nell’angolo opposto. Queste lettere verranno cifrate con quelle che si trovano all’estremità del rettangolo nel lato orizzontale opposto.
- Le lettere che stanno sulla stessa riga(o colonna) verranno sostituite con quelle che stanno immediatamente alla loro destra (o immediatamente sotto).
- Le lettere ripetute vanno separate da una lettera di riempimento, generalmente la meno utilizzata nella lingua, in italiano x es. la Q o la X
- Se l’ultimo digramma è incompleto perché formato da un solo carattere di testo in chiaro viene utilizzata la lettera di riempimento per completarlo.
La decifratura avviene al contrario.
'''b) Discutere i vantaggi rispetto alla cifratura monoalfabetica e le debolezze del sistema Playfair'''
Il vantaggio rispetto alla cifratura monoalfabetica è che con Playfair si hanno 676 possibili digrammi (26x26), a differenza delle sole 26 lettere della monoalfabetica; dunque l’identificazione dei singoli digrammi è più difficile. Nonostante ciò, la debolezza di questo sistema è che la struttura del testo rimane identica, e quindi un attacco statistico come l’analisi delle frequenze dei digrammi più comuni nella lingua è valido contro Playfair
Deleted lines 143-169:
[[#s4]]
!!Funzioni MAC
%center%''APPELLO DEL 21/06/2005''
[[http://ananke.crema.unimi.it/Crittografia/Appello-050621.pdf]]
%red%'''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
Added lines 180-209:
[[#s4]]
!!Funzioni MAC
%center%''APPELLO DEL 21/06/2005''
[[http://ananke.crema.unimi.it/Crittografia/Appello-050621.pdf]]
%red%'''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
Changed lines 173-174 from:
http://ananke.crema.unimi.it/Crittografia/Appello-100209.pdf to:
[[http://ananke.crema.unimi.it/Crittografia/Appello-100209.pdf]] Added lines 181-206:
%center%''APPELLO DEL 19/01/2010''
[[http://ananke.crema.unimi.it/Crittografia/Appello-100119.pdf]]
%red%'''CHIESTO AL PROF.'''
'''b) Si supponga di tentare di rompere una cifratura, giocando il ruolo dell’avversario e conoscendo il tipo di sistema utilizzato per ottenere il messaggio cifrato. Quale plaintext si potrebbe utilizzare (in maniera ottimale) per determinare la chiave sapendo che il cifrario utilizzato è:'''
'''i. Cifrario a Sostituzione'''
'''ii. Cifrario di Vigenere'''
'''iii. Cifrario di Hill'''
'''iv. Cifrario Affine'''
(Cioè io avversario devo mandare un testo in chiaro in modo tale da farmelo decifrare, con uno di questi cifrari, per poter risalire alla chiave)
i. ''Cifrario a sostituzione:''Invio un testo in chiaro con tutte le lettere dell’alfabeto (dalla a alla z) in modo tale da ottenere la cifratura corrispondente per ciascuna lettera
ii. ''Cifrario di Vigenere'': Data una chiave di lunghezza k, invio un testo in chiaro di lunghezza k, poiché in Vigenere la chiave utilizzata è la stessa ripetuta più volte per renderla pari alla lunghezza del testo da cifrare
iii. ''Cifrario di Hill:'' Invio un testo di m lettere in chiaro, perché vengono sostituite con m lettere cifrate secondo m equazioni lineari; quindi ad ogni blocco di caratteri lunghi m si avrà una chiave lunga m
iv. ''Cifrario Affine'':(?? su questo non sono sicura poichè il prof. si è perso via) (è un particolare cifrario a sostituzione) Invio un testo in chiaro con tutte le lettere dell’alfabeto per ottenere la corrispondente lettera cifrata; in questo modo posso risalire alla chiave perché la chiave utilizzata è una coppia di interi a e b appartenenti a Z26 che soddisfa tale equazione di cifratura: E(pi) = (api + b) mod 26 , dove a ha valori minori di 26 e primi con 26, mentre b qualsiasi valore tra 0 e 25
Added lines 170-181:
%center%''APPELLO DEL 09/02/2010''
http://ananke.crema.unimi.it/Crittografia/Appello-100209.pdf
'''a) Discutere la natura e i possibili attacchi al cifrario di Vigenere'''
Un possibile attacco a questo cifrario è il Known Ciphertext Attack, poiché conoscendo il testo cifrato è possibile utilizzare metodi statistici per risalire al messaggio in chiaro: utilizzando l’indice di coincidenza, in cui si risale alla lunghezza della chiave e utilizzando l’indice di mutua coincidenza per risalire alla chiave
'''b) Discutere la natura e i possibili attacchi al cifrario di Playfair'''
Un possibile attacco a questo cifrario è il Known Ciphertext Attack, poiché conoscendo il testo cifrato è possibile utilizzare metodi statistici per risalire al messaggio in chiaro: utilizzando l’analisi delle frequenze dei digrammi più comuni nella lingua
Added lines 131-141:
'''b) Descrivere le nozioni di algoritmo di cifratura incondizionatamente sicuro e computazionalmente sicuro'''
Un algoritmo di cifratura si definisce incondizionatamente sicuro se, indipendentemente dal tempo e dalle risorse disponibili, è impossibile decrittografare il testo cifrato; si definisce invece computazionalmente sicuro quando il tempo richiesto per violare la cifratura è grande e comunque superiore alla vita utile delle informazioni contenute
'''c) Discutere un sistema incondizionatamente sicuro di cifratura'''
Esiste un solo sistema di questo tipo, ed è il cifrario One-Time pad: si utilizza una chiave casuale di lunghezza pari alla lunghezza del testo in chiaro, in modo da non doverla ripetere. La chiave deve essere utilizzata per crittografare e de crittografare un solo messaggio e poi essere scartata e cambiata. Questo schema è considerato inviolabile perché:
- produce un output casuale che non ha più alcuna relazione statistica con il testo in chiaro;
- la chiave è di lunghezza pari al messaggio e viene cambiata di volta in volta.
Appunto per questi motivi però tale cifrario è utilizzabile sono in teoria e non in pratica poiché necessita di una grande quantità di chiavi casuali e vi è inoltre il problema di distribuzione delle chiavi poiché sia il mittente sia il destinatario devono essere a conoscenza della chiave.
Changed line 117 from:
# Known Ciphertext Attack: in cui l’avversario conosce solo il testo cifrato – esempio: se un testo è stato cifrato con il cifrario a sostituzione, un possibile attacco può essere l’analisi della frequenza dei caratteri, in cui è possibile risalire al testo in chiaro;(anche il cifrario di Vigenere è vulnerabile a questo attacco) to:
# '''Known Ciphertext Attack''': in cui l’avversario conosce solo il testo cifrato – esempio: se un testo è stato cifrato con il cifrario a sostituzione, un possibile attacco può essere l’analisi della frequenza dei caratteri, in cui è possibile risalire al testo in chiaro;(anche il cifrario di Vigenere è vulnerabile a questo attacco) Changed lines 120-124 from:
# Known Plaintext Attack: in cui l’avversario conosce sia il testo in chiaro sia il testo cifrato – esempio: se un testo è stato cifrato con il cifrario di Hill, l’avversario può intercettare n² coppie di caratteri in chiaro e cifrati e impostare un sistema lineare che può (di solito) essere risolto facilmente
# Chosen Plaintext Attack: in cui l’avversario può ottenere la cifratura di un testo in chiaro a sua scelta – esempio: crittografia a chiave pubblica, dove la chiave di cifratura è pubblica e l’attaccante può cifrare qualsiasi testo in chiaro egli voglia (x es. RSA) to:
# '''Known Plaintext Attack''': in cui l’avversario conosce sia il testo in chiaro sia il testo cifrato – esempio: se un testo è stato cifrato con il cifrario di Hill, l’avversario può intercettare n² coppie di caratteri in chiaro e cifrati e impostare un sistema lineare che può (di solito) essere risolto facilmente
# '''Chosen Plaintext Attack''': in cui l’avversario può ottenere la cifratura di un testo in chiaro a sua scelta – esempio: crittografia a chiave pubblica, dove la chiave di cifratura è pubblica e l’attaccante può cifrare qualsiasi testo in chiaro egli voglia (x es. RSA) Changed lines 126-127 from:
# Chosen Ciphertext Attack: in cui l’avversario può ottenere la decifratura di un testo cifrato a sua scelta – esempio: RSA, sfruttando le proprietà dell’omomorfismo e la cifratura dell’algoritmo to:
# '''Chosen Ciphertext Attack''': in cui l’avversario può ottenere la decifratura di un testo cifrato a sua scelta – esempio: RSA, sfruttando le proprietà dell’omomorfismo e la cifratura dell’algoritmo Changed line 129 from:
# Chosen Text Attack: in cui l’avversario può ottenere la cifratura e la decifratura di coppie di testi in chiaro/cifrato – esempio?? to:
# '''Chosen Text Attack''': in cui l’avversario può ottenere la cifratura e la decifratura di coppie di testi in chiaro/cifrato – esempio??
Added lines 108-129:
%center%''APPELLO DEL 10/09/2010''
[[http://ananke.crema.unimi.it/Crittografia/Appello-100910.pdf]]
'''a) Descrivere i principali tipi di attacco conosciuti e fornire un esempio per ciascuno scenario'''
Esistono 5 tipi di attacco:
# Known Ciphertext Attack: in cui l’avversario conosce solo il testo cifrato – esempio: se un testo è stato cifrato con il cifrario a sostituzione, un possibile attacco può essere l’analisi della frequenza dei caratteri, in cui è possibile risalire al testo in chiaro;(anche il cifrario di Vigenere è vulnerabile a questo attacco)
# Known Plaintext Attack: in cui l’avversario conosce sia il testo in chiaro sia il testo cifrato – esempio: se un testo è stato cifrato con il cifrario di Hill, l’avversario può intercettare n² coppie di caratteri in chiaro e cifrati e impostare un sistema lineare che può (di solito) essere risolto facilmente
# Chosen Plaintext Attack: in cui l’avversario può ottenere la cifratura di un testo in chiaro a sua scelta – esempio: crittografia a chiave pubblica, dove la chiave di cifratura è pubblica e l’attaccante può cifrare qualsiasi testo in chiaro egli voglia (x es. RSA)
# Chosen Ciphertext Attack: in cui l’avversario può ottenere la decifratura di un testo cifrato a sua scelta – esempio: RSA, sfruttando le proprietà dell’omomorfismo e la cifratura dell’algoritmo
# Chosen Text Attack: in cui l’avversario può ottenere la cifratura e la decifratura di coppie di testi in chiaro/cifrato – esempio??
Added lines 80-107:
%center%''APPELLO DEL 20/01/2011''
[[http://ananke.crema.unimi.it/Crittografia/Appello-110120.pdf]]
'''a) Si descriva la grandezza dello spazio delle chiavi dei seguenti cifrari'''
i. ''Cesare'': 25 possibili chiavi
(non 26 xkè se sposto di 26 ritorna alla posizione iniziale e quindi non sposto nulla)
ii. ''Sostituzione (generica)'': 26! possibili chiavi (permutazione dei 26 caratteri)
iii. ''Vigenere'': 26^t possibili chiavi ( dove t = lunghezza della chiave)
iv. ''Affine'': 26*12 possibili chiavi
(b = [0,26], a = [1,12] – i valori di b sono le 25 lettere dell'alfabeto e i valori di a sono i numeri primi con 26 minori di 26)
v.'' Parole della chiave lunghe 10 lettere'': 26! / 16 ! possibili chiavi
(perché il primo carattere viene scelto tra tutti i 26, il secondo carattere tra i 25 poichè è gia stato scelto il primo, ecc.. fino al decimo carattere della chiave, che viene scelto tra i 17 restanti e tutto diviso le 16 possibilità di caratteri mancanti)
'''b) Si consideri il cifrario di Cesare e si discuta l’eventuale vantaggio di adottare una doppia cifratura, cioè l’utilizzo in cascata di due chiavi k e k’ di cifratura'''
Il cifrario di Cesare è un cifrario a sostituzione in cui ogni lettera dell’alfabeto corrisponde alla lettera che si trova a 3 posizioni in avanti dell’alfabeto:
per es. la A che si trova in posizione 0, verrà sostituita con la D che si trova in posizione 3, la B verrà sostituita con la E, la C con la F ecc.. ecc…
Quindi l’utilizzo di una doppia cifratura non ha nessuna maggiore sicurezza perché la somma di k e k’ corrisponderà ancora ad una singola sostituzione, solo che sarà di uno spostamento maggiore.
Changed lines 21-28 from:
[[#s4]]
!!Funzioni MAC
%center%''APPELLO DEL 21/06/2005''
[[http://ananke.crema.unimi.it/Crittografia/Appello-050621.pdf]] to:
[[#s1]]
!!Cifratura classica
!!! Vigenere
%center%''APPELLO DEL 15/02/2011''
[[http://ananke.crema.unimi.it/Crittografia/Appello-110215.pdf]]
%red%'''FATTO IN AULA'''
'''a) Si descrivano le caratteristiche del cifrario di Vigenere'''
Il cifrario di Vigenere è un cifrario a sostituzione polialfabetica. Dato un testo in chiaro M ed una chiave di lunghezza n, si divide il testo in chiaro in blocchi di n caratteri, pari alla lunghezza della chiave; per crittografare un messaggio, la chiave deve essere lunga quanto il messaggio stesso e poiché di solito la chiave è di lunghezza minore del messaggio, viene ripetuta. Grazie alla ripetizione della chiave, il vantaggio di questo sistema di cifratura è che due o più lettere uguali nel messaggio in chiaro potranno essere cifrate in modo differente. La crittoanalisi mediante frequenza delle lettere risulta quindi limitata.
Per poter crittografare/decrittografare il messaggio in chiaro/cifrato veniva utilizzata per semplicità una matrice di 26x26 ( le 26 lettere dell’alfabeto) in cui si ricercava la coppia “carattere del testo in chiaro – carattere della chiave”.
Ora si possono utilizzare le seguenti formule:
crittografia : Ci = (Mi + K i mod t ) mod t
Decrittografia: Mi = (Ci – K i mod t ) mod t
dove t = lunghezza della chiave = 26, Mi = carattere del testo in chiaro
Ci = carattere cifrato ( a = 0, b = 1 …. Z = 25), K = chiave
'''b) Descrivere il significato e l’utilizzo degli indici di coincidenza e mutua coincidenza nella crittoanalisi del cifrario di Vigenere'''
''INDICE DI COINCIDENZA (IC)'': è utilizzato per calcolare la probabilità che due caratteri presi a caso in una stringa x1x2…xn siano uguali. Il suo utilizzo nella crittoanalisi serve per determinare la lunghezza della chiave. Grazie a questo indice è anche possibile capire in che lingua è stato scritto il messaggio in chiaro.
''INDICE DI MUTUA COINCIDENZA (MIC)'': è utilizzato per calcolare la probabilità che due caratteri presi a caso in una stringa x1x2…xn e in un’altra stringa y1y2…yn siano uguali. Il suo utilizzo nella crittoanalisi serve per determinare il valore della chiave
'''c) Si calcoli IC della parola “caccia”'''
Formula: [∑ da i=0 a i=25 fi*( fi – 1 )]/[n*( n – 1)]
frequenza f parola caccia : a = 2 c = 3 i = 1
n = lunghezza della parola caccia = 6
f0 = a = 2, (f1 = b = 0), f2 = c = 3, …. f8 = i = 1 …. (f25 = z = 0)
quindi:
IC = [2 ( 2 – 1 ) + 3 ( 3 – 1 ) + 1 ( 1 – 1 )]/[6 ( 6 – 1)] = 2/15
'''d) Si calcoli MIC delle parole “birba” e “babbo"'''
Formula: [∑ da i=0 a i=25 (fi*fi')]/n*n'
frequenza f parola birba: a = 1 b = 2 i = 1 r = 1
frequenza f' parola babbo: a’ = 1 b’ = 3 o’ = 1
n = lunghezza della parola birba = 5
n’ = lunghezza della parola babbo = 5
f0 = a, f1 = b, …. f8 = i …. f14 = o, f17 = r, …
MIC (birba, babbo)= [(1*1) + (2*3) + (1*0) + (1*0) + (1*0)]/(5*5) = 7/5
[[#s4]]
!!Funzioni MAC
Changed lines 25-26 from:
%red% ''APPELLO DEL 21/06/2005'' to:
%center%''APPELLO DEL 21/06/2005'' Changed lines 29-30 from:
to:
Changed lines 54-55 from:
%red% ''APPELLO DEL 20/01/2011'' to:
%center%''APPELLO DEL 20/01/2011'' Changed lines 58-59 from:
to:
%red%'''CHIESTO AL PROF.''' Changed lines 89-90 from:
%red% ''APPELLO DEL 14/09/2010'' to:
%center%''APPELLO DEL 14/09/2010'' Changed line 93 from:
to:
%red%'''CHIESTO AL PROF.'''
Changed lines 25-26 from:
''APPELLO DEL 21/06/2005'' to:
%red% ''APPELLO DEL 21/06/2005'' Changed lines 54-55 from:
''APPELLO DEL 20/01/2011'' to:
%red% ''APPELLO DEL 20/01/2011'' Changed line 89 from:
''APPELLO DEL 14/09/2010'' to:
%red% ''APPELLO DEL 14/09/2010''
Changed lines 1-2 from:
to:
[[Torna alla pagina di Crittografia -> Crittografia]] Added lines 114-115:
[[Torna alla pagina di Crittografia -> Crittografia]]
Added lines 1-113:
%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
|
|
