L'idea della crittografia a chiave pubblica (CCP) fu proposta in un articolo, pubblicato nel novembre del 1976, da Martin E. Hellman.

In tale articolo si suggerisce di impiegare cifrari in linea di principio decifrabili, ma solo da programmi di calcolo che operino su calcolatori per milioni di anni.

Tutto si riduce nel legare il sistema crittografico a un problema intrattabile.

A differenza della CCS, nella CCP:
- si impiegano due chiavi
- non occorre il preliminare invio di una chiave su di un canale sicuro
- non occorre che venga tenuto segreto il metodo di cifratura.

Hellman suggerì una serie di cifrari a chiave pubblica, ma nessuno si rivelò del tutto soddisfacente.

In un articolo pubblicato nell'aprile del 1977, a firma di Ronald L. Rivest, Adi Shamir e Leonard Adleman, fu proposto il sistema RSA, un modo elegante per realizzare la CCP.

Il sistema RSA si basa sul fatto che, sebbene sia semplice, sotto il profilo computazionale, trovare due numeri primi con un centinaio di cifre decimali, è viceversa a tutt'oggi un problema intrattabile la scomposizione del prodotto dei suddetti numeri primi.

Vediamo come funziona.

In prima battuta Alice si "fabbrica" le due chiavi. Quella pubblica la trasmetterà a tutti i suoi corrispondenti, fra i quali c'è Bob. Quella privata la terrà per sè, senza mai rivelarla a nessuno.

In pratica Alice:

- sceglie a caso un centinaio di basi b e verifica col test di Fermat se i due numeri dispari, scelti anch'essi a caso, p e q, con un centinaio di cifre decimali, sono (quasi certamente) primi

- determina m=pq ed N(m)=(p-1)(q-1)

- scegli E in modo che sia primo con N(m)

- da forma esplicita alla funzione

che è poi quella che Bob utilizzerà per crittate i messaggi diretti ad Alice

- determina D in modo che DE(mod N(m))=1

- da forma esplicita alla funzione inversa

che è poi quella che Alice utilizzerà per decrittate i messaggi a lei recapitati.

La coppia di numeri (E,m), ovvero la funzione C, è dunque la chiave pubblica, mentre quella (D,m), ovvero la funzione P, è la chiave privata.

Se un crittanalista, a partire dalla funzione C in suo possesso, tenta di determinare la funzione inversa P, dovrà calcolare D.

Per poterlo fare deve risolvere un problema intrattabile.

Deve cioè fattorizzare il numero a 200 cifre m.

Solo così potrà calcolare N(m)=(p-1)(q-1) e quindi D, essendo D tale che DE(mod N(m))=1.

Se un crittanalista, a partire da un insieme limitato di valori della variabile dipendente C, tenta per estrapolazione di calcolare i valori ignoti rimanenti, al fine di risalire alla funzione inversa P, semplicemente non può farlo.

Essendo infatti la funzione C, ad andamento disordinato, per poterla invertire occorre disporre di tutto l'insieme dei valori di arrivo della funzione C, che, in realtà, è un insieme titanico, visto che m è un numero a 200 cifre decimali.

Ad un modulo m corrispondono infatti m resti.

Se ad esempio m è un numero a tre cifre, i possibili resti sono un numero compreso tra 100 e 999.

Ad un modulo m a 200 cifre corrispondono allora un numero di resti compreso fra

Quest'ultimo tipo di protezione è del tutto eccessiva.

Come è esposto nel successivo paragrafo, si preferisce dar luogo al cosiddetto frazionamento del numero P in una successione di blocchi di numeri

con lo stesso numero di cifre, numero nettamente inferiore alle 200 cifre di m.

In fondo, ad un blocco Pi con 11 cifre, corrispondono pur sempre un numero di resti compreso fra 10 miliardi e 100 miliardi meno 1.