La crittografia tradizionale richiede una chiave segreta da concordarsi segretamente, cosa che complica molto le cose dal punto di vista pratico: non sempre infatti è facile trovare un canale di comunicazione assolutamente sicuro per comunicarsi la chiave segreta.

Nel 1976 Whitfield Diffie and Martin Hellman proposero i cosiddetti cifrari a chiave pubblica e definirono l'algoritmo DH; il primo cifrario proposto fu quello di Merkle destinato ad avere poca fortuna, mentre enorme è stata la fortuna del secondo il notissimo RSA definito nel 1977 e presentato nel 1978.

Questi cifrari sono basati su una filosofia del tutto nuova: la chiave per cifrare non è la stessa di quella per decifrare; la prima può allora essere resa pubblica mentre solo la seconda resta segreta. Per questo motivo sono detti anche cifrari asimmetrici.

La sicurezza di questi sistemi si fonda quasi sempre su funzioni relativamente facili da calcolare ma molto difficili da invertire (problemi ardui). Tali sono p.es.

• Il prodotto di due numeri primi, relativamente facile da calcolare, mentre fattorizzare un numero intero è molto più difficile.
• La potenza in un'aritmetica modulare ha due problemi inversi entrambi ardui:
  • Il calcolo del logaritmo discreto, è di una complessità proibitiva.
  • Il calcolo della radice discreta.

Supponiamo per esempio che Aldo e Biagio vogliano comunicare in modo segreto; per prima cosa Aldo e Biagio scelgono, ognuno per proprio conto, una chiave segreta e calcolano quindi la chiave pubblica facendo uso di una qualche funzione che sia (relativamente) facile da calcolare e impossibile (o quasi) da invertire (nell'RSA è il prodotto di due numeri primi elevati). Le chiavi pubbliche così calcolate sono inserite su una specie di elenco telefonico degli utenti. P.es. Aldo 123456789; Biagio 987654321.

A questo punto se Aldo deve inviare un messaggio segreto a Biagio trasformerà il suo messaggio in un numero o serie di numeri; effettuerà una serie di calcoli usando la chiave pubblica di Biagio e spedirà il messaggio cifrato a Biagio. Biagio decifrerà il messaggio usando una formula che, data la chiave segreta e il messaggio cifrato, permette di ricostruire il messaggio chiaro. Solo Biagio è in grado di decifrare il messaggio; paradossalmente lo stesso Aldo non è in grado di decifrare il messaggio da lui stesso cifrato! Questo avviene perchè la chiave per cifrare il messaggio non è la stessa di quella per decifrarlo.

Tra i cifrari a chiave pubblica il più noto resta RSA, ma vanno ricordati anche Diffie Hellman, ElGamal, PGP, DSA, e i cifrari basati sulle curve ellittiche molto promettenti ma la cui sicurezza è molto dibattuta.

La crittografia a chiave pubblica è utile anche per generare le cosiddette firme digitali.

Il vantaggio dei cifrari a chiave pubblica è evidente; non è più necessario concordare una chiave segreta, è sufficiente avere un elenco di chiavi pubbliche garantito da una qualche autorità. Lo svantaggio di questi metodi è che, richiedendo un gran numero di pesanti calcoli matematici, la trasmissione è molto più lenta di quella tradizionale. Per questo la soluzione oggi più usata è quella di utilizzare una combinazione dei due metodi: il messaggio chiaro viene cifrato con un metodo tradizionale, p.es. il DES, e una chiave segreta generata a caso; quindi usando un cifrario a chiave pubblica, p.es. RSA, si invia la chiave segreta, seguita dal messaggio cifrato; il ricevente, una volta ricevuta la chiave segreta può decifrare il messaggio segreto.