Disegno, analisi e testing di sistemi crittografici asimmetrici basati sul rumore

La prima proposta di utilizzo dei codici correttori d’errore in crittografia risale alla fine degli anni settanta, quando R.J. McEliece propose un crittosistema a chiave pubblica basato sui codici di Goppa, opportunamente mascherati.
La sicurezza di questi sistemi risiede principalmente nel problema NP-completo della decodifica di un codice lineare del quale non sia nota la struttura. Vedremo nel corso di questa tesi che un altro aspetto fondamentale ai fini della sicurezza risiede nella scelta del particolare codice utilizzato: un possibile candidato deve infatti rispettare alcuni vincoli che saranno esposti nel corso del lavoro.
I codici di Goppa sono risultati essere uno strumento crittografico valido perche' hanno particolari proprieta' che li rendono, sotto certe ipotesi, indistinguibili da un codice qualsiasi.
Malgrado siano ormai passati piu' di trent’anni dalla loro scoperta e definizione, non sono ancora stati trovati algoritmi efficienti in grado di riconoscere un codice di Goppa da una sua permutazione casuale ed e' questo uno dei motivi per i quali McEliece decise di adottarli. Uno degli obiettivi della tesi consisteva proprio nel capire il motivo che spinse l’autore del crittosistema a scegliere ed utilizzare i codici di Goppa tra i tanti possibili codici correttori presenti in letteratura.
I crittosistemi basati sui codici correttori d’errore prevedono una cifratura effettuata tramite una chiave pubblica che descrive un codice lineare qualsiasi, ma che in realta' e' il risultato di un’adeguata trasformazione del codice di Goppa originario (inteso in termini di matrice generatrice o di parita'), il quale, invece, rappresenta la chiave privata. Agli occhi esterni, la chiave pubblica appare come un codice lineare casuale per cui non sono noti algoritmi di decodifica. Di conseguenza, per poterla effettuare, occorre risolvere un problema NP-completo, cio' che risulta essere computazionalmente intrattabile. L’utente legittimo, invece, avendo a disposizione la chiave privata e' in grado di utilizzare gli appositi metodi di decodifica del codice, che risultano essere molto veloci e che costituiscono la trapdoor del crittosistema. Per ogni blocco cifrato viene aggiunto del rumore casuale di peso opportuno, ossia tale da poter essere rilevato ed eliminato durante la decrittazione.
Proprio la casualita' e' uno degli elementi rilevanti del sistema di McEliece, dato che esso fu il primo ad utilizzare in modo cosi' influente la generazione casuale di bit.
Nonostante questi elevati livelli di sicurezza (il sistema in questione risulta essere ancora oggi inviolato), va osservato che c'e' stato un suo scarso impiego a livello pratico, per questioni legate alle elevate dimensioni della chiave pubblica, all’impossibilita' di commutare le chiavi per ottenere metodi di firma digitale e perche' degli errori aggiuntivi, indesiderati ed incorreggibili potrebbero presentarsi a causa di comuni problemi di trasmissione. Inoltre, in particolari situazioni, come ad esempio l’utilizzo di chiavi deboli o prevedibili o in presenza di blocchi uguali e crittati con diversi errori casuali, il livello di sicurezza scende notevolmente.
Lo studio dei meccanismi che governano il crittosistema costituiva il secondo obiettivo di questo lavoro, unito ai motivi che hanno impedito negli anni la sua diffusione tra gli utenti.