Cifrari a chiave simmetrica e asimmetrica, algoritmo RSA e Vernam

Cifrari a chiave simmetrica e asimmetrica

Sistemi e reti 5ª

Istituto Tecnico Indirizzo Tecnologico Settore Informatica e Telecomunicazioni Articolazione Informatica Prof. Marcolin MattiaCifrario a chiave simmetrica

• Cifrario di Vernam -Cifrario di Vernam

Noto anche con il nome di cifrario One -Time Pad, è un sistema crittografico a chiave simmetrica inventato da G.Vernam nel 1917 Come sarà chiaro dalla trattazione, questo cifrario si caratterizza per essere: .

• estremamente efficiente da un punto di vista computazionale
• semplice da implementare utilizzando un linguaggio di programmazione
• un cifrario inviolabile o perfettamente sicuro
• Questo cifrario prevede che la chiave segreta, condivisa fra i due interlocutori, debba avere le seguenti due caratteristiche:
• dev'essere generata in modo casuale
• deve avere una lunghezza pari a quella del messaggio in chiaro che si vuole cifrare Sistemi e reti Cifrario di Vernam @Mattia Marcolin 3One-Time Pad

La stessa chiave non può essere utilizzata per cifrare due messaggi M ed M', ossia è una chiave monouso

• Se si utilizzasse la medesima chiave significherebbe che nel complesso si è cifrato un messaggio in chiaro MM' con una chiave inferiore rispetto alla sua lunghezza, violando il vincolo sulla lunghezza della chiave richiesto dal cifrario Messaggio in chiaro Messaggio cifrato Algoritmo di cifratura Vernam Chiave segreta Messaggio in chiaro Messaggio cifrato Algoritmo di cifratura Vernam Chiave segreta > Messaggio cifrato Algoritmo di cifratura Vernam Chiave segreta Messaggio in chiaro Sistemi e reti Cifrario di Vernam @Mattia Marcolin 4Algoritmo di cifratura

L'algoritmo di cifratura effettua l'operazione di XOR bit-a-bit tra il messaggio in chiaro e la chiave . Si ricorda che la tabella di verità dell'operatore logico XOR è A B A XOR B 0 0 0 0 1 1 1 0 1 1 1 0 Sistemi e reti Cifrario di Vernam @Mattia Marcolin 5Algoritmo di decifratura

• Date le proprietà dell'operatore XOR, il destinatario è in grado di riottenere il messaggio il chiaro eseguendo nuovamente la XOR tra il messaggio cifrato e la chiave segreta . Per esempio, supponiamo di dover trasmettere il messaggio in chiaro 10100011 . mittente e destinatario devono conoscere una chiave segreta generata in modo casuale e avente la medesima lunghezza del messaggio in chiaro, per esempio immaginiamo che la chiave sia 11000111
• il messaggio cifrato risulta essere 01100100 Fase di cifratura 1 0 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 1 1 0 0 1 0 0 Fase di decifratura 0 1 1 0 0 1 0 0 1 1 0 0 0 1 1 1 1 0 1 0 0 0 1 1 Sistemi e reti Cifrario di Vernam @Mattia Marcolin 6Efficienza computazionale

• All'interno dell'ALU è presente un circuito hardware che effettua l'operazione di XOR fra sequenze di bit, con tempi di esecuzione estremamente inferiori rispetto a operazioni matematiche più complesse
• Poiché ogni bit del messaggio viene cifrato indipendentemente dagli altri, il cifrario di Vernam è facilmente parallelizzabile sfruttando più core o processori
• L'operazione di cifratura e decifratura sono identiche: questo semplifica ulteriormente l'implementazione e mantiene basso il carico computazionale sia per cifrare che per decifrare i dati Sistemi e reti Cifrario di Vernam @Mattia Marcolin 7Cifrario inviolabile

Il cifrario di Vernam è l'unico cifrario che gode della proprietà di essere inviolabile, ossia immune da qualunque tipologia di attacco crittografico

• E' immune da qualunque tipologia di attacco poiché il messaggio cifrato è privo di qualsivoglia relazione statistica con il messaggio in chiaro
• Non è possibile violare il messaggio neppure utilizzando l'attacco a forza bruta: eseguendo l'operazione di XOR bit-a-bit tra il messaggio cifrato lungo N bit e ogni possibili chiave della medesima lunghezza, si otterranno tutti i possibili messaggi di N bit . dato infatti un qualsiasi testo cifrato lungo N, vi è una chiave lunga N che produce un testo in chiaro di lunghezza N
• tra questi messaggi, un certo numero saranno di senso compiuto. Tra questi, sarà impossibile per l'attaccante stabilire il messaggio in chiaro cifrato dal mittente Sistemi e reti Cifrario di Vernam @Mattia Marcolin 8Cifrario inviolabile .

Si consideri l'esempio sottostante, decifrando il medesimo messaggio cifrato con due chiavi distinte della medesima lunghezza, si sono ottenuti due messaggi di senso compiuto, rendendo così impossibile per l'attaccante stabilire il messaggio che il mittente ha trasmesso

• Messaggio cifrato: ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS Chiave: pxlmvmsydofuyrvzwc tnlebnecvgdupahfzzlmnyih Messaggio decifrato: mr mustard with the candlestick in the hall .

Messaggio cifrato: ANKYODKYUREPFJBY0JDSPLREYIUNOFD0IUERFPLUYTS Chiave: pftgpmiydgaxgoufhklllmhsqdqogtewbqfgyovuhwt Messaggio decifrato : miss scarlet with the knife in the library Sistemi e reti Cifrario di Vernam @Mattia Marcolin 9Svantaggi cifrario di Vernam

• Sebbene questo cifrario garantisca una sicurezza ineguagliabile, nella pratica è difficilmente utilizzabile in quanto generare una chiave realmente casuale lunga quanto il messaggio da trasmettere è un operazione computazionalmente onerosa, specialmente per messaggi lunghi o per trasmissioni continue . Nonostante i limiti esposti, sembra che questo cifrario sia stato usato effettivamente negli anni della guerra fredda dai servizi segreti dell'Est Sistemi e reti Cifrario di Vernam @Mattia Marcolin 10Cifrario a chiave simmetrica

Algoritmo DES (Data Encryption Standard)

Si tratta di un cifrario a chiave simmetrica realizzato dall'IBM e pubblicato nel 1975, due anni dopo divenne lo standard per la cifratura dei dati federali negli Stati Uniti . Prevede che la chiave segreta condivisa fra i due interlocutori abbia una lunghezza di 56 bit

• È stato il cifrario più utilizzato al mondo fino al 2001, quando divenne vulnerabile ad un attacco a forza bruta
• il progresso tecnologico ha infatti fatto sì che i calcolatori dei primi anni duemila, in tempi ragionevoli, erano in grado di decifrare un messaggio provando tutte le 256 ~ 7.2 * 1016 chiavi
• ai nostri giorni il cifrario a chiave simmetrica più utilizzato è l'algoritmo AES (Advanced Encryption Standard) che studieremo in seguito Sistemi e reti DES @Mattia Marcolin 12Algoritmo DES: elaborazione chiave

La chiave segreta, prima di essere utilizzata dell'algoritmo di cifratura o decifratura, subisce la seguente elaborazione:

• ad ogni blocco di 7 bit, viene aggiunto in coda il corrispondente bit di parità pari
• dopo questa elaborazione, si ottiene una sequenza di 64 bit Chiave (56 bit) 1 0 111010 0 1 1 1010 Chiave elaborata (64 bit) 1 0 1 1 1 01 10 . .. 0 1 1 10100 7 bit Bit parità pari Bit parità pari Sistemi e reti DES @Mattia Marcolin 13Permutazione iniziale dei bit del blocco

Il messaggio viene scomposto in blocchi aventi una lunghezza di 64 bit, con un riempimento dell'ultimo blocco se inferiore a tale lunghezza

• Nelle slide successive vedremo i passaggi per cifrare un singolo blocco; naturalmente se il messaggio si compone di m blocchi sarà necessario eseguire per ciascuno di essi le elaborazioni che presenteremo N bit Messaggio in chiaro 64 bit 000 .. 0 Blocco 1 Blocco 2 Blocco 3 Blocco 4 Sistemi e reti DES @Mattia Marcolin 14Algoritmo di cifratura DES: permutazione iniziale

Si permutano i 64 bit del blocco secondo una mappa prefissata che denomineremo permutazione iniziale PI

• Permutare una sequenza di bit significa variare la posizione dei i bit secondo una certa mappa prefissata, la quale viene codificata utilizzando un array di dimensione pari alla lunghezza della sequenza di bit da permutare
• Ad esempio, si immagini di avere la sequenza 10011001, se l'array che codifica la mappa di permutazione risulta essere [3,0,1,4,2,7,5,6], la sequenza permutata è 00111010 Array di permutazione 3 0 1 4 2 7 5 6 Sequenza originale 1 0 0 1 1 0 0 1 0 0 1 1 1 0 1 0 Sequenza permutata Sistemi e reti DES @Mattia Marcolin 15Algoritmo di cifratura DES: permutazione iniziale

N bit Messaggio in chiaro 64 bit Blocco 1 Blocco 2 Blocco 3 000 Blocco 4 . . 0 PI Blocco 1 permutato Sistemi e reti DES @Mattia Marcolin 16Algoritmo di cifratura DES: round

• Partendo dalla sequenza di 64 bit ottenuta dopo aver svolto la permutazione iniziale sui bit del blocco, l'algoritmo prevede di effettuare 16 round . Ogni singolo round comprende un insieme di operazioni che portano, al suo termine, l'ottenimento una nuova sequenza di 64 bit che sarà l'input del round successivo
• Da un punto di vista logico, la sequenza di 64 bit che fungono da input ad un generico round i vengono suddivisi in due blocchi chiamati rispettivamente:
• Li: composto dai 32 bit più significativi della sequenza binaria
• R ¡: composto dai 32 bit meno significativi della sequenza binaria Sistemi e reti DES @Mattia Marcolin 17Algoritmo di cifratura DES: round

Blocco 1(in chiaro) 64 bit PI (permutazione iniziale) 64 bit Input round 1 Lo Ro 64 bit Round 1 64 bit Output round 1 L1 = Ro | R1 = Lo @ F(Ro , K1) = Input round 2 64 bit Round 2 64 bit Output round 2 L2 = R1 | R2 = L1 + F(R1 , K2) Input round 3 Round 16 64 bit Output round 16 L16 = R15 (R16 = L15 @ F(R15 , K16) 64 bit PI-1 (permutazione iniziale inversa) 64 bit Blocco 1(cifrato) Sistemi e reti DES @Mattia Marcolin 18Algoritmo di cifratura DES: round

Si indicano con Lo e Ro rispettivamente il blocco composto dai 32 bit più significativi e il blocco composta dai 32 bit meno significativi dalla sequenza di 64 bit ottenuta dopo la permutazione iniziale . Il primo round riceve come input la sequenza LoRo, sulla quale vengono eseguite delle elaborazioni che porteranno ad ottenere una nuova sequenza di 64 bit L1R1 dove:

• L1 = Ro
• R1 = Lo + F( R), K1)
• Per calcolare R è necessario definire: . K1 : sequenza di 48 bit prelevati dai 64 bit della chiave processata secondo una mappa prefissata diversa ogni round . F(R) , K1): funzione di Feistel riceve come parametri Ro(32 bit) e K1 (48 bit) e produce in output una sequenza di 32 bit, sulla quale verrà svolta l'operazione di XOR bit a bit con la sequenza di bit Lo