Alice és Bob titkosít

21.1A kibővített euklidészi algoritmus

A 20.13. Tételben igazoltuk, hogy az ax+my=b lineáris diofantoszi egyenlet megolhatóságának szükséges és elégséges feltétele, hogy az egyenlet jobboldala – azaz b – osztható legyen az (a,m) kitüntetett közös osztóval. Az elégségesség bizonyításához a 20.5. szakaszban bemutatott Bézout-lemma volt a kulcs, amely kimondja, hogy ez a kitüntetett közös osztó minden főideálgyűrűben kifejezhető (a,m)=au+mv alakban alkalmasan választott u és v elemek segítségével.

Először tehát meg kell határoznunk az u és v együtthatókat. A Bézout-lemma főideálgyűrűk esetén ugyan garantálja ezek létezését, azonban a korábban ismertetett bizonyítás nem konstruktív abban az értelemben, hogy nem ad eljárást ezek kiszámítására. Szerencsére euklidészi gyűrűk esetén – amelyek ugye a 19.15. Tétel értelmében mindannyian főideálgyűrűk – egy ilyen eljárást is kapunk a kezünkbe, amennyiben a 17.4. szakaszban ismertetett euklidészi algoritmust egy kicsit kibővítjük.

Ezért most egy konstruktív bizonyítást mutatunk a Bézout-lemma euklidészi gyűrűkre vonatkoztatott változatára. Az eredeti bizonyítás nyilván automatikusan érvényes lenne ebben az esetben is, hiszen a 19.15. Tétel alapján minden euklidészi gyűrű főideálgyűrű. Ez azonban csak a keresett u és v együtthatók létezését garantálja, de nem ad eljárást a kiszámításukra. Ezzel szemben az alábbiakban bemutatott bizonyítás konstruktív, mivel ismerteti a kibővített euklidészi algoritmust, amelynek segítségével ezeket az együtthatókat meg is határozhatjuk. Cserébe viszont nem minden főideálgyűrűn, hanem speciálisan csak euklidészi gyűrűkön működik.

Az iménti bizonyításban látott kibővitett euklidészi algoritmus tehát abban különbözik a 17.4. szakaszban ismertetett eredeti algoritmustól, hogy itt nem csak a futás során kapott r_1, r_2, ..., r_n maradékokat számítjuk ki, hanem a k_1, k_2, ..., k_n hányadosokat is felhasználjuk e maradékok lineáris kombinációs előállításához.

21.2Lineáris diofantoszi egyenlet megoldásai

Most vizsgáljuk meg, hogy a kibővített euklidészi algoritmus segítségével hogyan kapható meg egy lineáris diofantoszi egyenlet összes megoldása. Az alábbi tételben ezt a kérdést válaszoljuk meg.

Azt már az euklidészi algoritmus segítségével kiszámítottuk, hogy a (79,47) kitüntetett közös osztó 1, aminek nyilván többszöröse az egyenlet jobboldalán szereplő 10000. Így tehát ennek az egyenletnek létezik egész megoldása. Kérdés, hogy vajon nemnegatív egész megoldás is létezik-e, és ha igen, akkor mennyi? Ehhez először meg kell határoznunk az összes megoldást.

Az imént bizonyított a 21.2. Tétel 1. pontja alapján az egyik megoldást a kibővített euklidészi algoritmus segítségével határozhatjuk meg, amelyből aztán a 2. és 3. állítás értelmében könnyedén előállíthatjuk az összes megoldást. Ezekből már látni fogjuk, hogy van-e közöttük olyan, amely esetén x is és y is nemnegatív.

Mi alapvetően lusták vagyunk, így nem szeretnénk a k paraméter végtelen sok lehetséges értékét végigvizsgálni azért, hogy megtudjuk, mikor kapunk nemnegatív számot x-re és y-ra egyaránt.

Félretéve a szöveges feladatot, most próbáljuk meg a 79x+47y=10000 lineáris diofantoszi egyenlet összes megoldását – amelyekbe tehát mostmár a negatívakat is beleértjük – egy kétdimenziós koordináta-rendszerben ábrázolni, ahol a két tengely a megoldásokhoz tartozó x és y értékeket jelenti.

A megoldásokat szolgáltató képletből látható, hogy ha egy adott megoldásból kiindulva a k értékét 1-gyel megnöveljük, akkor az így kapott új megoldáshoz tartozó x értéke 47-tel nő, míg az y értéke 79-cel csökken. Így tehát a megoldások mindannyian egy ferdén lefelé tartó egyenes mentén fognak elhelyezkedni – innen ered a "lineáris" elnevezés. A 21.1. ábrán a k paraméternek az adott megoldásokhoz tartozó értékeit is feltüntettük.

Ebből szépen látható, hogy valóban csak a k=4681, k=4682 és a k=4683 értékekhez tartozó megoldások esnek a jobb-felső síknegyedbe – amikoris mindkét koordináta pozitív.

Az ebben a szakaszban ismertetett módszerrel tehát bármilyen lineáris diofantoszi egyenletet, és így a 20.13. Tétel alapján bármilyen lineáris kongruenciát meg tudunk oldani. Ezzel az RSA rejtjelező eljárás egyik fontos összetevője már a kezünkben van. Most ismerkedjünk meg egy másik fontos összetevővel.

21.3Az Euler-féle \varphi-függvény kiszámítása

Ebben a szakaszban megtanuljuk, hogy hogyan lehet kiszámítani a 20.7. Definícióban ismertetett Euler-féle \varphi-függvény értékét bármilyen tetszőleges pozitív egész számra. A definíció szerint egy m pozitív egész szám esetén ez a függvény a modulo m redukált maradékosztályok számát adja meg. A 20.6. Definíció alapján ezek épp a 20.5. Tételben definiált \Z/m\Z maradékosztálygyűrű azon elemei, amelyek invertálhatók a maradékosztályok közötti szorzásra nézve.

Ezek száma 6, így tehát \varphi(18)=6. Az alábbi tételben a \varphi-függvény egy fontos tulajdonságát igazoljuk.

Ha feltételezzük, hogy a \varphi(7)=6 és a \varphi(11)=10 értékeket valahogyan kiszámítottuk, akkor a \varphi(77)=60 végeredmény már könnyen adódik. Az alábbiakban ezt a "valahogyant" vizsgáljuk meg. Ehhez azonban szükségünk lesz az alábbi segédtételre.

Ennek segítségével mostmár tetszőleges prímszámra – vagy még általánosabban tetszőleges prímhatványra – könnyedén ki tudjuk számítani az Euler-féle \varphi-függvény értékét.

Ennek és a 21.3. Tételnek a segítségével mostmár bármilyen m\gt 0 pozitív egész szám esetén könnyedén ki tudjuk számítani a \varphi(m) értéket. Ehhez "mindössze" az m egész szám prímtényezős felbontására van szükségünk.

Ha tehát ismerjük a bemeneti m egész szám prímtényezős felbontását, akkor könnyedén ki tudjuk számítani a \varphi(m) értéket. Ami viszont kriptográfiai szempontból hasonlóan fontos: Ha nem ismerjük m prímtényezős felbontását, akkor nem ismeretes hatékony algoritmus \varphi(m) kiszámításához. Ez lényeges szerepet játszik az RSA rejtjelező eljárás esetén. Mielőtt azonban ezt ismertetnénk, szükségünk van egy harmadik összetevőre is.

21.4Az ismételt négyzetreemelések módszere

A 18. fejezetben többek között a Diffie-Hellman kulcscsere protokoll kapcsán merült fel – ebben a fejezetben pedig az RSA eljárás kapcsán fog felmerülni – az igény arra, hogy hatékonyan tudjunk hatványozni az úgynevezett "óraaritmetikában". Egy ott szereplő példában annak meghatározása volt a feladat, hogy a 2^{328} hatvány mennyi maradékot ad 11-gyel osztva. Megmutattuk, hogy ez tulajdonképpen a 18.3. Definíció szerinti Z_{11} gyűrűben elvégzett hatványozásnak felel meg, méghozzá a \bmod_{11} maradékképző függvény művelettartó tulajdonságai miatt.

Ez azért szerencsés, mert így számolgatás közben nem fogunk olyan óriási részeredményeket kapni, amelyek túllépik a számítógép számábrázolási határait. A gyakorlatban azonban a kitevő nagyságrendje a többszázjegyű számok körében mozog, így ez a módszer beláthatatlanul sok moduláris szorzást igényel. Most egy olyan módszert fogunk mutatni, amelynek a segítségével még ezek az óriási kitevős moduláris hatványok is pillanatok alatt kiszámíthatók. Ez az ismételt négyzetre emelések módszere néven ismeretes, és a moduláris hatványozás 18.8. Tétel szerinti azonosságait használja ki igen trükkös módon.

Azaz egy olyan műveletsorozatot kell elvégeznünk, amelynek minden lépésében az előző lépésben kapott részeredményt vagy négyzetre emeljük, vagy pedig megszorozzuk a 2 alappal. Ebben a konkrét példában egy dupla négyzetreemelés után először szorozni kell, ezután következik egy tripla négyzetreemelés, aztán ismét egy szorzás, végül megint egy tripla négyzetreemelés.

Azaz a \bmod_{11}(2^{328})=3 végeredményt 327 helyett megkaptuk mindössze 10 darab moduláris szorzásból.

Azaz mind az n-2 darab zárójel esetén az addigi részeredményhez hozzá kell adni 1-et, majd az egészet megszorozni 2-vel. Végül az utolsó lépésben mégegyszer hozzá kell adni az egészhez 1-et. Mivel ez a kifejezés a \bmod_m(a^x) moduláris hatvány kitevőjében szerepel, ezért a 18.8. Tétel 2. és 3. pontjai alapján ennek a hatványnak a kiszámítása összesen 2n-1 darab moduláris szorzásból megúszható. Ráadásul ez a lehető legrosszabb eset, amikor a kitevő bináris számábrázolásában minden bit értéke 1.

Ez tehát azt jelenti, hogy mind a Diffie-Hellman kulcscsere protokoll, mind pedig a fejezet hátralévő szakaszaiban bemutatott RSA eljárás során előforduló moduláris hatványokat rendkívül gyorsan ki tudjuk számítani még abban az esetben is, ha több ezer bites számokról van szó. Ugyanis legrosszabb esetben is a kitevő bináris számjegyei számának duplája lesz az elvégzendő moduláris szorzások száma.

Ezek után minden készen áll arra, hogy megismerkedjünk az emberiség egyik legfontosabb találmányával.

21.5A Rivest-Shamir-Adleman (RSA) aszimmetrikus kulcsú rejtjelező eljárás

A 9.8. szakaszban mutattuk be az aszimmetrikus kulcsú rejtjelezés forradalmian új gondolatát. Ezt most pár mondatban átismételjük, ám javasoljuk az Olvasónak a hivatkozott szakasz átolvasását. A nagy ötlet ugye az volt, hogy a fogadó oldalon az üzenet visszafejtéséhez más kulcsot kelljen használni, mint amivel a küldő oldal titkosította azt. Ekkor ugyanis nincs szükség arra, hogy a fogadó és a küldő oldal előzetesen megállapodjon egy közös kulcsban.

Ezt sok esetben egyébként nem is tudnák megtenni. Gondoljunk csak például arra, amikor valamilyen külföldi webáruházban vásárolunk. Ez a vásárlás végén átirányít minket egy olyan bank fizetőoldalára, amelynek nem is vagyunk az ügyfelei. Ilyenkor a böngészőnknek a begépelt bankkártyaadatokat titkosítva kell elküldenie a bank szerverére, hiszen rendkívül érzékeny adatokról van szó. Amennyiben nem létezne aszimmetrikus kulcsú titkosítás, akkor a folyamat itt meg is akadna. Szükség lenne ugyanis egy közös kulcsra a vásárló és a bank közötti kommunikáció titkosításához.

Az RSA eljárásnak köszönhetően azonban ilyenre nincs szükség, mivel a böngésző a bank publikus kulcsával – amely tehát bárki számára elérhető – titkosíthatja az elküldendő bankkártyaadatokat, amelyet azután csak a bank fog tudni visszafejteni a saját titkos kulcsával. Megjegyezzük, hogy valójában nem pontosan ez történik a háttérben, ám ez az alapelv megértése szempontjából lényegtelen.

Most térjünk vissza főszereplőinkhez, és 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, míg a titkos kulcsot nem ismerő támadó számára ez gyakorlatilag lehetetlen. Ez a folyamat látható a 21.2. ábrán.

Az 1970-es évek nagy kérdése volt, hogy vajon mik lehetnek az ábrán szereplő E és D függvények – ha egyáltalán léteznek ilyenek. Az úttörő eredmény a 21.3. képen látható Ronald Linn Rivest, Adi Shamir és Leonard Max Adleman érdeme, akik 1977-ben publikálták az úgynevezett Rivest-Shamir-Adleman (RSA) algoritmust, amely talán az emberiség egyik legnagyobb horderejű felfedezése volt – legalábbis a társadalmunkra gyakorolt hatását tekintve mindenképpen.

Az alábbiakban – mostmár a szükséges számelméleti ismeretekkel felvértezve – ismertetjük ennek az eljárásnak a részleteit, majd az egészet egy egyszerű példán szemléltetjük.

21.6RSA kulcspár generálása

Előszöris Bobnak szüksége lesz egy publikus és egy titkos részből álló kulcspárra. Ezek előállítását kulcsgenerálásnak nevezzük. Ehhez Bob keres magának két különböző, elegendően nagy prímszámot. Az "elegendően nagy" manapság tipikusan 2048 vagy 4096 bináris számjeggyel ábrázolható prímeket jelent. Ez tízes számrendszerben körülbelül a 600 vagy 1200 számjegyű számok nagyságrendje. Arról a 23. fejezetben lesz szó, hogy Bob hogyan képes ilyen nagyságrendű prímeket találni viszonylag hamar, ezért ezt a problémát egyelőre tegyük félre.

Jelöljük a Bob által talált, és persze a lehető legnagyobb titokban tartott két prímet p-vel és q-val. Bob ezután összeszorozza ezt a két prímszámot. Az így kapott m=p\cdot q egész számot modulusnak fogjuk nevezni a továbbiakban. Ezt az m számot nem szükséges titokban tartani, az ugyanis a publikus kulcs része lesz.

Harmadik lépésként Bob választ egy tetszőleges 0 és \varphi(m) közötti e egész számot, amely relatív prím \varphi(m)-hez. A 20.15. Tétel alapján ezt úgy is megfogalmazhatjuk, hogy Bob választ egy modulo \varphi(m) redukált maradékosztályt, az e egész szám pedig ennek a legkisebb pozitív reprezentánseleme lesz. Megint más megfogalmazásban a gyűrűk homomorfizmustétele miatt e tulajdonképpen a 18.3. Definíció szerinti Z_{\varphi(m)} gyűrű valamelyik invertálható eleme lesz.

Ezt Bob szintén hatékonyan ki tudja választani, mivel szerencsére – itt nem részletezett analitikus számelméleti okok miatt – viszonylag gyakori, hogy két tetszőlegesen kiválasztott egész szám egymáshoz relatív prím. Így Bob megteheti, hogy véletlenszerűen választ a 0 és \varphi(m) közötti számok közül, majd a 17.4. szakaszban ismertetett euklidészi algoritmus segítségével kiszámítja a kiválasztott szám és \varphi(m) kitüntetett közös osztóját.

Ha ez egy egység, akkor a 17.10. Definíció utáni megjegyzés alapján a választott szám relatív prím \varphi(m)-hez, azaz megvan a keresett e. Ha pedig nem ez a helyzet, akkor Bob megismétli az eljárást egy másik véletlenszerűen választott számmal mindaddig, amíg nem talál egy \varphi(m)-hez relatív prím számot. Az említett analitikus számelméleti összefüggések miatt ez majdnem biztosan már az első próbálkozáskor megtörténik. Az így kapott e számot nem szükséges titokban tartani, az ugyanis a publikus kulcs része lesz.

A 20.8. Definíció alapján a megoldás a 20.14. Tétel 1. pontja miatt egyetlen darab modulo \varphi(m) maradékosztály lesz – mivel e relatív prím \varphi(m)-hez, és emiatt (e,\varphi(m))\sim 1. Az e szám Z_{\varphi(m)}-beli multiplikatív inverze ennek az eredményül kapott maradékosztálynak a legkisebb pozitív eleme lesz, amelyet a továbbiakban d-vel fogunk jelölni.

Bob ezek után akár meg is semmisítheti az eredetileg választott p és q prímszámokat, valamint a belőlük kiszámított \varphi(m) értéket, azokra ugyanis a továbbiakban nem feltétlenül van szüksége. A 22.7. szakaszban azonban látni fogjuk, hogy a p és q prímszámok segítségével Bob hogyan tudja jelentősen felgyorsítani a dekódolás folyamatát. Mindenesetre biztonságos helyen kell ezeket tárolnia, ugyanis a segítségükkel a publikus kulcsból a fentiek alapján hatékonyan kiszámítható a titkos kulcs, így nem lenne jó, ha illetéktelen kezekbe kerülnének. Nélkülük azonban jelenlegi számelméleti ismereteink alapján ez egy belátható időn belül nem kivitelezhető algoritmikus feladat még a világ összes számítási kapacitásával sem. Ehhez ugyanis prímtényezőire kéne bontani a publikus kulcsban szereplő m modulust, vagy valamilyen más – mindezidáig nem ismert – módon kiszámítani a \varphi(m) értéket, ami ugye a d dekódoló kulcs meghatározásához kell.

Bob a kulcspárjának publikus részét – azaz az (m;e) számpárt – nyilvánosságra hozhatja, ugyanis ennek segítségével lehet majd a neki szánt bizalmas üzeneteket titkosítani. Ezzel szemben a kulcspár titkos részét – azaz az (m;d) számpárt – a lehető legnagyobb titokban kell tartania, ugyanis a titkosított üzeneteket kizárólag ezzel lehet majd visszafejteni.

21.7RSA kódolás és dekódolás

Az RSA esetén mind a rejtjelezés, mind pedig a dekódolás során tulajdonképpen egy-egy moduláris hatványozást kell elvégezni. Ennek módjáról az ismételt négyzetreemelések módszerének kapcsán a 21.4. szakaszban volt szó bővebben. Ha Alice valamilyen üzenetet vagy adathalmazt szeretne küldeni Bob-nak, akkor előszöris kikeresi a nyilvános kulcstárból Bob publikus kulcsát. Az ebben szereplő m modulus fogja kijelölni azt a 18.3. Definíció szerinti Z_m gyűrűt, amiben majd moduláris hatványozást el kell végezni, az e szám pedig a kódoláshoz használandó kitevő lesz.

A rejtjelezni kívánt üzenetet Alice valamilyen egyezményes vagy szabványos módon egy, a Z_m gyűrű elemeiből álló számsorozattá alakítja át, amelyet előkódolásnak nevezünk. Ez sokféleképpen történhet, erről egy kicsit bővebben a blokkrejtjelezőkről szóló 5.6. szakaszban volt szó. A technikai részletekre itt nem térünk ki, ám a következő szakaszban fogunk mutatni erre egy egyszerű példát.

A lényeg, hogy Bob ebből a számsorozatból egyértelműen tudja majd rekonstruálni az eredeti üzenetet. Az RSA szempontjából tehát a nyílt szöveg tulajdonképpen egy x_1, x_2, x_3, \ldots számsorozat, amelynek tagjai a Z_m gyűrű elemei, azaz m-nél kisebb nemnegatív egész számok.

A visszakapott számsorozatból végül Bob az egyezmény vagy szabvány szerinti előkódolás megfordításával megkapja az eredeti üzenetet vagy adathalmazt. A 22. fejezetben fogjuk igazolni, hogy az imént említett "varázslat" valójában nem a véletlen műve, hanem az eddig megismert számelméleti összefüggések következménye. Most azonban nézzünk egy egyszerű példát az RSA rejtjelező használatára.

21.8Példa RSA rejtjelezésre

sziabobmiahelyzet#

Mivel a kommunikációs csatornát a szemtelen Eve lehallgatja, ezért Alice kénytelen titkosítani ezt a jelsorozatot. Sajnos azonban ezúttal Alice-nak és Bob-nak nincs módja személyes találkozót megbeszélni annak érdekében, hogy valamilyen közös szimmetrikus kulcsban meg tudjanak állapodni, ahogy tették azt például az 1. fejezetben. De ez nem is jelent problémát, hiszen ismerik az előző szakaszokban ismertetett aszimmetrikus kulcsú RSA rejtjelező eljárást. Alice ezért megkéri Bob-ot, hogy generáljon magának egy RSA kulcspárt, és annak publikus részét küldje el neki a kommunikációs csatornán keresztül, hogy azzal titkosítani tudja számára a fenti bizalmas üzenetet.

Ezek után Bob elküldi Alice-nak a kulcspár publikus részét – vagy akár elérhetővé teszi azt bárki számára egy nyilvános kulcstárban –, a titkos részét azonban szigorúan titokban tartja.

Alice-nak tehát az elküldendő bináris jelsorozatot a Z_m=Z_{29329} gyűrű elemeinek sorozatává kell alakítania. Ez egy olyan számsorozatot jelent, amelynek minden tagja nemnegatív és kisebb az m=29329 modulusnál. Egy rövid számolgatás után azt kapja, hogy a 14 bites számok biztosan megfelelnek ennek a kritériumnak, hiszen 2^{14}=16384. Ezzel szemben a 15 bites számok között már előfordulhatnának a modulusnál esetleg nagyobb számok is, mivel 2^{15}=32768. Így tehát Alice az üzenetet 14 bit hosszú részekre darabolja.

Ezeket a 15 bites darabokat Alice szépen egymás után fűzi, és az így kapott 105 bites titkosított bitsorozatot elküldi Bob-nak a kommunikációs csatornán keresztül. Ne feledjük, hogy az Alice által használt, Bob-hoz tartozó publikus kulcs csak a titkosításhoz elegendő. A kulcs Bob-nál lévő titkos része nélkül maga Alice sem tudja visszafejteni ezt az üzenetet, így az teljes biztonságban utazik a csatornán a pofátlan Eve orra előtt.

21.9Példa RSA dekódolásra

Most nézzük meg, hogy mit tud kezdeni ezzel a titkosított bitsorozattal a vételi oldalon lévő Bob, illetve a kommunikációs csatornát lehallgató Eve. Bob publikus kulcsát mindketten ismerik. Bob nyilván, hiszen ő maga generálta azt az előző szakaszban. Eve pedig legkésőbb akkor értesül róla, amikor Bob közli azt Alice-szal a kommunikációs csatornán keresztül, de akár közvetlenül le is töltheti a nyilvános kulcstárból.

Bob tehát valóban visszakapta az Alice által küldött eredeti számsorozatot. Eve azonban ezen a ponton bajba kerül, mivel nem ismeri a d=11623 dekódoló kulcsot, hiszen azt Bob mindvégig titokban tartotta. Sebaj, gondolja Eve, és megkísérli kiszámítani a publikus kulcsból a titkos kulcsot, pontosan úgy, ahogyan Bob tette a kulcsgenerálás során. Ehhez Eve-nek meg kéne tudnia határozni az e=187 egész szám multiplikatív inverzét a 18.3. Definíció szerinti Z_{\varphi(m)} gyűrűben, hiszen ez épp a keresett d dekódoló kulcs lesz.

Igenám, csakhogy Eve számára még \varphi(m) értéke sem ismert, és ennek kiszámításához a 21.3. és a 21.5. Tétel alapján szüksége volna az m=29329 modulus prímtényezős felbontására. Nem ismeretes ugyanis olyan algoritmikus módszer, amellyel a \varphi(m) értéke hatékonyan kiszámítható m prímtényezőinek ismerete nélkül. Ezért Eve sajnos – szerencsére – kénytelen megkeresni m prímtényezőit, amelyre szintén nem ismert hatékony algoritmus. Így ez a feladat az idők végezetéig is eltarthat neki a világ összes számítógépével, amennyiben a Bob által választott prímszámok megfelelően nagyok.

Ezzel szemben Bob azért volt képes olyan gyorsan meghatározni \varphi(m)-et, és így a d titkos dekódoló kulcsot, mivel ő ismerte a p=211 és q=139 prímtényezőket. Nyilván, hiszen azokat ő maga választotta, és a kulcsgenerálás során ezek szorzatából képezte az m=29329 modulust. Természetesen – mint már említettük – a gyakorlatban a választott prímszámoknak többszázjegyűeknek kell lenniük a megfelelő biztonsági szint eléréséhez.

Bob tehát minden gond nélkül ki tudta számítani az x_1, x_2, \ldots, x_7 számsorozatot. És ami még fontosabb: mivel kizárólag ő ismeri a d=11623 dekódoló kulcsot, ezért rajta kívül bárki más, aki az üzenet megfejtésével próbálkozik Eve-vel azonos helyzetben találja magát.

Az x_1, x_2, \ldots, x_7 számsorozatból már viszonylag egyszerűen megkapható az Alice által elküldött karaktersorozat. Ehhez csak az előző szakaszban alkalmazott előkódolás lépéseit kell megfordítani. Ez már nem része az RSA eljárásnak, de a teljesség igénye miatt röviden ismertetjük.

Ezután pedig válaszolhat Alice-nak ugyanezen a módon. Ekkor azonban Alice publikus kulcsával kell rejtjeleznie a választ, amelyet viszont csak Alice fog tudni visszafejteni a saját titkos kulcsával. Alice-nak és Bob-nak tehát nincs szükségük biztonságos csatornára – például személyes találkozó – ahhoz, hogy egy közös kulcsban megegyezzenek, amelyet aztán egy valamilyen, az RSA-nál jóval hatékonyabb szimmetrikus kulcsú rejtjelező eljáráshoz használhatnak. Ezt egészen nyugodtan megtehetik Eve orra előtt a nembiztonságos csatornán keresztül az RSA eljárásnak köszönhetően.

Az 1. fejezetben ismertetett kulcsmegosztás problémája tehát megoldódni látszik. Van azonban még egy probléma, amelyet meg kell oldani.

21.10RSA partnerhitelesítés és digitális aláírás

Vegyük észre, hogy egy aktív támadó – például Mallory – ezt a rendszert könnyedén kijátszhatja. Mallory ugyanis képes elérni, hogy Alice a Bob-nak szánt üzenetek kódolásához az ő publikus kulcsát használja, miközben abban a hitben van, hogy az valójában Bob publikus kulcsa. Alice-nak emiatt meg kell tudnia győződnie arról, hogy a kódoláshoz használt publikus kulcs valóban Bob publikus kulcsa, és nem pedig Mallory-é, aki csak azt hazudja magáról, hogy ő Bob. Ezt partnerhitelesítésnek neveztük, és a hozzá kapcsolódó problémakört részletesen kifejtettük a 10. fejezetben. A megoldást a digitális aláírások jelentették, amelynek lényegét most röviden átismételjük.

Egy aszimmetrikus kulcsú rejtjelezési eljárás esetén a kulcspár publikus részével kódolt üzeneteket kizárólag ugyanezen kulcspár titkos részével lehet dekódolni. Most igazolni fogjuk, hogy az RSA esetében a kulcsok szerepe felcserélhető. Nevezetesen: a kulcspár titkos részével kódolt üzeneteket kizárólag a kulcspár publikus részével lehet dekódolni.

Vagyis valóban: ha először kódolunk egy üzenetet egy kulcspár titkos részével, majd ezt dekódoljuk ugyanazon kulcspár publikus részével, akkor szintén az eredeti üzenetet kapjuk vissza. Ez a tulajdonság alkalmassá teszi az RSA eljárást digitális aláírások képzéséhez is. Ha ugyanis egy bitsorozat dekódolható például Bob publikus kulcsával, akkor azt csak egy olyan résztvevő kódolhatta, aki Bob titkos kulcsának birtokában volt. Márpedig ha Bob nem teljesen bolond, és valóban sosem adja ki a kezéből a titkos kulcsát, akkor ez bizonyíték arra, hogy az adott üzenetet kizárólag ő küldhette. A digitális aláíráson alapuló partnerhitelesítésről a 10. fejezetben volt szó részletesen, így azt itt nem ismételjük meg.