Wszystkie systemy, które omówiliśmy powyżej, miały na celu osiągnięcie wysokiego stopnia bezpieczeństwa z łatwym do zarządzania układem obsługi kluczy. Ale wszyscy mają wspólny problem, że nadal musi istnieć bezpieczny kanał dostarczania tajnych kluczy. Jest to przykład stosunkowo bezpiecznego, algorytmicznie bezpiecznego systemu, który może zostać naruszony przez uciążliwy proces bezpieczeństwa. Na pierwszy rzut oka wydaje się to nieuniknionym wymogiem; jeśli odkryjesz klucz, którego używam do zaszyfrowania wiadomości, to na pewno łatwo ci go odszyfrować? To prawda, jeśli klucz do odszyfrowania wiadomości jest albo identyczny z kluczem szyfrowania, albo łatwo go z niego wyprowadzić, a metoda odszyfrowania polega na prostym odwróceniu szyfrowania. Ale załóżmy, że tak nie jest? W tym przypadku okazuje się, że istnieje szereg technik, które otwierają zaskakującą możliwość. Możliwość otwartego publikowania klucza szyfrowania dla każdego, co nie ułatwia nikomu poza wystawcą klucza odszyfrowania wiadomości zaszyfrowanych tym kluczem. Aby zrozumieć, co to oznacza, rozważ przykład pokazany na rysunku
Bob chce wysłać tajną wiadomość do Alice. Zauważa, że Alicja powiedziała światu swój klucz publiczny. Używa tego do zaszyfrowania swojej wiadomości, zgodnie z jednym z algorytmów, które omówimy później. Następnie wysyła do niej swoją wiadomość przez otwarty kanał, wiedząc, że nawet jeśli Charlie zdoła ją przechwycić, nie będzie w stanie jej zrozumieć. Jednak Alicja i tylko Alicja, która posiada klucz prywatny, który działa jako odwrotność klucza publicznego i którego pilnie strzeże dla siebie, może zostać wykorzystana do odszyfrowania wiadomości. Ze względu na specjalną relację między kluczami prywatnymi i publicznymi Charlie jest niezwykle trudny do odszyfrowania wiadomości i opracowania klucza prywatnego. Być może bardziej zaskakujące jest to, że nikt, nawet Bob, nie może wrócić od znajomości wiadomości i klucza publicznego do prywatnego. Systemy szyfrowania klucza publicznego opierają się na fakcie, że niektóre operacje matematyczne są łatwe do wykonania w jednym kierunku, ale trudne w innym. Jednym z przykładów jest formowanie kwadratu liczby – prosta operacja mnożenia samej liczby – w porównaniu z otrzymaniem wyniku i poproszeniem o znalezienie pierwiastka kwadratowego. Liczba wymaganych do tego kroków jest znacznie większa niż w przypadku operacji kwadratu. Inną, bardziej odpowiednią operacją jest „faktoryzacja iloczynów liczb pierwszych”. Przypominamy sobie, że liczby pierwsze to liczby całkowite, których nie można „rozłożyć na czynniki” na iloczyn liczby mniejszych liczb całkowitych. 1, 2, 3, 5, 7 to liczby pierwsze, ale nie 4 (= 2 x 2), 6 (= 2 x 3) lub 9 (= 3 x 3). Wiadomo, że istnieje nieskończona liczba liczb pierwszych, z których około 10150 ma 512 bitów lub mniej, ale nie ma znanego wzoru na udowodnienie, ogólnie, że liczba jest lub nie jest liczbą pierwszą, co jest znacznie szybsze niż próba lub błąd. Czas potrzebny na wykonanie tego rośnie bardzo szybko wraz z wielkością liczby. Podobny problem dotyczy „rozkładania na czynniki iloczynu dwóch liczb pierwszych”. (tj. znalezienie p i q, mając tylko p czas q). Łatwo jest pomnożyć dwie liczby pierwsze, ale trudno odwrócić ten proces.