DT
D é n e s T a m á s matematikus TD
független
szakértő
e-mail: tdenest@freemail.hu
A Public Key System és az RSA biztonsági kérdései
(Megjelent: Híradástechnika,
2002/1. 47-55)
„Nem tulzás
azt állítani,
az absztrakt
rejtjelzés azonos
az absztrakt
matematikával.”
A.A.Albert [37]
Kulcsszavak: Public Key System, RSA,
rejtjelzés biztonsága, prímfaktorizáció, prímszita
A nyilvános kulcsú titkosító eljárások (Public Key
System: PKS) első gondolata 1976-ban jelent meg [20]-ban.
Míg a klasszikus rejtjelzésben a
rejtjeles szöveg és a rejtjelzési kulcs a visszaállítást (megoldást)
egyértelműen lehetővé teszi, addig a PKS-nél a rejtjeles szöveg és a nyilvános
kulcs ismerete nem teszi lehetővé a megoldást. A megoldáshoz szükséges a kulcs
inverzének az ismerete is amit titokban tartanak.
A PKS létrehozóinak elgondolása az volt, hogy a K kulcs ismeretéből, ennek K-1 inverze csak nagyon nehezen legyen
meghatározható. Merkle és Hellman [39]-ben
azt fejtegették, hogy K-1 meghatározása
gyakorlatilag lehetetlen. A PKS működését úgy kell elképzelni, hogy a telefonkönyvhöz hasonlóan közreadnak egy
névsort és mindenki neve mellett a hozzá tartozó K érték szerepel, míg az Ő egyéni (titkos) K-1 kulcsát (amelyet feltételezés szerint K ismeretében szinte lehetetlen
kiszámítani) csak az érintett ismeri.
A PKS előnyei: nem kell központi kulcs elosztás, nem
kell kulcs váltás, az összes viszonylatot nem lehet egyszerre árulás útján
megfejteni, a fejtésnél nem alkalmazhatók a szokásos statisztikai eljárások
stb..
Ennek a tanulmánynak az a célja, hogy a PKS néhány hátrányát, azaz a matematikai konstrukció támadhatóságát is kimutassa, vagyis a PKS kritikai elemzését adja, különös tekintettel az RSA[1]-ra.
Néhány
általános megállapítás a PKS hátrányairól
Minden rejtjelzési eljárás készítője számít arra,
hogy eljárása a nyilvánosság, így az ellenség előtt is ismertté válik, ezért
felkészül a fejtés kivédésére. Mégis a gyakorlatban az eljárás megismerése igen
fáradságos. A PKS első hátrányaként tekinthetjük, hogy az eljárás megismerésére
nem kell jelentős időt, fáradtságot és pénzt fordítani. Egy második hátrány,
hogy a PKS biztonsága azon múlik, hogy a K-ból
a K-1 –be vezető függvényt
(one-way function, trap door) valóban milyen nehéz meghatározni.
A knap-sack eljárás mutatja, hogy itt mennyire lehet tévedni a biztonság megítélésében. Az IEEE 1983. évi információ-elméleti konferenciáján Desmedt előadásában pont azt a knap-sack feladatot fejtette meg néhány perc alatt, amelyet a hallgatóság körében ülő a knap-sack rendszert bevezető Hellman gyarkorlatilag megoldhatatlannak tartott. Később Desmedt közölte eredményeit [15]-ben, majd [62]-ben Shamir foglalta össze a Merkle-Hellman féle algoritmus (knap-sack) gyengéit.
Shamir véleménye szerint módszere csak az
alapeljárásra ad fejtési eljárást, az iterált változatra nem, de a készítők nem
voltak felkészülve ilyen gyors és látványos vereségre. Ugyancsak intő jel, hogy
az algoritmus kis teljesítményű számítógépen is futtatható (lásd [62])..
A biztonság ugyanakkor megköveteli egy
rejtjel rendszertől, hogy ellenálljon bármilyen nagy sebességű vagy akár
párhuzamos működésű célgépeknek is (lásd [05]).
A.Shamir [62]-ben azt írja, hogy „A rejtjel rendszer akkor válik használhatatlanná, ha a kulcsok többsége hathatósan fejthető.” Sajnos ezzel a gyakorlatban elfogadhatatlan állásponttal sok, nem gyakorlati szakember is egyetért. Ez ugyanis a teljes kipróbálás módszerét (brute force) tekinti a megfejthetőség abszolút mércéjének, ami csak a legkedvezőtlenebb esetet jelenti.
Ebből a szempontból nem csupán érdekes történeti
tény, hogy a „one-way function” gondolata nem egészen új, hiszen azt csírájában
már a Hill-féle eljárás is tartalmazta [28],
[29],
melynek lényege: Legyen a nyílt szöveg egy A
nxn méretű mátrix formában írva, a kulcs K egy ugyancsak nxn
méretű invertálható mártrix, ekkor a rejtjeles szöveg R=AK
megfejthető, mivel RK-1=AKK-1=A.
Látható tehát, hogy 1929-ben a mátrix invertálás, a biztonság szempontjából
elegendően nehéz feladatnak tűnt, ami ma már nagy n esetén sem az. Így elképzelhető, hogy a ma megfelelő biztonságot
nyújtó PKS eljárások a számítástechnika ismert ütemű fejlődését figyelembe
véve, belátható időn belül megfejthetővé válnak. Ez azt mutatja, hogy azok az
eljárások, amelyek alapvetően a kulcstér rendkívül nagy számosságára és a kulcs
teljes kipróbálással való megkeresésére alapoznak, legfeljebb átmeneti
biztonságot adhatnak.
A továbbiakban megmutatjuk, hogy a PKS és ezen belül
az RSA biztonságát tovább gyengíti, hogy a kulcsokat nem a teljes kulcstérben,
hanem annak csak bizonyos tulajdonságú részhalmazaiban kell keresni.
Az RSA algoritmus
A Merkle-Hellman eljárás után nem sokkal újabb PKS
került nyilvánosságra [53]. Ezt az eljárást a
szerzők nevének kezdő betűi után RSA (Rivest-Shamir-Addleman) rendszernek
szokás nevezni. Az RSA rendszer a következő módon jellemezhető:
Válasszunk két különböző, nagy (legalább 100
decimális jegyű) prímszámot, p-t és q-t. Ezután válasszunk véletlenszerűen
egy e számot, amely (p-1)-hez és (q-1)-hez egyaránt relatív prím. Legyen N=pq
, ekkor j(N)=(p-1)(q-1). Ezután határozzuk meg azt
az egyetlen d számot, amelyre
fennáll, hogy ed º 1 mod j(N) .
Ha N és e ismert például egy telefonkönyvszerű
listából, akkor egy M üzenetet úgy
rejtjelzünk, hogy az üzenetet felosztjuk k=[logN
+
1]
hosszúságú blokkokra, legyen X egy
ilyen blokk, akkor R(X)=
Xe mod N lesz a
rejtjelzett üzenet egy blokkja. A címzett (és csak ő) ismeri d-t így a megoldás R(X)d =Xed =X adódik.
A rejtlejzés igen egyszerű Knuth szerint [31]
Xe mod N kiszámítása
ismételt négyzetre emeléssel legfeljebb [2
log2 (e)] mod
N szerinti szorzást igényel. E tanulmány későbbi részében ugyanakkor látni
fogjuk, hogy nagy e és N értékekre (ez igaz már a fent
megjelölt nagyságrendre) az RSA nem ad kellő gyorsaságot folyamatos szöveg
rejtjelzésére, így azt inkább elektronikus aláírásra, vagy kulcstovábbításra
használják.
Az RSA eljárás igen nagy népszerűsítést kapott a
Scientific American 1977. augusztusi számában, ahol M.Gardner, az USA
nagytekintélyű népszerűsítő matematikusa írt cikket [23],
hasonló lelkesedést mutatott [63] is. Az egyébként
kitűnő [58]
kötet is úgy írt a 115. oldalon, hogy egy 100 jegyű szám faktorizációja a
leggyorsabb számítógépen is 40 trillió évet venne igénybe, ami 2000-szer
hosszabb idő mint a világegyetem fennállásának ideje. Bár a szerző
tárgyilagosan hozzáteszi, hogy vannak olyan vélemények, amelyek ezzel
ellentétesek [49],
[05].
Bár érdemes megjegyezni, hogy a faktorizációs
probléma megoldása és az RSA megfejthetősége közötti azonosság csak
feltételezés. Ezt igyekszünk ebben a tanulmányban megcáfolni. A következőkben
fel kívánjuk vázolni, hogy a faktorizációs probléma megoldásának csak igen
speciális esetét igényli az RSA megfejtése. Továbbá a faktorizációs probléma
megoldásának helyzete a gépi háttér fejlődésével évről évre jelentősen
változik.
Ezzel kapcsolatosak
M.Gardner [23]-ből származó 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.”
Prímfaktorizáció
A faktorizációs probléma két lépésben közelíthető [72].
Az első lépés egy N számról
eldönteni, hogy prímszám-e, majd megtalálni N
prímtényezőit. A prímtesztek igen előrehaladott állapotban vannak, egy 200
jegyből álló számra vonatkozóan sikerült olyan algoritmust készíteni, amely
néhány másodpercen belül eldönti, hogy N
prím-e vagy sem [12].
Mai ismereteink szerint a legjobb prím tesztre vontkozó algoritmus exp(c
) bit műveletet igényel, míg a leggyorsabb faktorizációs
algoritmus idő igénye exp(c
).
Annak eldöntésében, hogy a vizsgált N prím-e vagy összetett szám, segít
Fermat egy híres tétele, amely szerint, ha N
prím és (a,N)=1 (a és N
relatív prímek), akkor fennáll, hogy aN-1º1 mod N. Ebből következik, hogy ha faktorizáció elvégzése nélkül találunk
olyan a számot amelyre fennáll, hogy aN-1
nem kongruens 1 mod N, akkor
N összetett szám.
Itt kell megjegyezni, hogy Fermat eme tételének
teljesülése, N prím voltának csak
szükséges, de nem elégséges feltétele. Azokat az összetett N számokat amelyekre a fenti kongurencia teljesül, legalább egy (a, N)=1 esetén, álprímnek szokás nevezni. Sarrus
1819-ben megmutatta, hogy 341 álprím,
mivel egyrészt teljesül a 2340º 1 mod 341 kongurencia, másrészt fennáll, hogy 341=11x31.
Érdekes megjegyezni, hogy ugyanezt felismerte már Bolyai János is ([30]
79.oldal). H.C.Pocklington már 1914-ben használta a fent leírt módszert prím
szitaként.
Egy N
páratlan álprímszámot erősnek nevezünk az a
bázisra vonatkozóan, ha 
, ahol 
a Jacobi szimbolumot
jelöli[2].
Az N
álprímet akkor nevezzük Carmichael számnak, ha aN-1º1 mod N az összes a-ra teljesül, ha (a,N)=1
fennáll. D.H. Lehmer [35]-ban megmutatta, hogy
nem létezik erős Carmichael szám. A legtöbb prímszitálási eljárás Fermat
tételéből, vagy ennek valamilyen általánosításából indul ki. A prímszitálási
eljárások meggyorsítása érdekében olyan valószínűségi eljárások is elterjedtek
amelyek az álprímeket, illetve az erős álprímeket is prímnek tekintik, vagyis
csak bizonyos valószínűséggel döntik el egy adott számról, hogy prím-e vagy
sem. A prímteszteknek egy valószínűségi megközelítése található például [22]-ben,
ennek segítségével egy N páratlan
egészről egy multiprocesszoros gépen m=6(mlog2N)
lépésben nagy valószínűséggel el lehet dönteni, hogy prím-e. Nevezetesen az
említett algoritmus (amit Solovay-Strassen próbának neveznek) biztosan
megállapítja, ha egy N szám
összetett, de ha N prím, akkor
legfeljebb 
valószínűséggel
összetettnek tekinti.
A Solovay-Strassen próbához legyen N>1
páratlan szám és tekintsük az 
kongruenciát, ahol 
a Jacobi-szimbólumot
jelöli. Ha N prím, akkor a fenti
kongruencia minden esetben teljesül, ha a
nem osztható N-nel. Ha N összetett, akkor a fenti kongruencia
egy mod N teljes maradékrendszer
elemeinek kevesebb, mint a felére teljesül.
A történelmi hűség kedvéért meg kell említeni, hogy
a valószínűségi eljárás gondolata már [47]-ben
is felmerült. A [47]-ben
és a [68]-ban
közölt algoritmusokat egy időben, egymástól függetlenül közölték. Néhány évvel
később M.O.Rabin [51]-ben
lényegében ugyanezt a valószínűségi prímszita gondolatot ismétli meg, bár a
Rabin féle algoritmus nem azonos a Solovay-Strassen féle algoritmussal. Az
algoritmus ismertetésére azért térünk ki, mert gyakorlati tapasztalatok szerint
jobb eredményeket ad, mint a Solovay-Stressen algoritmus. A Rabin féle
valószínűségi prímszita a következőkkel jellemezhető:
Legyen N=2rd+1,
ahol d páratlan. Válasszunk egy 1 és N-1
közé eső a-t véletlenszerűen.
Fogadjuk el a-t prímnek, ha a
következő két kongruencia közül legalább az egyik teljesül:
valamely j-re
(
). Ha egyik kongurencia sem teljesül akkor a-t nem fogadjuk el prímnek. Az eljárás
különböző véletlenszerűen választott a-ra
megismételhető.
A prím szitálás, majd ennek gépesítése már sok évtizede foglalkoztatja a rejtjelfejtőket. [56]-ból megtudhatjuk, hogy a német rejtjelfejtés már az 1930-as években felfigyelt D.H.Lehmer amerikai matematikus mechanikus működésű prím szitájára [18]. A folytatás már az elektronikus számítógépek megjelenésének idejére esett. D.H.Lehmer eredményei [33], [34]-ben találhatók, melyek egyik alapgondolata, hogy a prímszitálásra felhasználható a Wilson tétel, mely szerint
(N-1)!+1º0 mod N fennállása N prím voltára szükséges és elégséges feltételt ad.
[44]-ben
található tétel szerint, ha N nem
prímszám, akkor az általánosított Riemann sejtés igazságából következik, hogy
létezik olyan 
, amely a-ra mint
bázisra N egy erős álprím. (A tétel
használhatóságát rontja, hogy ma sem tudjuk, hogy az általánosított Riemann
sejtés igaz-e?) További prímszám szitáló algoritmusok találhatók [12]-ben.
A prímsziták sorát jelen szerző eredményével zárjuk,
amely szerint bizonyítást nyert a következő tétel [19]: Legyenek
N, k, u, v természetes számok, valamint u,v 
1, ekkor
N= 6k+1 akkor és csak akkor összetett szám, ha k = 6uv + u + v vagy
k= 6uv - u - v
N= 6k -1 akkor és csak akkor összetett szám, ha k = 6uv - u + v
vagy k= 6uv +u - v
Erre a tételre épül a CPS, azaz a Complementary Prime Sieve (Komplementer Prímszita).
Ugyanakkor [72]-ben
a szerző bemutatja, hogy zsebszámológépen is igen rövid idő alatt lehet 20
jegyű számokat faktorizálni.
Történetileg a XX. század első harmadáról datálható, ám mai szemmel is elég hatékonynak mondható faktorizációs eljárás alapját a következő eredmény képezi:
Ha x2ºy2 mod N, akkor x-y és N legnagyobb közös osztója, N-nek egy nem triviális osztója lehet. Ezt a módszert CFRAC-nak nevezik. A
módszer igen régen ismert, [72] a történetet az
1920-as évekig vezeti vissza, de véleményem szerint a CFRAC gondolata régebbi,
mivel már Fermatnak Marsennéhez írt 1638. december 26-án kelt levelében is
szerepelt. Igazi fellendüléshez a nagy teljesítményű számítógépek megjelenésére
volt szükség. A CFRAC módszer egy N
számot kb. 
művelettel
faktorizál. Nyilvánvalóan a CFRAC nem más, mint négyzetgyökvonás mod N
maradékosztályok szorzás félcsoportjában. Például 72º22 mod 15, vagyis 4-nek
legalább két gyöke van mod 15, a 7 és a 2. Az adott esetben adódik, hogy (7-2)(7+2) º0 mod 15 vagyis (5,15)=5 és (9,15)=3 osztói 15-nek.
Később látni fogjuk és ki fogjuk használni, hogy a mod N maradék osztályok szorzás
félcsoportja ZN (a bennünket érdeklő N=pq esetben) csoportok egyesítéseként állítható elő vagyis Zpq
inverz félcsoport, ezért a négyzetgyökvonás itt is végeredményben csoportban
történik. Számos algoritmus ismeretes az x2ºy2 mod N diofantikus kongruencia megoldására.
[48]-ban egy új
faktorizációs eljárás került bevezetésre, a Quadratikus szita [17],
amely nagyon hasonlít CFRAC-hoz. A quadratikus szitát az 1970-es évek végének
szuperszámítógépére, a CRAY-1 gépre alkalmazták[3]
és sikerült a 3128+1, 2253-1, 1064+1, 3124+1,
53, 55, 55 és 58 jegyű számoknak a 235-nél nagyobb prímfaktorait
egyenként kb. 8 óra gépidővel meghatározni. A CRAY-2 1985-ben megjelent
számítógép sebessége több mint hatvanszorosan meghaladja a CRAY-1 sebességét.
Így ezzel a sebességgel az ismertetett faktorizációs feladat megoldásához 8 perc
volt szükséges. A számítástechnika rohamos fejlődését jellemzi, hogy a mai
szuperszámítógépek sebessége a tera, azaz a 1012 művelet per
secundum tartományban mozog, ami a CRAY-1 sebességének az ezerszerese, így egy
ilyen gépen a fenti feladat már fél percet sem vesz igénybe.
Végül, ha tekintetbe vesszük, hogy az RSA lényegéből
fakad az, hogy a modulus speciális szerkezetű (két azonos nagyságrendű prímszám
szorzata) továbbá, hogy a faktorizáció Monte Carlo módszer segítségével
tökéletesen megfelel, akkor az RSA biztonságának értékelésénél igen nagy
óvatossággal lehet csak nyilatkozni és nem lehet az [58]-ban
és a [23]-ben
leírt értékeléssel egyetérteni. Ezekre az értékelésekre igaz ugyanis Giordono
Bruno 1585-ből származó megállapítása, mely szerint „Si non é vero, é molto ben trovato”, azaz „Ha nem is igaz, jól van kitalálva”.
Érdemes megjegyezni ugyanakkor, hogy a
prímfaktorizációra szolgáló célgépek építésénél még vannak sebesség tartalékok.
A kínai maradéktételen alapuló aritmetikák alapvető összefoglaló műve [69].
Az RSA támadása
prímfaktorizáció felhasználása nélkül
Az előző fejezetben leírtuk, hogyan juthatunk el j(N) meghatározásához prímfaktorizáció segítségével.
Ebben a fejezetben igazoljuk, hogy az RSA megfejtéséhez nem szükséges
feltétlenül j(N) meghatározása,
illetve, hogy j(N) meghatározható N faktorizációja nélkül is. A
következőkben néhány gondolatot mutatunk be annak alátámasztására, hogy j(N) meghatározása sem szükségszerű. A gondolatok
kifejtéséhez meg kell vizsgálni közelebbről a mod N maradékosztályok szorzás félcsoportját ZN-t és az 
, ha (a,N)=1 (Kis
Fermat tétel) néhány általánosítását.
Absztrakt algebrai megfontolásokból adódik, hogy N=pq esetén 
. Eme négy komponens mindegyike csoport és az 1-t kivéve elemidegenek. Ez az egyes
komponensek rendjét vizsgálva könnyen látható, hiszen
pq=(p-1)(q-1)+p+q+1-2=pq-q-p+1+p+q-1=pq.
Ha találunk egy olyan a elemet amely Zp-ben vagy Zq-ban van, akkor (a,N)¹1 miatt (a,N)=p vagy (a,N)=q adódik és a teljes rendszer megfejtését megkapjuk.
Tehát feltehetjük, hogy 
. Mivel 
a rendje j(N),
tehát a rendje osztója j(N)-nek és ezért fennáll, hogy 
, ha (a,N)=1. Ez a
rövid és triviális okfejtés a kis Fermat tétel egy félcsoportelméleti
bizonyításának is tekinthető.
Ismeretes azonban, hogy ilyen általános kitevő j(N) osztói között is van, ezek közül a legkisebb általános kitevőt nevezik Carmichael számnak, mivel a fogalmat először Carmichael vezette be [11], j(N) helyettesítése Carmichael számmal [64]-ben is kifejtett gondolat. (ott ezt Haupt kitevőnek nevezik.)
Az N-hez tartozó Carmichael
számot jelölje l(N), ekkor l(N)=1, ha N=1, l(N)=2d-2,
ha N=2d és d>2, l(N)=j(N), ha
N=2,4,pd (p páratlan prímszám). Ha 
, akkor 
, ahol [
]
jelöli a legkisebb közös többszöröst. A fentiek miatt fennáll, hogy 
, ha (a,N)=1.
Az RSA rendszer fejtési kísérleteinél tehát l(N)-t
is lehet használni j(N)
helyett. Ez l(N)£ j(N)
miatt előnyös. Következésképpen az RSA felhasználójának törekedni kell arra,
hogy a 
hányados kicsi legyen
(vagyis a rendszer erről az oldalról ne legyen könnyen támadható).
A kis Fermat tételnek számos másfajta általánosítása is létezik.
Rédei Lászlótól származik a következő tétel tetszőleges a-ra (lásd [66]): 
Már Gauss is tudta, hogy tetszőleges a esetén 
, ahol m
a Möbius függvényt jelöli (lásd [64] továbbá Gauss Werke T2, 1863, S222).
Singmaster [66]-ben azt bizonyította be, hogy 
esetén legyen L(N)=max(e1,e2….en),
akkor tetszőleges N-re és a-ra
fennáll, hogy 
.
Ugyancsak [66]-ben található a következő tétel: Legyen r>s, akkor áll fenn arºas mod N minden a-ra, ha l(N)-nek r-s osztója.
Az eddig áttekintett általánosításokban j(N) értékét helyettesítettük egy kisebb értékkel. Az RSA támadása szempontjából az itt leírt általánosított Fermat tételek jelentősége az, hogy a j(N)-nél kisebb hatványkitevők megkönnyíthetik az egyes alapokra vonatkozó teljes kipróbálást.
Egy további általánosítás leírásakor szükségünk lesz a következő definícióra: az A gyűrű (félcsoport) a elemét akkor nevezzük regulárisnak (esetenként Neumann regulárisnak), ha van A-nak legalább egy olyan x eleme, hogy fennálljon az axa=a egyenlőség. José Morgado több cikkében [41],[40] azzal foglalkozott, hogy jellemezze ZN-ben a reguláris elemeket. Morgado főtétele szerint a ZN-beli elem akkor és csak akkor reguláris, ha (a,N) = (a2,N). Ebből következik, hogy ha N négyzetmentes, akkor ZN összes eleme reguláris. Ezért négyzetmentes N esetén bármely a-ra létezik legalább egy olyan x, hogy az a2xºa mod N kongruencia teljesül. A fenti kongruencia, illetve a belőle nyerhető a2x-a = cN diofantikus egyenlet az RSA rendszer elleni támadásokba jelentős szerepet játszik.
A kis Fermat tétel általánosításainak egy másik csoportját azok az általánosítások képezik, amelyek Zn helyett egy másik félcsoportban vagy gyűrűben érvényesek. Nyilvánvaló, hogy az RSA rendszer elleni támadásnál a kis Fermat tételnek csak azok az általánosításai hasznosak, amelyek Zn-ben érvényesek, azonban az RSA-hoz hasonló, de más algebrai sturktúrában operáló rejtjelző eljárások vizsgálatához hasznos lehet Zn-től eltérő algebrai struktúrákban a kis Fermat tétel általánosítási lehetőségeinek vizsgálata.
Schwarz mutatott rá [59]-ban arra, hogy tetszőleges véges félcsoport S tetszőleges a elemére igaz, hogy ak = ak+d , ahol az ak,…,ak+d-1 elemek egy d-edrendű ciklikus csoportot alkotnak. Schwarz arra hívja fel a figyelmet, hogy az ak = ak+d képlet a legáltalánosabb formája a kis Fermat tételnek, félcsoportokban.
Ugyancsak [59]-ben található, hogy ZN-ben
a kis Fermat tétel általánosításának 
alakja mellett
felírható a még általánosabb képlet nevezetesen:
, ahol v(N)=max(d1,d2,…,dr),
ha 
Könnyű látni, hogy az RSA-nál N=pq miatt v(N)=1, tehát Zpq bármely eleme által generált részstruktúra csoport.
[59]-ban a szerző megvizsgálta a kis Fermat tétel általánosítását Bn egy részfélcsoportjára Cn-re. Cn elemei az olyan nxn méretű Boole mátrixok, amelyek sorai egymás ciklikus permutáltjai. Schwarz [59]-ban kimutatta, hogy ha A eleme Cn-nek, akkor fennáll, hogy An-1=A2n-1.
Schwarz eredménye azért is érdekes a rejtjelzés szempontjából, mert a kétdimenziós rejtjelzés (képek rejtjelzése) egyre nagyobb elméleti és gyakorlati figyelmet kap. További érdekességet kölcsönöz a fentieknek Ecker [21]-ben kifejtett véleménye, amely szerint a Zn feletti mátrixok multiplikatív félcsoportja az RSA rendszer kiterjesztésének legtöbbet ígérő útja. Ebből a szempontból érdemes megemlíteni, hogy Davis tetszőleges mátrixokra is általánosította a kis Fermat tételt.
[64]-ben mutattak rá a szerzők az RSA rendszer olyan gyengeségére, amely a megfejtésre bizonyos esetben, a faktorizációs probléma megkerülésével is lehetőséget ad. Ez a módszer a felülrejtjelzés, vagyis a rejtjeles szövegen a rejtjelzés ismételt elvégzése. Legyen ugyanis a nyílt szöveg C , a rejtjelzési kitevő e, akkor a rejtjeles szöveg Ce.
Mivel C relatív prím az
N modulushoz, azaz 
, tehát Ce
is relatív prím N-hez, így Ce hatványozásával megkapjuk C-t. Könnyű belátni ugyanis, hogy ha 
valamilyen s-re, akkor 
. [64]-ben
arra mutattak rá a szerzők, hogy igen nagy N
és e esetén is lehet s nagyon kicsi. Erre konkrét példát
mutattam be [17]-ben,
ahol N hatvan decimális számjegyből
áll és az ezzel titkosított üzenet hét lépésben megfejthető.
Simmonsnak [64] megjelenése után komoly nézeteltérése volt az NSA-val és valószínűleg ennek tulajdonítható, hogy Rivest [54]-ben kifejtett érvelését Simmons [65]-ben elfogadta. Rivest ugyanis azt állította, hogy ha az RSA javaslói [53]-ban leírt feltételeit kiegészítjük azzal, hogy j(p’) és j(q’) legnagyobb közös osztója legyen kicsi és j(p’)-nek, valamint j(q’)-nek legyen nagy prímfaktora p’’ illetve q’’, akkor az eljárás biztonságos. Rivest végeredményben az erős prímek használatát javasolta.
Nem lehet másra vélni Simmons beletörődését ebbe a tarthatatlan érvelésbe, mint az NSA hatásának. Annak bizonyítására, hogy nem teljesen alaptalan a feltételezésünk, álljon itt a Cryptologia 1978. évfolyamának 193-194 oldalon található szerkesztőségi közleménye, amely szerint az Institute for Defence Analysis (IDA) titkos ülése (az ülésről szóló híradást lásd Science 14 april 1978) úgy döntött, hogy az RSA gyengeségeinek megvitatása nem célszerű a nyilvánosság előtt. Az NSA álláspontját nem a konkrét esetre vonatkozóan, hanem általánosságban jól tükrözi [43], [36].
A [64]-ben indított támadást az RSA ellen, a svéd Herlestam folytatta [27]-ban. Rivest újra válaszolt [55]-ban, de a további támadásokat (lásd [03],[67]) már válasz nélkül hagyta. Összességében megállapítható, hogy Rivest a viszont támadást azért hagyta abba, mert védekezése és kiegészítő feltételei sem küszöbölik ki az RSA rendszer támadhatóságát.
Könnyű látni, hogy a felülrejtjelzés azt az egyszerű tényt használja ki, hogy egy véges csoport összes elemeit egy a rendhez relatív prím hatványra emelve, újra az adott csoportot kapjuk. [64]-ben a szerzők másik gondolata ZN-ben az alacsony rendű elemek meghatározása, mivel ez a felülrejtjelzéssel kombinálva szolgálhatja az RSA rendszernek, a modulus prímfaktorizációja nélküli megfejtését.
Mullin ezredes [42]-ben egy látszólag teljesen elméleti kérdést vizsgál, amelyről a következőkben megmutatjuk, hogy mennyire gyakorlativá tehető.
Mullin a következő formulát vezeti le: j(N)d(N)=(N-d-1)(N+d-1), ahol d(N) N osztóinak összegét jelöli, N=pq , ahol p és q prímek, továbbá p-q=d, d³1. Az előbbi összefüggést diofantoszi definiáló relációnak nevezi, majd vizsgálja, hogy milyen feltételek mellett megfordítható a diofantoszi definiáló reláció. Azt, hogy nem minden esetben megfordítható, a következő példán látható: N=24, d=7 esetén fennáll, hogy j(24)d(24)=16x30. Ennek ellenére 24 nem két prímszám szorzata és nem létezik két olyan prím, amelynek különbsége 7.
Ugyanakkor d=2 esetében az iker prímeket karakterizálja a diofantoszi definiáló reláció, vagyis N akkor és csak akkor egy ikerprím pár szorzata, ha j(N)d(N)=(N-3)(N+1). [42] szerint a diofantoszi definiáló reláció megfordítása igaz d=1, 2, 6, 11, 12 esetében is. Példa: p=5, q=7, ekkor N=35, j(N)=24, d(N)=48, tehát 24x48=1152=(35-3)(35+1)=32x36
A következőkben néhány olyan eredményt mutatunk be, ami kapcsolódik [42]-höz és aminek jelentős gyakorlati jelentősége is van. [42] alapötletének a jelen tanulmány szerzője azt tartja, hogy p+q helyett 2p-d-vel lehet számolni, ugyanis tudjuk, hogy ha N=pq=p(p-d), akkor
N=p2-pd és j(N)=N+1-2p+d adódik.
Világos, hogy p csak akkor lehet egész szám, ha létezik olyan t egész szám, hogy fennálljon a d2 + 4N = t2 összefüggés. Ily módon egy olyan speciális diofantikus egyenletet nyerünk, amelynek vizsgálata a babilóniai időkre, (IBN AL HUSAIN idejére) nyúlik vissza. Néhány évszázaddal később ezt Palermoi János problémájaként ismerték és Leonardo Pisano (Fibonacci) és Fermat foglalkoztak a probléma megoldásával. (Lásd Scritti di Leonardo Pisano, Roma, Publ. de Boncompagni 1962 T.2.p272 Fermat Oeveres Ed P.Tannery et Ch.Henry. Paris 1891-1922 T.3. ch 4.)
IBN AL HUSAIN, majd később Leonardo Pisano és Fermat is megmutatta, hogy az RSA megfejtése szempontjából fontos d2+4N=t2 már korábban felírt diafontikus egyenletben N nem lehet négyzetszám.[4]
Fermat azt is észrevette, hogy a fenti tételből következik a később róla elnevezett sejtés (xn+yn=zn) igazsága n=4 esetben.
Könnyen látható, hogy a vizsgált diafonikus egyenlet lényegében azonos a CFRAC-nál szereplő kongurenciával. Ezért az a korábban leírt kétségünk, hogy a CFRAC nem a Williams által [72]-ben leírt módon az 1920-as évekből való, hanem sokkal régebbi, nem csak Fermat-val támasztható alá, hanem IBN AL HUSAIN tevékenységével is.
Mullin gondolatához hasonló megközelítést alkalmazott D.N.Lehmer
(Bull. Amer.Math.Soc. 13(1906-7) 501-502), aki feltette, hogy N=p(p-d) és 
. Ezzel a megkötéssel igen gyors algoritmust dolgozott ki p és q
meghatározására.
Az RSA egy további gyengesége, hogy véletlenszerű kompromisszumok felülrejtjelzésével az általános megoldási kitevő egyes osztói meghatározhatók és az általános kitevő az egyes rész megoldásokból nyert kitevők szorzatával közelíthető.
Ha a tervezett RSA rendszerben valaki két helyre ugyanazt a C nyilt szöveget kívánja rejtjelezve
eljuttatni, akkor 
rejtjeles szövegek
keletkeznek, ha feltesszük, hogy (e1,e2)=1,
akkor az s1e1+s2e2=1
diofantikus egyenletnek van egész megoldása és az könnyen kiszámítható. Ha
viszont s1 és s2 ismert, akkor C úgy nyerhető, hogy 
. Ebből következik, hogy az RSA rendszer körtávirati formában
nem alkalmazható.
Jelen tanulmányban már több alkalommal foglalkoztunk az x2 º
y2 mod N kongruenciákkal, illetve az x2–y2=cN típusú diofantikus egyenletekkel.
Annak ellenére, hogy ezek megoldására kidolgozott algoritmusok vannak, fel
kívánjuk hívni a figyelmet, hogy a megoldáshoz vezető egyik út, ha az egész
megoldások helyett racionális megoldásokkal is megelégszünk. (Van olyan eset,
amikor egész megoldás nincsen csak racionális). Egy példán keresztül mutatjuk
be a racionális megoldást. Tekintsük az x2–y2=cN
egyenletet és legyen c=1, N=5, akkor 
, mivel 
. Így 5 „racionális prím” felbontása 
Az RSA rejtjelzés nemcsak mint önálló eljárás kerül felhasználásra, hanem elektronikus aláírásként (electronic signature) is, valamint a DES kulcs szétosztó eljárásaival kombinálva (lásd pl. [50],[53],[38]).
Az RSA részleges megfejtése
Az eddigiek során olyan eljárásokat vettünk számba, amelyek bizonyos feltételek teljesülése esetén az RSA-val rejtjelzett üzenetet úgy tudják megfejteni, hogy az eredeti nyilt szöveg hiba nélkül előálljon. A rejtjelfejtésben erre sokszor nincsen szükség, mert ha egy C nyílt szöveg helyett egy olyan C’ nyílt szöveget sikerül előállítani, amely kevés hibát tartalmaz (azaz C és C’ közötti Hamming távolság kicsi), akkor a nem mesterséges nyelvek redundanciája miatt, C egyrészt hiba nélkül visszaállítható, másrészt C egyes töredékeinek visszaállítása is bírhat operatív értékkel. Dénes J. [16]-ban a leképezésekre és permutációkra vonatkozóan bevezette a k-rendet, amely pontosan a következőt jelenti:
Jelölje Sn ,
illetve Tn a szimmetrikus
csoportot, illetve az n-ed fokú
szimmetrikus félcsoportot, 
és 
elemei Tn-nek illetve Sn-nek. Az a és b
közötti távolságot d(a,b)-val
jelöljük és d(a,b)=m akkor, ha pontosan m olyan különböző i érték
létezik, hogy bi¹ci. (Nyilvánvaló, hogy Sn két eleme között hasonlóan
definiálhatjuk a távolságot.)
aÎTn k-rendjét, 0k-t úgy definiáljuk, hogy legyen az a legkisebb r pozitív egész szám, amelyre fennáll, hogy ar=b és d(b,e)=k ahol e az a által generált ciklus félcsoport idempotensét jelöli. (aÎSn esetén a k-rendjét hasonló módon lehet definiálni.)
Zn-ben az elemek k-rendjét hasonló módon lehet definiálni. Legyen C egy nyílt szöveg és Ce=M a rejtjelzett szöveg. A jelen tanulmány szerzőjének az a sejtése, hogy amennyiben felülrejtjelzéssel nem C-t keressük, hanem egy olyan C’-t amelyre fennáll, hogy d(C,C’)£ k, akkor az egyébként gondos körültekintéssel kiválasztott RSA paraméterek sem jelentenek védelmet a részleges megfejtés ellen.
Az RSA értékelése
Keveset tudunk a hivatásos rejtjelfejtők (pl. NSA) álláspontjáról. Az a kevés információ, amely nyilvánosságra került publikációkból nyerhető arra mutat, hogy az NSA a DES-t részesíti előnybe a PKS-sel szemben. Ugyanakkor komoly erőfeszítéseket tesz, hogy a rejtjelzési kutatásokat ellenőrizni tudja. Már a hagyományos távközlő csatornán keresztüli rejtjelzésre is komoly nyomás nehezedik azáltal, hogy az űrtávközlés elterjedésével, üzleti okokból, a rejtjelzésre kerülő üzenetek mennyisége ugrásszerűen megnőtt.
Az űrtávközlés [73] szerint nem csak a klasszikus értelemben vett rejtjelzési problémákat veti fel, hanem az úgynevezett „titok megosztást” is. Ezt a fogalmat Shamir [60]-ban vezette be. Annak megelőzésére, hogy egy titok (pl. rejtjel kulcs) műszaki hiba miatt vagy árulás miatt elveszhessen, osszuk fel az S titkot (egy 0,1 sorozatot) n részre, ezeket jelölje S1, S2,…,Sn. Az űrtávközlésben minden egyes Si egy állomást jelölhet. A titok megosztó rendszer lényege az, hogy S egyértelműen visszaállítható az egyéni kulcsok közül bármely k<n ismeretéből, ugyanakkor k-1 vagy kevesebb egyéni kulcsból S egyértelműen nem állítható vissza.
A titok megosztó rendszerek között PKS is előfordul, de [73]-ban sikerült megmutatni, hogy a titok megosztó rendszerek egységes tárgyalását ortogonális latin négyzetek segítségével lehet megvalósítani.
A rejtjelzés ugrásszerű elterjedéséből és újszerűségéből adódó megnövekvő hatósági feladatok indították az USA kormányát új irányelvek kiadására. További nehézséget jelent, hogy a rejtjelzés híradástechnikai csatornán keresztüli módján kívül megjelentek a számítógépes háttértárakban (pl. mágneslemezen) levő adatok rejtjelzése, valamint a „smart card”-ok is ebbe a kategóriába tartoznak.
I R O D A L O M
[01] F.L. Bauer: Cryptology methode and maxims, Cryptography, Prog, Burg. Feuersten, Ed. T. Beth Lecture Notes in computer science 149, 1982, 31-48
[02] H.J.Beker, F.C. Piper: Communications security. A. survey of cryptography. IEEE Proc. 129(1982) No.6 357-376
[03] G.R. Blakley, I. Borosh: Riveat Shamir Adlemann public key cryptosystems do not always ponceal message. Computers and Mathematics with applications 5(1979) 169-178.
[04] D.Boneh-R.Venkatesan: Breaking RSA may not be equivalent to factoring. In: Advances in Cryptology, Proc. Eurocrypt ’98, 1998. pp 25-34.
[05] G. Brassard: A note on the complexity of cryptography.
IEEE Trans. IT-25 1979. 232-233
[06] G.Brassard: A Time-Luck Trade off in Relativized Cryptography. Journal of Computer and System Sciences 22(1981) 280-311
[07] G. Brassard: Relativized Cryptography. IEEE Trans. IT 29(1983) 877-893
[08] R.P. Brent, J.H.Pollard: Factorization of the eighth Fermat number. Math.Comp 36(1981). 627-630
[09] Stephen Budiansky: ELMÉK HARCA (A Második Világháború Kódfejtésének Teljes Története), Vince Könyvkiadó, Budapest, 2005.
[10] N.P.Callas: An application of computers to cryptography. Cryptologia 2(1978) 350-364
[11] R.D. Carmichael: Note on a new number theory function. Amer. Math. Soc. Bull. 16(1910) 232-238
[12] R.Crandall-C.Pomerance: Prime Numbers (A Computational Perspective), Springer, New York, 2000.
[13] D.W. Davies, W.L. Price, G.I. Parkin: An evaluation of public key cryptosystems. Information Privacy 2(1980) 138-154
[14] D.D.Denning: Digital signatures with RSA and other Public-Key Cryptosystems.Communications ACM 27(1984) 388-395
[15] Y.Desmedt, J. Vandewalle, R.Govaerts: Critical analysis of the security of Knapsack
public key Algorithm.
IEEE Transaction of Information Theory 1984. 601-611
[16] J. Dénes: Research problem 27. Periodica Math. Hung 11(1980) 177-178
[17] Dénes Tamás: Új eredmények az RSA kulcsok megfejtéséhez, Híradástechnika, 2002/1. 47-55
[18] Dénes Tamás: Titkos-számítógép-történet, Aranykönyv Kiadó, Budapest, 2003.
[19] T. Dénes: Complementary prime-sieve, PUre
Mathematics and Applications, Vol.12 (2002), No. 2, pp. 197-207
[20] W.Diffie, M. E. Hellmann: New directions in cryptography.
IEEETrans. Infor. Th. IT-22 Nov. 1976. 644-654
[21] A. Ecker: Finite semigroupe and the RSA-Cryptosystem. Cryptography-Proc. Burg Feuersten, Ed. T. Beth, Lecturs Notes in Computer Science 149,(1982) 353-369
[22] Freud Róbert-Gyarmati Edit: Számelmélet, Nemzeti Tankönyvkiadó, Budapest, 2000.
[23] M. Gardner: A new kind of cipher that would take millions of years to break. Scientific American 237(1977) No2. 120-124
[24] J.A. Gordon: The use of intractable problems in cryptography. Information Privacy 2(1980) 178-184
[25] N.E. Hellman: An overview of public key cryptography, IEEE Communications Society, 16(1978), 24-31
[26] M.E. Hellmann: The mathematics of public-key cryptography. Scientific American 214(1979) 2 szám 130-139
[27] T. Herlestam: Critical remarks on some public-key cryptosystems. BIT 18(1978) 493-496.
[28] L. S. Hill: Cryptography in an algebraic alphabet. Amer. Math. Monthly 36(1929) 306-312
[29] L.S. Hill: Concerning certain linear transformation apparatus of cryptography. Amer. Math. Monthly 38 (1931) 135-154
[30] Kiss Elemér: Matematikai kincsek Bolyai János kéziratos hagyatékából, Typotex Kiadó, Budapest, 1999.
[31] D.E. Knuth: The art of computer programming. Vol 2 Seminumarical algorithms.
Addison-Wesley 1969.
[32] S.Landau: Prímes codes and the National Security Agency, Notices Amer. Math.Soc. Jan. 1983. 7-10
[33] D.H. Lehmer: A photo-electric number sieve, Amer. Math. Monthly(1933) 661-667
[34] D.H. Lehmer: The sieve problem for all pupose computer. Math. Tablea other aids of computation (1953) 6-14
[35] D.H. Lehmer: Strong Carmichael numbers. Journal of the Australian Math. Soc.Ser.A 21(l976)508-511
[36] C.Lim-P.Lee: A key recovery attack on discrete log-based schemes using a prime order subgroup. In: Advances in Cryptology, Proc. Crypto ’97, Spriger-Verlag, 1997. pp. 249-265.
[37] J. Massey: Applied digital information theory. ETH Zürich 1985.
[38] S.M. Mátyás: Digital signatures. An overview. Computer Networks 3(1979) 87-94
[39] R.C Merkle, M.E. Hellmann: Hiding information and signatures in trapdoor knapsacks.
IEEE Trans. IT-24 sept. 1978 525-530
[40] J.Morgado: A property of the Euler j-function concacning the integers which are regular modulo n. Portugalia Mathematica 35(1974) 185-191
[41] J.Morgado: Another generalization of Euler’s theorism. Portugalis Mathematica 35(1975) 241-243
[42] A.A. Mullin: A note on the mathematics of Public-key cryptosystems. Computer and Security 3(1984) 45-47
[43] National Security Agency: Public cryptography. Signal August 1981 67-77.
[44] J. L. Nicolas: Treat de prímalité. Expositiones Mathematical 2(1984) 223-234
[45] W. Nöbauer, J. Wiesenbauer: Zahlentheorie, Prugg Verlag, Eisenstadt 1981.
[46] J.M.Pollard: Theorems on factorizations and prímality testing. Proc.Camb.Philos.Soc.76(1974) 521-528
[47] J.M.Pollard: A Monte Carlo method for factorization. BIT 15(1975) 331-334
[48] C. Pomerance: Analysis and comparisions of some integer factoring algorithms. Number Theory and Computers (H.W. Lenstra Jr and R. Tijdeman eds.) Math. Centrum Tracte Number 154. Part I and Number 155 part II. Amsterdam 1983.
[49] J.J. Quisquater, C. Couvreur: Fast dechipherment algorithm for RSA public-key
cryptosystem.
Elekctron. Lett. 18(1982) 905-907.
[50] M.O. Rabin: Digitalized signatures and public key functions as intractable as factorization. MIT Lab. For Computer Sience, Techn. Rep. LCS/TR-212. 1979
[51] M.O. Rabin: Probabilistic algorithm for testing prímality. Journal of Number Thachy 12(1980) 128-138
[52] B.Randell: The Colossue. A History of Computing in the Twentieth Century. Ed.N.Metropolis J. Howlett and Gian Carlo Rota, New York, Academic Press, 1980.
[53] R.L. Rivest, A. Shamir, L. Adleman: A method for obtaining digital signatures and public
key cryptosystems. Comm. ACM 21(1978) 120-126
[54] R.L. Rivest: Remarks on a proposed cryptanalytic attack on the MIT public-key cryptosystem. Cryptologia 2(1978) 62-65
[55] R.L. Rivest: Critical remarke on „Critical remarke on some public-key cryptosystems”. By T. Herlestem. BIT 19(1979) 274-275
[56] H. Rohrbach: Mathematical and mechanical methodes in cryptography, Cryptologia 2(1978) 20-37. angol fordítása a német eredetinek (Matematische und maschinelle methoden bei chiffrieren und deschiffrieren. FIAT Review of German Science, Applied Math. Part I. Wiesbaden 1948. 233-257
[57] C.P. Schnorr: Is the RSA-Scheme Safe? (Abstract) Cryptography. Proc. Burg Feuerstein Ed. T.Beth, Lecture Notes in Computer Science 149(1982) 325-329
[58] M.R. Schroeder: Number theory in science and communication Springer-Verlag, Berlin,
Heidelberg, New York, Tokyo, 1984.
[59] S. Schwarz: The Euler-Fermat theorem for the semigroup of circulant Boolean matrices. Chechoslovak Math. Journal 30(1980) 135-41
[60] A. Shamir: How to share a secret, Comm. of ACM 22(1979) 612-613
[61] A. Shamir: A polinomial time algorithm for breaking Merkle-Hellmann cryptosystems. Proceddings of the 23rd. Annual Symp on the foundations of computer science 145-152
[62] A. Shamir: A polynomial-time algorithm for breaking the basic Merkle-Hellmann
cryptosystem.
IEEE Trans IT-30 sept. 1984. 699-704
[63] D. Shapley: The new unbreakable codes-will they put NSA out of busines? The Washington Post Sunday July 9 1979.
[64] G.J.Simmons, M.J. Morris: Preliminary comments on the MIT public-key cryptosystem. Cryptologia 1 (1977) 406-414
[65] G.J.Simmons: Cryptology, the mathematica of secure communication. Math.Intelligencer 1(1978) 233-246
[66] D. Singmaster: A maximal generalization of Fermat’s theorem. Math. Mag. 39(1966) 103-107
[67] D.R. Smith, J. T. Palmer: Universal fixed messages and the Rivest-Shamir –Adleman cryptosystems. Mathematika 26(1979) 44-52
[68] R.Solovay, V. Strassen: A fast Monte-Carlo test for prímality. SIAM Journal on
Computing 6(1977) 84-85
Erratum 7(1978) p118
[69] N.S.Szabó, R.I. Tanaka: Residue artihmetic and its applications to computer technology. Mc Graw Hill, New York 1967
[70] M.M.Waldrop: NSF Commits to Supercomputers. Science Vol. 228 3 May 1985. 568-571
[71] H.C. Williams-J. Shallit: Factoring integers before computers. In: Proc. Sympos. Appl. Math., Amer. Math. Soc., 1994., pp. 481-531.
[72] H.C. Williams: Factoring on a computer. The Mathematical Intelligencer 6(1984) No.3
29-36
[73] W.W.Wu: Elements of satellite communications.
