DT                    D é n e s   T a m á s matematikus                                         TD

független szakértő            

   e-mail: tdenest@freemail.hu

                                                                                                             

Új eredmények az RSA kulcsok megfejtéséhez

 

A  Ron Rivest, Adi Shamir és Len Adleman szerzőhármas által az 1970-es évek közepén megalkotott titkosítási eljárás, melynek elnevezése RSA (neveik kezdőbetűiből), azóta ismertté vált az egész világon. Napjainkban az RSA algoritmus szinte minden informatikai, számígógépes, kommunikációs rendszerben jelentős szerepet játszik, ahol a digitális adatok biztonságáról gondoskodni szeretnének. Ilyenek például az e-kereskedelem, az e-bank rendszerek, ezzel biztosítják a web serverek és a kliensek közti biztonságos kapcsolatot, az e-mailek hitelességét és titkosságát, használják a távoli terminálokról bejelentkező felhasználók és az elektronikus hitelkártyás rendszerek.

Az első publikációk óta sok kutató, köztük maguk a szerzők is keresték az RSA algoritmus gyenge pontjait. Az eltelt huszonöt év vizsgálódásai egy sor nagyon érdekes elméleti és gyakorlati támadási módszert eredményeztek, azonban eddig egyik sem oldotta meg az RSA általános megfejthetőségét, mivel a számítástechnika rohamos fejlődése ezeket a támadásokat technikával kompenzálta. Jelen dolgozat célja, hogy rámutasson arra, hogy bár a támadások egyenként nem rendítik meg (bizonyos feltételek teljesülése esetén!) az RSA biztonságát, összességükben olyan arzenált képviselnek, amelyek állandó szemelőtt tartása jelentősen megnehezíti (lelassítja) az RSA tömeges alkalmazását.

Itt mutatom be először azokat az új támadási lehetőségeket, amelyek nem az RSA modulus faktorizációját célozzák és amelyek érdekessége, hogy részben éppen annak a P.Fermatnak az eredményeiből vezethetők le, akinek a "kis Fermat tételére" alapul maga az RSA algoritmus.

Az RSA titkosító algoritmus rövid összefoglalása

·        Legyen N = pq, két nagy prímszám szorzata (n/2 bit hosszú mindkettő), ezt nevezzük RSA modulusnak. Napjainkban  N tipikus hosszúsága  n=1024 bit, ami 309 decimális jegyet jelent. A két prímtényező pedig 512 bit hosszú. Nem így volt ez kezdetben, amikor  az  n=128  bites modulus is biztonságosnak bizonyult, majd éppen a támadások és a technika fejlődése hatására, a biztonságot a számok nagyságának emelésével igyekeztek biztosítani. Így lett az RSA modulus hossza  256, 512, majd  1024 bit. Már itt érdemes megjegyezni, hogy az ilyenfajta biztonság növelés jelentős anyagi ráfordítást igényel, mivel a technikai eszközöket általában le kell cserélni, illetve ahol ezt nem tudják megoldani, ott csökken a rendszer biztonsága.

·        Legyen továbbá  e, d  két egész szám úgy, hogy ,

      ahol j(N)=(p-1)(q-1)

      e-t nyilvános (publikus) exponensnek, míg  d-t privát (titkos) exponensnek

     nevezzük.

·        Az (N,e) páros a publikus kulcs, amely mindenki számára hozzáférhető, ezzel titkosítják az üzeneteket.

·        Az (N,d) páros pedig a privát vagy másképp a tikos kulcs, ezt csak a cél személy ismeri, és arra használja, hogy dekódolja a titkos üzeneteket.

·        Az üzenetet minden korlátozás nélkül tekinthetjük egy egész számnak, jelöljük M-mel, amelyre teljesül, hogy  . Ha a tényleges üzenet ennél hosszabb, akkor úgynevezett blokkokra osztjuk, amelyek teljesítik e feltételt.

·        A tikosított szöveg: .

·        A dekódolt szöveg: , mivel az Euler-Fermat tétel alapján:

     

 

Az RSA egy úgynevezett egyirányú függvény, amely adott d esetén könnyen invertálható az előzők alapján, azonban a privát kulcs ismerete nélkül ez nagyon nehéz. Az RSA feltörése pontosan arra irányul, hogy d  ismerete nélkül kell invertálni az RSA függvényt. Pontosabban fogalmazva, ha csupán az (N, e, C) hármas adott, akkor képesek vagyunk-e az eredeti, úgynevezett nyílt üzenetet M-et előállítani?

Az RSA támadások csoportosítása

Implementáció függő támadások

Az RSA támadásoknak ez a típusa az adott implementáció ellen irányul, ami csak az adott helyzetben alkalmazható, viszont ott és akkor, igen hatékony fegyvert ad a támadó kezébe. Ilyen támadási lehetőség például a tárolt kulcsok elleni támadás (a szerver azon területének behatárolása, amelyen a kulcsok, akár kódolt formában tárolásra kerültek), vagy például a smartcardok számítási idejének és áram felvételének időbeni mérésén alapuló támadás. Ezek a  támadások már nem csupán elméleti megfontolásokat, hanem komoly technikát is igényelnek.

Kulcskereséses támadás

Nicko van Sommeren és Adi Shamir kidolgoztak egy olyan technikát, ami igen hatékony módszert ad a kulcsok memóriában való megkeresésére. A legtöbb alkalmazás ugyanis, a szerver kulcsait a merevlemezen olyan fileokban tárolja, amihez csak nagyon kevés felhasználónak van hozzáférési joga, sőt ezen felhasználók számára is olvashatatlan ez az állomány, mivel általában ez is titkosítva van. A célalkalmazás tudja csak olvasni és értelmezni, dekódolni a kulcsokat. Viszont a cél alkalmazásnak ahhoz, hogy felhasználja a kulcsot, ki kell bontania és ekkor a kulcs a rendszer memóriájában lesz kódolatlan formában. Ha a támadó valamilyen módon eléri, hogy a rendszer összeomoljon, akkor valószínűleg ott lesz a memória dumpban is kulcs, vagy ha hozzáfér a rendszer memóriájához, akkor is megszerezheti azokat. Viszont a feladat még így sem egyszerű, mivel egy egy memória dump több száz megabyte is lehet, a keresendő kulcs 1024 bites RSA kulcsot feltételezve is, csak néhány száz byte. Olyan mintha egy tűt keresnénk a szénakazalban. A kulcsokat általában álvéletlenszám generátorral generálják, így nagy entrópiájú adatokként detektálhatók a tárolóban. Tehát ha a keresés során, olyan részadatokat találunk amiknek nagy az entrópiája, akkor azok jó eséllyel lehetnek a keresett kulcsok. Az alábbi ábrán jól látható, hogy középen helyezkedik el a keresett kulcs.

           

Az RSA privát kulcsok keresésénél különösen jól alkalmazható ez az eljárás, hiszen nyilvános kulcsú titkosítás lévén, könnyen megszerezhetjük a publikus kulcsot. A modulus a privát kulcsban és a publikus kulcsban megegyezik, így tehát rendelkezünk a privát kulcs felével. Nicko van Sommeren egy webserver kulcsain mutatta be a támadást, a webserver ha cgi-ket futtat, akkor a cgi olvashatja a process memóriáját. Így másodpercek alatt megkeresheti a privátkulcsot. Állítása szerint ez a módszer remekül működik Netscape, IIS, Apache-SSL, Stronghold és még jó pár webserveren és jó néhány operációs rendszeren, köztük például Windows NT és Solarison is.

Védekezésképpen be lehet vezetni néhány nagyon szigorú biztonsági intézkedést, például a felhasználók nem futtathatnak cgi-ket, nem lehet távolról hozzáférni a rendszerhez, stb. Ezen intézkedések viszont nagyon lecsökkentik az adott server használhatóságát. A software-eken is lehet javítani, hogy a privát kulcsot minél kevesebb ideig tárolják tisztán a memóriában. Az igazi védekezés ez ellen a támadás ellen, ha a kulcsokat nem a rendszer memóriájában tároljuk, hanem egy úgynevezett hardware kripto egységen. Ezek alkalmazása elég költséges, viszont magasfokú biztonságot nyújtanak.

 

Számítási idő mérése

Napjainkban egyre inkább teret hódítanak a smartcardok és a smartcardokra épülő alkalmazások. A smartcardok képesek a privát kulcs tárolására és az RSA aláírási illetve titkosítási műveletek elvégzésére anélkül, hogy a privát kulcs kikerülne a smartcardból. Kocher módszerének [8] köszönhetően mégis aránylag gyorsan megszerezhetjük a privát kulcsot. A támadás azon alapszik, hogy pontosan kimérjük mennyi ideig tart a smartcardnak az RSA dekódolás, vagy RSA aláírás művelet elvégzése.

A támadás során a smartcardot arra használjuk, hogy generáljuk néhány véletlen üzenetnek a digitális aláírását,  és rendre lemérjük, hogy az aktuális művelet elvégzése a smartcardnak mennyi időbe telik . Ezzel a módszerrel ki lehet nyomozni bitről bitre a d értéket. Legyen  az az idő amit a smartcard igénybe vesz a  számítás elvégzésére. Ezek a -k különböznek egymástól, számítás igénye függ  értékétől, mivel az egyszerű  moduláris egyszerűsítés művelet számítási igénye függ a konkrét értéktől. Kocher azt állapította meg, hogy a két sorozat {} és {} korrelál egymással, ha , ha viszont  akkor a két sorozat {} és {} úgy viselkedik mint két független valószínűségi változó.

            Kochen egy ehhez hasonló támadási módszert is felvázolt, ezt „power cryptanalysis” nak nevezte el. Azt figyelte meg, hogy a smartcard áramfelvétele nagyobb olyankor mikor a nagypontosságú szorzásokat végzi, mint általában. Így ha azt mérjük, hogy az aláírás generálása közben, hogyan változik a smartcard energiafelvétele, akkor az előzőhöz hasonló támadáshoz jutunk. Meg kell mérni a nagy áramfelvételű szakaszok hosszát. Ezen szakaszok hosszából megállapítható, hogy egy-egy iteráción belül a smartcard egy vagy két szorzást végzett. Ezáltal megfejthető a privát kulcs.

 

Helytelen alkalmazáson alapuló támadások

A helytelen alkalmazás alatt azt kell érteni, hogy az RSA algoritmus fentiekben ismertetett feltételei mellett, a választható kulcsok száma elképzelhetetlenül nagy, azonban a feltörhetőség szempontjából nem mindegyik kulcs egyformán biztonságos. Már az előzőkben utaltam a kulcsok hosszára, vagy egy igen egyszerű példa a helytelen alkalmazásra, ha  p  és  q  ikerprímek, azaz  N=p(p+2), amelyből  p  pillanatok alatt kiszámítható és ezzel egyidőben megkapjuk  N  faktorizációját. Mondhatnánk erre, hogy nagyon speciális esetnek tekinthető, ugyanakkor nem elhanyagolható, hogy még számtalan olyan speciális alkalmazást találtak eddig, amit ugyan nem tilt meg az RSA algoritmus, viszont használatuk esetén igen széles biztonsági rések keletkeznek a rendszerben. Ilyen például a kis privát exponens használata, a közös modulusu üzenetek gyűjtése, vagy éppen a semleges üzenetek digitális aláírása. Az  RSA körültekintő használata tehát kulcskérdés az üzenetek biztonsága szempontjából, mivel a matematika mai ismeretei szerint az RSA feltörhetetlensége elméletileg nem garantálható (ezt maguk a szerzők is elismerik).

Közös modulus

Néhány rendszer nem generál minden felhasználónak külön modulust, mivel ezzel igen sok számítást spórol meg. Rögzítenek egy N = pq modulust és a központi Certificate Authority mindenkinek ezt a modulust osztja ki és ehhez mindenkinek generál egy saját e és d értéket.

Az alábbi tétel szerint (melynek bizonyításától itt eltekintek) a privát kulcs leleplezése és N faktorizációja egyenértékü. Ezért nincs értelme elrejteni N faktorizációját azok elől, akik amúgy is ismerik a privát kulcsot.

Tétel (Simmons)

Legyen (N, e) egy RSA publikus kulcs. Ha adott a privát kulcs d, akkor N faktorizációja hatékonyan elvégezhető. Ha  N faktorizációja ismert, akkor hatékonyan kiszámítható d.

Így a rejtjelzett  üzenet nincs biztonságban, ha az A és B felhasználó ugyanazt a modulust használja.  Bár  B  nem rendelkezik a -val (A privát exponense), ugyanakkor rendelkezik egy saját kulccsal, aminek ugyanaz a modulusa. A  fenti tétel alapján a saját exponensei  segítségével faktorizálhatja N-t, majd N osztóinak birtokában könnyen kiszámíthatja A privát exponensét -t.

 

Kis privát exponens

Az alkalmazások egy részében, hogy csökkentsék a kulcsok generálási idejét, vagy hogy gyorsabb legyen a dekódolás, véletlenszerű  d  privát exponens helyett, inkább egy kis d-t választanak. Mivel a modulo hatványozás művelet igénye , ezért egy jól megválasztott d segítségével akár tízszeres gyorsítás is elérhető (pl. ha 1024 bit hosszú a modulus). Azonban az  M. Wiener által bizonyított alábbi tétel mutatja, hogy ha d  egy magadott értéknél kisebb, akkor a kód megfejthetővé válik.

 

Tétel (M.Wiener)

Legyen N = pq úgy, hogy  és legyen . Ha adott (N, e) úgy, hogy , akkor  d  hatékonyan megfejthető.

Mivel  N általában 1024 bit hosszú, e tétel következményeként adódik, hogy  d-nek legalább 256 bit hosszúnak kell lennie, hogy ez a támadás ne jelentsen veszélyt. Ez a feltétel például igen megnehezíti a gyenge számítási kapacitással bíró hardware-eken való alkalmazásokat, ahol a kis d használata nagy előny lenne.

A  Wiener tételt  Boneh és Durfee élesítették, így most már a d  (N, e)-ből való megfejtésének korlátja . Valószínűnek látszik, hogy az igazi korlát valahol  körül lehet, azonban ez még nyitott kérdés.

 

A modulus faktorizációján alapuló támadások

Az elméleti RSA támadások legelterjedtebb csoportja az, amelyben a támadás a publikus kulcs ismeretében (N, e), a modulus  N  faktorizálására irányul. N osztóinak ismeretében a támadó könnyen kiszámíthatja -t, és ennek ismeretében a privát kulcs is adódik  A modulus faktorizációján alapuló támadások műveletigénye a modulus hosszának exponenciális függvénye, így elég nagy modulus esetén, a gyakorlati feltörés irreális időigényű lehet. A jelenlegi leggyorsabb faktorizációs algoritmus az 1993 ban A.K. Lenstra, H. W. Lenstra, M. S. Mantasse és J. M. Pollard által publikált Number Field Sieve algoritmus, amelynek műveleti igénye egy n-bites szám esetén  egy alkamas   konstanssal.

Az RSA Security által meghirdetett faktorizációs versenyen is ezzel az algoritmussal érték el a rekordot, ami egy 512 bites szám osztóinak a megkeresesése volt. Érdemes felidézni Martin Gardner, a Scientific American világhírű rovatvezetőjének 1977-es gondolatait: „Ha a ma ismert legjobb algoritmust és a leggyorsabb számítógépeket használjuk, egy ilyen 125 jegyű RSA kulcs megfejtésére, Rivest becslése szerint a szükséges mefejtési idő körülbelül 40 quadrillió év! Ez azt jelenti, hogy praktikusan a belátható jövőben reménytelen az RSA kulcsok faktorizáció útján történő megfejtése. Ugyanakkor maga Rivest és kollégái is elismerik, hogy semmilyen elméleti bizonyítékuk nincs arra, hogy az RSA titkosítási eljárás megfejthetetlen.”

Az NFS algoritmusnak a lépésszáma elég lassan nő a bemenet bináris hosszának a függvényében.  Tegyük fel, hogy az 512 bites szám faktorizációja X lépést, időt vett igénybe, ha egy ennél 100 bittel hosszabb számot szeretnénk faktorizálni, akkor 40X lépésre lesz szükségünk, ha 150 bittel hosszabbat, akkor kb 220X, ha 200 bittel növeljük a bemenetet, akkor 1100X re nő a szükséges lépések száma.

Adi Shamir, 2000 ben, az éves RSA konferencián bemutatott egy gépezetet, amit TWINKLE [12] névre keresztelt, a gépezett egy érdekes optikai technikát alkalmaz, aminek segítségével az NFS algoritmus sebességét képes két három nagyságrenddel felgyorsítani, ezáltal képes az algoritmusok által belátható időn belül faktorizálható számok halmazát kitolni 100 esetleg 200 bittel. Így az 512 bites RSA kulcsok igen komoly támadásnak lesznek kitéve. Ezt különösen fontos kiemelni, mivel az aktuális statisztikák szerint 512 bites RSA kulcsokat használnak az interneten és az e-kereskedelemben résztvevő szerverek 95%-nál.

 

S.W. GOLOMB ALGORITMUSA

Adott . Írjuk fel N-t mint két négyzet különbségét

           

ahol a és b természetes számok, p és q pedig prímszámok. Az összefüggésből könnyen látható, hogy ha sikerül két ilyen négyzetszámot találnunk akkor megvannak N prímtényezői.

Az algoritmus lépései:

 

S.W.Golomb az 1870-ben még megoldhatatlannak vélt Jevons szám (8.616.460.799) prímfaktorizációjának megkeresésével demonstrálta, hogy ez a módszer egyszerűen alkalmazható akár egy zsebszámológépen is, és  lépésben meghatározhatóak a Jevons szám prímtényezői   és . A lépések száma a prímtényezők távolságától is függ. Kisebb számok esetében hatékonyabb, mint az NFS algoritmus mivel az iterációban szereplő műveletek nagyon egyszerűek. Az egymást követő teljes négyzetek -ek meghatározására ugyanis az  képletből jól láthatóan egy shiftelés és egy összeadásból áll. A négyzetgyökvonásra pedig szintén nincs szükség hiszen az egyenlőség túloldalát is léptethetjük hasonló módszerrel.

Az algoritmus könnyen, hatékonyan és viszonylag olcsón megvalósítható hardware közeli elemekkel és ezek sorozatgyártásával és párhuzamos futtatásával futásideje drasztikusan csökethető.

A komplementer prímszita

Jelen szerző algoritmusa azon tételre épül, mely szerint az összes 3 nál nagyobb prímszám 6k+1 vagy 6k-1 alakú, ahol k=1,2,3,... természetes szám. Az alábbi tételre alapuló algoritmus a  komplementer prímszita.

Tétel (Dénes T.)

Legyenek N, k, u, v  természetes számok, valamint .

, akkor és csak akkor összetett szám, ha , vagy

, akkor és csak akkor összetett szám, ha , vagy .

 

Ennek a tételnek a következményeként kapjuk N kéttényezős felbontását, azaz

            , vagy

            , vagy

A tétel következményeként konstruálható algoritmus:

 

A Golomb algoritmushoz hasonlóan, könnyen implementálható, nagyon alacsonyszintű hardware elemek segítségével, ezáltal nagyon gyorsan elvégezhetővé válik egy iteráció. Az algoritmus nagyon jól párhuzamosítható. 

 

Új támadási lehetőség   becslésével

A következőkben a prímszámok egy jelentős csoportjáról mutatjuk meg, hogy alkalmatlanok az  RSA modulus képzésére.

Legyen    és  N=pq . Ekkor  =(p-1)(q-1)-re a következő összefüggést kapjuk:

Ekkor N-re a fenti feltételek mellett adódik:

                                

   

Tehát a fenti két összefüggés összevetéséből kapjuk:

   

 

Vezessük be az   jelölést, amelyből következik, hogy  x  pozitív egész szám, amelyre a következő megoldásokat kapjuk:

 

 

 

 

Tehát  N  és    ismeretében a  p  és  q  prímtényezők kiszámíthatók. Érdemes megjegyezni, hogy máig bizonyítatlan az a sejtés, mely szerint a fentieknek megfelelő  p, q  prímekből végtelen sok létezik. 

Megmutatjuk, hogy a gyökös kifejezés mindig egész szám és éppen a  p, q  prímtényezők különbsége:

 

Az alábbi levezetés bizonyítja, hogy a fenti másodfokú egyenletnek bármely  p, q  prímszám esetén (nem csak a  alakúak esetén)  egész megoldása van és a két megoldás pontosan a  p-1  és  q-1  értékeket adja.

 

 

Példák:  N=185,  =144

 

= 

 

=  

Valóban  N=pq=375=185

 

 

N=23.796.476.449,  =23.794.913.536

              

 

 

 

Valóban  N=pq=154753715377=23.796.476.449

 

 

Megjegyzés:

A    érték az RSA nyilvános kulcsával közvetlenül nem áll rendelkezésre, azonban  N  igen. Így a támadás szempontjából lényeges az alábbi összefüggés:

       

Ebből következik, hogy ha  p  és  q   n-jegyű decimális számok, azaz

      

      

 

Ez azt jelenti, hogy tetszőleges  N  esetén, egy N körüli  hosszúságú intervallumban helyezkedik el  , így maximum ennyi lépésben megtalálhatjuk.

Így maximum   lépésben  N  prímtényezői is megtalálhatók !

N  számjegyeinek száma (két  n-jegyű szám szorzataként)  2n-jegyű, azaz  , így a prímtényezők előállításához szükséges lépések maximális száma: 

 

 

Példák:

-  p=23, q=11,  N=pq=253, n=2

     ,   , tehát 

    A pontosan számított érték: 

 

-  p=1234577, q=7654337,  N=9.449.868.410.449

 

      ,

     tehát  

     A pontosan számított érték:  =9.449.859.521.536

 

Ha tehát  N  nagyságrendje  , akkor a fentiek szerint a   meghatározásához szükséges maximális lépésszámra a következő összefüggést kapjuk:

     

 

 

 

Az  RSA ellenszere Fermat-ba rejtve

 

Fermat egy tétele azt mondja ki, hogy ha egy tetszőleges m egész számot egy megadott modulus (N) szerint ismételten megszorzunk önmagával, akkor véges számú lépésben visszakapjuk a kiindulási számot.

Példa:

N=55, m=6

1.

mod 55

2.

mod 55

3.

mod 55

4.

mod 55

5.

mod 55

6.

mod 55

7.

mod 55

8.

mod 55

9.

mod 55

10.

mod 55

11.

mod 55

 

Fermat tétele igaz akkor is, ha egy szám hatványaira alkalmazzuk az ismételt beszorzást

N=55, m=

1.

mod 55

2.

mod 55

3.

mod 55

4.

mod 55

5.

mod 55

6.

mod 55

7.

mod 55

           

N=55, m=

1.

mod 55

2.

mod 55

3.

mod 55

 

A tétel akkor is igaz, ha a kapott számot ismételten hatványra emeljük, . N=55, m=6, e=3

1.

mod 55

2.

mod 55

3.

mod 55

4.

mod 55

 

Ezen módszer segítségével, meglepően gyorsan megfejthető a helytelenül választott RSA kulcs, hiszen a megfejtéshez szükséges idő, a kulcsgenerálás idejével szinte azonos.

Bemutatok egy példát, amelyben 60 jegyű RSA modulussal  dolgozunk, mégis  6  lépésben megtalálja a megoldást.

Legyen  p és q  két 30 decimális jegyű prímszám.

 

,  valamint

Tehát az RSA publikus kulcs (N,e). Ezt ismerheti bárki. Vegyünk egy M üzenetet

 Erre a C-re indítsuk el az előző algoritmust. , tehát adódik, hogy , azaz sikerült megfejteni a nyílt üzenetet a titkos kulcs ismerete nélkül, és ez mindössze 6 lépést igényelt. Ezen támadás ellen a kulcsgenerálás során lehet védekezni, ha figyelünk arra, hogy a választott e és d értékek megfelelően távol legyen egymástól és a hatványozási ciklus hossza is elegendően nagy legyen. Ezen feltételek biztosítása igen nehéz és számolásigényes, így jelentősen lassítja az algoritmus használatát, de amint láthatjuk, szükséges az RSA kulcsok biztonságához. A fenti példa jól illusztrálja, hogy ha eme feltételek vizsgálatára mégsem figyelünk kellőképpen, akkor a kulcsmérettől függetlenül, igen széles rés keletkezik az RSA biztonsági pajzsán.

 

Az RSA titkosítás matematikai alapjai a kis Fermat tételre alapulnak, amit később, Euler bizonyított be.

"kis Fermat tétel":

Ha  a  nem osztható p-vel és p prímszám, akkor teljesül az alábbi kongruencia.

Euler ezt a tételt nem csak bizonyította, hanem általánosította is, így ma már  Euler-Fermat tételnek nevezzük.

 

Euler-Fermat tétel:

Legyen    egész szám és  (a,m)=1, azaz  a  és  m  relatív prímek, akkor teljesül

Hogy ez valóban a kis Fermat tétel általánosítása, ahhoz a    Euler-féle függvény értelmezéséről kell beszélnünk.    jelenti a  0, 1, 2, ..., m-1  számok közül az  m-hez relatív prímek számát. Az alábbi táblázatban az első néhány ilyen értéket bemutatjuk:

                    m                     1,2,3,…,m-1          m-hez relatív prímek         

                    3 (prím)           1, 2                         1, 2                                          2

                    4                      1, 2, 3                     1, 3                                          2

                    5 (prím)           1, 2, 3, 4                 1, 2, 3, 4                                  4

                    6                      1, 2, 3, 4, 5             1, 5                                          2

                    7 (prím)           1, 2, 3, 4, 5, 6         1, 2, 3, 4, 5, 6                          6

 

               

Könnyen belátható, hogy ha  m=p  prímszám, akkor . Továbbá igaz az Euler függvényre, hogy ha  p és  q  prímek, akkor  . Így tehát az  N=pq  RSA modulusra alkalmazva az Euler-Fermat tételt, éppen az RSA algoritmus alapösszefüggését kapjuk.

Azonban vannak olyan  n  összetett számok, amelyek, adott  n-hez relatív prím  a-ra kielégítik a kis Fermat tételt, vagyis

                              ahol   n  összetett szám és  (a,n)=1

Az ilyen összetett  n  számokat, amelyekre az összefüggés teljesül, a-alapú pszeudoprímeknek, vagy álprímeknek nevezzük.

Talán még meglepőbb, hogy vannak olyan  n  összetett számok, amelyek minden  n-hez relatív prím  a-ra kielégítik a fenti összefüggést. Az ilyen  n  számokat nevezzük  felfedezőjükről  Carmichael számoknak, melyekről csak a XX. század közepén sikerült bebizonyítani, hogy végtelen sok létezik belőlük.

A fenti tulajdonságaik alapján belátható, hogy az RSA támadások szempontjából, igen nagy jelentőséggel bírnak a pszeudoprímek és ezek speciális reprezentánsai, a  Carmichael számok. Ugyanis ha az  RSA modulus egy  Carhmichael szám valamely osztója, vagy bizonyos tulajdonságokkal rendelkező pszeudoprím, akkor a fent bemutatott Fermat-féle ciklus hossza éppen  1. Néhány példa ennek illusztrálására:

2-es alapú pszeudoprímek: 341,561,645

,  ,  

3-as alapú pszeudoprímek: 91,121,286

,  ,  

5-ös alapú pszeudoprímek: 124,217,561

,  ,  

A legkisebb Carmichael szám az 561, tehát minden N-re, amelyik kisebb mint 561 és ahhoz relatív prím, igaz, hogy

Felmerülhet a kérdés, hogy ezek az RSA rejtjelezés szempontjából veszélyes modulusok milyen valószínűséggel fordulnak elő? Ugyanúgy ahogy a prímszámokra, a pszeudoprímekre és Carmichael számok számára sem ismert zárt formula, azt azonban tudjuk, hogy mindkettőből végtelen sok van. R.G.E Pinch munkássága eredményeképpen léteznek az interneten is elérhető nagy pszeudoprím és Carmichael számtáblázatok [ ][ ], ezen táblázatok segítségével becsülhetjük az ílymódon veszélyes  RSA modulusok arányát.

 

Intervallum

Pszeudoprímek száma

Carmichael számok száma

1-10

1

-

1-100

30

-

1-1000

434

1

1-10000

5106

7

1-100000

55576

16

 

 

 

 

Mint az a táblázatból jól látható a Carmichael számok aránya  1 ezrelék körül mozog, a pszeudoprímek aránya  ennél jóval magasabb 55-60% . Ez egy óriási bizonytalansági tényező, amely jelentősen megingathatja az  RSA biztonságába vetett hitet és egyúttal egy új, az RSA modulus faktorizációjától jelentősen eltérő utat mutat az RSA támadások területén.

 

Irodalomjegyzék

1

R.L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public key cryptosystems. Commun. ACM 21 120-126

2

M. Wiener, Cryptanalysis of short RSA secret exponents, IEEE Trans. Inform. Theory 36 (1990), 553-558

3

D. Boneh, and G.Durfee, New results on crpyptanalysis of low private exponent RSA, preprint 1998

4

D. Coopersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology 10 (1997), 233-260

5

J. Hastad, Solving simultaneous modular equations of low degree, SIAM J. Comput. 17 (1988), 336-341

6

A. Menezes, P. Van Oorschot, and S. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, FL, 1996.

7

Nicko van Sommeren, Adi Shamir

8

P. Kocher, Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems, CRYPTO’96, Lecture Notes in Computer Science, vol. 1109, Springer-Verlag, 1996, pp 104-113.

9

D. Boneh, G. Durfee, and Y. Frankel, An attack on RSA given a fraction of the private key bits, AsiaCrypt’98, Lecture Notes in Computer Science, Springer-Verlag, Berling and New York, 1998

10

C. Pomerance, The quadratic sieve factoring algorithm, Proceedings of EUROCRYPT 84 (LNCS 209), 169-182, 1985

11

A. K. Lenstra, H. W. Lenstra, M. S. Manasse, and J. M. Pollard, The Number Field Sieve, Vol. 1554 of Lecture Notes in Mathematics, 11-42, Springer Verlag, 1993.

12

Adi Shamir: Factoring Large Numbers with the Twinkle Device (Extended Abstract). CHES 1999: 2-12

13

Dan Boneh, Twenty years of attacks on the RSA cryptosystem, Notices of the AMS, February 1999, 203-213

14

Tamás Dénes, Complementary Prime-Sieve, P.U.M.A, Vol. 12. (2002)

15

S.W. Golomb, On factoring Jevons’ number, CRYPTOLOGIA, vol XX. No3 1996

16

W.S. Jevons, The Principles of Sience, A Treatise on Logic and Scientific Method, Macmillan & Co. London. 1873 Second Edition. 1877

 

 

17

R.G.E.Pinch:  The pseudoprimes up to  10^13

                                ftp://ftp.dpmms.cam.ac.uk/pub/PSP

18

R.G.E.Pinch:  The Carmichael numbers up to  10^16

                                ftp://ftp.dpmms.cam.ac.uk/pub/Carmichael

19

Martin Gardner: Mathematical games

                           A new kind of cipher that would take millions of years to break

                           Scientific American, 1977.