DT
D é n e s T a m á s matematikus TD
független szakértő
e-mail: tdenest@freemail.hu
Piérre Fermat
és a nyilvános
kulcsú rejtjelzés
Szinte hónapra
pontosan 100 évvel Girolamo Cardano
születése után, 1601-ben született meg
Piérre Fermat. Bár Fermat, Cardanohoz hasonlóan sokoldalú tudós volt,
aki nemcsak korának, hanem az egész tudománynak (nem csak a matematikának)
jelentős alakja, mégis nevéhez többnyire csupán a "Fermat sejtés"
tapad. Valószínűleg ez a sejtéshez fűződő különös történetnek köszönhető, amely
szerint Fermatról ránk maradt Diophantosz "Aritmetikájának" egy
1621-ben kiadott példánya, amelyben számos megjegyzést irt a könyv különböző
helyeire. E megjegyzések a Diophantosz által felvázolt problémákkal
kapcsolatosak és igen sok értékes anyagot szolgáltatnak a matematikusoknak,
főleg a számelmélet területéről. Az egyik ilyen megjegyzésben, melyet egy lap margójára irt, Fermat arra utal,
hogy az 
egyenletnek
nincsenek 
természetes számokra
zérustól különböző egész megoldásai. A könyv margóján ez olvasható: "Ennek igazán bámulatos bizonyítását
találtam meg, azonban a könyv margója túlságosan keskeny, hogy ide írjam."
Ettől kezdve a
matematikusok és érdeklődő nem matematikusok állandóan igyekeztek a bizonyítást
megtalálni, vagy egy olyan példát keresni, amely megdönti Fermat állítását.
A kételkedők
szerint Fermat nem is bizonyította be ezt a tételt, ezért az 1990-es évek közepéig, amíg a bizonyítást
valóban sikerült megadni, Fermat sejtésnek nevezték. A kételkedők érveit
nagyban alátámasztotta, hogy Fermatnál elég gyakran fordulnak elő téves
matematikai állítások, ilyen például, hogy
"minden 
alakú szám prím,
ha n
természetes szám", ezeket
nevezzük Fermat számoknak.
A Fermat
sejtés bizonyítási kísérleteire lelkesitőleg hatott, hogy 1908-ban
Wolfskehl német matematikus 100
ezer márkát adott át a Göttingai Tudományos Társaságnak, hogy jutalomként
fizesse ki annak, aki a sejtés bizonyítását megtalálja, vagy téves voltát
bebizonyítja. Több mint 300 éves
szunnyadás után a XX. században több részleges eredményt sikerült elérni elég
nagy, de mégis véges n
értékekre, míg Andrew Wiles amerikai matematikus 1993-ban bejelentette a szenzációt, hogy
sikerült a teljes bizonyítást megtalálnia. Nemsokára kiderült, hogy Wiles
bizonyítása hiányos. Ezt azonban
Richard Taylorral közösen sikerült pótolni 1994-ben, így 1995-ben az
Annals of Mathematics 141.
számában a teljes bizonyítás megjelenhetett. Magyar nyelven is tájékozódhat a
kedves Olvasó Rónyai Lajos
dolgozatából (Matematikai Lapok, új
sorozat 2., 3-4. szám).
Így 1995-óta jogosan beszélhetünk sejtés helyett
nagy Fermat tételről. A "nagy" jelző a "kis"
Fermat tételtől való megkülönböztetésre szolgál, amelyről a következőkben lesz
szó és amelynek "kis" jelzője ellenére alapvető hatása van napjaink
információ titkosítására. Fermat eredetileg a következő tételt mondta ki:
Kis Fermat tétel:
Ha p prímszám és
a nem osztható p-vel, akkor teljesül az (1) kongruencia[1]
(1) 
Fermat
bizonyítása azonban ebben az esetben sem maradt fenn. Az első bizonyítás majd
100 évig váratott magára és Leonhard
Eulertől (1707-1783) a XVIII. század
matematikus óriásától származik. Euler egyben a tétel általánosítását is
bebizonyította, így ma Euler-Fermat
tételnek nevezzük, amely így szól:
Euler-Fermat tétel:
Ha 
egész szám és (a,m)=1,
azaz a és m relatív prímek[2],
akkor
(2) 
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.
Például: 
Általában igaz
a tétel, hogy ha m=p prímszám, akkor
(3) 
Ebből az is
könnyen belátható, hogy ha p
és q különböző prímek,
akkor
(4) 
A
prímszámoknak és a számok osztóinak titokzatos szerepet tulajdonítottak az
ókori számmisztikában olyannyira, hogy Püthagorasz és követői, akik e
számmisztika fő hirdetői voltak (i.e. VI-V. század), úgy tartották, hogy "A dolgok természete, lényege: a
szám." De nem csak hirdették,
hanem valóban a természeti és társadalmi jelenségeket mind-mind a számok
csodálatos tulajdonságai "testesítették meg". A pütagoreusok ugyanis
nem a számokat személyesítették meg, hanem a személyes (emberi) tulajdonságokat
"számosították meg".
Tökéletesnek tartottak egy számot, ha az
megegyezett osztói összegével. Tökéletes számok[3]
például a 6=1+2+3 és a 28=1+2+4+7+14
. A pütagoreusok csak néhány tökéletes számot ismertek, így a 496-ról és a 8128-ról is tudták, hogy tökéletes számok. A matematikusok az ókor
óta nem tudják, hogy van-e végtelen sok tökéletes szám.
Az ötödik
tökéletes számot, a 33.550.336-ot a
XV. században találták meg, míg a XVI. század adta a hatodik és hetedik
tökéletes számot, a 
és a 
. Látható, hogy a tökéletes számok között, ahogy haladunk
"előre" egyre nagyobb távolságok vannak, így nem meglepő, hogy egyre
nehezebb újabb tökéletes számokat találni. A nyolcadik tökéletes szám
megtalálására a XVIII. századig kellett várni, amikor Leonhard Euler kimutatta,
hogy a 
is tökéletes szám. A
számítógépek megjelenéséig még négy tökéletes számot sikerült megtalálni a XIX.
században kézi számolással, ezek a 
, 
, 
, 
tökéletes számok[4].
Modern
számítógépekkel a XX. században már egyre nagyobb tökéletes számokat sikerült
előállítani, például ma már tudjuk, hogy
, 
, 
, 
, 
, 
, 
, 
is tökéletes számok[5].
De a
pütagoreusok szerint vannak barátságos
számok is. Két szám akkor áll barátságban egymással, ha az egyik osztóinak
összege pontosan a másik számot adja és fordítva. Barátságos számok például
a 220
és 284, ugyanis
220 osztói: 1+2+4+5+10+11+20+22+44+55+110=284
284
osztói: 1+2+4+71+142=220
A barátságos
számok felfedezésének története is sok évszázados történet. Már a régiek
ismerték az 1184 és 1210 barátságos
számpárt, majd Piérre Fermat mutatta ki ugyanezt a 17296 és 18416 számpárról. René Descartes (1596-1650), aki szintén
a matematika egyik óriása volt[6]
fedezte fel a 9363584 és 9437056 barátságos számpárt, majd Euler a XVIII.
században még 61 barátságos számpárt
határozott meg.
A számmisztika
már régen homályba merült, de a harmóniába, a harmonikus szépségbe vetett hit
napjainkig fennmaradt. De fennmaradt az a számtalan örökérvényű gondolat,
tudományos tétel is, amely e misztikus gondolkodás talaján fogant és mégis a
természet mély összefüggéseit írja le. Mint a bemutatott példák is mutatják,
néha olyan mély titkokat sikerült a pütagoreusoknak
"számszerűsíteni", hogy még a mai napig sem tudta az emberiség a
megfejtést megtalálni. Napjaink
kriptográfiája[7] nagy részben
ezekre az évezredes meg nem fejtett titkokra épül.
Igen érdekes
magyar vonatkozásokra derül fény a prímszámokkal és a kis Fermat tétellel
kapcsolatban, Kiss Elemér marosvásárhelyi matematikus és Bolyai kutató
tollából. 1999-ben megjelent könyvében (lásd [8])
egészen új képet kapunk Bolyai Jánosról, eddig ismeretlen dokumentumokra
alapozva. Kiss Elemér könyvéből kiderül, hogy Bolyai János leginkább a
prímszámokkal szeretett foglalkozni, erről így ír Ő maga:
"Az egész számtan sőt az egész tan mezején alig
van szebb és érdekesebb ... s a legnagyobb nyiászok (matematikusok) figyelme és eleje
óta elfoglalt tárgy, mint a főszámok (prímszámok) oly mély homályban rejlő titka."[8]
Bolyai is,
mint a Pütagoreusok óta annyi matematikus, kereste az úgynevezett prímszám
képletet, vagyis olyan formulát, amely közvetlen összefüggést ad meg az n-edik
prímszám értéke és az n
index között. 1855 tájékán még úgy gondolta, hogy sikerült megtalálnia a
titok megfejtését:
"Azt megmutatni, hogy bármely 
alakú szám prím
mihelyt p prím, ugyanakkor amikor a
-gyel bajlódám, magam is megkísértettem, mert amint irataim
is megmutatják én is abban a sejtelemben voltam, hogy 
mindig prím, ha p
prím. Ez egy történeti fontosságú felfedezése volna a legelső olyan
függvénynek, mely mindig prímet ad. Azonban ez sem valósul meg, mert
például 
..."[9]
Apja (Bolyai
Farkas) ösztönzésére megkísérelte a kis Fermat tétel fordítottját
bebizonyítani, mivel ha ez sikerül, akkor megkapta volna a vágyott
prímszámképletet. A kis Fermat tétel fordítottja azt mondja ki, hogy ha 
osztható p-vel, akkor p biztosan prímszám. Néhány kísérlet után azonban rádöbbent, hogy a bizonyítás lehetetlen,
mivel a kis Fermat tétel fordítottja általában nem érvényes. Ellenpéldákat
keresve, felfedezte a legkisebb úgynevezett pszeudoprím számot,
a 341-et.
Vannak ugyanis
olyan n összetett számok,
amelyek minden n-hez relatív prím a-ra kielégítik a kis Fermat tételt,
vagyis
(5) 
ahol n összetett szám és (a,n)=1
Az ilyen n számokat nevezzük 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.
Az olyan összetett
n számokat, amelyekre az (5)
összefüggés a=2 esetén teljesül,
2-re vonatkozó pszeudoprímeknek, vagy álprímeknek nevezzük.
Az álprímek
történetében Bolyai János fontos szerepet játszott, amely Kiss Elemér kutatásai
nélkül mindmáig ismeretlen maradt volna.
A modern
kriptográfia az 1970-es években újra
"felfedezte" a számelméleti eszközök felhasználásának előnyeit. Az
időpont talán nem véletlen, hiszen ekkorra tehető a globális információs
rendszerek, a globális kommunikáció, az "információ robbanás"
korszakának kezdete, amely óriási kihívást jelentett az információk biztonságos
tárolásával és továbbításával foglalkozóknak.
Íme a
klasszikus titkosítás vázlata:
Titkos
kulcs
Nyílt üzenet[10]
Rejtjeles üzenet
Titkosító eljárás
Küldő Fogadó
A Fogadó fél
(ha nem illetéktelen) rendelkezett ugyanazzal a titkos kulccsal és
természetesen a titkosító eljárásnak megfelelő megoldó eljárással, így a
rejtjeles üzenet megoldásának (elolvasásának) vázlata:
Titkos
kulcs
Rejtjeles üzenet
Nyílt üzenet
Megoldó eljárás
A klasszikus
titkosítás tehát megfelelő (szigorú) titoktartást és pontos szervezést
igényelt, hiszen a "titkos kulcs" illetéktelen kézbe kerülése,
mindkét irányban végzetes lehetett. Az illetéktelen
küldő képessé vált ugyanis hamis üzenetek küldésére, amely a fogadó oldalán
felismerhetetlen volt, míg az illetéktelenül
a titkos kulcs birtokába jutott fogadó, képes volt a másnak címzett
üzenetet elolvasni. Hétköznapi hasonlattal élve ez olyan, mintha az egy zárral nyitható ajtó kulcsát rosszul dugjuk
el és azt a betörő megtalálja.
Ezen problémák
megakadályozása érdekében a titkos kulcsot rendszeresen változtatták, ami
viszont igen pontos (és titkos!) szervezést igényelt, hiszen erről a
változásról a küldő és fogadó fél "egyszerre" kellett, hogy
értesüljön.
W.S.Jevons
már 1873-ban megjelent könyvében
felvetette (lásd [07])
azt az elvet, hogy vannak bizonyos matematikai műveletek, amelyek elvégzése
nagyon egyszerű (ilyen például az összeadás, vagy a szorzás), de az eredményből
a kiindulási komponensek visszaállítása igen nehéz, sokszor reménytelen.
Illusztrációként bemutatja az azóta róla elnevezett 10 jegyű számot, a Jevons számot (8.616.460.799), amely két
prímszám szorzata, ám a prímtényezők meghatározását (a prímfaktorizációt)
akkor reménytelennek látta[11].
Hogy Jevons ezzel a felvetésével mennyire megelőzte korát, azt mi sem
bizonyítja jobban, mint hogy szinte pontosan
100 év szunnyadás után, az 1970-es évek elején merült fel ismét e
gondolat. Erdős Pál és Surányi János [05]-ben
így fogalmazza meg a problémát:
"Létezhet-e azonban olyan rejtjelzés,
amelyiknél nem lehet kitalálni, hogy hogyan kell azt visszacsinálni ? Első
pillanatban ez valószínűtlennek látszik, mégis az Euler-Fermat tétel, továbbá a
számítógépek rendkívüli teljesítőképessége egy oldalról, a teljesítőképességük
határa a másik oldalról lehetőséget ad erre."
Az világos, hogy
ahhoz, hogy az Euler-Fermat tétel
alkalmazható legyen, az üzenetnek numerikusnak kell lennie, vagyis a betűkből
és egyéb írásjelekből álló szövegeket számokká kell alakítani. Ez azonban
könnyen megtehető a klasszikus helyettesítéses titkositási eljárással, amikor
mindenegyes írásjelnek egy-egy számot feleltetünk meg[12].
Napjaink digitális világában már nem csupán a szöveges üzeneteket, hanem a kép
és hang üzeneteket is számok sorozatává alakítják, így tárolják és továbbítják
a kommunikációs vonalakon, aminek sok más mellett pontosan az az előnye, hogy
jóval biztonságosabb adatvédelem érhető el, mint az úgynevezett analóg
jeleknél.
Ez azt
jelenti, hogy nincs akadálya annak, hogy a továbbiakban üzeneten mindig
számokat értsünk. Így már kézenfekvőbbnek tűnik, hogy a számelmélet
eredményeit, ezen belül az Euler-Fermat
tételt is felhasználjuk a titkosításra. Legyen eljárásunk a következő:
a. Válasszunk
két különböző p, q prímszámot, amelyek
szorzata
(6)
pq=N
b. Ha a
továbbítandó üzenet (mint szám) nagyobb mint
N, akkor bontsuk fel N-nél
kisebb részekre. Egy ilyen rész legyen h. Tehát fennáll, hogy
(7) 
c. Legyen
továbbá r és m két pozitív egész szám, amelyekre
(8) 
ami pontosan
azt jelenti, hogy
(9) 
d. Ekkor
az R(h) rejtjelzés kulcsa legyen 
legkisebb nemnegativ
maradéka, amely az N-nel való osztáskor keletkezik.
e. Ha az így rejtjelzett
üzenet h’,
akkor a megoldó kulcs M(h’) a 
legkisebb nemnegativ
maradéka, amely az N-nel való osztáskor keletkezik.
f. Be kell tehát látnunk,
hogy e két kulcs kielégíti az alábbi összefüggést:
(10) R(M(h'))=M(R(h))=h
Nos, a fentiek szerint
igazak az alábbi összefüggések:
(11) 
Ha (h,N)=1, akkor az
Euler-Fermat tétel szerint:
(12) 
Tehát
(13) 
és (7)
szerint a (13) jobb oldala éppen 
legkisebb nemnegativ
maradéka, azaz ebben az esetben teljesül a
(10) összefüggés.
Vizsgáljuk
most a még lehetséges (h,N)=p
esetet. Ekkor
(14) 
ekkor a kis
Fermat tétel alapján
(15) 
Szorozzuk be
mindkét oldalt 
-val:
(16) 
Ekkor (14)
folytán most is teljesül:
(17) 
Megjegyzések:
- Nyilvánvaló,
hogy a (h,N)=q eset ugyanígy
vezethető le.
- Könnyen
belátható, hogy a kongruencia akkor is fennáll, ha h osztható
N-nel, bár ez a gyakorlatban
soha nem fordul elő.
Beláttuk
tehát, hogy a fenti eljárás kielégíti a
(10) összefüggést, amellyel egy
egészen új elven alapuló titkosításhoz jutottunk. Ezt vették észre az 1970-es évek közepén R.L.Rivest, A.Shamir és L.Adleman az MIT
(Massachusetts Institute of Technology)
munkatársai, majd a részletes kidolgozás után, 1978-ban hozták hozták
nyilvánosságra (lásd [13])
és szabadalmaztatták (lásd [14]). Nevük kezdőbetűi
alapján RSA algoritmusként lett
közismert az egész világon és vált az egyik olyan szoftver és hardver termékké,
amelyből máig a legtöbb példányt használják fel.
Jevons
felvetése tehát 100 évvel később
beteljesedett, Fermat 250 évvel
azelőtti eredményére alapozva. Az RSA
algoritmus valóban a titkosítás egészen új korszakát nyitotta meg, amelyet "nyilvános kulcsú rejtjelzésnek"
hívunk. Miért ?
Mert a cikkünk
elején bemutatott klasszikus titkositási eljárásokkal szemben, itt két kulccsal
dolgozunk, amelyek közül az egyik nyilvánosságra hozható (ez a nyilvános
kulcsnak nevezett N, r pár) anélkül, hogy a rejtjelzés biztonsága
sérülne. Miért hozható
nyilvánosságra N, r ? A válasz érvelésére felhívom a kedves Olvasó
figyelmét, mivel ez egyúttal az RSA algoritmusának lényegét is megadja !
- Jól
választva két elég nagy p,q
prímszámot (ezek ma már többszáz jegyű prímszámok) kiszámíthatjuk N-et és 
-et.
- Ezután
alkalmasan választott r-rel az euklideszi algoritmust
végrehajtva, ellenőrizzük, hogy 
teljesül-e.
- Végül r-hez
meghatározzuk azt az m
számot, amelyre (8) teljesül, amihez szintén euklideszi
algoritmust használunk.
Mindezen
műveletek közül a nagy prímszámok megtalálása a legkritikusabb, de ma már elég
gyors eljárásokkal rendelkezünk annak eldöntésére, hogy egy szám prím-e vagy
sem.
Ha tehát N-et
és r-et,
mint nyilvános kulcsot közzé tesszük, akárcsak a telefonkönyvben a
telefonszámokat és p,q,m-et tartjuk csupán titokban (ez a titkos kulcs), akkor ahhoz,
hogy valaki illetéktelenül hozzájusson titkunkhoz, N-et kell
törzstényezőkre bontania. Erről pedig érdemes felidézni Martin Gardner, a
Scientific American világhírű rovatvezetőjének 1977-es gondolatait, amely éppen
R.L.Rivest-re hivatkozik:
"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 megfejté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
titkositási eljárás megfejthetetlen."
Érdekes a
gondolatok hasonlósága miatt is felidézni Jevons több mint száz évvel korábbi
nézetét, amelyet a Jevons számmal kapcsolatban írt le [07]-ben:
"Meg tudja mondani az Olvasó, hogy melyik két
szám összeszorzásából adódik a
8.616.460.799 szám ? Úgy gondolom reménytelen, hogy akárki (magamat is beleértve), valaha
megtudja."
Természetesen
akkor még nem voltak másodpercenként millió műveletet végző számítógépek, így a
megoldás csak kézi számolással volt elképzelhető (illetve elképzelhetetlen). A
technika nagyot fejlődött azóta. Ma már számítógéppel egy ekkora szám
faktorizációja nem okoz problémát. Ezért használnak az RSA algoritmusnál
többszáz jegyű számokat, amelyek faktorizációja a mai számítástechnika mellett
ugyanolyan reménytelennek tűnik, mint 1870-ben a Jevons számé.
Ha jól
megfigyelte a kedves Olvasó, a fenti érvelésekben, melyek a rejtjel
megfejthetetlenségéről szóltak, az elméleti érvek mellett igen nagy szerepet kapott a technika korlátaiba vetett remény, amely
nem képes bizonyos határokat meghaladni !
Ezt a reményt
(vagy reménytelenséget) azonban beárnyékolja, hogy például 1996-ban S.W. Golomb amerikai matematikus olyan
egyszerű eljárást adott, amely kézi számolással 56 lépésben megadja a Jevons szám szorzattábontását, azaz kimutatta,
hogy 8.616.460.799 = 96.079 •
89.681 (lásd [06]).
Végül a
prímszámokra vonatkozó néhány érdekes tételt mutatok be (bizonyítás nélkül),
amelyekre építve megadható a
Golomb-féle eljárás jelen szerző által javított változata, ami nem
csupán a Jevons szám faktorizálására használható.
1.Tétel:
Minden 3-nál nagyobb p prímszám 6k+1 vagy
6k-1 alakú, ahol k = 1,2,3,... természetes szám.
E tétel
alapján a természetes számokat
az alábbi módon rendezhetjük hat oszlopba (lásd 1.tábla), ahol az összes prímszám az 1.
és az 5. oszlopban helyezkedik
el. Méghozzá az 1.oszlopban a 6k+1, míg az 5.oszlopban a 6k-1
alakúak.
1.Tábla
6k+1
6k-1
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17
18
19 20 21 22 23 24
25 26 27 28 29 30
31 32 33 34
35 36
37 38 39 40 41 42
43 44 45 46 47 48
49 50 51 52 53 54
55 56 57 58 59 60
61 62 63 64 65 66
67 68 69 70 71 72
73
74 75 76
77 78
79 80 81 82 83 84
85 86 87 88 89 90
91 92 93 94 95
96
97 98 99 100
101 102
. . . .
A fenti
1.tételből érdekes következményként adódik, hogy ha a prímszámokat hatos számrendszerben írjuk fel, akkor minden 6k+1
alakú prímszám 1-re, míg minden
6k-1 alakú prímszám 5-re
végződik. (lásd a 2.táblát)
2. Tábla
6k+1 hatos sz.r. 6k-1
hatos sz.r.
7 11 5 5
13 21 11 15
19 31 17 25
31 51
23 35
37 101 29
45
43 111 41 105
61 141 71 155
. . .
Az 1.tétel
alapján tehát a 3-nál nagyobb prímszámok szempontjából elegendő csupán
a 
alakú természetes
számokat vizsgálni. Az alábbi
2.tétel szükséges és elegendő
feltételt ad a 
alakú összetett
számokra, ez a komplementer prímszita.
2.Tétel (Komplementer
prímszita):
Legyenek N, k,
u, v természetes számok,
valamint u,v 
1.
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
A 2.tétel következményeként megkapjuk N kéttényezős felbontását is, azaz
(18) N= 6k+1
N=(6u+1)(6v+1), vagy N= (6u-1)(6v-1)
(19) N=6k-1
N=(6u+1)(6v-1), vagy N=(6u-1)(6v+1)
Fontos
megjegyezni, hogy mivel a komplementer prímszita egyáltalán nem feltételezi a 
-nél kisebb prímszámok ismeretét, így a (18), (19)
felbontás megtalálására jól alkalmazható osztott (párhuzamos)
algoritmus.
Most térjünk
vissza a Jevons számhoz. S.W. Golomb [06]
cikkében a Jevons szám faktorizációja kapcsán bemutat egy általános eljárást a
két prímtényezős szorzatok prímtényezőinek meghatározására. Ha J jelöli a szorzatot, akkor a módszer
alapötlete így írható
le:
(20) 
ahol a és b
természetes számok, p és q
prímszámok.
Az (20) összefüggéshez igen egyszerűen
számolható, hatékony algoritmust mutat be az
a, b számok meghatározására. Az algoritmus
lényeges lépései:
- Képezzük
az 
kezdőértéket.
- Legyen 
, ahol k=1,2,3,...
- Képezzük
az 
sorozatot, amíg
teljes négyzetet kapunk, azaz
(21) 
Ekkor
tehát 
természetes számok
és így teljesül, hogy
(22) 
Az eljáráshoz
mindössze egy memóriára van szükség, amelyben az aktuális 
értéket tároljuk.
Így akár egy zsebszámológép segítségével elvégezhetők a számítások. Igen
meggyőző, hogy a Jevons által 1870-ben megoldhatatlannak tartott feladat,
a J=8.616.460.799 szám faktorizációja, S.W. Golomb
módszerével k=56 lépésben célhoz vezet
és megadja az 
=92.880, 
=3199 megoldást[13].
Más
megközelítésben láttuk, hogy a 2.tétel (komplementer prímszita) szintén megadja
bármely 
alakú összetett szám
két tényezős prímfelbontását[14],
amelynek alakja
(23) 
(u, v= 1,2,3, ...)
Ha tehát
feltételezzük, hogy J-nek két prímtényezője van (lásd
(20)), akkor fennáll:
(24) 
A két
prímtényezőre vonatkozó feltétel, valamint a
2.tétel miatt (24)-ből következik, hogy
(25) ha J=6K+1, akkor 
ha J=6K-1, akkor 
A két egyenlet
összeadásával adódik:
(26) 
(26)-ből
következik, hogy 
, vagy 
mindig osztható 3-mal. Ha tehát az 
kezdőértéket úgy
választjuk, hogy
(27) 
azaz 
osztható 3-mal, akkor a Golomb algoritmus szerint:
(28) 
amely (27)
és (28) alapján csak akkor teljesülhet, ha k is osztható
3-mal, vagy 
. Így a rekurziós lépések számát harmadára csökkenthetjük,
hiszen a k=1,2,3, ... lépések
helyett csak a k=3,6,9, ..., vagy
k=1,4,7,..., illetve k=2,5,8,...
esetek kiszámítására van szükség. A
Jevons szám esetén tehát:
(29) 
(h=1)
azaz 56
lépés helyett, 19 lépésben előáll a
megoldás.
Ez az eljárás
(és több másik, lásd pl. [01] ) alapvetően
megingatja az RSA módszer elméleti biztonságát. A ma működő információs és
kommunikációs rendszerek (internet, hálózati szoftverek, távközlési hálózatok,
stb.) több mint 80%-ában RSA alapú információ-védelem van. Hogy mennyire nem
alaptalan az aggodalom, azt alátámasztják az utóbbi 1-2 év jelentős (és
sikeres) hacker támadásai, amelyeknek egy része a kulcsok megfejtésén alapult
(lásd [02]).
Szeretném
végül felhívni a figyelmet arra a matematikus és kriptográfus
gondolkodásmódbeli különbségre, hogy a matematikailag kiszámítható kulcstér
mérete, azaz, hogy egy adott típusú kulcsból összesen hány különböző létezik,
csak akkor lenne meggyőző érvként felhasználható, ha a rejtjelfejtési támadások
az úgynevezett "teljes
kipróbálás" módszerét használnák, amelyre szinte sosem kerül sor.
Ekkor lenne érvényes az egyébként rohamosan fejlődő számítástechnikai
kapacitások korlátait jellemző több évezredes és évmilliós érv, amely a
megfejthetetlenség jellemzésére szolgál.
Az érvelés
azonban azt is figyelmen kívül hagyja, hogy a hagyományos számítási kapacitások
egy-számítógépes modellekre épülnek és csak ezek sebesség és tároló kapacitását
veszik figyelembe, míg a már ma is létező
óriási számítógép hálózatok, több száz, ezer, vagy akár százezer gép
kapacitásait integrálják. Ha tehát, mint a jelen szerző által is bemutatott
osztott (párhuzamos) algoritmussal is végezhető támadást alkalmazunk, akkor a
technikai kapacitásokra alapuló érvelés egyre kevésbé tartható. Ilyen
internetes projectek már működnek, például a SETI program keretében, amely a
földönkivüli élet kutatásával foglalkozik és a világűrből érkező, óriás
antennákkal felfogott, óriási mennyiségű adat, több százezer internetre
kapcsolt számítógépen történő osztott feldolgozásával működik. A globális
hálózatok tehát egészen új technikai dimenziókat vezetnek be, amelyek
szükségessé teszik azon módszerek újragondolását, amelyeknél a technikai
korlátok is szerepet kapnak.
Irodalomjegyzék
[01] Dan Boneh: Twenty
years of attack on the RSA cryptosystem.
Notices
of the AMS, February 1999, 203-213.
[02] Dénes Tamás: REJTJELFEJTÉS
Trükkök, módszerek, megoldások
Magyar
Távközlés, XI.évf. 4.szám, 2000. április
[03] T. Dénes:
Complemetary Prime-Sive
P.U.M.A. Vol.12 (2002) No.4. pp. 355-363
[04] Dénes Tamás: Kódtörő ABC
Bagolyvár Könyvkiadó, Budapest, 2002.
[05] Erdős Pál, Surányi János: Válogatott fejezetek a számelméletből
POLYGON, Szeged, 1996.
[06] S.W.Golomb:
On factoring Jevons’ number
CRYPTOLOGIA, (vol XX. no.3.) 1996.
[07] W.S. Jevons: The Principles of Science:
A Treatise on Logic and Scientific Method
Macmillan & Co., London, 1873. Second edition 1877.
[08] Kiss Elemér: Matematikai kincsek Bolyai János kéziratos hagyatékából
Typotex Ltd., Budapest, 1999.
[09] Sain Márton: Nincs királyi út!
(Matematikatörténet)
GONDOLAT, Budapest, 1986.
[10] Bruce Schechter: Agyam nyitva áll! (Erdős
Pál matematikai utazásai)
Vince Kiadó, Park Kiadó, 1999.
[11] Szalay Mihály: Számelmélet
Tankönyvkiadó, Budapest, 1991.
[12] W.Diffie, M.E.Hellman: New directions in cryptography
IEEE Trans. 1976. IT-22.
[13] R.L.Rivest, A.Shamir, L.Adleman: A method for obtaining digital signatures
and public key cryptosystems
Commun. ACM, 1978. 21/2.
[14] R.L.Rivest:
RSA chips (past/present/future)
presented at
Eurocrypt 84, Paris, France, 1984.
[15] Jack Davies: Piérre de Fermat
(1601-1665) Mathematician and
Jurist
Thesis for the
Degree of Master of Philosophy
Faculty of Arts, University of Liverpool,
1996.