A szimmetrikus titkosítás évezredeken keresztül kielégítette az igényeket, mert a bizalmas üzenetcserét csak nagyon korlátozott körben és jól szervezett közösségekben – hadsereg, rendőrség, titkosszolgálatok – alkalmazták. A kommunikációs, majd az informatikai hálózatok megjelenésével és elterjedésével a bizalmas üzenetcserére megnőtt az igény. Banki vagy egészségügyi adatokat például nem szabad nyilvános csatornán, titkosítás nélkül továbbítani. A szimmetrikus algoritmusok, például a DES elég gyors és biztonságos volt a múlt század hetvenes éveiben, de volt egy gyenge pontja: a titkosító (és visszafejtő) kulcsot mindkét partnernek ismernie kell az üzenetcseréhez. A kulcsot tehát biztonságos módon kell eljuttatni a partnerhez, más nem szerezheti meg és a fogadó félnek biztosnak kell lenni abban, hogy attól kapta a kulcsot, aki ezt állítja magáról. A klasszikus módszerek: a kulcs előzetes egyeztetése, futár vagy postagalamb alkalmazása lassú, egyedi és nagyon drága megoldás, az infokommunikációs hálózatok korában nem használható.
A problémát Whitfield Diffie és Martin E. Hellman fogalmazta meg egy 1976-ban megjelent dolgozatukban. Egyben megfogalmazták a megoldás elvét is, amelynek lényege: minden felhasználó (feladó és címzett egyaránt) rendelkezik egy kulcspárral, ami egy nyilvános (public) és egy titkos (private) kulcsot tartalmaz. A mindenki számára elérhető nyilvános kulcs a titkosításhoz, a csak a tulajdonosa által ismert privát kulcs pedig a visszafejtéshez használatos. Fontos megjegyezni, hogy a nyilvános kulcsból a titkos kulcs nem számítható ki még az előállításukra szolgáló algoritmus ismeretében sem.
Az előző ábra a nyilvános kulcsú titkosítás folyamatát mutatja. Amikor Kriszta bizalmas üzenetet akar küldeni Aladárnak, akkor elkéri vagy megkeresi Aladár nyilvános kulcsát. Ezzel kódolja az üzenetet és elküldi például e-mailben Aladárnak. Aladár a saját titkos kulcsával fejti meg – dekódolja – Kriszta üzenetét. Ha válaszolni akar, akkor persze Kriszta nyilvános kulcsával titkosít.
A két kulcs tehát egymást kiegészítve működik; a címzett nyilvános kulcsával titkosítjuk az üzenetet, amit rajta kívül más nem tud elolvasni, hiszen csak ő rendelkezik a visszafejtést végző titkos kulccsal. A módszer erősségét a szimmetrikus kulcsos titkosítás hátrányának kiküszöbölése adja: azok is tudnak titkosított üzeneteket váltani, akik nem ismerik egymást (elég, ha előzőleg kicserélték nyilvános kulcsaikat). Ez a csere történhet Interneten keresztül is, hiszen attól, hogy valaki megszerzi a nyilvános kulcsunkat még nem fér hozzá bizalmas információkhoz. További előnyös tulajdonsága, a digitális aláírás készítésének lehetősége, mely opciót a hitelességvizsgálat céljából érdemes kihasználni. Ezzel egy későbbi fejezetben részletesen foglalkozunk.
Diffie és Hellman dolgozata nyitva hagyta azt a problémát, hogy van-e nyilvános kulcsú kódolási eljárás. Cikkük megjelenése után azonban számos javaslat jelent meg a probléma gyakorlati megvalósítására a tudományos irodalomban. Ezek közül néhányról több-kevesebb idő után kiderült, hogy nem felel meg a követelményeknek. Az egyik legelső algoritmus, az RSA, azonban máig feltörhetetlennek bizonyult és széles körben elterjedt.
Az RSA-t 1977-ben publikálta Ronald Rivest, Adi Shamir és Leonard Adleman és családi neveik kezdőbetűiből lett az RSA betűszó. Algoritmusuk elemi számelméleti ötleten alapszik.
Legyenek p és q különböző prímszámok, azaz olyan természetes számok, amelyeknek 1-en és önmagukon kívül nincs más osztójuk. Prímszámok például a 2,3,5,7,… Az ókori görög matematikus Eukleidész Elemek című könyvében szerepel annak bizonyítása, hogy végtelen sok prímszám létezik. A XIX. sz. vége óta azt is tudjuk, hogy a prímszámok elég gyakoriak. Annak a valószínűsége ugyanis, hogy egy véletlenszerűen kiválasztott x-nél kisebb szám prímszám legyen 1/ln x. A Miller-Rabin teszttel gyorsan eldönthető, hogy egy szám prímszám-e. (Pontosabban, ha egy szám átmegy a Miller-Rabin teszten, akkor csak azt mondhatjuk, hogy nagy valószínűséggel prímszám. Ez azonban a gyakorlatban elegendő. 2002-ben Manindra Agrawal, Neeraj Kayal és Nitin Saxena indiai informatikusok publikáltak egy polinom idejű determinisztikus prímszámtesztet, amelynek hatékonysága azonban ma még nem vetekedik a Miller-Rabin teszttel.)
Nagy prímszámokat tehát könnyű találni, de ha két ilyet összeszorzunk, akkor csak a szorzatot ismerve nagyon nehéz a tényezőket megtalálni. Ezt a faktorizáció problémájának nevezik, ami tudásunk szerint egy nagyon nehéz algoritmikus probléma.
Legyenek p és q különböző prímszámok és n=qp. Ekkor az n-nél kisebb, n-hez relatív prím természetes számok száma φ(n) = (p-1)(q-1). Ezt az értéket p és q ismeretében könnyű kiszámítani. A φ függvényt Euler függvénynek nevezzük. Legyen most e egy olyan φ(n)-hez relatív prím természetes szám, amelyik kisebb φ(n)-nél. Akkor pontosan egy olyan 1 <= d < φ(n) természetes szám létezik, amelyre ed mod φ(n) = 1. Itt és a továbbiakban a mod m jelenti az a természetes szám maradékát m-mel osztva. Ezek után a nyilvános kulcs az e,n számpáros, a titkos kulcs pedig a d szám. A kulcsok meghatározása után a p és q értékét is titokban kell tartani vagy ezeket a számokat meg kell semmisíteni.
A kódolás során az üzenetet először számok sorozatává alakítjuk olyan módon, hogy a számok mindegyike kisebb legyen, mint n. Ez könnyen megtehető, hiszen az üzenetet a számítógépben bináris alakban tároljuk és most ezt a bináris sorozatot, mint egy kettes számrendszerben megadott szám számjegyeit értelmezzük. Ezután az egyes m számokat az
M = me mod n
képlettel kódoljuk előállítva a rejtjelezett M üzenetet. A kódoláshoz csak a nyilvános kulcsot, az e,n számpárt kell ismerni! A titkos M üzenetet az
m = Md mod n
képlet alapján lehet dekódolni. A visszafejtéshez tehát a titkos d kulcs ismerete kell!
A kódolás és dekódolás során is moduláris hatványozást kell végezni, amelyik az „intelligens” hatványozó algoritmussal elfogadható gyorsasággal elvégezhető. Az elemi számelméletből jól ismert Euler-Fermat tételből következik, hogy a dekódolás után tényleg az eredeti üzenetdarabot kapjuk vissza.
Az algoritmus ismertetése után néhány megjegyzést teszünk az RSA paraméterek megválasztásával kapcsolatban. A titkos kulcs – d – mai ismereteink szerint csak a φ(n) birtokában számítható ki, φ(n) meghatározása viszont ugyanolyan nehézségű, mint n prímtényezőkre bontása. Az RSA biztonsága tehát azon múlik, hogy milyen gyorsan tudjuk az n számot faktorizálni. Ha p és q és így n is kicsi, akkor ez egyszerű feladat. Növelve azonban p-t és q-t egyre nehezebb, ma még megoldhatatlan problémához jutunk. A felhasznált számoknak olyan nagyoknak kell lenniük, hogy az n számot ne lehessen prímtényezőkre bontani. Ma azt mondhatjuk, hogy n-nek legalább 1024 bináris, azaz kb. 308 decimális jegyű számnak kell lennie. A faktorizáló algoritmusok pillanatnyi csúcsteljesítménye az RSA-200, egy 200 decimális jegyű szám tényezőkre bontása, amelyet közel két év munka után 2005-ben fejezett be egy 80 számítógépből álló klaszter.
A p és q megválasztása során nemcsak a nagyságukra kell figyelni, hanem arra is, hogy a különbségük is nagy legyen. Ellenkező esetben ugyanis a Fermat faktorizációs algoritmus gyorsan megtalálja a tényezőket. Feltéve, hogy az n 1024 bites szám, p és q-t 512 bitesnek célszerű választani úgy, hogy a különbségük legalább 400 bit nagyságú legyen.
Az n szám megválasztása után áttérünk e és d közelebbi elemzésére. Fentebb leírtuk, hogy d értékét az e és φ(n) egyértelműen meghatározza. Az is jól ismert, hogy d értékét a kiterjesztett euklideszi algoritmussal könnyen ki tudjuk számítani. A nyilvános kulcsdarab – e – megválasztására általában kétféle módszert követnek: az e-t véletlenszerűen választjuk ki az [1, φ(n)-1] intervallumból vagy olyan kis, páratlan számnak választjuk, amelynek bináris felírásában kevés 1-es számjegy található, például 17 vagy 65537. Az első esetben nem biztos, hogy rögtön olyan számot választunk, amelyik relatív prím φ(n)-hez, ilyenkor meg kell ismételni a választást, amíg ez a feltétel nem teljesül. Be lehet bizonyítani, hogy néhány választás után ez igen nagy valószínűséggel teljesül.
Az aszimmetrikus titkosítás elvének megfogalmazása óta eltelt több, mint 30 évben számos más algoritmust is javasoltak, például a diszkrét logaritmus kiszámításának nehézségén alapuló ElGamal, a diszkrét elliptikus görbéket alkalmazó algoritmus vagy a hibajavító kódok dekódolásának bonyolultságára építő Mc Ellise módszer. Ezekkel most nem foglalkozunk.
A nyilvános kulcsú titkosítás előnye, hogy a titkos kulcsot csak egy ember ismeri, így titkosított üzenetet nyilvános csatornán is lehet vele küldeni. A gyakorlatban azonban ez az előny csak korlátozottan aknázható ki, mert a jelenleg ismert módszerekkel a kódolás (és dekódolás) nagyságrendekkel tovább tart, mint a szimmetrikus algoritmusokkal. Ezért az aszimmetrikus módszereket csak rövid üzenetek kódolására célszerű alkalmazni. Ezen az észrevételen alapulnak az úgynevezett hibrid kriptorendszerek, amelyeknél egy szimmetrikus és egy aszimmetrikus módszert – pl. AES és RSA – kombinálnak a következőképpen:
6 - Kriszta választ egy K kulcsot a szimmetrikus algoritmushoz,
7 - K-t Aladár nyilvános kulcsával kódolva elküldi Aladárnak,
8 - Aladár a titkos kulcsával visszafejti K-t,
9 - A bizalmas információcsere K használatával a szimmetrikus algoritmussal történik.
A kulcscserének vannak olyan variánsai is, amelyekben a szereplők egyforma mértékben veszik ki részüket a közös kulcs kiszámításában. A hibrid kriptorendszer működését úgy is felfoghatjuk, hogy a klasszikus szcenárióban alkalmazott futár szerepét az aszimmetrikus titkosítás veszi át. Ilyen elven működik a távoli számítógépre való biztonságos bejelentkezésre szolgáló ssh (secure shell) szabványcsalád.
Az aszimmetrikus titkosításnak a kulcscserén kívül vannak más, fontos alkalmazásai is. Korábban már hangsúlyoztuk, hogy a titkos kulcsot csak egyetlen ember, a tulajdonosa ismeri, így a titkos kulcs egyértelműen azonosítja a tulajdonosát. A titkos kulcsot persze nem kérhetjük el igazoltatáskor a tulajdonosától, mert ha odaadná, akkor az igazoltató is megismerné azt és a tulajdonos többé már nem is használhatná. Olyan módszert kell tehát kitalálni, amely során a tulajdonos nem fedi fel titkos kulcsát, hanem csak bizonyítja, hogy ő rendelkezik a titkos kulccsal. Mivel az eljárás nagyon hasonlít a digitális aláírásnál alkalmazott módszerhez, ezért a következő fejezetben foglalkozunk vele.