A legtöbb kriptográfiai rendszer gyenge pontja hosszú időn keresztül a kulcskiosztás problémája volt. Függetlenül a titkosító rendszer erejétől, ha a kulcs a támadó kezébe került, a rendszer teljesen védtelenné vált. Mivel a kriptológusok mindig elfogadták azt a nézetet, hogy a kódoláshoz és dekódoláshoz szükséges kulcsoknak azonosnak (vagy egymásból könnyűszerrel generálhatóknak) kell lenniük, és ezeket minden érintett felhasználóhoz el kell juttatni, feloldhatatlan problémának tűnt a kulcsok illetéktelen kezektől való megóvása, mivel azokat nem lehetett páncélszekrénybe zárni a kulcskiosztás szükségessége miatt.
1976-ban két stanfordi kutató, Diffie és Hellman [1976] egy merőben új kriptográfiai rendszert javasolt, amelyben a kódoló és dekódoló kulcsok nemcsak különbözők, de egymásból nem állíthatók elő. A módszerükben szereplő kódoló 
és dekódoló 
algoritmussal szemben három követelményt támasztottak. Ezek a feltételek a következők:
D előállítása E alapján rendkívül nehéz feladat legyen.
E feltörhetetlen legyen választott nyílt szöveg típusú támadással.
Az első szabály azt mondja, hogy ha a D műveletet alkalmazzuk a kódolt szövegre, 
-re, akkor az eredeti szöveget, P-t kell visszakapnunk. A második pont önmagáért beszél. A harmadik követelményre azért van szükség, mivel – ahogy ezt mindjárt látni fogjuk – a támadók kényük-kedvük szerint kísérletezhetnek majd a kódoló eljárással. Ilyen feltételek mellett semmi sem szól az ellen, hogy a kódoló kulcsot nyilvánossá tegyük.
A módszer a következőképpen működik. Tegyük fel, hogy Aliz titkos üzeneteket szeretne fogadni, ezért először kifejleszt két olyan algoritmust, melyek megfelelnek a fenti követelményeknek. Ezek után a kódoló algoritmust, illetve a titkosító kulcsot nyilvánosságra hozza, innen ered a nyilvános kulcsú titkosítás (public-key cryptography) elnevezés is. Aliz felrakhatja például a nyilvános kulcsát a webes honlapjára. Mi az 
jelölést fogjuk alkalmazni arra a titkosító (encryption) algoritmusra, melyet Aliz nyilvános kulcsával paramétereztünk. Hasonlóképp, az Aliz egyéni kulcsával paraméterezett (titkos) dekódoló (decryption) algoritmus jele 
lesz. Bob ugyanúgy tesz, mint Aliz: ő is nyilvánosságra hozza 
-t, de titokban tartja 
-t.
Most pedig nézzük meg, hogyan oldhatjuk meg az Aliz és Bob között létrehozandó, titkosított csatorna problémáját, ha ők ketten még sohasem találkoztak azelőtt! Feltesszük, hogy mind Aliz, mind Bob titkosító kulcsa, azaz 
és 
is nyilvánosan olvasható állományokban vannak. Aliz veszi az első P üzenetét, kiszámítja 
-t, és az eredményt elküldi Bobnak. Bob ezt a 
titkos kulcsa segítségével visszafejti [azaz kiszámítja 
-t]. Rajta kívül senki más nem képes a titkosított üzenetet, 
-t elolvasni, mivel feltételezzük, hogy a kódolás erős védelmet nyújt, és 
előállítása az ismert 
alapján túl bonyolult feladat. Az R válasz elküldéséhez Bobnak az 
üzenetet kell leadnia. Aliz és Bob ezek után biztonságosan kommunikálhatnak.
Érdemes talán egy megjegyzést tenni a szóhasználattal kapcsolatban. A nyilvános kulcsú módszerek minden felhasználótól két kulcsot követelnek meg: egy nyilvános kulcsot, melynek segítségével a világon bárki kódolhat számukra információt, és egy egyéni kulcsot, melyet tulajdonosa az üzenetek dekódolására használ. Ebben a könyvben következetesen nyilvános és egyéni kulcsként fogunk rájuk hivatkozni, hogy megkülönböztessük őket azoktól a titkos kulcsoktól, amelyeket a hagyományos szimmetrikus kulcsú kriptográfiában alkalmaznak.
Az egyetlen buktató, hogy a fenti három követelménynek eleget tevő eljárásokat kellene találnunk. A nyilvános kulcsú titkosítás nyilvánvaló előnyei miatt számos szakember komoly munkába kezdett, és sikerült mára néhány ilyen módszert kifejleszteniük. Az egyiket ezek közül egy, az M.I.T.-n dolgozó csoport [Rivest és mások, 1978] alkotta meg. Az algoritmus azóta a felfedezők (Rivest, Shamir, Adleman) kezdőbetűi alapján RSA-algoritmus néven vonult be a köztudatba. A módszer immár negyed százada túlélt minden egyes támadási kísérletet, tehát nagyon erősnek tekinthető. Ennek köszönhetően sok gyakorlati megoldás is ezen alapszik. A legfőbb hátránya, hogy a kielégítő biztonság érdekében legalább 1024 bites kulcsokat igényel (szemben a szimmetrikus kulcsú algoritmusok 128 bites kulcsaival), ami meglehetősen lassúvá teszi.
Az RSA a számelmélet tételein alapszik. Most röviden összefoglaljuk az algoritmus lépéseit, a részletek megismeréséhez az eredeti művet ajánljuk.
Válasszunk két nagy (jellemzően 1024 bites) prímszámot, p-t és q-t.
Számoljuk ki az
és a 
számokat.Válasszunk egy z-hez relatív prímet, jelöljük d-vel.
Keressünk egy olyan e számot, melyre
.
A fenti paraméterek előzetes meghatározása után megkezdhetjük a titkosítást. A nyílt szöveget, mint egyszerű bitsorozatot blokkokra osztjuk oly módon, hogy egy kódolandó szegmens 
a 
< 
intervallumba essen. Ezt legkönnyebben úgy érhetjük el, ha az eredeti üzenet bitjeit k bit hosszú csoportokba szedjük, ahol k az a legnagyobb egész, melyre még fennáll a 
< 
összefüggés.
A titkosítandó üzenetdarab 
értéket. C visszakódolásához a 
összefüggést használjuk. Bebizonyítható, hogy minden olyan P-re, mely a fenti tartományba esik, a megadott kódoló és dekódoló függvények egymás inverzei. A kódoláshoz az e és az n számokra van szükség, míg a visszafejtéshez a d-re és az n-re. Ennek alapján a nyilvános kulcs az (e, n) párból, míg az egyéni kulcs a (d, n) párból fog állni.
A módszer biztonsága a nagy számok faktorizálásának nehézségén alapszik. Ha a támadó képes lenne szorzatalakra hozni a mindenki által ismert n számot, megkapná a p-t és a q-t, ami alapján a z-t kiszámolhatná. A z érték ismeretében pedig az e és a d meghatározása az euklideszi algoritmussal elvégezhető. Szerencsére azonban az utóbbi 300 év próbálkozásai alapján a matematikusok többsége azon a véleményen van, hogy a nagy számok szorzatra bontása rendkívül nehéz feladat.
Rivest és kollégái szerint egy 500 digites szám számítógépes faktorizálása 
évet venne igénybe az összes lehetőséget kipróbálva. Mindkét esetben az általuk leghatékonyabb algoritmust és egy olyan számítógépet tételeztek fel, mely egy utasítást 1 
s alatt hajt végre. Ez még akkor is 
évet igényelne, ha egymillió lapka párhuzamosan futna és mindegyik utasítás végrehajtási ideje 1 ns lenne. Még ha folytatódna is a számítógépek sebességének évtizedenkénti egy nagyságrenddel való növekedése, akkor is sok év múlva kerülne elérhető közelségbe az 500 digites számok gyors faktorizálása. Utódainknak ekkor sem kell mást tenniük, mint a p és a q számokat hosszabbra választani.
Az RSA-algoritmus egy klasszikus iskolapéldáját mutatjuk be a 8.17. ábrán. A példa kedvéért kis számokat választottunk: 
és 
, amiből 
és 
adódik. A 
választás megfelelőnek tűnik, mivel 7-nek és 20-nak nincs közös osztója. A fenti értékekkel e könnyen kiszámolható a 
összefüggés alapján, amelyből 
. A P nyílt szöveg sifrírozott párja, C, a 
kifejezésből adódik. Az üzenet fogadója az eredeti szöveget a 
képlet segítségével kapja vissza. Az ábra a „SUZANNE” tartalmú üzenet kódolási lépéseit mutatja.
Mivel a példában szereplő prímeket készakarva kicsire választottuk, a P értékének is alacsonynak (33-nál kisebbnek) kell lennie, ezért egy kódolandó szövegblokk csak egy karaktert tartalmazhat. Ennek eredményeképpen egy egyszerű egybetű-helyettesítéses kódolót kapunk, ami nem túl hatásos. Ha ehelyett a p-t és q-t 
nagyságrendben választottuk volna meg, akkor az 
érték adódott volna, így minden blokk 1024 bitet vagy 128 darab 8 bites karaktert tartalmazhatott volna, szemben a DES 8 és az AES 16 karakterével.
Érdemes megjegyeznünk, hogy a fenti módon használt RSA hasonlóan viselkedik az ECB-módú szimmetrikus algoritmusokhoz abban a tekintetben, hogy ugyanaz a bemeneti blokk itt is mindig ugyanazt a kimeneti blokkot fogja eredményezni. Ennélfogva a titkosításnál célszerű valamilyen láncolást alkalmazni. A gyakorlatban azonban a legtöbb RSA-alapú rendszer a nyilvános kulcsokat csak egy, egyszer használatos viszonykulcs biztonságos szétosztására használja. A viszonykulcsot ezután hagyományos titkos kulcsként lehet felhasználni, például az AES- vagy a háromszoros DES-algoritmusokban. Az RSA túl lassú, ha nagy mennyiségű adatot kell titkosítani, de a kulcsok szétosztására széles körben használják.
Bár az RSA igen széles körben alkalmazott, korántsem ez az egyetlen ismert nyilvános kulcsú algoritmus. Az első nyilvános kulcsú eljárás a hátizsák- (knapsack) módszer volt [Merkle és Hellman, 1978]. Tegyük fel, hogy az üzenetet küldeni szándékozó fél nagyszámú különböző súlyú tárggyal rendelkezik. Az üzenet kódolásához a tárgyak közül titokban kiválaszt párat, és azokat a zsákba teszi. A zsák összsúlyát, valamint a szóba jöhető tárgyak listáját ezek után nyilvánosságra hozza. A zsákban levő tárgyak listáját titokban tartja. Néhány magától értetődő korlátozás mellett azon tárgyak listájának előállítása, mely adott össztömeggel rendelkezik, algoritmikusan nehéz feladat, és ez képezi a módszer alapját.
Az algoritmus kifejlesztője, Ralph Merkle, olyannyira biztos volt a módszer feltörhetetlenségében, hogy 100 dolláros díjat ajánlott fel annak, akinek mégis sikerül. Adi Shamir (az RSA-ban szereplő „S” betű tulajdonosa) hamarosan jelentkezett a megoldással a 100 dollárért. Merkle nem riadt vissza, így nemsokára 1000 dolláros díjat tűzött ki feljavított algoritmusának feltöréséért. Ron Rivest (az RSA „R” betűje) nem késlekedett a megoldással, és bezsebelte a díjat. Merkle ezek után nem mert a következő változatra 10 000 dolláros tétet tenni, így az „A” betű (Leonard Adleman) hoppon maradt. Annak ellenére, hogy újra javítottak rajta, a hátizsák algoritmust nem tekintik biztonságosnak, és nem igazán alkalmazzák.
Más nyilvános kulcsú módszerek a diszkrét logaritmus számításának számítási igényére alapoznak [Rabin, 1979]. El Gamal [1985] és Schnorr [1991] erre az elvre épülő algoritmusokat fejlesztett ki.
Létezik még pár másfajta séma is, mint például Menezes és Vanstone [1993] elliptikus görbéken alapuló módszere, de az eljárások alapvetően két nagy kategóriába sorolhatók: az egyikbe tartoznak a nagy számok faktorizálásának nehézségén alapuló, a másikba pedig a diszkrét logaritmusok nagy prímekkel vett modulusát számoló módszerek. Ezen problémák megfejtése tényleg nagyon nehéznek tekinthetők – a matematikusok sok éven át dolgoztak rajtuk, és nem értek el semmilyen jelentős áttörést.