Kriptográfia: Prímszámháború

szerző
- ry kóder -
publikálva
1997/37. (09. 11.)
Twitter megosztások száma
Google +1
Egyéb megosztás

"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.

"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.

szerző
- ry kóder -
publikálva
1997/37. (09. 11.)
Twitter megosztások száma
Google +1
Egyéb megosztás
Cimkék:
Ezt már olvasta?

Legfrissebb Narancs

„Nem kérünk bocsánatot”
Interjú „Tibi atyával”
Interjú Palkovics Lászlóval
Mi lesz az MTA-intézetekkel?
Évadnyitó melléklet
Jordán Adél, Carly Wijs, Pintér Béla színháza
Tartalomjegyzék Legfrissebb Narancs

Kultúra

még több Kultúra...

Narancs

Vélemény

még több Vélemény...