Episode I

Alice és Bob

9. fejezet

Alice és Bob nyilvános kulcsot használ

A 6., a 7. és a 8. fejezetben egy algoritmuselméleti kitérő keretében eléggé pontosan tisztáztuk, hogy mit értünk "könnyű" illetve "nehéz" algoritmikus feladat alatt. Ezért ebben a fejezetben visszatérünk Alice és Bob fő problémájához, és ott folytatjuk, ahol az 5. fejezetben abbahagytuk. Nevezetesen: ahhoz, hogy biztonságosan tudjanak kommunikálni egymással, Alice-nak és Bob-nak először egy kulcsnak nevezett közös titokban kell megállapodniuk. Ezt neveztük a kulcsmegosztás problémájának. A 20. század végéig tartotta magát az a hittétel, miszerint ez kizárólag biztonságos csatornán keresztül – például személyes találkozó – oldható meg. De vajon mit tehet Alice és Bob, ha ilyen csatorna nem áll rendelkezésükre? Hogyan működik és hogyan támadható a Diffie-Hellmann kulcscsere protokoll? Mi az az aszimmetrikus kulcsú rejtjelezés? Ebben a fejezetben erről lesz szó...

Figyelem! Ennek a fejezetnek a megértéséhez erősen ajánlott elolvasni az 5. fejezetet is.

Az összes eddig vizsgált rejtjelezési eljárás nagyon hasonlóan működött. Alice-nak lényegében egy $E$ rejtjelezőt, míg Bob-nak egy $D$ dekódolót kellett paramétereznie egy közös $k$ kulccsal ahhoz, hogy biztonságosan kommunikálni tudjanak egymással.

**9.1. ábra:** Szimmetrikus kulcsú rejtjelező modell

A $k$ -val paraméterezett $E$ rejtjelező az $x$ nyílt szövegből előállítja az $y$ kódszöveget, míg a vételi oldalon a szintén $k$ -val paraméterezett $D$ dekódoló az $y$ kódszövegből visszaállítja az $x$ nyílt szöveget. A biztonság szempontjából megköveteljük, hogy amennyiben a támadó nem ismeri a $k$ kulcsot, akkor számára algoritmikusan nehéz feladat legyen az $x$ nyílt szöveget előállítani pusztán az $y$ kódszöveg ismeretében. Ezt a felállást szimmetrikus kulcsú titkosításnak nevezzük, mivel Alice ugyanazt a $k$ kulcsot használja a rejtjelezéshez, mint amit Bob használ a dekódoláshoz. Ilyenekre a korábbi fejezetekben láttunk pár példát: Caesar-kód, Vigenére-kód, a német Enigma vagy akár az 5. fejezetben bemutatott, ténylegesen feltörhetetlen one-time-pad.

1976-ban azonban megjelent Whitfield Diffie és Martin Hellman Új direktívák a kriptográfiában című írása, amely két forradalmian új ötletet tartalmazott. Egyrészt ez az írás ismerteti az úgynevezett Diffie-Hellman kulcscsere protokollt, amelynek a segítségével Alice és Bob képes megállapodni egy közös kulcsban egy nem biztonságos csatornán keresztül oly módon, hogy az mégis rejtve marad a csatornát lehallgató Eve elől. Másrészt pedig az írásból körvonalazódott az úgynevezett aszimmetrikus kulcsú titkosítás alapgondolata – habár a konkrét eljárást végül nem ők, hanem Ron Rivest, Adi Shamir és Len Adleman fejlesztették ki 1977-ben. Ezt a feltalálók vezetékneveinek kezdőbetűi után RSA eljárásnak nevezzük, amely napjaink egyik leggyakrabban használt titkosítási eljárása. Ez a rejtjelezésen kívül partner- és üzenethitelesítést is biztosít Alice és Bob számára. Mindkét eljárás működése az úgynevezett egyirányú függvényeken alapszik, ezért először ezzel a fogalommal – és általánosságban a függvény fogalmával – ismerkedünk meg.

9.1Ismét a függvényekről

A 6.2. szakaszban a Turing-gépek kapcsán már felmerült a függvény fogalma. Ott adva volt egy Turing-gép, amely a bemeneti szalagjára írt jelsorozatból a futása során a kimeneti szalagján előállított egy másik jelsorozatot. Azt mondhatjuk tehát, hogy a Turing-gép valamilyen hozzárendelést valósít meg a szimbólumkészletéből alkotható jelsorozatok között. Ezt a hozzárendelést a 6.4. szakaszban a Turing-gép által kiszámított függvénynek neveztük. Az alábbiakban egy ennél általánosabb definíciót adunk a függvény fogalmára.

Általánosságban egy függvény is egy hozzárendelést valósít meg két tetszőleges – nem feltétlenül különböző – halmaz között. Egy halmazt úgy kell elképzelni, mint bizonyos objektumok – például számok – gyűjteményét. Alaphalmaznak nevezzük azt a halmazt, amelyek közül a bemenetek, míg képhalmaznak nevezzük azt a halmazt, amelyek közül a kimenetek kerülhetnek ki. Az alaphalmaz és a képhalmaz lehet különböző, ezt azonban nem követeljük meg. A mostani példánkban jelöljük $A$ -val az alaphalmazt, $B$ -vel pedig a képhalmazt.

Ekkor egy olyan $f$ hozzárendelést, amely az $A$ halmaz minden eleméhez legfeljebb egy $B$ -beli elemet rendel hozzá, az $A$ alaphalmazból a $B$ képhalmazba képező függvénynek nevezzük és így jelöljük:

f:A \to B

Ha például $x$ az $A$ alaphalmaz egy olyan eleme, amelyhez az $f$ függvény hozzárendel egy $B$ -beli elemet, akkor ezt az elemet az $x$ képének nevezzük és így jelöljük:

f(x)

Elképzelhető, hogy az alaphalmaz nem minden elemének van képe, azonban fontos megkötés, hogy minden elemnek legfeljebb egy képe lehet. Az alaphalmaz azon részét, amely a képpel rendelkező elemeket tartalmazza, a függvény értelmezési tartományának nevezzük. Hasonlóan elképzelhető, hogy a képhalmaz nem minden eleme képe az alaphalmaz valamely elemének, itt viszont már nincs megkötés arra vonatkozóan, hogy a képhalmaz egy adott eleme hány alaphalmazbeli elemnek lehet képe. Ha például $x$ és $y$ az alaphalmaz két különböző eleme, akkor elképzelhető, hogy a képük ugyanaz az elem a képhalmazban, azaz $f(x)=f(y)$ . A képhalmaz azon részét, amely azokat az elemeket tartalmazza, amelyek képei legalább egy alaphalmazbeli elemnek, a függvény értékkészletének nevezzük.

**9.2. ábra:** Függvény értelmezési tartománya és értékkészlete

A halmazok közötti ilyen jellegű tartalmazási viszonyokra azt mondjuk, hogy a szűkebb halmaz részhalmaza a bővebb halmaznak. Itt például a $C$ értelmezési tartomány részhalmaza az $A$ alaphalmaznak, mivel $C$ minden eleme egyben $A$ -nak is eleme. Hasonlóan a $D$ értékkészlet is részhalmaza a $B$ képhalmaznak, mivel $D$ minden eleme egyben $B$ -nek is eleme.

Jogosan merülhet fel a kérdés az Olvasóban, hogy mi értelme van az értelmezési tartományon kívül az ennél – adott esetben – bővebb alaphalmazról beszélni, ha a függvény úgyis csak az értelmezési tartományban lévő elemekhez rendel képet? Hasonlóan jogos kérdés, hogy mi értelme van az értékkészleten kívül az ennél – adott esetben – bővebb képhalmazról beszélni, ha a függvény úgyis csak az értékkészletben lévő elemeket rendeli hozzá képként az alaphalmazban lévő elemekhez? Ennek pusztán praktikussági okai vannak, ugyanis sok esetben nehéz pontosan meghatározni akár az értelmezési tartományt, akár az értékkészletet. Ezért célszerűbb olyan alap- és képhalmazt választani, amelyeket könnyen meg tudunk határozni, ugyanakkor nem túl tágak a tényleges értelmezési tartományhoz és értékkészlethez képest.

Hogy ne csak a levegőbe beszéljünk, nézzük is rögtön egy egyszerű példát. Tekintsük például azt a függvényt, amely tetszőleges $n$ egész számhoz hozzárendeli mondjuk a $2$ -nek az $n$ -edik hatványát, azaz a $2^n$ egész számot. Nevezzük ezt a függvényt $f$ -nek.

Ekkor az alábbi képlettel írhatjuk le ezt a függvényt:

f(n)=2^n

Látható, hogy ennek a függvénynek a bemenetei és a kimenetei is ugyanabból a halmazból, nevezetesen az egész számok közül kerülnek ki. Az egész számok halmazát konvencionálisan $\Z$ -vel szokták jelölni, ezért a korábbi jelölésekkel ezt írhatjuk:

f:\Z \to \Z

A fenti $f$ függvény különleges abból a szempontból, hogy le lehet írni csak az $n$ változótól függő explicit képlettel: $f(n)=2^n$ . Ez sok esetben nem, vagy csak nehezen tehető meg.

Tekintsük például a híres Fibonacci-függvényt, amely a pozitív egész számokon van értelmezve. Ennek az értéke $n=1$ és $n=2$ esetén $1$ , azaz $f(1)=1$ és $f(2)=1$ , minden további $n$ -re pedig teljesíti az alábbi, úgynevezett függvényegyenletet:

f(n)=f(n-1) + f(n-2)

A Fibonacci-függvény néhány további értékét ennek alapján könnyedén kiszámíthatjuk:

\begin{aligned} f(3) &= f(2)+f(1) = 1+1 = 2 \\ f(4) &= f(3)+f(2) = 2+1 = 3 \\ f(5) &= f(4)+f(3) = 3+2 = 5 \\ \phantom{f(6)} &\phantom{=} \phantom{f(5)+f(4)} \vdots \phantom{5+3 = 8} \\ \end{aligned}

Látható, hogy ez az $f(n)$ -re adott kifejezés nem explicit, mivel a függvény két korábbi helyén felvett értékétől függ. Ha például ez alapján az $f(100)$ -at szeretnénk kiszámítani, akkor előbb ki kell számítanunk a függvény $100$ alatti számokra adott értékeit is.

Érdekességképp megjegyezzük, hogy a Fibonacci-függvény esetén létezik csak $n$ -től függő explicit képlet is:

f(n)=\frac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{\sqrt{5} \cdot 2^n}

Az Olvasó behelyettesítésekkel könnyen leellenőrizheti ennek a képletnek a helyességét. Az persze más kérdés, hogy hogyan lehet egy ilyen képletre rájönni. Ennek ismertetését a szükséges absztrakt algebrai ismeretek hiányában mellőzzük. Sok olyan fontos függvény van azonban, amelyre ilyen explicit képlet nem is létezik, ezért általánosságban az értelmezési tartomány vagy az értékkészlet meghatározása nem egyszerű feladat.

9.2Egyirányú függvények

Most térjünk vissza az $f(n)=2^n$ függvényhez, és ennek kapcsán vizsgáljuk meg, hogy mit jelent az egyirányú függvény fogalma. A pontos matematikai definíció helyett egy gyakorlati példán keresztül mutatjuk meg a fogalom lényegét. Tekintsük az $f(n)=2^n$ függvénynek azt a megszorítását, amely csak az $1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $7$ , $8$ , $9$ és $10$ számokra van értelmezve. Ezekre az értékekre algoritmikusan könnyű meghatározni a függvény értékét, hiszen csak hatványozni kell. Az értékek rendre a $2$ , $4$ , $8$ , $16$ , $32$ , $64$ , $128$ , $256$ , $512$ és $1024$ számok lesznek.

Tegyük fel, hogy ennek a függvénynek a megfordítása a feladat, azaz olyan algoritmust kell készítenünk, amely bemenetként kap egy számot ebből az értékkészletből, és azt kell kiszámítani, hogy ez melyik $n$ értéknek a képe az $f$ függvény szerint. Nézzük például az $512$ egész számot, mint bemenetet. Keressük tehát azt az $n$ kitevőt, amelyre $2$ -t emelve épp $512$ -t kapunk. A szemfülesebb olvasók egyből észreveszik, hogy itt az $512$ -nek a 2-es alapú logaritmusának a kiszámításáról van szó, de tegyük most félre ezt a fogalmat és szorítkozzunk a "józan paraszti eszünkre".

Jobban megvizsgálva észrevehetjük, hogy a függvényünk ad bizonyos támpontokat. Nevezetesen $n$ értékét növelve (illetve csökkentve) az $f(n)$ mennyiség is határozottan növekszik (illetve csökken). Ezt a tulajdonságot okosan kihasználva igen hatékonyan megtalálhatjuk az $512$ -höz tartozó $n$ értékét megfelelő szisztéma szerinti próbálgatással.

Végezzünk például egy próbát az értelmezési tartomány közepe táján lévő $n=5$ -re. Ebben az esetben $f(5) = 2^5 = 32$ . Ez ugyan $512$ -nél kisebb, viszont a függvényünk fenti tulajdonsága miatt egyből következik, hogy a keresett $n$ csak nagyobb lehet $5$ -nél. Azaz a lehetőségek felét kizárhatjuk, és a továbbiakban elegendő $n$ értékét a $6$ , $7$ , $8$ , $9$ és $10$ egész számok között keresnünk. Most végezzünk egy újabb próbát ennek a szűkített számsornak a közepén lévő $n=8$ -ra. Ebben az esetben $f(8) = 2^8 = 256$ . Ez még mindig kisebb, mint $512$ , azaz a keresett $n$ biztos, hogy csak a $9$ és $10$ számok valamelyike lehet, vagyis újra kizárhattuk a lehetőségek felét. Végül egy utolsó próbával megkapjuk, hogy $f(9) = 2^9 = 512$ , azaz a keresett $n$ értéke $9$ .

Általánosságban bináris keresésnek hívjuk az olyan módszereket, amikor egy véges halmazban kell keresnünk a megoldást, és minden lépésben ki tudjuk zárni a lehetőségek felét. Ez egy rendkívül hatékony algoritmikus módszer, mivel a szükséges lépések száma a halmaz méretének kettes alapú logaritmusával arányos. Ha például a megoldást egy ezermilliárdszor milliárdszor milliárd nagyságú halmazban kell is keresnünk, a szükséges lépések száma akkor is nagyságrendileg mindössze $100$ körül van. Többek között ezért tudunk megtalálni hamar egy keresett szót egy szótárban. Habár nem tudatosul bennünk, de ilyenkor is lényegében egy bináris keresést hajtunk végre a szavak halmazán, csak ebben az esetben a rendezést az ábécé-sorrend határozza meg.

Az olyan függvényeket, amelyek esetén az alaphalmaz elemeinek képe algoritmikusan könnyen kiszámítható, de a képhalmaz tetszőleges eleméhez algoritmikusan nehéz olyan elemet találni az alaphalmazban, amelynek épp ő a képe, egyirányú függvényeknek nevezzük. Az egyirányú függvényeket egy adott irányban nyíló csapóajtóhoz hasonlíthatjuk. Az egyik irányban (az alaphalmazból a képhalmaz irányába) könnyű áthaladni rajta, azonban ha egyszer bezárult mögöttünk az ajtó, akkor nehezen juthatunk vissza rajta a másik irányba (a képhalmazból az alaphalmazba).

A fenti példában szereplő $f$ függvény nyilván nem egyirányú függvény, hiszen a megfordítása egy algoritmikusan könnyű bináris keresési feladathoz vezet, azonban egy aprónak tűnő módosítással ezt a megfordítást reménytelenül nehézzé tehetjük egy potenciális támadó számára. Ehhez teszünk egy kis kitérőt az úgynevezett moduláris aritmetika irányába, amelyet most az egyszerűség kedvéért csak óraaritmetikának fogunk nevezni. Az elnevezés mindjárt világossá válik. A 18. fejezetben részletesen ki fogunk térni a moduláris aritmetikára, most azonban az elsődleges cél az alapgondolat megértése.

9.3Számolás az óralapon

Ezen az óralapon egy nagyon hasonló műveletet tudunk definiálni, mint amilyen a hagyományos összeadás volt. Ezt a műveletet modulo $11$ összeadásnak nevezzük, vagy általánosságban – egy $N$ darab számot tartalmazó óralap esetén – modulo $N$ összeadásról beszélünk. Adjuk össze ismét az előző példában szereplő $8$ és $4$ számokat, de ezúttal a számegyenes helyett ezen az óralapon végezzük a számolást. Induljunk el a $8$ -as számtól, és tegyünk meg $4$ lépést az óramutató járásával megegyező irányban. Az összeadás eredménye az a szám lesz, ahová megérkeztünk, ami jelen esetben az $1$ .

A modulo $11$ összeadás esetén tehát a $8$ és a $4$ összege $1$ , amit így jelölünk:

8+4\equiv1 \pmod{11}

Az összeadáshoz hasonlóan szorzást is értelmezhetünk ebben a furcsa óraaritmetikában. Legyen például a két összeszorzandó szám a $4$ és az $5$ . Ilyenkor a $0$ -ról indulunk, és annyiszor lépünk az egyik tényezőnek megfelelő lépést, mint amennyi a másik tényező. A hagyományos számegyenesen jobbra kell lépkedni, így a $20$ -as számhoz jutunk, azaz $4\cdot 5=20$ . Ezzel szemben az óraaritmetikában ismét az óramutató járásával megegyező irányban kell lépkedni, így nem egész két kör megtétele után a $9$ -es számhoz jutunk, azaz $4\cdot 5\equiv 9 \pmod{11}$ .

Most, hogy van már szorzásunk is, nem lesz nehéz értelmezni a modulo $11$ hatványozást sem. Egy $x$ szám $n$ -edik hatványát – hasonlóan a hagyományos hatványozáshoz – úgy kapjuk meg, hogy veszünk egy olyan $n$ darab tényezőből álló szorzatot, amelyben minden tényező $x$ . A különbség annyi a hagyományos hatványozáshoz képest, hogy a szorzások elvégzésekor most is az imént bevezetett modulo $11$ szorzást alkalmazzuk:

x^n = \underbrace{x \cdot x \cdot \ldots \cdot x}_{\text{n darab}}

Most vizsgáljuk meg, hogy mi történik a 9.2. szakaszban bevezetett $f(n) = 2^n$ függvénnyel, ha a hagyományos számegyenes helyett a modulo $11$ óraaritmetikában értelmezzük azt.

9.4A diszkrét logaritmus fogalma

Az alábbi táblázat első oszlopa az $n$ változó, míg a második és harmadik oszlopa az $f(n) = 2^n$ függvény értékét tartalmazza rendre a hagyományos és a modulo $11$ hatványozás esetén:

\begin{array}{c}{ \begin{array}{|c|c|c|} \hline n & 2^n & 2^n \pmod{11} \\ \hline \hline 0 & 1 & 1 \\ \hline 1 & 2 & 2\\ \hline 2 & 4 & 4\\ \hline 3 & 8 & 8\\ \hline 4 & 16 & 5 \\ \hline 5 & 32 & 10 \\ \hline 6 & 64 & 9 \\ \hline 7 & 128 & 7 \\ \hline 8 & 256 & 3 \\ \hline 9 & 512 & 6\\ \hline 10 & 1024 & 1\\ \hline 11 & 2048 & 2\\ \hline \end{array}} \\ \vdots \end{array}

Ha megvizsgáljuk a táblázat harmadik oszlopát, akkor láthatjuk, hogy ez a sorozat – a második oszloppal ellentétben – teljesen véletlenszerűen ugrál össze-vissza a függvény értékkészletét alkotó számokon. Ezúttal nem kapunk semmiféle támpontot a függvény megfordításához.

Ennek érzékeltetéséhez képzeljük most magunkat egy potenciális támadó – például Eve – helyébe. Tegyük fel, hogy a támadási kísérlet során Eve-nek ki kell számítania azt az $n$ kitevőt, amely esetén $2^n \equiv 6 \pmod{11}$ . Ezt a kitevőt a $6$ -os szám kettes alapú diszkrét logaritmusának nevezik. Mivel modulo $11$ óraaritmetikában számolunk, ezért Eve csak annyit tud, hogy a megoldás az $1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $7$ , $8$ , $9$ , $10$ számok közül kerülhet ki.

Eve azt megteheti, hogy elkezdi sorban kipróbálni ezeket a kitevőket, ez azonban reménytelenül sokáig tarthat neki, amennyiben nem egy $11$ elemű, hanem egy ennél sokkal nagyobb óralapon kell keresgélnie. Sebaj – gondolja magában Eve –, szerencsére a fentebb már ismertetett bináris keresést épp az ilyen esetekre találták ki.

Eve tehát először tesz egy próbát az értelmezési tartomány közepén lévő $n=5$ értékre. Erre azt kapja, hogy $2^5\equiv 10 \pmod{11}$ . Az így kapott eredmény nagyobb, mint $6$ , ezért Eve a bináris keresés logikáját követve azt a következtetést vonja le, hogy a keresett kitevő biztosan $5$ -nél kisebb. Ez azonban hibás feltételezés, hiszen a megoldás ebben az esetben a $9$ lenne. A modulo $11$ hatványozás tehát nem ad olyan támpontokat, mint a hagyományos, így Eve ezzel a módszerrel nem tudja kizárni minden lépésben a kitevőjelöltek felét.

Sőt, jelenleg nem is ismeretes semmilyen más módszer sem, ami a modulo hatványozás megfordítására lényegesen gyorsabb megoldást szolgáltatna, mint az összes lehetséges kitevőjelölt végigpróbálgatása. Ez viszont egy megfelelően nagy méretű óralap esetén reménytelen feladat elé állítja Eve-et. A modulo hatványozás tehát valóban egy egyirányú függvénynek tűnik, amelyet Alice és Bob kulcsmegosztásra használhatnak. A 8.8. szakaszban a prímfaktorizációról tett megjegyzéshez hasonlóan azonban itt is kénytelenek vagyunk megjegyezni, hogy a diszkrét logaritmus problémájáról sem bizonyított, hogy NP-teljes lenne.

9.5A Diffie-Hellman kulcscsere protokoll

Tegyük fel, hogy Alice és Bob szeretnének megegyezni egy közös kulcsban, amelyet aztán egy valamilyen szimmetrikus kulcsú titkosításhoz fognak használni. Az 5.6. szakaszban már láttuk, hogy az Alice és Bob közötti kommunikáció gyakorlatilag számok küldözgetéséből áll, így a rejtjelező és dekódoló komponensekre nyugodtan tekinthetünk matematikai függvényekként, amelyeket egy kulcsnak nevezett $k$ egész számmal paraméterezhetünk. Alice és Bob feladata tehát megegyezni ebben a $k$ kulcsban olymódon, hogy arról Eve nehogy tudomást szerezzen. Jelen esetben azonban nem tudnak egymással személyesen találkozni, így a kulcsban való megegyezést egy nembiztonságos csatornán keresztül kell megoldaniuk.

Alice ezért felhívja Bob-ot telefonon, és megállapodnak egy egyirányú függvényben. Legyen ez az egyirányú függvény például a 9.3. szakaszból már ismerős modulo $11$ hatványozás:

f(n) \equiv 2^n \pmod{11}

Miután ezt megbeszélték, mindketten kiválasztanak maguknak egy-egy titkos kitevőt, ezt azonban titokban tartják még egymás előtt is. Tegyük fel, hogy Alice az $a=4$ , míg Bob a $b=8$ titkos kitevőt választja magának. Most mindketten alkalmazzák ezekre a kitevőkre a megbeszélt egyirányú függvényt, és az eredményt elküldik egymásnak. Alice tehát elküldi a $5$ -ös számot Bob-nak – mivel $2^a=2^4\equiv 5 \pmod{11}$ –, Bob pedig elküldi a $3$ -as számot Alice-nak – mivel $2^b=2^8\equiv 3 \pmod{11}$ .

Végül a kapott számot mindketten a saját titkos kitevőjükre emelik szintén modulo $11$ hatványozással. Alice ugye a $3$ -as számot kapta Bob-tól, a saját titkos kitevője $a=4$ , ezért ő a $3^4 \equiv 4 \pmod{11}$ értéket fogja kapni végeredményül. Bob ehhez hasonlóan jár el: ő a $5$ -ös számot kapta Alice-tól, a saját titkos kitevője $b=8$ , így az általa kiszámított végeredmény a $5^8 \equiv 4\pmod{11}$ lesz. Láss csodát: mindketten ugyanúgy a $4$ -es számot kapták végeredményül. Ez lesz tehát a közös $k$ kulcs.

**9.8. ábra:** Diffie-Hellman kulcscsere protokoll

Mielőtt azt a kérdést megválaszolnánk, hogy hogyan kaphatta Alice és Bob is ugyanazt az eredmény, először vizsgáljuk meg, hogy mit lát ebből az egészből Eve. Róla ugye az 5.2. szakaszból már tudjuk, hogy minden olyan üzenetnek ő is a birtokába kerül, amely áthalad a kommunikációs csatornán. Az első ilyen alkalom az, amikor Alice telefonon megbeszéli Bob-bal azt az egyirányú függvényt, amely alapján a kulcscserét végre fogják hajtani. Eve tehát megtudja, hogy Alice és Bob az $f(n)=2^n \pmod{11}$ függvényt fogják használni.

Ezután Eve elfogja az Alice által Bob-nak küldött $5$ -ös és a Bob által Alice-nak küldött $3$ -as számot, és nyilván szeretné ő is kiszámítani a közös kulcsot. Eve-nek ezen a ponton két választása van: vagy Bob-hoz hasonlóan az $5^b \pmod{11}$ vagy pedig Alice-hoz hasonlóan a $3^a \pmod{11}$ értéket számítja ki. Mindegy melyiket választja, hiszen mindkettő ugyanazt az eredmény – a $k$ kulcsot – adja. A probléma csak annyi, hogy Eve nem ismeri sem az $a$ , sem pedig a $b$ kitevőt, hiszen ezeket Alice és Bob nem közölte egymással.

Eve mindössze két dolgot tud az $a$ és $b$ kitevőkről. Egyrészt az Alice által Bob-nak küldött $5$ -ös számból tudja, hogy $2^a\equiv 5 \pmod{11}$ . Másrészt pedig a Bob által Alice-nak küldött $3$ -as számból tudja, hogy $2^b\equiv 3 \pmod{11}$ . Bármelyik kitevőt is szeretné kiszámítani, kénytelen megoldani a 9.4. szakaszban ismertetett diszkrét logaritmus problémáját. Ez azonban jóval nagyobb számok esetén – mint tudjuk – gyakorlatilag lehetetlen feladat a számára még a világ összes számítógépével is. Ezzel szemben Alice-nak és Bob-nak mindössze két modulo $11$ hatványozást kell csak elvégeznie, amely – ahogy azt majd a 21.4. szakaszban látni fogjuk – egy algoritmikusan könnyű feladat számukra.

Most vizsgáljuk meg, hogy miből adódik a Diffie-Hellman kulcscsere protokoll helyessége. Bob ugye megkapja Alice-tól a $2^a \pmod{11}$ számot, és ezt hatványozza a saját titkos kitevőjével. Azaz végeredményként a $(2^a)^b \pmod{11}$ kulcsot fogja kapni. Ehhez hasonlóan Alice megkapja Bob-tól a $2^b \pmod{11}$ számot, és ezt hatványozza a saját titkos kitevőjével. Azaz végeredményként a $(2^b)^a \pmod{11}$ kulcsot fogja kapni.

A Diffie-Hellman kulcscsere protokoll ezek után nyilván akkor helyes, ha ez a két szám ugyanaz, vagyis:

(2^a)^b \equiv (2^b)^a \pmod{11}

Erre a figyelmetlen Olvasó – aki jól megtanulta általános iskolában a hatványozás azonosságait – rögtön rávágná, hogy nyilvánvalóan teljesül. Vigyázzunk azonban, itt ugyanis nem a hagyományos, hanem modulo $11$ hatványozás történik. Szerencsére ezek az összefüggések a moduláris aritmetikában is érvényesek, ez azonban korántsem magától értetődő. Ezt majd a 18.4. szakaszban fogjuk igazolni.

9.6A Diffie-Hellman kulcscsere protokoll festékekkel

A fentiek megértéséhez most egy egyszerű analógiát ismertetünk. Ennek ugyan semmi köze nem lesz a kriptográfiához, ám jól szemlélteti az egyirányú függvények működését. Képzeljük el, hogy Alice és Bob most nem számokkal, hanem festékekkel dolgozik. A közös titok, amelyben meg szeretnének egyezni, egy adott színű festékkeverék. Ennek érdekében először megegyeznek egy közös kiinduló színben. Ebben a példában ez legyen mondjuk egy-egy liter fehér festék.

**9.9. ábra:** Diffie-Hellman kucscsere protokoll – festék analógia

Vegyük észre, hogy Eve megint hasonló szituációban van, mint a modulo $11$ hatványozásra épülő példában. Nevezetesen: hiába ismeri a kiinduló fehér színt, és hiába kukkant bele az egymásnak küldött köztes keverékekbe, ezekkel az információkkal nem tud mihez kezdeni, mivel nem ezek alkotják a kulcsot. Ahhoz, hogy Eve is elő tudja állítani a végső színkeveréket, ismernie kéne Alice és Bob titkos színei közül legalább az egyiket. Ehhez azonban külön kéne választania ezeket a kiinduló fehér színtől, amikor a köztes keverékeket elfogja a kommunikációs csatornán. Ez Eve számára gyakorlatilag lehetetlen feladat, tekintve, hogy a festékkeverés egy egyirányú művelet.

9.7A Diffie-Hellman kulcscsere protokoll támadása

Jelenleg ugyan – mint azt a 9.4. szakaszban már említettük – még nincs bizonyítva a diszkrét logaritmus problémájának NP-teljessége, de tegyük fel, hogy ez valóban egy reménytelen feladat. Ezután jogosan merül fel a kérdés, hogy vajon milyen módszerek állnak egy passzív támadó – például Eve – rendelkezésére ahhoz, hogy sikeres támadást hajtson végre a protokoll ellen, és megszerezze Alice és Bob kulcsát.

A protokoll egy gyenge pontja lehet az, amikor Alice és Bob megállapodnak a használt egyirányú függvény paramétereiben. Egy Diffie-Hellman kulcscsere során használt függvény általános alakja így néz ki:

f(n)=g^n \pmod{N}

Itt a $g$ paramétert generátorelemnek, az $N$ paramétert pedig modulusnak nevezzük. A 9.5. szakaszban ismertetett egyszerű példában Alice és Bob a $g=2$ generátorelemben és az $N=11$ modulusban egyeztek meg. Ám egy valódi kulcscsere esetén ennél jóval nagyobb számokat használunk. Egy tipikus $N$ modulus például nagyságrendileg kétszáz számjegyből áll.

Előfordulhat, hogy bizonyos szerencsétlenül megválasztott $g$ generátorelem és $N$ modulus esetén Eve-nek lényegesen könnyebb dolga van egy ilyen függvény megfordításával még akkor is, ha nagy számokat használnak. Azonban eléggé jól ismerjük azokat a számelméleti kritériumokat, amelyeket e paramétereknek teljesíteniük kell a megfelelő biztonság érdekében. Ezekről a 26.6. szakaszban lesz szó, most azonban nyugodtan feltételezhetjük, hogy Alice és Bob ilyen értelemben megfelelő körültekintéssel választja meg a használt paramétereket.

Ilyen feltételezések mellett kimondhatjuk, hogy a Diffie-Hellman protokoll egy passzív támadó – például Eve – számára gyakorlatilag feltörhetetlen. Sajnos azonban egy aktív támadó – például a csaló Mallory – könnyedén ki tud csalni titkos információkat Alice-tól és Bob-tól egy úgynevezett közbeékelődéses támadás (man-in-the-middle attack) segítségével.

Mallory ezt úgy tudja elérni, hogy Alice és Bob közé ékelődik a kommunikációs folyamat során, és elhiteti velük, hogy egymással folytatják le a kulcscsere folyamatot. Valójában azonban Alice és Bob is Mallory-vel kommunikál közvetlenül, nem pedig egymással.

**9.10. ábra:** A Diffie-Hellmann kulcscsere protokoll támadása

Itt Alice kulcscserét kezdeményez Bob-bal, ez a kezdeményezés azonban nem jut el Bob-hoz, mivel Mallory eltéríti az üzenetet. Bob helyett tehát Mallory folytatja le a kulcscserét Alice-szal, méghozzá Bob-nak kiadva magát. Így Alice azt hiszi, hogy Bob-bal állapodott meg a $k_1 = 9$ közös kulcsban. Mallory ezzel párhuzamosan Bob-bal is kezdeményez egy kulcscserét, amikoris Alice-nak adja ki magát. Így Bob azt hiszi, hogy Alice-szal állapodott meg a $k_2 = 5$ közös kulcsban.

A kulcscserét követően tehát Alice és Bob valójában Mallory-n keresztül kommunikál egymással, aki gond nélkül dekódolni tudja Alice üzeneteit a $k_1$ kulccsal, ezáltal birtokába jut a bizalmas információknak, majd a $k_2$ kulccsal titkosítva továbbítja azokat Bob-nak. Visszafele: a Bob-tól érkező üzeneteket dekódolja a $k_2$ kulccsal, majd a $k_1$ kulccsal titkosítva továbbítja Alice-nak. Ráadásul mindez teljesen rejtve marad Alice és Bob számára, akik azt hiszik, hogy közvetlenül egymással kommunikálnak.

Ez igen pofátlan dolog, nemde? A kérdés tehát az, hogy Alice hogyan tudja igazolni Bob-nak, hogy ő valóban Alice, és viszont? Erre a következő fejezetben fogjuk megadni a választ, amelyhez most felvázoljuk egy olyan rejtjelező rendszer alapjait, amely ezt lehetővé teszi.

9.8Aszimmetrikus kulcsú rejtjelezés

Ennek a fejezetnek az elején felvázoltuk az eddig ismertetett rejtjelezők közös működési modelljét, amelyet szimmetrikus kulcsú rejtjelezésnek neveztünk. Ebben az esetben Bob ugyanazt a kulcsot használja a dekódoláshoz, mint amit Alice használ a rejtjelezéshez. Diffie és Hellman fentebb már említett forradalmi írásában azonban az úgynevezett aszimmetrikus kulcsú rejtjelezés merőben új alapgondolata körvonalazódott.

Az 5.7. szakaszban a háromutas kulcsforgalom kapcsán már éltünk egy olyan analógiával, amely ládákat, lakatokat és kulcsokat használt a rejtjelezés szemléltetésére. Ezzel az analógiával élve a szimmetrikus kulcsú rejtjelezés úgy fogható fel, hogy Alice a Bob-nak szánt üzenetet beteszi egy ládába, amelyet lezár egy lakattal. Bob csak akkor tudja kinyitni a ládát, ha neki is van egy másolata a lakatot nyitó kulcsról. A problémát itt az okozza, hogy hogyan tudjuk eljuttatni a kulcsmásolatokat a kommunikáló felekhez biztonságosan.

Az aszimmetrikus kulcsú rejtjelezés egy egészen más gondolatra épül. A kulcsos, lakatos analógiával élve ez kicsit olyan, mintha nem a kulcsról, hanem a lakatról készítenénk másolatokat. Képzeljük el, hogy Bob szeretné, ha bárki tudna neki titkos üzenetet küldeni. Ennek érdekében Bob a saját lakatját minél több példányban publikusan elérhetővé teszi bárki számára. A trükk abban van, hogy a Bob-féle lakatokat mindössze egyetlen kulcs nyitja, amely végig ott lapul Bob zsebében.

Tegyük fel, hogy Alice szeretne Bob-nak egy titkos üzenetet küldeni. Elmegy hát a postára, kér egy Bob-féle lakatot, az üzenetet beleteszi egy ládába, amelyet lezár ezzel a lakattal. Ezt könnyedén megteheti, hiszen a lakatot csak rá kell pattintani a ládára. Innentől kezdve azonban kizárólag Bob fogja tudni kinyitni ezt a lakatot, hiszen csak ő rendelkezik az ehhez szükséges egyetlen kulccsal. Olyannyira, hogy a láda lezárása után még maga Alice sem tudja többé kinyitni azt.

A lakatokat félretéve itt tehát arról van szó, hogy egy üzenet dekódolásához szükség van egy plusz információra ahhoz képest, mint ami a rejtjelezéséhez kell. A dekódoláshoz szükséges plusz információt titkos (privát) kulcsnak, míg a rejtjelezéshez szükséges információt publikus (nyilvános) kulcsnak nevezzük. A rendszerben lévő valamennyi résztvevőhöz tehát nem egy kulcs, hanem egy kulcspár tartozik. E kulcspár titkos részét csak az adott résztvevő ismeri, és azt soha nem adja ki a kezéből. Ezzel szemben a kulcspár publikus része bárki számára elérhető egy nyilvános kulcstárban egy telefonkönyvhöz hasonlóan.

Tegyük fel, hogy Alice szeretne Bob-nak elküldeni egy $x$ üzenetet. Ehhez előkeresi a nyilvános kulcstárból Bob $K_b$ publikus kulcsát, és ezzel paraméterezi az $E$ rejtjelező függvényt. Ily módon előáll az $y$ kódszöveg, amelyet elküld Bob-nak. Ezt az üzenetet kizárólag Bob tudja visszafejteni, mivel a $K_b$ publikus kulcshoz tartozó $k_b$ titkos kulcsot csak ő ismeri. Bob tehát a $k_b$ titkos kulccsal paraméterezve a $D$ dekódoló függvényt könnyedén vissza tudja állítani az eredeti $x$ üzenetet. A támadó azonban csak a $K_b$ publikus kulcsot ismeri, ez azonban nem elegendő információ a dekódoláshoz.

**9.11. ábra:** Aszimmetrikus kulcsú rejtjelező modell

Ez az alapgondolat forradalmat indított el a kriptográfiában, megindult ugyanis a versenyfutás a dicsőségért, amely a fentieknek megfelelő $E$ és $D$ függvények elsőként való megtalálásáért járt. A dicsőség Ron Rivestnek, Adi Shamirnak, és Len Adlemannak jutott, akik 1977-ben publikálták az úgynevezett RSA algoritmust, amely alapjaiban változtatta meg világunkat.

Ebben a fejezetben tehát megismerkedtünk a modern kriptográfia két alapvető felfedezésével. Az első a Diffie-Hellman kulcscsere protokoll volt, amely lehetővé teszi, hogy Alice és Bob a pofátlan Eve szeme láttára állapodjanak meg egy közös titkos kulcsban, teljes biztonságban. Láttuk azonban, hogy egy aktív támadó könnyedén kijátszhatja ezt a rendszert, hacsak nem tudjuk kibővíteni a protokollt valamilyen partnerhitelesítéssel. Ezért megismerkedtünk az úgynevezett aszimmetrikus kulcsú rejtjelezés alapgondolatával. A következő fejezetben erre építkezve bemutatjuk a digitális aláírás és partnerhitelesítés működésének alapjait, majd a 11. fejezettől kezdve elkezdünk megismerkedni az RSA algoritmus számelméleti hátterével.