Corso di Crittografia UNIMI PDF

Preview

Summary

CrittografiaIlaria Salbesalbeilaria@gmailAppunti per il CdL Magistrale: Sicurezza InformaticaUniversità degli Studi di Milano Anno Accademico 2019/Indice 1 Introduzione 2 Crittografia Classica 2 Cifrari Simmetrici 2.1 Cifrario Affine 2.1 Cifrario Alberti 2.1 Cifrario Porta 2.1 Cifrario Playfair 2.1 ...

Description

Crittografia

Ilaria Salbe [email protected]

Appunti per il CdL Magistrale: Sicurezza Informatica Università degli Studi di Milano Anno Accademico 2019/2020

Indice 1 Introduzione

4

2 Crittografia Classica 2.1 Cifrari Simmetrici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Cifrario Af f ine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Cifrario Alberti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3 Cifrario Porta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.4 Cifrario Playfair . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.5 Cifrario di Hill . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.6 Cifrario di Vigenère . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.7 Cifrari a trasposizione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.8 Crittogrammi Beale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Macchine cifranti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Macchina Enigma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Probabilità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 10 . 13 13 14 14 15 17 18 20 21 22 29

3 Crittoanalisi 3.1 Cifrari a shift . . . . . . . . . . . . 3.1.1 Cifrario di Hill . . . . . . . 3.1.2 Metodo Kasiski . . . . . . . 3.1.3 Indice di coincidenza . . . . 3.1.4 Indice mutuo di coincidenza

. . . . .

30 30 31 31 32 35

4 Cifratura Simmetrica - DES 4.1 Cifratura di Feistel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Modalità operative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Sicurezza dei cifrari moderni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Approccio concreto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 Approccio asintotico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Crittoanalisi di DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.1 Attacco a forza bruta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.2 Crittoanalisi differenziale . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.3 Crittoanalisi Lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37 38 40 49 54 55 55 61 61 62 65

5 Cifratura AES 5.1 Decifratura di AES . . . . . . . . . . . . . . . . 5.1.1 Trasformazione Shift Rows inversa . . . 5.1.2 Trasformazione Mix Columns inversa . . 5.1.3 Trasformazione Substitute Bytes inversa 5.1.4 AddRoundKey Transformation . . . . . 5.1.5 Decifratura AES . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

67 77 77 78 78 79 79

6 DES: Cifratura multipla 6.1 DES Doppio . . . . . . . . . . . . . 6.1.1 Attacco Meet in the Middle 6.2 DES Triplo . . . . . . . . . . . . . 6.2.1 DES-X . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

80 . 80 . 81 . 82 . 85

. . . . .

. . . .

. . . . .

. . . .

1

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

7 Altri cifrari simmetrici 7.1 Blowf ish . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1.1 Espansione della chiave . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 RC5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Stream Cipher - Cifrari a flusso . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.1 Generazione di un keystream . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.2 RC4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.3 Attacchi a WEP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Crittografia asimmetrica 8.1 Cifrari ibridi . . . . . . . . . . . . . . . . . . 8.2 RSA . . . . . . . . . . . . . . . . . . . . . . 8.2.1 Generazione delle chiavi . . . . . . . 8.2.2 Cifratura e decifratura . . . . . . . . 8.2.3 "Piccolo Esempio" . . . . . . . . . . 8.2.4 Trapdoor Functions . . . . . . . . . 8.2.5 RSA e Teoria dei numeri . . . . . . . 8.2.6 Elevazione a potenza modulare . . . 8.2.7 Attacco di Wiener . . . . . . . . . . 8.2.8 Generazione di numeri primi grandi 8.2.9 Generazione di e e d . . . . . . . . . 8.2.10 Sicurezza di RSA . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

85 85 86 89 93 94 96 98

99 101 102 102 103 104 105 106 109 111 111 114 116

9 Altri cifrari asimmetrici 118 9.1 Crittostistema di El-Gamal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 9.2 Crittosistemi su Curve Ellittiche . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 10 Funzioni hash 123 10.1 MD4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 10.2 MD5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 10.3 SHA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 10.3.1 SHA-256, SHA-512, SHA-384 . . . . . . . . . . . . . . . . . . . . . . . . . 136 10.4 Whirpool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 10.5 Conclusioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 10.6 Marca temporale (timestamp) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 10.6.1 Digital Notary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 10.6.2 PGP Digital Timestamping Service . . . . . . . . . . . . . . . . . . . . . . 140 11 Message Authentication Code (MAC) 11.1 CBC-MAC . . . . . . . . . . . . . . . 11.2 MAC basati su funzioni Hash . . . . . 11.2.1 Metodo del segreto prefisso . . 11.2.2 Metodo del segreto suffisso . . 11.2.3 HMAC . . . . . . . . . . . . . . 11.3 Output troncato . . . . . . . . . . . . 11.3.1 Sicurezza HMAC . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

141 143 145 145 146 146 148 149

12 Firme digitali 12.1 Firma RSA . . . . 12.1.1 RSA-PSS . 12.2 Altri schemi e DSS 12.2.1 DSS . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

150 153 154 155 156

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . 2

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

13 PKI - Public Key Infrastructure

162

14 Accordo su chiavi 171 14.1 Scambio di chiavi Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 14.2 Puzzle di Merkle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 15 Secret Sharing 173 15.1 Schema (n, n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 15.2 Schema (k, n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174

3

1

Introduzione

La crittografia o criptografia (dal greco κρυπτ oζ [kryptós], "nascosto", e γραφια [graphía], "scrittura") è la branca della crittologia che tratta delle "scritture nascoste", ovvero dei metodi per rendere un messaggio "offuscato" in modo da non essere comprensibile/intelligibile a persone non autorizzate a leggerlo. La crittologia è la scienza che si occupa della comunicazione in forma sicura e di solito segreta. Da un lato comprende l’ideazione di metodi sempre più sicuri per occultare il reale significato di determinati segni (crittografia), dall’altro riguarda la decifrazione di testi occultati senza conoscerne a priori il metodo usato (crittoanalisi). Quindi, la crittoanalisi è la scienza di risolvere i crittosistemi per recuperare l’informazione nascosta. Crittografia e crittoanalisi sono le due facce della stessa medaglia, una medaglia che nel corso della storia ha dato più importanza all’una o all’altra, alternativamente. Fino dall’antichità l’uomo ha sentito l’esigenza di trasmettere messaggi segreti; infatti i primissimi esempi di crittografia sono stati scoperti in alcuni geroglifici egiziani risalenti a più di 4500 anni fa. Nella città di Menet Khufu, che sorge sulle sponde del Nilo, è stata ritrovata una delle più antiche testimonianze di alterazione di una scrittura: si tratta di una incisione funeraria di circa 4000 anni fa realizzata sulla tomba di un nobile. In questo caso, l’intento della trasformazione consisteva semplicemente nel conferire dignità e onoreficenza alla persona defunta. Nello stesso periodo, tuttavia, cominciarono a comparire anche trasformazioni aventi lo scopo di rendere misterioso ed arcano il significato delle parole. Fonti preziose di esempi di scritture segrete sono i testi sacri. Nel Vecchio Testamento gli storici hanno evidenziato 3 tipi di trasformazioni: l’Atbash, l’Albam e l’Atbah. La prima è universalmente accettata; le seconde sono maggiormente discusse. L’Atbash ebraico, è una tecnica di trasformazione ad alfabeto capovolto: il primo carattere dell’alfabeto viene sostituito con l’ultimo dell’alfabeto, il secondo carattere viene sostituito con il penultimo, e così via. Il nome deriva dalla regola di trasformazione. Infatti la prima lettera dell’alfabeto ebraico è Aleph, l’ultima è Taw, la seconda è Beth e la penultima è Shin. Concatenando le iniziali di queste lettere nell’ordine si ottiene la parola Atbash. L’Atbash viene utilizzato nel libro del profeta Geremia per cifrare il nome della città di Babilonia. L’Albam, invece, richiede che l’alfabeto venga diviso in due parti e che ogni lettera venga sostituita con la corrispondente dell’altra metà. Infine, l’Atbah richiede che la sostituzione soddisfi una relazione di tipo numerico. Le prime nove lettere dell’alfabeto vengono sostituite in modo tale che la somma della lettera da sostituire e della lettera sostituente risulti uguale a 10. Quindi, per esempio, Aleph (prima lettera dell’alfabeto) viene sostituita con Teth (nona lettera dell’alfabeto). Per le restanti lettere dell’alfabeto deve valere una regola simile con somma pari a 28 in decimale (per esempio, la 13-esima lettera viene sostituita con la 15-esima, etc.). In India, invece, forme di crittografia furono concretamente praticate. In diversi testi indiani, infatti, sono presenti riferimenti a forme di scritture segrete. Nell’Artha-Sastra, un testo classico sugli affari di stato, si sottolinea l’importanza delle scritture segrete nei servizi di spionaggio, mentre nel Latila-Vistara, un libro che esalta le virtù di Budda, si narra di come questi stupisse il proprio insegnante parlando di scritture perpendicolari, disordinate, etc.. Nel Kama-Sutra, invece, tra le 64 arti (yogas) che la donna deve conoscere e praticare c’è l’arte delle scrittura segreta. La 44-esima e, in particolare, la 45-esima arte (mlecchita-vikalpa) trattano di regole di trasformazione delle parole basate essenzialmente sulla sostituzione dei caratteri. Nessun esempio dimostra le potenziali conseguenze della crittoanalisi in modo più drammatico del processo a Maria di Scozia, il cui esito dipese esclusivamente dallo scontro tra i suoi cifratori e i decrittatori di Elisabetta I. Nel 1586 Maria Stuarda, regina di Scozia, fu condannata a morte per aver cospirato contro la cugina Elisabetta. La congiura, organizzata da Anthony Babington, prevedeva: • La liberazione di Maria dalla prigionia in Inghilterra; • L’uccisione di Elisabetta; 4

• Una ribellione alla religione protestante. Sir Francis Walsingham, segretario di stato, provò che Maria aveva preso parte alla congiura. Maria e Babington comunicavano grazie a • Un corriere (Gilbert Gifford) • Un birraio, che nascondeva i messaggi dentro lo zipolo delle botti di birra • Un cifrario, costituito da: – 23 simboli che sostituivano le lettere; – 35 simboli, che sostituivano parole o frasi; – 4 nulle e un simbolo per le doppie. Gifford consegnava a Walsingham tutti i messaggi, che venivano decifrati da Thomas Phelippes. Maria firmò la sua condanna a morte rispondendo alla lettera di Babington. Babington e complici furono arrestati e squartati vivi. Maria fu decapitata l’8 febbraio 1587. La ricerca di nuovi sistemi crittografici diede un grande impulso alla crittografia durante il periodo antecedente la Seconda Guerra Mondiale. Già dall’inizio del XX sec, infatti, stava nascendo l’esigenza di poter usufruire di una crittografia sicura e, soprattutto, veloce e facilmente utilizzabile: per questo nacquero le prime macchine cifranti. Fin dalla fine del XIX sec, lo sviluppo della crittografia rese necessaria una progressiva automatizzazione dei metodi di cifratura e decifratura, le macchine cifranti nacquero quindi non tanto per rendere i sistemi crittografici più sicuri, ma semmai per velocizzarli. La più famosa di queste macchine è sicuramente Enigma, brevettata dall’ingegnere tedesco Arthur Scherbius nel 1918 e adottata dell’esercito e dalla marina tedesca durante la Seconda Guerra Mondiale. Nell’agosto del 1939 i Britannici costituirono la scuola dei codici e dei cifrari a Bletchley Park, dove reclutarono i migliori crittoanalisti, matematici e scienziati. Sfruttando anche le conoscenze raggiunte dagli alleati polacchi, durante la guerra, gli inglesi continuarono a forzare sistematicamente i messaggi cifrati con Enigma e dal 1941 anche quelli cifrati con la più sofisticata macchina Lorenz. La crittografia giocò quindi un ruolo di fondamentale importanza durante tutta la durata della guerra e, ad esempio, fu fondamentale per lo Sbarco in Normandia. Infatti Eisenhower e Montgomery erano in grado di leggere tutti i messaggi degli alti comandi tedeschi, che usavano la macchina Lorenz; ebbero così conferma che Hitler aveva creduto alla falsa notizia di un imminente sbarco alleato nei pressi di Calais, e aveva concentrato le sue migliori truppe in quella zona. Poterono quindi ordinare lo sbarco in Normandia sicuri che avrebbe incontrato ben poca resistenza. La crittografia trova spazio anche in letteratura. Un esempio è Il codice Da Vinci di Dan Brown. La crittografia moderna si differenzia notevolmente dalla crittografia di cui si è parlato fin ora; l’avvento dei computer infatti ha rivoluzionato profondamente sia i sistemi crittografici sia il modo di vedere e utilizzare la crittografia. Molti sistemi crittografici analizzati in precedenza e considerati ragionevolmente sicuri fino al XIX secolo, possono oggi essere forzati in tempi brevissimi grazie alla velocità di elaborazione del computer. Nell’era dei computer la crittografia è "uscita dai campi di battaglia" e viene utilizzata da ogni persona, più o meno consapevolmente, nella vita di tutti i giorni: per prelevare soldi con un bancomat, nell’effettuare acquisti su internet o, semplicemente, chiamando con un telefono cellulare. La crittografia è diventata uno strumento di massa, atto a proteggere i segreti di stato tanto quanto i dati che noi vogliamo, o almeno vorremmo, rimanessero privati. La crittografia moderna si occupa del progetto e della valutazione di metodi e tecniche per la protezione dell’informazione, non solo segretezza delle comunicazioni. É fondata su solide basi matematiche. Possiamo distinguere tre fasi principali nella storia della crittografia: 5

• Primo stadio: dalle prime civiltà fino al secolo scorso. Gli algoritmi sono sviluppati e implementati "a mano". • Secondo stadio: seconda guerra mondiale con l’apparizione delle prime macchine cifranti. • Terzo stadio: ultimi 50 anni. Si sviluppa l’utilizzo di computer e fondamenti matematici. Nei documenti fisici, a differenza dei documenti digitali, la copia è distinguibile dall’originale; l’alterazione lascia tracce e la prova di autenticità si basa su caratteristiche fisiche (firma, ceralacca, ...). La firma digitale può essere un metodo per provare l’autenticità di un documento digitale. Introduciamo ora il concetto di Romantic Cryptography noto anche come "Matching without embarrassment". E se desideri esprimere il tuo amore a qualcuno, ma temere le conseguenze se lui o lei non restituisce i tuoi sentimenti? É un problema secolare: quanti di noi conoscono qualcuno che chiede a un amico di parlare con lui/lei per "vedere se le/gli piaccio?" Mostriamo come Alice e Bob possono stabilire se si amano a vicenda, ma senza l’imbarazzo di rivelare che lo fanno se l’altra parte non condivide i propri sentimenti. Se sono interessati devono mettere prima l’asso rosso e poi quello nero, se no al contrario, poi mettono le carte nel mazzo e shiftano le carte. Se compaiono 3 carte rosse di seguito, sarà un sì. Una terza persona se vede che esce un no, non capisce chi ha detto di no. Il problema è che se un partecipante avvia il protocollo è perché è interessato. La soluzione è quella di fare incontri casuali. Un protocollo o schema definisce le interazioni fra le parti per ottenere le proprietà di sicurezza desiderate, dove le parti sono le entità coinvolte nello schema, mentre le proprietà di sicurezza sono gli obiettivi di sicurezza che si vogliono ottenere con lo schema. Quello che si vuole ottenere è un tubo, ovvero un cana...