La storia della crittografia moderna inizia con la stesura del De Cifris di Leon Battista Alberti, che per primo insegnò a cifrare per mezzo di un disco cifrante con un alfabeto segreto da spostare ad libitum ogni due o tre parole. Anche il tedesco Tritemio prevedeva una forma di cifra polialfabetica, facendo scorrere l'alfabeto ordinato di un posto ad ogni lettera del chiaro (come si definisce in gergo il testo non crittato). Ma il vero progresso nella cifratura polialfabetica è stato compiuto dal bresciano Giovan Battista Bellaso, che ha inventato la tecnica di alternare alcuni alfabeti segreti formati con parola chiave sotto il controllo di un lungo versetto chiamato contrassegno. La sua prima tavola a 11 alfabeti reciproci, uscita nel 1553, fu ripubblicata dal napoletano Giovanni Battista Della Porta dieci anni più tardi e ne prese il nome grazie alla notevole diffusione che ebbe il suo trattato De furtivis literarum notis. Il francese Vigenère utilizzò poi il versetto per cifrare ciascuna lettera con la sua tavola ad alfabeti regolari identica a quella del Tritemio e che oggi porta il suo nome. Il suo sistema è stato considerato indecifrabile per tre secoli, finché nel 1863 il colonnello prussiano Friedrich Kasiski non pubblicò un metodo per "forzarlo", chiamato Esame Kasiski.
Qualsiasi sia il sistema crittografico utilizzato, la legge fondamentale sul corretto uso di tali tecniche fu scritta da Kerckhoffs ("Legge di Kerckhoffs") nel suo libro del 1883 La Cryptographie Militaire e di seguito riportata: «La sicurezza di un crittosistema non deve dipendere dal tener celato il crittoalgoritmo. La sicurezza dipenderà solo dal tener celata la chiave.»
Cruciali sono anche i tempi necessari alla crittoanalisi per la decifrazione del messaggio: per diverse applicazioni di telecomunicazioni e informatica un sistema si può considerare sicuro anche se il suo sistema di cifratura risulta violabile, ma con tempi di realizzazione che renderebbero poi vani i successivi tentativi di attacco diretto.
Nel 1918 Gilbert Vernam maggiore dell'Esercito USA e tecnico all'AT&T Bell, perfezionò il metodo di Vigenère proponendo l'idea di usare chiavi segrete casuali lunghe almeno quanto il messaggio. Successivamente, nel 1949, Claude Shannon, padre della teoria dell'informazione, nel lavoro La teoria della comunicazione nei sistemi crittografici dimostrò che questo è l'unico metodo crittografico possibile che sia totalmente sicuro.
Con il possesso di un sistema crittografico perfetto, la battaglia teorica tra crittografia e crittoanalisi si è risolta con una vittoria della prima sulla seconda. Ipotizzando di voler far uso di questa insuperabile protezione, restano però aperti molti problemi di ordine pratico. Bisogna infatti soddisfare i stringenti requisiti del cifrario di Vernam: chiave lunga quanto il messaggio e mai più riutilizzabile. Tuttavia si hanno notizie di utilizzi di questo cifrario in ambiente militare (comunicazione con le spie: si veda a proposito One Time Pad), o per la protezione delle comunicazioni del telefono rosso tra Washington e Mosca durante la Guerra fredda. Anche il cifrario trovato nel 1967 sul corpo di Che Guevara è un'applicazione del cifrario di Vernam.
L'attuale ricerca crittografica, avendo risolto il problema teorico della garanzia della sicurezza, si dedica al superamento dei forti limiti d'uso anzidetti. Si cercano metodi più comodi ma ciononostante estremamente sicuri che, possibilmente, utilizzino chiavi corte e riutilizzabili senza compromettere la loro utilità.
Al momento non esiste alcuna tecnica crittografica che si possa definire sicura in senso assoluto, tranne forse il Cifrario di Vernam: tutte le altre tecniche rendono sicuro il dato solo per un certo arco temporale e non possono garantire la durata della segretezza.
Fino a pochi anni fa l'unico metodo crittografico esistente era quello della crittografia simmetrica, in cui si faceva uso di un'unica chiave sia per proteggere il messaggio che per renderlo nuovamente leggibile. Il problema è condividere la chiave di cifratura con il destinatario del messaggio criptato senza che questa venga scoperta. La ricerca sulla crittografia simmetrica ha negli anni prodotto sistemi crittografici di tutto rispetto (ultimo tra tutti il cifrario Rijndael, scelto per il nuovo standard Advanced Encryption Standard per essere utilizzato nel prossimo ventennio, sostituendo l'ormai datato Data Encryption Standard).
Nel 1976 Whitfield Diffie e Martin E.Hellman, un matematico e un ingegnere in forza alla Stanford University, introducono l'utilizzo della chiave pubblica per la crittazione e l'autenticazione; nell'anno seguente il gruppo di ricerca del MIT formato da Ronald L. Rivest, Adi Shamir e Loenard M. Adleman realizza il primo sistema a chiave pubblica, in questo modo viene ideato l'algoritmo RSA.
Il funzionamento di questo sistema è basato sul fatto che è matematicamente e computazionalmente molto facile moltiplicare due numeri primi (che singolarmente rappresentano la chiave privata, quella che solo A conosce per decifrare), ma è invece molto difficile il problema inverso ovvero risalire ai fattori primi del numero ottenuto dal precedente prodotto (che invece rappresenta la chiave pubblica che chiunque può vedere e che si usa per crittografare).
Siccome la crittografia asimmetrica è molto lenta se si devono spedire grandi quantità di dati, spesso si usa questo tipo di crittografia per scambiarsi una chiave con cui iniziare una comunicazione in crittografia simmetrica, molto più semplice, veloce e sicura.
L'idea base della crittografia con coppia di chiavi diviene più chiara se si usa un'analogia postale, in cui il mittente è Alice ed il destinatario Bob, i lucchetti fanno le veci delle chiavi pubbliche e le chiavi recitano la parte delle chiavi private:
Se adesso Bob volesse mandare un altro pacco ad Alice, dovrebbe farlo chiudendolo con il lucchetto di Alice (che lei dovrebbe aver preventivamente dato a Bob) che solo lei potrebbe aprire.
Si può notare come per mettere in sicurezza il contenuto dei pacchi ci sia bisogno del lucchetto del destinatario, mentre per aprirli viene usata esclusivamente la propria chiave segreta, rendendo l'intero processo di cifratura/decifratura asimmetrico (una chiave per cifrare ed una differente per decifrare). Chiunque intercettasse il lucchetto (aperto) o il messaggio chiuso con il lucchetto non potrebbe leggerne il contenuto poiché non ha la chiave. Uno dei vantaggi della crittografia asimmetrica sta nel fatto che le chiavi pubbliche possono essere scambiate anche utilizzando un mezzo insicuro, come Internet.
Usando un'altra analogia si può dire che il metodo è analogo a quello di una cassaforte che abbia due chiavi distinte, una usata per aprirla (chiave segreta), l'altra per chiuderla (chiave pubblica).
Nella crittografia simmetrica invece, che basa la sicurezza del sistema sulla segretezza della chiave di codifica/decodifica utilizzata, si rende necessario utilizzare un canale sicuro per la trasmissione della chiave, poiché l'intercettazione della stessa, da parte di terzi, vanificherebbe la sicurezza del sistema stesso.
La crittografia a chiave pubblica permette invece a due (o più) persone di comunicare in tutta riservatezza senza usare la stessa chiave e anche se non si sono mai incontrate precedentemente.
Per utilizzare questo tipo di crittografia è necessario creare una coppia di chiavi, una chiave pubblica (da diffondere) ed una chiave privata (da tenere segreta). La proprietà fondamentale della coppia di chiavi pubblica/privata è che un messaggio cifrato usando la chiave pubblica può essere decifrato usando soltanto la chiave privata corrispondente. In pratica, la chiave pubblica serve unicamente per codificare il messaggio, mentre quella privata serve unicamente per decodificarlo.
La coppia di chiavi pubblica/privata viene generata attraverso un algoritmo (ad esempio RSA o DSA) a partire da dei numeri casuali. Gli algoritmi asimmetrici sono studiati in modo tale che la conoscenza della chiave pubblica e dell'algoritmo stesso non siano sufficienti per risalire alla chiave privata e tale meccanismo è reso possibile grazie all'uso di funzioni unidirezionali. In realtà, in molti casi, l'impossibilità di risalire alla chiave privata non è dimostrata matematicamente, ma risulta dallo stato attuale delle conoscenze in matematica e della potenza di calcolo disponibile. Per esempio è sufficiente un piccolo computer e qualche millesimo di secondo per moltiplicare due numeri primi da 150 cifre, ma occorre il lavoro di decine di migliaia di computer per un anno per trovare i fattori primi di quel numero. Un altro problema simile è quello della funzione unidirezionale esponenziale modulo n (aritmetica modulare) e del rispettivo problema inverso del calcolo del suo logaritmo discreto.
A questo punto il gioco è fatto: ogni utilizzatore si crea la propria (o le proprie, in casi particolari) coppia di chiavi; la chiave privata viene tenuta segreta e non viene mai rivelata a nessuno (nemmeno alle persone con le quali si comunica); viceversa, la chiave pubblica viene diffusa in vari modi: può essere aggiunta automaticamente in coda a ciascun proprio messaggio nelle varie conferenze elettroniche cui si partecipa, o può essere depositata in archivi pubblici (keyserver) a disposizione di chi la desideri. È importante che la chiave pubblica sia liberamente accessibile, perché chiunque voglia comunicare con la persona che l'ha generata dovrà preventivamente munirsi di questa, con la quale cifrerà il messaggio.
Oltre alla cifratura dei dati di una comunicazione la crittografia asimmetrica presenta altri possibili impieghi: firma digitale per verificare l'autenticazione del mittente e l'integrità informativa del messaggio, fornire una condizione di ending e per i programmi che tentano la forzatura delle chiavi; supporto alla fase di handshake ovvero di avvio di una sessione con crittografia simmetrica per negoziare la chiave di sessione, il protocollo e gli altri aspetti della connessione cifrata.
Un utente può firmare un messaggio utilizzando la propria chiave privata; per far ciò viene creata un'impronta (digest) del messaggio da firmare e questa viene firmata con la chiave privata ed inviata assieme al messaggio (l'impronta, generata per mezzo di un algoritmo di hash, è tale che varia sensibilmente al minimo variare del messaggio). Tutti i destinatari del messaggio possono verificare l'integrità del messaggio stesso e l'autenticazione dell'autore/mittente creando, a partire dal messaggio ricevuto e decifrato, un'impronta (utilizzando in maniera simmetrica la stessa funziona hash utilizzata dall'autore del messaggio) e confrontandola poi con quella ricevuta assieme al messaggio e cifrata con la chiave pubblica del presunto autore: se le due impronte risultano identiche il messaggio è integro, ovvero non ha subito modifiche da parte di terzi (ad esempio attraverso attacchi del tipo man in the middle) da quando l'autore a monte l'ha firmato.
La firma digitale fornisce anche una condizione di termine per i programmi che tentano di forzare la cifratura. Tali programmi tentano di ricostruire la chiave privata del destinatario per leggere il messaggio. Il programma ha come riferimento la firma digitale del messaggio, o meglio la decifra con la chiave pubblica del mittente e utilizza l'hash. Il programma propone n chiavi private, per ognuna decifra il messaggio, ne calcola l'hash e lo confronta con quello ricavato dalla firma digitale: se coincidono, è stata trovata la chiave privata giusta ed è visibile il contenuto del messaggio originale.
In realtà il problema della sicurezza riguardante la segretezza della comunicazione non è del tutto risolto con questo tipo di crittografia in quanto passibile di attacchi di tipo man in the middle: non si può essere certi infatti che la chiave (per esempio una chiave presente sul keyserver) appartenga davvero alla persona nominata nell'intestazione della chiave stessa apportando così attacchi di tipo spoofing in assenza di un meccanismo di autenticazione tra le parti in causa. Una soluzione resta sempre il contatto fisico tra i due interlocutori, i quali, scambiandosi le chiavi pubbliche hanno una reciproca autenticazione. PGP, il primo sistema crittografico di massa che si avvale delle idee della crittografia asimmetrica consiglia, dopo essersi scambiati le chiavi per e-mail o altro mezzo, di telefonarsi e di leggersi i fingerprint (letteralmente "impronte digitali"), ovvero un codice (codice di hash) associabile in modo sicuro alla chiave stessa, ma da cui non si può ricavare la chiave; in questo modo, riconoscendo le rispettive voci, si certifica anche la validità della chiave ottenuta.
Un altro problema da non escludere è quello dell'effettiva protezione della chiave privata: questa infatti risiede nel disco rigido del proprietario ed è generalmente cifrata con una password (quindi con crittografia simmetrica). Data la relativa semplicità di accesso alla chiave (basta inserire una password per "sbloccarla"), con particolari trojan/keylogger programmati ad-hoc è quindi possibile ricavare dal PC della vittima sia il file contenente la chiave privata sia la password per utilizzarla, violando a tutti gli effetti l'efficienza della crittografia asimmetrica.
Il principio generale della crittografia asimmetrica ha una solida base matematica che lo giustifica; tale base, riassunta e semplificata all'estremo, si fonda sull'uso di un problema complesso, ovvero un'operazione matematica semplice da eseguire ma difficile da invertire, cioè dal cui risultato è difficile risalire agli argomenti di partenza. L'esempio classico è il problema della fattorizzazione di un numero (trovare i numeri primi che lo producono se moltiplicati tra loro, ad esempio è facile moltiplicare 17*23 ottenendo 391, ben più difficile è per esempio fattorizzare il numero 377 nei fattori primi 13 e 29) usata nel primo e più famoso sistema crittografico a chiave pubblica: RSA. Le conoscenze di matematica pura sviluppate dall'uomo negli ultimi secoli hanno reso sempre più efficiente fattorizzare, ma nessuno è mai riuscito a far fare quel "salto" che porta il problema da complesso a non essere più complesso; il problema diventa quindi intrattabile per numeri oltre una certa dimensione.
Attualmente, per la crittografia RSA vengono considerati "sicuri" numeri che in base 10 hanno almeno 300 cifre, il che significa chiavi di 1024 bit e oltre.
Altro esempio di problema complesso è il logaritmo discreto, usato nella nascente crittografia ellittica.
La crittografia è comunque una scienza basata sulle probabilità: i problemi complessi vengono considerati complessi basandosi sul fatto che centinaia di anni di studio non hanno saputo risolverli in modo rapido (ricordiamoci che c'è sempre almeno un modo "non rapido" per risolvere un problema: provare a fare l'operazione diretta con tutti i numeri fino alla dimensione necessaria; questo tipo di soluzione in genere non è neanche contemplata in quanto il tempo necessario aumenta vertiginosamente con la dimensione dei numeri usati), ma nessuno dei problemi usati in crittografia ha un teorema che ne dimostra la complessità (l'unico sistema crittografico dimostrato è lo One Time Pad, ma sfortunatamente è un sistema simmetrico – ovvero non a chiave pubblica – ed estremamente scomodo da usare).
.