A nyilvános kulcsú kriptográfia lehetővé teszi, hogy azok is biztonságosan kommunikálhassanak, akik nem rendelkeznek közös kulccsal. Lehetőség nyílik továbbá az üzenetek aláírására egy megbízható harmadik fél jelenléte nélkül is. Végül, az aláírt üzenetpecsétek segítségével a vett üzenetek sértetlensége is könnyen és biztonsággal ellenőrizhető.
Van azonban egy probléma, ami felett egy kicsit átsiklottunk: ha Aliz és Bob nem ismerik egymást, akkor hogyan szerzik meg egymás nyilvános kulcsát, hogy megkezdhessék a kommunikációt. A kézenfekvő megoldás – ti. hogy mindenki tegye fel a nyilvános kulcsát a weboldalára – a következők miatt nem működik. Tegyük fel, hogy Aliz meg akarja keresni Bob nyilvános kulcsát Bob weboldalán. Hogyan teszi ezt meg? Először is begépeli Bob URL-jét. A böngészője ekkor kikeresi Bob honlapjának DNS-címét, majd elküld egy GET kérést, amint azt a 8.23. ábra mutatja. Sajnálatos módon Trudy elfogja ezt a kérést, és egy hamis honlappal válaszol, ami valószínűleg Bob honlapjának másolata lesz, de nem Bob, hanem Trudy nyilvános kulcsát fogja tartalmazni. Amikor Aliz ezután kódolja az első üzenetét 
-vel, Trudy visszafejti azt, elolvassa, újra titkosítja Bob nyilvános kulcsával, majd elküldi Bobnak, akinek fogalma sincs arról, hogy Trudy olvassa a beérkező üzeneteit. Sőt még ennél is rosszabb, hogy Trudy módosíthatja is az üzeneteket, mielőtt újra kódolná azokat Bob számára. Nyilvánvalóan szükség van tehát valamilyen eljárásra a nyilvános kulcsok biztonságos cseréjéhez.
Első kísérletünk a nyilvános kulcsok biztonságos szétosztására az lehetne, hogy egy KDC-t (Key Distribution Center – kulcselosztó központ) kellene felállítani, mely 24 órás online üzemben, kérésre adná a nyilvános kulcsokat. Ezzel a megoldással több probléma is van, például nem skálázható, így a kulcselosztó központ hamar szűk keresztmetszetté válna. Ráadásul, ha a központ egyszer meghibásodna, akkor hirtelen az egész internetes biztonság odalenne.
Emiatt egy másik megoldást fejlesztettek ki, egy olyat, melyben a kulcselosztó központnak nem kell folyamatosan online lennie, sőt egyáltalán nem is kell online lennie. A központ itt csak annyit tesz, hogy hitelesíti az egyes személyekhez, vállalatokhoz és más szervezetekhez tartozó nyilvános kulcsokat. Az olyan szervezeteket, melyek a nyilvános kulcsokat hitelesítik, CA-nak (Certification Authority – tanúsító hatóság) nevezzük.
Példának okáért tegyük fel, hogy Bob szeretné lehetővé tenni, hogy Aliz és más emberek biztonságosan kommunikálhassanak vele. Elmehet tehát a CA-hoz, ahol benyújtja a nyilvános kulcsát az útlevelével vagy a jogosítványával együtt, és egy tanúsítványt kér. A CA erre egy, a 8.24. ábrán láthatóhoz hasonló tanúsítvány állít ki, amit saját kulcsának segítségével egy SHA-1 pecséttel lát el. Bob ezután befizeti a CA által kért díjat, és megkapja a floppylemezt, ami a tanúsítványt és az aláírt pecsétet tartalmazza.
A tanúsítvány alapvető feladata az, hogy hozzárendelje a nyilvános kulcsot a főszereplő (személy, vállalat stb.) nevéhez. Maguk a tanúsítványok nem titkosak és nem védettek. Bob úgy is dönthet például, hogy felrakja az új tanúsítványát a weboldalára, és a főoldalon elhelyez egy ilyen linket: „Kattintson ide, és megkapja a nyilvános kulcsú tanúsítványomat”. Kattintás után tehát megkapnánk a tanúsítványt és az aláírásblokkot (a tanúsítvány aláírt SHA-1 pecsétjét) is.
Menjünk most újra végig a 8.23. ábra forgatókönyvén! Mit tehet Trudy, amikor elkapja Aliz Bob honlapjára vonatkozó kérését? Rárakhatja saját tanúsítványát és aláírásblokkját a hamis oldalra, de ha Aliz meglátja a tanúsítványt, rögtön tudni fogja, hogy nem Bobbal beszél, mert abban nem szerepel Bob neve. Trudy röptében is módosíthatja Bob honlapját, kicserélve Bob nyilvános kulcsát a sajátjával. Csakhogy amikor Aliz lefuttatja az SHA-1 algoritmust a tanúsítványon, akkor olyan pecsétet kap, ami nem egyezik meg azzal, amit akkor kap, ha a CA jól ismert nyilvános kulcsát alkalmazza az aláírásblokkra. Trudy nem rendelkezik a CA egyéni kulcsával, ezért sehogy sem tud olyan aláírásblokkot előállítani, amelyik az ő nyilvános kulcsát magában foglaló módosított weboldal pecsétjét tartalmazná. Ily módon Aliz biztos lehet abban, hogy Bob nyilvános kulcsával rendelkezik, nem pedig Trudyéval vagy valaki máséval. Emellett, ahogy ígértük, ez a séma nem igényli azt, hogy a CA online ellenőrizhető legyen, ezáltal megszűnik egy esetleges szűk keresztmetszet.
A tanúsítványok szokásos feladata a nyilvános kulcsok és a főszereplők egymáshoz rendelése, de ezenkívül arra is fel lehet használni őket, hogy egy nyilvános kulcshoz egy attribútumot (attribute) rendeljenek. Egy tanúsítvány például azt is kimondhatja: ez a nyilvános kulcs olyasvalakihez tartozik, aki már elmúlt 18 éves. Használható tehát például annak igazolására, hogy a kulcs tulajdonosa már nem kiskorú, így engedélyezett számára a nem gyerekeknek szánt tartalomhoz való hozzáférés stb. Mindez a tulajdonos személyazonosságának felfedése nélkül lehetséges. Egy ilyen tanúsítványt az illető jellemzően egy olyan weboldalnak, főszereplőnek vagy folyamatnak küld el, amelynél fontos az életkor. Az adott oldal, főszereplő vagy folyamat erre előállít egy véletlen számot, és titkosítja azt a tanúsítványban található nyilvános kulccsal. Ha a tulajdonosnak sikerül ezt dekódolnia és az eredményt visszaküldenie, akkor az azt bizonyítja, hogy az illető tényleg rendelkezik a tanúsítványban kiállított attribútummal. Vagy egy másik megoldás lehet az is, hogy a véletlen számot egy viszonykulcs előállítására használják fel, mely az azt követő üzenetváltást fogja biztosítani.
A tanúsítvány például egy objektumorientált elosztott rendszerben is tartalmazhat attribútumot. Rendszerint minden objektumnak több metódusa van. Az objektum tulajdonosa minden ügyfelének adhat egy tanúsítványt, mely egy olyan bittérképet tartalmaz, ami megadja, hogy az adott ügyfél melyik metódusokat hívhatja meg. Magát a bittérképet pedig egy nyilvános kulcshoz lehet rendelni egy aláírt tanúsítvány segítségével. Ha a tanúsítvány tulajdonosa igazolni tudja, hogy rendelkezik a megfelelő egyéni kulccsal, akkor végrehajthatja a bittérkép által megjelölt műveleteket. Itt is megtalálhatjuk tehát azt a tulajdonságot, hogy a tulajdonos kilétének ismeretére nincs szükség, ez pedig jól jön azokban a helyzetekben, ahol fontosak a személyiségi jogok.
Ha mindenki a saját típusú tanúsítványát szeretné aláíratni a CA-val, akkor a különböző formátumok kezelése hamar gondot okozna. Épp ezért kidolgoztak egy tanúsítványokra vonatkozó szabványt, amit az ITU is elfogadott. A szabvány neve X.509, és az interneten széles körben használják. Szabványosításának kezdete, vagyis 1988 óta már három verziót élt meg, mi ezek közül a harmadikat tárgyaljuk.
Az X.509-re erős hatással volt az OSI világa olyannyira, hogy át is vett néhányat az OSI legrosszabb tulajdonságaiból (például a névkezelést és a kódolást). Meglepő módon az IETF is egyetértett az X.509-cel, bár a gépek címzésétől kezdve a szállítási protokollokon át az e-levél formátumokig szinte minden más területen általában figyelmen kívül hagyta az OSI-t, és a maga útját járta. Az IETF-féle X.509-et az RFC 5280 írja le.
Az X.509 lényegében a tanúsítványok leírására ad módot. A tanúsítványok legfontosabb mezőit a 8.25. ábra sorolja fel. Reméljük, az ábra megjegyzéseiből mindenkinek sikerül képet alkotni az egyes mezők funkcióiról, aki pedig még többet szeretne tudni, az tanulmányozza magát a szabványt vagy az RFC 2459-öt.
Például, ha Bob a kölcsönökért felelős részlegben dolgozik a Pénzes Banknál, akkor az X.500-as címe valami ilyesmi lehet:
/C=US/O=PenzesBank/OU=Kolcson/CN=Bob/
ahol a C az országot, O a szervezetet, OU a szervezeti egységet, a CN pedig a hétköznapi nevet jelenti. A CA-kat és más entitásokat is hasonló módon nevezik meg. Az X.500-as nevek egyik legnagyobb problémája az, hogy ha Aliz a bob@penzesbank.com címmel szeretné felvenni a kapcsolatot, akkor az X.500-as nevet tartalmazó tanúsítványból nem biztos, hogy egyértelműen ki tudja deríteni, hogy a tanúsítvány vajon arra a Bobra vonatkozik-e, akire ő gondolt. Szerencsére a 3. verziótól kezdve már DNS-neveket is lehet használni az X.500-as nevek helyett, ez a probléma tehát idővel megszűnhet.
A tanúsítványokat az OSI ASN.1 (Abstract Syntax Notation 1 – absztrakt szintaxisjelölés 1) szerint kódolják, ami voltaképpen egy C struktúrához hasonló, de nagyon különös és terjengős jelölésmód. Az X.509-ről többet is olvashatunk Ford és Baum [2000] munkájában.
Nyilvánvalóan nem kivitelezhető az, hogy egyetlen CA adja ki a világ összes tanúsítványát, hiszen egy ilyen központ összeomlana a nagy terhelés miatt, és a hibák gócpontja is lenne. Elképzelhető lenne egy olyan megoldás is, mely szerint egyetlen nagy szervezet több CA-t is működtetne, amelyek mind ugyanazt az egyéni kulcsot használnák a tanúsítványok aláírására. Ez megoldaná a terhelés és a hibák problémáját, de újabb gonddal járna: megjelenne a kulcsszivárgás. Ha szerte a világon több tucatnyi kiszolgáló rendelkezne a CA egyéni kulcsával, akkor nagyban megnőne annak az esélye, hogy a kulcsot ellopják vagy valami egyéb módon kiszivárog. Nagyon kockázatos dolog lenne tehát egyetlen központi CA-t üzemeltetni, hiszen a kulcs gyanúba keveredése az egész világ elektronikus biztonsági infrastruktúráját romba dönthetné.
Ráadásul nagy kérdés is, hogy melyik szervezet üzemeltetné a CA-t. Nehéz elképzelni egy olyan hatóságot, amit a világon mindenhol törvényesnek és megbízhatónak tartanak. Az emberek egyes országokban ragaszkodnának ahhoz, hogy a kormány legyen ez a szerv, máshol meg azt követelnék, hogy ne a kormány legyen.
Ezen okok miatt egy másfajta módja alakult ki a nyilvános kulcsok hitelesítésének. Az eljárás általános neve a PKI (Public Key Infrastructure – nyilvános kulcs infrastruktúra). Ennek általános működését foglaljuk össze ebben a szakaszban. A témában sok új javaslat is született, a részletek tehát változhatnak még az idővel.
A PKI-nek számos összetevője van, köztük felhasználók, CA-k, tanúsítványok és könyvtárak. A PKI lényegében annyit tesz, hogy módot ad ezen összetevők szervezetbe rendezésére, és szabványokat definiál a különféle dokumentumok és protokollok számára. A PKI egyik különösen egyszerű formája a CA-k hierarchiája, amit a 8.26. ábra mutat be. A példában három szintet ábrázoltunk, de a gyakorlatban lehet ennél több vagy kevesebb szint is. A legfelső szintű CA, a gyökér a második szintű CA-kat hitelesíti, melyeket RA-nak (Regional Authorities – regionális hatóságok) nevezünk, mert egy földrajzi régiót (például országot vagy kontinenst) foghatnak át. Ez az elnevezés ugyanakkor nem szabványos, sőt valójában a fa egyéb szintjeinek neve sem igazán az. Az RA-k pedig a tényleges CA-kat hitelesítik, melyek aztán kiadják az X.509 tanúsítványokat a szervezeteknek és a magánszemélyeknek. Amikor a gyökér engedélyez egy új RA-t, akkor kiállít egy X.509 tanúsítványt, mely kimondja, hogy az RA-t jóváhagyták, valamint tartalmazza az új RA nyilvános kulcsát. A gyökér ezután aláírja a tanúsítványt, és átadja az RA-nak. Hasonlóképpen, amikor egy RA hagy jóvá egy új CA-t, akkor kiállít és aláír egy tanúsítványt, mely megerősíti a jóváhagyást és tartalmazza a CA nyilvános kulcsát.
Példánk PKI-je a következőképp működik. Tegyük fel, hogy Aliz kommunikálni szeretne Bobbal, ezért szüksége van Bob nyilvános kulcsára. Keres tehát egy, a kulcsot tartalmazó tanúsítványt, és talál is egyet, melyet a CA 5 írt alá. Aliz azonban még sohasem hallott a CA 5-ről, felőle az akár Bob 10 éves kislánya is lehetne. Elmehet tehát a CA 5-höz, és azt mondhatja: „Kérem, igazolja a jogosultságát!” A CA 5 erre az RA 2-től kapott tanúsítvánnyal válaszol, ami tartalmazza a CA 5 nyilvános kulcsát. Aliz a CA 5 nyilvános kulcsának birtokában meggyőződhet róla, hogy Bob tanúsítványát tényleg a CA 5 írta alá, tehát hiteles.
Feltéve persze, hogy az RA 2 szerepét nem Bob 12 éves fia játssza el. A következő lépés tehát az, hogy Aliz az RA 2-t kéri fel a jogosultságának igazolására. Válaszul egy tanúsítványt kap a gyökér aláírásával, mely tartalmazza az RA 2 nyilvános kulcsát. Aliz tehát már biztos lehet benne, hogy tényleg Bob nyilvános kulcsával rendelkezik.
De honnan ismeri Aliz a gyökér nyilvános kulcsát? Most jön a trükk! Feltételezzük, hogy a gyökér nyilvános kulcsát mindenki ismeri. Elképzelhető például, hogy a böngészőjébe előre beépítették a gyökér kulcsát.
Bob persze nagyon rendes, és nem akar Aliznak ennyi fáradságot okozni. Tudja, hogy Aliz ellenőrizni fogja a CA 5-öt és az RA 2-t, ezért hogy Aliznak ne legyen rá gondja, ő maga gyűjti össze a két tanúsítványt, és a sajátjával együtt átadja azokat Aliznak. Aliz a gyökér nyilvános kulcsának ismeretében ellenőrizheti a legfelső szintű tanúsítványt, majd az abban található nyilvános kulcs segítségével a másodikat is. Ily módon Aliznak senkivel nem kell felvennie a kapcsolatot ahhoz, hogy elvégezhesse az ellenőrzést. A tanúsítványok pedig mind alá vannak írva, ezért könnyen észre lehetne venni, ha valaki megpróbálná átírni a tartalmukat. A gyökérhez ilyen módon visszavezető tanúsítványok láncát néha bizalmi láncnak (chain of trust) vagy tanúsítvány-útvonalnak (certification path) is nevezik. Az eljárást széles körben alkalmazzák a gyakorlatban.
Természetesen még mindig kérdéses, hogy ki fogja üzemeltetni a gyökeret. A megoldás az, hogy ne egy gyökér legyen, hanem több, és mindegyikhez saját RA-k és CA-k tartozzanak. A modern böngészőkbe valójában több mint 100 gyökér nyilvános kulcsa van eleve beépítve – ezekre bizalmi horgony (trust anchor) néven is szoktak hivatkozni. Ily módon tehát nincs szükség egyetlen, világszerte bizalmat élvező hatóságra.
Ez viszont azt a kérdést veti fel, hogy hogyan tudja eldönteni a böngésző gyártója, hogy a beépített bizalmi horgonyok közül melyik megbízható és melyik nem. Végeredményben minden azon múlik, hogy a felhasználó mennyire bízik meg abban, hogy a böngésző gyártója okosan választ, és nem fogad el minden olyan horgonyt, ami hajlandó lenne megfizetni a bekerülés díját. A böngészők többsége lehetővé teszi, hogy a felhasználó megvizsgálhassa a gyökerek kulcsait (általában a gyökér által aláírt tanúsítványok formájában), és letörölhesse azokat, melyek gyanúsnak tűnnek.
A PKI további kérdése, hogy hol tároljuk a tanúsítványokat (és azok valamely bizalmi horgonyhoz visszavezető láncát). Az egyik lehetőség az, hogy minden felhasználó maga tárolja a saját tanúsítványát. Ez a megoldás biztonságos ugyan (az aláírt tanúsítványokat nem lehet módosítani anélkül, hogy észrevennék a turpisságot), de egyben kényelmetlen is. Egy másik javasolt alternatíva szerint a DNS-t is lehetne tanúsítványkönyvtárnak használni. Ha a kapcsolatfelvétel előtt Aliznak úgyis ki kell keresnie Bob IP-címét a DNS segítségével, akkor miért ne lehetne az IP-címmel együtt mindjárt Bob teljes tanúsítványláncát is visszaadni?
Egyesek szerint ez jelenti a megoldást, mások azonban szívesebben látnának külön erre a célra kijelölt könyvtárkiszolgálókat, melyeknek csak az X.509-es tanúsítványok kezelése lenne a feladatuk. Az ilyen könyvtárakban az X.500-as nevek tulajdonságai alapján lehetne kereséseket végezni. Egy ilyen könyvtárszolgáltatás elméletileg válaszolni tudna például egy ilyen kérésre: „Adja meg az összes olyan Aliz nevű személy listáját, aki egy kereskedelmi osztályon dolgozik valahol az USA-ban vagy Kanadában!”
A való világ is tele van tanúsítványokkal: ilyenek például az útlevelek vagy a jogosítványok is. Ezeket a tanúsítványokat esetenként vissza is lehet vonni – egy jogosítványt például be lehet vonni ittas vezetésért vagy más közlekedési vétségekért. A digitális világban is jelentkezik ez a probléma: a kiállító szerv olykor dönthet úgy, hogy visszavonja a tanúsítványt, mert az azt birtokló személy vagy szervezet valamilyen módon visszaélt vele. A tanúsítvány visszavonható akkor is, ha kitudódott az alany egyéni kulcsa, vagy ami még rosszabb, ha a CA egyéni kulcsa keveredett gyanúba. A PKI-nek tehát foglalkoznia kell a visszavonás kérdésével. A visszahívás lehetősége bonyolítja a dolgot.
Az első lépés ebben az irányban az, hogy az egyes CA-k bizonyos időközönként kiadnak egy CRL-t (Certificate Revocation List – tanúsítvány-visszavonási lista), amely megadja az adott CA által visszavont tanúsítványok sorszámainak listáját. Mivel a tanúsítványoknak lejárati idejük is van, a CRL-eknek csak a még nem lejárt tanúsítványok sorszámait kell tartalmazniuk. A tanúsítványok ugyanis automatikusan érvénytelenné válnak, ha az idejük lejár, nincs szükség tehát a lejárt és a ténylegesen visszahívott tanúsítványok megkülönböztetésére. Akár így történt, akár úgy, többé nem használhatók.
Sajnos a CRL-ek bevezetése azt is maga után vonja, hogy a tanúsítványt használni készülő felhasználónak meg kell szereznie a CRL-t, hogy megnézze, visszavonták-e az adott tanúsítványt. Ha igen, akkor nem szabad használni. Lehetséges azonban, hogy a tanúsítvány nem szerepel a listán, de épp a lista kiadása után visszavonták. Az igazság kiderítésének egyetlen módja tehát az, hogy megkérdezzük a CA-t. Ha később újra használni akarjuk az adott tanúsítványt, akkor megint a CA-hoz kell fordulni, hiszen lehet, hogy épp csak pár másodperce történt a visszavonás.
Tovább bonyolítja a helyzetet, hogy a visszavont tanúsítványt akár újra érvénybe is helyezhetik, például ha azért lett visszavonva, mert a tulajdonosa nem fizetett be valamilyen díjat, de később rendezte a tartozását. A visszavonások (és az esetleges újra érvénybe helyezések) kezelése miatt épp a tanúsítványok egyik legjobb tulajdonságáról kell lemondanunk, mégpedig arról, hogy a CA-val való kapcsolatfelvétel nélkül is lehetett használni azokat.
Hol lenne célszerű a CRL-eket tárolni? Jó ötlet lenne ugyanoda tenni őket, ahol maguk a tanúsítványok is vannak. Az egyik stratégia szerint a CA időnként magától kiadná a CRL-eket, a könyvtárszolgáltatások pedig a CRL-ek alapján egyszerűen törölnék a visszavont tanúsítványokat. Ha a tanúsítványokat éppen nem könyvtárakban tároljuk, akkor a CRL-eket a hálózat számos más kényelmesen elérhető helyén is el lehet helyezni. Mivel a CRL maga is aláírt dokumentum, könnyen észrevehető lenne, ha valaki esetleg belenyúlna a tartalmába.
Ha a tanúsítványoknak hosszú az élettartama, akkor a CRL-ek is hosszúak lesznek. Ha a hitelkártyák például 5 évig érvényesek, akkor az esedékes visszavonások száma sokkal nagyobb lesz, mint ha 3 havonta mindig új kártyákat adnának ki. A hosszú CRL-eket általában úgy kezelik, hogy néha kiadnak egy nagy listát, és gyakrabban kiadják a lista aktuális változásait. Ezzel csökken a CRL-ek szétosztásához szükséges sávszélesség is.