Come abbiamo visto un sistema crittografico classico consiste in una funzione, data dalla chiave k, f:T --> M che trasforma le lettere del testo T, nelle lettere del messaggio M. Per decodificare, la chiave permette di ottenere la funzione inversa f* :M --> T, che trasforma le lettere del messaggio cifrato nelle lettere del testo originale. La stessa chiave k permette di passare da f a f* e viceversa.
I sistemi a chiave pubblica si basano sull'esistenza di funzioni "a senso unico": conoscendo f e la chiave di codificazione, non è possibile risalire a f* senza ulteriori informazioni (la chiave privata).
Supponiamo di avere a disposizione tali funzioni "a senso unico", fA , fB, fC,... una per ogni utente del sistema, Alice, Bob, Christine, ... Il fatto importante è che solo Alice conosce fA*, solo Bob conosce fB*, ecc... mentre fA , fB, fC,... sono noti a tutti (per esempio sono riportati in un elenco pubblico). Se Alice vuole spedire un messaggio a Bob, applica fB al testo T, Bob riceve il messaggio cifrato fB(T), applica fB* (lui è l'unico a conoscerlo) e ottiene fB*(fB(T))=T. Se Christine intercetta il messaggio fB(T), non può decifrarlo perchè non conosce fB*.
Osservare che Alice e Bob non hanno dovuto scambiarsi nessuna chiave.
Questo sistema permette tra le altre cose di risolvere il problema della firma elettronica.
Rimane da vedere come costruire delle funzioni "a senso unico"....