Temi Desame

Torna alla pagina di Crittografia

 :: Esercizi di Crittografia ::

Esercizi svolti by Licia

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..

Cifratura classica

Vigenere

APPELLO DEL 15/02/2011

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)] = 4/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/25

APPELLO DEL 20/01/2011

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.

APPELLO DEL 10/09/2010

a) Descrivere i principali tipi di attacco conosciuti e fornire un esempio per ciascuno scenario Esistono 5 tipi di attacco:

1. 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)
2. 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
3. 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)
4. 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
5. Chosen Text Attack: in cui l’avversario può ottenere la cifratura e la decifratura di coppie di testi in chiaro/cifrato – esempio??

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.

APPELLO DEL 09/02/2010

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

APPELLO DEL 19/01/2010

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

APPELLO DEL 25/09/2009

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

c) Utilizzare la parola chiave "viva i farabutti" per cifrare il testo in chiaro "giornalisti" e decifrare il testo cifrato "qpgruatfourn

Attach:playfair.gif

APPELLO DEL 11/07/2009

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.

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.

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.gif Attach:HILL2.gif Attach:HILL3.gif

Cifratura simmetrica

APPELLO DEL 25/09/2010

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ⁿ”

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ⁿ 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ⁿ)

ESEMPIO: se ho un blocco di 3 bit, ho i seguenti valori: 000, 001, 010, 011, 100, 101, 110, 111 = 24 = 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*2ⁿ

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ⁿ. Quindi sapendo che DES utilizza blocchi di 64bit la grandezza della tabella sarà 64*2⁶⁴ , mentre AES prevede 128bit, quindi la grandezza della tabella sarà 128*2¹²⁸

APPELLO DEL 09/02/2010

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.

APPELLO DEL 04/11/2010

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:

Y = DESk2(DESk1(x))

La decifratura è analoga alla cifratura, ma richiede l’applicazione delle chiavi in ordine inverso:

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⁵⁶, 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⁵⁶ possibili chiavi k1, memorizzando i testi cifrati in una tabella ( che viene eventualmente ordinata). Successivamente viene decifrato C usando tutte le 2⁵⁶ 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⁴⁸ 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.

APPELLO DEL 12/09/2009

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

APPELLO DEL 02/02/2010

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: C₀ = N C_i = Ek(Mi) XOR C_i-1 per i = 1,2,3…,n

a) Scrivere la funzione di decifratura

C0 = N

C1 = E_k(M1) XOR C0

C2 = E_k(M2) XOR C1 ….

La decifratura è la seguente

M1 = D_k (C1 XOR C0)

M2 = D_k (C2 XOR C1)….

Quindi la funzione di decifratura è: Mi = D_k (Ci XOR C_i-1) per i = 1,2,3….,n

Funzioni MAC

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

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))

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

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’) = Em1(IV)

Quindi questa proprietà non è soddisfatta

Torna alla pagina di Crittografia