Informatika | Informatikai biztonság » Csink László - A digitális aláírás algoritmusai

A digitális aláírás algoritmikus kérdései Csink László 2001. 2001. Csink László: A digitális aláírásról 1 A hálózati adatbiztonsággal kapcsolatos problémák négy különbözõ, de egymást át is fedõ területre oszthatók: Titkosság: feladata az adatok védelme és kódolása az illetéktelen felhasználókkal szemben. Sértetlenség: feladata annak biztosítása, hogy a küldött és a kapott üzenetet egy külsõ támadó ne változtathassa meg. Hitelesség: feladata a kommunikációban résztvevõ felek személyazonosságának egyértelmû bizonyítása. Ide sorolható a hozzáférés védelem, jogosultság vizsgálata is. Általában jelszavakat menedzselõ, ellenõrzõ és hozzáférési jogosultságot kezelõ részekbõl áll. Letagadhatatlanság: feladata annak biztosítása, hogy a küldõ az eredeti üzenetet a késõbbiek során ne cserélhesse ki egy másikra. 2001. Csink László: A digitális aláírásról 2 A hitelességet és

letagadhatatlanságot azonban csak az applikációs rétegben lehet érdemben kezelni. Az applikációs réteg védelmi eszköze a kriptográfia. A felhasználó terület adat elévülési idejétõl függ, hogy egy adott kriptográfiai rendszer (algoritmusok és protokollok együttese) megbízhatónak mondható-e vagy sem. A kriptográfiai rendszer készítésének legfontosabb szempontjai: • a minél gyorsabb kódolás és dekódolás a küldõ és fogadó oldaláról és • a minél nehezebb visszafejthetõség az esetleges támadókkal szemben. A sebesség a nagy adatmennyiségnél igazán érdekes. 2001. Csink László: A digitális aláírásról 3 Forrás: Katonáné Hanák Zsuzsa: Hálózati adatvédelem az applikációs rétegben, BMF NIK AII szakdolgozat, Budapest, 2001, 7. oldal 2001. Csink László: A digitális aláírásról 4 A letagadhatatlanság és a sértetlenség biztosítását az egyirányú hash függvények segítségével, az úgynevezett MDC

(Modification Detection Code) hash-ek használatával oldják meg Ld.: http://compscimathkltehu/bognar/adatsz/konyv5html RSA algoritmus A nyilvános kulcsú rejtjelezés legelterjedtebb módszere az RSA algoritmus. Ez az algoritmus egy matematikai tételen, Fermat kis tételén alapul. E szerint a tétel szerint ha p prímszám, és nem osztója egy a egésznek, akkor a(p-1)-1 osztható p-vel. A tétel alapján, ha p és q különbözõ prímszámok, és a-nak egyik sem osztója, akkor mind p, mind pedig q osztója a(p-1)(q-1)-1-nek, ami képlettel leírva: qp | a(p-1)(q-1)-1 2001. Csink László: A digitális aláírásról 5 Fermat kis tétele tehát: Ha p prímszám, és nem osztója egy a egésznek, akkor a(p-1) -1 osztható p-vel. A következõ két tételt fogjuk felhasználni a bizonyításban VI. tétel Ha egy szám osztója egy szorzatnak, de az egyik tényezõhöz relatív prím, akkor a másik tényezõnek osztója. VII. tétel Ha egy szám relatív prím az a1, a2, ,

ah számok mindegyikéhez, akkor a szorzatukhoz is relatív prím. 2001. Csink László: A digitális aláírásról 6 A Fermat tétel bizonyítása abból fog állni, hogy megvizsgáljuk sorra az a, 2a, ., (p-1)a számok maradékát p-vel való osztásnál: legyen ka=p qk + rk, 0<= rk <p (k=1,2,.,p-1) Egyik rk sem lehet nulla, mert k nem osztható p-vel, s így relatív prím hozzá, a-ra feltétel szerint ugyanaz áll, s így a VII. tétel szerint ka is relatív prím p-hez. Az összes maradékok különböznek egymástól. Legyen ugyanis k1 > k2 és vonjuk ki a k1 -edik egyenletbõl a k2 -ediket: (k1 – k2)a=p(q k1 - q k2)+(rk1 - rk2 ). Itt a (k1 – k2) szám p-nél kisebb pozitív egész, és így a bal oldal az elõbbiekhez hasonló okoskodás szerint nem osztható p-vel, tehát rk1 - rk2 sem lehet 0. 2001. Csink László: A digitális aláírásról 7 Az r1,r2,.,rp-1 számok tehát az 1,2,,p-1 számok közül kerülnek ki, és nincs köztük két

egyenlõ. Ebbõl viszont az következik, hogy valamilyen sorrendben az 1,2,.,p-1 számok mindegyike elõfordul közöttük. Szorozzuk össze most az egyenlõségeinket és vizsgáljuk meg a jobb oldalt. Itt, ha tagonként beszorzunk, az r1,r2,,rp-1 tagon kívül csupa p-vel osztható tag keletkezik, e tag pedig utolsó megállapításunk szerint (p-1)!-sal egyenlõ. Ilyen alakú egyenlõséget kapunk tehát: (p-1)! ap-1 =p Q +(p-1)! ahol Q valamilyen egész szám. 2001. Csink László: A digitális aláírásról 8 Ezt úgy is mondhatjuk, hogy (p-1)! (ap-1 -1) osztható p-vel. (p-1)! azonban relatív prím p-hez a VII tétel értelmében, mert mindegyik tényezõje relatív prím hozzá. Így a VI tétel szerint ap-1 -1 osztható p-vel, és ezt akartuk bizonyítani. 2001. Csink László: A digitális aláírásról 9 Térjünk vissza az RSA algoritmushoz. Ott tartottunk, hogy ha p és q különbözõ prímszámok, és a-nak egyik sem osztója, akkor mind p, mind pedig q

osztója a(p-1)(q-1)-1-nek, ami képlettel leírva: qp | a(p-1)(q-1)-1 Ez valójában nem más, mint a Fermat tétel, csak a tételbeli képletben a helyére egyszer ap-1, egyszer pedig aq-1 kerül rendre a q-val, illetve p-vel való oszthatóságot felírva. Mivel p és q különbözõ prímek, ezért a szorzatukkal is osztható a(p-1)(q-1)-1. Legyen n=qp Ekkor a(p-1)(q-1)+1 pont a maradékot ad n-nel osztva, ha a kisebb, mint n. 2001. Csink László: A digitális aláírásról 10 Alkalmazzuk a fentieket. Legyen ef=(p-1)(q-1)+1 szorzat alakban feírva. Ekkor az aef mod n = a egyenlethez jutottunk, ahol a mod a maradékképzést jelenti. Legyen a nyilvános kulcs az e,n számpáros, a titkos kulcs pedig az f szám. A kódolás során az üzenetet elõször számokká alakítjuk olyan módon, hogy a számok mindegyike kisebb legyen mint n. Ezután az egyes m számokat az M=me mod n képlettel kódoljuk elõállítva a rejtjelezett M üzenetet, és ezt az üzenetet az m=Mf mod n

képlet alapján lehet dekódolni. 2001. Csink László: A digitális aláírásról 11 Hogyan lehetne megfejteni az f visszafejtõ kódot? Ha n és e ismert, és megkeressük a lehetséges p és q prímket, melyekre n = pq, akkor az ef=(p-1)(q-1)+1 egyenletbõl f meghatározható. A célunk tehát az, hogy n = pq alapján p és q meghatározása legalábbis nehéz legyen, azaz olyan hosszú ideig tartson, amely már a titokfejtõnek nem éri meg. Ez akkor érhetõ el, ha n nagyon nagy, így p és q meghatározása, azaz a prímfaktorizáció, nagyon sokáig tart. 2001. Csink László: A digitális aláírásról 12 Mint említettük, a prímtényezõs felbontásra pillanatnyilag nem áll rendelkezésre hatékony algoritmus, bár az sem bizonyított, hogy ilyen algoritmus nem létezik. Mivel az alapvetõ aritmetikai mûveletek, mint szorzás, összeadás, hatványozás hatékonyan elvégezhetõek, ezért lehetséges olyan nagy p és q használata, amely esetén n nem

bontható fel szorzattá. A tipikus méret általában bithosszban van megadva, és többnyire kettõhatvány. Ha n 1024 bit hosszú, azt általában katonai célokra is megfelelõnek tartják. 2001. Csink László: A digitális aláírásról 13 RSA megvalósítás adatstruktúrái A megvalósításhoz olyan adatstruktúra kell, amely tetszõlegesen nagy egész számok ábrázolásához alkalmas. Ehhez a következõ adatstruktúrát használjuk: typedef struct number { int n; /* a szám hossza bájtokban. */ int digit[]; /* a szám bájtjai. */ } Number; A számokat ebben az adatstruktúrában binárisan tároljuk. n adja meg a szám hosszát bájtokban, azaz azt, hogy a digit tömb milyen hosszú. digit tárolja a szám bájtjait olyan módon, hogy digit[i] 256 i helyiérték szerint számít. 2001. Csink László: A digitális aláírásról 14 Számok összehasonlítása 1. Az egyéb aritmetikai mûveletekhez szükségünk van arra, hogy számokat össze tudjunk

hasonlítani. Mint a fejlesztés során kiderült: olyan összehasonlító függvényre van szükségünk, amelyik egy a és egy b*256pow számot hasonlít össze. A számítások során ideiglenesen elõállnak olyan számok, amelyeknél a struktúra digit tömbjének végén, azaz a magas helyiértéken nullák vannak. Ezek a számok a számítás további folyamatában normalizálásra kerülnek, azaz a vezetõ nullákat a program levágja. Ez a függvény számít arra, hogy a paraméterei normalizáltak, és arra is, hogy pow nem negatív. 2001. Csink László: A digitális aláírásról 15 Számok összehasonlítása 2. /* Összehasonlítja az a és b*256pow számokat. Visszatérési érték: 1 ha a > b*256pow 0 ha a = b*256pow -1 ha a <b*256pow */ int powerCompare(Number a, Number b, int pow){ register int i,j; Ha valamelyik szám hoszabb, mint a másik, akkor természetszerûen nagyobbnak is kell lennie, hiszen a bevezetõ nullák nem engedélyezettek. if( a->n

> (i=b->n+pow) ) return 1; 2001. Csink László: A digitális aláírásról 16 Számok összehasonlítása 3. Ha viszont a két szám hossza megegyezik akkor az a nagyobb, amelyiknél a nagyobb helyiértékektõl lefelé haladva elõbb találunk nagyobb digitet. Természetesen a helyiértékeket pow bájttal eltolva kell érteni. for( j=b->n ; j-- ; ) if( i=((int)a->digit[pow+j]) - ((int)b->digit[j]) )return i; Ha ezek a helyiértékek mind megegyeznek, akkor b már nem lehet nagyobb, hiszen b minden pow helyiértéknél kisebb digitje nulla. Ha ezen helyiértékek valamelyikén a egy digitje nem nulla, akkor a a nagyobb, for( i=0 ; i digit[i] )return 1; ellenkezõ esetben a két szám megegyezik. return 0; }Hogyan mûködik a program hogyan speciális értékek esetén, például, ha pow nulla. ? 2001. Csink László: A digitális aláírásról 17 Szám hossza Egy szám hosszának a megállapítása egyszerû, ha a szám normalizált, azaz, ha nem

tartalmaz bevezetõ nullákat a magas helyiértékeken. Ellenkezõ esetben, például a normalizáláshoz meg kell keresni a legmagasabb helyiértékû nem nulla digitet. A program a nullát speciális számként értelmezi, amelynek a hossza nulla, bár egy nulla értékû digitet tartalmaz. int Length(Number a){ register int i; i = a->n-1; while( i && (a->digit[i] == 0) )i--; if( a->digit[i] == 0 )return 0; else return i+1; } 2001. Csink László: A digitális aláírásról 18 Szám növelése 1. Ez a függvény az argumentumaként kapott q számot növeli meg a szintén argumentumként kapott egy digites cy értékkel. A visszatérési érték 1 ha minden rendben, és a növelés megtörtént. 0 ha az eredmény nem fér el azon a helyen, ami q számára rendelkezésre áll. q eredeti értékét a növelt értékkel felülírja a függvény, abban az esetben is, ha az eredmény nem fér el q-ban. Ebben az esetben q lefutás utáni értéke nem definiált.

2001. Csink László: A digitális aláírásról 19 Szám növelése 2. int Increment(Number q, int cy){ register int i,acc; cy értéke a ciklus mindenegyes megkezdésekor annyi, amennyivel a 256 i helyiértéken levõ digitet növelni kell. Ezt az értéket a program hozzáadja a digithez, és egy átmeneti helyen tárolja. Ennek az értéknek a 256-od részét kell majd a következõ digithez hozzáadni, míg az aktuális digit új értéke az lesz, ami acc átmeneti tároló alsó bájtjában van. A ciklust addig kell folytatni, amíg van a felsõbb helyiértékû digitekhez hozzáadni való és amíg vannak még digitek. for( i = 0 ; i n && cy ; i++ ){ acc = q->digit[i] + cy; cy = acc / 0x100; q->digit[i] = acc & 0xff; } 2001. Csink László: A digitális aláírásról 20 Szám növelése 3. Ha a ciklus úgy ért véget, hogy még lett volna hozzáadni való a nagyobb helyiértékû digitekhez, de már nincsnenek ilyen digitek, akkor az eredmény

nem fér el a q számára rendelkezére álló helyen. Ha nem, akkor a növelés sikeres volt. if( cy )return 0; else return 1; } 2001. Csink László: A digitális aláírásról 21 Szám csökkentése 1. Csökkenti az argumentumaként kapott számot a szintén argumentumaként kapott bájtos értékkel. A visszatérési érték 1, ha a csökkentés megtörtént, és 0 ha a kapott eredmény negatív lenne. A deklaráció: int Decrement(Number a, int Value){ register int j; 2001. Csink László: A digitális aláírásról 22 Szám csökkentése 2. Ha a legalsó digitje kisebb, mint a levonandó érték, akkor a többi digittel nem is kell törõdni. Ez a leggyakoribb eset a használat során, ezért ennek a külön vizsgálata gyorsítja a programot. if( a->digit[0] >= Value ){ a->digit[0] -= Value; return 1; } 2001. Csink László: A digitális aláírásról 23 Szám csökkentése 3. És most folytassuk az if utasítás másik ágával: else{ Ha nem ez

a helyzet, akkor kölcsön kell vennünk egy bitet az eggyel nagyobb helyiértékû digitbõl. a->digit[0] += 0x100 - Value; A kölcsönvett bitet vissza kell adnunk, azaz levonni egyet a második, harmadik, . digitbõl, mindaddíg, amíg találunk egy olyan digitet, ami pozitív, vagy amíg el nem fogynak a digitek. for( j=1 ; j n ; j++ ){ Ha le lehet vonni a kölcsönvett bitet az aktuális digitbõl, akkor megtesszük, és készen vagyunk, sikeres volt a csökkentés. if( a->digit[j] ){ a->digit[j] --; return 1; } 2001. Csink László: A digitális aláírásról 24 Szám csökkentése 4. Ha nem sikerült, akkor a digit értéke 255 lesz, és az eggyel nagyobb helyiértékû digitbõl kell levonni egyet. a->digit[j] = 0xff;/* 0+0x100-1 is constant. */ } return 0; } } 2001. Csink László: A digitális aláírásról 25 Kivonás 1. Ez a függvény a-mult*b256pow értéket számítja ki. mult egydigites. A visszatérési értéket egy dinamikusan lefoglalt

területen adja vissza a függvény, amelyet a NewNumber fügvénnyel allokál. a és b értéke érintetlen marad Megjegyzés: Nincs ellenõrzés a két szám nagyságára, és az eredmény csak akkor értelmes, ha pozitív. A hívó programrésznek kell a függvény meghívása elõtt ellenõrizni, hogy a>mult*b256pow A felhasznált típusok: u8 és u32 8 illetve 32 bites elõjel nélküli egészek. 2001. Csink László: A digitális aláírásról 26 Kivonás 2. void powerSub(Number a, Number b, int pow, u8 mult){ register int j,lim; register u32 cy0,cy1,mcy0,BB; register u8 *p,q; Bpow(j) nem más, mint b j-edik digitje. Ezt a makrót nyugodtan használhatjuk akkor is, ha j nagyobb, mint b legnagyobb értékes helyiértéke. A sebesség növelése érdekében a megfelelõ digitet a q mutatón keresztül éri el a program, ezért nagyon kell vigyázni, hogy ez a mutató mindig a megfelelõ helyre mutasson. #define Bpow(j) ((u32)(j n+pow ? *q : 0)) #define min(x,y)

((x)<(y)?(x):(y)) 2001. Csink László: A digitális aláírásról 27 Kivonás 3. A különbözõ átviteli változók értéke kezdetkor nulla, és a helyiérték limit a két szám legnagyobb helyiértékének kisebbike. p a sebesség növelése érdekében az a szám mindig aktuális bitjére mutat, míg q ugyanezt teszi b digitjeivel. cy0 = mcy0 = 0; lim = min(a->n , b->n+pow); p = a->digit+pow; j = pow; 2001. Csink László: A digitális aláírásról 28 Kivonás 4. for( q = b->digit ; j n); j++ , p++ , q++ ){ BB felveszi azt az értéket, amit a aktuális digitjébõl le kell vonni. Ez nem más, mint b megfelelõ digitje megszorozva a szorzóparaméterrel, plusz azok az értékek, amelyek túlcsordulás miatt nem lehetett levonni a kisebb digitbõl. BB = Bpow(j)*mult+mcy0+cy0; Ennek a számnak a 256-nál nagyobb részét biztos, hogy nem lehet levonni ebbõl a digitbõl. Ezt majd a következõ ciklusban kell levonni a következõ digitbõl,

természetesen a helyiértéknek megfelelõen csak a 256-od részét. A most levonandó érték pedig az, ami 8 biten elfér. 2001. Csink László: A digitális aláírásról 29 Kivonás 5. mcy0 = BB >> 8; BB &= 0xff; Ha az így keletkezett levonandó érték nem vonható le a aktuális digitjébõl, akkor kölcsön kell venni az egyel nagyobb helyiértékû digitbõl egyet, ez cy1. Ugyanakkor ezt a következõ ciklusban vissza kell majd adni, ez }cy0}. if( ((u32)*p) <((u32)bb) )cy1="POW2 8;" else cy1="0;" *p="(u8)(cy1+((u32)p)-BB);" cy0="!(!cy1);" } Ha itt maradt kölcsönvett bit, akkor a hívó függvény nem ellenõrizte, hogy a kivonás elvégezhetõ. if( cy0 ){ ReportLog(I, " Internal Error in powerSub mult=%d powerCompare=%d", pow, mult,powerCompare(a,b,pow)); } 2001. Csink László: A digitális aláírásról pow=%d, 30 Kivonás 6. Kiszámítjuk az eredmény hosszát. for( j = a->n ; j &&

!a->digit[--j] ; ) continue; j++; a->n = j; return; } 2001. Csink László: A digitális aláírásról 31 Maradék képzés Ez a program elosztja a-t b-vel, és a maradékot adja vissza eredményként. A helyet az eredmény számára a NewNumber függvényen keresztül foglalja le. Ha nincs elég memória, akkor a visszatérési értk NULL Az osztás a szokásos algoritmus alapján történik. A b-t addig toljuk nagyobb helyiértékek felé, amíg még éppen kisebb vagy egyenlõ, mint a. Természetesen a feltolás a memóriában fizikailag nem történik meg, az aktuális eltolás értékét pow változóban tároljuk. Amikor a lehetséges maximális eltolást kiszámítottuk elkezdõdik a levonás. Mivel a számrendszer alapja nem 2, hanem 256, ezért lehet, hogy b felshiftelt értékének multszorosát lehet levonni. mult értékét nem lehet gyorsan kiszámítani, csak biztonságos becslést adni. Amikor ez a becslés megvan, akkor kiszámítjuk amult*b256pow

értékét. (A részletezéstõl a kissé bonyolult algoritmus miatt eltekintünk.) 2001. Csink László: A digitális aláírásról 32 Szorzás 1. A két argumentumaként kapott számot összeszorozza, és az eredményt egy dinamikusan allokált területen tárolva adja vissza. A program kódolása a sebesség optimalizálása miatt egy kicsit kevésbé olvasható, mint az kívánatos lenne egy oktató anyagban. Number Multiply(Number a, Number b){ register int i,j; /* indexeléshez / register Number result; register lNumber accumulator; register u32 cy; register u32 *q; / olyan mutató, amely az index számításokat csökkenti */ register u8 *p,r; 2001. Csink László: A digitális aláírásról 33 Szorzás 2. accumulator = NewlNumber(a->n+b->n); /* létrehozzuk az akkumulátort */ if( !accumulator )return (Number)0; /* Kitöröljük az akkumulátor tartalmát / for( j=0 ; j n ; j++ ) ACC(j) = (u32)0; p = a->digit; 2001. Csink László: A digitális

aláírásról 34 Szorzás 3. A következõ két egymásba ágyazott ciklusban minden digitet megszorzunk minden digittel, és a helyiértékek összegének megfelelõ helyre tesszük. for( i=0 ; i n ; i++,p++ ){ r = b->digit;q = accumulator->digit + i; for( j=0 ; j n ; j++ ) *q++ += ((u32)p)((u32)r++); /* Normalizáljuk az akkumulátor használt részét. */ q = accumulator->digit;cy=0; for( j=0 ; j n || (jn+b->n && cy) ; j++,q++ ){ *q += cy; cy = (*q)/POW2 8; *q &= (POW2 8-1); } if( cy ){ ReportLog(I,"Internal error in multiply."); } } 2001. Csink László: A digitális aláírásról 35 Szorzás 4. /* Kiszámítjuk az eredmény hosszát. */ for( i=0,j=1 ; i n ; i++ ) if( ACC(i) )j=i+1; result = NewNumber(j); if( !result ){ DisposelNumber(accumulator); return (Number)0; } for( i=0 ; i digit[i] = (u8)ACC(i); DisposelNumber(accumulator); return result; } 2001. Csink László: A digitális aláírásról 36 Modulo hatványozás 1. Ez

afüggvény kiszámítja ab mod c értékét. A számítás a következõ módon megy végbe: ab kiszámítható lenne úgy, hogy a-t megszorozzuk a-val b-szer. Ha azonban b nagy, a számítás ilyen módon millió évekig tartana, még a világ leggyorsabb mikroprocesszorával is. Ennél gyorsabb némileg, ha kiszámítjuk az a, a2 , a4, ., a2n, . értékeket Legyen b bináris megjelenítése b0, b1, , bn, és bn a b n-edik bitje. a^b értéke a következõ egyenlettel számítható ki: ab=f[b 1*a] f[b 2a2] . f[b n*a2n] . ahol f[x] egy olyan függvény, amely minden egész számra identitás, kivéve a nullát, ahol f[0]=1. Más szavakkal a szorzatba csak azokat a tagokat vesszük be, ahol bi nem nulla bit. A képlet végén levõ három pont végtelen szorzást jelentene, de egy idõ után b-nek csupa nulla bitje van, hiszen b véges. 2001. Csink László: A digitális aláírásról 37 Modulo hatványozás 2. Ezzel az eljárással a számítás idõigénye arányos a b

bitjeinek a számával és nem b nagyságával. Mivel minket nem érdekel a^b értéke, csak a^b mod c ezért minden egyes szorzás után az eredményt helyettesíthetjük a c-vel adott osztási maradékával. Ezzel annyi memóriahelyet és idõt tudunk spórolni, hogy a számítás elvégezhetõ. 2001. Csink László: A digitális aláírásról 38 Modulo hatványozás 3. Ezzel az eljárással a számítás idõigénye arányos a b bitjeinek a számával és nem b nagyságával. Mivel minket nem érdekel a^b értéke, csak a^b mod c ezért minden egyes szorzás után az eredményt helyettesíthetjük a cvel adott osztási maradékával. Ezzel annyi memóriahelyet és idõt tudunk spórolni, hogy a számítás elvégezhetõ. A részletezést - az algoritmus bonyolultsága miatt - elhagyjuk. 2001. Csink László: A digitális aláírásról 39 A következõ probléma a fentiekben szereplõ p és q prímek elõállítása, melyek szorzata a nyilvános kulcs egyik tagját

adta, amit n-nel jelöltünk Igen nagy prímszámok elõállítása véges idõben nemtriviális feladat. Lássuk tehát a praktikus prímszámtesztet: Generáljunk egy n-bites p számot. A legmagasabb (MSB, most significant bit) és legalacsonyabb (LSB, least significant bit) bitet állítsuk be 1-re. A legmagasabb bit beállítása garantálja a szám hosszát, a legalacsonyabb bit beállítása azt, hogy a szám páratlan. 2001. Csink László: A digitális aláírásról 40 Az egyszerûség kedvéért vizsgáljuk meg, hogy a szám osztható-e a 256-nál kisebb prímekkel, csak akkor vizsgáljuk tovább, ha nem osztható ezekkel. (Lehet 256 helyett mondjuk 2000-el is dolgozni.) Ha osztható, adjunk hozzá 2-t p-hez és kezdjük újra az 1.lépést Valamely a véletlen számra futtassuk le a Rabin-Miller tesztet (ld. a következõ diát) Ha kiállja a próbát, másik véletlen számra ismételjük meg a tesztet Ha a viszonylag kicsi, a teszt gyorsabban fut Csináljunk mondjuk

5 tesztet. Ha nem jön be, újabb p-vel kezdjük el elölrõl. Kísérleti tapasztalatok szerint a 3, 5, 7 –tel való oszthatóság az összetett páratlan számok felét kiszûri, a 256-nál kisebb páratlan prímosztókkal való ellenõrzés az összetett páratlan számok mintegy 80 százalékát. Ezen egyszerû elõszûrés után célszerû a Rabin-Miller tesztalkalmazása. 2001. Csink László: A digitális aláírásról 41 Nagy szám prím voltának ellenõrzése: a Rabin-Miller Teszt http://www.geocitiescom/SiliconValley/Network/2811/ Legyen p a tesztelendõ szám. Jelölje b azt a számot, ahányszor 2 osztja a p-1 számot. Legyen m az a szám, melyre p = 1 + 2 b*m. 1. Legyen a egy véletlen szám, melyre a kisebb, mint p 2. Legyen j = 0, és z = am mod p 3. Ha z = 1, vagy z = p – 1, akkor p kiállta a tesztet, és feltehetõleg prím. 4. Ha j > 0 és z = 1, akkor p nem prím 5. Legyen j = j +1 Ha j < b és z ≠ z2 mod p jöjjön a 4 lépés Ha z = p – 1,

akkor p kiállta a tesztet és valószínûleg prím. 6. Ha j = b és z ≠ p –1, akkor p nem prím A lehetséges értékeinek ¾-ed része megfelelõ a teszt szempontjából. Vagyis annak esélye, hogy a teszt prímet mutat ki, és a szám nem prím, ¼. Tehát ha t alkalommal iteráljuk, újabb a számokkal, akkor (1/4)t a valószínûsége, hogy a teszt rossz eredményt ad. 2001. Csink László: A digitális aláírásról 42