Prímszámháború

"Kellene egy csapat" - írta egy fellelkesült rendszergazda a múlt héten egy másiknak, "mert buli van". A buli jónak látszott, a kolléga egy kicsit adta a hülyét, egy kicsit kérette magát, egy kicsit nagyon fikázott, mert õ már csak ilyen, de közben persze ezzel foglalkozott, majd néhány óra leforgása után az eddigi néhány tízezer számítógép mellé jó tucatnyi újabb, magyar felségjelzésû gép is beszállt az RSA RC5-32/12/7 jelû feladványának megoldási kísérletébe. Az effajta versengésnek már hagyománya van: az Interneten összegzõdõ nyers számítóerõ küzd meg az egyre korszerûbb titkosító-algoritmusokkal.

A feladvány tényleg ellenállhatatlan, egyrészt mert kriptográfia, másrészt mert tényleg sokáig tart megoldani. A kriptográfia - fõleg a nyilvános kulcsú titkosítás - roppant divatos manapság, mivel az autoritások attól tartanak, hogy a globális kommunikáció hajnalán elvesztik a kontroll lehetõségét a polgár felett, az emancipálódott polgár pedig az autonómiáját félti az elvben bevezethetõ abszolút kontrolltól (lásd: Cypherpunk, MaNcs, 1995. szeptember 21.; Big Brother Négyárbocosa, MaNcs, 1996. február 1.). A személyesen soha nem találkozott netterek összefogása amúgy is minden veterán rendszergazda vérében van, az Interneten nagyon egymásra vannak utalva az egyes helyi hálózatokat üzemeltetõk, elõbb az összes ismeretlen kolléga a világ végérõl, aztán család: ez a legtöbb guru prioritása. Ráadásul tízezer dollárt is lehet nyerni, amit majd jól odaad a gyõztes a Szabad Szoftver Alapítványnak (lásd: Szoftverfelszabadítás, MaNcs, 1996. március 21.) vagy valami hasonló társaságnak, a család meg a lemondásért cserébe kap egy fagyit, persze ha nem lesz elfelejtve. El lesz.

A világtörténelemben az elmúlt húsz évet leszámítva a titkosítás mûfaját a titkos kulcsú, avagy

szimmetrikus kriptográfia

dominálta. Diplomáciai védettséget élvezõ futárok szaladgáltak a világban, lezárt táskájukban üzenetekkel, kulcsokkal, amelyek egészen addig biztonságban is voltak, amíg valakiknek nem fûzõdött erõs érdeke a kulcs megszerzéséhez. A módszernek ez a gyenge pontja, erõsen hinni kell benne, hogy a kulcs nem jutott illetéktelen kezekbe. Gyakorlati problémát okoz, hogy ha sokan akarnak kommunikálni, és páronként más-más kulcsot használnak, a kommunikáció során rengeteg kulcsra van szükség. Például a narancs-l levelezõlistán részt vevõ közel 200 ember esetén összesen 19 900 kulcsra lenne szükség ahhoz, hogy biztonságosnak hihessék az egymás közötti kommunikációt. A másik probléma az, hogy titkosított üzenet küldésére addig nincs mód, amíg a felek meg nem egyeztek a titkosítás módszerében. Erre az USA kormányzata úgy próbált megoldást találni, hogy az NSA (Nemzetbiztonsági Hivatal) készítette és központilag osztotta ki a kommunikációhoz szükséges kulcsokat. Aztán a Ronald W. Pelton NSA-ügynök nevével fémjelzett kémkedési botrány során kiderült, hogy Pelton semmilyen titkos információt nem szolgáltatott ki - csupán kulcsokat.

A titkos kulcsú kriptográfiát minden nehézkessége ellenére sem szabad lebecsülni. Ilyen módszer a DES (Data Encryption Standard), amelyet az USA kormányzata 1977-ben, az ANSI 1981-ben fogadott el szabványnak. A DES ugyan egy 56 bites kulcsot használó erõs algoritmus, de egymillió dollárból építhetõ számítógép, amely néhány óra leforgása alatt az összes DES-kulcsot kipróbálja. A Triple-DES a módszer egyszerû matematikai feljavítása, amely a biztonságot a kétszeresére növeli. Az RC2, RC4 és RC5 kódok Ronald Rivest nevéhez fûzõdnek. A kulcs hossza 1 és 1024 bit között változhat, de 48 bitnél rövidebb kulccsal egyszerû feltörni. Az RC2 módszerében hasonlít a DES-hez, az RC4 némileg különbözõ. Az RC4 algoritmusát 1994 szeptemberében valaki névtelenül közzétette az Interneten, a szakértõk helybõl dobtak egy hátast, amikor meglátták az algoritmus egyszerûségét. Az IDEA James L. Massey és Xueija Lai nevéhez fûzõdik, 1990-ben publikálták. A kulcs 128 bites, ami megvéd attól, hogy valaki az algoritmus ismeretében brute-force támadással kísérletezzen. Maga az algoritmus eddig erõsnek bizonyult.

Az érdemi áttörést végül is a nyilvános kulcsú, másnéven az

aszimmetrikus kriptográfia

hozta meg. A nyilvános kulcsú kriptográfia lényege, hogy a kommunikációban minden résztvevõ matematikai módszerekkel két különbözõ kulcsot készít magának. Az egyik a nyilvános kulcsa, amit bárki tudhat, a másik a titkos kulcsa, amit titokban kell tartania. A módszer lényege az, hogy ha kódolt üzenetet akarok küldeni - akár egy ismeretlen - címzettnek, akkor a titkosításhoz a címzett nyilvános kulcsát kell használni. A címzett a levél kézhezvétele után fogja a saját titkos kulcsát, amellyel visszafejti az üzenetet. Ezen az elven mûködik az Interneten népszerû PGP e-mail-titkosítóprogram (lásd: Csõre töltött prímszámok, MaNcs, 1996. február 22.) is.

A nyilvános kulcsú kriptográfia története 1974-ben kezdõdött. Ralph Merkle a kaliforniai Berkeley egyetem hallgatójaként elhatározta, hogy megoldja egy titkosított kommunikáció két résztvevõje között a kulcscsere problémáját. Dolgozatának a Biztonságos kommunikáció nem biztonságos csatornán címet adta. Professzora egyszerûen nem értette meg Merkle feladatválasztásának lényegét, cikkét a Communications of the ACM címû vezetõ számítástudományi szaklap is visszadobta elsõ körben. Az egyik recenzens szerint ötlete kriptográfiai nonszensz, hibás tudomány, hiszen mindenki tudja, hogy a kriptográfiai kulcsokat titokban kell tartani. Végül is a CACM 1978. áprilisban, mikor a nyilvános kulcsú kriptográfia már hétköznapi fogalommá vált, publikálta a cikket. Idõközben (1975 végén) ugyanis Whitfield Diffie és Martin Hellman kidolgozta a nyilvános kulcsú kriptográfiát. Mûködõképes, gyakorlatban alkalmazható modellt még nem produkáltak, csak leírták, hogy milyen módszer lenne alkalmas a feladat megoldására, ha ilyen nyilvános kulcsú módszer már létezne. 1976 tavaszán három fiatal MIT-professzor: Ronald Rivest, Adi Shamir és Len Adleman nekigyürkõzött a feladatnak. Különös munkamegosztásuk volt: Rivest különféle ötletekkel jött elõ, Adleman (aki késõbb DNS-számítógépet is konstruált, lásd Génzseni, MaNcs, 1995. november 16.) lelõtte azokat, míg Shamir hol kódokat csinált, hol pedig mások kódjait törte fel.

Egy évre rá Rivest Donald E. Knuth megjegyzését - miszerint amilyen egyszerû

két prímszámot összeszorozni,

ugyanolyan nehézségekbe ütközik a faktorizáció, azaz a szorzat alapján megállapítani, hogy mely számokat is szoroztuk össze - felhasználva vázolta egy algoritmus alapjait. Az új módszer kidolgozóinak iniciáléiból az RSA nevet kapta. 1977 augusztusában a nyilvános kulcsú kriptográfia fogalma bevonult a köztudatba: a három feltaláló a Scientific American hasábjain 100 dollárt ajánlott annak, aki elõször faktorizálja a publikált 129 jegyû decimális számot, és megfejti a kódolt üzenetet. Ez igen kisstílû ajánlat volt, lévén az 1977-es év technikai színvonalán semmi esélye nem volt, hogy a felfedezõk életében bárki is megfejtse a kódot. 1994-ben Arjen Lenstra a Bellcore-tól és Derek Atkins az MIT-rõl elhatározta, hogy összefognak a megfejtés érdekében. Tizenhét év alatt történt ez-az mind a számítástechnikában, mind a faktorizáció elméletében. Áprilisra több mint 600 jelentkezõ gyûlt össze legalább két tucat országból, és 1600 munkaállomás, mainframe és szuperszámítógép segítségével nyolc hónap alatt faktorizálták a feladatban szereplõ számot.

Rivest, Shamir és Adleman sem tétlenkedett közben: 1982-ben Jim Bidzosszal összefogva megalapították az RSA Data Security nevû céget (http://www.rsa.com), amely 1986-ban termék, vásárlók és bevétel híján majdnem tönkrement. Tíz évvel késõbb 16 millió dolláros forgalmat produkáltak. Jelenleg jó néhány titkosítással kapcsolatos szoftvert forgalmaznak, többek között Rivest eddig elkészült algoritmusait: az RC2-t és az RC4-t, valamint a legfrissebb RC5-t. Rivest márkavédjegye az RC1-RC9 algoritmus, noha még nincs is mind készen, és RC2 van a Netscape webböngészõben is.

A cég idén január végén

pénzjutalmat tûzött ki

egy DES-kódolt, valamint 12 különbözõ kulcshosszúságú RC5-kódolt szöveg visszafejtésére, demonstrálandó az RC5 felsõbbrendûségét a DES felett. A 40 bites RC5-kódolású üzenet megfejtéséért 1000, a 48 bitesért 5000, a hosszabbakért 10 000 dollárt ajánlottak fel. A 40 bites RC5 üzenet megfejtése 3 óra, a 48 bitesé 313 nap alatt készült el az Interneten, a DES kód 140 nap után, idén június közepén adta meg magát egy svéd csapatnak (http://www.des.sollentuna.se).

Jelenleg az 56 bites kulcsú RC5-kódolt üzenet megfejtése folyik, három nagyobb társaság versenyzik a dicsõségért és a pénzért. Az Infinite Monkeys (http://www. rc5.cs.wisc.edu), a Bovine (http://rc5.distributed.net) és a Cyberian (http://www.rc5.cyberian.org). A csapatok a 72,057,594,037,927,936 számú lehetséges kulcsból bõszen keresik az egyetlen jót, amellyel a kód visszafejthetõ. A módszer a nyers számítóerõre (brute-force) épül, a három társaság szervere a velük együttmûködõ csapatok minden egyes résztvevõjének elküld egy adott mennyiségû kulcsot, aminek kipróbálására véges idõ áll rendelkezésre. Amit a résztvevõ gépe kipróbált, azt visszaküldi. Mivel minden kulcsot csak egyszer próbálnak ki, annak van a legnagyobb esélye a helyes kulcs megtalálására, aki a legtöbbet tudja kipróbálni. Minden szükséges program ingyen letölthetõ a három társaság szerverérõl, a résztvevõknek csak futtatniuk kell. A három társaság egyelõre egymással is verseng, de felmerült a kooperáció lehetõsége is. Az egész hajtásból két dolog fog kiderülni: egyrészt, hogy mekkora biztonsággal áll ellent az RC5-kódolt szöveg a brute-force támadásnak, másrészt hogy teremthetõ-e olyan összefogás az Interneten, amellyel belátható idõn belül megfejthetõ egy titkosított üzenetet. Végül, de nem utolsósorban a dolog jó buli: a maroknyi lelkes hazai õrült a Cyberian-féle társaságot erõsíti STB+ néven, csatlakozni a http://caesar.elte.hu/~rc5/ címen lehet. Lapzártakor a teljes Cyberian-féle társulat 74 nap elteltével, több tízezernyi számítógép folyamatos munkájával a kulcsok 2,2 százalékán van túl (a jelenlegi kapacitás mellett a kulcsok nagyjából 1 százaléka próbálható ki 15 nap alatt), az STB+ csapat a 150. hely környékén áll a megoldólistán.

- ry kóder -

Kriptotörténelem

A titkosítás 4000 éves írásos múltat tudhat maga mögött, a jelenleg legrégebbinek tartott titkosírás kõbe karcolt hieroglifikus egyiptomi temetési szöveg. A titkosírás iránt mindig is érdeklõdtek békés naplóíró hobbisták, de azért a klasszikusnak tekinthetõ célja többnyire ellenséges területen átjuttatandó üzenetek kódolása volt sikeres diplomáciai vagy háborús bonyodalom kiváltása céljából. A legnagyobbat talán Mária, a skótok nevezetes királynõje bukta a XVI. században, amikor a börtönbõl küldött titkosírásos üzenetét elfogták és megfejtették, majd Máriát rövid úton kivégezték. Ekkoriban még futárok és postagalambok szelték a földi és légi utakat, és az üzenet megszerzéséhez elõbb a hordozót is el kellett fogni, aztán jöhetett a megfejtés. Ráérõs tevékenység volt, lévén, hogy egy üzenet-válasz ciklus ideje akár hónapokra is rúghatott, és az üzenet küldõje egészen addig nem is gyanakodott, míg hónapokkal az üzenet elküldése után el nem jöttek a fejét venni. Ezek a korai, fapados módszerek domináltak a távíró és a rádióhullámú kommunikáció feltalálásáig, amelyek új színt vittek a titkosítók és a visszafejtõk küzdelmébe. Ezek a kommunikációs módszerek egyrészt felgyorsították, szinte azonnalivá tették egy üzenet elküldését, másrészt sérülékennyé tették az üzenetet továbbító csatornát. A távíró üzenet illetéktelen megszerzéséhez alapvetõ lehallgatói ismeretekre van csupán szükség, a rádióhullámokat pedig mindenütt halljuk a besugározható területen belül, és még csak azt sem tudhatjuk biztonsággal, hányan hallgatják az adón és a vevõn kívül az adást. A modern csatornák titkosítás nélkül használhatatlanok bizalmas adatok továbbítására. Ez fokozottan igaz egy olyan világméretû számítógép-hálózat esetén, mint az Internet, ahol a küldõ és a vevõ között az üzenet akár többtucatnyi telefontársaság vonalát és közel ugyanennyi adatátviteli szolgáltatást nyújtó cég eszközeit érinti, és elvben szinte mindenütt egyidejûleg jelen lehet a lehallgatáshoz és visszafejtéshez szükséges ember, technika és kapacitás. Ebbõl a lehetõségbõl az a gyakorlati következtetés adódik, hogy titkosítani szükséges, akár az egyszerû polgárnak is, már csak a miheztartás végett. A kérdés a hogyan, a módszer. Természetesen jól, nehogy úgy járjunk, mint Mária.