La crittografia a chiave pubblica nasce nel maggio del 1975 come risposta a due problemi fondamentali:
Nella crittografia simmetrica, infatti, non era possibile implementare firme autentiche. Questo perché, utilizzando la stessa chiave, un eventuale “giudice” non sarebbe in grado di distinguere chi sia l’utente legittimo e chi no.
La scoperta della crittografia a chiave pubblica non consisteva tanto in una soluzione pratica immediata, quanto nel riconoscimento che questi due problemi apparentemente irrisolvibili potevano essere risolti.
E sorprendentemente, la soluzione per entrambi i problemi arrivava in un unico pacchetto: la crittografia a chiave pubblica.
In un sistema crittografico, l'obiettivo è rendere difficile decifrare un messaggio cifrato senza la chiave corretta. In questo contesto, consideriamo una coppia di trasformazioni $(E_e, D_d)$, dove $E_e$ è la funzione di cifratura e $D_d$ è la funzione di decifrazione.
La funzione $E_e$ è detta "funzione unidirezionale con trappola" perché rende difficile risalire al messaggio originale $m$ dal cifrato $c$, a meno di una conoscenza specifica chiamata "trapdoor". Questa trapdoor, rappresentata da $d$, consente di decifrare agevolmente il messaggio. In altre parole, senza la trapdoor $d$, la decifrazione dovrebbe rimanere computazionalmente difficile.
La chiave pubblica $e$ può essere resa accessibile a chiunque, poiché anche conoscendola non dovrebbe essere possibile risalire facilmente al messaggio originale dal cifrato, senza possedere la trapdoor $d$.
In sintesi, il principio è che conoscere la chiave pubblica $e$ non permette di decifrare facilmente i messaggi cifrati, a meno di possedere anche la trapdoor $d$, necessaria per invertire la trasformazione.