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

  • - ry kóder -
  • 1997. szeptember 11.

Tudomány

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

Figyelmébe ajánljuk

Tendencia

Minden tanítások legveszélyesebbike az, hogy nekünk van igazunk és senki másnak. A második legveszélyesebb tanítás az, hogy minden tanítás egyenértékű, ezért el kell tűrni azok jelenlétét.

Bekerített testek

A nyolcvanas éveiben járó, olasz származású, New Yorkban élő feminista aktivista és társadalomtudós műveiből eddig csak néhány részlet jelent meg magyarul, azok is csupán internetes felületeken. Most azonban hét fejezetben, könnyebben befogadható, ismeretterjesztő formában végre megismerhetjük 2004-es fő műve, a Caliban and the Witch legfontosabb felvetéseit.

„Nem volt semmi másuk”

Temették már el élve, töltött napokat egy jégtömbbe zárva, és megdöntötte például a lélegzet-visszatartás világrekordját is. Az extrém illuzionista-túlélési-állóképességi mutatványairól ismert amerikai David Blaine legújabb műsorában körbejárja a világot, hogy felfedezze a különböző kultúrákban rejlő varázslatokat, és a valódi mesterektől tanulja el a trükköket. 

Játék és muzsika

Ugyanaz a nóta. A Budapesti Fesztiválzenekarnak telefonon üzenték meg, hogy 700 millió forinttal kevesebb állami támogatást kapnak az együttes által megigényelt összegnél.

A klónok háborúja

Március 24-én startolt a Tisza Párt Nemzet Hangja elnevezésű alternatív népszavazása, és azóta egyetlen nap sem telt el úgy, hogy ne érte volna atrocitás az aktivistákat.

Hatás és ellenhatás

  • Krekó Péter
  • Hunyadi Bulcsú

Az európai szélsőjobb úgy vágyott Donald Trumpra, mint a megváltóra. Megérkezik, majd együtt elintézik „Brüsszelt” meg minden liberális devianciát! Ám az új elnök egyes intézkedései, például az Európával szemben tervezett védővámok, éppen az ő szavazó­táborukat sújtanák. Egyáltalán: bízhat-e egy igazi európai a szuverenista Amerikában?

„Egy normális országban”

Borús, esős időben több száz fő, neonácik és civilek állnak a Somogy megyei Fonó község központjában. Nemzeti és Mi Hazánk-os zászlók lobognak a szélben. Tyirityán Zsolt, a Betyársereg vezetője és Toroczkai László, a szélsőjobboldali párt elnöke is beszédet mond. A résztvevők a lehangoló idő ellenére azért gyűltek össze szombat délután, mert pár hete szörnyű esemény történt a faluban. Március 14-én egy 31 éves ámokfutó fahusánggal rontott rá helyi lakosokra: egy középkorú és egy idős nő belehalt a támadásba, egy idős férfi súlyos sérüléseket szenvedett.