Giovedì 29 Giugno 2006

- Sezione 6 - Dal 1994 a ieri - Approfondimenti

Crittografia

Il concetto centrale della crittografia è quello di messaggio, cui sono associati

  • un testo,

  • un significato,

  • un mittente che genera il messaggio,

  • un destinatario (o più) cui è destinato il messaggio,

  • un terzo (ostile) che è interessato a capire il messaggio: è obbiettivo del mittente e del destinatario che questo non avvenga.

La crittografia risolve due problemi:

a. rendere un messaggio comprensibile solo a un certo insieme di interlocutori: un mittente e uno o più destinatari (e quindi a tenere il significato nascosto ai terzi),

b. garantire la autenticità (cioè la originalità e la provenienza) di un certo messaggio verso una (ampia) platea di destinatari.

Lo scenario generale per il problema è:

un mittente, utilizzando un metodo M, trasforma il testo originario del messaggio (detto in chiaro) in un altro (detto in scuro) e lo spedisce, su un canale di trasmissione, al destinatario che, con un metodo D, recupera il testo il testo originale e ne capisce il significato; il canale può essere accessibile a un terzo, potenzialmente ostile: il problema sta nell’impedire che questi possa capire il significato del messaggio. Quindi per mantenere riservata una comunicazione occorre:

  • avere una coppia di metodi (coordinati) per il passaggio chiaro-scuro e scuro-chiaro rispettivamente;

  • distribuire i metodi tra gli interlocutori;

  • assicurarsi che un terzo non possa (senza conoscere preventivamente i metodi) recuperare il testo in chiaro se ha intercettato il testo in scuro.

legge di Kerckhoffs: la sicurezza di un sistema di crittografia non deve dipendere dalla segretezza dell’algoritmo ma solo dalla segretezza della chiave.

Due sono i mestieri della crittografia:

  1. il crittografo: escogita nuove maniere di crittografare, cioè nuovi modi con cui un mittente e un destinatario si possono scambiare un messaggio senza

  2. il cripto-analista (o semplicemente analista); ha due obbiettivi: esaminare uno o più testi in scuro per scoprire il metodo per tradurli in chiaro; oppure studia gli algoritmi (M e D) per capire come si può ricostruire il testo in chiaro senza conoscere la chiave.

Cronologia della crittografia fino all’avvento dell’informatica

quinto secolo a.c. Scìtala spartana ()

primo secolo a.c. sostituzione di Cesare () sostituzione monoalfabetica

nono secolo analisi delle frequenze (dallo studio critico delle massime di Maometto)

decimo secolo atbash e studio della bibbia

‘400 fiorire della crittografia nel rinascimento: disco rotante di Leon Battista Alberti

‘500 fiorire della criptoanalisi

1586 congiura di Babington e condanna di Maria Stuarda

1586 chiffre indéchiffrable d i Blaise de Vigenère sostituzioni polialfabetiche

‘600 sostituzioni isofrequenziali

‘600 grand chiffre di Antoine e Bonaventure Rossignol sostituzione sillabica

‘700 uso sistematico della crittografia (e della criptoanalisi)

1822 Jean-François Champollion decifra i geroglifici

metà ‘800 invenzione del telegrafo: necessità della crittografia “di massa”

seconda metà ‘800 Charles Babbage e Friedrich Wilhelm Kasiki decrittano la cifra di Vigenère

‘800 la crittografia nella letteratura: Conan Doyle (L’avventura dei danzatori), Allan Poe (Lo scarabeo d’oro), il pamphlet Ward-Bbeale.

1883 Auguste Kerckhoffs: La cryptographie militaire

fine ‘800 invenzione della radio: nuove necessità di crittografia

1917 il telegramma di Arthur Zimmermann

1918 il sistema ADFGVX e George Painvin

1918 Arthur Scherbius inventa Enigma (una estensione del disco di Alberti)

1926 le forze armate tedesche adottano Enigma a tre dischi

1931 Hans-Tilo Schmidt passa due manuali di Enigma ai francesi che li passano ai polacchi.

1932 Marian Rejewski decripta Enigma, a causa di una ripetizione presente all’inizio di ogni messaggio

1938 Enigma viene migliorata: i tre dischi sono scelti tra cinque e aumentano da sei a dieci le connessioni del pannello, rendendo così molto difficoltoso il metodo Rejewski

1939 i polacchi cedono a francesi e inglesi i risultati raggiunti

1939 si insedia il gruppo di Bletchley Park, che con maggiori risorse decriptano la versione migliorata di Enigma (col metodo Rejewski)

1940 Alan Turing introduce un metodo alternativo a quello di Rejewski indispensabile quando i tedeschi tolgono la ripetizione dai messaggi

1943 viene costruito Colossus per decriptare il codice Lorenz simile a Enigma, ma molto più complessa)

1953 Michael Ventris e John Chadwick (in seguito agli studi di Alice Kober) decifrano il “lineare B” (scrittura sillabica del greco antico)

Cronologia della crittografia dopo l’avvento dell’informatica

1976 il National Bureau of Standard adotta il DES (Data Encription Standard) nella versione con chiave a 56 bit (sviluppato da Horst Feistel alla IBM col nome i Lucifer alla fine dgli anni ‘60)

1976 Whitfield Diffie, Martin Hellman, Ralph Merkle risolvono il problema dello scambio delle chiavi e propongono lo schema di crittografia a chiave pubblica

1977 Ronald Rivest, Adi Shamir, Leonard Aldeman sviluppano la crittografia RSA

L’algoritmo DES

Il DES (Data Encription System) è un algoritmo simmetrico, cioè, con riferimento alla figura 1, la chiave M e la chiave D sono eguali e l’algoritmo M è il “simmetrico” (vale a dire con le stesse operazioni eseguite nella sequenza inversa) dell’algoritmo D.

……………………………

Lo scambio di chiavi

Il problema è quello di far si che due corrispondenti possano scambiarsi una chiave (un numero), da usarsi per la crittografia simmetrica prima di iniziare la corrispondenza criptata, in “sicurezza”, cioè senza che un terzo possa scoprirla. La soluzione fu proposta da Diffie, Hellman e Merkle nel 1976.

È immediato che se a, x e y sono interi allora:

a (xy) = (a x ) y = (a y ) x .

Se p è un numero primo e a < p , è facile verificare che la precedente uguaglianza rimane vera nell’aritmetica “modulo p”:

a (xy) mod p = (ax ) y mod p = (ax mod p ) y mod p = (ay ) x mod p = (ay mod p ) x mod p.

Allora Alice e Bob possono condividere una chiave numerica nella seguente maniera:

  1. scelgono, accordandosi per telefono, gli interi a < p, con p primo;

  2. Alice pensa un numero intero x, calcola A = a x mod p e lo comunica per telefono a Bob;

  3. Bob pensa un numero intero y, calcola B = a y mod p e lo comunica per telefono ad Alice;

  4. Alice calcola C = B x mod p;

  5. Bob calcola C = A y mod p (per quanto osservato in precedenza i due numeri sono eguali!);

  6. Carla che ha ascoltato a, p, A, B sulla linea telefonica non può in nessun modo costruire C.

  7. Alice e Bob possono usare C come chiave per criptare i loro messaggi (per esempio con DES)

Si noti che 1 £ A £ p; Carla non riesce a ricostruire x, pur conoscendo a, p, A perché sono infiniti i numeri a x che divisi per p hanno come resto A; analogamente per y. Naturalmente, poiché anche 1 £ C £ p Carla potrebbe provare tutti i C possibili per decrittare i messaggi di Alice e Bob: per evitare ciò basta scegliere p abbastanza grande.

Home Tour virtuale Sezione 6 Approfondimenti