Episode I
Alice és Bob
21. fejezet
Alice és Bob titkosít
Az előző fejezetben azt vizsgáltuk meg, hogy a 18. fejezetben bevezetett kongruencia, maradékosztály és maradékosztálygyűrű fogalmai mit jelentenek az egész számok esetében. Láthattuk, hogy a kongruenciákkal nagyjából ugyanúgy kell számolni, mint a hagyományos egyenletekkel, de azért bizonyos esetekben vigyázni kell. Ezután megismerkedtünk az Euler-féle -függvénnyel, amely a modulo redukált maradékosztályok számát adja meg. Végül az úgynevezett lineáris kongruenciák megoldhatóságának feltételeit, valamint az Euler-Fermat tételt ismertük meg. Ugyanis az ebben a fejezetben ismertetett RSA eljárás esetén ezek teremtik meg a nyilvános és titkos kulcsok közötti számelméleti kapcsolatot.
De vajon hogyan lehet a kitüntetett közös osztó kiszámítására szolgáló, a 17.4. szakaszban ismertetett euklidészi algoritmust lineáris kongruenciák megoldásához is használni? Hogyan kell kiszámítani az Euler-féle -függvény értékét egy adott számra, és milyen információra van ehhez szükség? Hogyan működik az RSA nevű aszimmetrikus kulcsú rejtjelező eljárás? Ebben a fejezetben erről lesz szó...
Figyelem! Ez a fejezet erőteljesen épít a 17., 19. és 20. fejezetekben felépített alábbi definíciókra, valamint a hozzájuk kapcsolódó tételekre:
Ezek kontextusba helyezése miatt erőteljesen ajánlott elolvasni a 17., 19. és 20. fejezeteket, mivel gyakran hivatkozni fogunk rájuk.
Kezdjük tehát a lineáris kongruenciák megoldásával. Rögzítsünk egy pozitív modulust. A 20.8. Definíció és az utána lévő megjegyzés alapján egy lineáris kongruencia egy megoldása alatt egy olyan modulo maradékosztályt értünk, amelynek bármely elemét behelyettesítve helyére a kongruencia fennáll.
A 20.13. Tétel alapján a fenti lineáris kongruencia akkor és csak akkor oldható meg – azaz létezik ilyen maradékosztály –, ha megoldható az alábbi úgynevezett lineáris diofantoszi egyenlet:
Ebben az esetben tehát megoldás alatt olyan egész számpárt értünk, amelyet a fenti egyenletbe és helyére behelyettesítve fennáll az egyenlet. Ha tehát egy ilyen egyenletet meg tudunk oldani, akkor bármilyen lineáris kongruenciát is meg tudunk oldani. Azok mindegyike ugyanis egy-egy ilyen egyenletre vezethető vissza. Nézzünk is egy gyors példát egy lineáris diofantoszi egyenlethez vezető egyszerű problémára.
A 7., 10. és 13. fejezetekben szó volt már a messzi-messzi Kompánia országáról. Tegyük fel, hogy ebben az országban az emberek aranytallérokon kívül bankjegyeket is használnak fizetőeszközként. Igenám, csakhogy ebben a furcsa országban mindössze kétféle címlet létezik: és aranytallér névértékű bankjegy. Tegyük fel, hogy Alice kinézett valamilyen ajándékot Bob-nak, amely aranytallérba kerül, viszont csak bankjegyek vannak nála.
Kérdés, hogy Alice ki tudja-e fizetni pontosan az összeget ezen bankjegyek segítségével, és ha igen, akkor hányféleképpen? Keressük tehát az alábbi lineáris diofantoszi egyenlet megoldásait:
Ne feledjük, hogy -nek és -nak is egész számnak kell lennie, ráadásul ebben a példában nemnegatív egésznek, mivel a kifizetendő bankjegyek számáról van szó. A 20.13. Tétel alapján a fenti egyenlet akkor és csak akkor oldható meg, ha az kitüntetett közös osztó osztója az egyenlet jobboldalának, azaz -nek. Előszöris tehát ki kell számítanunk a kitüntetett közös osztót annak érdekében, hogy eldöntsük, egyáltalán létezik-e megoldás.
A 17.4. szakaszban ismertettük az euklidészi algoritmus alapgondolatát, amely pontosan erre való. Azt is megmutattuk, hogy ez az eljárás minden olyan gyűrűn végrehajtható, amelynek elemei között valamilyen absztrakt értelemben elvégezhető a maradékos osztás. Ezeket a 17.17. Definícióban euklidészi gyűrűknek neveztük el, és a 17.18. Tétel bizonyításában általánosságban is ismertettük az euklidészi algoritmus menetét.
Eszerint a gyűrű bármely és elemének kitüntetett közös osztóját megkapjuk az alábbi maradékos osztások során kapott utolsó nemnulla maradékként:
Ez jelen esetben tehát lesz:
Itt a szimbólum a 16.6. Definíció szerinti asszociáltság relációt jelöli.
Azt is megmutattuk, hogy az eljárás garantáltan végetér véges számú lépés után, mivel az euklidészi függvénynek a kapott maradékoknál felvett értékei egy szigorúan monoton csökkenő sorozatot alkotnak a természetes számok halmazán, és így a 17.15. Tétel értelmében előbb-utóbb biztosan elérik a -t.
Az egész számok gyűrűjében a 17.19. Definíció szerinti abszolútérték-függvény a 17.20. Tétel értelmében egy euklidészi függvény – azaz euklidészi gyűrű –, és így ezen a gyűrűn alkalmazható az euklidészi algoritmus. Végrehajtva az algoritmus lépéseit a és bemeneti számokon, az alábbi maradékos osztásokat kapjuk:
Az utolsó nemnulla maradék lesz a két bemeneti szám kitüntetett közös osztója, azaz jelen esetben . Ez a szám természetesen osztója a lineáris diofantoszi egyenlet jobboldalának, következésképp ennek az egyenletnek a 20.13. Tétel értelmében létezik megoldása. A 21.1. és a 21.2. szakaszban megmutatjuk, hogy egyrészt hogyan található meg az egyik megoldás az euklidészi algoritmus segítségével, másrészt, hogy ebből hogyan számítható ki az összes többi.
21.1A kibővített euklidészi algoritmus
A 20.13. Tételben igazoltuk, hogy az lineáris diofantoszi egyenlet megolhatóságának szükséges és elégséges feltétele, hogy az egyenlet jobboldala – azaz – osztható legyen az 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ő alakban alkalmasan választott és elemek segítségével.
Amennyiben tehát fennáll az oszthatóság, az azt jelenti, hogy létezik olyan elem, hogy teljesül az alábbi:
Ezt összevetve a Bézout-lemmával a következőt kapjuk:
Felbontva a zárójelet végsősoron megkapjuk az lineáris diofantoszi egyenlet egy megoldását:
Először tehát meg kell határoznunk az és 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 és 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 , , ..., maradékokat számítjuk ki, hanem a , , ..., hányadosokat is felhasználjuk e maradékok lineáris kombinációs előállításához.
Hogy ne csak a levegőbe beszéljünk, térjünk most vissza a 17.4. szakaszban bemutatott példához, és futtassuk le ezúttal a kibővített euklidészi algoritmust a és a egész számokra. A feladat ismét e két szám kitüntetett közös osztójának kiszámítása – jelöljük ezt most -vel –, ezúttal azonban ki is szeretnénk őt fejezni e két szám lineáris kombinációjaként. Azaz keressük az alábbi egyenletben szereplő és együtthatókat:
Ehhez megint használhatunk bármilyen kalkulátort, csak most az osztási maradékokon kívül a hányadosokat is ki kell számolnunk. Ez elvégezhető egy közönséges osztással, aminek az eredményéből a tizedesjegyeket levágva kapjuk meg a keresett hányadost. Ez az egész osztásnak nevezett művelet – itt nem részletezett digitális áramköri okok miatt – az osztási maradék kiszámításához hasonlóan egy számítógép számára rendkívül gyorsan elvégezhető. Ezek után az és együtthatókat az iménti bizonyításban szereplő módon számíthatjuk ki. Az első két lépés együtthatóit tehát az alábbi képletekkel:
A további lépések együtthatóit pedig a megelőző két lépés együtthatóiból az alábbi képletekkel:
Ezek alapján az alábbi táblázat mutatja az algoritmus futását:
A kitüntetett közös osztó az utolsó nemnulla maradék lett, azaz . Ennek lineáris kombinációs együtthatói pedig ugyanebben a sorban találhatók:
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.
Most térjünk vissza a fejezet elején felvetett kompániai példánkhoz, és az iménti tétel alapján határozzuk meg, hogy hányféleképpen tudja Alice kifizetni a Bob-nak szánt aranytalléros ajándékot, amennyiben csak és aranytallér névértékű bankjegyek állnak rendelkezésére. Keressük tehát a nemnegatív egész megoldásait az alábbi lineáris diofantoszi egyenletnek:
Azt már az euklidészi algoritmus segítségével kiszámítottuk, hogy a kitüntetett közös osztó , aminek nyilván többszöröse az egyenlet jobboldalán szereplő . Í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 is és is nemnegatív.
Futtassuk hát le a két együtthatón a kibővített euklidészi algoritmust, és állítsuk elő a kitüntetett közös osztójukat a lineáris kombinációjukként:
A megkapott lineáris kombináció tehát az alábbi:
Minthogy fennáll az oszthatóság a kitüntetett közös osztó és az egyenlet jobboldalán szereplő között, ezért létezik az ő hányadosuk, amelyet jelöljünk most -tel. Ez tehát egy egész szám, amelyre teljesül az alábbi:
A hányadost egy egész osztással kiszámítva – ami jelen esetben nyilván lesz, mivel a "nevezőben" szereplő kitüntetett közös osztó –, valamint felhasználva az imént előállított lineáris kombinációt az alábbit kapjuk:
A baloldalon lévő zárójelet felbontva tulajdonképpen megkaptuk a egyenlet egyik megoldását:
Ebben a megoldásban az sajnos negatív, így ez nem egy jó megoldás számunkra. A 21.2. Tétel 2. és 3. állításai alapján azonban az alábbi képlet segítségével megkapjuk az összes megoldást, amennyiben a paraméterrel végigszaladunk az összes létező egész számon:
Mi alapvetően lusták vagyunk, így nem szeretnénk a paraméter végtelen sok lehetséges értékét végigvizsgálni azért, hogy megtudjuk, mikor kapunk nemnegatív számot -re és -ra egyaránt.
Ehelyett az alábbi egyenlőtlenségeket írjuk fel:
Mivel a 15.11. Definíció szerinti 1. rendezési axióma alapján az összeadás kompatibilis a rendezési relációval, ezért e két egyenlőtlenség átalakítható:
A és a egész osztásokat elvégezve azt kapjuk, hogy mindössze a , és a esetekben lesz a megoldás nemnegatív. Alice tehát háromféleképpen tudja kifizetni a aranytallért a Bobnak szánt ajándékra, amennyiben csak és aranytallér névértékű bankjegyek vannak nála:
Félretéve a szöveges feladatot, most próbáljuk meg a 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ó és értékeket jelenti.
A megoldásokat szolgáltató képletből látható, hogy ha egy adott megoldásból kiindulva a értékét -gyel megnöveljük, akkor az így kapott új megoldáshoz tartozó értéke -tel nő, míg az értéke -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 paraméternek az adott megoldásokhoz tartozó értékeit is feltüntettük.
Ebből szépen látható, hogy valóban csak a , és a é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 -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 -függvény értékét bármilyen tetszőleges pozitív egész számra. A definíció szerint egy pozitív egész szám esetén ez a függvény a modulo 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 maradékosztálygyűrű azon elemei, amelyek invertálhatók a maradékosztályok közötti szorzásra nézve.
A 20.18. Következményben megmutattuk, hogy ez a szám éppenséggel megegyezik a és közötti, -hez relatív prímek számával, amely tehát az Euler-féle -függvénynek egy alternatív definícióját adja. Például a és közötti, -hoz relatív prímek halmaza az alábbi számhalmaz:
Ezek száma , így tehát . Az alábbi tételben a -függvény egy fontos tulajdonságát igazoljuk.
Például próbáljuk ez alapján meghatározni a értékét. Ehhez a prímtényezős felbontását, valamint az iménti tételt használva az alábbi adódik:
Ha feltételezzük, hogy a és a értékeket valahogyan kiszámítottuk, akkor a 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 -függvény értékét.
Ennek és a 21.3. Tételnek a segítségével mostmár bármilyen pozitív egész szám esetén könnyedén ki tudjuk számítani a értéket. Ehhez "mindössze" az egész szám prímtényezős felbontására van szükségünk.
Tegyük fel például, hogy szeretnénk kiszámítani a értéket a prímtényezős felbontásának ismeretében, amely a következő:
Ehhez alkalmazhatjuk a 21.3. és a 21.5. Tételt:
Ha tehát ismerjük a bemeneti egész szám prímtényezős felbontását, akkor könnyedén ki tudjuk számítani a értéket. Ami viszont kriptográfiai szempontból hasonlóan fontos: Ha nem ismerjük prímtényezős felbontását, akkor nem ismeretes hatékony algoritmus 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 hatvány mennyi maradékot ad -gyel osztva. Megmutattuk, hogy ez tulajdonképpen a 18.3. Definíció szerinti gyűrűben elvégzett hatványozásnak felel meg, méghozzá a maradékképző függvény művelettartó tulajdonságai miatt.
Eszerint tehát ahelyett, hogy először a gyűrűben számítanánk ki a hatványt, és vennénk ennek a bődületesen nagy számnak a -gyel való osztási maradékát, a gyűrűben végezzük el az alábbi tényezős moduláris szorzást. Ezt képlettel kifejezve:
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.
Maradjunk továbbra is a moduláris hatvány kiszámításának példájánál. Első lépésként a -as kitevőt felírjuk kettes számrendszerben:
A különböző számrendszerekről részletesen a 3. fejezetben volt szó. Az ott leírtaknak megfelelően ez tulajdonképpen a felírása a bizonyos hatványainak összegeként. Ebben az összegben a -nek épp azok a hatványai szerepelnek, amelyeknek megfelelő helyiértéken -es áll a fenti bináris számábrázolásban. Azaz:
Ennek az összegnek a tagjaiból a 14.12. Definíció 5. pontja szerinti disztributivitási szabályt alkalmazva kiemelhetjük a hatványt:
Ehhez hasonlóan a zárójelben maradt összeg első két tagjából ismételten kiemelhető a hatvány:
Így tehát az eredeti moduláris hatvány felírható a következőképpen:
A hatványozás azonosságairól szóló 18.8. Tétel 2. és 3. pontjai alapján ez így írható fel:
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 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.
Minthogy a maradékképző függvény a 18.7. Tétel alapján egy gyűrűhomomorfizmus az egész számok gyűrűje és a gyűrű között, ezért ez a műveletsorozat a gyűrűben is elvégezhető. Ezt az alábbiakban el is végezzük lépésenként:
Azaz a végeredményt helyett megkaptuk mindössze darab moduláris szorzásból.
Most vizsgáljuk meg az imént leírt módszer lépésszámát általánosságban is. Tegyük fel, hogy a moduláris hatványt szeretnénk meghatározni. Lépésszám alatt most értelemszerűen a szükséges moduláris szorzások számát értjük. Ezt az kitevő nagysága határozza meg, amelyről most tegyük fel, hogy darab számjeggyel írható le a kettes számrendszerben. A legrosszabb eset nyilván az, amikor minden bináris számjegy értéke , hiszen ekkor az összes neki megfelelő 2-hatvány szerepel az összegben:
A sorozatos kiemelések hatására egy olyan kifejezést kapunk, amely darab egymásba ágyazott zárójelet tartalmaz:
Azaz mind az darab zárójel esetén az addigi részeredményhez hozzá kell adni -et, majd az egészet megszorozni -vel. Végül az utolsó lépésben mégegyszer hozzá kell adni az egészhez -et. Mivel ez a kifejezés a 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 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 .
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.
Eddig tehát megismertük a továbbiakban fontos három fő összetevőt:
- Lineáris kongruenciák megoldása
- az Euler-féle -függvény kiszámítása
- az ismételt négyzetreemelések módszere
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 üzenetet. Ehhez előkeresi a nyilvános kulcstárból Bob publikus kulcsát, és ezzel paraméterezi az rejtjelező függvényt. Ily módon előáll az kódszöveg, amelyet elküld Bob-nak. Ezt az üzenetet kizárólag Bob tudja visszafejteni, mivel a publikus kulcshoz tartozó titkos kulcsot csak ő ismeri. Bob tehát a titkos kulccsal paraméterezve a dekódoló függvényt könnyedén vissza tudja állítani az eredeti ü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ő és 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 vagy bináris számjeggyel ábrázolható prímeket jelent. Ez tízes számrendszerben körülbelül a vagy 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 -vel és -val. Bob ezután összeszorozza ezt a két prímszámot. Az így kapott egész számot modulusnak fogjuk nevezni a továbbiakban. Ezt az számot nem szükséges titokban tartani, az ugyanis a publikus kulcs része lesz.
Második lépésként Bob kiszámítja az Euler-féle -függvény értékét -re, azaz kiszámítja a értéket, amelyet szintén a lehető legnagyobb titokban tart. A és prímszámok ismeretében ezt a 21.3., valamint a 21.5. Tétel alapján könnyen meg tudja tenni:
Harmadik lépésként Bob választ egy tetszőleges és közötti egész számot, amely relatív prím -hez. A 20.15. Tétel alapján ezt úgy is megfogalmazhatjuk, hogy Bob választ egy modulo redukált maradékosztályt, az 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 tulajdonképpen a 18.3. Definíció szerinti 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 és 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 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 -hez, azaz megvan a keresett . 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 -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 számot nem szükséges titokban tartani, az ugyanis a publikus kulcs része lesz.
Utolsó lépésként Bob kiszámítja az előző lépésben kiválasztott szám multiplikatív inverzét a gyűrűben. Ehhez ugye meg kell oldania az alábbi lineáris kongruenciát:
A 20.8. Definíció alapján a megoldás a 20.14. Tétel 1. pontja miatt egyetlen darab modulo maradékosztály lesz – mivel relatív prím -hez, és emiatt . Az szám -beli multiplikatív inverze ennek az eredményül kapott maradékosztálynak a legkisebb pozitív eleme lesz, amelyet a továbbiakban -vel fogunk jelölni.
A kiszámításához a 20.13. Tétel szerint Bobnak tulajdonképpen az alábbi lineáris diofantoszi egyenletet kell megoldania, amelyhez a 21.2. Tétel 1. pontja alapján a kibővített euklidészi algoritmust használhatja:
Bob a kapott számot titokban tartja, az ugyanis a titkos kulcs része lesz.
A kulcsgenerálás ezzel befejeződött. Bob kulcspárja a következő lesz:
- Bob publikus kulcsa: Az modulusból és az egész számból álló számpár.
- Bob titkos kulcsa: Az modulusból és a egész számból álló számpár.
Bob ezek után akár meg is semmisítheti az eredetileg választott és prímszámokat, valamint a belőlük kiszámított é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 és 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ő modulust, vagy valamilyen más – mindezidáig nem ismert – módon kiszámítani a értéket, ami ugye a dekódoló kulcs meghatározásához kell.
Bob a kulcspárjának publikus részét – azaz az 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 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ő modulus fogja kijelölni azt a 18.3. Definíció szerinti gyűrűt, amiben majd moduláris hatványozást el kell végezni, az 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 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 számsorozat, amelynek tagjai a gyűrű elemei, azaz -nél kisebb nemnegatív egész számok.
Az Alice által használt rejtjelező függvény az alábbi moduláris hatványozás lesz:
Itt jelöli a nyílt szöveget reprezentáló számsorozat soron következő tagját, az kitevő és az modulus pedig Bob publikus kulcsát alkotják.
Alice tehát a bemeneti nyílt számsorozatból a Bob publikus kulcsával paraméterezett rejtjelező függvény segítségével előállítja az rejtjelezett számsorozatot:
Az így kapott számsorozatot Alice átküldi a nembiztonságos kommunikációs csatornán Bob-nak. A Bob által használt dekódoló függvény nagyon hasonlít a rejtjelező függvényhez. Az egyetlen különbség, hogy ezúttal Bob titkos kulcsával kell paraméterezni a moduláris hatványozást:
Bob tehát a bemeneti rejtjelezett számsorozatból a saját titkos kulcsával paraméterezett dekódoló függvény segítségével "varázslatos módon" visszakapja az Alice által közölni kívánt nyílt számsorozatot:
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
Tegyük fel, hogy Alice egy bizalmas üzenetet szeretne elküldeni Bob-nak. Az egyszerűség kedvéért Alice és Bob megegyeznek, hogy a kommunikációhoz az angol ábécé betűit használják írásjelek és szóközök nélkül, az üzenet végét pedig a # karakter fogja jelezni. A bizalmas üzenet ezek alapján a következő:
sziabobmiahelyzet#
Ahhoz, hogy Alice ezt az üzenetet egy digitális kommunikációs csatornán átküldhesse, valamilyen módon egy bináris jelsorozattá kell alakítania azt. Ez történhet például az ASCII kódrendszer alapján, amelyről bővebben a 2.2. szakaszban volt szó. Mi most az egyszerűség kedvéért egy ennél egyszerűbb kódrendszert fogunk használni, amely csak az angol ábécé kisbetűit és az üzenet végét jelző # karaktert tartalmazza. Ez összesen szimbólum, amely bites kódszavakkal ábrázolható. Az alábbi táblázat első oszlopa a kódolandó szimbólumokat, a második és harmadik oszlop pedig a hozzájuk rendelt számokat tartalmazza tízes és kettes számrendszerben. A számrendszerekről bővebben a 3. fejezetben volt szó:
Ezek alapján a sziabobmiahelyzet# üzenetből az alábbi bit hosszú bináris jelsorozat lesz:
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.
Bob ezért választ magának két különböző prímszámot. Tegyük fel, hogy Bob a és prímszámokat választotta. A gyakorlatban persze a választott prímszámoknak többszázjegyűeknek kell lenniük a megfelelő biztonság érdekében, azonban most a példa kedvéért maradjunk ezeknél. Bob e két prímszám összeszorzásával meghatározza az modulust, majd kiszámítja a értéket:
Bob választ továbbá egy -hez relatív prím számot. Ezt a leírtaknak megfelelően úgy tudja megtenni, hogy választ egy véletlen számot és között, majd az euklidészi algoritmus segítségével leellenőrzi, hogy a választott szám valóban relatív prím-e -hez. Ez majdnem biztosan teljesülni fog már elsőre. Ha esetleg mégsem, akkor újabb véletlenszámokkal próbálkozik mindaddig, amíg nem talál egy megfelelőt. Tegyük fel, hogy Bob az számot választotta. Ha valóban relatív prím -hez, akkor az alábbi lineáris kongruenciának egyetlen megoldása lesz, méghozzá az a modulo maradékosztály, amelyben ott csücsül az számnak a 18.3. Definíció szerinti gyűrűben vett multiplikatív inverze:
Ennek a lineáris kongruenciának a 20.13. Tétel alapján az alábbi lineáris diofantoszi egyenlet felel meg:
Szerencsére a 21.1. Tétel bizonyításában ismertetett kibővített euklidészi algoritmus egyszerre számítja ki az kitüntetett közös osztót, és állítja elő azt és lineáris kombinációjaként. Bob tehát lefuttatja a kibővitett euklidészi algoritmust:
Az utolsó nemnulla maradék , így valóban relatív prím -hoz, továbbá Bob megkapta a 21.1. Tétel szerinti lineáris kombinációs együtthatókat is, azaz lényegében a fenti lineáris diofantoszi egyenlet egy megoldását:
Megvan a keresett , ami tehát . A kulcsgenerálás ezzel befejeződött, Bob RSA kulcspárja a következő:
- Bob publikus kulcsa: Az modulus és az egész szám.
- Bob titkos kulcsa: Az modulus és a egész szám.
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 gyűrű elemeinek sorozatává kell alakítania. Ez egy olyan számsorozatot jelent, amelynek minden tagja nemnegatív és kisebb az modulusnál. Egy rövid számolgatás után azt kapja, hogy a bites számok biztosan megfelelnek ennek a kritériumnak, hiszen . Ezzel szemben a bites számok között már előfordulhatnának a modulusnál esetleg nagyobb számok is, mivel . Így tehát Alice az üzenetet bit hosszú részekre darabolja.
Az elküldendő bitsorozat bit hosszú, így az utolsó darab bitből fog állni. A fennmaradó bitet Alice nyugodtan kitöltheti véletlenszerűen választott bitekkel, mivel a vételi oldalon Bob az üzenet végét jelző # karakterből egyértelműen azonosítani tudja majd ezeket az eldobható biteket. Így tehát az Alice által titkosítandó számsorozat a következő:
Alice ezután a Bob publikus kulcsát alkotó modulus és kitevő segítségével kiszámítja a titkosított számsorozatot. Ezeket a moduláris hatványokat Alice a 21.4. szakaszban ismertetett ismételt négyzetreemelés módszerének segítségével hatékonyan tudja kiszámítani:
Ezután Alice az így kapott számokat kettes számrendszerben ábrázolja az eredeti számsorozathoz hasonlóan. Most azonban már előfordulhat bármilyen szám és között, így Alice kénytelen bitet használni:
Ezeket a bites darabokat Alice szépen egymás után fűzi, és az így kapott 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.
Így tehát mindketten ismerik az modulust, azaz tudják, hogy az Alice által elküldött titkosított bitsorozatot bites részekre kell darabolni ahhoz, hogy megkapják a és közötti számokból álló sorozatot, amely tehát a következő:
Ebből a Bob titkos kulcsát alkotó modulus és kitevő segítségével lehet kiszámítani az eredeti számsorozatot. Ezeket a moduláris hatványokat Bob a 21.4. szakaszban ismertetett ismételt négyzetreemelés módszerének segítségével hatékonyan tudja kiszámítani:
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 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 egész szám multiplikatív inverzét a 18.3. Definíció szerinti gyűrűben, hiszen ez épp a keresett dekódoló kulcs lesz.
Igenám, csakhogy Eve számára még é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 modulus prímtényezős felbontására. Nem ismeretes ugyanis olyan algoritmikus módszer, amellyel a értéke hatékonyan kiszámítható prímtényezőinek ismerete nélkül. Ezért Eve sajnos – szerencsére – kénytelen megkeresni 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 -et, és így a titkos dekódoló kulcsot, mivel ő ismerte a és 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 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 számsorozatot. És ami még fontosabb: mivel kizárólag ő ismeri a 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 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.
Az modulusból ugye tudható, hogy Alice bites számokat használt, amikor előállította ezt a sorozatot. A bites számok között ugyanis már előfordulhatnának ennél nagyobb számok is, mivel a biten kódolható számtartomány -tól -ig terjed. Ezért Bob biten ábrázolja a visszafejtett számokat:
Bob ezeket a biteket összefűzi, és az így kapott bitsorozatból a kódábécé alapján dekódolja az üzenetet. Amikor az üzenet végét jelző # karakterhez ér, a fennmaradó kitöltő biteket eldobja:
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.
Az alábbi egyenlet a publikus kulccsal való kódolás, majd a titkos kulccsal való dekódolás egymás utáni végrehajtását írja le. Ezt ugyan majd csak a következő fejezetben fogjuk igazolni, de most tegyük fel, hogy ennek eredményeként valóban az eredeti üzenetet kapjuk vissza:
Minthogy a maradékképző függvény a 18.7. Tétel alapján egy gyűrűhomomorfizmus az egész számok gyűrűje és a 18.3. Definícióban bevezetett gyűrű között, ezért a zárójelen belüli hatványozás a gyűrűben is elvégezhető. Ugyanezen okok miatt a kitevővel való külső hatványozás szintén elvégezhető a gyűrűben. Ha tehát ezt a két egymás utáni hatványozást a gyűrűben értjük, akkor az alábbi egyenlet írható fel:
A hatványozás azonosságairól szóló 18.8. Tétel bármilyen kommutatív gyűrű esetén alkalmazható, így nyilván a gyűrű esetén is. Ennek 2. pontja alapján az alábbit kapjuk:
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.
Ebben a fejezetben tehát megtanultunk lineáris diofantoszi egyenleteket megoldani a kibővített euklidészi algoritmus segítségével. Ezután az Euler-féle -függvény kiszámításához szükséges összefüggéseket tisztáztuk. Majd a moduláris hatványozáshoz mutattunk egy igen hatékony módszert: az úgynevezett ismételt négyzetreemelések módszerét. Végül ismertettük az RSA algoritmus részleteit, amelyet egy konkrét példán ki is próbáltunk.
Ebből úgy tűnik, hogyha egy üzenetet egy RSA kulcspár valamelyik tagjával kódolunk – legyen az akár a publikus, akár a titkos kulcs –, majd az így kapott eredményt dekódoljuk a kulcspár másik tagjával, akkor varázslatos módon az eredeti üzenetet kapjuk vissza. A következő fejezetben matematikai bizonyítást adunk arra, hogy ez az összefüggés valóban bármilyen, az ismertetett kritériumoknak megfelelő kulcspár, továbbá bármilyen üzenet esetén fennáll. Ezután a 23. fejezetben megismerjük azokat a módszereket, amelyek segítségével viszonylag könnyedén találhatunk többszázjegyű prímszámokat az RSA kulcsgeneráláshoz.