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

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.

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

Egyrészt, mivel n\neq 0, ezért a 16.2. Tétel 4. pontja alapján k és l egyike sem lehet 0. Másrészt, mivel a fenti felbontás ugye nemtriviális, ezért egyikük sem lehet egység, továbbá egyikük sem lehet asszociáltja n-nek. Harmadrészt, indirekt feltevésünk miatt egyikük sem eshet az 1 és az |n|=n közötti számtartományba. Végül negyedrészt a 17.2. Lemma alapján egyikük sem lehet nagyobb n-nél. Összefoglalva tehát k és l mindketten negatívak, határozottan kisebbek -1-nél, továbbá -n-től különbözőek. Ezt mutatja a 23.2. ábra.

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)

A k és l egész számok ellentettjei tehát szintén osztói n-nek, mindketten pozitívak, határozottan nagyobbak 1-nél, továbbá n-től különbözőek. Ezt az alábbi a 23.3. ábra.

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→

∎

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.

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.

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

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.

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.

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.

A 23.4. ábrán a Fermat-nemtanúk elhelyezkedése látható az összes modulo n maradékosztályok között. A Fermat-tanúk pontosan a kiszürkített részben helyezkednek el.

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 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.

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.

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.

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?!

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.

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 á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 á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.

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.

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".

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.

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.

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.

A 23.5. ábrán a Miller-Rabin-nemtanúk és a Fermat-nemtanúk elhelyezkedése látható az összes nemnulla modulo n maradékosztályok között. A Miller-Rabin-tanúk pontosan a kiszürkített részben helyezkednek el.

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.

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.

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.

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.

Í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.

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.

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.