Episode I

Alice és Bob

22. fejezet

Alice, Bob és a kínaiak

Az előző fejezetben megismerkedtünk napjaink egyik legfontosabb aszimmetrikus kulcsú rejtjelezési eljárásával, az RSA algoritmussal. Ehhez alapvetően három összetevőre volt szükség. Először is hatékonyan kell tudni megoldani lineáris kongruenciákat, amelyhez bemutattuk az euklidészi algoritmus kibővített változatát. Másodszor hatékonyan kell tudni kiszámítani az Euler-féle $\varphi$ -függvény értékét. Láttuk, hogy a bemeneti szám prímtényezőinek ismeretében ez gyerekjáték. Megemlítettük ugyanakkor, hogy a prímtényezők ismerete nélkül jelenlegi tudásunk szerint ez gyakorlatilag kivitelezhetetlen, amennyiben ezek a prímtényezők kellően nagyok. Ez adja az RSA eljárás biztonságát. Harmadszor a kódoló és dekódoló műveletek elvégzéséhez hatékonyan kell tudni moduláris hatványozást végezni, amelyhez az ismételt négyzetreemelések módszerével ismerkedtünk meg. Végül egy konkrét példán ki is próbáltuk az eljárást, és megmutattuk, hogy a kulcspár egyik tagjával kódolt üzenetet varázslatos módon a kulcspár másik tagjával lehet dekódolni.

De vajon varázslat helyett valójában mi áll az RSA algoritmus helyes működésének hátterében? Mit állít a kis Fermat-tétel és a kínai maradéktétel, és mi közük van ehhez az egészhez? Mit értünk egy maradékosztálygyűrű dekompozíciója alatt? Hogyan lehet ennek segítségével lényegesen felgyorsítani az RSA dekódolási algoritmust? Ebben a fejezetben erről lesz szó...

Figyelem! Ez a fejezet erőteljesen épít a 20. és a 21. fejezetben 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 20. és a 21. fejezetet, mivel gyakran hivatkozni fogunk rájuk.

Az RSA algoritmus lépéseit tehát már ismerjük, és az előző fejezetben mutattunk is egy konkrét példát az alkalmazására. Ebben a példában először Bob generált magának egy RSA kulcspárt, amelynek publikus részét elérhetővé tette Alice – illetve bárki más – számára, a titkos részét viszont nem adta ki a kezéből. Alice ezután a sziabobmiahelyzet# üzenetet kódolta Bob publikus kulcsával, a titkosított üzetetet pedig átküldte a nembiztonságos csatornán. Ezt az üzenetet egy támadó, de még maga Alice sem tudja dekódolni. Arra ugyanis csak Bob képes, mivel nála van az ehhez szükséges titkos kulcs.

Úgy tűnik tehát, hogyha egy üzenetet egy kulcspár valamelyik tagjával – legyen az akár a publikus, akár a titkos kulcs – kódolunk, 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. Most azt fogjuk megmutatni, hogy ez az összefüggés bármilyen, az ismertetett kritériumoknak megfelelő kulcspár, továbbá bármilyen üzenet esetén valóban fennáll. Ehhez azonban szükségünk lesz két nagyon fontos tételre. Ismerkedjünk is meg az elsővel.

22.1A kis Fermat-tétel

A kis Fermat-tétel egy fontos számelméleti tétel, amelyet Pierre de Fermat fedezett fel 1636-ban. Fermat-nak bosszantó szokása volt, hogy bizonyítás nélkül közölte felfedezéseit kortársaival, mintegy kihívást intézve hozzájuk: jöjjenek rá ők is a bizonyításra. Fermat szokásához híven a kis Fermat-tételre sem adott bizonyítást. Ezt bizonyíthatóan elsőként Gottfried Wilhelm Leibniz német matematikus írta le egy dátumozatlan kéziratban, ahol azt is állította, hogy már 1683 előtt is ismert bizonyítást e tételre. A tétel nevében szereplő "kis" jelzőt a híres nagy Fermat-tételtől való megkülönböztetés miatt szokás használni. Ez utóbbi egészen 1995-ig "nagy Fermat-sejtés" néven volt ismeretes, mivel csak ekkor – mintegy 350 évvel később – sikerült bizonyítást adni rá.

Visszatérve a kis Fermat-tételre, az egy viszonylag egyszerű számelméleti tétel, amely moduláris hatványokról szól, méghozzá azokban az esetekben, amikoris a modulus egy valamilyen pozitív $p$ prímszám. Fermat azt vizsgálta, hogy egy tetszőleges $a$ egész szám moduláris hatványai hogyan alakulnak ebben a modulo $p$ óraaritmetikában. Észrevette, hogy minden olyan esetben, amikor a kitevő megegyezik a $p$ modulussal, akkor az $a$ egész szám $p$ -edik moduláris hatványa is épp megegyezik $a$ -val.

Vizsgáljuk meg például, hogy az $a=2$ egész szám moduláris hatványai hogyan alakulnak a kitevőknek megfelelő óraaritmetikákban. Nyilakkal jelöltük meg azokat a sorokat, amelyekben a kitevő és a modulus prímszám:

\begin{aligned}\to 2^2&\equiv 2\pmod 2 \\ \to 2^3&\equiv 2\pmod 3 \\ 2^4&\equiv 0\pmod 4 \\ \to 2^5&\equiv 2\pmod 5 \\ 2^6&\equiv 4\pmod 6 \\ \to 2^7&\equiv 2\pmod 7 \\ 2^8&\equiv 0\pmod 8 \\ 2^9&\equiv 8\pmod 9 \\ 2^{10}&\equiv 4\pmod{10} \\ \to 2^{11}&\equiv 2\pmod{11} \\ &\vdots \end{aligned}

Valóban úgy tűnik, hogy a prím kitevők esetében a $2$ hatványai mindig kongruensek lesznek $2$ -vel a kitevőnek megfelelő óraaritmetikában.

Az alábbi tétel második állítása éppen azt fogalmazza meg, hogy ez bármilyen alap – tehát nem csak a $2$ –, továbbá bármilyen pozitív prím kitevő esetén így van. Amennyiben $a$ és $p$ relatív prímek, akkor érvényes az első állítás is, amely a kis Fermat-tétel gyakoribb alakja.

22.1. Tétel (A kis Fermat-tétel):

Legyen $p\gt 0$ egy tetszőleges pozitív prímszám, továbbá $a$ egy tetszőleges egész szám, amely relatív prím $p$ -hez. Ekkor teljesül az alábbi kongruencia:

a^{p-1}\equiv 1\pmod p

Az alábbi kongruencia tetszőleges $a$ egész számra – tehát nem csak a $p$ -hez relatív prímekre – teljesül:

a^p\equiv a\pmod p

Megnézem a tudásbázisban

♣

Bizonyítás:

Amennyiben $a$ relatív prím a $p$ modulushoz, akkor alkalmazható az Euler-Fermat tétel, amely szerint ugye teljesül az alábbi kongruencia:

a^{\varphi(p)}\equiv 1\pmod p

A 21.5. Tétel alapján az Euler-féle $\varphi$ -függvény értéke ebben az esetben $p-1$ . Ebből a tétel első állítása adódik:

a^{p-1}\equiv 1\pmod p

Ám ebben az esetben a 20.2. Tétel 5. pontja szerint a kongruencia mindkét oldalát megszorozhatjuk $a$ -val. Így teljesül az alábbi kongruencia is, amely tehát a tétel második állítása azokra az esetekre, amikoris $a$ relatív prím $p$ -hez:

a^p\equiv a\pmod p

Már csak annyit kell megmutatni, hogy ez a második állítás abban az esetben is teljesül, ha $a$ és $p$ nem relatív prímek. A 21.4. Lemma alapján ebben az esetben teljesül a $p|a$ oszthatóság. Ez viszont a 20.1. Tétel 3. pontja alapján épp az alábbi kongruenciát jelenti:

a\equiv 0\pmod p

Ám ekkor a 20.2. Tétel 6. pontja alapján a kongruencia mindkét oldalát $p$ -edik hatványra emelhetjük. Így teljesül az alábbi kongruencia is:

a^p\equiv 0\pmod p

Mivel tehát $a$ is és $a^p$ is $0$ -val kongruens modulo $p$ , ezért a 20.2. Tétel 3. pontja alapján ők egymással is kongruensek modulo $p$ , épp ahogyan a tétel állítja:

a^p\equiv a\pmod p

Megnézem a tudásbázisban

∎

Megjegyzés:

Ez a tétel magától Fermat-tól származik 1636-ból. A bizonyításban felhasználtuk, hogy a kis Fermat-tétel az Euler-Fermat tétel egy speciális esete, amikoris a modulus egy $p$ prímszám, és így a $\varphi(p)$ kitevő $p-1$ -gyel egyezik meg. Megemlítjük azonban, hogy az Euler-Fermat tételt Leonhard Euler mintegy 100 évvel a kis Fermat-tétel felfedezése után publikálta, méghozzá éppen annak tetszőleges – tehát nem csak prím – kitevőkre történő általánosításaként. A kis Fermat-tétel közvetlenül – tehát az Euler-Fermat tétel felhasználása nélkül – is viszonylag könnyen bizonyítható.

Vigyázat! Attól még, hogy valamely $a$ és $n$ egész számokra teljesülnek a tételben szereplő kongruenciák, még nem biztos, hogy $n$ prímszám. Ez azonban elsőre nem látszik. Például $a=2$ esetén a $2^n\equiv 2\pmod n$ kongruenciák látszólag csak azokban az esetekben teljesülnek, amikor az $n$ kitevő prím. Az első ellenpéldára csak az $n=341$ kitevőnél bukkanunk rá. Ekkor teljesül ugyan a $2^{341}\equiv 2\pmod{341}$ kongruencia, a $341$ azonban nem prím, hiszen $341=11\cdot 31$ . A következő ellenpélda $n=561=3\cdot 11\cdot 17$ -nél következik. Néhány továbbit találunk ebben a listában.

Ráadásul az $n=561$ ellenpélda különleges abból a szempontból, hogy esetében nemcsak az $a=2$ , hanem tetszőleges $a$ alap esetén is teljesül az $a^n\equiv a\pmod n$ kongruencia, ennek ellenére $n$ mégsem prím. Másként fogalmazva ez tehát azt jelenti, hogy a tétel megfordítása nem igaz!

Megnézem a tudásbázisban

♣

Azon túlmenően, hogy a most ismertetett kis Fermat-tétel fontos szerepet játszik az RSA algoritmus helyességének igazolásában, Alice-nak és Bob-nak is nagy hasznára lesz a kulcsgeneráláshoz szükséges óriási – a gyakorlatban többszázjegyű – prímszámok kereséséhez. Erről a következő fejezetben lesz szó, most azonban ismerkedjünk meg egy másik, az RSA működése szempontjából fontos kérdéssel.

22.2Kongruenciarendszerek

A 20. fejezetben megismerkedtünk az úgynevezett kongruenciaegyenletekkel. Ezek olyan kongruenciák, amelyekben valamilyen $x$ ismeretlen is szerepel, a feladatunk pedig az egész számok egy olyan részhalmazának – vagy részhalmazainak – meghatározása, amelynek – vagy amelyeknek – elemeit behelyettesítve az $x$ ismeretlen helyére a kongruencia teljesül. E kongruenciaegyenletek legegyszerűbb képviselői az úgynevezett lineáris kongruenciák voltak, így a továbbiakban elsősorban ezeket fogjuk példaként felhozni.

Legyen például $a$ és $b$ tetszőleges, $m\gt 0$ pedig valamilyen pozitív egész szám, és tekintsük az alábbi lineáris kongruenciát:

a\cdot x\equiv b\pmod m

A 20.8. Definíció utáni megjegyzés alapján egy ilyen kongruenciaegyenletnek a megoldásai teljes modulo $m$ maradékosztályok lesznek – amennyiben persze létezik megoldás.

Most bonyolítsuk meg a dolgot egy kicsit. A hagyományos egyenletekhez hasonlóan a kongruenciaegyenletek esetén is előfordulhat, hogy ugyanarra az ismeretlenre egyidejűleg több, különböző modulus szerinti kongruenciafeltételt is előírunk. Ezeket kongruenciarendszereknek nevezzük.

A példa kedvéért továbbra is a lineáris kongruenciáknál maradva tegyük fel, hogy most az egész számoknak azon részhalmazát – vagy részhalmazait – keressük, amelynek – vagy amelyeknek – elemei egyszerre elégítik ki az alábbi mindkét kongruenciát:

\begin{aligned}3x&\equiv 2\pmod 5 \\ 6x&\equiv 4\pmod 8\end{aligned}

Nyilvánvalóan egy ilyen rendszer megoldhatóságának szükséges feltétele, hogy a benne szereplő kongruenciák külön-külön megolhatók legyenek. Ez ebben a példában természetesen a 20.13. Tétel alapján teljesül, mivel a $(3,5)\sim 1$ és a $(6,8)\sim 2$ kitüntetett közös osztók osztói a megfelelő kongruenciák jobboldalainak, azaz rendre a $2$ és a $4$ egész számoknak.

A 20.14. Tétel 1. pontja alapján az első kongruenciának $(3,5)\sim 1$ darab modulo $5$ maradékosztály, míg a másodiknak $(6,8)\sim 2$ darab modulo $8$ maradékosztály lesz a megoldása.

Ezek megtalálásához előszöris a 20.13. Tétel alapján az alábbi két lineáris diofantoszi egyenletet kell megoldani:

\begin{aligned}3x+5y&=2 \\ 6x+8y&=4\end{aligned}

Ezt a 21.2. Tétel 1. pontja alapján a kibővített euklidészi algoritmussal tudjuk megtenni. Az így kapott megoldásokat a 20.13. Tételben leírtaknak megfelelően visszafordítva a kongruenciák nyelvére azt kapjuk, hogy a $3x\equiv 2\pmod 5$ kongruenciának a $[4]_5$ modulo $5$ maradékosztály, míg a $6x\equiv 4\pmod 8$ kongruenciának a $[6]_8$ modulo $8$ maradékosztály egy-egy megoldása lesz. Előbbinek ugye nincs más megoldása, míg utóbbinak a 20.14. Tétel 2. pontja alapján egy további megoldása lesz a $[2]_8$ modulo $8$ maradékosztály.

A fenti kongruenciarendszerben szereplő két lineáris kongruencia megoldásait az alábbiakban foglaltuk össze a 19.1. és a 19.3. Definícióban tanult halmazelméleti jelölésekkel:

\begin{aligned}3x\equiv 2\pmod 5 &\to x\in [4]_5 \\ 6x\equiv 4\pmod 8 &\to x\in [6]_8 \cup [2]_8\end{aligned}

Olyan egész számokat keresünk tehát, amelyek $5$ -tel osztva $4$ maradékot, és $8$ -cal osztva $6$ vagy $2$ maradékot adnak. Azaz tulajdonképpen az alábbi két kongruenciarendszer megoldásait keressük:

\begin{array}{c} \boxed{\begin{aligned}x&\equiv 4\pmod 5 \\ x&\equiv 6\pmod 8\end{aligned}} \\ \\ \boxed{\begin{aligned}x&\equiv 4\pmod 5 \\ x&\equiv 2\pmod 8\end{aligned}} \end{array}

Az ilyen jellegű kérdések megválaszolására siet segítségünkre a most bemutatásra kerülő nagyon fontos összefüggés.

22.3A kínai maradéktétel

Azt a kérdést szeretnénk tehát megválaszolni, hogy melyek azok az egész számok, amelyek adott modulusokkal osztva adott maradékokat adnak. Itt most csak azzal a számunkra fontos esettel foglalkozunk, amikor ezek a modulusok páronként relatív prímek egymáshoz – azaz bármely két modulus egymáshoz relatív prím. Ilyen például az előző szakaszban szereplő példa, hiszen az $5$ és $8$ modulusok egymáshoz relatív prímek.

Az írásos emlékek alapján az alábbi tételt már mintegy 2000 évvel ezelőtt is ismerte egy bizonyos Szun Cu nevű kínai matematikus, ezért ezt kínai maradéktétel néven szoktuk emlegetni.

22.2. Tétel (Kínai maradéktétel):

Legyenek $a$ és $b$ tetszőleges, $p\gt 0$ és $q\gt 0$ pedig valamilyen egymáshoz relatív prím pozitív egész számok. Ekkor az alábbi kongruenciarendszer megoldható, és a megoldás egyetlen modulo $pq$ maradékosztály lesz:

\begin{aligned}x&\equiv a\pmod p \\ x&\equiv b\pmod q\end{aligned}

Más megfogalmazásban minden, a fenti két kongruenciát egyszerre kielégítő egész szám ugyanabba az egyetlen modulo $pq$ maradékosztályba esik, továbbá ennek a bizonyos maradékosztálynak minden eleme kielégíti a fenti két kongruenciát.

Megnézem a tudásbázisban

♣

Bizonyítás:

Először a kongruenciarendszer megoldhatóságát igazoljuk. Az első kongruenciát pontosan az $a$ egész szám által reprezentált $[a]_p$ maradékosztály elemei elégítik ki. Ezek a 20.4. Tétel alapján épp azok az $x$ egész számok lesznek, amelyek felírhatók az alábbi alakban valamilyen alkalmasan megválasztott $k$ paraméterrel:

x=kp+a

Ezt behelyettesítve a második kongruenciába:

\underbrace{kp+a}_{=x}\equiv b \pmod q

Azt kell tehát igazolnunk, hogy létezik ilyen $k$ . Vegyük észre, hogy a kongruencia mindkét oldalából $a$ -t kivonva az alábbi lineáris kongruenciát kapjuk:

kp\equiv b-a\pmod q

Ez viszont a 20.13. Tétel alapján megoldható $k$ -ra, hiszen a tétel szövege szerint ugye $p$ és $q$ egymáshoz relatív prímek, azaz $(p,q)\sim 1$ , ami nyilván osztója a kongruencia jobboldalának, azaz $b-a$ -nak.

Másodszor azt mutatjuk meg, hogy minden, a kongruenciarendszert kielégítő egész szám ugyanabból a modulo $pq$ maradékosztályból származik. Legyen ezért $x_1$ és $x_2$ két tetszőleges egész szám, amelyek mindkét kongruenciát kielégítik. Azaz egyrészt:

\begin{aligned}x_1&\equiv a\pmod p \\ x_1&\equiv b\pmod q\end{aligned}

Másrészt:

\begin{aligned}x_2&\equiv a\pmod p \\ x_2&\equiv b\pmod q\end{aligned}

Ez a 20.2. Tétel 3. pontja alapján azt jelenti, hogy az $x_1$ és $x_2$ egész számok kongruensek egymással mindkét modulus szerint, azaz:

\begin{aligned}x_1&\equiv x_2\pmod p \\ x_1&\equiv x_2\pmod q\end{aligned}

Ez a 20.1. Tétel 3. pontja alapján azt jelenti, hogy az $x_1-x_2$ különbség többszöröse $p$ -nek is és $q$ -nak is, azaz:

\begin{aligned}p&|x_1-x_2 \\ q&|x_1-x_2\end{aligned}

Az első oszthatóság azt jelenti, hogy létezik olyan $k$ egész szám, hogy

pk=x_1-x_2

Következésképp a második oszthatóság így írható fel:

q|\underbrace{pk}_{=x_1-x_2}

Mivel $q$ és $p$ egymáshoz relatív prímek, ezért az Euklidészi lemma alapján:

q|k

Azaz létezik olyan $l$ egész szám, hogy:

ql=k

Ezt behelyettesítve a $pk=x_1-x_2$ egyenletbe az alábbit kapjuk:

p\cdot\underbrace{ql}_{=k}=pq\cdot l=x_1-x_2

Azaz $pq|x_1-x_2$ , ami a 20.1. Tétel 3. pontja alapján azt jelenti, hogy valóban teljesül az alábbi kongruencia:

x_1\equiv x_2\pmod{pq}

Tehát valóban igaz, hogy bármely két, a tételben szereplő kongruenciarendszert kielégítő egész szám ugyanabba a modulo $pq$ maradékosztályba esik.

Végül azt kell igazolni, hogy ennek a bizonyos modulo $pq$ maradékosztálynak minden eleme kielégíti a kongruenciarendszert. Tegyük fel ezért, hogy $s$ egy olyan egész szám ebben a maradékosztályban, amelyre teljesül a kongruenciarendszer, azaz:

\begin{aligned}s&\equiv a\pmod p \\ s&\equiv b\pmod q\end{aligned}

Tegyük fel ezenkívül indirekt, hogy létezik olyan $t$ egész szám ugyanebben a maradékosztályban, amelyre viszont nem teljesül legalább az egyik a tételben szereplő kongruenciák közül. Mivel $t$ ugyanabban a modulo $pq$ maradékosztályban van, mint $s$ , ezért igaz az alábbi:

s\equiv t\pmod{pq}

Minthogy a $p|pq$ valamint a $q|pq$ oszthatóságok a 16.2. Tétel 7. pontja alapján teljesülnek, ezért a 20.2. Tétel 7. pontja miatt teljesülnek az alábbi kongruenciák is:

\begin{aligned}s&\equiv t\pmod p \\ s&\equiv t\pmod q\end{aligned}

Azaz $t$ egyrészt ugyanabba a modulo $p$ maradékosztályba esik, mint $s$ , vagyis a 20.8. Definíció utáni megjegyzés alapján ő kielégíti az $x\equiv a\pmod p$ kongruenciát. Másrészt ehhez hasonlóan $t$ ugyanabba a modulo $q$ maradékosztályba is esik, mint $s$ , ezért ő kielégíti az $x\equiv b\pmod q$ kongruenciát is. Így tehát $t$ mégiscsak kielégíti a tételben szereplő kongruenciarendszert, ami ellentmond az indirekt feltételezésünknek. Az $[s]_{pq}$ maradékosztálynak tehát valóban minden eleme kielégíti a kongruenciarendszert, ahogyan a tétel állítja.

Megnézem a tudásbázisban

∎

Az előző szakaszban szereplő példánál maradva keressük tehát az alábbi két kongruenciarendszer megoldásait:

\begin{array}{c} \boxed{\begin{aligned}x&\equiv 4\pmod 5 \\ x&\equiv 6\pmod 8\end{aligned}} \\ \\ \boxed{\begin{aligned}x&\equiv 4\pmod 5 \\ x&\equiv 2\pmod 8\end{aligned}} \end{array}

Az első kongruenciarendszer megoldásit az a halmaz fogja alkotni, amely a $[4]_5$ és a $[6]_8$ maradékosztályok közös része, azaz metszete. Mivel az $5$ és a $8$ modulusok egymáshoz relatív prímek, ezért alkalmazhatjuk a kínai maradéktételt. Eszerint a keresett halmaz épp egy modulo $5\cdot 8=40$ maradékosztály lesz.

Ellenőrizzük is le, azaz írjuk fel egymás alá a $[4]_5$ és a $[6]_8$ maradékosztályokat, és keretezzük be a közös elemeiket:

\begin{aligned}[4]_5&=\{\ldots; 4;9;\boxed{14};19;24;29;34;39;44;49;\boxed{54};59;\ldots\} \\ [6]_8&=\{\ldots; 6;\boxed{14};22;30;38;46;\boxed{54};62;\ldots\} \end{aligned}

Látható, hogy a felső sorban az elemek – modulo $5$ maradékosztályról lévén szó – $5$ -ösével követik egymást, és minden $8$ -adik elem lett bekeretezve. Ezzel szemben az alsó sorban az elemek – modulo $8$ maradékosztályról lévén szó – $8$ -asával követik egymást, és minden $5$ -ödik elem lett bekeretezve.

Ha tehát kigyűjtjük a bekeretezett elemeket egy halmazba, akkor azok épp $40$ -esével fogják egymást követni, tehát ők valóban egy modulo $40$ maradékosztályt alakotnak, méghozzá a következőt:

[14]_{40}=\{\ldots; 14;54;94;134;174;214;\ldots\}

Ezek – és a kínai maradéktétel alapján csak ezek – az egész számok elégítik ki tehát az első kongruenciarendszert.

A második kongruenciarendszer esetén a $[4]_5$ és a $[2]_8$ maradékosztályok metszetét keressük. Ezt az előzőhöz hasonló módszerrel kaphatjuk meg:

\begin{aligned}[4]_5&=\{\ldots; 4;9;14;19;24;29;\boxed{34};39;44;49;54;59;64;69;\boxed{74};\ldots\} \\ [2]_8&=\{\ldots; 2;10;18;26;\boxed{34};42;50;58;66;\boxed{74};\ldots\} \end{aligned}

Ha ismét kigyűjtjük a bekeretezett elemeket egy halmazba, akkor azok szintén $40$ -esével fogják egymást követni, tehát ők ugyancsak egy modulo $40$ maradékosztályt alakotnak, méghozzá a következőt:

[34]_{40}=\{\ldots; 34;74;114;154;194;234;\ldots\}

Az alábbiakban összefoglaltuk a két kongruenciarendszer megoldását, amely tehát egy-egy modulo $40$ maradékosztály:

\begin{array}{ccc} \boxed{\begin{aligned}x&\equiv 4\pmod 5 \\ x&\equiv 6\pmod 8\end{aligned}} & \to & [14]_{40} \\ \\ \boxed{\begin{aligned}x&\equiv 4\pmod 5 \\ x&\equiv 2\pmod 8\end{aligned}} & \to & [34]_{40} \end{array}

22.4Kongruenciarendszerek megoldása

Most megmutatjuk, hogy ez a "bekeretezős" módszer mindig működik, és eljárást is adunk a keresett maradékosztály kiszámítására. Tulajdonképpen az a feladat, hogy adva van egy modulo $p$ maradékosztályból – jelöljük ezt $A$ -val – és egy modulo $q$ maradékosztályból – jelöljük ezt $B$ -vel – álló rendezett pár, ahol $p$ és $q$ egymáshoz relatív prímek. A feladat megtalálni azt az $X$ -szel jelölt halmazt, amely épp a megadott két maradékosztály metszetével egyezik meg:

X=A\cap B

A kínai maradéktétel tehát azt állítja, hogy amennyiben $p$ és $q$ egymáshoz relatív prímek, akkor az $X$ -szel jelölt halmaz éppenséggel egy modulo $pq$ maradékosztály lesz. Hamarosan látni fogjuk, hogy ennél jóval több is igaz.

Ehhez először röviden átismételjük a rendezett pár fogalmát, amelyről korábban már volt szó. Elsőként a kétváltozós művelet fogalmának bevezetésekor találkoztunk vele a 11.5. szakaszban. A kétváltozós műveleteket a 11.3. Definícióban olyan függvényekként definiáltuk, amelyek egy valamilyen $S$ halmaz elemeiből alkotott párokhoz az $S$ halmaz elemeit rendelik hozzá. Például az egész számok $\Z$ halmazán értelmezett szokásos összeadás művelet, mint függvény a $(3;2)$ rendezett párhoz az $5$ egész számot rendeli hozzá.

Másodszor a 12.5. szakaszban definiált kétváltozós reláció kapcsán került elő ez a fogalom. Egy szintén valamilyen $S$ halmazon értelmezett kétváltozós relációt a 12.9. Definícióban az $S$ elemeiből alkotott rendezett párok halmazának egy részhalmazaként definiáltuk. Azt mondtuk, hogy egy $R$ reláció akkor áll fenn két $S$ -beli $a$ és $b$ elem között, ha az $(a;b)$ rendezett pár eleme az $R$ halmaznak. Például a $\Z$ halmazon értelmezett $\leq$ relációnak, mint halmaznak eleme a $(2;3)$ rendezett pár – hiszen $2\leq 3$ –, de nem eleme a $(3;2)$ rendezett pár – hiszen $3\nleq 2$ .

Végül a 13. fejezetben magukat az egész számokat is a természetes számok $\N$ halmazának elemeiből alkotott rendezett párok segítségével definiáltuk.

Az eddig felsorolt példákban egyrészt "párokról", azaz kétkomponensű objektumokról volt szó, másrészt pedig a "pár" két komponense ugyanabból a halmazból került ki. A 12.8. Definícióban ennél általánosabban fogalmazva határoztuk meg, hogy pontosan mit értünk kettő vagy több halmaz direkt szorzata, valamint rendezett pár vagy rendezett $n$ -es alatt.

Egy kézenfekvő példa $n$ darab halmaz direkt szorzatára az $n$ dimenziós tér pontjainak halmaza. Az egyszerűség kedvéért szorítkozzunk most a sík pontjaira, amikoris $n=2$ . Ezeket általában egy derékszögű koordinátarendszerben szoktuk ábrázolni. Ilyenkor felrajzolunk két egymásra merőleges számegyenest, amelyek a $0$ -nál metszik egymást. Ezek után egy síkbeli pontot egy számpárral írhatunk le, amelynek komponenseit a pont koordinátáinak nevezzük.

**22.1. ábra:** Derékszögű koordinátarendszer

A számegyenes pontjainak halmazát $\R$ -rel szoktuk jelölni, a sík pontjainak halmaza pedig ennek megfelelően az $\R\times \R$ , vagy másként az $\R^2$ direkt szorzat lesz. Ehhez hasonlóan a $3$ , $4$ , ..., $n$ dimenziós tér pontjainak halmazát $\R^3$ , $\R^4$ , ..., $\R^n$ jelöli, amelynek elemei $3$ , $4$ , ..., $n$ komponensből fognak állni.

Egy másik kézenfekvő példa direkt szorzatra az 52 lapos franciakártya. Egy ilyen pakliban minden kártyalapnak van valamilyen "színe" (angolul "suit") és "értéke" (angolul "rank"). Jelöljük a lehetséges színek halmazát $S$ -sel, a lehetséges értékek halmazát pedig $R$ -rel:

\begin{aligned}S&=\{\clubs;\diamonds;\spades;\hearts\} \\ R&=\{2;3;4;5;6;7;8;9;10;\text{J};\text{Q};\text{K};\text{A}\}\end{aligned}

Mivel a kártyapakliban lévő lapok minden lehetséges színt és értéket felvehetnek, ezért e lapok halmaza tulajdonképpen az $S\times R$ direkt szorzat lesz. Ekkor egy kártyalapot egy olyan rendezett pár reprezentál, amelynek első komponense az $S$ , a második komponense pedig az $R$ halmaz eleme. Például a "treff hetest" reprezentáló rendezett pár a $(\clubs;7)$ lesz.

Most vonatkoztassuk a direkt szorzat fogalmát a kínai maradéktétel állítására. A szakasz elején szereplő $A$ -ból és $B$ -ből álló rendezett pár első komponense tehát a modulo $p$ maradékosztálygyűrű, míg a második komponense a modulo $q$ maradékosztálygyűrű eleme. Maga az $(A;B)$ rendezett pár tehát eleme e két maradékosztálygyűrű direkt szorzatának. Azaz a 20.5. Tételben szereplő és a most bevezetett jelölésekkel:

\begin{aligned}A &\in \Z/p\Z \\ B &\in \Z/q\Z \\ (A;B) &\in \Z/p\Z \times \Z/q\Z\end{aligned}

Ezek után az alábbi tételben megadjuk a kínai maradéktétel egy alternatív megfogalmazását, valamint egy eljárást is mutatunk a tételben szereplő $A\cap B$ halmaz előllítására:

22.3. Tétel (A kínai maradéktétel alternatív megfogalmazása):

Legyenek $p\gt 0$ és $q\gt 0$ valamilyen pozitív egész számok, továbbá tegyük fel, hogy $p$ és $q$ egymáshoz relatív prímek. Ekkor minden $(A;B)\in \Z/p\Z \times \Z/q\Z$ rendezett pár esetén $A\cap B\in \Z/pq\Z$ .

Tegyük fel, hogy az $x_1$ és $x_2$ egész számok kielégítik az alábbi kongruenciákat:

\begin{aligned}px_1&\equiv 1\pmod q \\ qx_2&\equiv 1\pmod p\end{aligned}

Amennyiben az $A$ és $B$ maradékosztályokat rendre valamilyen $a$ és $b$ egész számokkal reprezentáljuk – azaz $A=[a]_p$ és $B=[b]_q$ –, akkor az alábbi képlet az $A\cap B$ maradékosztály egy reprezentánselemét szolgáltatja:

A\cap B=[aqx_2 + bpx_1]_{pq}

Megnézem a tudásbázisban

♣

Bizonyítás:

Az $A=[a]_p$ és $B=[b]_q$ maradékosztályok metszete pontosan azokat az egész számokat fogja tartalmazni, amelyek mindkét maradékosztályban benne vannak. Ezek ugye az alábbi kongruenciarendszert kielégítő egész számok lesznek:

\begin{aligned}x&\equiv a\pmod p \\ x&\equiv b\pmod q\end{aligned}

A kínai maradéktétel alapján ezek az egész számok pontosan egy modulo $pq$ maradékosztályt alkotnak, azaz valóban $A\cap B\in \Z/pq\Z$ .

Most igazoljuk, hogy a tételben megadott képlet valóban az $A\cap B$ maradékosztály egy reprezentánselemét adja. Ehhez azt kell megmutatni, hogy az $aqx_2 + bpx_1$ egész szám benne van ebben a halmazban. A halmazok közötti metszetképzésről szóló 19.3. Definíció alapján ez pontosan akkor teljesül, ha teljesül az alábbi mindkét feltétel:

\begin{aligned}aqx_2 + bpx_1 &\in A \\ aqx_2 + bpx_1 &\in B\end{aligned}

Nézzük először az első feltételt: Mivel az $A$ halmaz egy modulo $p$ maradékosztály, amelynek az $a$ egész szám egy reprezentánseleme, ezért ez a feltétel pontosan akkor teljesül, ha fennáll az alábbi kongruencia:

aqx_2 + bpx_1 \equiv a\pmod p

A kongruencia baloldalán szereplő összeg második, $bpx_1$ tagja ugye $p$ -nek többszöröse, így ő $0$ -val kongruens modulo $p$ . Az összeg első, $aqx_2$ tagjában viszont a $qx_2$ tényező a tétel szövege alapján $1$ -gyel, és így ez a tag $a$ -val kongruens modulo $p$ . Összefoglalva tehát valóban teljesül a fenti kongruencia, mivel:

a\cdot \underbrace{qx_2}_{\equiv 1} + \underbrace{bpx_1}_{\equiv 0} \equiv a\pmod p

Most nézzük a második feltételt: Mivel a $B$ halmaz egy modulo $q$ maradékosztály, amelynek a $b$ egész szám egy reprezentánseleme, ezért ez a feltétel pontosan akkor teljesül, ha fennáll az alábbi kongruencia:

aqx_2 + bpx_1 \equiv b\pmod q

A kongruencia baloldalán szereplő összeg első, $aqx_2$ tagja ugye $q$ -nak többszöröse, így ő $0$ -val kongruens modulo $q$ . Az összeg második, $bpx_1$ tagjában viszont a $px_1$ tényező a tétel szövege alapján $1$ -gyel, és így ez a tag $b$ -vel kongruens modulo $q$ . Összefoglalva tehát valóban teljesül a fenti kongruencia, mivel:

\underbrace{aqx_2}_{\equiv 0} + b\cdot \underbrace{px_1}_{\equiv 1} \equiv b\pmod q

A $aqx_2 + bpx_1$ összeg tehát benne van az $A\cap B$ metszethalmazban, amely – mint láttuk – egy modulo $pq$ maradékosztály, és így valóban annak egy reprezentánselemét adja.

Megnézem a tudásbázisban

∎

Megjegyzés:

A tételben szereplő $px_1\equiv 1\pmod q$ és $qx_2\equiv 1\pmod p$ kongruenciáknak a 20.13. Tétel alapján létezik megoldása, hiszen $p$ és $q$ a tétel szövege alapján relatív prímek. Ugyanezen okból a 20.14. Tétel 1. pontja miatt a megoldás mindkét kongruencia esetén egy-egy maradékosztály lesz. Ezek megtalálásához a 20.13. Tétel alapján az alábbi lineáris diofantoszi egyenleteket kell megoldani:

\begin{aligned}px_1+qy_1&=1 \\ qx_2+py_2&=1\end{aligned}

Ezeket a 21.2. Tétel 1. pontja alapján a 21.1. Tétel bizonyításában ismertetett kibővített euklidészi algoritmus segítségével tehetjük meg. Azaz valóban egy eljárást kaptunk az $A\cap B$ maradékosztály egy reprezentánselemének meghatározásához.

Megnézem a tudásbázisban

♣

Most térjünk vissza az előző szakaszban szereplő példára, amelynek során a "bekeretezős" módszerrel az alábbi két kongruenciarendszer megoldását kerestük meg:

\begin{array}{ccc} \boxed{\begin{aligned}x&\equiv 4\pmod 5 \\ x&\equiv 6\pmod 8\end{aligned}} & \to & [14]_{40} \\ \\ \boxed{\begin{aligned}x&\equiv 4\pmod 5 \\ x&\equiv 2\pmod 8\end{aligned}} & \to & [34]_{40} \end{array}

Az első rendszernek tehát a $[14]_{40}$ , a másodiknak pedig a $[34]_{40}$ maradékosztály volt a megoldása. Ez a módszer azonban a gyakorlatban nem használható, így most próbáljuk meg megtalálni a megoldásokat a 22.3. Tételben ismertetett eljárás segítségével.

Az első kongruenciarendszer esetén keressük tehát az $A=[4]_5$ és a $B=[6]_8$ maradékosztályok metszetét. Ehhez a tétel szerint kell keresnünk olyan $x_1$ és $x_2$ egész számokat, amelyek kielégítik az alábbi kongruenciákat:

\begin{aligned}5x_1&\equiv 1\pmod 8 \\ 8x_2&\equiv 1\pmod 5\end{aligned}

Ezeket a 21.1. Tétel bizonyításában ismertetett kibővített euklidészi algoritmussal megoldva például az alábbi számokat választhatjuk $x_1$ -nek és $x_2$ -nek:

\begin{aligned}x_1&=5 \\ x_2&=2\end{aligned}

Ezután a tételben szereplő képletet alkalmazva az $A\cap B$ maradékosztály alábbi reprezentánselemét kapjuk:

4\cdot 8\cdot 2 + 6\cdot 5\cdot 5=64+150=214

Valóban, az eredményül kapott $214$ egész szám benne van a $[14]_{40}$ maradékosztályban, amelyet a "bekeretezős" módszerrel kaptunk az első kongruenciarendszerre az előző szakaszban.

Most nézzük meg a második kongruenciarendszert. Ebben az esetben az $A=[4]_5$ és a $B=[2]_8$ maradékosztályok metszetét keressük. Az előző példánál már megkaptuk az $5x_1\equiv 1\pmod 8$ és a $8x_2\equiv 1\pmod 5$ kongruenciák megoldásait, így azokat most is használhatjuk. A tételben szereplő képletet alkalmazva most az alábbi reprezentánselemét kapjuk meg az $A\cap B$ halmaznak:

4\cdot 8\cdot 2 + 2\cdot 5\cdot 5=64+50=114

Valóban, az eredményül kapott $114$ egész szám benne van a $[34]_{40}$ maradékosztályban, amelyet a "bekeretezős" módszerrel kaptunk a második kongruenciarendszerre az előző szakaszban.

A most tanult eljárás tehát tulajdonképpen egy függvényt valósít meg, amely a $\Z/p\Z \times \Z/q\Z$ halmazt képezi le a $\Z/pq\Z$ halmazra. Méghozzá minden maradékosztálypárt e párban szereplő maradékosztályok metszetére.

**22.2. ábra:** Példa nem bijektív és bijektív leképezésre

Most igazoljuk, hogy az utóbbi a helyzet. Hamarosan kiderül, hogy ez miért olyan fontos.

22.4. Tétel (A kínai maradéktétel megfordítása):

Legyenek $p\gt 0$ és $q\gt 0$ valamilyen pozitív egész számok, továbbá tegyük fel, hogy $p$ és $q$ egymáshoz relatív prímek. Ekkor minden $X\in \Z/pq\Z$ maradékosztályhoz pontosan egy olyan $(A;B)\in \Z/p\Z\times \Z/q\Z$ maradékosztálypár létezik, amely pár komponenseinek $X$ a metszete, azaz amelyre teljesül az alábbi:

X=A\cap B

Amennyiben az $X$ maradékosztályt egy valamilyen $s$ egész számmal reprezentáljuk – azaz $X=[s]_{pq}$ –, akkor $s$ egyúttal a keresett $A$ és $B$ maradékosztályok reprezentánseleme is:

\begin{aligned}A&=[s]_p \\ B&=[s]_q\end{aligned}

Megnézem a tudásbázisban

♣

Bizonyítás:

A tétel bizonyításához az alábbi két állítást kell igazolni:

Az $X$ maradékosztály valóban az $(A;B)\in \Z/p\Z\times \Z/q\Z$ maradékosztálypár metszete, azaz $X=A\cap B$ .
Nincs másik olyan maradékosztálypár a $\Z/p\Z\times \Z/q\Z$ halmazban, amelynek $X$ a metszete lenne.

Az 1. állítás: a 19.2. Definíció utáni megjegyzés 5. pontja alapján $X$ és $A\cap B$ akkor és csak akkor egyezik meg, ha egymásnak részhalmazai, azaz teljesülnek az alábbiak:

\begin{aligned} X&\sube A\cap B \\ X&\supe A\cap B \end{aligned}

Az $X\sube A\cap B$ tartalmazási reláció a 19.2. Definíció alapján azt jelenti, hogy az $X=[s]_{pq}$ maradékosztály minden eleme egyúttal az $A=[s]_p$ -nek is és $B=[s]_q$ -nak is eleme. Legyen például $t\in X$ egy tetszőleges elem az $X=[s]_{pq}$ maradékosztályban. Ezt úgy is megfogalmazhatjuk, hogy $t$ ugyanúgy az $X$ maradékosztályt reprezentálja, mint $s$ . Azaz $[s]_{pq}=[t]_{pq}$ , ami ugye az alábbi kongruenciát jelenti:

s\equiv t\pmod{pq}

Mivel azonban a $p|pq$ és $q|pq$ oszthatóságok nyilvánvalóan teljesülnek, ezért a 20.2. Tétel 7. pontja miatt teljesülnek az alábbi kongruenciák is:

\begin{aligned}s&\equiv t\pmod p \\ s&\equiv t\pmod q\end{aligned}

Tehát $t$ benne van az $A=[s]_p$ és $B=[s]_q$ maradékosztályokban, azaz valóban teljesül az $X\sube A\cap B$ tartalmazási reláció.

Most az $A\cap B\sube X$ tartalmazási relációt igazoljuk. Ez a 19.2. Definíció alapján azt jelenti, hogy az $A=[s]_p$ és $B=[s]_q$ maradékosztályok közös elemei egyúttal az $X=[s]_{pq}$ maradékosztálynak is elemei. Legyen például $t\in A\cap B$ egy tetszőleges elem az $A=[s]_p$ és $B=[s]_q$ maradékosztályok metszetében. Ezt úgy is megfogalmazhatjuk, hogy $t$ ugyanúgy benne van mind az $A$ , mind pedig a $B$ maradékosztályokban, mint $s$ .

Az $A=[s]_p$ maradékosztályba pontosan azok az egész számok tartoznak bele, amelyeket az alábbi kongruenciába az $x$ ismeretlen helyére behelyettesítve a kongruencia teljesül:

x\equiv s\pmod p

Ehhez hasonlóan a $B=[s]_q$ maradékosztályba pontosan azok az egész számok tartoznak bele, amelyeket az alábbi kongruenciába az $x$ ismeretlen helyére behelyettesítve a kongruencia teljesül:

x\equiv s\pmod q

A fentebb említett $t$ tehát $s$ -sel karöltve kielégíti az iménti két kongruenciából álló rendszert. Ám a kínai maradéktétel állítása szerint minden ilyen tulajdonságú egész szám ugyanabba az egyetlen modulo $pq$ maradékosztályba esik. Az nyilvánvaló, hogy $s\in X$ , hiszen a tétel szövege alapján ő épp az $X$ maradékosztály reprezentánseleme. Következésképp $t$ is szükségképpen $X$ -ben van, azaz valóban teljesül az $A\cap B\sube X$ tartalmazási reláció.

Mivel mindkét irányú tartalmazási reláció teljesül $X$ és $A\cap B$ között, ezért a két halmaz valóban megegyezik.

A 2. állítás: Tegyük fel indirekt, hogy létezik egy $(A;B)$ -től különböző $(C;D)$ maradékosztálypár a $\Z/p\Z\times \Z/q\Z$ halmazban, amelynek $X$ a metszete, azaz:

C\cap D=X

Tegyük fel továbbá, hogy a $C$ maradékosztályt a $c$ egész számmal, míg a $D$ maradékosztályt a $d$ egész számmal reprezentáljuk, azaz:

\begin{aligned}C&=[c]_p \\ D&=[d]_q\end{aligned}

Legyen $t$ egy tetszőleges elem az $X=[s]_{pq}$ maradékosztályban. Egyrészt a fentebb egyszer már leírt gondolatmenetet megismételve ez az alábbi kongruenciákat jelenti:

\begin{aligned}s&\equiv t\pmod p \\ s&\equiv t\pmod q\end{aligned}

Másrészt viszont az indirekt feltételezésünk miatt $X$ a $C=[c]_p$ és $D=[d]_q$ maradékosztályok metszete. Emiatt $t$ ugyanúgy benne van a $C=[c]_p$ maradékosztályban, mint $c$ , valamint ugyanúgy benne van a $D=[d]_q$ maradékosztályban, mint $d$ . Teljesülnek tehát az alábbi kongruenciák:

\begin{aligned}t&\equiv c\pmod p \\ t&\equiv d\pmod q\end{aligned}

A 20.2. Tétel 3. pontja miatt teljesülnek tehát az alábbi kongruenciák is:

\begin{aligned}s&\equiv c\pmod p \\ s&\equiv d\pmod q\end{aligned}

Azaz egyrészt az $s$ által reprezentált modulo $p$ maradékosztály – ez ugye az $A$ halmaz – megegyezik a $c$ által reprezentált modulo $p$ maradékosztállyal – ez pedig ugye a $C$ halmaz. Másrészt az $s$ által reprezentált modulo $q$ maradékosztály – ez ugye a $B$ halmaz – megegyezik a $d$ által reprezentált modulo $q$ maradékosztállyal – ez pedig ugye a $D$ halmaz.

Minthogy $A=C$ és $B=D$ , ezért indirekt feltételezésünkkel ellentétben az $(A;B)$ maradékosztálypár mégiscsak megegyezik a $(C;D)$ maradékosztálypárral. Azaz a 2. állításnak megfelelően az $(A;B)$ páron kívül nincs másik olyan maradékosztálypár a $\Z/p\Z\times \Z/q\Z$ halmazban, amelynek $X$ a metszete lenne.

Megnézem a tudásbázisban

∎

Ez azt bizonyítja, hogy a $\Z/p\Z \times \Z/q\Z$ és a $\Z/pq\Z$ halmazok közötti függvény egy kölcsönösen egyértelmű leképezés. Ha úgy tetszik egy kétirányú híd képezhető a két halmaz között. Ez azt jelenti, hogy az egyik halmazban lévő bármely elemnek egyértelműen megvan a párja a másik halmazban és viszont. A $\Z/p\Z \times \Z/q\Z$ halmazból a $\Z/pq\Z$ halmazba a 22.3. Tétel, visszafelé pedig a 22.4. Tétel biztosítja ezt a fajta átjárást.

A fentebbi példánkhoz visszatérve tehát egyrészt a $\Z/5\Z\times \Z/8\Z$ halmazban lévő $([4]_5;[6]_8)$ maradékosztálypárnak a $[14]_{40}$ maradékosztály, míg a $([4]_5;[2]_8)$ maradékosztálypárnak a $[34]_{40}$ maradékosztály a megfelelője a $\Z/40\Z$ halmazban. Másrészt pedig biztosak lehetünk benne, hogy a $[14]_{40}$ és a $[34]_{40}$ maradékosztályok csakis ezekhez a párokhoz vannak ilymódon hozzárendelve.

22.5Az RSA algoritmus helyes működésének bizonyítása

Az előző fejezetben megismertük napjaink egyik legfontosabb felfedezését, az RSA nevű aszimmetrikus kulcsú rejtjelezési eljárást. Ebben a szakaszban törlesztjük végre az adósságunkat, és igazolni fogjuk, hogy az RSA valóban mindig helyesen működik. Ezért most ismételjük át röviden, hogyan is történik a kulcsok generálása, majd az üzenetek titkosítása és dekódolása.

Az RSA biztonsága a nagy számok prímtényezős felbontásának algoritmikus nehézségén alapul. Egy kulcspár generálásához ezért először is választani kell két egymástól különböző, óriási prímszámot – jelöljük ezeket $p$ -vel és $q$ -val –, majd képezni kell ezek szorzatából az $m=pq$ modulust, és ki kell számítani az Euler-féle $\varphi$ -függvény értékét erre a modulusra. Ezután választunk egy tetszőleges $\varphi(m)$ -hez relatív prím $e$ számot a 18.3. Definíció szerinti $Z_{\varphi(m)}$ gyűrűből, amely a kulcspár publikus része lesz, és kiszámítjuk $e$ multiplikatív inverzét ebben a gyűrűben. Az így kapott $d$ szám lesz a kulcspár titkos része. A publikus és titkos kulcsok közötti számelméleti kapcsolatot tehát a $Z_{\varphi(m)}$ gyűrű jelenti, amely gyűrű ismeretlen marad a támadó számára. Ennek oka, hogy $\varphi(m)$ értéke jelenlegi számelméleti ismereteink szerint csak $m$ prímtényezőinek ismeretében számítható ki hatékonyan.

Ezután részletesen leírtuk, és egy példával szemléltettük, hogyan történik egy üzenet titkosítása az adó, és dekódolása a vételi oldalon. Ehhez az elküldeni kívánt üzenetet valamilyen szabványos módon a $Z_m$ gyűrű elemeinek sorozatává kell alakítani, majd a sorozat tagjaira külön-külön kell alkalmazni a kódoló és dekódoló függvényeket. Legyen az üzenetet leíró számsorozat következő tagja $x$ . Ennek titkosítása az alábbi $Z_m$ -beli moduláris hatványozás elvégzését jelenti:

y=x^e

Az így képzett $y$ szám nyugodtan átküldhető a kommunikációs csatornán. Ebből ugyanis csak a $d$ titkos kulcs ismeretében állítható vissza "varázslatos módon" az eredeti $x$ üzenet. Ehhez az alábbi, szintén $Z_m$ -beli moduláris hatványozást kell elvégezni:

x=y^d

Most igazolni fogjuk, hogy ez a "varázslat" tényleg mindig teljesül. Az $y$ helyére behelyettesíthetjük az őt képző, kódolófüggvény szerinti kifejezést. Ekkor az alábbit kapjuk:

x=({\underbrace{x^e}_{=y}})^d=x^{ed}

A 20.4. szakaszban láthattuk, hogy a $Z_m$ gyűrű izomorf a $\Z/m\Z$ maradékosztálygyűrűvel. Így tehát a fenti kifejezést tulajdonképpen úgy is értelmezhetjük, hogy az $x$ egész számnak ugyanabba a modulo $m$ maradékosztályba kell esnie, mint az $x^{ed}$ egész számnak. Ez az alábbi kongruencia teljesülését jelenti:

x\equiv x^{ed}\pmod m

Most igazolni fogjuk, hogy ez a kongruencia valóban teljesül tetszőleges, a megadott kritériumoknak megfelelő $e$ , $d$ , $m$ és $x$ egész számokra.

22.5. Tétel (Az RSA algoritmus helyes működése):

Tegyük fel, hogy teljesülnek az alábbi feltételek:

Választunk két tetszőleges, egymástól különböző pozitív $p$ és $q$ prímszámot.
Képezzük ezekből az $m=pq$ modulust.
Képezzük az Euler-féle $\varphi$ -függvény értékét az $m$ modulusra, azaz a 21.3. és a 21.5. Tételek alapján kiszámítjuk a $\varphi(m)=(p-1)(q-1)$ egész számot.
Választunk egy tetszőleges $e$ egész számot, amely relatív prím $\varphi(m)$ -hez.
Keresünk egy olyan $d$ egész számot, amelyre teljesül az $ed\equiv 1\pmod{\varphi(m)}$ kongruencia.

Ekkor tetszőleges $x$ egész szám esetén teljesül az alábbi kongruencia is:

x^{ed}\equiv x\pmod m

Megnézem a tudásbázisban

♣

Bizonyítás:

Mivel teljesül az $ed\equiv 1\pmod{\varphi(m)}$ kongruencia, ezért a 20.1. Tétel 3. pontja alapján teljesül az alábbi oszthatóság:

\varphi(m)|ed-1

Az oszthatóság 16.1. Definíciója alapján ekkor létezik olyan $k$ egész szám, amelyre teljesül az alábbi egyenlet:

k\varphi(m)=ed-1

Mindkét oldalhoz $1$ -et adva:

k\varphi(m) + 1=ed

Azt kell tehát bizonyítani, hogy tetszőleges $x$ esetén teljesül az alábbi kongruencia:

x^{\overbrace{k\varphi(m)+1}^{=ed}}\equiv x\pmod m

Itt két eset lehetséges. Az első – és legvalószínűbb – esetben $x$ relatív prím $m$ -hez. Ekkor közvetlenül alkalmazható az Euler-Fermat tétel. Ehhez alakítsuk át a kongruencia baloldalán álló kifejezést a 18.8. Tétel 2. és 3. pontjainak megfelelően:

(x^{\varphi(m)})^k\cdot x\equiv x\pmod m

Az Euler-Fermat tétel miatt az $x^{\varphi(m)}$ kifejezés $1$ -gyel kongruens modulo $m$ . Így a 20.2. Tétel 6. és 5. pontjai alapján a fenti kongruencia egyszerűsíthető:

\underbrace{1^k\cdot x}_{=x}\equiv x\pmod m

Ez a kongruencia viszont nyilvánvalóan teljesül a 20.2. Tétel 1. pontja alapján.

Most nézzük meg, hogy mi a helyzet abban a nem túl gyakori esetben, ha $x$ nem relatív prím az $m=pq$ modulushoz, azaz $x$ -nek és $m$ -nek van egységtől különböző közös osztója. Ekkor a $p|x$ és a $q|x$ oszthatóságok közül legalább az egyik teljesül. Ha ugyanis egyik sem teljesülne, akkor a 21.4. Lemma alapján $x$ relatív prím lenne $p$ -hez is és $q$ -hoz is, és a 20.12. Következmény miatt az $m=pq$ modulushoz is, ami ellentmondás. A $p|x$ és $q|x$ oszthatóságok tekintetében tehát az alábbi három eset lehetséges:

1. eset:

p|x

és

q|x

Ez a 20.1. Tétel 3. pontja alapján azt jelenti, hogy teljesülnek az alábbi kongruenciák:

\begin{aligned} x&\equiv 0\pmod p \\ x&\equiv 0\pmod q \end{aligned}

Ekkor a 20.2. Tétel 6. pontja alapján e kongruenciák mindkét oldalát a $k\varphi(m)+1$ -edik hatványra emelve teljesülnek az alábbi kongruenciák is:

\begin{aligned} x^{k\varphi(m)+1}&\equiv 0\pmod p \\ x^{k\varphi(m)+1}&\equiv 0\pmod q \end{aligned}

A két-két kongruenciát összevetve a 20.2. Tétel 2. és 3. pontja alapján az alábbi kongruenciákat kapjuk:

\begin{aligned} x^{k\varphi(m)+1}&\equiv x\pmod p \\ x^{k\varphi(m)+1}&\equiv x\pmod q \end{aligned}

2. eset:

p|x

és

q\nmid x

Nyilván teljesül az alábbi kongruencia, mivel $x$ többszöröse $p$ -nek, és így mindkét oldal $0$ -val kongruens modulo $p$ :

x^{k\varphi(m) +1}\equiv x\pmod p

Továbbá mivel $\varphi(m)=(p-1)(q-1)$ , ezért teljesül az alábbi – itt a második lépésben felhasználtuk a hatványozás azonosságairól szóló a 18.8. Tételt:

x^{k\varphi(m)+1}=x^{k\overbrace{(p-1)(q-1)}^{=\varphi(m)} + 1}=(x^{q-1})^{k(p-1)}\cdot x

Mivel $q\nmid x$ , ezért a 21.4. Lemma alapján $x$ relatív prím $q$ -hoz, és így alkalmazható a kis Fermat-tétel, amely szerint tehát teljesül az alábbi kongruencia:

x^{q-1}\equiv 1\pmod q

A 20.2. Tétel 6. pontja alapján mindkét oldalt a $k(p-1)$ -edik hatványra emelve, valamint a 20.2. Tétel 5. pontja alapján mindkét oldalt $x$ -szel megszorozva továbbra is érvényes kongruenciát kapunk:

(x^{q-1})^{k(p-1)}\cdot x\equiv x\pmod q

De mivel $x^{k\varphi(m)+1} = (x^{q-1})^{k(p-1)}\cdot x$ , ezért teljesül az alábbi kongruencia:

x^{k\varphi(m)+1}\equiv x\pmod q

3. eset:

p\nmid x

és

q|x

Ebben az esetben az $x$ egész szám $q$ helyett $p$ -hez lesz relatív prím, tehát az előző gondolatmenetet szinte szóról szóra meg lehet ismételni, csak $p$ és $q$ szerepét fel kell cserélni. Ekkor is azt fogjuk kapni, hogy teljesülnek az alábbi kongruenciák:

\begin{aligned} x^{k\varphi(m)+1}&\equiv x\pmod p \\ x^{k\varphi(m)+1}&\equiv x\pmod q \end{aligned}

Mivel ugye $ed=k\varphi(m)+1$ , ezért mindhárom esetben végülis azt kaptuk, hogy teljesül az alábbi két kongruencia:

\begin{aligned} x^{ed}&\equiv x\pmod p \\ x^{ed}&\equiv x\pmod q \end{aligned}

Ez a $\Z/p\Z$ és a $\Z/q\Z$ maradékosztálygyűrűkben az alábbiakat jelenti:

\begin{aligned} [x^{ed}]_p &= [x]_p \\ [x^{ed}]_q &= [x]_q \end{aligned}

Ennek megfelelően ezt így írhatjuk fel a $\Z/p\Z \times \Z/q\Z$ direkt szorzat egy elemeként:

([x^{ed}]_p; [x^{ed}]_q) = ([x]_p; [x]_q)

A 22.3. és a 22.4. Tétel alapján azonban tudjuk, hogy a $\Z/p\Z \times \Z/q\Z$ direkt szorzat elemei kölcsönösen egyértelműen megfeleltethetők a $\Z/pq\Z$ maradékosztálygyűrű elemeivel. Ez a leképezés az iménti egyenlet bal és jobboldalához a 22.4. Tételben szereplő képlet alapján az alábbi modulo $pq$ maradékosztályokat rendeli hozzá:

\begin{aligned}([x^{ed}]_p; [x^{ed}]_q) &\to [x^{ed}]_{pq} \\ ([x]_p; [x]_q) &\to [x]_{pq}\end{aligned}

Mármost ha itt a nyilak baloldalán álló objektumok megegyeznek, akkor a leképezés kölcsönösen egyértelműsége miatt a nyilak jobboldalán álló objektumok is meg kell egyezzenek, azaz:

[x^{ed}]_{pq}=[x]_{pq}

Ugyanezt kongruenciával megfogalmazva megkapjuk a tétel állítását:

x^{ed}\equiv x\pmod{\underbrace{pq}_{=m}}

Megnézem a tudásbázisban

∎

22.6Maradékosztálygyűrűk dekompozíciója

Az RSA algoritmussal főként az a probléma, hogy szimmetrikus kulcsú társaihoz képest relatíve lassú. Ezt elsősorban a moduláris hatványozás okozza. Ez némileg ellentmond annak, amit a 21.4. szakaszban állapítottunk meg erről a műveletről. Akkor ugyanis azt mondtuk, hogy az ismételt négyzetreemelések módszerével rendkívül gyorsan elvégezhető a moduláris hatványozás. Ez algoritmuselméleti értelemben valóban így van, hiszen láttuk, hogy az elvégzendő moduláris szorzások száma legfeljebb a kitevő bináris számjegyei számának a kétszerese lehet. Márpedig egy ilyen jellegű skálázódás a 7. fejezetben leírtak fényében bőven hatékony algoritmusnak tekinthető.

Igenám, csakhogy hiába a megfelelő skálázódás, amennyiben eleve nagyméretű bemenetekről van szó. A gyakorlatban ugyanis több ezer bites számokon kell több ezer moduláris szorzást elvégezni. Az ismételt négyzetreemelések módszerét vizsgálva megállapítottuk, hogy a szükséges moduláris szorzások száma attól függ, hogy a kitevő bináris számábrázolásában hány $1$ -es bit szerepel. Az RSA esetén a publikus kulcsban szereplő, kódoláshoz használt $e$ kitevő megválasztásától nem függ az eljárás biztonsága. Emiatt általában olyan publikus $e$ kitevőt választanak a kulcsgeneráláskor, amelyben minimális számú $1$ -es számjegy van. Célszerű például valamilyen $2$ -hatványnál $1$ -gyel nagyobb számot választani, hiszen ebben az esetben csak az első és az utolsó számjegy nem $0$ . Következésképp a kódoláskor elvégzendő moduláris hatványozás mindössze egy-két moduláris szorzásból megúszható.

A probléma érezhetően a dekódoláskor, vagy digitális aláírások képzésekor jön elő, amikor is a titkos $d$ kitevőt kell használni. Ez ugyanis az $e$ publikus kitevő multiplikatív inverze a 18.3. Definíció szerinti $Z_{\varphi(m)}$ gyűrűben. Itt $m$ ugye a kulcsgeneráláskor véletlenszerűen választott $p$ és $q$ prímszámok szorzata. Mivel emiatt a $\varphi(m)$ is gyakorlatilag véletlenszerű lesz, ezért nemigazán lehet szabályozni, hogy a $Z_{\varphi(m)}$ gyűrűben az $e$ multiplikatív inverzének éppenséggel milyen számjegyei lesznek. Emiatt pedig a fogadó oldal által elvégzendő RSA dekódolás általában sokkal lassabb művelet, mint a küldő által elvégzett kódolás.

Ezért most a kínai maradéktétel egy nagyon praktikus alkalmazását mutatjuk be, amelynek a segítségével Alice és Bob a nekik küldött üzenetek dekódolását a 21.9. szakaszban leírtakhoz képest sokkal gyorsabban is el tudja végezni. Ehhez a kulcspár generálásakor választott titkos $p$ és $q$ prímszámokat is fel kell használni, így ezt a módszert csak a titkos kulcs birtokában lehet alkalmazni. Az eljárásban kulcsszerepe lesz a már sokat emlegetett $\Z/p\Z \times \Z/q\Z$ halmaznak.

Most e halmaz elemei között fogunk két műveletet értelmezni. Az egyiket "összeadásnak", a másikat pedig "szorzásnak" fogjuk nevezni, és rendre a $\oplus$ és a $\odot$ szimbólumokkal fogjuk őket jelölni. A $\Z/p\Z \times \Z/q\Z$ halmaz elemei ugye olyan maradékosztálypárok, amelyeknek első komponense egy modulo $p$ maradékosztály, második komponense pedig egy modulo $q$ maradékosztály. Adja magát a kérdés, hogy vajon mi legyen két ilyen maradékosztálypár "összege" és "szorzata":

\begin{aligned}(A;B)\oplus (C;D)&=\text{???} \\ (A;B)\odot (C;D)&=\text{???}\end{aligned}

Az ötletet a 22.4. szakaszban már említett síkbeli pontok derékszögű koordinátáit leíró számpárok adhatják. Amennyiben a koordinátarendszer kezdőpontjából egy $(a;b)$ számpárral megadott pontba képzeletben egy "nyilacskát" rajzolunk, akkor mondhatjuk azt is, hogy az $(a;b)$ számpár tulajdonképpen ezt a "nyilacskát", vagy tudományosabb nevén vektort reprezentálja. E vektorok között az alábbi kézenfekvő módon értelmezhető az "összeadás" művelete: két vektor "összege" legyen az a vektor, amelynek koordinátáit úgy kapjuk, hogy az eredeti két vektor megfelelő koordinátáit egymással összeadjuk a szokásos értelemben. Azaz:

(a;b)\oplus (c;d)=(a+c;b+d)

Eszerint tehát a két vektor "összege" épp abba a pontba mutat, amelybe úgy juthatunk el, hogy az egyik vektor végpontjába toljuk a másik vektor kezdőpontját, majd a koordinátarendszer kezdőpontjából végigmegyünk az így kijelölt útvonalon.

Visszatérve a $\Z/p\Z \times \Z/q\Z$ halmazhoz adja magát az ötlet, hogy ezen a halmazon is hasonlóképpen, azaz "koordinátánkénti" műveletvégzésként definiáljuk a két kérdéses műveletet. Nevezetesen:

\begin{aligned}(A;B)\oplus (C;D)&=(A+C;B+D) \\ (A;B)\odot (C;D)&=(A\cdot C;B\cdot D)\end{aligned}

A vektorok között definiált "összeadáshoz" képest itt mindössze annyi a különbség, hogy az egyes "koordináták" nem feltétlenül azonos gyűrűkből származnak. Például jelen esetben az eredmény első "koordinátáját" adó $A+C$ összeadást a modulo $p$ maradékosztálygyűrűben, míg a második "koordinátát" adó $B+D$ összeadást a modulo $q$ maradékosztálygyűrűben kell elvégezni. A "szorzásra" természetesen ugyanez vonatkozik.

Ezután minden bizonnyal nem lesz túl meglepő, hogy a $\Z/p\Z \times \Z/q\Z$ halmaz az imént értelmezett $\oplus$ és $\odot$ műveletekkel egy gyűrűt alkot. Az alábbi tételben ezt ennél általánosabban igazoljuk.

22.6. Tétel (Gyűrűk direkt szorzata):

Legyenek $R_1$ , $R_2$ , ..., $R_n$ tetszőleges gyűrűk, és értelmezzünk két műveletet az $R_1\times R_2\times \ldots \times R_n$ halmaz tetszőleges $(a_1;a_2;\ldots;a_n)$ és $(b_1;b_2;\ldots;b_n)$ elemei között az alábbi módon:

\begin{aligned} (a_1;a_2;\ldots;a_n)\oplus (b_1;b_2;\ldots;b_n)&=(a_1+b_1;a_2+b_2;\ldots;a_n+b_n) \\ (a_1;a_2;\ldots;a_n)\odot (b_1;b_2;\ldots;b_n)&=(a_1\cdot b_1;a_2\cdot b_2;\ldots;a_n\cdot b_n) \end{aligned}

A $\oplus$ illetve a $\odot$ műveleteket tehát úgy kell elvégezni, hogy az azonos pozícióban lévő komponensek összegeit illetve szorzatait képezzük a megfelelő gyűrűkben.

Ekkor az $R_1\times R_2\times \ldots \times R_n$ halmaz szintén egy gyűrűt alkot ezzel a két művelettel. Ezt a gyűrűt az $R_1$ , $R_2$ , ..., $R_n$ gyűrűk direkt szorzatának, vagy szorzatgyűrűjének nevezzük. E szorzatgyűrű nulleleme egy olyan rendezett $n$ -es, amelynek minden komponensében a megfelelő gyűrű nulleleme áll. Azaz:

0_{R_1\times R_2\times \ldots \times R_n}=(0_{R_1};0_{R_2};\ldots;0_{R_n})

A szorzatgyűrű egy tetszőleges $(a_1;a_2;\ldots;a_n)$ elemének $\ominus (a_1;a_2;\ldots;a_n)$ -nel jelölt ellentettjét úgy kapjuk meg, hogy vesszük minden komponens ellentettjét a megfelelő gyűrűben. Azaz:

\ominus (a_1;a_2;\ldots;a_n)=(-a_1;-a_2;\ldots;-a_n)

Megnézem a tudásbázisban

♣

Bizonyítás:

A 14.12. Definícióban felsorolt gyűrűaxiómákat kell ellenőrizni. A $\oplus$ művelet kommutativitása könnyedén adódik az $R_1$ , $R_2$ , ..., $R_n$ gyűrűkön értelmezett összeadások ugyanezen tulajdonságából:

\begin{aligned} (&a_1;\ldots;a_n)\oplus(b_1;\ldots;b_n)= \\ &= (a_1+b_1;\ldots;a_n+b_n)= \\ &=(b_1+a_1;\ldots;b_n+a_n)= \\ &= (b_1;\ldots;b_n) \oplus (a_1;\ldots;a_n) \end{aligned}

Hasonlóképpen adódik a $\oplus$ művelet asszociativitása:

\begin{aligned}((&a_1;\ldots;a_n)\oplus(b_1;\ldots;b_n))\oplus(c_1;\ldots;c_n) =\\&= (a_1+b_1;\ldots;a_n+b_n)\oplus(c_1;\ldots;c_n) =\\&=((a_1+b_1)+c_1;\ldots;(a_n+b_n)+c_n) =\\&= (a_1+(b_1+c_1);\ldots;a_n+(b_n+c_n)) =\\&=(a_1;\ldots;a_n)\oplus(b_1+c_1;\ldots;b_n+c_n)=\\&=(a_1;\ldots;a_n)\oplus((b_1;\ldots;b_n)\oplus(c_1;\ldots;c_n))\end{aligned}

És a $\odot$ művelet asszociativitása is:

\begin{aligned}((&a_1;\ldots;a_n)\odot(b_1;\ldots;b_n))\odot(c_1;\ldots;c_n) =\\&= (a_1\cdot b_1;\ldots;a_n\cdot b_n)\odot(c_1;\ldots;c_n) =\\&=((a_1\cdot b_1)\cdot c_1;\ldots;(a_n\cdot b_n)\cdot c_n) =\\&= (a_1\cdot (b_1\cdot c_1);\ldots;a_n\cdot (b_n\cdot c_n)) =\\&=(a_1;\ldots;a_n)\odot(b_1\cdot c_1;\ldots;b_n\cdot c_n)=\\&=(a_1;\ldots;a_n)\odot((b_1;\ldots;b_n)\odot(c_1;\ldots;c_n))\end{aligned}

Továbbá a két művelet közötti mindkét oldali disztributivitás is könnyen látszik. Nézzük először a baloldali disztributivitást, a jobboldali disztributivitás ugyanígy igazolható:

\begin{aligned}(&a_1;\ldots;a_n)\odot((b_1;\ldots;b_n)\oplus(c_1;\ldots;c_n))=\\&=(a_1;\ldots;a_n)\odot (b_1+c_1;\ldots;b_n+c_n)=\\&=(a_1\cdot(b_1+c_1);\ldots;a_n\cdot (b_n+c_n))=\\&=(a_1b_1+a_1c_1;\ldots;a_nb_n+a_nc_n)=\\&=(a_1b_1;\ldots;a_nb_n)\oplus (a_1c_1;\ldots;a_nc_n)=\\&=((a_1;\ldots;a_n)\odot (b_1;\ldots;b_n))\oplus ((a_1;\ldots;a_n)\odot (c_1;\ldots;c_n))\end{aligned}

Végül igazoljuk a nullelemre és az ellentettképzésre vonatkozó állításokat. Legyen $(a_1;\ldots;a_n)$ az $R_1\times \ldots \times R_n$ halmaz egy tetszőleges eleme. Ezt a $(0_{R_1};\ldots;0_{R_n})$ elemmel összeadva az eredmény valóban nem változik, hiszen minden komponensben a megfelelő gyűrű nullelemével való összeadás fog szerepelni:

\begin{aligned}(&a_1;\ldots;a_n)\oplus(0_{R_1};\ldots;0_{R_n})=\\&=(a_1+0_{R_1};\ldots;a_n+0_{R_n})=\\&=(a_1;\ldots;a_n)\end{aligned}

Ehhez hasonlóan az $(a_1;\ldots;a_n)$ elemet a $(-a_1;\ldots;-a_n)$ elemmel összeadva az eredmény valóban a $(0_{R_1};\ldots;0_{R_n})$ elem lesz, hiszen minden komponensben az adott komponens és annak a megfelelő gyűrűben vett ellentettjének összege fog szerepelni:

\begin{aligned}(&a_1;\ldots;a_n)\oplus(-a_1;\ldots;-a_n)=\\&=(a_1-a_1;\ldots;a_n-a_n)=\\&=(0_{R_1};\ldots;0_{R_n})\end{aligned}

Megnézem a tudásbázisban

∎

E tételből következően a $\Z/p\Z \times \Z/q\Z$ halmaz a komponensenkénti moduláris összeadásra és moduláris szorzásra nézve valóban egy gyűrűt alkot. Például a 22.4. szakaszban szereplő $([4]_5;[6]_8)$ és $([4]_5;[2]_8)$ maradékosztálypárok ilyen értelemben vett "összegét" és "szorzatát" az alábbiak szerint kapjuk meg:

\begin{aligned}([4]_5;[6]_8)\oplus ([4]_5;[2]_8) &= ([4]_5+[4]_5; [6]_8+[2]_8) = ([3]_5; [0]_8) \\ ([4]_5;[6]_8)\odot ([4]_5;[2]_8) &= ([4]_5\cdot [4]_5; [6]_8\cdot [2]_8) = ([1]_5; [4]_8) \end{aligned}

A szakasz elején említett RSA dekódolást gyorsító eljárás működésének a kulcsa az a tény, hogy szoros kapcsolat áll fenn a $\Z/p\Z \times \Z/q\Z$ és a $\Z/pq\Z$ gyűrűk között. Olyannyira szoros, hogy az alábbi tétel szerint lényegében ugyanannak a gyűrűnek csupán két megjelenési formájáról van szó.

22.7. Tétel (Maradékosztálygyűrűk dekompozíciója):

Legyenek $p\gt 0$ és $q\gt 0$ valamilyen egymáshoz relatív prím pozitív egész számok. Ekkor a 22.6. Tétel szerint értelmezett $\Z/p\Z \times \Z/q\Z$ szorzatgyűrű izomorf a $\Z/pq\Z$ maradékosztálygyűrűvel, azaz:

\Z/p\Z \times \Z/q\Z\simeq \Z/pq\Z

Legyenek $a$ , $b$ és $c$ tetszőleges egész számok, továbbá tegyük fel, hogy az $x_1$ és $x_2$ egész számok kielégítik az alábbi kongruenciákat:

\begin{aligned} px_1&\equiv 1\pmod q \\ qx_2&\equiv 1\pmod p \end{aligned}

Ekkor az alábbi $f:\Z/p\Z \times \Z/q\Z \to \Z/pq\Z$ és $g:\Z/pq\Z \to \Z/p\Z \times \Z/q\Z$ leképezések épp egymás megfordításai, továbbá mindketten gyűrűizomorfizmusok a két gyűrű között:

\begin{aligned} f(([a]_p;[b]_q))&=[aqx_2 + bpx_1]_{pq} \\ g([c]_{pq})&=([c]_p;[c]_q) \end{aligned}

Megnézem a tudásbázisban

♣

Bizonyítás:

Az $f$ függvényről a 22.3. Tételben igazoltuk, hogy minden $\Z/p\Z \times \Z/q\Z$ -beli rendezett párhoz pontosan egy $\Z/pq\Z$ -beli maradékosztályt rendel hozzá. Méghozzá azt a maradékosztályt, amely a rendezett pár két komponensének a metszete. A 22.4. Tételben pedig azt mutattuk meg, hogy ilymódon minden $\Z/pq\Z$ -beli maradékosztály pontosan egy $\Z/p\Z \times \Z/q\Z$ -beli rendezett párhoz lehet hozzárendelve, amelyet ráadásul épp a $g$ függvény segítségével kaphatunk meg.

Az f és g függvények egymáshoz való viszonya — **22.4. ábra:** Az $f$ és $g$ függvények egymáshoz való viszonya

Így már csak azt kell igazolni, hogy az $f$ és $g$ függvények rendelkeznek-e a 18.6. Definíció szerinti művelettartó tulajdonsággal. Annak érdekében, hogy világos legyen, melyik műveletet melyik gyűrűben kell elvégezni, a $\Z/pq\Z$ maradékosztálygyűrű összeadását és szorzását a $\boxplus$ és $\boxdot$ , míg a $\Z/p\Z \times \Z/q\Z$ gyűrű összeadását és szorzását a $\oplus$ és $\odot$ szimbólumokkal fogjuk jelölni.

Ezeket a jelöléseket bevezetve tehát azt kell igazolni, hogy tetszőleges $a$ , $b$ , $c$ és $d$ egész számokra teljesülnek az alábbiak:

\begin{aligned} f(([a]_p;[b]_q) \oplus ([c]_p;[d]_q)) &= f(([a]_p;[b]_q))\boxplus f(([c]_p;[d]_q)) \\ f(([a]_p;[b]_q) \odot ([c]_p;[d]_q)) &= f(([a]_p;[b]_q))\boxdot f(([c]_p;[d]_q)) \\ g([a]_{pq} \boxplus [b]_{pq}) &= g([a]_{pq})\oplus g([b]_{pq}) \\ g([a]_{pq} \boxdot [b]_{pq}) &= g([a]_{pq})\odot g([b]_{pq}) \end{aligned}

Kezdjük a $g$ függvénnyel. Az erre vonatkozó két állítás baloldalait a 20.5. Tétel és a $g$ függvény képletének felhasználásával az alábbi módon lehet kifejteni – itt a $+$ és $\cdot$ szimbólumok a szokásos egészek közötti összeadást és szorzást jelölik:

\begin{aligned} g([a]_{pq} \boxplus [b]_{pq}) &= g([a+b]_{pq})=([a+b]_p;[a+b]_q) \\ g([a]_{pq} \boxdot [b]_{pq}) &= g([a\cdot b]_{pq})=([a\cdot b]_p;[a\cdot b]_q) \end{aligned}

Míg a jobboldalakból ezt kapjuk:

\begin{aligned} g([a]_{pq})\oplus g([b]_{pq}) &= ([a]_p;[a]_q)\oplus ([b]_p;[b]_q) \\ g([a]_{pq})\odot g([b]_{pq}) &= ([a]_p;[a]_q)\odot ([b]_p;[b]_q) \end{aligned}

A 22.6. Tétel alapján a kapott rendezett párokat komponensenként kell összeadni illetve összeszorozni. Az első komponenshez szükséges műveleteket a modulo $p$ maradékosztálygyűrűben, míg a második komponenshez szükséges műveleteket a modulo $q$ maradékosztálygyűrűben kell elvégezni. Ismételten a 20.5. Tétel felhasználásával így az alábbit kapjuk:

\begin{aligned}g([a]_{pq})\oplus g([b]_{pq}) &= ([a+b]_p;[a+b]_q) \\ g([a]_{pq})\odot g([b]_{pq}) &= ([a\cdot b]_p;[a\cdot b]_q)\end{aligned}

A $g$ -re vonatkozó két állítás bal- és jobboldalai tehát megegyeznek, azaz a $g$ függvény tartja mindkét műveletet, így ő egy gyűrűizomorfizmus $\Z/pq\Z$ és $\Z/p\Z \times \Z/q\Z$ között.

Mivel az $f$ függvény a $g$ függvény megfordítása, ezért a 18.6. Definíció utáni megjegyzés 2. pontja alapján ő is egy gyűrűizomorfizmus a két gyűrű között, csak épp a másik irányba képez.

Megnézem a tudásbázisban

∎

Tekintsük ismét példaként a már sokat emlegetett $([4]_5;[6]_8)$ és $([4]_5;[2]_8)$ maradékosztálypárokat a $\Z/5\Z\times \Z/8\Z$ gyűrűben. Ezek összege és szorzata ebben a gyűrűben az alábbiak voltak:

\begin{aligned} ([4]_5;[6]_8)\oplus ([4]_5;[2]_8) &= ([3]_5; [0]_8) \\ ([4]_5;[6]_8)\odot ([4]_5;[2]_8) &= ([1]_5; [4]_8) \end{aligned}

A 22.4. szakaszban már láttuk, hogy az imént tanult gyűrűizomorfizmusok – és persze az ezek hátterében lévő kínai maradéktétel – alapján az ő párjaik a $\Z/40\Z$ gyűrűben rendre a $[14]_{40}$ és a $[34]_{40}$ maradékosztályok. Most nézzük meg ezek összegét és szorzatát a $\Z/40\Z$ gyűrűben:

\begin{aligned}[14]_{40}\boxplus [34]_{40} &= [48]_{40}=[8]_{40} \\ [14]_{40}\boxdot [34]_{40} &= [476]_{40}=[36]_{40}\end{aligned}

Valóban, a 22.7. Tételben szereplő $g$ gyűrűizomorfizmus a $[8]_{40}$ maradékosztályhoz a $([8]_5;[8]_8)=([3]_5;[0]_8)$ , míg a $[36]_{40}$ maradékosztályhoz a $([36]_5;[36]_8)=([1]_5;[4]_8)$ maradékosztálypárt rendeli hozzá. Azaz tényleg egy művelettartó leképezésről van szó a $\Z/40\Z$ és a $\Z/5\Z \times \Z/8\Z$ gyűrűk között.

Tulajdonképpen az történt, hogy a $\Z/40\Z$ gyűrűt felbontottuk két kisebb gyűrű direkt szorzatára. A két algebrai struktúra izomorfiája miatt bármelyikben elvégezhetjük a szükséges számításokat, és az egyikben kapott eredményt könnyedén áttranszformálhatjuk a másik struktúrába a gyűrűizomorfizmusok segítségével. Most megvizsgáljuk, hogy mégis miért jó ez Alice és Bob számára.

22.7Az RSA dekódolás gyorsítása

Térjünk most vissza a 21. fejezetben bemutatott példára, amikoris Alice az RSA algoritmussal rejtjelezett sziabobmiahelyzet# üzenetet küldte el Bob-nak. Bob a kulcsgenerálás során a $p=211$ és $q=139$ prímszámokat választotta, és ezek segítségével előállította az $m=29329$ modulust, az $e=187$ publikus, valamint a $d=11623$ titkos kitevőt.

Alice a példában leírt módon a 18.3. Definíció szerinti $Z_{29329}$ gyűrű elemeinek sorozatává alakította az elküldendő üzenetet, melyek közül az első az $x_1=9620$ volt. Ebből a rejtjelezett számsorozat első tagja a $Z_{29329}$ gyűrűben végrehajtott alábbi moduláris hatványozás eredményeként állt elő:

Z_{29329} \text{: } 9620^{187}=7812=y_1

Bob ebből a $d=11623$ kitevő segítségével az alábbi, szintén a $Z_{29329}$ gyűrű végrehajtott moduláris hatványozással kaphatja vissza az eredeti $x_1$ számot:

Z_{29329} \text{: } 7812^{11623}=9620=x_1

A 20.4. szakaszban az egész számok maradékosztályai kapcsán szó volt róla, hogy a gyűrűk homomorfizmustétele miatt tetszőleges $m\gt 0$ pozitív egész szám esetén a $Z_m$ gyűrű izomorf a $\Z/m\Z$ maradékosztálygyűrűvel. Következésképp a maradékosztálygyűrűk dekompozíciójáról szóló 22.7. Tétel miatt a $Z_p \times Z_q$ szorzatgyűrű is izomorf a $Z_{pq}=Z_m$ gyűrűvel.

Emiatt Bob a $p$ és $q$ prímszámok ismeretében megteheti, hogy a dekódoláskor elvégzendő moduláris hatványozást a $Z_m$ gyűrű helyett a $Z_p \times Z_q$ szorzatgyűrűben végzi el, majd az eredményt visszatranszformálja a $Z_m$ gyűrűbe. Kérdezhetnénk, hogy ez miért jó neki, amikor így egy helyett gyakorlatilag két moduláris hatványozást kell elvégeznie? Igenám, csakhogy ezeknél már nem $m$ , hanem a nagyságrendileg feleannyi számjegyből álló $p$ és $q$ lesz a modulus. A moduláris hatványozás sebessége pedig a kitevő méretén kívül erőteljesen függ a modulus méretétől is. Ráadásul a modulus méretét megfelezve a moduláris hatványozás futásideje kevesebb mint a felére csökken. Így két feleakkora modulussal elvégzett hatványozás összességében hatékonyabb, mintha csak egyet végeznénk el ugyan, de az eredeti modulussal.

A fenti példában ez azt jelenti, hogy megérkezik Bob-hoz az $y_1=7812$ rejtjelezett szám, amely ugye a $Z_{29329}$ gyűrű egy eleme. Ezt Bob a 22.7. Tételben megadott $g$ gyűrűizomorfizmus segítségével áttranszformálja a $Z_{211}\times Z_{139}$ szorzatgyűrűbe, azaz veszi a két prímmel való osztási maradékát:

g(7812)=(5; 28)

Ezután elvégzi a dekódolást ebben a szorzatgyűrűben, azaz kiszámítja az alábbi két moduláris hatványt:

\begin{aligned}Z_{211} &\text{: } 5^{11623} \\ Z_{139} &\text{: } 28^{11623}\end{aligned}

Itt tehát az első moduláris hatványozást a $Z_{211}$ , míg a másodikat a $Z_{139}$ gyűrűben kell végrehajtani. Ez hatékonyabban végrehajtható, mintha csak a $7812^{11623}$ moduláris hatványozást hajtanánk végre ugyan, viszont a jóval nagyobb modulusú $Z_{29329}$ gyűrűben. A 21.4. szakaszban megismert ismételt négyzetreemelések módszerével Bob az alábbi eredményt kapja:

\begin{aligned}Z_{211} &\text{: } 5^{11623}=125 \\ Z_{139} &\text{: } 28^{11623}=29\end{aligned}

A kapott rendezett pár tehát a $(125;29)$ . Ahhoz, hogy Bob ebből megkapja az Alice által küldött eredeti $x_1$ üzenetet, vissza kell transzformálja ezt a $Z_{211}\times Z_{139}$ -beli elemet a $Z_{29329}$ gyűrűbe. Ezt a 22.7. Tételben megadott $f$ gyűrűizomorfizmussal teheti meg:

f((125;29))=9620=x_1

A kapott $x_1=9620$ eredmény helyességét könnyen leellenőrizhetjük. Ha ugyanis alkalmazzuk rá az említett tételben szereplő $g$ függvényt, akkor vissza kell kapnunk a $(125;29)$ rendezett párt, hiszen a $g$ függvény épp az $f$ függvény megfordítása. Valóban: a $9620$ egész számnak a $p=211$ -gyel való osztási maradéka $125$ , míg a $q=139$ -cel való osztási maradéka $29$ . Vagyis a $(125;29)$ valóban az $x_1=9620$ üzenet párja a két gyűrű közötti gyűrűizomorfizmus szerint.

Végezetül a kis Fermat-tétel egy egyszerű következményét ismertetjük, aminek a segítségével Alice és Bob nemcsak a dekódolás során használt modulus, hanem a $d$ titkos kitevő méretét is jelentősen képes lecsökkenteni.

22.8. Következmény:

Legyen $d\gt 0$ egy tetszőleges pozitív egész szám, $p\gt 0$ pedig egy tetszőleges pozitív prímszám. Tegyük fel továbbá, hogy $d_p$ egy olyan egész szám, amelyre teljesül az alábbi kongruencia:

d_p\equiv d\pmod{p-1}

Ekkor minden $y$ egész szám esetén teljesül az alábbi kongruencia is:

y^d\equiv y^{d_p}\pmod{p}

Megnézem a tudásbázisban

♣

Bizonyítás:

A $d_p\equiv d\pmod{p-1}$ kongruencia a 20.1. Tétel 3. pontja alapján az alábbi oszthatóság teljesülését jelenti:

p-1|d_p-d

Ez az oszthatóság a 16.1. Definíció alapján azt jelenti, hogy létezik olyan $k$ egész szám, amelyre teljesül az alábbi egyenlet:

k(p-1)=d_p-d

Az egyenlet mindkét oldalához $d$ -t adva az alábbi kifejezést kapjuk $d_p$ -re:

d_p=k(p-1)+d

Ez alapján az $y^d\equiv y^{d_p}\pmod p$ kongruencia így írható fel:

y^d\equiv y^{\overbrace{k(p-1)+d}^{=d_p}}\pmod p

Ez a hatványozás azonosságairól szóló 18.8. Tétel 2. és 3. pontjai alapján az alábbi alakra hozható:

y^d\equiv (y^{p-1})^k \cdot y^d\pmod p

Amennyiben $y$ relatív prím $p$ -hez, akkor alkalmazható a kis Fermat-tétel, amely alapján a fenti kongruencia jobboldalán szereplő $y^{p-1}$ tényező $1$ -gyel kongruens modulo $p$ :

y^d\equiv 1^k \cdot y^d\pmod p

Így tehát a kongruencia jobboldala a 20.2. Tétel 4. és 6. pontja alapján valóban $y^d$ -vel kongruens modulo $p$ .

Amennyiben $y$ nem relatív prím $p$ -hez, akkor a 21.4. Lemma alapján teljesül a $p|y$ oszthatóság. Ilyenkor tehát ugyancsak teljesül a fenti kongruencia, hiszen mindkét oldal $0$ -val kongruens modulo $p$ .

Megnézem a tudásbázisban

∎

A fenti példánál maradva Bob-nak tehát a dekódoláshoz végre kéne hajtania az alábbi moduláris hatványozásokat a $Z_{211}$ és a $Z_{139}$ gyűrűben:

\begin{aligned}Z_{211} &\text{: } 5^{11623}=125 \\ Z_{139} &\text{: } 28^{11623}=29\end{aligned}

Az imént bizonyított 22.8. Következmény alapján ezen a ponton megteheti, hogy veszi a $d=11623$ kitevő $p-1=210$ -zel és $q-1=138$ -cal való osztási maradékait, és $d$ helyett ezeket az osztási maradékokat használja kitevőként. Jelöljük az így kapott új kitevőket $d_p$ -vel és $d_q$ -val. Jelen esetben ezek az alábbiak lesznek:

\begin{aligned}d_p&=\bmod_{210}(11623)=73 \\ d_q&=\bmod_{138}(11623)=31\end{aligned}

A moduláris hatványozásokat ezekkel az eredeti $d$ -nél jóval kisebb kitevőkkel elvégezve valóban ugyanazt az eredményt kapjuk:

\begin{aligned}Z_{211} &\text{: } 5^{73}=125 \\ Z_{139} &\text{: } 28^{31}=29\end{aligned}

Ráadásul a $d_p$ és $d_q$ kitevők csak a választott $p$ és $q$ prímszámoktól függenek, azaz Alice és Bob megteheti, hogy már a kulcsgenerálás során előállítják ezeket.

Összességében a $Z_p \times Z_q$ szorzatgyűrű, valamint a redukált $d_p$ és $d_q$ titkos kitevők használatával az RSA dekódolást nagyjából négyszer hatékonyabban el tudják végezni, mintha az eredeti $Z_m$ gyűrűt és az eredeti $d$ titkos kitevőt használnák. Megtehetik továbbá, hogy az RSA eljárást alapvetően csak arra használják, hogy egy közös titokban állapodjanak meg, amelyet aztán egy valamilyen sokkal hatékonyabb, szimmetrikus kulcsú rejtjelező kulcsaként használhatnak a kommunikáció további részéhez.

Ebben a fejezetben tehát megismerkedtünk a kis Fermat-tétellel és a több kongruenciából álló kongruenciarendszerek egyértelmű megoldhatóságát biztosító kínai maradéktétellel. Ezek segítségével igazoltuk, hogy az RSA algoritmus valóban mindig helyesen működik. Ezután megismerkedtünk egy olyan konstrukcióval, amelynek a segítségével kettő vagy több gyűrűből egy újabb gyűrűt tudunk létrehozni azok direkt szorzataként. A kínai maradéktétel következményeként megmutattuk, hogy ezen a módon bármely összetett modulusú maradékosztálygyűrű felbontható egymáshoz relatív prím modulusú maradékosztálygyűrűk direkt szorzatára, amely ráadásul izomorf lesz az eredeti gyűrűvel. Ezt és a kis Fermat-tétel egy következményét kihasználva Alice és Bob jelentősen gyorsítani tudja az RSA dekódolási eljárást.

A következő fejezetben megtudjuk, hogy hogyan lehet az RSA kulcsokhoz szükséges óriási prímszámokat találni anélkül, hogy az idők végezetéig osztáspróbákat kelljen végezni. Ezenkívül megismerkedünk néhány olyan módszerrel, amellyel a gonosz Eve képes feltörni az RSA algoritmust, amennyiben Alice és Bob nem kellő körültekintéssel jár el a kulcsgenerálás során.

22.1A kis Fermat-tétel

22.1. Tétel (A kis Fermat-tétel):

Bizonyítás:

Megjegyzés:

22.2Kongruenciarendszerek

22.3A kínai maradéktétel

22.2. Tétel (Kínai maradéktétel):

Bizonyítás:

22.4Kongruenciarendszerek megoldása

22.3. Tétel (A kínai maradéktétel alternatív megfogalmazása):

Bizonyítás:

Megjegyzés:

22.4. Tétel (A kínai maradéktétel megfordítása):

Bizonyítás:

22.5Az RSA algoritmus helyes működésének bizonyítása

22.5. Tétel (Az RSA algoritmus helyes működése):

Bizonyítás:

22.6Maradékosztálygyűrűk dekompozíciója

22.6. Tétel (Gyűrűk direkt szorzata):

Bizonyítás:

22.7. Tétel (Maradékosztálygyűrűk dekompozíciója):

Bizonyítás:

22.7Az RSA dekódolás gyorsítása

22.8. Következmény:

Bizonyítás:

Iratkozz fel a hírlevelünkre