Episode I

Alice és Bob

23. fejezet

Alice és Bob prímszámok után nyomoz

Az előző fejezetben igazoltuk, hogy az RSA rejtjelezési eljárás valóban minden esetben helyesen működik. Ezt alapvetően két fontos számelméleti összefüggés biztosította számunkra. Az első a kis Fermat-tétel, amely a 20.7. szakaszban ismertetett Euler-Fermat tétel következménye a prímekre nézve. A másik összefüggés pedig a 22.3. szakaszban szereplő kínai maradéktétel, amely az úgynevezett kongruenciarendszerek megoldhatóságával, illetve a megoldások számával volt kapcsolatos. Végül egyrészt ennek következményeként egy – egyébként a számelmélet más területein is – rendkívül fontos gyűrűizomorfizmussal, másrészt a kis Fermat-tétel egy egyszerű következményével ismerkedtünk meg, amelyek együtt lehetővé teszik a kommunikáló felek számára az RSA dekódolás felgyorsítását.

De vajon hogyan képes Alice és Bob az RSA kulcsgeneráláshoz szükséges többszázjegyű prímszámokat találni? Hogyan tudják ezt megtenni anélkül, hogy az idők végezetéig osztáspróbákat kellene végezniük? Mik azok a prímtesztek, és pontosan hogyan működnek? Mely számokat nevezzük univerzális álprímeknek, és hogyan tudunk megszabadulni tőlük? Ebben a fejezetben erről lesz szó...

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

Alice és Bob tehát ott ülnek az RSA algoritmus 21. fejezetben ismertetett leírása felett, és mindketten szeretnének maguknak egy-egy kulcspárt generálni. Ezután ezek publikus részeit megosztják majd egymással, és indulhat a biztonságos kommunikáció, azaz mindenki boldog. Igenám, csakhogy a kulcsgenerálási eljárás első lépéseként először is mindkettejüknek kellene találnia két-két többszázjegyű prímszámot. Azt a 16.14. és a 17.12. Tétel következményeként tudják, hogy az egész számok $\Z$ gyűrűjében a prímek és felbonthatatlan elemek köre éppenséggel egybeesik. Emiatt a továbbiakban ezt a két – egyébként teljesen különböző – gyűrűelméleti fogalmat egymás szinonímájaként fogjuk használni az egész számok kontextusában.

A prímszámok keresése szempontjából lényeges kérdés, hogy azok mennyire gyakran fordulnak elő ebben a számtartományban. Az úgynevezett prímszámláló függvény egy olyan függvény, amely azt adja meg bármilyen $n$ pozitív egészre, hogy mennyi az $n$ -nél nemnagyobb pozitív prímek száma. Ezt a függvényt $\pi$ -vel jelöljük. Az alábbiakban a prímszámláló függvény értékét láthatjuk néhány pozitív egész számra:

\begin{aligned}\pi(1)&=0 \\ \pi(2)&=1 \\ \pi(3)&=2 \\ \pi(3)&=2 \\ \pi(10)&=4 \\ \pi(100)&=25 \\ \pi(1000000)&=78498 \\ &\vdots \end{aligned}

Sajnos a prímszámláló függvényre nincs képletünk, amelybe tetszőleges pozitív egész számot behelyettesítve varázslatos módon megkaphatnánk az értékét. Azonban az úgynevezett analitikus számelmélet egy nevezetes tétele szerint ez az érték viszonylag jól becsülhető egy másik, könnyen kiszámítható függvénnyel. Ez "nagy prímszámtétel" néven ismeretes, amelynek részleteire ebben a cikksorozatban nem térünk ki. Ez alapján kiszámítható, hogy abban a számtartományban, amelyben Alice-nak és Bob-nak prímeket kéne keresnie az RSA kulcsokhoz, hogyan alakul a prímek eloszlása. Eszerint ha Alice és Bob teljesen véletlenszerűen kisorsol számokat ebből a tartományból, akkor nagyjából minden párszázadik próbálkozásnál belebotlanak egy-egy prímszámba.

Így már csak az a kérdés, hogy Alice és Bob hogyan tudja gyorsan eldönteni egy konkrét egész számról, hogy prím-e vagy sem. Az erre szolgáló algoritmusokat prímteszteknek nevezzük. A most következő prímtesztelő eljárás ismerős lehet az általános iskolából is.

23.1Prímtesztelés osztáspróbákkal

Alice és Bob némi gondolkodás után néhány korábbi fejezetben ismertetett összefüggés alapján az alábbi egyszerű, és mindenki számára jól ismert következtetésre jut a prímszámokkal kapcsolatban.

23.1. Tétel:

Legyen $n\neq 0$ egy tetszőleges nemnulla egész szám, amely nem egység, és jelölje $|n|$ az $n$ egész szám abszolút értékét. Ebben az esetben $n$ akkor és csak akkor prím, ha nem létezik $1$ -nél nagyobb, de $|n|$ -nél kisebb osztója.

Ezzel ekvivalens megfogalmazás: Az $n$ akkor és csak akkor összetett, ha létezik $1$ -nél nagyobb, de $|n|$ -nél kisebb osztója.

Megnézem a tudásbázisban

♣

Bizonyítás:

Először nézzük azt az esetet, amikor $n$ pozitív, azaz $n\gt 0$ . Ekkor ugye $|n|=n$ a 17.19. Definíció alapján. Tegyük fel, hogy $n$ -nek létezik $1$ -nél nagyobb, de $|n|=n$ -nél kisebb osztója, és mutassuk meg, hogy ekkor $n$ összetett. Jelöljük ezt a feltételezett osztót $k$ -val. Azaz teljesülnek az alábbiak:

\begin{aligned} 1\lt k&\lt n \\ k&|n \end{aligned}

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

n=kl

A 16.11. Definíció alapján azt kell bizonyítani, hogy ez a szorzat $n$ -nek egy nemtriviális felbontása, azaz sem $k$ , sem pedig $l$ nem egység, és nem is asszociáltja $n$ -nek.

Egyrészt a 16.5. Tétel alapján az egész számok $\Z$ gyűrűjében az $1$ -en és a $-1$ -en kívül nincs más egység. Mivel $1$ pozitív, ezért a 15.12. Definíció utáni megjegyzés alapján $-1$ negatív. Emiatt $k$ biztosan nem lehet egység, hiszen ő maga pozitív, továbbá határozottan nagyobb $1$ -nél.

Másrészt a 16.10. Tétel alapján $n$ -nek mindössze két asszociáltja van, méghozzá önmaga, és az ellentettje, azaz $-n$ . Mivel $n$ pozitív, ezért a 15.12. Definíció utáni megjegyzés alapján $-n$ negatív. Emiatt viszont $k$ biztosan nem lehet $n$ asszociáltja sem, hiszen ő maga pozitív, továbbá határozottan kisebb $n$ -nél.

A $k$ egész szám tehát egy olyan osztója $n$ -nek, amely se nem egység, se nem asszociáltja $n$ -nek. Most ugyanezt kellene megmutatni a fenti szorzat másik tényezőjéről, azaz $l$ -ről is. Ez viszont automatikusan teljesül a 16.12. Tétel miatt. Ha ugyanis $l$ egység lenne, akkor ez alapján $k$ szükségképpen $n$ -nek asszociáltja lenne. Ha viszont $l$ asszociáltja lenne $n$ -nek, akkor $k$ szükségképpen egység lenne. Mindkét esetről láttuk, hogy nem ez a helyzet. Megtaláltuk tehát $n$ -nek egy nemtriviális felbontását, így ő a 16.11. Definíció alapján valóban összetett.

Visszafelé: Tegyük most fel indirekt, hogy $n$ összetett ugyan, ám mégsem létezik olyan osztója, amely $1$ -nél nagyobb, de $|n|=n$ -nél kisebb. Mivel összetett, így a 16.11. Definíció alapján létezik valamilyen nemtriviális felbontása. Például:

n=kl

Az $n=kl$ egyenlet miatt azonban a 15.1. Tétel 4. pontja alapján teljesül az alábbi egyenlet is:

n=(-k)(-l)

**23.3. ábra:** Osztók ellentettjeinek elhelyezkedése

A 17.2. Lemma miatt az $n$ -nél nagyobb számtartományt ismételten kizárhatjuk. Így végülis indirekt feltételezésünkkel ellentétben mégiscsak találtunk két olyan osztót – nevezetesen a $-k$ és $-l$ egész számokat –, amelyek $1$ -nél nagyobbak, de $|n|=n$ -nél kisebbek.

Végezetül nézzük most azt az esetet, amikor $n$ negatív, azaz $n\lt 0$ . Ekkor egyrészt a 15.12. Definíció utáni megjegyzés alapján $-n$ pozitív. Másrészt pedig a 16.8. Tétel 1. pontja alapján ő $n$ -nek asszociáltja, azaz pontosan ugyanazok az osztói, mint $n$ -nek. Így $n$ akkor és csak akkor prím, ha $-n$ is, amelyre viszont pozitivitása miatt szóról szóra alkalmazható a fenti gondolatmenet.

Megnézem a tudásbázisban

∎

Ez alapján tehát egy adott $n$ egész szám esetén elegendő osztáspróbákkal ellenőrizni, hogy teljesül-e valamelyik oszthatóság az alábbiak közül:

\begin{aligned}2&|n \\ 3&|n \\ 4&|n \\ &\vdots \\ |n|-1&|n\end{aligned}

Ha ezek közül akárcsak egyetlen oszthatóság is teljesül, akkor az iménti tétel alapján a prímtesztelő algoritmus leállhat azzal a válasszal, hogy $n$ biztosan összetett. Ezzel szemben ha egyetlen oszthatóság sem teljesül a fentiek közül, akkor ugyancsak az iménti tétel alapján $n$ biztosan prím. Például az $n=7$ biztosan prím, hiszen:

\begin{aligned}2&\nmid 7 \\ 3&\nmid 7 \\ 4&\nmid 7 \\ 5&\nmid 7 \\ 6&\nmid 7\end{aligned}

Viszont az $n=35$ biztosan összetett, hiszen:

\begin{aligned}2&\nmid 35 \\ 3&\nmid 35 \\ 4&\nmid 35 \\ 5&|35\end{aligned}

Főhőseink tehát ez alapján bármilyen egész számról el tudják dönteni, hogy prímszám-e vagy sem. Csakhogy van egy kis probléma ezzel az eljárással, amely akkor jelentkezik, amikor a gyakorlatban előforduló nagyságrendű számokra kezdjük el lefuttatni. Vizsgáljuk ezért meg, hogy mekkora az eljárás számításigénye a bemenet méretének függvényében. A "bemenet mérete" alatt itt értelemszerűen a leírásához szükséges számjegyek számát fogjuk érteni. Jelöljük ezt a számot mondjuk $k$ -val, és tegyük fel, hogy tízes számrendszerben dolgozunk.

A lehető legkisebb $k$ számjegyből álló egész szám a $10^{k-1}$ lesz. Vagyis ha a bemenet történetesen prímszám, akkor ez nagyságrendileg legalább ennyi osztáspróba után fog csak kiderülni. Ez bizony a bemenet méretének exponenciális függvénye, és így az algoritmus sajnos a 7. fejezetben tanultak alapján nem nevezhető hatékonynak. Nem sokkal jobb a helyzet akkor sem, ha a bemenet összetett szám, kivéve persze az olyan ritka eseteket, amikor viszonylag kicsi prímtényezője is van. A 21. fejezetben már említettük, hogy az RSA rejtjelezéshez manapság tipikusan 600-1200 számjegyből álló prímszámokat használnak, ezért az algoritmus futása ebben a számtartományban az idők végezetéig is eltarthat, és így a gyakorlatban nem használható.

Alice és Bob tehát tovább töri a fejét, hogyan tudnának ennél jóval kevesebb osztáspróbával is célt érni, és némi gondolkodás után az alábbi következtetésre jutnak.

23.2. Tétel:

Legyen $n\neq 0$ egy tetszőleges nemnulla egész szám, amely nem egység, és jelölje $|n|$ az $n$ egész szám abszolút értékét. Jelöljük továbbá $r$ -rel a lehető legnagyobb olyan egész számot, amelyre $r^2\leq |n|$ teljesül. Ebben az esetben az $n$ egész szám akkor és csak akkor prím, ha nem létezik olyan osztója, amely $1$ -nél nagyobb, de legfeljebb $r$ .

Ezzel ekvivalens megfogalmazás: Az $n$ akkor és csak akkor összetett, ha létezik olyan osztója, amely $1$ -nél nagyobb, de legfeljebb $r$ .

Megnézem a tudásbázisban

♣

Bizonyítás:

Előszöris az világos, hogy $r$ nemnegatív, hiszen az ő és az ellentettjének a négyzete megegyezik, így ha negatív lenne, akkor nem ő lenne a legnagyobb olyan egész szám, amelyre $r^2\leq |n|$ teljesül.

Másodszor $r$ biztosan nem lehet $0$ sem. Az abszolútérték-függvény 17.19. Definíciója alapján $n\neq 0$ -ból $|n|\neq 0$ , azaz végülis $1\leq |n|$ következik. Ha mármost $r=0$ lenne, akkor igaz ugyan, hogy a négyzete legfeljebb $|n|$ lenne, ám ekkor lenne nála nagyobb ugyanilyen tulajdonságú szám is – például az $1$ .

Összefoglalva $r$ -re teljesülni fog az $1\leq r$ egyenlőtlenség, ebből pedig a 15.11. Definíció 2. pontja miatt $r\leq r^2$ következik. Ezt összevetve a tétel szövegében szereplő $r^2\leq |n|$ feltétellel teljesül tehát az alábbi:

1\leq r\leq |n|

Ennyi előkészület után igazoljuk a tétel állítását. Tegyük fel, hogy $n$ prím. Ekkor a 23.1. Tétel szerint egyáltalán nincsen osztója $1$ és $|n|$ között. Következésképp az ennél szűkebb, $1$ és $r$ közötti szakaszon "méginkább" nincs osztója.

Visszafelé: Először azt az esetet igazoljuk, amikoris $n$ pozitív. Tegyük fel, hogy $n$ összetett, azaz létezik valamilyen $n=kl$ nemtriviális felbontása. Az általánosság megsértése nélkül feltehetjük, hogy $k$ és $l$ mindketten pozitívak, máskülönben ellentettjüket véve ez az állapot elérhető. Azt kell igazolni, hogy $k$ és $l$ közül legalább az egyik nemnagyobb $r$ -nél. Tegyük fel indirekt, hogy nem ez a helyzet, vagyis az alábbi két eset valamelyike áll fenn:

\begin{aligned}r&\lt k\leq l \\ r&\lt l\leq k\end{aligned}

Első esetben a jobboldali egyenlőtlenség mindkét oldalát $k$ -val megszorozva az alábbit kapjuk:

k^2\leq kl=n

Ez viszont $r\lt k$ miatt lehetetlen, hiszen a tétel szövege alapján $r$ a legnagyobb olyan szám, amelynek négyzete $|n|=n$ -t nem lépi túl.

Ehhez hasonlóan a második esetben a jobboldali egyenlőtlenség mindkét oldalát $l$ -lel megszorozva ezt kapjuk:

l^2\leq lk=n

Ez $r\lt l$ miatt az előbb ismertetett okból szintén lehetetlen. Indirekt feltételezésünk hibás volt, vagyis $k$ és $l$ közül az egyik biztosan nem lehet nagyobb $r$ -nél, ahogyan a tétel állítja.

Végezetül nézzük most azt az esetet, amikor $n$ negatív, azaz $n\lt 0$ . Ekkor egyrészt a 15.12. Definíció utáni megjegyzés alapján $-n$ pozitív. Másrészt pedig a 16.8. Tétel 1. pontja miatt ő $n$ -nek asszociáltja, azaz pontosan ugyanazok az osztói, mint $n$ -nek. Így $n$ akkor és csak akkor prím, ha $-n$ is, amelyre viszont pozitivitása miatt szóról szóra alkalmazható a fenti gondolatmenet.

Megnézem a tudásbázisban

∎

Ez alapján tehát az osztáspróbákkal elegendő addig a számig elmenni, amelynek a négyzete még épp $|n|$ alatt marad. Ha eddig nem találunk osztót, akkor az iménti tétel szerint garantáltan ezután sem fogunk. Például az $n=61$ biztosan prím, hiszen:

\begin{aligned}2&\nmid 61 \\ 3&\nmid 61 \\ 4&\nmid 61 \\ 5&\nmid 61 \\ 6&\nmid 61 \\ 7&\nmid 61\end{aligned}

A további osztáspróbákat már nem érdemes elvégezni, hiszen $8^2\gt 61$ , így ha $7$ -ig bezárólag nincs osztója a $61$ -nek, akkor $7$ -nél nagyobb osztója sem lesz. Ez első látásra lényeges gyorsításnak tűnik, de sajnos nem az. Most nem teljes matematikai precizitással felvázoljuk, hogy miért.

Tegyük fel ismét, hogy a bemeneti szám $k$ darab számjegyből áll, és tízes számrendszerben dolgozunk. A lehető legkisebb $k$ számjegyből álló szám a $10^{k-1}$ . Egy ekkora számnak a teszteléséhez az iménti tétel alapján nagyságrendileg $r$ darab osztáspróbát kell elvégezni, ahol $r$ a legnagyobb olyan szám, amelyre teljesül, hogy $r^2\leq 10^{k-1}$ . Tegyük fel, hogy $r$ a tízes számrendszerben $l$ darab számjeggyel írható le, azaz $10^{l-1}\leq r$ . Ezt négyzetre emelve azt kapjuk, hogy $10^{2(l-1)}\leq r^2$ . Összefoglalva:

10^{2(l-1)} \leq r^2 \leq 10^{k-1}

Azaz:

10^{l-1} \leq r \leq 10^{\frac{k-1}{2}}

Ez az exponenciális függvény tulajdonságai miatt azt jelenti, hogy $r$ felírásához legalább feleannyi számjegy kell, mint ahány számjegyből az eredeti $n$ szám áll. Mivel $r$ az elvégzendő osztáspróbák számát jelenti, ezért ez sajnos még mindig a bemenet méretének exponenciális függvénye.

Alice és Bob tehát továbbra sem mennek sokra ezzel a prímtesztelési eljárással abban a számtartományban, ahol prímszámokat szeretnének keresni. Ezért most szintet lépünk, és egy lényegesen más elven működő prímtesztet ismertetünk.

23.2A Fermat-prímteszt

Ennek a prímtesztelő eljárásnak az alapja a 22.1. szakaszban megismert kis Fermat-tétel. Ez a tétel azt állítja, hogy ha egy $n\gt 1$ pozitív egész szám prímszám, akkor minden $n$ -hez relatív prím $a$ egész szám esetén teljesülni fog az alábbi kongruencia:

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

Más megfogalmazásban azt is mondhatjuk, hogy amennyiben akárcsak egyetlen olyan $n$ -hez relatív prím $a$ egész szám is létezik, amelyre nem teljesül a fenti kongruencia, akkor $n$ biztosan nem prím – azaz összetett. Vigyázzunk azonban, mivel a dolog a másik irányba nem működik. Vagyis abból, hogy találunk $n$ -hez egy olyan $a$ egész számot, amelyre teljesül a fenti kongruencia még nem következik, hogy $n$ prím. A kis Fermat-tétel utáni megjegyzésben mutattunk is néhány ellenpéldát erre. Kérdés, hogy ennek ellenére az ilyen találatok megerősíthetik-e bennünk azt a feltételezést, hogy $n$ esetleg tényleg prím, és ha igen, akkor milyen mértékben?

Egy szemléletes analógiával élve képzeljük el azt, hogy egy $n$ összetett egész szám a "vádlott" egy bírósági tárgyaláson, ahol az ő "bűnösségét" – vagyis azt, hogy összetett – szeretnénk bizonyítani. Azok az $a$ egész számok, amelyekre nem teljesül a fenti kongruencia, tulajdonképpen "leleplezik" $n$ bűnösségét – vagy mondhatjuk úgy is, hogy "tanúsítják" $n$ összetettségét a bíróság előtt. Ha viszont egy $a$ egész számra teljesül a kongruencia, akkor egy ilyen $a$ egész szám akadályozza a bíróságot, hiszen nem árul el semmit $n$ bűnösségével kapcsolatban. Vagy mondhatjuk úgy is, hogy $a$ ebben az esetben "cinkosa" $n$ -nek. Természetesen amennyiben $n$ nem bűnös – azaz valóban prím –, akkor a kis Fermat-tétel értelmében nyilván nem létezik hozzá olyan, a fenti értelemben vett tanú, amely ennek ellenkezőjét bizonyítaná.

A fenti gondolatmenetből egy valószínűségi alapon működő prímtesztelő eljárást kaphatunk. Ehhez elsősorban azt a kérdést kell megvizsgálnunk, hogy bűnösség esetén mennyi a valószínűsége annak, hogy egy véletlenszerűen választott, $n$ -hez relatív prím $a$ egész szám ezt a bűnösséget tanúsítja. Tegyük fel, hogy ez a valószínűség kellőképpen nagy. Amennyiben szúrópróbaszerűen kiválasztunk néhány ilyen $a$ egész számot, és $n$ valóban összetett, akkor ezt szinte biztosan tanúsítani fogja valamelyik azáltal, hogy nem teljesül rá a fenti kongruencia. Vagy megfordítva: amennyiben néhány szúrópróbaszerűen kiválasztott $a$ jelölt mindegyike teljesíti a kongruenciát, akkor $n$ szinte biztosan prím.

Mielőtt megvizsgálnánk, hogy ténylegesen hogyan alakulnak ezek a valószínűségek, először öntsük precíz matematikai formába, hogy pontosan mit értünk "tanú" alatt a fenti értelemben.

Könnyen adódik, hogy ha egy $a$ egész szám "tanú", akkor minden olyan $b$ egész szám is "tanú", amely $a$ -val azonos modulo $n$ maradékosztályban van. Ekkor ugyanis teljesül az $a\equiv b\pmod n$ kongruencia, és így a 20.2. Tétel 6. pontja miatt teljesül az alábbi kongruencia is:

a^{n-1} \equiv b^{n-1} \pmod n

Mármost ha a baloldal nem kongruens $1$ -gyel – mivel ugye $a$ "tanú" –, akkor a jobboldal sem lehet kongruens $1$ -gyel – azaz ilyenkor $b$ is "tanú". Hasonló megfontolásból: ha a baloldal nem "tanú", akkor a jobboldal sem. Az alábbi definícióban tehát a "tanú" fogalmát praktikus módon komplett maradékosztályokra fogjuk vonatkoztatni.

23.3. Definíció (Fermat-tanú):

Legyen $n\gt 1$ egy tetszőleges pozitív, $a$ pedig tetszőleges $n$ -hez relatív prím egész szám. Tegyük fel továbbá, hogy $a$ -ra nem teljesül a kis Fermat-tételben szereplő kongruencia, azaz:

a^{n-1} \ \cancel{\equiv} \ 1 \pmod n

Ekkor az $a$ egész szám által reprezentált $[a]_n$ maradékosztályt az $n$ egész szám Fermat-tanújának nevezzük. Amennyiben $a$ -ra teljesül a fenti kongruencia, akkor az $[a]_n$ maradékosztályt Fermat-nemtanúnak nevezzük. Ha $n$ összetett, akkor az ő Fermat-nemtanúit Fermat-cinkosoknak nevezzük.

Megnézem a tudásbázisban

♣

Megjegyzés:

Mivel $a$ -ról kikötöttük, hogy relatív prím $n$ -hez, ezért a 20.17. Tétel 2. pontja alapján $[a]_n$ mindenképpen redukált maradékosztály, tehát a definíció a Fermat-tanúk körét a redukált maradékosztályok körén belülre korlátozza. Vegyük észre, hogy ez egy teljesen önkényesen meghozott terminológiai döntés. A nem redukált maradékosztályok – a $[0]_n$ kivételével – ugyanis már csak a létezésükkel is bizonyítják $n$ összetettségét. Ezeket azonban ebben a definícióban mégsem nevezzük Fermat-tanúknak, mivel egy ilyen maradékosztály elsősorban azzal buktatja le $n$ -et, hogy bármely elemének van az egységektől és $n$ asszociáltjaitól különböző közös osztója vele.

Megjegyezzük ugyanakkor, hogy egy Fermat-nemtanú mindenképpen csak redukált maradékosztály lehetne az említett megszorítás nélkül is. Ha ugyanis $[a]_n$ nem redukált maradékosztály, akkor $a$ nem relatív prím $n$ -hez, és így a 20.21. Tétel miatt amúgysem teljesülhetne a Fermat-kongruencia.

**23.4. ábra:** A Fermat-nemtanúk elhelyezkedése

Megnézem a tudásbázisban

♣

A kis Fermat-tétel eszerint úgy is megfogalmazható, hogy amennyiben egy $n$ egész számnak létezik Fermat-tanúja, akkor biztosan összetett. Így ha $n$ -ről azt szeretnénk bizonyítani, hogy összetett, akkor nincs más dolgunk, mint keresni egy Fermat-tanút a modulo $n$ redukált maradékosztályok között. Igenám, csakhogy e maradékosztályok száma borzasztóan nagy, így reménytelennek tűnik bármiféle ezek között való keresgélés. Az az érdekes, hogy ennek ellenére viszonylag gyorsan tudunk Fermat-tanút találni, amennyiben egyáltalán létezik ilyen. Most ennek okát fogjuk megvizsgálni.

Az alábbi táblázatban néhány adatot láthatunk az összes $500$ és $600$ közötti páratlan egész számról. A táblázat első oszlopa magát a vizsgált $n$ számot tartalmazza. A második oszlopban azt láthatjuk, hogy összesen hány modulo $n$ redukált maradékosztály létezik. Ez ugye a 20.7. Definíció alapján épp az Euler-féle $\varphi$ -függvény értéke. A harmadik oszlop tartalmazza azt, hogy e $\varphi(n)$ darab redukált maradékosztály között mennyi Fermat-tanú van. Ezt az értéket $w(n)$ -nel jelöltük. Végül a negyedik oszlop azt tartalmazza, hogy $n$ ténylegesen prím-e vagy sem:

\begin{array}{c||c}\begin{array}{c|c|c|c} n & \varphi(n) & w(n) & \text{prím} \\ \hline 501 & 332 & 328 & \text{nem} \\ 503 & 502 & 0 & \text{igen} \\ 505 & 400 & 384 & \text{nem} \\ 507 & 312 & 308 & \text{nem} \\ 509 & 508 & 0 & \text{igen} \\ 511 & 432 & 396 & \text{nem} \\ 513 & 324 & 320 & \text{nem} \\ 515 & 408 & 404 & \text{nem} \\ 517 & 460 & 456 & \text{nem} \\ 519 & 344 & 340 & \text{nem} \\ 521 & 520 & 0 & \text{igen} \\ 523 & 522 & 0 & \text{igen} \\ 525 & 240 & 224 & \text{nem} \\ 527 & 480 & 476 & \text{nem} \\ 529 & 506 & 484 & \text{nem} \\ 531 & 348 & 344 & \text{nem} \\ 533 & 480 & 464 & \text{nem} \\ 535 & 424 & 420 & \text{nem} \\ 537 & 356 & 352 & \text{nem} \\ 539 & 420 & 416 & \text{nem} \\ 541 & 540 & 0 & \text{igen} \\ 543 & 360 & 356 & \text{nem} \\ 545 & 432 & 416 & \text{nem} \\ 547 & 546 & 0 & \text{igen} \\ 549 & 360 & 352 & \text{nem} \end{array} & \begin{array}{c|c|c|c} n & \varphi(n) & w(n) & \text{prím} \\ \hline 551 & 504 & 500 & \text{nem} \\ 553 & 468 & 432 & \text{nem} \\ 555 & 288 & 280 & \text{nem} \\ 557 & 556 & 0 & \text{igen} \\ 559 & 504 & 468 & \text{nem} \\ 561 & 320 & 0 & \boxed{\text{nem}} \\ 563 & 562 & 0 & \text{igen} \\ 565 & 448 & 432 & \text{nem} \\ 567 & 324 & 320 & \text{nem} \\ 569 & 568 & 0 & \text{igen} \\ 571 & 570 & 0 & \text{igen} \\ 573 & 380 & 376 & \text{nem} \\ 575 & 440 & 436 & \text{nem} \\ 577 & 576 & 0 & \text{igen} \\ 579 & 384 & 380 & \text{nem} \\ 581 & 492 & 488 & \text{nem} \\ 583 & 520 & 516 & \text{nem} \\ 585 & 288 & 256 & \text{nem} \\ 587 & 586 & 0 & \text{igen} \\ 589 & 540 & 504 & \text{nem} \\ 591 & 392 & 388 & \text{nem} \\ 593 & 592 & 0 & \text{igen} \\ 595 & 384 & 360 & \text{nem} \\ 597 & 396 & 392 & \text{nem} \\ 599 & 598 & 0 & \text{igen} \end{array} \end{array}

Az nyilvánvaló, hogy a prímeknek nincs egyetlen Fermat-tanúja sem, hiszen az ellentmondana a kis Fermat-tételnek. A táblázatot tovább vizsgálva úgy tűnik továbbá, hogy amennyiben viszont egy $n$ egész szám összetett, akkor ezt rendkívül sok – sőt, majdnem mindegyik – modulo $n$ redukált maradékosztály tanúsítja. Ez abból látszik, hogy az összetett számok esetén a $w(n)$ értéke csak alig kisebb $\varphi(n)$ -nél. Van azonban egy kakukktojás ebben a számtartományban, méghozzá az $561$ . Neki ugyanis nincs egyetlen Fermat-tanúja sem annak ellenére, hogy összetett. Őt most tegyük félre egy kicsit, és térjünk vissza rá a 23.4. szakaszban.

Az látszik tehát, hogy véletlenszerűen választott redukált maradékosztályok vizsgálatával jó eséllyel nagyon hamar "leleplezhetjük" $n$ -t, amennyiben összetett, hiszen kicsi az esélye, hogy nem találunk el egyetlen Fermat-tanút sem abból a rengeteg sokból. Ráadásul egy-egy ilyen vizsgálatot a 21.4. szakaszban tanult ismételt négyzetreemelések módszerével rettentően hamar el is tudunk végezni. Hamarosan általánosságban is igazolni fogunk egy alsó becslést a Fermat-tanúk számára vonatkozóan. Ez ugyan jóval szerényebb lesz annál, mint ami a táblázatból látszik, ám egy hatékonyan működő prímteszthez még ez is bőven elég lesz.

Ehhez azonban először két segédtételre lesz szükségünk. Az első arra vonatkozik, hogy egy Fermat-tanúból hogyan tudunk előállítani egy másik Fermat-tanút.

23.4. Lemma:

Amennyiben egy tetszőleges $n\gt 1$ pozitív egész szám bármely Fermat-tanúját megszorozzuk egy tetszőleges Fermat-nemtanúval, akkor az eredmény szintén Fermat-tanú lesz.

Megnézem a tudásbázisban

♣

Bizonyítás:

Legyen $[a]_n$ egy Fermat-tanú, $[b]_n$ pedig egy Fermat-nemtanú. Képezzük e két maradékosztály szorzatát, ami a 20.5. Tétel alapján az $[ab]_n$ maradékosztály lesz. Mivel $[b]_n$ Fermat-nemtanú, ezért a 23.3. Definíció alapján teljesül az alábbi kongruencia:

b^{n-1}\equiv 1\pmod n

Következésképp a 20.2. Tétel 5. pontja miatt teljesül az alábbi kongruencia is:

a^{n-1}b^{n-1} \equiv a^{n-1} \pmod n

Ennek a baloldala a hatványozás azonosságairól szóló 18.8. Tétel 1. pontja alapján átírható:

(ab)^{n-1} \equiv a^{n-1} \pmod n

Mivel $[a]_n$ Fermat-tanú, ezért a 23.3. Definíció alapján a jobboldali kifejezés biztosan nem kongruens $1$ -gyel modulo $n$ . Így hát a baloldali kifejezés sem, azaz:

(ab)^n \ \cancel{\equiv} \ 1\pmod n

Ez ismét a 23.3. Definíció alapján épp azt jelenti, hogy az $[ab]_n$ maradékosztály valóban egy Fermat-tanú.

Megnézem a tudásbázisban

∎

A második segédtétel arra vonatkozóan mond ki egy fontos állítást, hogy mi történik akkor, ha egymástól különböző maradékosztályokat egyesével végigszorozzuk ugyanazzal a redukált maradékosztállyal.

23.5. Lemma:

Ha bármely két egymástól különböző $[a]_n$ és $[b]_n$ maradékosztályt megszorzunk egy tetszőleges $[c]_n$ redukált maradékosztállyal, akkor az így kapott maradékosztályok is különböznek egymástól.

Azaz ha $[a]_n \neq [b]_n$ , akkor $[c]_n \odot [a]_n \neq [c]_n \odot [b]_n$ , ahol $\odot$ jelöli a 20.5. Tétel szerinti szorzást.

Megnézem a tudásbázisban

♣

Bizonyítás:

Tegyük fel indirekt, hogy nem ez a helyzet, vagyis annak ellenére, hogy $[a]_n$ és $[b]_n$ különböznek egymástól, mégiscsak teljesül az alábbi egyenlőség:

[c]_n \odot [a]_n = [c]_n \odot [b]_n

A $\odot$ művelet 20.5. Tételben ismertetett definíciója alapján ez az alábbit jelenti:

[ca]_n = [cb]_n

A 20.4. Tétel alapján ugyanezt a kongruenciák nyelvén is kifejezhetjük:

ca\equiv cb\pmod n

Mivel $[c]_n$ egy redukált maradékosztály, ezért a 20.15. Tétel alapján $c$ relatív prím $n$ -hez, és így a fenti kongruencia a 20.3. Tétel utáni megjegyzés szerint minden további nélkül egyszerűsíthető $c$ -vel. Ezt kapjuk tehát:

a\equiv b\pmod n

Ez viszont azt jelenti, hogy indirekt feltételezésünkkel ellentétben $a$ és $b$ mégiscsak ugyanazt a maradékosztályt reprezentálja, ami ellentmondás.

Megnézem a tudásbázisban

∎

E két segédtétel segítségével mostmár könnyedén igazolhatjuk a Fermat-tanúk számára vonatkozó alsó becslésünket.

23.6. Tétel:

Legyen $n\gt 1$ egy tetszőleges pozitív egész szám. Amennyiben $n$ -nek létezik Fermat-tanúja, akkor a redukált maradékosztályoknak legalább a fele Fermat-tanú.

Megnézem a tudásbázisban

♣

Bizonyítás:

Tegyük fel, hogy összesen $k$ darab olyan redukált maradékosztály van, amely Fermat-nemtanú. Legyenek például ezek az alábbiak, amelyek tehát páronként különböző redukált maradékosztályok:

\begin{aligned}&[a_1]_n \\ &[a_2]_n \\ &[a_3]_n \\ &\vdots \\ &[a_k]_n \end{aligned}

A tétel szövege alapján tegyük fel, hogy $n$ -nek létezik legalább egy Fermat-tanúja. Legyen ez például az alábbi redukált maradékosztály:

[b]_n

Amennyiben ezzel a $[b]_n$ Fermat-tanúval végigszorozzuk a fenti $k$ darab Fermat-nemtanút, akkor az alábbi maradékosztályokat kapjuk, amelyek a 23.4. Lemma alapján szintén mindannyian Fermat-tanúk:

\begin{aligned}[b]_n &\odot [a_1]_n \\ [b]_n &\odot [a_2]_n \\ [b]_n &\odot [a_3]_n \\ &\vdots \\ [b]_n &\odot [a_k]_n \end{aligned}

Mivel a szorzáshoz használt $[b]_n$ egy redukált maradékosztály, továbbá az $[a_1]_n$ , $[a_2]_n$ , ..., $[a_k]_n$ maradékosztályok páronként különbözőek voltak, emiatt a 23.5. Lemma alapján az eredményül kapott szorzatok is páronként különböző redukált maradékosztályok. Ráadásul ezek az $[a_1]_n$ , $[a_2]_n$ , ..., $[a_k]_n$ redukált maradékosztályoktól is biztosan különböznek, hiszen azok nem is voltak Fermat-tanúk.

Ha tehát teljesül a tétel feltétele, miszerint $n$ -hez létezik legalább egy Fermat-tanú, akkor ennek a segítségével minden Fermat-nemtanúhoz elő tudunk állítani egy-egy újabb Fermat-tanút. Más szavakkal a redukált maradékosztályok között minimum annyi Fermat-tanú van, mint ahány Fermat-nemtanú. A redukált maradékosztályoknak tehát valóban legalább a fele Fermat-tanú.

Megnézem a tudásbázisban

∎

Na és akkor mi van?! – kérdezhetné az Olvasó. Nos, az a helyzet, hogy ezt az első látásra nem túl érdekes tényt Alice és Bob egy meglehetősen pofátlan kis trükkel prímteszteléshez tudja felhasználni.

23.3„Valószínűleg” prím?!

Az alábbiakban ismertetett eljárást Fermat-prímtesztnek nevezzük. Az algoritmus bemenete egy $n\gt 1$ pozitív egész szám, amelyről el kellene dönteni, hogy prím-e vagy összetett:

Válasszunk véletlenszerűen egy tetszőleges $1$ és $n$ közötti $a$ egész számot, azaz legyen $1\lt a\lt n$ .
A 17.18. Tétel bizonyításában ismertetett euklidészi algoritmus segítségével számítsuk ki az $(a,n)$ kitüntetett közös osztót. Ha ennek értéke $1$ , akkor folytassuk az eljárást a 3. lépéstől. Egyébként az algoritmus leáll a következő válasszal: az $n$ egész szám biztosan összetett, és az egyik osztója $(a,n)$ .
A 21.4. szakaszban ismertetett ismételt négyzetreemelések módszerével ellenőrizzük le, hogy teljesül-e az $a^{n-1}\equiv 1\pmod n$ kongruencia.
Amennyiben nem teljesül a kongruencia, akkor az algoritmus leáll a következő válasszal: az $n$ egész szám biztosan összetett, de nem találtuk meg egyetlen osztóját sem.
Amennyiben teljesül a kongruencia, akkor az algoritmus a következő válasszal áll le: az $n$ egész szám "valószínűleg" prím.

Ez az egész elsőre teljesen értelmetlennek tűnik, ezért most vizsgáljuk meg, hogy miről is van szó tulajdonképpen. Képzeljük el, hogy a bemenő $n$ egész szám valójában összetett, ám ezt szeretné minél jobban eltitkolni előlünk. Mi azonban a kis Fermat-tételből tudjuk, hogy $n$ esetleges összetettségét egy Fermat-tanú egyértelműen leleplezné.

Ezért az összes nemnulla modulo $n$ maradékosztályt szépen bedobáljuk egy képzeletbeli kalapba, majd becsukjuk a szemünket, és teljesen véletlenszerűen kihúzunk közülük egyet. Olyan ez, akárcsak egy lottósorsolás. Ez lenne tehát az algoritmus 1. lépése. A 2. lépésben azt vizsgáljuk meg, hogy egy redukált maradékosztályt húztunk-e ki. Annak, hogy nem, gyakorlatilag semmi esélye, de ha mégis, akkor ez leleplezi $n$ -et, ráadásul még egy osztóját is megkapjuk. Majdnem biztos azonban, hogy tovább kell mennünk a 3. lépésre.

Ezen a ponton már tudjuk, hogy a kiválasztott maradékosztály egy redukált maradékosztály. Ebben a lépésben azt ellenőrizzük le, hogy véletlenül nem egy Fermat-tanút húztunk-e ki a kalapból. Ha igen – azaz a vizsgált kongruencia nem teljesül – akkor $n$ lelepleződött, hiszen a kis Fermat-tétel miatt biztosan összetett. Ha azonban egy Fermat-nemtanút húztunk ki – azaz a vizsgált kongruencia teljesül –, akkor nem tudunk semmi biztosat mondani $n$ -ről, ugyanis a kis Fermat-tétel megfordítása nem igaz.

Azt viszont a 23.2. szakaszban bizonyított 23.6. Tétel alapján tudjuk, hogy a kalapban lévő redukált maradékosztályoknak legalább a fele – ám a tapasztalat alapján általában ennél jóval nagyobb része – Fermat-tanú. Így annak valószínűsége meglehetősen kicsi, hogy pont belehúztunk abba a néhány Fermat-nemtanúba, miközben $n$ összetett. Ennél sokkal valószínűbb, hogy $n$ ténylegesen prím, és emiatt valóban nincs egyetlen Fermat-tanú sem abban a bizonyos kalapban. Ám biztosat ezen a ponton nem tudunk mondani, és ez az oka ennek a meglehetősen furcsán hangzó "valószínűleg prím" válasznak.

A Fermat-tanúk számára vonatkozó, a 23.6. Tételben bizonyított alsó becslés ugyan önmagában nem túl erős, azonban Alice és Bob megteheti, hogy többször is húz a kalapból. A Fermat-tanúság ellenőrzése ugyanis – mint említettük – az ismételt négyzetreemelések módszerével rendkívül gyorsan elvégezhető. Tegyük fel, hogy a lehető legrosszabb a helyzet, és a redukált maradékosztályoknak mindössze csak a fele Fermat-tanú. Ekkor 50% annak valószínűsége, hogy főhőseink egy véletlenszerű választással pont a másik feléből választanak egy redukált maradékosztályt. Annak pedig már csak 25%, hogy ez kétszer egymás után is megtörténik. Az, hogy egy újabb, harmadik húzással sem találunk Fermat-tanút, már csak 12.5% valószínűséggel következik be. És így tovább, minden újabb húzással megfeleződik annak valószínűsége, hogy tévesen prímszámmá nyilvánítjuk $n$ -et.

Tegyük fel például, hogy 100 teljesen véletlenszerűen kiválasztott redukált maradékosztály egyike sem bizonyul Fermat-tanúnak. Ennek már csupán annyi az esélye, mint százszor zsinórban eltalálni, hogy egy feldobott pénzérme fej vagy írás lesz-e. Ez nagyságrendileg kevésbé valószínű, mint hogy valakinek háromszor egymás után telitalálata lesz az ötöslottón.

Van azonban egy kis probléma ezzel a prímteszttel, amivel mindenképpen fogalkoznunk kell: sajnos léteznek olyan összetett egész számok, amelyeket nem lehet ilyen módon kiszűrni.

23.4Univerzális álprímek

Térjünk vissza egy kicsit a 23.2. szakaszban szereplő táblázathoz. Itt a második oszlop a modulo $n$ redukált maradékosztályok számát mutatja – amely ugye az Euler-féle $\varphi$ -függvény értéke –, a harmadik pedig azt, hogy ezek között hány Fermat-tanú van – ezt $w(n)$ -nel jelöltük.

Értelemszerűen a prímszámok esetén ez utóbbi $0$ , hiszen egy prímszámhoz nyilván nem létezik az összetettségét igazoló Fermat-tanú. Kérdés, hogy vajon létezik-e olyan összetett szám, amelyhez szintén nincs Fermat-tanú a redukált maradékosztályok között. A táblázatban felhívtuk a figyelmet az $561$ egész számra, amely épp ezzel a szemtelen tulajdonsággal rendelkezik, és sajnos nem ő az egyetlen. Ezeknek a számoknak külön nevük is van.

23.7. Definíció (Carmichael-számok):

Legyen $n\gt 1$ tetszőleges pozitív, továbbá $a$ egy $n$ -hez relatív prím egész szám, és tegyük fel, hogy $n$ összetett. Amennyiben az $[a]_n$ redukált maradékosztály Fermat-nemtanú, akkor azt mondjuk, hogy $n$ egy Fermat-álprím az $a$ alapra nézve.

Amennyiben a modulo $n$ redukált maradékosztályok közül mindegyik Fermat-nemtanú, akkor $n$ -et univerzális Fermat-álprímnek vagy Carmichael-számnak nevezzük.

Megnézem a tudásbázisban

♣

Ha tehát véletlenül épp egy Carmichael-számba botlunk, akkor a Fermat-prímteszt azt nagyon nagy valószínűséggel tévesen prímnek fogja minősíteni, hiszen akárhány redukált maradékosztályt is húzunk ki a kalapból, azokra mind teljesülni fog a kis Fermat-tételben szereplő kongruencia. Az ilyen számok összetettségét egyedül akkor fogjuk tudni detektálni, ha sikerül épp egy nem redukált maradékosztályt kihúzni a kalapból. Ilyenkor ugyanis a 2. lépésben végrehajtott euklidészi algoritmus $1$ -től különböző eredménye lebuktatja a számunkat. Erre azonban gyakorlatilag semmi esély nincs, hiszen egy nagy szám esetén a maradékosztályoknak általában csak elenyésző hányada nem redukált maradékosztály.

A figyelmes Olvasó észreveheti az említett táblázatból, hogy egy $n$ univerzális Fermat-álprímet mindössze az különbözteti meg egy valódi prímtől, hogy összetettsége miatt a $[0]_n$ maradékosztályon kívül vannak még egyéb, nem redukált maradékosztályai is. Ez onnan látszik, hogy a táblázat második oszlopában az Euler-féle $\varphi$ -függvény értéke nem $n-1$ , ahogyan a prímek esetében a 21.5. Tétel alapján elvárható, hanem egy ennél kisebb szám. Ez valóban lebuktatja álprímünket. A gond csak az, hogy – mint ahogyan a 21.3. szakaszban már említettük – az Euler-féle $\varphi$ -függvény kiszámítására csak $n$ prímtényezőinek ismeretében van esélyünk, máskülönben az idők végezetéig is eltarthat. Így erre itt nem tudunk támaszkodni.

Érdekes kérdés, hogy vajon hány Carmichael-szám létezik? Ha esetleg ezek száma véges, akkor ezeket nyilvántarthatnánk a számítógép memóriájában, az algoritmus pedig leellenőrizhetné, hogy $n$ véletlenül nem szerepel-e ebben a listában. Régóta ismeretes, hogy tetszőleges $a\gt 1$ egész szám esetén végtelen sok $a$ alapú álprím létezik, az azonban sokáig nyitott kérdés volt, hogy vajon az univerzális Fermat-álprímek száma is végtelen-e. Sajnálatos módon 1994-ben ezt is sikerült igazolni. Emiatt nem mehetünk el szó nélkül a probléma mellett, és az $a^{n-1}\equiv 1\pmod n$ kongruencia ellenőrzésén kívül egyéb dolgokat is meg kell vizsgálnunk annak érdekében, hogy a Carmichael-számokat is ki tudjuk szűrni.

23.5A Miller-Rabin prímteszt

Ebben a szakaszban tehát a Fermat-prímtesztünket fogjuk egy kicsit feljavítani annak érdekében, hogy a Carmichael-számok se okozhassanak gondot. Ezt az új eljárást Miller-Rabin-prímtesztnek fogjuk nevezni. Előszöris szögezzük le, hogy a továbbiakban csak a páratlan $n$ egész számokkal fogunk foglalkozni. Ez nem jelent tényleges megszorítást, hiszen az utolsó számjegyből azonnal látszik, hogy páratlan vagy páros-e a bemenetünk. Ez utóbbi esetben nyilván megállhatunk, és összetettnek nyilváníthatjuk $n$ -et, hiszen az osztható $2$ -vel.

Az általánosság megsértése nélkül feltételezhetjük tehát, hogy $n\gt 1$ egy páratlan egész szám. Ekkor azonban a kis Fermat-tételben szereplő $a^{n-1}\equiv 1\pmod n$ kongruencia baloldalán az $n-1$ kitevő biztosan páros lesz. Vagyis létezik olyan $k_1$ egész szám, amelyre teljesül az alábbi – és ezt meg is kapjuk, ha $n-1$ -et "elosztjuk" $2$ -vel:

n-1 = 2\cdot k_1

Ezután $k_1$ -re vizsgáljuk meg, hogy páratlan-e vagy páros. Utóbbi esetben hasonlóképpen tovább bonthatjuk $n-1$ -et, azaz létezni fog olyan $k_2$ egész szám, amelyre teljesül az alábbi:

n-1 = 2\cdot 2\cdot k_2

És így tovább, mindaddig bontjuk tovább a jobboldali tényezőt, amíg páratlan számot nem kapunk. Ez garantáltan be fog következni véges számú lépés után, máskülönben $n-1$ prímtényezős felbontásában végtelen sok $2$ -es tényező szerepelne, ami lehetetlen. Tegyük fel, hogy $e$ darab lépés után egy valamilyen $k$ páratlan számot kapunk. Ekkor $n-1$ -re tulajdonképpen az alábbi kifejezést kaptuk:

n-1=\underbrace{2\cdot 2\cdot \ldots \cdot 2}_{e \text{ darab}}\cdot k=2^e\cdot k

Például ha az $n=561$ Carmichael-szám a bemenetünk, akkor $n-1=560$ -ra az iménti felbontás után $e=4$ és $k=35$ adódik, hiszen:

\begin{aligned}n-1=560&=2\cdot 280=\\&=2^2\cdot 140=\\&=2^3\cdot 70=\\&=2^4\cdot 35\end{aligned}

Ilymódon kiszámítva az $e$ és $k$ értékét, a kis Fermat-tételben szereplő $a^{n-1}\equiv 1\pmod n$ kongruencia az alábbi alakot ölti:

a^{2^e\cdot k}\equiv 1\pmod n

Amennyiben tehát $[a]_n$ egy redukált maradékosztály és $n$ prím, akkor teljesül a fenti kongruencia. Ez viszont a 20.1. Tétel 3. pontja alapján azt jelenti, hogy teljesül az alábbi oszthatóság:

n|a^{2^e\cdot k}-1

Most ennek az oszthatóságnak a jobboldalán szereplő kifejezést fogjuk szorzattá alakítani a következő tétel segítségével.

23.8. Tétel:

Legyenek adottak valamilyen tetszőleges $e\geq 1$ és $k\geq 1$ egész számok. Ekkor bármilyen $a$ egész szám esetén teljesül az alábbi összefüggés:

a^{2^e\cdot k}-1 = (a^k-1)\cdot (a^k+1)\cdot (a^{2k}+1)\cdot (a^{4k}+1)\cdot \ldots \cdot (a^{2^{e-1}k}+1)

Megnézem a tudásbázisban

♣

Bizonyítás:

Azt a jól ismert azonosságot fogjuk használni, miszerint bármilyen kommutatív gyűrű tetszőleges $x$ és $y$ elemeire teljesül az alábbi:

x^2-y^2=(x-y)\cdot (x+y)

Ez a 14.12. Definícióban szereplő gyűrűaxiómák közvetlen következménye, amelyet most le is ellenőrzünk. Rögtön alkalmazhatjuk az 5. axiómában lévő első disztributivitási szabályt:

(x-y)\cdot (x+y)=(x-y)\cdot x + (x-y)\cdot y=\ldots

A kapott összeg mindkét tagjára alkalmazhatjuk a második disztributivitási szabályt. Figyelembe véve a 15.1. Tétel 3. pontját, valóban a fent szereplő kifejezést kapjuk:

\ldots = x^2-yx + xy-y^2 = x^2-y^2

Ezek után alkalmazhatjuk ezt az azonosságot az $a^{2^ek}-1$ kifejezésre. Ez ugyanis a hatványozás azonosságairól szóló 18.8. Tétel 2. és 3. pontjai alapján a következőképpen alakítható át:

a^{2^ek}-1=a^{2^{e-1}\cdot k\cdot 2}-1=(a^{2^{e-1}\cdot k})^2-1

Erre már alkalmazhatjuk a fenti azonosságot $x=a^{2^{e-1}\cdot k}$ és $y=1$ szereposztással:

(\underbrace{a^{2^{e-1}\cdot k}}_{=x})^2-(\underbrace{1}_{=y})^2=(\underbrace{a^{2^{e-1}\cdot k}}_{=x}-\underbrace{1}_{=y})\cdot (\underbrace{a^{2^{e-1}\cdot k}}_{=x}+\underbrace{1}_{=y})=\ldots

Amennyiben az $e-1$ kitevő még mindig nagyobb $0$ -nál, akkor a kapott szorzat első tényezőjére megismételhetjük a fenti eljárást:

\ldots=\underbrace{(a^{2^{e-2}\cdot k}-1)\cdot (a^{2^{e-2}\cdot k}+1)}_{=a^{2^{e-1}\cdot k}-1}\cdot (a^{2^{e-1}\cdot k}+1)=\ldots

Ha még az $e-2$ kitevő is nagyobb $0$ -nál, akkor az első tényezőt ugyanígy tovább bonthatjuk. Minden lépésben tovább fog csökkenni a kitevő, és előbb-utóbb – egészen pontosan $e$ lépés után – eléri a $0$ -t. Ekkor épp a tételben szereplő szorzatot fogjuk kapni.

Megnézem a tudásbázisban

∎

Tegyük fel például, hogy továbbra is az $n=561$ Carmichael-szám a bemenetünk. Az $n-1=560$ -ból ugye már korábban kiszámítottuk az $e=4$ és $k=35$ értékeket. Ekkor az $a^{n-1}-1=a^{560}-1$ kifejezés az iménti tétel alapján így alakítható szorzattá:

a^{560}-1=(a^{35}-1)\cdot (a^{35}+1)\cdot (a^{70}+1)\cdot (a^{140}+1)\cdot (a^{280}+1)

Ha tehát $[a]_{561}$ egy tetszőleges redukált maradékosztály, és az $n=561$ egy prímszám lenne, akkor ő garantáltan osztója lenne a baloldali $a^{560}-1$ kifejezésnek. Természetesen ez az oszthatóság teljesülhet egészen más okból is, és – minthogy az $n=561$ egy Carmichael-szám – jelen esetben teljesül is bármilyen $[a]_{561}$ redukált maradékosztályra. A Fermat-prímteszt ezen a ponton annak rendje és módja szerint meg is bukik, hiszen néhány véletlenszerűen kiválasztott $[a]_{561}$ redukált maradékosztály vizsgálata után tévesen arra a következtetésre jut, hogy az $n=561$ "valószínűleg prím".

A Miller-Rabin-prímteszt viszont nem elégszik meg ennyivel, és az $n=561$ esetleges prímtulajdonságát próbálja meg cáfolni a kiválasztott $[a]_{561}$ redukált maradékosztály segítségével. Ha ugyanis $n=561$ osztója a baloldali $a^{560}-1$ egész számnak, akkor a prímtulajdonság miatt a 16.13. Definíció utáni megjegyzés szerint osztója kell legyen legalább az egyik jobboldalon szereplő tényezőnek is. Vagyis az alábbi oszthatóságok közül legalább az egyiknek teljesülnie kell tetszőleges $[a]_{561}$ redukált maradékosztály esetén:

\begin{aligned}561&|a^{35}-1 \\ 561&|a^{35}+1 \\ 561&|a^{70}+1 \\ 561&|a^{140}+1 \\ 561&|a^{280}+1\end{aligned}

Ez viszont a 20.1. Tétel 3. pontja alapján azt jelenti, hogy teljesülnie kell legalább az egyik alábbi kongruenciának tetszőleges $[a]_{561}$ redukált maradékosztály esetén:

\begin{aligned}a^{35}&\equiv +1\pmod{561} \\ a^{35}&\equiv -1\pmod{561} \\ a^{70}&\equiv -1\pmod{561} \\ a^{140}&\equiv -1\pmod{561} \\ a^{280}&\equiv -1\pmod{561} \end{aligned}

Más megfogalmazásban ez azt jelenti, hogy amennyiben találunk egy olyan $[a]_{561}$ redukált maradékosztályt, amely esetén a fenti kongruenciák közül egyik sem teljesül, akkor az $n=561$ biztosan nem lehet prím. Egy ilyen maradékosztály tehát "leleplezi", vagy "tanúsítja" az $n=561$ összetettségét.

Vizsgáljuk meg például a $[2]_{561}$ redukált maradékosztályt, azaz legyen $a=2$ . A 21.4. szakaszban ismertetett ismételt négyzetreemelések módszerével viszonylag gyorsan leellenőrizhetjük a kérdéses kongruenciákat. Az alábbi eredményeket fogjuk kapni:

\begin{aligned}2^{35} \equiv 263 \ &\cancel{\equiv}\ +1\pmod{561} \\ 2^{35} \equiv 263 \ &\cancel{\equiv}\ -1\pmod{561} \\ 2^{70}\equiv 166 \ &\cancel{\equiv}\ -1\pmod{561} \\ 2^{140}\equiv 67 \ &\cancel{\equiv}\ -1\pmod{561} \\ 2^{280}\equiv 1 \ &\cancel{\equiv}\ -1\pmod{561} \end{aligned}

Minthogy egyetlen kongruencia sem teljesül, ezért az eddigi okfejtés alapján az $n=561$ Carmichael-szám biztosan összetett, azaz megbukott a Miller-Rabin-prímteszten.

Az eljárás általános megfogalmazásához most bevezetünk egy új tanú-fogalmat.

23.9. Definíció (Miller-Rabin-tanú):

Legyen $n\gt 1$ egy tetszőleges páratlan, $a$ pedig tetszőleges $n$ -hez relatív prím egész szám. Képezzük továbbá azt az $e\geq 1$ kitevőt és $k\geq 1$ páratlan számot, amelyekre teljesül az alábbi:

n-1=2^e\cdot k

Valamint tegyük fel, hogy az alábbi kongruenciák közül egyik sem teljesül:

\begin{aligned}a^k&\equiv +1\pmod n \\ a^k&\equiv -1\pmod n \\ a^{2k}&\equiv -1\pmod n \\ a^{4k}&\equiv -1\pmod n \\ &\vdots \\ a^{2^{e-1}\cdot k}&\equiv -1\pmod n\end{aligned}

Ekkor az $a$ egész szám által reprezentált $[a]_n$ maradékosztályt az $n$ egész szám Miller-Rabin-tanújának nevezzük. Amennyiben $a$ -ra teljesül a fenti kongruenciák közül legalább az egyik, akkor az $[a]_n$ maradékosztályt Miller-Rabin-nemtanúnak nevezzük. Ha $n$ összetett, akkor az ő Miller-Rabin-nemtanúit Miller-Rabin-cinkosoknak nevezzük.

Megnézem a tudásbázisban

♣

Megjegyzés:

A Fermat-tanúkhoz hasonlóan ebben az esetben is teljes maradékosztályokról célszerű beszélni. Ha ugyanis egy $b$ egész szám $a$ -val azonos maradékosztályban van, akkor teljesül az $a\equiv b\pmod n$ kongruencia, és így a 20.2. Tétel 6. pontja alapján teljesülnek az alábbi kongruenciák is:

\begin{aligned}a^k&\equiv b^k\pmod n \\ a^{2k}&\equiv b^{2k}\pmod n \\ a^{4k}&\equiv b^{4k}\pmod n \\ &\vdots \\ a^{2^{e-1}\cdot k}&\equiv b^{2^{e-1}\cdot k}\pmod n\end{aligned}

Mármost e kongruenciák baloldalai pontosan akkor kongruensek a definícióban szereplő $+1$ és $-1$ számokkal, amikor a jobboldalaik is. Így tehát az $[a]_n$ maradékosztálynak vagy minden eleme teljesíti a Miller-Rabin-tanúkkal szemben támasztott kritériumokat, vagy egyik sem.

Szintén a Fermat-tanúkhoz hasonlóan itt is önkényesen kikötöttük, hogy $[a]_n$ egy redukált maradékosztály. Ennek terminológiai indoklása szóról szóra megegyezik a 23.3. Definíció utáni megjegyzésben leírtakkal.

Ugyanakkor megjegyezzük, hogy minden Miller-Rabin-nemtanú Fermat-nemtanú is egyben – és így a 23.3. Definíció utáni megjegyzés alapján szintén csak redukált maradékosztály lehetne az említett megszorítás nélkül is. Ilyenkor ugyanis a definícióban szereplő Miller-Rabin-kongruenciák közül teljesül legalább az egyik. Ez a 20.1. Tétel 3. pontja alapján azt jelenti, hogy $n$ osztója az alábbi kifejezések közül legalább az egyiknek:

\begin{aligned}&a^k-1 \\ &a^k+1 \\ &a^{2k}+1 \\ &a^{4k}+1 \\ &\vdots \\ &a^{2^{e-1}\cdot k}+1\end{aligned}

Ám e kifejezések szorzata a 23.8. Tétel alapján épp $a^{n-1}-1$ , aminek a 16.2. Tétel 7. pontja miatt $n$ szintén osztója. Ez ismét a 20.1. Tétel 3. pontja alapján azt jelenti, hogy teljesül az $a^{n-1}\equiv 1\pmod n$ kongruencia, és így $[a]_n$ valóban Fermat-nemtanú. Másként fogalmazva ez azt jelenti, hogy minden Fermat-tanú egyúttal Miller-Rabin-tanú is, vagyis az új definíció valóban tágítani igyekszik az $n$ összetettségét igazoló tanúk körét.

**23.5. ábra:** A Miller-Rabin-nemtanúk elhelyezkedése

Megnézem a tudásbázisban

♣

Felmerül a kérdés, hogy vajon a tanú-fogalom kiszélesítését nem vittük-e túlzásba. Azaz nem lehetséges-e, hogy ha Fermat-tanúja nem is, de Miller-Rabin-tanúja már lehet esetleg prímszámoknak is. Az alábbi tétel szerint szerencsére nem ez a helyzet.

23.10. Tétel:

Semmilyen $1$ -nél nagyobb páratlan prímszámnak nincs Miller-Rabin-tanúja. Másként fogalmazva ha egy $1$ -nél nagyobb $n$ páratlan számnak van Miller-Rabin-tanúja, akkor $n$ összetett.

Megnézem a tudásbázisban

♣

Bizonyítás:

Legyen $n\gt 1$ egy tetszőleges páratlan prímszám, továbbá legyen adva egy tetszőleges $[a]_n$ redukált maradékosztály. Képezzük azt az $e\geq 1$ kitevőt és $k\geq 1$ páratlan egész számot, amelyekre teljesülnek az alábbiak:

n-1=2^e\cdot k

Mivel $n$ prím, továbbá $a$ és $n$ relatív prímek – hiszen $[a]_n$ redukált –, ezért a kis Fermat-tétel alapján teljesül rá az alábbi kongruencia:

a^{\overbrace{2^e\cdot k}^{=n-1}}\equiv 1\pmod n

Ez a 20.1. Tétel 3. pontja értelmében azt jelenti, hogy teljesül az alábbi oszthatóság:

n|a^{2^e\cdot k}-1

Az oszthatóság jobboldalán szereplő kifejezést a 23.8. Tétel szerint szorzatra bonthatjuk:

n|(a^k-1)\cdot (a^k+1)\cdot (a^{2k}+1)\cdot (a^{4k}+1)\cdot \ldots \cdot (a^{2^{e-1}k}+1)

Mivel $n$ prím, ezért a 16.13. Definíció utáni megjegyzés szerint legalább az egyik jobboldali tényezőnek osztója kell legyen. Azaz az alábbi oszthatóságok közül legalább az egyiknek teljesülnie kell:

\begin{aligned}n&|a^k-1 \\ n&|a^k+1 \\ n&|a^{2k}+1 \\ n&|a^{4k}+1 \\ &\vdots \\ n&|a^{2^{e-1}k}+1 \end{aligned}

A 20.1. Tétel 3. pontja alapján ez tehát azt jelenti, hogy legalább az egyik kongruenciának teljesülnie kell az alábbiak közül:

\begin{aligned}a^k\equiv +1\pmod n \\ a^k\equiv -1\pmod n \\ a^{2k}\equiv -1\pmod n \\ a^{4k}\equiv -1\pmod n \\ &\vdots \\ a^{2^{e-1}k}\equiv -1\pmod n \end{aligned}

Ez viszont a 23.9. Definíció szerint épp azt jelenti, hogy az $[a]_n$ maradékosztály Miller-Rabin-nemtanú.

Megnézem a tudásbázisban

∎

Ezekután ismertetjük a Miller-Rabin-prímtesztet, amely tehát a Fermat-prímtesztnek a továbbfejlesztett változata. Az algoritmus bemenete egy $n\gt 1$ páratlan egész szám, amelyről el kellene dönteni, hogy prím-e vagy összetett:

Válasszunk véletlenszerűen egy tetszőleges $1$ és $n$ közötti $a$ egész számot, azaz legyen $1\lt a\lt n$ .
A 17.18. Tétel bizonyításában ismertetett euklidészi algoritmus segítségével számítsuk ki az $(a,n)$ kitüntetett közös osztót. Ha ennek értéke $1$ , akkor folytassuk az eljárást a 3. lépéstől. Egyébként az algoritmus leáll a következő válasszal: az $n$ egész szám biztosan összetett, és az egyik osztója $(a,n)$ .
Képezzük azt az $e\geq 1$ kitevőt és $k\geq 1$ páratlan számot, amelyre $n-1=2^e\cdot k$ teljesül.
A 21.4. szakaszban ismertetett ismételt négyzetreemelések módszerével ellenőrizzük le, hogy $a$ -ra teljesül-e legalább az egyik a 23.9. Definícióban felsorolt kongruenciák közül.
Amennyiben nem teljesül egyetlen kongruencia sem, akkor az algoritmus leáll a következő válasszal: az $n$ egész szám biztosan összetett, de nem találtuk meg egyetlen osztóját sem.
Amennyiben teljesül legalább az egyik kongruencia, akkor az algoritmus a következő válasszal áll le: az $n$ egész szám "valószínűleg" prím.

Már megint csak "valószínűleg" prím? – kérdezhetné teljes joggal az Olvasó. Látszólag valóban nem kerültünk közelebb a prímek azonosításához, hiszen ismét csak összetett számokat tudunk egyértelműen leleplezni. Ha azonban szerencsétlenül épp egy olyan maradékosztályt sikerült kihúzni a kalapból, amely Miller-Rabin-nemtanú, akkor ismét csak annyit mondhatunk, hogy a kérdéses szám "valószínűleg" prím.

Ez valóban így van, azonban a Fermat-prímteszthez hasonlóan itt is megtehetjük, hogy többször húzunk a kalapból. Ezen túlmenően a 23.9. Definíció utáni megjegyzés alapján egy adott $n$ -hez tartozó Miller-Rabin-tanúk köre biztosan nem szűkebb, mint az ugyanezen $n$ -hez tartozó Fermat-tanúk köre. Sőt, azt is láthattuk, hogy az $n=561$ -nek egyáltalán nincs Fermat-tanúja, hiszen Carmichael-számról van szó. Ezzel szemben például a $[2]_{561}$ maradékosztály "lebuktatja" ezt a számot is, hiszen ő egy Miller-Rabin-tanú, amely bizonyítja az $561$ összetettségét.

Úgy tűnik tehát, mintha a Miller-Rabin-prímteszt elől még a Carmichael-számok sem tudnának "elbújni", ami kétségkívül hatalmas előrelépés. De vajon tényleg nem léteznek univerzális álprímek erre a tesztre nézve? Sajnos ahhoz, hogy ezt megválaszolhassuk, az absztrakt algebra egy rendkívül fontos ágának, az úgynevezett csoportelméletnek az eszköztárára lesz szükségünk. Így ezt csak a következő fejezetben tudjuk majd igazolni.

Most azonban térjünk vissza egy kicsit az RSA kulcsgenerálás kérdésköréhez. Nem árt ugyanis, ha felhívjuk Alice és Bob figyelmét néhány fontos dologra, amire vigyázniuk kell, ha nem akarják, hogy Eve és Mallory borsot törjön az orruk alá.

23.6A Fermat-faktorizáció

Az RSA implementációja során sok apró részleten múlhat a biztonság. Számos hatékony támadás ismert ugyanis, amelyek az üzenethalmaz, a kulcsgeneráláshoz használt prímek, valamint a kódoló és dekódoló kulcs nem elég körültekintő megválasztását használják ki. Ezt néhány példán keresztül illusztráljuk, amelyek közül az első az úgynevezett Fermat-faktorizációs algoritmus.

Ez az eljárás bizonyos körülmények között lehetővé teszi egy támadó számára, hogy hatékonyan kiszámíthassa a kódoláshoz és dekódoláshoz használt $n$ modulus prímtényezőit, és így tulajdonképpen ő maga is a titkos kulcs birtokába juthasson. Erre akkor nyílik lehetősége, ha a prímtényezők közötti különbség nem eléggé nagy. Ebben az esetben a két prímtényező közel van a 23.2. Tételben szereplő $r$ számhoz. Ez ugye a legnagyobb olyan egész szám, amelynek négyzete még éppen nemnagyobb $n$ -nél. Így ennek a környékén jó eséllyel hamar megtalálhatjuk a prímtényezőket. Az erre szolgáló alább ismertetett módszer magától Pierre de Fermat-tól származik, amely a 23.8. Tétel bizonyításának elején már említett $x^2-y^2 = (x+y)\cdot (x-y)$ összefüggésen alapul.

Képzeljük magunkat Eve helyébe, és tegyük fel, hogy az $n=57\ 319\ 249\ 499$ RSA modulus prímtényezőit szeretnénk megtalálni. Azaz keressük azokat a $p$ és $q$ prímszámokat, amelyekre teljesül az alábbi egyenlet – itt nyugodtan feltételezhetjük, hogy $p\gt q$ , ha pedig mégsem, akkor nevezzük el őket fordítva:

n=p\cdot q

Ez első látásra reménytelennek tűnik, azonban abban bízhatunk, hogy az ismeretlen $p$ és $q$ prímtényezőket a kulcsgeneráláskor óvatlanul választották ki, és a különbségük kicsi. Most megmutatjuk, hogy mindig léteznek olyan $a$ és $b$ egész számok, amelyeknek összege $p$ -vel, különbsége pedig $q$ -val egyenlő. Azaz:

\begin{aligned}p&=a+b \\ q&=a-b\end{aligned}

Adjuk össze, és vonjuk ki egymásból a két egyenletet:

\begin{aligned}p+q&=2a \\ p-q&=2b\end{aligned}

Mivel $p$ és $q$ is biztosan páratlan – hiszen a $2$ az egyetlen páros prímszám – ezért a fenti két egyenlet baloldalán álló $p+q$ összeg és $p-q$ különbség biztosan páros, azaz osztható $2$ -vel. A keresett $a$ és $b$ egész számok tehát valóban léteznek. Ekkor a fentebb említett összefüggés alapján:

n=(\underbrace{a+b}_{=p})\cdot (\underbrace{a-b}_{=q})=a^2-b^2

Ha valóban igaz a feltételezésünk, miszerint a két prímszám egymáshoz közel van, akkor a $p-q=2b$ összefüggés alapján $b$ kicsi. Ha viszont $b$ kicsi, akkor a négyzete is kicsi, amit az $n=a^2-b^2$ összefüggés jobboldaláról elhanyagolhatunk. Azaz feltételezhetjük, hogy a keresett $a$ közel lesz a 23.2. Tételben szereplő $r$ számhoz, ami ugye a legnagyobb olyan egész szám, amelynek a négyzete nemnagyobb $n$ -nél. Ha most az $n=a^2-b^2$ összefüggésből kifejezzük $b^2$ -et, akkor az alábbit kapjuk:

b^2=a^2-n

Feladatunk $a$ megkeresése. Azt tudjuk, hogy $r$ környékén van, ezért innen kiindulva elkezdünk tippelni mindaddig, míg a jobboldali kifejezésre nem négyzetszámot kapunk. A fenti példában tehát $n=57\ 319\ 249\ 499$ . Ekkor $r=239\ 414$ , mivel ez az a legnagyobb egész szám, amelynek a négyzete még nemnagyobb $n$ -nél. Ebből kiindulva adunk tippeket $a$ -ra, és vizsgáljuk, hogy az $a^2-n$ négyzetszám-e:

\begin{array}{c|c|c}a & a^2-n & \text{négyzetszám?} \\ \hline 239\ 415 & 292\ 726 & \text{nem} \\ 239\ 416 & 771\ 557 & \text{nem} \\ 239\ 417 & 1\ 250\ 390 & \text{nem} \\ 239\ 418 & 1\ 729\ 225 & \text{igen} \end{array}

Meglepően gyorsan, mindössze $4$ lépés után négyzetszámot kaptunk a második oszlopban, amely tehát $b^2$ -tel egyezik meg. Ebből $b=1315$ adódik, és mivel $a$ -t is sikerült megtippelnünk, végülis megkaptuk a két prímtényezőt is:

\begin{aligned}p&=a+b=239\ 418 + 1315 = 240\ 733 \\ q&=a-b=239\ 418 - 1315=238\ 103\end{aligned}

Látható, hogy eléggé hatékonyan sikerült prímtényezőire bontani a bemeneti számunkat. Mostmár látszik is, hogy miért: a két prím különbsége mindössze $2630$ volt, ami nagyon kicsi a két prímhez képest.

Amikor tehát Alice és Bob RSA kulcspárt generálnak maguknak, vigyázniuk kell, hogy a kiválasztott prímszámok átlagosan az őket leíró bitek felében különbözzenek egymástól. Ezzel viszonylag hamar elvehetik Eve kedvét a fenti eljárástól, a keresett $a$ ugyanis ebben az esetben nagyon messze lesz $r$ -től, amelyet így az idők végezetéig keresgélhet.

23.7A kicsi kódoló kulcsok problémája

A 22.6. szakaszban a RSA dekódolás gyorsítási lehetőségei kapcsán megemlítettük, hogy az RSA biztonsága nem függ a publikus $e$ kódoló kitevő megválasztásától. Az ismételt négyzetreemelések módszerét vizsgálva a 21.4. szakaszban megállapítottuk, hogy célszerű olyan kitevőt választani, amelynek bináris számábrázolásában kevés számú $1$ -es bit szerepel. Emiatt racionális megfontolásnak tűnhet, ha a megvalósítás során úgy döntünk, hogy egy viszonylag alacsony számtartományból választjuk ki a rendszer felhasználóihoz tartozó $e$ publikus kitevőket a kulcsgenerálás során. Ez azonban bizonyos körülmények között a nyílt üzenet kiszámítására adhat lehetőséget egy támadó számára anélkül, hogy feltörné az eljárást.

Tegyük fel ugyanis, hogy egy sokfelhasználós rendszerről van szó, és kicsi az a számtartomány, amelyből kisorsoljuk a felhasználók számára a publikus $e$ kitevőt. Ekkor előfordulhat, hogy több felhasználó is ugyanazt a kitevőt kapja. Tegyük fel, hogy $k$ darab felhasználó kapta ugyanazt az $e$ kitevőt. Szerencsétlen, ugyanakkor nem túl ritka esetekben még az is megeshet, hogy $e\leq k$ is teljesül. Ez látszólag nem jelent problémát, hiszen természetesen más és más prímpárokat sorsolunk hozzájuk, tehát e $k$ darab felhasználóhoz különböző modulusok és dekódoló kitevők fognak tartozni.

Képzeljük el azonban, hogy valaki egy bizalmas körlevelet küld felhasználók egy csoportjának, amelybe történetesen a fenti $k$ darab felhasználó is beletartozik. Ebben az esetben tehát az $x$ nyílt szöveg ugyanaz lesz. A küldő fél egyenként előkeresi a publikus kulcstárból a címzettek publikus kulcsait, és mindenki számára egyedileg kódolja az üzenetet a 21. fejezetben leírt módon.

A szerencsétlenül járt $k$ darab felhasználónak kiküldött $y_1$ , $y_2$ , ..., $y_k$ rejtett üzenetekből a támadó az alábbi kongruenciarendszert tudja felírni:

\begin{aligned}y_1&\equiv x^e\pmod{m_1} \\ y_2&\equiv x^e\pmod{m_2} \\ &\vdots \\ y_k&\equiv x^e\pmod{m_k}\end{aligned}

Ebben a kongruenciarendszerben a támadó számára egyedül az $x$ nyílt üzenet ismeretlen, hiszen a felhasználókhoz tartozó $e$ kitevő és a modulusok számára is elérhetők a publikus kulcstárból, az $y_1$ , $y_2$ , ..., $y_k$ rejtett üzeneteket pedig a kommunikációs csatorna lehallgatásával ismeri meg. Most megmutatjuk, hogy a támadó a fent ismertetett szerencsétlen körülmények fennállása esetén ebből a kongruenciarendszerből egy pillanat alatt megkaphatja az $x$ nyílt üzenetet.

Azt mindjárt az elején feltehetjük, hogy az $m_1$ , $m_2$ , ..., $m_k$ modulusok páronként relatív prímek. Ezek ugyanis véletlenszerűen sorsolt prímpárok szorzataiként állnak elő, így annak gyakorlatilag nincs esélye, hogy van közöttük két olyan, amelyeknek közös legalább az egyik prímtényezője. Emlékeztetnénk az olvasót a kínai maradéktételhez kapcsolódó 22.3. Tételre, valamint a 22.4. Tételre, amelyek így már alkalmazhatók.

Ezek többszöri alkalmazásával azt kapjuk, hogy a $\Z/m_1\Z \times \Z/m_2\Z \times \ldots \times \Z/m_k\Z$ szorzatgyűrű elemei kölcsönösen egyértelmű megfeleltetésben állnak a $\Z/m_1m_2\ldots m_k\Z$ maradékosztálygyűrű elemeivel. A fenti kongruenciarendszer a szorzatgyűrűben tulajdonképpen az alábbi elemet írja le:

([x^e]_{m_1};[x^e]_{m_2};\ldots;[x^e]_{m_k})

Ennek a $\Z/m_1m_2\ldots m_k\Z$ maradékosztálygyűrűben a 22.4. Tétel alapján az alábbi maradékosztály felel meg:

[x^e]_{m_1m_2\ldots m_k}

Tegyük fel, hogy az $x$ nyílt üzenetet a küldő az előkódolás során szerencsétlenül úgy választotta meg, hogy az $0$ és a legkisebb modulus közé essen. Az előkódolásról a 21.8. szakaszban írtunk bővebben. Teljesülnek tehát az alábbi egyenlőtlenségek:

\begin{aligned}0\leq x &\lt m_1 \\ 0\leq x&\lt m_2 \\ &\vdots \\ 0\leq x &\lt m_k\end{aligned}

Mivel azt mondtuk, hogy szerencsétlen módon az $e\leq k$ egyenlőtlenség is fennáll, ezért ebben az esetben nyilván teljesül az alábbi is:

0\leq x^e \lt m_1m_2\ldots m_k

Így a támadó valójában az $[x^e]_{m_1m_2\ldots m_k}$ maradékosztály legkisebb nemnegatív reprezentánselemét kapja meg, amely nem más, mint a nyílt üzenetnek ténylegesen az $e$ -edik hatványa – és nem pedig annak modulo megfelelője. Ebből viszont az $x$ nyílt üzenetet már egyszerűen megkaphatja.

Alice-nak és Bob-nak tehát azt javasolhatjuk, hogy a kulcsgeneráláskor semmiképpen se korlátozzák az $e$ kitevőt egy szűk számtartományra, nehogy a fenti kellemetlenségben legyen részük. A kódolás gyorsasága szempontjából a lényeg úgyis az, hogy kevés számú $1$ -es legyen $e$ bináris ábrázolásában, nem pedig az, hogy ő maga kicsi legyen. Ezen túlmenően amikor ugyanazt az üzenetet nagyszámú résztvevőnek továbbítjuk, akkor célszerű az üzenet egyes példányaiba valamilyen véletlentől függő elemet is belevinni. Például megtehetjük, hogy az utolsó valahány biten hasznos tartalom helyett elhelyezünk egy véletlenszámot.

Ennek az az előnye, hogy így az eredeti $x$ üzenet egyes példányai különböző kódolandó nyílt üzenetekké válnak, amivel a fenti támadás lehetőségét egycsapásra kiiktattuk. Természetesen ekkor a küldő és fogadó félnek meg kell egyezniük egymással, hogy melyek lesznek a haszontalan bitek.

23.8Közös modulus választásának hibája

Végül egy nagyon súlyos potenciális rendszertervezési hibára hívnánk fel a figyelmet. Mivel az RSA meglehetősen számításigényes, ezért csábító lehet az a gondolat, hogy a teljes rendszer számára egyetlen $m$ modulust generálunk, és csak az egyes felhasználókhoz tartozó $e$ publikus és $d$ titkos kitevők lesznek különbözőek a kulcsgenerálás során. Ez látszólag előnyös lehet, hiszen így például előre le tudunk gyártatni egy célhardvert, amely a modulo $m$ maradékosztálygyűrűben való számolásra van optimalizálva.

Képzeljük el, hogy az előző szakaszhoz hasonlóan ismét egy közös $x$ üzenet – például egy körlevél – érkezik mondjuk két felhasználóhoz. Tegyük fel, hogy e két felhasználóhoz az $e_1$ és $e_2$ publikus kitevők vannak rendelve. Nagy az esély rá, hogy e két kitevő egymáshoz relatív prím – azaz $(e_1,e_2)\sim 1$ –, és ebben az esetben egy támadó sajnos meg tudja fejteni az $x$ nyílt üzenetet. Ő ugyanis az alábbi kongruenciákat írhatja fel:

\begin{aligned}y_1&\equiv x^{e_1}\pmod m \\ y_2&\equiv x^{e_2}\pmod m\end{aligned}

Ebben a kongruenciarendszerben a támadó számára ismét egyedül az $x$ nyílt üzenet ismeretlen, hiszen az összes többi paraméter a nyilvános kulcstárból, valamint a kommunikációs csatorna lehallgatásával megismerhető. Nézzük, hogy mihez kezd mindezzel a támadó. A Bézout-lemmából tudjuk, hogy bármely két egész szám kitüntetett közös osztója kifejezhető a két szám lineáris kombinációjaként. Ezt jelen esetben az $e_1$ és $e_2$ kitevőkre alkalmazhatjuk.

Mivel róluk azt mondtuk, hogy relatív prímek – azaz $(e_1,e_2)\sim 1$ –, ezért a Bézout-lemma alapján léteznek olyan $u$ és $v$ egész számok, amelyekre teljesül az alábbi:

(e_1,e_2)\sim 1=ue_1 + ve_2

Ráadásul a támadó a keresett $u$ és $v$ egész számokat hatékonyan elő tudja állítani a kibővített euklidészi algoritmus segítségével, amelyről a 21.1. szakaszban volt szó részletesen. Most vizsgáljuk meg, hogy a kiszámított $u$ és $v$ egész számokból, valamint a kommunikációs csatornán elfogott $y_1$ és $y_2$ kódszövegekből képzett alábbi kifejezés mivel kongruens modulo $m$ :

y_1^uy_2^v \equiv\ ?\pmod m

Mivel $y_1\equiv x^{e_1}\pmod m$ és $y_2\equiv x^{e_2}\pmod m$ az RSA kódolás alapján, ezért a kongruencia tulajdonságairól szóló 20.2. Tétel 6. és 4. pontjait alkalmazva ezt kapjuk:

(\underbrace{x^{e_1}}_{\equiv y_1})^u\cdot (\underbrace{x^{e_2}}_{\equiv y_2})^v \equiv \ ?\pmod m

A baloldali kifejezést a hatványozás azonosságairól szóló 18.8. Tétel 2. és 3. pontjai alapján átírhatjuk az alábbi módon:

x^{ue_1 + ve_2}\equiv \ ?\pmod m

A Bézout-lemma alapján a kitevőről viszont már tudjuk, hogy az az $(e_1,e_2)\sim 1$ kitüntetett közös osztóval egyezik meg, azaz teljesül az alábbi:

x^{\overbrace{ue_1 + ve_2}^{=1}}\equiv x\pmod m

A támadó tehát pusztán publikusan, illetve a csatorna lehallgatása által megszerezhető információkból ki tudja számítani az $x$ nyílt szöveget anélkül, hogy feltörte volna az RSA eljárást. A fentiek alapján ugyanis nincs más dolga, mint kiszámítani az $y_1^uy_2^v$ kifejezést, amely tehát biztosan az $x$ nyílt üzenettel lesz kongruens modulo $m$ .

Felhívnánk a figyelmet azonban egy apró "csalásra", amelyet a fenti okfejtésben elkövettünk. Vizsgáljuk meg ugyanis jobban a Bézout-lemmából kapott $ue_1 + ve_2=1$ egyenletet. Mivel itt az $e_1$ és $e_2$ kitevők mindketten pozitívak, ezért ebből következik, hogy $u$ és $v$ közül pontosan az egyik szükségképpen negatív. Ők viszont a fenti $y_1^uy_2^v$ kifejezésben kitevőkként szerepelnek. Márpedig ebben az esetben elvileg nem használhatnánk a hatványozás azonosságairól szóló 18.8. Tételt és a kongruencia tulajdonságairól szóló 20.2. Tételt, hiszen ezeket csak pozitív kitevőkre bizonyítottuk. Arról már nem is beszélve, hogy az eddigi definícióink alapján negatív kitevőket egyelőre nem is tudunk értelmezni.

Ezt a kis hiányosságot a 24.5. szakaszban fogjuk pótolni, mivel ehhez fel kell építeni néhány újabb fontos algebrai fogalmat. Ám elöljáróban megjegyezzük, hogy a hatványozás azonosságai és a kongruenciák tulajdonságai ebben a kibővített értelmezésben is érvényben fognak maradni. Így válik majd a fenti érvelés teljessé. Konklúzióként azonban elmondhatjuk, hogy a közös modulus választását mindenképpen el kell kerülni az RSA eljáráson alapuló kriptográfiai rendszerekben.

Ebben a fejezetben tehát főként azzal a problémával foglalkoztunk, hogy hogyan tud Alice és Bob az RSA kulcsgeneráláshoz szükséges óriási prímszámokat találni. Ennek keretében megmutattuk, hogy a hagyományos, osztáspróbákon alapuló módszer a gyakorlatban a lassúsága miatt nem alkalmazható. Ezért bemutattunk két valószínűségi prímtesztet, amelyek a kis Fermat-tételen alapulnak. Az első a Fermat-prímteszt volt, amelynek fő hátránya, hogy léteznek olyan összetett számok, amelyeket nem tud kiszűrni. Ezeket univerzális Fermat-álprímeknek vagy Carmichael-számoknak nevezzük, amelyekről a közelmúltban kimutatták, hogy sajnos végtelen sok van belőlük. Ezt a problémát kiküszöbölendő bemutattuk a Miller-Rabin-prímtesztet, amely – úgy tűnik – kiszűri a Carmichael-számokat is. Végül felhívtuk a figyelmet pár olyan dologra, amelyekre Alice-nak és Bob-nak oda kell figyelniük a kulcsgenerálás során.

A következő fejezetben megismerkedünk az absztrakt algebra talán legfontosabb ágának, az úgynevezett csoportelméletnek az alapjaival. Ezután az így felépített eszközök segítségével igazolni fogjuk, hogy a Miller-Rabin-prímtesztre nézve valóban nem léteznek univerzális álprímek. Végül adunk egy felső korlátot is annak valószínűségére, hogy egy összetett számot tévesen prímmé nyilvánít ez a teszt.

23.1Prímtesztelés osztáspróbákkal

23.1. Tétel:

Bizonyítás:

23.2. Tétel:

Bizonyítás:

23.2A Fermat-prímteszt

23.3. Definíció (Fermat-tanú):

Megjegyzés:

23.4. Lemma:

Bizonyítás:

23.5. Lemma:

Bizonyítás:

23.6. Tétel:

Bizonyítás:

23.3„Valószínűleg” prím?!

23.4Univerzális álprímek

23.7. Definíció (Carmichael-számok):

23.5A Miller-Rabin prímteszt

23.8. Tétel:

Bizonyítás:

23.9. Definíció (Miller-Rabin-tanú):

Megjegyzés:

23.10. Tétel:

Bizonyítás:

23.6A Fermat-faktorizáció

23.7A kicsi kódoló kulcsok problémája

23.8Közös modulus választásának hibája

Iratkozz fel a hírlevelünkre