La parola "crittografia" significa "parole nascoste" ed è l'arte di comunicare con il proprio interlocutore usando messaggi non direttamente intelleggibili, cioè, appunto, "criptati" (o "cifrati"). Due sono le qualità che deve avere una comunicazione di una certa importanza, e cioè segretezza ed autenticità. Accanto alle tecniche per comunicare in modo riservato sono state quindi sviluppate anche procedure per garantire che i messaggi non siano stati modificati da terze persone e provengano proprio dall'interlocutore che ci si attende. Entrambe queste tecniche sono sempre state fondamentali per i militari, ed attualmente sono sempre più al centro dell'interesse dato lo sviluppo della rete informatica, ed al desiderio di riservatezza ed autenticità delle comunicazioni che su essa si svolgono.

     Oltre all'impiego negli stessi ambiti inoltre, crittografia ed autenticazione sono intimamente connesse in quanto con una si riesce a fare quanto si fa con l'altra. Se per esempio solo A e B (che in questo ambito di solito vengono chiamati Alice e Bob, aggiungendo Carol quando serve una terza persona) conoscono un modo di cifrare dei messaggi, quando a B arriva un messaggio criptato, può essere sicuro che l'ha scritto A, perché un terzo C non può sperare che modificando a caso il testo cifrato si ottenga qualcosa che, una volta decifrato, abbia significato coerente ne, tanto meno, proprio un certo significato distorto che si volesse far arrivare a B. La crittografia può quindi essere usata per l'autenticazione, e questo è sempre stato evidente, ma anche l'inverso è vero, ed è acquisizione recentissima (Rivest, '97), generata dagli sforzi degli studiosi tesi a dimostrare che limitare l'uso di tecniche crittografiche è inutile, potendo queste essere sostituite da tecniche di autenticazione su cui finora nessun governo ha mai pensato di poter imporre restrizioni.

     Le tecniche crittografiche sono state usate fin dall'antichità. Per esempio, Giulio Cesare comunicava con i suoi ufficiali utilizzando una semplice "traslazione" delle lettere dell'alfabeto. Per semplificare il caso reale si potrebbe pensare che sostituisse ogni lettera con la successiva (considerando la "a" come successiva di "z"), cosicché il messaggio:

          "Attaccheremo il campo nemico all'alba, dalle colline."

     diventerebbe:

          "Buubdifsfnp lm dbnqp ofnldp bmm'bmcb, ebmmf dpmmlof."

     Si può facilmente cambiare questo schema, creandone tutta una famiglia, semplicemente decidendo di sostituire una lettera non con la successiva ma con quella che si trova due, tre, ecc., posti più in là nell'alfabeto. Per esempio sembra che il generale romano usasse il valore quattro per cifrare i suoi messaggi.

     Già questo semplice esempio contiene gran parte dei concetti fondamentali della crittografia. Si hanno da una parte i messaggi "in chiaro", cioè i messaggi in forma comprensibile, scritti in un dato alfabeto di simboli, quasi sempre il normale alfabeto perché usarne altri sarebbe inutile, e questi messaggi vengono trasformati in messaggi "cifrati" tramite un algoritmo. Un algoritmo è procedura matematica ben specificata attraverso l'accurata descrizione delle sue operazioni, che permette di costruire trasformazioni complesse partendo da un limitato bagaglio di semplici operazioni "elementari". L'algoritmo crittografico da solo riveste una grande importanza, ed è su di esso che di solito si incentra l'attenzione, ma non è tutto, perché in realtà importantissimo, e sottovalutato in genere, è anche il protocollo. Questo si potrebbe chiamare anche "algoritmo di scambio e conservazione delle informazioni" ed è la procedura generale che si segue per scambiarsi i messaggi, al di là della semplice operazione di cifratura. Per esempio nel caso di sopra il protocollo potrebbe essere il seguente:

1) le carte utilizzate per cifrare e decifrare i messaggi vanno distrutte dopo l'uso, in modo che non possano essere usate da estranei;

2) l'algoritmo di cifratura deve essere noto al minor numero possibile di persone, in particolare non deve conoscerlo colui che porta il messaggio, in modo che se cadesse in mano al nemico non potrebbe, nemmeno volendo, essere d'aiuto per la decifrazione.

     In pratica ci sono protocolli all'interno dei quali l'algoritmo di cifratura non riveste un ruolo centrale, e può essere sostituito da altre procedure quando fosse necessario farlo. Inoltre, spesso la debolezza dei sistemi crittografici risiede non nell'imperfezione dell'algoritmo crittografico ma in problemi di protocollo. Nell'esempio, il problema è che l'uso di un algoritmo prefissato presuppone che questo non venga a conoscenza del nemico, perché altrimenti tutti i messaggi saranno decifrati. E' quello che è capitato nella seconda guerra mondiale, quando la cattura di un sommergibile tedesco permise agli inglesi di impossessarsi di una delle macchine Enigma che servivano per cifrare i messaggi tra la flotta e il comando. Il cedimento di un singolo elemento ha compromesso così tutto il sistema e i tedeschi hanno continuato a comunicare senza sospettare di essere capiti. Il problema non era il difficilissimo algoritmo di Enigma ma il fatto che il protocollo aveva una cosiddetta "chiave segreta": la chiave deve essere protetta e non cadere in mano ad estranei.

     L'eliminazione di questo problema è una sviluppo recente, del 1976, quando Diffie ed Hellmann diedero il primo esempio di algoritmi a "chiave pubblica", ed è di importanza straordinaria. L'idea è sostanzialmente quella di dividere le informazioni necessarie in due parti, nessuna delle quali, da sola, sia sufficiente a decifrare il messaggio. Sempre rifacendoci all'esempio, piuttosto che traslare le lettere di quattro posizioni e rendere la cosa nota a tutti gli ufficiali, Cesare avrebbe potuto istruirli sul metodo generale di traslazione, ma decidendo di volta in volta di quante posizioni traslare le lettere, trasmettendo poi questa informazione con un corriere diverso da quello che portava il messaggio cifrato. Solo la riunione delle due informazioni, messaggio cifrato e traslazione, permette di ricostruire il messaggio originale, e, anche nell'improbabile caso di cattura di entrambi i messaggeri e di conoscenza della procedura di decifrazione, si può decifrare solo il messaggio presente, non anche i seguenti.

     Naturalmente si dirà che quest'ultimo esempio è stupido in quanto le lettere dell'alfabeto sono poche e non è difficile provare tutte le possibili traslazioni finché si trova quella che funziona. Il problema si può esprimere dicendo che l'algoritmo di Cesare ha troppo poche chiavi, tante quante le lettere dell'alfabeto, per poter sperare che questo crei un segreto significativo, in quanto chi non conosce la chiave giusta può ottenerla con il cosiddetto "metodo di forza bruta", cioè provando tutte le possibilità. Di nuovo, il semplice esempio contiene tutti gli sviluppi, perché gli algoritmi usati in pratica, semplicemente hanno un numero enorme di chiavi possibili, un numero tanto alto da rendere inattuabile il metodo anche usando i computer più veloci.

     Riguardo a questo, si può notare che uno dei primi utilizzi significativi dei calcolatori si è avuto nello sforzo di decifrazione dei codici crittografici altrui. Questo non solo dal punto di vista delle macchine, ma anche da quello della teoria. Infatti il matematico inglese Alan Turing partì proprio dal suo lavoro di crittografo per sviluppare la descrizione matematica degli algoritmi, cioè la famosa macchina di Turing. Tra l'altro la sua macchina originale non opera su bit, come fanno tante forme ad essa equivalenti inventate in seguito, ma direttamente su parole scritte in un dato alfabeto, proprio ciò che è d'uso in ambito crittografico.

     Una parola va detta sul metodo delle molte chiavi. Tutti i sistemi crittografici moderni si basano non sulla segretezza dell'algoritmo, che anzi si preferisce sia noto in tutti i dettagli ed approfonditamente studiato, ma sul numero enorme di possibili chiavi utilizzabili. Una chiave è nient'altro che un numero o una stringa di lettere e numeri, che bisogna scegliere tra tante possibilità quando si cripta un messaggio. La segretezza non risiede nel modo in cui l'algoritmo è fatto (nell'esempio di Cesare, la traslazione alfabetica) ma nella chiave scelta (di quanto si traslano le lettere). Ovviamente bisogna che le possibili scelte siano troppe per l'attacco a forza bruta. Questo pone il cosiddetto problema della lunghezza delle chiavi, che sarebbe più significativo dire del numero di chiavi possibili. Infatti l'evoluzione dei computer fa sì che algoritmi una volta sicuri divengano con il passare del tempo sempre più violabili, perché il tempo necessario per provare tutte le chiavi diventa sempre minore. E' quindi necessario aggiornare continuamente gli algoritmi, in pratica basta utilizzare solo una quantità maggiore di dati per le chiavi, cioè chiavi più lunghe. Questo pone completamente al riparo dell'attacco di forza bruta, perché in genere la maggior potenza di calcolo facilita la criptazione più di quanto faccia per la decriptazione. Rimane però il problema che messaggi del passato possono via via venire decifrati, e questo può non essere accettabile in certi ambiti. Inoltre è sempre possibile un completo crollo del sistema quando gli studi matematici permettessero di trovare un metodo "facile", diverso da quello di forza bruta, per violare l'algoritmo di cifratura. Anche quando questa ipotesi catastrofica non si verifica, comunque, in genere i progressi teorici per la decifrazione forniscono maggior aiuto di quanto non faccia il semplice progresso dei calcolatori.

     Allora, visti tutti questi problemi, perché si adotta uno schema in cui l'algoritmo è noto a tutti, invece di tenerlo nascosto? Tenere segreto l'algoritmo è possibile quando si vuole semplicemente comunicare tra due persone, ma, difficoltà ad inventarselo a parte, la condivisione in gruppi più ampi ha il problema della "chiave segreta", cioè che se anche un solo componente del gruppo viola il segreto, le comunicazioni di tutti gli altri sono in pericolo. Il fatto di basare la segretezza non sull'algoritmo ma su una tra tante chiavi permette inoltre di sostituire facilmente le chiavi, cambiandone addirittura una per ogni sessione della comunicazione. Inoltre permette di comunicare anche con persone con cui non ci si era precedentemente incontrati per scambiarsi chiavi segrete, attraverso l'importante scoperta degli algoritmi a "doppia chiave", vera rivoluzione della crittografia moderna.

     Nel seguito descriveremo i più importanti protocolli ed algoritmi crittografici, nonché di firma digitale ed autenticazione dei documenti, in quanto sono molto interessanti anche dal semplice punto di vista matematico.