Gyakoriságelemzés
A Wikipédiából, a szabad lexikonból.
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.
Tartalomjegyzék |
[szerkesztés] A gyakoriságelemzés alapjai
Szócikk: Betűgyakoriság
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 ábécének szerves részét nem képező 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.
[szerkesztés] 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.
[szerkesztés] 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 legyakoribb 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.
[szerkesztés] 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ámasokat tekintették a szöveg egységeinek (jó példa rá a Playfair-rejtjel, amelyet Charles Wheatstone az 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 megmutatatta), 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, emelett 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 II. 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ópés 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.
[szerkesztés] 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.
[szerkesztés] A történelemben
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 lefejezik, a harmadik csapás sikerül csak, röptében leesik a paróka, s kivillan a majdnem kopasz fej, ráadásul a levágott fő ajkai még negyedóráig mozognak. Segítőjét lófarokra kötötték, majd leszedték, fölakasztották, majd leszedték, majd kibelezték, így végezték ki.
| Klasszikus titkosírás |
| Rejtjelek: ADFGVX | Affin | Atbash | Autokulcs | Bifid | Book | Caesar | Négy négyzet | Hill | Nihilista | Permutációs | Pigpen | Playfair | Polialfabetikus | Reihenschieber | Reservehandverfahren | Futókulcs | Helyettesítő | Transzpozíció | Trifid | Két négyzet | Vigenère |
| Kriptanalízis: Gyakoriságelemzés | Egybeesés-számlálás |
| Egyéb: Kriptogram | Polübiosz négyzete | Scytale | Straddling checkerboard | Tabula recta |
[szerkesztés] Lásd még
- Betűgyakoriság
- ETAION SHRDLU
- Zipf törvényei
- Nyelvstatisztika
[szerkesztés] Referenciák
- Helen Fouché Gaines, "Cryptanalysis", 1939, Dover. ISBN 0486200973
- 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 0883856220.
Based on work by 