Gyakoriságelemzés
A matematikában, a fizikában és a jelfeldolgozásban a gyakoriságelemzés módszerével lehet felbontani egy függvényt, hullámot vagy jelet gyakorisági összetevőire, így lehetővé téve a frekvenciaspektrum elkészítését.
A kriptanalízisben a gyakoriságelemzés a kódolt szövegben a betűk vagy betűcsoportok gyakoriságának vizsgálatát jelenti, amelyet a klasszikus rejtjelek feltörésére használnak.
A gyakoriságelemzés alapjai
A gyakoriságelemzés azon a tényen alapszik, hogy bármely szövegrészletben bizonyos betűk vagy betűkombinációk különböző gyakorisággal fordulnak elő. Sőt, egy adott nyelvben a betűknek rájuk jellemző az eloszlása, amely minden szövegrészletben nagyjából azonos. Így például az angol nyelvben az E betű nagyon gyakori, szemben az igen ritka X-szel (a leggyakoribb betűk az angol nyelvben sorban: E, T, A, O, I, N, S, a legritkább a Z, melyet a Q, a J és az X követ). Az ún. bigrammák vagy digráfiák, azaz a két egymást követő betűből álló betűkombinációk (betűpárok) terén az angol nyelvben azt tapasztaljuk, hogy a TH és a HE fordul elő a leggyakrabban, ami nem meglepő, hiszen a THE szó az angol nyelv határozott névelője. A sorban a leggyakoribb kötőszavak (AND), elöljárószók (IN, ON), illetve azok elemei következnek. A legritkábban előforduló bigrammák között említhetjük az NZ és a QJ betűpárokat.
Természetesen a magyar nyelvben is megvan minden egyes betűre a rá jellemző eloszlás: a leggyakoribb betűk az E, az A, a T, az L és az N, és nyilván a magyar nyelvtől idegen betűk (Q, W, X) igen ritkák.
Néhány kódolt szöveg az adott nyelv ilyen természetű tulajdonságai megőrződnek, és ezt az ún. ciphertext-only attacknél (COA) lehet kihasználni.
A megemlített gyakoriságok a nyelvstatisztikának a legelemibb részét képezik, amely ennél bonyolultabb témákkal is foglalkozik, így az egyes nyelvekben az egy betűre jutó információmennyiség, azaz az adott nyelv entrópiájának kiszámításával, vagy a betűk, szavak gyakorisága és egyéb gyakoriságok között fennálló matematikai összefüggésekkel.
Használata egyszerű helyettesítő rejtjelek megfejtésére
Egy egyszerű helyettesítő rejtjel minden betűt egy másik betűvel helyettesít úgy, hogy azonos betűk helyett azonos, különböző betűk helyett különböző betűket írunk a kódolt szövegben. Így például, ha a leggyakoribb betűt (e) X-nek írjuk a kódolt szövegben, akkor a szöveg elemzőjének az X-ek magas száma azt fogja sugallni, hogy az X ezt a leggyakoribb betűt, vagyis az e-t helyettesítheti.
A gyakoriságelemzés alapvető használatának két fő lépése van: először meg kell számolni, hogy az egyes betűk a kódolt szövegben hányszor fordulnak elő, majd ez alapján (az adott nyelvre vonatkozó betűgyakorisági előismeretek birtokában) megfeleltetni azokat az eredeti szöveg feltételezett betűinek. Ha többször szerepel az X a kódolt szövegben, mint bármelyik másik betű, akkor elég valószínű, hogy az e-nek felel meg, de ez persze korántsem biztos. Ha ebből kiindulva nem sikerül előrejutnunk, esetleg a szövegkörnyezet alapján egyértelműen ki tudjuk zárni a megfeleltetést, akkor (mind az angol, mind a magyar nyelvben) az ugyancsak nagyon gyakori a, t, o betűkkel próbálkozhatunk. Ugyanakkor például a q vagy a z betűre mindkét vizsgált nyelvben jellemző gyakoriságból kiindulva nincs reális esélye annak, hogy egy ilyen gyakori X helyettesítse ezeket. Ilyen megfontolások alapján a kriptanalitikusnak több kombinációt kell próbálgatnia, hogy oda-vissza történő leképezésekkel, társításokkal előbb-utóbb eljusson a megfejtéshez.
Ennél bonyolultabb alkalmazása is elképzelhető a nyelvi statisztikának, így a már említett bigrammák (betűpárok) vagy trigrammák (betűhármasok), de akár még több egymást követő betű csoportjának gyakoriságának figyelembe vétele. Ez bonyolultabb szövegek megfejtésénél elengedhetetlen a kriptanalitikus számára. Például az angol nyelvben a Q ugyan ritkán fordul elő, de amikor szerepel a szövegben, akkor szinte kivétel nélkül az U betűvel párban.
Példa az angol nyelvből
Tegyük fel, hogy Éva elfogott egy kriptogramot, amelyről tudja, hogy egy egyszerű helyettesítő rejtjellel lett kódolva:
LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX
Ebben a példában a nagybetűket a kódolt szöveg betűinek, a kisbetűket az eredeti szöveg (feltételezett) betűinek jelölésére használjuk, az X~t jelölés pedig azt fejezi ki, hogy arra gondolunk, a kódolt X az eredeti szöveg t betűjének felel meg.
Éva az alábbi gondolatmeneten keresztül használja fel a gyakoriságelemzést a kriptogram megfejtéséhez: a betűk és betűcsoportok megszámolása után arra a következtetésre jutott, hogy a leggyakoribb betű az I, a leggyakoribb betűpár az XL, a leggyakoribb betűhármas pedig az XLI. Az angol nyelvben a leggyakoribb betű az e, a leggyakoribb betűpár a th, a leggyakoribb betűhármas pedig a the. Mindez erősen azt sugallja, hogy X~t, L~h és I~e. Mivel a szöveg második leggyakoribb betűje az E, és az angol nyelv két leggyakoribb betűjét, a t és az e betűt Éva már társította valamelyik kódolt betűhöz, ezért a legvalószínűbb az, hogy E~a, ami az angol betűk között a harmadik leggyakoribb. Próbaképpen elvégezve az ezen feltételezéseknek megfelelő behelyettesítéseket az alábbi, félig desifrírozott szöveget kapjuk:
heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReM WQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJ GSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtV eZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMtha PPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPP thMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMt
Ezeket a kezdeti tippeket használva Éva feltételezéseinek bizonyítására sémákat fedez fel, mint például a that szót. Ugyanakkor újabb feltételezésekbe tud bocsátkozni: a Rtate lehet state (R~s) az atthatMZe at that time (M~i, Z~m), a heVe here (V~r), amely feltételezésekkel tovább fejtheti a szöveget:
hereTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGasei WQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJ GSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtr emitFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQitha PPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPP thiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYit
Ezek az újabb összefüggések még több betűt sugallnak (például a remarA lehet remark (A~k)), és innentől kezdve egyenes az út a megoldás felé hasonló gondolkodás mentén haladva.
Ebben a példában Éva tippjei mind helyesek voltak. Ez azonban nincs mindig így, gyakran már a legelső feltételezésünk hibásnak bizonyul, ilyenkor szükség lehet több lépést is visszalépni vagy a példa leegyszerűsített indoklásaival ellentétben sokkal mélyebben megvizsgálni a szöveg statisztikáját.
Az is elképzelhető, hogy az eredeti szöveg a legkevésbé sem tükrözi az elvárt eloszlásokat, különösen a rövidebb üzeneteknél számíthatunk jelentős eltérésekre. Sőt, készíthető szándékosan elferdített szöveg is, az irodalomban is ismerünk olyan regényt, amelyből például teljes mértékben kihagyták az e betűt - ezt az irodalmi formát lipogrammának nevezzük.
Története és használata
A gyakoriságelemzés (és egyáltalán a kriptanalízis bármely ágának) első magyarázatát a 9. századi arab polihisztor, Abu Yusuf Yaqub ibn Ishaq al-Sabbah Al-Kindi írta le Egy kézirat a kriptográfiai üzenetek megfejtéséről (Ibraham, 1992) című munkájában. A Korán szövegének alapos vizsgálata fényt derített arra, hogy az arab nyelvnek jellemző betűgyakorisága van. A használata egyre csak terjedt, és a reneszánsz korában az európai államokban már olyan széles körben használták, hogy a kriptográfusok több csellel is próbálkoztak, hogy térdre kényszerítsék:
- Homofónok használatával, ami azt jelenti, hogy a leggyakoribb betűkre az amúgy monoalfabetikus (egy ábécével dolgozó) helyettesítő rejtjelben több alternatívát is használtak, így például az angol nyelvben az X és az Y is jelenthette az E-t.
- Polialfabetikus rejtjelek használatával, azaz több helyettesítő ábécével kódoltak, ahol körmönfont módon válogatták meg és variálták az ábécéket (valószínűleg Leone Alberti tervelte ki először).
- Poligrafikus helyettesítéssel, vagyis betűk helyett a betűpárokat vagy betűhármasokat tekintették a szöveg egységeinek (jó példa rá a Playfair-rejtjel, amelyet Charles Wheatstone a 19. század közepén talált fel)
Ezeknek a gyakoriságszámoló támadások elleni próbálkozásoknak mind az volt a hátránya, hogy tovább bonyolította mind a sifrírozást, mind a desifrírozást, ami hibákhoz vezetett. Egy elhíresült történet szerint egy brit külügyminiszter a Playfair-rejtjelet azért utasította el, mert, mint mondta "még ha az iskolás gyerekek meg is tudnak birkózni vele (ahogyan ezt Wheatstone és Playfair megmutatta), a mi attaséink soha nem fogják tudni megtanulni!".
A 20. század első felének rotoros gépei (mint például az Enigma) lényegében immunisak voltak a gyakoriságelemzésre. Azonban másféle elemzések ("támadások") sikeresen megfejtették ezen gépek üzeneteit is.
A gyakoriságelemzés használata az eredeti szövegnyelv statisztikájának megértését csupán alapvető szinten igényli, emellett némi problémamegoldó képességre van szükségünk és kézi használat esetén nem árt, ha jól tűrjük a sok papírmunkával járó fejtést. A második világháború idején mind az amerikaiak, mind az angolok úgy toborozták kódtörőiket, hogy újságokból vett keresztrejtvények megoldására szerveztek versenyeket, majd a győztesekre rátették a kezüket. Néhány, a tengelyhatalmak által használt kód gyakoriságelemzés használatával megfejthető volt. A betűszámolás és statisztikai elemzés gépiesített módszereit először a II. világháború alatt használták, talán az amerikai hadsereg SIS nevű szervezete. Manapság a betűszámlálás és -elemzés fáradságos munkáját számítógépes programok végzik, ami másodperceken belül sikerrel járhat. A modern számítástechnikai erők ismeretében a klasszikus rejtjelek aligha nyújtanak bármiféle védelmet a bizalmas információknak.
Az irodalomban
Az irodalomban többen is írtak a gyakoriságelemzésről, így Edgar Allan Poe Az Arany Bogár, valamint Arthur Conan Doyle Sherlock Holmesról szóló A táncoló figurák esete című műve, ahol ezt a módszert az egyszerű helyettesítő rejtjelek elleni támadásra használják. A Poe művében megjelenő rejtjel több megtévesztő elemet is tartalmaz, de ez mégis inkább csak egy irodalmi eszköz, mintsem bármiféle kriptográfiai jelentőséggel bíró kód.
A másik említett műben egy ügyfél Sherlock Holmeshoz pár furcsa levéllel állított be. A kertjében talált levélkék mindegyikén pálcikaemberek hemzsegtek, mindegyik máshogy tartotta kezét, lábát. Sherlock persze nem lenne Sherlock, ha rá nem jönne, hogy ez egy titkosírás. S ha már rájön, akkor meg is fejti, a betűgyakoriság alkalmazásával. Holmes, mint művelt ember, tudta, hogy az angolban a leggyakoribb betű az e. Föltette, hogy a levél angolul van, s megszámolta, mely figura ismétlődik leginkább. Próbaként ez lett az e. Több háromfigurás csoportot talált, ahol ez állt utoljára. Hohó (– szólt –,) ez lesz a the, vagyis a határozott névelő. Máris az összes ilyen figura fölé beírhatta a t és h betűket. Ilyenképpen nemsokára végzett is a levelek megfejtésével, dr. Watson nem kis ámulatára.
A történelemben
A Babington-összeesküvés
A gyakoriságelemzés egy királynő halálát is okozta. Stuart Mária nyugodtan szövögetett összeesküvést Angliai Erzsébet ellen, hisz titkosírással írogatta leveleit. Ám egy Felipez nevű korai kódfejtő rájött e módszerre – amit valójában 1 200 éve az arabok találtak ki, mint annyi minden mást –, s az ellenség így birtokába jutott a terhelő bizonyítéknak. A vég ismert: Máriát lefejezték.
Lásd még
Források
- Helen Fouché Gaines, "Cryptanalysis", 1939, Dover. ISBN 0-486-20097-3
- Ibraham A. “Al-Kindi: The origins of cryptology: The Arab contributions”, Cryptologia, 16(2) (April 1992) pp. 97–126.
- Abraham Sinkov, "Elementary Cryptanalysis : A Mathematical Approach", The Mathematical Association of America, 1966. ISBN 0-88385-622-0.
