Budapesti Műszaki Főiskola – Kandó Kálmán Villamosmérnöki Főiskolai Kar Számítógéptechnikai Intézet - Székesfehérvár
Bevezetés a kriptográfiába I. A kriptorendszerek első generációja Segédlet az Információtechnika c. tárgy Kriptográfia fejezetéhez
Dr. Tóth Mihály főiskolai tanár
Táskaszám:
2002. szeptember
SZKÜTALI Spártai vezéri pálca, amit a rátekert szalaggal titkosításra is használtak. Az American Cryptogram Association (ACA) hivatalos szimbóluma Felelős kiadó: Dr. Bognár Sándor főigazgató Készült a BMF Sokszorosító üzemében Műszaki vezető: Bélteky István Példányszám: 200 Munkaszám:
2
Tartalomjegyzék
Bevezetés a kriptográfiába ......................................................................................... 5 Előszó ........................................................................................................................ 5 Titkosítás és rejtés ..................................................................................................... 6 Kriptorendszerek generációi ...................................................................................... 7 Alapfogalmak és jelölések .......................................................................................... 9 Néhány általános megjegyzés a kriptorendszerekről ............................................... 11 Az ó-egyiptomi írások és nyelv ................................................................................ 15 Az ó-egyiptomi írások és nyelv ................................................................................ 15 A sumér nyelv ......................................................................................................... 16 A sumér nyelv ......................................................................................................... 16 A krétai lineáris B írás .............................................................................................. 16 A megfejtések ma is hasznosítható tanulságai ........................................................ 18 A megfejtések ma is hasznosítható tanulságai ........................................................ 18 Első generációs kriptorendszerek ............................................................................ 19 A helyettesítés ......................................................................................................... 19 Monoalfabetikus helyettesítési módszerrel titkosított szöveg feltörése .................... 29 A reciprocitás elve .................................................................................................... 41 A feltörés „receptje” ................................................................................................ 41\\ A 2.1 megfejtési példa tanulságai ............................................................................ 44 Az első generációs rendszerek uniformitásai ........................................................... 46 A két- és több-betűs (biliterális, polyliterális) helyettesítések ................................... 48 Mire jó a szövegstatisztika? ..................................................................................... 49 A φ teszt ................................................................................................................... 51 A koincidencia-index ................................................................................................ 52 A transzpoziciós titkosítás ........................................................................................ 53 A geometriai titkosítás .............................................................................................. 53 Miért geometriai ez a titkosítás? .............................................................................. 54 Transzpozició forgatható ráccsal.............................................................................. 56 A transzpoziciós titkosítási transzformáció jellegzetes tulajdonságai ....................... 57 Az ismételt transzformációk ..................................................................................... 58 A szorzat-transzformáció és az invertálhatóság ....................................................... 59 Tárgymutató ............................................................................................................. 62
3
Szakirodalom ........................................................................................................... 64
4
1 Bevezetés a kriptográfiába 1
Előszó Amióta az ember ismeri az írást és olvasást, azóta igény van arra is, hogy valamely leírt szöveget csak annak az elolvasására hivatottak legyenek képesek elolvasni és értelmezni. Más esetekben az írásokat, vagy a mai képregények ókori megfelelőit éppenséggel arra szánták, hogy lehetőleg minél több ember képes legyen azokat értelmezni. Az utóbbi kategóriába tartoznak pl. a királyok nagy tetteit, isteni származását, dicsőségét vagy törvényeit megörökítő képek, feliratok, de ide tartoznak azok a feliratok, lenyomatok, jelek is, amelyek hitelesíteni hivatottak e jelekkel ellátott írásokat, okleveleket, kereskedelmi szerződéseket, rendelkezéseket, mint pl. az akár 4000 évnél is régebbről előkerült pecsétek. Mind a kétféle célnak léteznek a mai megfelelői. Az előbbiek a mai modern titkosírások, üzenetek, az utóbbiak pedig a valamilyen dokumentumot hitelesítő, annak eredetét, tulajdonjogát, szerzőjét azonosító technikák. Ma már sok országban ―így Magyarországon is― törvény gondoskodik arról, hogy ezeket az (elektronikus) technikákat a hagyományos aláírásokkal és hitelesítési módszerekkel azonos jogérvényűnek fogadják el mind a közigazgatásban, mind a mindennapi joggyakorlatban. Miért aktuális kérdés ma a kriptográfia gyűjtőnéven összefoglalt témakör és annak alkalmazásai? 1
A nyílt, mindenki által (t.i. aki a nyelvet tudja) megérthető információk titkosításának, és az ilyen titkosított információ megfejtésének tudományát nevezik idegen szóval kriptográfiának (Cryptography). Ezt a szót aztán az angol terminológia szóösszetételekben, jelzős szerkezetekben és igeként is használja ( Pl., Cryptoanalysis, Criptographic sg. Cryptanalyst, Cryptosystem stb.) A Cryptosystem kifejezés felöleli egy titkosítási/megfejtési rendszer módszereit, sajátságait. Helyette a szó szerinti fordítását, azaz a „kriptorendszer” megnevezést alkalmazzuk. Ismert és a magyar szaknyelvben használatos szó a francia eredetű "sifrírozás" (angolban: encryption) szó is, valamint a származékai (pl. "desrifrírozás"), aminek az angol terminológiában a "cyphering - decyphering" szópár a megfelelője. A sifrírozást (vagy a "cyphering"-et) persze jól helyettesíthetjük a "titkosítás" szóval, s még a "titkosított szöveg" kifejezés is elmegy (a "ciphertext" helyett), a fosztóképzős alakokra (desifrírozás, decyphering) azonban már új szót kell találnunk, mint pl. "megfejtett" szöveg, vagy megfejtett kód. Ezek kissé nehézkesen hangzanak. Az azonos alapelven működő "cyphering" és "decyphering" gyűjtőfogalmaként alkalmazott "cipher" (vagy a francia chiffre) fogalom magyar megfelelőjének megtalálásával aztán végképp gond van: esetenként kiírjuk helyette a "titkosító - megfejtő" (eljárás) kifejezést, vagy egyszerűen csak titkosító ―esetleg kódoló― eljárásról beszélünk, de beleértjük a megfejtést is. Az alábbiakban, ahol csak lehet, magyar kifejezéseket használunk, de esetenként elkerülhetetlen valamelyik idegen eredetű kifejezés magyar helyesírás szerinti átírásának használata. Ahol lehet, zárójelben vagy lábjegyzetben megadjuk az angol szakkifejezést is azoknak, akik az angol szakirodalmat olvassák. Jóllehet a magyarnyelvű szakirodalomban használják már a "kriptográfia" helyett a "titkosítás" szót, ez még korántsem elfogadott, s addig, amíg jobb szó nincs rá, itt a "kriptográfia" szót és válfajait is használjuk. Az alábbiakban nem csak lábjegyzetben, hanem a főszövegben is összefoglaljuk azokat a legfontosabb fogalmakat és megnevezéseket, amelyeket használni fogunk.
5
Nos nagyjából a második világháború végéig (és az azt követő további két évtizedben) a titkos üzenetváltást szinte kizárólag katonai és diplomáciai célokra alkalmazták. Ez persze nem jelenti azt, hogy éleseszű, a rejtvények készítését és megfejtését szórakozásnak tekintő emberek nem készítettek korábban is titkos írásokat vagy nem foglalkoztak elfelejtett nyelvek írásainak megfejtésével, de a titkosírások széleskörű, civil alkalmazásának és elterjedésének kezdetei kb. az 1970-es évek közepére tehetők. Titkosítás és rejtés Említettük, hogy amióta írás létezik, annak az igénye is létezik, hogy az írott üzenetet csakis az arra illetékes személy vagy személyek legyenek képesek elolvasni és értelmezni. Bizonyos mértékig szóban közölt információkra is érvényes ez a megállapítás. „Nicht for dem Kinder” ― mondták a szülők egymásnak, ha olyasmi került szóba, amit nem a jelenlévő gyerekeik fülének szántak. 2 A második világháborúban a csendes óceáni amerikai flottánál navaho (Navajo) indiánokat alkalmaztak híradósokként olyan alkalmakkor, amikor szóban kellett a japánok számára érthetetlen üzeneteket küldeni és nem volt idő körülményes titkosításra és megfejtésre, valamint az üzenetküldő személyének a hitelesítésére. Az ókorban a titkosírások mellett vagy helyett elterjedten alkalmazták az üzenetek elrejtését is. Még olyan kuriózus módszereket is (a görögök), hogy egy rabszolga leborotvált fejbőrére tetoválták az üzenetet s megvárták míg kinő a haja. Ez után küldték el az „üzenetet” saját lábán a címzettnek. Polybios ―Kr.e. 200 – 120. élt görög történetíró― a háború tudományáról írt könyvében titkosírási módszerek mellett rejtési módszereket is leír. Egy általa ismertetett módszer az, hogy egy ártatlannak látszó szöveg egyes jószerivel észrevehetetlenül megjelölt betűit összeolvasva kapjuk meg a rejtett üzenetet. Polybios maga ólomlemezre írt üzenet egyes betűit apró tűszúrásokkal ajánlotta megjelölni. Fény felé tartva az ólomlemezt, jól láthatóan előtűntek a jelölések. 3 E módszernek egy változatát aztán még a második világháborúban is használták úgy, hogy a diplomáciai postával küldött nyomtatott újságok egyes betűit jelölték meg pl. szabad szemmel nem is látható mikropontokkal. Számos láthatatlan tintát is használtak, ami csak vegyi hatásokra vagy hőre vált láthatóvá. Ma az elektronikus üzenetekben is elrejthető információ. Képekben pl. úgy, hogy egy-egy képponthoz tartozó un. szín byteok legkisebb helyiértékű bitjeibe rejtik az információt. Ez ugyan megváltoztatja a kép színeit, de csak szemmel észrevehetetlen mértékben. Meglepően sok ilyen rejtett információt tartalmazhat egy-egy kép. Ezzel a rejtési módszerrel azonban az a prob2
Felnőttek körében azonban nem illik olyan nyelven párbeszédet folytatni, amit nem ért meg a jelenlévők közül mindenki. Sajnos sok magyar turista gondolja külföldön, hogy úgysem érti senki, ha magyarul mondanak dehonesztáló megjegyzéseket egymásnak, pedig a legváratlanabb helyeken és alkalmakkor is lehet a közelükben olyan, aki megérti a magyar szót. Akár egy afrikai szafarin is a bennszülöttek között is.
3
Polybios még arra is kitért, hogy a vékony ólomlemezre írt üzenetet be lehet varrni egy saru dupla talpbőrei közé és akkor sem megy tönkre, ha a sarú elázik. A következőkben még visszatérünk Polybiosra, de jegyezzük meg, hogy elsősorban a történetírói tevékenységéről ismert s nem a titkosírások területén kitalált vagy leírt módszereiről.
6
léma, hogy elvész, ha a képet tömörítik, vagy editálják (átméretezik, a kontrasztját megváltoztatják, stb.). Lényegében ugyanígy, a legkisebb helyiértékű bitekben lehet információt elrejteni hang fileok esetében is. Html formátumú fileoknál kihasználható, hogy a formátum információt hordozó un. „tag”-ek nem érzékenyek a kisbetű-nagybetű váltásra s így információt hordozhatnak pl. a nagybetűk. Sajnos az un. „fedőszöveghez” képest igen kevés a „tag”, tehát csak kevés információ rejthető imígyen. Az álló vagy mozgó képekbe, vagy hangfilokba rejtett információ ma leginkább az elektronikus „vízjel” szerepét tölti be és a copy-right információk hordozására alkalmazzák. Az információrejtés, idegen szóval szteganográfia, nem tartozik a kriptográfia témaköréhez, ezért majd másutt foglalkozunk vele részletesebben. Kriptorendszerek generációi Jóllehet ma már nem szokás a számítástechnika (ill. a számítógépek) és alkalmazásaik újabb s újabb eredményeit egy-egy új „generációként” emlegetni, érdemes arra emlékezni, hogy korábban a számítógépek un. generációit lényegében az alkalmazott technika határozta meg. Ennek alapján neveztük (később) az elektroncsöves számítógépeket első generációs gépeknek, a félvezetős és un. ferrit-logikás számítógépeket második generációs számítógépeknek, s így tovább. Ennek az írásnak a szerzője úgy véli, hogy hasznos lehet a kriptorendszerek generációiról beszélni annak alapján, hogy milyen technikák jellemzőek az egyes generációkra. Teszi ezt annak a tudatában, hogy a mai modern kriptorendszerek, és különösen azok alkalmazásai már olyan széles területet érintenek (és olyannyira összefüggenek pl. az adatbiztonsági és kommunikációs kérdésekkel), hogy ma már nem érdemes újabb generációkról beszélni, mint ahogyan a számítógépek esetében sem tesszük. Nem a kriptográfia az egyetlen terület, amelynél az újabb s újabb rendszerek öröklik a megelőző rendszerek valamely lényeges tulajdonságait. A kriptográfia mindenesetre ilyen. Ezért nem csak érdekes, hanem a modern rendszerek megértéséhez szükséges is, hogy a korábbi, „történeti” kriptorendszerek lényegét megértsük, legalább röviden foglakozzunk ezekkel a rendszerekkel. A kriptorendszerek generációinál egészen biztosan nagy szerepe van az alkalmazott titkosítási/megfejtési módszereknek, technikának, közös néven az un. transzformációs módszereknek 4 , de nagy szerepe van az üzenet továbbítási technikájának is, vagyis a kommunikációs technológiának 5 is.
4
A nyílt szöveget a titkosítási eljárás során átalakítjuk, más szóval transzformáljuk. Innen az elnevezés.
5
Szigorúan véve ez nem „csak” a kommunikációs technikát jelenti, hanem azokat a nagyon ravasz módszereket is, amelyekkel az üzenet sértetlensége legalább ellenőrízhető és nagy biztonsággal csakis a küldő és a címzett között jöhet létre a kívánt kapcsolat. Mindezeket gyűjtőnéven protokolloknak szokás nevezni.
7
Eszerint a kriptogenerációkat két technológia együttesen határozza meg. Nevezetesen a transzformációs és a kommunikációs technológia. Valahogyan úgy, ahogyan ezt a következő ábra szemlélteti NYÍLT SZÖVEG
TITKOSÍTOTT SZÖVEG KÓDOLÁS
DEKÓDOLÁS
NYÍLT SZÖVEG
TITKOSÍTÁS MEGFEJTÉS KOMMUNIKÁCIÓS TECHNOLÓGIA TRANSZFORMÁCIÓS TECHNOLÓGIA
Jóllehet alább részletesebben is szólunk még a kriptorendszerek egyes generációiról, a következő táblázatban összefoglaljuk a legfontosabb jellemzőiket.
8
GENE-
JELLEMZŐJE
TRANSZFORMÁCIÓS
RÁCIÓ 1.
KOMMUNIKÁCIÓS TECHNOLÓGIA
Monoalfabetikus
Helyettesítés Nagyon ritkán: keverés
Nem jellemző
Polialfabetikus és blokkos
Helyettesítés (kézi módszerrel) KULCSSZÓ
Nem jellemző
Mint az előző de nagyon sok ábécével
Betűnkénti helyettesítés (elektro) mechanikus (pl. rotoros) géppel
Rádió kommunikáció
4.
Produkttranszformációk több iterációban ismételve más-más ún. szubkulcsokkal. Nagy kulcstér és nagy számítási kapacitás, de általában gyorsabbak, mint az 5. generációs rendszerek.
Számítógéppel segített blokkos transzformációk, amelyeknek nem létezik a nyers erő módszerénél gyorsabb kulcs nélküli algoritmusos feltörése.
5.
Azonos titkosító és visszafejtő transzformációk INVERZ kulcsokkal Nagyon nagy számítási igény.
Lényegében u.a. mint a 4. generációnál, de a transzfomációk jellege más
2.
3.
Kommunikáció a világhálón, magánhálózatokon, vagy legalább virtuális magánhálózatokon
Lényegében u.a. mint a 4.generációnál, de a titkosított kommunikációt nem kell kulcs-cserének megelőznie
Alapfogalmak és jelölések Az „eredeti”, titkosítatlan szöveg 6 : nyílt szöveg. Angol terminológiával: plaintext vagy cleartext. Ha a nyílt szöveget egy képletben egyetlen betüvel jelöljük (ld alább), akkor arra a „P” jelölést használjuk a „Plaintext” kifejezés rövidítéseként.
6
A „szöveg itt bármilyen karaktersorozat lehet, tehát számok is, vagy egy képpontokból álló kép egyes pontjaira vonatkozó (szín- vagy szürke-árnyalat) információk sorozata.
9
A titkosítás után kapott, a beavatatlan számára érthetetlen szöveg: a titkosított szöveg, kód vagy kriptogram. 7 Angol terminológiával: ciphertext. Ha a titkosított szöveget egy képletben egyetlen betüvel jelöljük (ld. alább), akkor arra a „C” jelölést használjuk a „Ciphertext” kifejezés rövidítéseként. A titkosítási eljárás: kódolás vagy siffrírozás. Angol terminológiával: encryption (vagy encipherment). Ezért az erre vonatkozó képletekben „E”-vel rövidítik. Érdemes megjegyezni, hogy ez a titkosítási (vagy –más szóval- kódolási) folyamat valamilyen algoritmus szerint átalakítja, azaz transzformálja a nyílt szöveget. A kulcs (angolul: key) az egész titkosítási és megfejtési eljárás igen-igen fontos eleme. Ezért aztán fontos az is, hogy az arra illetékes személyeken kívül ne juthasson senki más birtokába. A titkosítási eljárás és a kulcs együttesen hozza létre a nyílt szövegből a titkosított szöveget. Ezt így jelöljük:
EK(P) = C Lényeges, hogy ugyanaz a titkosítási eljárás ugyanabból a nyílt szövegből más kulccsal más titkosított szöveget hoz létre, azaz
EK1(P) ≠ EK2(P) ha K1 ≠ K2 A kulcs (vagy az egész titkosítási rendszer) kompromittálódásának nevezzük azt, ha a titkosítási kulcs arra illetéktelen személy birtokába jut. Ilyenkor szokás azt mondani, hogy arra illetéktelennek sikerült betörnie (betörés) a rendszerbe. Már itt hangsúlyozzuk, hogy a betörések túlnyomó többségének az oka emberi gondatlanság, a biztonsági előírások be nem tartása szokott lenni. (Pl. elbocsátott dolgozó bosszúja, akinek a távozásakor nem cserélték ki a kulcsokat, nem újították meg a jelszavakat, stb.) Egy adott titkosítási rendszerhez általában sokféle kulcs tartozhat, de egyáltalán nem mindegy, hogy hányféle. Ha egy kriptorendszernek mondjuk összesen 26 féle kulcsa létezhet, akkor biztosan nem nehéz és nem időigényes dolog kipróbálni mindegyik kulcsot egy ismeretlen kriptog7
A „kód” mindenesetre sokkal általánosabb fogalom, mint a „kriptogram vagy siffe”. Nehéz is definiálni, mint a nagyon széles körben használt fogalmakat általában. Azt mondhatjuk, hogy a „kód” valamilyen információnak valamilyen adott szempont szerinti leginkább alkalmas megjelenítési formája. Többnyire nem is titkosítás a célja. Gondoljunk pl. a Morze kódra, a tengerészeti jelzések nemzetközi kódjaira, vagy éppenséggel a DNS-ben kódolt genetikai információra. Kódnak tekinthető azonban pl. a közlekedésrendészeti táblákon egyegy „ikonnal” jelzett, nyelvhez nem kötött információk rendszere is. A titkosírások rendszerében azonban a „kód” a titkosított szöveget (ciphertext, siffre vagy kriptogram) jelenti. „Kódolóknak” nevezik azokat az embereket, akik a titkosítással foglalkoznak és „kódtörőknek” azokat, akik a titkosított szövegek megfejtésével. Ld. pl. David Kahn klasszikus könyvét. [8]. William F. Friedman (a második világháború híres kódtörőinek egyike) elég élesen megkülönbözteti a kriptogram és a kód fogalmát. Szerinte a kriptogramot úgy kapjuk, hogy valamilyen kriptográfiai módszerrel (algoritmussal) transzformáljuk a nyílt szöveg egyes karaktereit vagy rögzített hosszúságú karaktercsoportjait, blokkjait. Maga a transzformációs algoritmus változatlan, míg a hozzá alkalmazott kulcs változik. Ezzel szemben a titkosítási kódot egy un. kódkönyvvel állítjuk elő, amelyben tetszőleges karakterekhez, szavakhoz, több szavas kifejezésekhez, rész-szavakhoz egy-egy szimbólumot, vagy karaktercsoportot rendelünk hozzá.
10
ram megfejtésére, mert még a legrosszabb esetben is megtalálható a megfelelő kulcs a 26. próbálkozásra. Egy konkrét kriptorendszerben alkalmazható valamennyi lehetséges kulcs összességét kulcstérnek nevezzük, és az adott kriptorendszer biztonsága annál nagyobb lehet, minél nagyobb a kulcstér. A titkosított szöveg visszafejtése a dekódolás vagy desiffrírozás. Angol terminológiával: decryption (vagy decipherment). Ezért az erre vonatkozó képletekben „D”-vel rövidítik. A desiffrírozás a titkosított szövegből, azaz a kriptogramból előállítja az eredeti nyílt szöveget. Képletben:
DK(C) = P A desiffrírozás (=dekódolás) a titkosítási (=kódolási) eljárás ill. algoritmus inverze. A dekódolási eljárás is transzformáció, amely a titkosított szöveget alakítja vissza az eredeti nyílt szöveggé. Kivétel nélkül minden tradicionális titkosítási rendszerben ugyanazt a kulcsot használták a kódoláshoz és a dekódoláshoz, bár nem feltétlenül ugyanolyan módon. (Gondoljunk pl. arra, hogy egy ajtó bezárásához és kinyitásához is ugyanazt a kulcsot használjuk, de záráskor egyik irányba, nyitáskor pedig az ellenkező irányba kell a kulcsot elforgatni.) Szimmetrikus rendszereknek nevezzük azokat a titkosító rendszereket, amelyek ugyanazt a kulcsot használják a kódoláshoz és a dekódoláshoz. Mint említettük az imént, minden tradicionális titkosító rendszer ilyen volt egészen 1976-ig, amikor is feltalálták az un. aszimmetrikus (vagy más szóval: nyiltkulcsú) rendszereket, amelyekben más a kódolás kulcsa és más a dekódolásé, de a két kulcs valamilyen bonyolult, és kívülálló számára megfejthetetlen módon összefügg egymással. A kódoló és a dekódoló eljárást, valamint az azokhoz használatos kulcsok rendszerét együttesen kriptorendszernek (Cryptosystem) nevezzük, a kriptorendszerekkel foglalkozó tudományt pedig kriptográfiának. A titkosított szöveg (= kriptogram) megfejtésére persze kiváncsi olyan ember is, aki nem ismeri a titkosítási kulcsot, bár lehet, sőt valószínű, hogy a titkosítási módszert mégis csak felismeri. A kulcs nélkül azonban vagy egyáltalán nem tudja megfejteni a titkosított szöveget, vagy csak többkevesebb nehézséggel. Az ilyen (tehát a kulcs ismerete nélküli) megfejtést kriptoanalízisnek vagy kód(fel)törésnek nevezik. A kriptoanalízisnek nem feltétlenül célja a titkosított szöveg visszafejtése. Lehet, hogy csak a kulcsát szeretné megismerni, amellyel aztán további szövegeket már könnyen meg tud fejteni. Az ilyen megfejtésekkel foglalkozó emberek a kódtörők (Codebrakers) vagy kriptoanalizátorok (Cryptanalists). Néhány általános megjegyzés a kriptorendszerekről
11
Valamikor úgy gondolták, hogy a titkosítás lényege annak a módszere, mert a módszer az, amire az illetéktelen úgy sem képes rájönni. Ezért aztán a titkosítás története során több módszerről is állították, hogy az megfejthetetlen. Ez többé-kevésbé igaz is volt a technikai fejlődésnek azon a szintjén, amely akkor állt fenn, amikor az adott módszert feltalálták. Legalább 200 éve rájöttek azonban arra, hogy a titkosításhoz használt kulcs az, ami igazán egyedivé és igazán biztonságossá teszi az alkalmazott módszert. A titkosítási módszer és a kulcs (vagy kulcsok) szerepe és jelentősége tehát nagyon is különböző. A ma használatos modern kriptorendszerek esetében a titkosítási módszer nem csak nyilvános, hanem egyenesen szabványosított 8 , és ugyanúgy közzéteszik, mint bármely más szabványt. Nagyon sokszor és nagyon jól használhatók a kriptorendszerek lényeges tulajdonságainak megértetésére a zárak és lakatok analógiái. A mondottak szemléltetésére hadd említsük meg, hogy pl. egy ajtó zárjáról rendszerint első rátekintésre megállapítható, hogy milyen rendszerű zárról van szó (pl. un. cilinderzár), vagy egy számzáras táskáról az, hogy azon számkombinációs zár van, de a zár rendszerének az ismerete nem jelenti azt, hogy az kulcs nélkül is kinyitható. (Tekintsünk el itt és most a zárak feltörésének mestereitől, akiknek mellesleg tetemes időre lehet szükségük a bonyolult zárak feltöréséhez.) Tulajdonképpen két eset van: 1. Vagy található az adott kriptorendszerhez valamilyen algoritmus, amely lehetővé teszi a kulcs nélküli megfejtést is ill. azt, hogy a kulcsot meghatározzuk (analógia az álkulcs), 2. vagy nincs hozzá (ismert) megfejtési algoritmus. ebben az esetben nincs más mód a rendszer feltörésére, mint az összes lehetséges kulcs kipróbálása. Ezt nevezik a nyers erő (brute force) módszerének. A kriptográfia története során megfejthetetlennek nevezett rendszerek esetében azok feltalálásakor nem volt a feltörésükre alkalmas módszer, de azonnal feltörhetővé váltak, amint ilyen módszert találtak. (A később tárgyalandó un. de Vigenere rendszer esetében azért erre az „azonnalra” majdnem 300 évet kellett várni.) Ezek a rendszerek tartoznak tehát a fenti 1. csoportba. Ha a kriptorendszernek nem létezik (ismert) algoritmikus feltörési módszere, akkor nincs más lehetőség, mint valamennyi elképzelhető kulcsot sorra kipróbálni. Ezt nevezik a nyers erő (brute force) módszerének. Ezek a rendszerek tartoznak a fenti 2. csoportba és ezeknél van nagy jelentősége a kulcstér méretének. Tulajdonképpen az elképesztően nagyméretű kulcstér jelenti a mai modern rendszerek biztonságát is. Az un. erős kriptorendszereknél olyan nagy a lehetséges kulcsok száma, hogy a mai leggyorsabb számítógépekkel is ezerévekbe (vagy még hosszabb időbe) kerülne valamennyi
8
A szabványosítást megelőzően egy-egy kriptorendszert annyi megbízhatósági próbának vetnek alá (pl. igen magas díjakat tűznek ki adott időn belüli feltörésükre), hogy akármelyik potenciális felhasználó biztos lehet abban, hogy egy szabványos titkosító rendszer valószínűleg sokkal biztonságosabb, mint egy csakis az ő használatára kitalált új és egyedi titkosító rendszer, amelynek esetleg egyáltalán nincsenek előzetes referenciái.
12
lehetséges kulcs végigpróbálgatása. (Párhuzamos processzálásnál ez az idő lényegesen rövidebb, de még ekkor is elképzelhetetlenül hosszú lehet.) Nem nyilvánvaló azonban, hogy egy újonnan felfedezett kriptorendszer az 1. vagy a 2. csoportba tartozik-e. Lehet, hogy az innovátor meg van győződve arról, hogy az általa felfedezett kriptorendszernek nincs algoritmikus feltörési módszere s később valaki mégis talál hozzá ilyen módszert. 9 Ezért szokás a szabványosítás előtt nyilvánossá tenni az új rendszereket és versenyt hirdetni azok feltörésére. A szabványosításra csak azután kerül sor, hogy a bevezetendő új rendszer kiállta a kriptográfusok minden elképzelhető „támadását”. Ebben rejlik a szabványos kriptorendszerek megbízhatósága. Az elmondottakból következik, hogy a modern (erős) kriptorendszerek mind a 2. csoportba tartoznak, legalább is a mai ismereteink szerint. 10 A titkosító rendszereket kitaláló kriptográfusok és a kriptoanalizátorok (akik nemegyszer ugyanazok) között egyfajta verseny van: Melyikük képes túljárni a másik eszén? Melyik tud olyan rendszert alkotni, amit a másik nem tud feltörni, vagy fordítva: ki tudja előbb, vagy egyáltalán feltörni azt a rendszert, amelyet egy másik megalkotott? Ezért a kriptorendszerek kitalálásakor mindig gondolni kell arra, hogy hogyan lehet azt úgy megalkotni, hogy legalább is nagyon megnehezítsük a feltörést megkísérlő dolgát. Az alábbiakban mi is úgy tárgyaljuk a kriptorendszerek generációit, hogy megvizsgáljuk azok feltörési lehetőségét, módszerét is. Előbb azonban összefoglaljuk, hogy mit is kell tudni ahhoz, hogy megkísérelhessük egy titkosírás megfejtését. Ehhez a következő négy dolog kell: 1. Jó ha (legalább nagyjából) ismerjük azt a nyelvet, amelyen az a nyílt szöveg íródott, amelyből előállították a megfejtendő kriptogramot. 2. Valamilyen módon rá kell jönnünk, hogy milyen módszert alkalmaztak a titkosításhoz. (Identifikáció, azonosítás) 3. Meg kell határozni a titkosító rendszer vagy gép kezdeti beállítását. 11
9
Konkrét példák vannak arra is, hogy jelenleg nem létezik algoritmikus feltörési módszer és arra is, hogy egy kriptorendszerhez a rendszer publikálása után később mégis találtak ilyet. Az előbbi esetre példa az RSA rendszer, amelynek az az alapja, hogy csak próbálgatással lehet eldönteni egy igen nagy (pl. 200 jegyű) számról, hogy az prímszám-e, vagy ha összetett szám, akkor melyek a törzstényezői. Ezért az un. faktorizáción alapuló titkosítási módszerek (mint amilyen az RSA módszer is) csak addig megbízhatóak, amíg nem találnak valamilyen gyors algoritmust az igen nagy számok törzstényezőinek a meghatározására. (Már 300 éve hiába keresnek ilyen módszert, de ez nem jelenti azt, hogy nem is létezhet.) ellenpélda az un. knapsack titkosítás, amely a kitalálásakor igen megbízhatónak látszott de később El Gamal talált hozzá algoritmikus megfejtést. Ezért a knapsack titkosítást nem is tekintik erős kriptorendszernek.
10
Felmerülhet az a kérdés, hogy elképzelhető-e olyan titkosítási rendszer, amely nem „csak” a mai ismereteink szerint, hanem elméletileg is feltörhetetlen. Erre a kérdésre az a válasz, hogy igen, elképzelhető. Nem tudunk (ma) arról, hogy meg is valósítottak ilyen rendszert, de ha a titkosítás valamilyen fizikailag meghatározhatatlan elvre épül, akkor a természettörvényekből következik, hogy feltörhetetlen. Ilyen fizikai elv viszont létezik: Heisenberg határozatlansági tétele.
11
Később, a harmadik generációs (rotoros, elektromechanikus) titkosító gépeknél pl. nem „csak” a titkosítási kulcs lényeges, hanem az a kezdeti beállítás is, amelyből a gép kiindul, amikor egy üzenet titkosítását elkezdi. Ilyen gép volt pl. az un. Enigma, amelynél a kulcsot az éppen használt rotorok és azok sorrendje jelentette, a kezdeti beállítást pedig a kezdeti rotor-poziciók és az un. dugaszok kombinációja. Ilyen kezdeti beállítás azonban a modern szimmetrikus rendszereknél is van. A DES üzemmódjai kapcsán pl. szó lesz egy un. 13
4. Végül, de egyáltalán nem utolsó sorban, fel kell törni a rendszert, azaz meg kell fejteni a titkosírást, ha erre egyáltalán van valami remény. Az utóbbi félmondat a megfejtés egzisztenciájára utal. Más szóval arra, hogy ha lehet (és nagyon sokszor lehet), akkor vizsgáljuk meg először, hogy egyáltalán érdemes-e a megfejtés fáradságos munkájához hozzálátni. Nincs-e annak valamilyen elvi vagy gyakorlati korlátja?
kezdeti vektorról (Initial vector), ami nem azonos a titkosítás kulcsával. Klasszikus rendszereknél –mint amilyen pl. a Cézár kerék- a kezdeti beállítás egyúttal a titkosítási kulcsot is jelentette. Általános esetben azonban más dolog a kezdeti beállítás és más dolog a kulcs.
14
Ez más szóval a megfejthetőséget jelenti. Egészen nyilvánvaló pl., hogy ha csak nagyon kevés szöveg áll a rendelkezésünkre, akkor eléggé reménytelen azt megfejteni, míg ha sok, azonos módon titkosított szövegünk van, akkor több a remény a megfejtésre. 12 Ezt a tapasztalatot alátámasztják egyes mára már elfelejtett (vagy nem ismert) nyelven és nem ismert szimbólumokkal írt ókori írások megfejtései is. Az un. krétai lineáris B írást Michael Ventris és John Chadvick –a zsenialitásukon kívül- azért is tudták megfejteni, mert elég sok ezzel írt írás állt a rendelkezésükre, míg az ugyancsak Kréta szigetén talált un. phaistosi korong írása –többek között- azért megfejtetlen, mert mindmáig nem állnak rendelkezésre vele azonos írással írt más szövegek, vagyis túl kevés az elemezhető szövegmennyiség. Nagyon tanulságosak ebből a szempontból az ókori írások megfejtései, amelyek egyrészt kultúrtörténeti mérföldkövek, másrészt vannak a mai kriptográfiában is hasznosítható tanulságaik. Ezért a kriptorendszerek generációinak tárgyalása előtt a következőkben röviden áttekintünk három, kultúrtörténeti írás-megfejtést. Az ó-egyiptomi írások és nyelv Az egyiptomi nyelv és írás ismerete nem maradt fenn úgy, mint pl. az ókori görögé, kínaié és a latiné. Pythagoras (Kr.e.VI.sz.) állítólag éveket töltött Egyiptomban, ahol a papoktól megtanulta a nyelvet is és az írást is, de ennek semmi nyoma nem maradt fenn az írásaiban. Alexandriai Kelemen egyházatya ( kb. Kr.u.200) már tudta, hogy egyiptomban háromféle írást használtak. Horapollon (Kr.u. V.sz.) eredetileg kopt nyelven írt írása a hieroglifákról görög átiratában maradt fenn s tartalmaz ugyan ma is jónak tartott megfejtéseket az ó-egyiptomi írásjelekről, de annyira félrevezető magyarázatokkal, hogy azok elfogadhatatlanná teszik az egészet. (Vak tyúk is talál szemet...) A megfejtéseivel az is baj, hogy csak szójelket ad meg, jóllehet ezek nem az egyetlen és nem is a legjelentősebb csoportja a hieroglifáknak. 1799-ben Rasid (Rosette) közelében Bonaparte Napóleon katonái sáncásás közben találták meg a Rosette-i követ, amelyre háromféle írással vésték rá ugyanazt a feliratot (t.i. feltételezték, hogy mindhárom ugyanaz): Hieroglif, hieratikus és görög írással. A kő 196-ból származik. J.F.Champollion 1822-ben publikálta a megfejtést, 20 évi munka után. Csak 1828-ban jutott el először Egyiptomba és nem sokkal később, 42 éves korában meghalt. A hieroglif írás történeti, vallási, rituális (szent) szövegek kőbevéséséhez használt képszerű jeleket tartalmaz, de nem képírás. A megfejtések magánhangzói különbözőek. Az írásjelek csak utalnak a hangértékekre. A hieroglif
12
Erre Shannon egy információelméleti megfogalmazást is adott, amellyel majd a szimmetrikus kriptorendszerek tárgyalása során megismerkedünk.
15
írást többnyire jobbról balra írták, de találtak balról jobbra, és felülről lefelé írt szövegeket is. A köznapi életben az írnokoknak diktálták a szöveget s ennek a leírására nem volt alkalmas a hieroglif írás. Ezért már az írásbeliség kezdetén kialakult egy másik írás is, amely rendszerében hasonlít a hieroglif írásra, de a megjelenési formája egészen más. Ezt az írást a görögök hieratikusnak (= papi, szent) nevezték A Kr.előtti VIII.-VII. században ebből fejlődött ki az un. demotikus írás (a görög demos = nép szóból van a neve). Ez egyszerűbb jeleket és rövidítéseket tartalmaz és igen nehéz olvasni. Mind a hieratikus, mind a démotikus írást mindíg jobbról balra írták.
A sumér nyelv • • •
Szóvégződéseket (pl. ragokat) használó, u.n. agglutináló nyelv Olyan sok ékírásos táblát sikerült Babilonban és Ninivében kiásni, hogy szignifikáns statisztikai analízist lehetett elvégezni. Rendelkezésre állt egy korábbi megfejtésből a hasonlóan ékírásos perzsa írás megfejtése.
Rawlinson megfejtésének (persze) előzményei is voltak. Nevezetesen az, hogy a perzsák is ékírást használtak, amit viszont nem Rawlinson, hanem egy a rejtvényfejtést hobbiból művelő német középiskolai tanár: Georg Friedrich Grotenfeld fejtett meg. Ez a megfejtés is érdekes és tanulságos. Rawlinson a sumér nyelvet fejtette meg, s nem az ékírást. Egyébként ő is abból indult ki, hogy talált egy többféle írással kőbevésett feliratot és feltételezte, hogy mindegyik írás ugyanazt a jelentést hordozza, bár különböző nyelveken. A sumér nyelv is szóvégződéseket, ragokat használ, mint a magyar, de e struktúrális sajátságon kívül semmilyen más nyelvi hasonlóságra nem akarok ezzel utalni. Vannak agglutináló nyelvek és kész. Ha azonban valaki olyan foglalkozik egy agglutináló nyelv megfejtésével, aki anyanyelvének logikája attól teljesen különböző, nos az igen nagy nehézségekkel bírkózik. Így volt ezzel Henry Creswicke Rawlinson (1810-1895) is, aki 1844-től politikai ügynök volt Bagdadban és aki végül is 1844-ben babiloni ékírásos táblák alapján megfejtette a sumér nyelvet. A megfejtés történeti érdekessége, hogy nagy segítségére volt Rónai Jácint, aki az 1848-as magyar szabadságharc honvédtisztje volt és 49-ben Angliába emigrált. Rawlinson asszisztenseként dolgozott és a magyar anyanyalvű Rónai számára semmiféle nehézséget nem jelentett egy ugyancsak agglutináló, de egyébként ismeretlen nyelv logikájának megértése. (Csak érdekességként: Az ékírás angol neve: cuneiform.) Ha a magyar nyelvben minden különböző végződést külön-külön esetnek tekint valaki, akkor több, mint 800 esetet kell megkülönböztetnie. Ez előtt egyszerűen értetlenül áll egy angol anyanyelvű ember (hacsak nem éppen idegen nyelvek megfejtésével foglalkozik, mint pl. Randall K. Nichols professzor, az ACA volt elnöke a George Washington egyetemen.) A krétai lineáris B írás
16
• • • • •
Nem volt ismert a nyelv, amelyet használtak Sok írásminta állt rendelkezésre Jó hipotézisekből indult ki Ventris (és Chadwick) és képes volt összefüggések megtalálására Agglutináló nyelvről és szótagírásról volt szó. Michael Ventris 1952-ben publikálta a megfejtést
A krétai un. lineáris B írás megfejtéséhez sok írást találtak, ezért szignifikáns statisztikai analízist tudtak elvégezni. Ellenpélda az ugyancsak Krétán felfedezett un. lineáris A irás, amelyből kevés írásminta van és talán ezért, máig sem fejtették meg. Michael Ventris, aki megfejtette, építész volt és nagyon jó vizuális memóriával rendelkezett, ami segítette abban, hogy különböző írásminták jelei között összefüggéseket fedezzen fel. Megvizsgálták pl., hogy összesen hányféle jelet használtak. (Nem volt nyilvánvaló, hogy a nagyon hasonló, de nem azonos jelek csak az írnokok egyéni eltérései-e, vagy tényleg különböző jelekről van szó.) Mintegy 86 jelet találtak, ami egy betűírás ábécéjének túl sok, egy képíráshoz viszont túl kevés jel. Ezért feltételezték, hogy szótag-írásról van szó. A 86 jel azonban még nem dönti el, hogy nem betűírásról van szó, mert egy csomó ábécében vannak olyan jelek is, amelyeknek nincs hangértékük, hanem csak a kiejtésre vagy a hangsúlyra utalnak, vagy egyszerűen csak az írás díszítő elemei. Pl. a 28 betűs ábécével rendelkező arab írásnál igen fontos az írás dekoratív hatása, ezért vannak betűk, amelyeket másképp írnak a szó elején, a végén, vagy a szó belsejében. Ventris feltételezte, hogy a megtalált krétai írások raktározási listák és nyilvántartások, tehát főleg csak főneveket és mennyiségeket tartalmaznak. Zavaró volt a dátumok teljes hiánya. Bizonyos jellegzetességek alapján feltételezték, hogy itt is agglutináló nyelvről van szó. Ez munkahipotézis volt, amely végül is működőképesnek bizonyult. Michael Ventris 1948-ban kezdett el foglalkozni a krétai lineáris B megfejtésével, miután a hadseregtől leszerelt. 1952-ben volt a „nagy áttörés”. Kb ekkor jött rá, hogy a görög (akháj) nyelv egy nagyon régi, Homéroszt legalább 500 évvel megelőző változatáról van szó. Ventris autóbalesetben halt meg 34 éves korában 1956-ban. A krétai lineáris B írás megfejtéséről John Chadwick-kel együtt írt könyvet, ami Ventris halála évében, 1956-ban jelent meg. Chadwick-nek jelentős szerepe volt mind a munkahipotézisek felállításában, mind a megfejtésben.
17
A megfejtések ma is hasznosítható tanulságai • • • •
Elegendően sok szöveggel kell rendelkezni ahhoz, hogy szignifikáns statisztikai elemzéseket lehessen végezni. A használt nyelv statisztikai szerkezetének ismerete nagyon nagy segítség a megfejtéshez. Ha az ismeretlen szöveg ismert nyelven is rendelkezésre áll, akkor ez kulcs a megfejtéshez. Ha a szöveg ill. a nyelv ismerete nélkül is következtetni lehet az eredeti szöveg értelmére (vagy legalább a rendeltetésére) akkor ez is segítség a megfejéshez.
Térjünk vissza ezek után a kriptorendszerek generációinak tárgyalásához.
18
2 Első generációs kriptorendszerek Az első generációs kriptorendszerek legjellemzőbb tulajdonsága az, hogy un. monoalfabetikus 13 rendszerekről van szó, amelyek a titkosított szöveg (= kriptogram, cyphertext) előállításához egyetlen titkos ábécét használtak. Ez a titkos ábécé persze lehetett valamilyen egyedi, a beavatatlan számára ismeretlen szimbólumkészlet is, de használható volt a mindennapi nyílt szövegek írására alkalmazott ábécé is úgy, hogy a kriptogram ábécé betűi a nyílt szöveg ábécéjének más-más betűihez voltak hozzárendelve, azokat helyettesítették. Pl. úgy, hogy a nyílt szöveg minden betűje helyett az utána következő negyedik betűt írták a titkosított szövegbe. Már az első generációs kriptorendszerek bevezették a titkosítási transzformációk két alaptipusát, nevezetesen •
a helyettesítést és
•
a transzpoziciót (permutációt) vagyis a betűk összekeverését.
Ezt a két alapvető transzformáció-tipust aztán valamennyi későbbi generáció alkalmazta. A negyedik generációs, modern kriptorendszerek mindkettőt vegyesen. A helyettesítés Jóllehet a kezdetektől ismert volt mindkét említett transzformációs eljárás, mégis inkább a helyettesítés volt az, amelyet gyakrabban alkalmaztak az elsőtől a harmadik generációs kriptorendszerekben. Ezért mi is egy nagyon népszerű első generációs kriptorendszeren, az un. Cézár-féle titkosítási eljáráson mutatjuk be a helyettesítési transzformáció legfontosabb tulajdonságait. Jegyezzük meg azonban, hogy a Cézár-féle titkosítási módszer egyáltalán nem az egyetlen helyettesítést alkalmazó titkosítás. Legyen pl. a nyílt szöveg írásához használt ábécé a következő: AÁBCDEÉFGHIÍJKLMNOÓÖŐPRSTUÚÜŰVYZ Legyen a nyílt szöveg pl. ABACUS Ha a nyílt szöveg mindegyik betűjét az alkalmazott ábécé tőle jobbra eső negyedik betűjével helyettesítjük, akkor a titkosított szöveg az adott példában a következő: DÉDFVÜ 13
Pontosabb, ha azt mondjuk, hogy monoalfabetikus, vagy egyetlen kriptogram ábécére visszavezethető rendszerekről van szó, de itt, e rendszerek bevezetésekor még nem szeretnénk a fogalmakat bonyolítani. Később, a helyettesítési módszerek tárgyalása után majd példaként megemlítünk olyan titkosítást is, amelynél a nyílt ábécé egy-egy betűjét pl. kétbetűs betűcsoport helyettesíti.
19
Megfejtésnél a kriptogram minden egyes betűjét az alkalmazott ábécében a tőle balra eső negyedik betűvel kell helyettesíteni.. A könnyebb megkülönböztetés kedvéért írjuk csupa kisbetűvel a kriptogram szövegét. Akkor az adott példa esetében a nyílt szöveg (csupa nagybetűs) ábécéjét egy négy betűhellyel eltolt csupa kisbetűs ábécével helyettesítjük. A Á B C D E É F G H I ű v y z
a
á b c d
e
Í J K L M N O Ó Ö Ő P R S T U Ú Ü Ű V Y Z
é f g h i
í
j
k
l
m n
o ó
ö ő p
r
s
t
u ú ü
Látható, hogy a kriptogram ábécének a táblázat jobboldalán „kicsúszó” négy betűjét a táblázat elejére írtuk be (vastagított betűk). Az adott esetben tehát a nyílt szöveg csupa nagybetűs ábécéjét egyetlen, csupa kisbetűs kriptogram ábécével helyettesítettük. Az alkalmazott titkosítási technológia tehát monoalfabetikus helyettesítés, mert csak egyetlen kriptogram ábécét használunk ti. a csupa kisbetűből állót. Elvileg mindegy, hogy a kriptogram ábécé betűkből áll-e vagy valamilyen, az adott titkosíráshoz kitalált speciális szimbólumkészletből. A fenti példában bemutatott egyszerű titkosírás kapcsán is sokmindent lehet elmondani. Néhány jellemzője a következő: •
A titkosírás küldője és címzettje előre meg kell, hogy állapodjon az alkalmazott ábécében, beleértve ebbe a betűk felsorolási sorrendjét is. Ezt akár a korábban már említett kezdeti beállításnak is tekinthetjük.
•
Ugyancsak előzetesen meg kell, hogy állapodjanak a kriptogram ábécé eltolásának mértékében, ami az adott esetben a titkosírás kulcsa.
Az ábécé bemutatott eltolásán alapuló monoalfabetikus helyettesítést Cézárféle titkosításnak nevezik, mert úgy tudjuk, hogy Julius Caesar alkalmazta először a gall háborúban (amikor még nem is volt császár). A Cézár-féle titkosíráshoz egy nagyon egyszerű eszköz, az un. cézár kerék alkalmazható. Ez nem más, mint két, koncentrikus tárcsa, amelyek kerületére egyenlő közökkel fel van írva az adott esetben alkalmazott ábécé (és ha egyéb jeleket, pl. betűközöket is használnak, akkor azok a jelek is). A két tárcsát egymáshoz képest annyi pozicióval elforgatva, amennyit az adott kulcs meghatároz, a kerületeken egymás alá ill. fölé kerülnek a nyílt szöveg és a kriptogram betűi.
20
Cézár kerék A külső –nagybetűs- kerék a nyílt szöveg, a belső –kisbetűs- kerék a kriptogram ábécét tartalmazza. Az ábécék (itt) nem tartalmazzák pl. a szóköz karaktert és írásjeleket, számokat sem. Itt mindkét ábécé 32 betűs. Egyébként feltétel is, hogy a nyílt szöveg ábécéjében ugyanannyi karakter legyen, mint a kriptogram ábécében, de nem feltétlenül kell a két ábécé karakterkészletének megegyeznie. Az ábrán a külső és a belső kerék egymáshoz képest nincs elforgatva.
A cézár-kerék „automatikusan biztosítja azt, hogy a belső kerék elforgatásakor az ábécé végén lévő betűk a külső kerék ábécéjének elején lévő betűk alá kerüljenek. A Cézár-féle monoalfabetikus helyettesítéshez egy igen célszerű matematikai modell is rendelhető, nevezetesen n karakteres ábécé esetén a modulo n összeadás (a kódolásnál) ill. a modulo n kivonás (a dekódolásnál).
21
Ehhez az kell, hogy az alkalmazott n karakteres ábécé minden karakteréhez monoton növekvő sorrendben 14 egy-egy számot rendeljünk 0-tól (n-1)-ig. 15 A nyílt szöveg titkosításakor a kulcsnak megfelelő egyetlen számot kell hozzáadni a nyílt szöveg aktuális karakterének a sorszámához s megkapjuk a kriptogram megfelelő karakterét. Ha az összeg nagyobb lenne n-nél, akkor ki kell belőle vonni n-et s így kapjuk meg a kriptogram aktuális karakterének a sorszámát. Használjuk pl. az előbbi cézár-keréknél is alkalmazott magyar ábécét és titkosítsuk az ABACUS szót úgy, hogy a titkosítási kulcs most a 9. sz. betű, azaz H. A nyílt szó
A
B
A
C
U
Sorszáma
0
2
0
3
25 23
A H kulcs
9
9
9
9
9
Az összeg
9 11 9 12 34 32
A mod 32 összeg 9 11 9 12 A kriptogram
H
Í
H
J
S 9
2
0
B
A
Dekódoláskor a mod 32 kivonás műveletét kell alkalmazni, azaz a kriptogram szöveg betűsorszámaiból kell kivonni a kulcsbetű sorszámát és ha negatív számot kapnánk eredményül, akkor ahhoz a modulust hozzá kell adni. Az adott példa esetében a következőképp: B
A
9 11 9 12
2
0
A H kulcs
9
9
9
9
9
9
A különbség
0
2
0
3
-7
-9
A kriptogram A betűk sorszámai
H
Í
H
J
A mod 32 különbség
9 11 9 12 25 23
A visszafejtett szöveg
A
B
A
C
U
S
A Cézár-féle helyettesítési titkosításnak számos változata van. Elegendő talán csak azt megemlíteni, hogy a kriptogram ábécé nem betűszimbólumokból is állhat és ha ugyanolyan betűkből áll is, mint a nyíltszöveg ábécé, akkor is más lehet a kriptogram ábécében a betűk sorrendje.
14
Elvileg nem kikötés, hogy a számsorrend monoton növekvő legyen, de mind az n karakterhez más-más szám kell, hogy tartozzék 0-tól (n-1)-ig. A monoton növekvő sorrendű számozás ezt biztosítja és pontosan megfelel a példában bemutatott, nem „kevert” ábécéjű Cézár-féle titkosításnak is.
15
Nagyon lényeges, hogy a számozást 0-tól kell kezdeni, mert –mint a Számítástechnika algebrai alapjai c. tárgyban kifejtettükegy műveletnek csak akkor van inverze, ha van egységeleme és a mod n additív műveletnek éppen 0 az egységeleme.
22
A példaként bemutatott eset a legegyszerűbb. Mivel itt 32 karakterből áll az ábécé, a két kerék is 32 féle elforgatási poziciót vehet fel. Láttuk, hogy a Cézár-féle titkosítás kulcsa a két kerék egymáshoz viszonyított poziciója. Mivel itt 32 pozíció lehetséges, ezért 32 kulcs létezik, amelyek közül a legelső nem is forgatja el egymáshoz képest a kereket, tehát nem is titkosít. Említettük már, hogy a nyers erő (brute force) módszerének nevezzük bármilyen kriptogram olyan feltörését, amikor egyszerűen végigpróbálgatjuk valamennyi lehetséges kulcsot. A bemutatott Cézár-féle titkosításnál (az adott 32 karakteres ábécét feltételezve) 32 féle kulcs létezik, amelyeket nagyon könnyen és gyorsan végig lehet próbálgatni. Ennek a titkosításnak tehát nagyon kicsi a kriptográfiai erőssége (= ellenállóképessége a feltörési kísérletek ellen), mert kicsi a kulcstér, azaz a lehetséges kulcsok száma. Ha figyelembe vesszük azt, hogy a kriptogram ábécében a betűk permutálhatók is, akkor nagyságrendekkel nagyobb ugyan a nyers erővel kipróbálandó lehetőségek száma, de a monoalfabetikus helyettesítéssel előállított titkos szöveg nem csak a nyers erő módszerével, hanem más úton-módon is feltörhető. Ezt mutatjuk be a következőkben. A monoalfabetikus helyettesítés egyik tulajdonsága (és egyúttal gyengesége is) az, hogy a nyílt szöveg ugyanazon betűjéhez a kriptogramban is mindig ugyanaz a betű tartozik. Egy beszélt nyelv (más szóval természetes nyelv) esetében a különböző betűk különböző gyakorisággal fordulnak elő. A magánhangzók gyakorisága pl. általában nagyobb, mint a legtöbb mássalhangzóé és sem a magánhangzókból sem a mássalhangzókból nem állhat túl sok egycsomóban, azaz a nyelv nem engedi meg a szélsőséges torlódásokat. Az ilyenfajta tulajdonságokat gyűjtőnéven a nyelv statisztikai tulajdonságainak nevezzük, amelyek jól kihasználhatók a kriptogram kulcs nélküli megfejtésénél, azaz feltörésekor. Ehhez persze tudni kell, hogy milyen nyelven írták azt a nyílt szöveget, amelynek a sifrírozott formája a kezünkben van. No és persze az sem közömbös, hogy rendelkezésünkre áll-e annyi szöveg, amennyiből már szignifikáns statisztikai következtetéseket tudunk levonni. Shannon képletet is adott az utóbbi kérdésre, azaz arra, hogy mennyi az a minimális szöveghossz, ami már elegendő a statisztikai elemzésre. (Erre majd később még kitérünk.) Itt elegendő annyit mondani, hogy kb. 200 betűt tartalmazó kriptogram már többnyire elegendő a sikeres statisztikai elemzésre a monoalfabetikus helyettesítéssel végzett titkosítások esetén, ha a nyílt szöveg nyelvezetének a statisztikai tulajdonságai ismertek.
23
Egészen pontosan négy dolgot kell (vagy kellene) tudnunk ill. ismernünk a kriptogram feltöréséhez: 16 1. A nyílt szöveg nyelvét, nyelvezetét. 17 2. A nyílt és a kriptogram ábécét 18 (amelyek nem feltétlenül azonosak, mint demonstrálni is fogjuk). 3. A nyílt szöveg nyelvére vonatkozó legfontosabb statisztikai adatokat 4. Elegendően hosszú és statisztikailag szignifikáns kriptogramot. (Erre mondtuk azt, hogy kb. 200 betűből álló kriptogram rendszerint elegendő.) Az alábbiakban feltételezzük a következőket I. A nyílt szöveg nyelve a magyar irodalmi nyelv. II. A nyílt szöveg ábécéje a már alkalmazott 32 betűs magyar ábécé a szóközzel kiegészítve, azaz a következőkben 33 karakteres nyílt ábécét tételezünk fel. A kriptogram ábécében azonban nem használunk szóközt, hanem a nyílt szöveg szóköz-karakterét a kriptogram ábécében valami olyan karakterrel helyettesítjük, ami a nyílt ábécében nem fordul elő. III. A betűgyakoriság és betűpár-gyakoriság adatokat Arany János Toldijának a szövegelemzéséből külön erre a célra készült programmal határozta meg e sorok írója. 19
16
Egy helyettesítési kriptogram feltörését demonstráló példa tanulságainak levonása után majd a 40. oldalon visszatérünk még arra, hogy a kriptoanalízis nagy doájenje, William F. Friedman szerint milyen műveletekre van szükség egy kriptogram feltöréséhez.
17
Nem elegendő azt tudni, hogy a nyílt szöveg nyelve pl. magyar, mert szignifikáns eltérések lehetnek a magyar irodalmi nyelv és egy mai újságszöveg nyelvezete között. Arany János irodalmi nyelve pl. nem használta a Q, W, X, betűket, de egy mai újságszövegben előfordulhatnak idegen nevek, amelyekben ezek a betűk is megtalálhatók és az Y sem csak a magyar irodalmi nyelv GY, LY, NY, TY betűpárjaiban található meg. Szélsőséges példa a játékos „eszprente” nyelvezet, amelyben az összes magánhangzó közül csak az E és az É fordul elő.
18
Ezt sem határozza meg egyértelműen a nyílt szöveg nyelve. A kriptogram ábécékben ugyan nem szokás számjegyeket szerepeltetni, hanem ehelyett szöveggel írják ki a számokat, és nem szokás a kis- és a nagybetűk megkülönböztetése sem. Egyáltalán nem mindegy azonban, hogy a szóköz előfordul-e a kriptogram ábécében vagy sem. Ennek az az oka, hogy bármelyik természetes nyelvben a szóköz gyakorisága messze a legnagyobb, ezért a kriptogram betűinek gyakoriságelemzésével nagyon könnyen meg lehet állapítani, hogy milyen karakter helyettesíti a szóközt. (Ld. alább.)
19
Az idegennynelvű szakirodalom nem csak a saját nyelvére, hanem más nyelvekre is megad ilyen statisztikákat. (Pl. [2] és [5]) Ismételten elkövetik azonban azt a hibát, hogy nem tesznek különbséget ugyanannak a betűnek az ékezetes és ékezet nélküli alakja között az előfordulási adatok meghatározásakor, pedig a magyarban pl. az A és az Á betű, vagy az E és az É betű egészen más hangalakot jelöl. (Itt azonban írott szövegekről van szó és nem a hangalakokról, ezt hangsúlyoznunk kell!) Az ékezetek elhagyása a szöveg jelentését is megváltoztathatja, ezért tartottuk fontosnak a statisztikák meghatározásakor az ékezetes és az ékezet nélküli betűk megkülönböztetését.
24
Lássuk először a magyar nyelv betűgyakoriság statisztikáit. A Toldi 1%-nál nagyobb betűgyakoriságai Sorrend Gyakoriság 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
Betű ASCII kódok
0,146 0,070 e 0,063 a 0,057 t 0,044 n 0,044 l 0,041 s 0,031 k 0,030 r 0,029 o 0,028 i 0,027 g 0,026 á 0,025 m 0,025 z 0,022 é 0,021 y 0,017 d 0,014 v 0,013 b 0,011 h 0,011 j 0,204 egyéb
32 101 97 116 110 108 115 107 114 111 105 103 225 109 122 233 121 100 118 98 104 106
1,000
2.1. táblázat Az elemzés a teljes Toldi 73603 karakterére terjed ki. 20 Az elemzésből kivettük a soremelés és hasonló vezérlő karaktereket valamint az írásjeleket. (A soremelés és a vessző gyakorisága is az első 25 karakter között szerepelne.) Az elemző program megkülönböztette a kis- és a nagybetűket. Az utóbbiak sem szerepelnek a fenti statisztikában. Figyelemre méltó, hogy a szóköz karakter (amelynek ASCII kódja 32) gyakorisága több mint kétszerese az utána következő legnagyobb gyakoriságú betűének, nevezetesen az e betű 7%-os gyakoriságának. Ezért is állítottuk korábban, hogy a monoalfabetikus helyettesítésnél nagyon egyszerűen megállapítható, hogy van-e a szóköz karaktert helyettesítő szimbólum a kriptogram ábécében.
20
A szöveget a Magyar Elektronikus Könyvtár internetes szolgáltatta.
25
Csak az érdekesség kedvéért megadjuk egy 34384 betűs újságszöveg (több cikk) egyes betűinek az előbbihez hasonló gyakoriság statisztikáját is. Egy 2002.nyári újságszöveg 1%-nál nagyobb betűgyakoriságai Sorrend Gyakoriság 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23.
Betű ASCII kódok
0,127 0,079 e 0,070 a 0,067 t 0,050 l 0,048 s 0,046 n 0,041 k 0,041 o 0,039 z 0,037 r 0,035 i 0,033 á 0,028 é 0,025 m 0,024 g 0,017 y 0,016 d 0,016 v 0,014 b 0,010 p 0,010 ó 0,126 egyéb
32 101 97 116 108 115 110 107 111 122 114 105 225 233 109 103 121 100 118 98 112 243
1,000
2.2. táblázat Ebben a táblázatban az y is bekerült az 1%-nál nagyobb gyakoriságú betűk listájába. Talán azért, mert a vizsgált újságszövegek egy olyan időszakból származtak, amikor sokszor fordult elő az újságokban y–ra végződő név.
26
A következőkben szükség lesz hosszabb karaktercsoportok gyakoriság statisztikáira is, ezért először táblázatosan megadjuk ezeknek a csoportoknak a szakirodalomban szokásos elnevezéseit, majd a Toldi betűcsoportjainak elemzése alapján a leggyakrabban előforduló betűpárok, majd az egy és kétbetűs magyar szavak gyakoriságait. 21
A karaktercsoport hossza (db.karakter)
Elnevezések
1
Szingli karakter, betüstatisztika, singleton
2
Karakterpár, duplet, digraph, bigraph
3
Karakterhármas, triplet, trigraph
4
Karakternégyes, quadruplet, tetragraph
5
5-ös karakterlánc, quintuplet, pentagraph
…
…
Sokbetűs karakterlánc
Polygraph,Betűtöbbes
2.3. táblázat Karakterláncok elnevezései Az idegennyelvű elnevezésekben a görög „gráf” szó előtt a karakterlánc hosszát jelentő görög számnevek állnak, az angolszász „tuple” 22 végződésű elnevezésekben pedig a név prefixuma a latin számnevekből származik. 21
Az előbbiek a szóköz-betű-szóköz karakterhármasok, az utóbbiak a szóköz-betű-betű-szóköz karakternégyesek gyakoriságait jelentik. Ugyanilyen válogatással megadhatók a szókezdő (szóköz-betű) betűk és a szóvégek (betű-szóköz ill. betű-pont vagy betű-vessző) statisztikái is, de ezekre itt nem térünk ki. Az [5] szakirodalom az angol szövegek statisztikai elemzésének mikéntjére számos példát és referenciát sorol fel, amelyek éppenséggel példát is adhatnának arra, hogy milyen elemzéseket kellene és lehetne a magyar szövegekkel kapcsolatban elvégezni.
22
A matematikai szakkifejezések körében olyan összetételekben használják mint pl. n-tuple, amit szám n-esnek fordítunk.
27
A 0,2%-nál nem kisebb relatív gyakoriságú betüpárok Arany János Toldijában Sorrend
%
ASCII kódok
Sorrend
%
Bigráf
ASCII kódok
1
1,22
ar
(97; 114)
58
0,28
ho
(104; 111)
0,39
ze
(122; 101)
59
0,27
sa
2
1,13
(115; 97)
3
0,93
4
0,87
31
0,39
ha
(104; 97)
60
0,27
ye
(121; 101)
32
0,38
ra
(114; 97)
61
0,27
ly
5
0,7
tt
(116; 116)
(108; 121)
33
0,38
ki
(107; 105)
62
0,26
lá
(108; 225)
6
0,68
eg
(101; 103)
34
0,38
ek
(101; 107)
63
7
0,67
te
(116; 101)
0,26
ad
(97; 100)
35
0,38
ve
(118; 101)
64
0,26
zt
(122; 116)
8
0,66
em
(101; 109)
36
0,37
nt
(110; 116)
65
9
0,62
et
(101; 116)
0,26
nd
(110; 100)
37
0,37
se
(115; 101)
66
0,26
st
10
0,56
ol
(111; 108)
(115; 116)
38
0,36
og
(111; 103)
67
0,25
la
(108; 97)
11
0,55
ne
(110; 101)
12
0,55
ak
(97; 107)
39
0,36
ke
(107; 101)
68
0,25
ét
(233; 116)
40
0,36
az
(97; 122)
0,24
ör
(246; 114)
13
0,54
me
14
0,53
an
(109; 101)
41
0,36
rt
(114; 116)
70
0,24
ed
(101; 100)
(97; 110)
42
0,35
on
(111; 110)
71
0,24
ko
(107; 111)
15
0,53
le
(108; 101)
43
0,35
be
(98; 101)
72
0,24
ég
(233; 103)
16
0,52
ny
(110; 121)
44
0,35
ár
(225; 114)
73
0,24
de
(100; 101)
17
0,52
mi
(109; 105)
45
0,35
va
(118; 97)
74
0,24
ma
(109; 97)
18
0,51
es
(101; 115)
46
0,34
án
(225; 110)
75
0,23
zé
(122; 233)
0,49
ta
(116; 97)
0,33
or
(111; 114)
0,23
ka
(107; 97)
20
0,49
na
(110; 97)
48
0,33
ik
(105; 107)
77
0,23
él
(233; 108)
21
0,48
al
(97; 108)
49
0,33
ja
(106; 97)
78
0,23
fe
(102; 101)
22
0,46
er
(101; 114)
50
0,32
ál
(225; 108)
79
0,22
di
(100; 105)
23
0,43
cs
(99; 115)
51
0,32
ér
(233; 114)
80
0,22
én
(233; 110)
24
0,43
lt
(108; 116)
52
0,31
is
(105; 115)
81
0,21
to
(116; 111)
25
0,42
át
(225; 116)
53
0,3
at
(97; 116)
82
0,21
ss
(115; 115)
26
0,41
in
(105; 110)
54
0,29
ot
(111; 116)
83
0,21
aj
(97; 106)
27
0,41
ag
(97; 103)
55
0,29
ll
(108; 108)
84
0,21
it
(105; 116)
28
0,4
re
(114; 101)
56
0,29
ba
(98; 97)
85
0,21
ás
(225; 115)
0,39
ar
(97; 114)
0,28
os
(111; 115)
0,2
zo
(122; 111)
19
29
Bigráf
ASCII kódok
Sorrend
%
sz
(115; 122)
29
0,39
gy
(103; 121)
30
el
(101; 108)
en
(101; 110)
47
57
Bigráf
69
76
86
2.4. táblázat A leggyakoribb betűpárok A betűpár-gyakoriságok nem azonosak a karakterpár-gyakoriságokkal. Ebből a táblázatból is kihagytuk a szövegformátum-vezérlő karakterpárokat, a szóköz és valamely betűpár kombinációját (ami szókezdetet vagy szóvéget jelent) és az írásjelek valamint valamely betűpár kombinációját. A statisztikában nem különböztettük meg a kis-és a nagybetűket sem. Valószínűsíthető, hogy az mi és a to betűpárok relatív gyakoriság adata nem szignifikáns, mert a Toldiban mind a Miklós, mind a Toldi szavak többször fordulnak elő, mint más szövegekben.
28
Egybetűs szavak a magyar irodalmi nyelvben: a (mint határozott névelő), az ő (mint személyes névmás), az s (mint az és kötőszó rövid alakja) és az ó valamint az á (mint indulatszavak) Ezek közül minden bizonnyal az a a leggyakoribb. Kétbetűs szavakból már sok van: az, is, és, de, ha, (a névelő és a kötőszavak a leggyakoribb kétbetűs szavak.) át, be, el, ki, le, rá, (határozószók ill. a ki kérdőszóként is) ad, ah, ád, ám, bá, ej, he, hé, hú, ím, ja, jé, na, ne, ni, no, óh, (mint indulatszavak), ál, ár, ás, bő, bú, eb, ez, ég, éj, él, ék, én,ép, ér, év, fa, fi, fő, fú, fű, hó, hő, hű, ír, ív, íz, jó, jő, kő, ló, lő, ma, mi, nő, oh, ok, ól, ón, óv, ők, ön, ős, öt, öv, őz, se, sí, só, rí, ró, te, tó, tő, tű, un, úr, út, ük, ül, üt, űr, űz, vő, A felsorolást a teljesség igénye nélkül közöljük azzal, hogy egy-egy szó gyakorisága jellemző lehet az adott szövegre is. A „ló” szó pl. a Toldiban nem is kis gyakorisággal előfordul, de a mai újságok szövegeiben szinte egyáltalán nem. Egyébként a Toldi szövegéből a 0,2%-nál nagyobb gyakoriságú betűpárok között az itt felsorolt kétbetűs szavakból csak 23 féle fordul elő, de azok sem feltétlenül önálló szóként, hanem egy-egy hosszabb szó részeként. A kérdőszavak csak akkor jelennek meg két szóköz között, ha nem áll közvetlenül utánuk kérdőjel, vagy –mint a titkosírásoknál gyakori- a mondatvéget jelző ponton és a vesszőn kívül más írásjeleket egyáltalán nem szoktak sifrírozni. Ugyanez áll az indulatszavakra is. Persze a nyíltszöveg nyelvére vonatkozó további ismeretek is segítik a megfejtést. A mondat elején álló kétbetűs szó nagy valószínűséggel az vagy ha (is, és és nem lehet), de a felsorolt többi kétbetűs szó közül szinte bármelyik. A mondottakból eléggé nyilvánvaló, hogy ha valamilyen módon sikerül a szóközöket azonosítani a kriptogramban, akkor a rövid szavak elég jó találgatási alapot nyújthatnak a megfejtéshez. Nem soroltunk fel a fentiek között olyan szakszavakat mint pl. a szolmizálásnál használtak. Más szakszövegeknek is lehetnek a szövegekre jellemző szakszavai.
Monoalfabetikus helyettesítési módszerrel titkosított szöveg feltörése 2.1 Példa A következőkben egy példát mutatunk be arra, hogy hogyan lehet egy monoalfabetikus helyettesítéssel titkosított szöveget a nyílt szöveg statisztikai adatainak (no és a titkosítás módjának) ismeretében megfejteni. Az adott esetben nem a Cézár-féle eltolásos helyettesítésről van szó, hanem arról, hogy a magyar ékezetes ábécé minden egyes betűjéhez egy-egy betűt rendelünk hozzá, de nem az ábécé eltolásával (mint a Cézár-féle helyettesítésnél), hanem úgy, hogy összekeverjük a nyílt szöveghez tartozó ábécé betűit és ezt a kevert sorrendű ábécét rendeljük hozzá kriptogram ábécéként a nyílt szöveg ábécéjéhez.
29
Mivel nem Cézár-féle (eltolásos) helyettesítésről van szó, a kulcstér sem csak 32 kulcsból áll, hanem annyi kulcsból, amennyi a lehetséges permutációk száma egy 32 betűs ábécénél, ami 32!, azaz igen nagy szám. Mindenesetre akkora, hogy nem igen van remény a nyers erővel való feltörés alkalmazására. A példával éppen azt szeretnénk demonstrálni, hogy egy ilyen reménytelennek látszó esetben sem nehéz egy monoalfabetikus helyettesítési kriptogram feltörése ha a nyelv és a módszer ismert és elegendően sok titkosított szöveg áll a rendelkezésünkre. (Mellesleg még néhány más dolgot is demonstrálunk majd a példával.) A feltörés az adott esetben nem csak a nyílt szöveg előállítását, hanem a titkosítás kulcsának a megállapítását is jelenti. A 24. oldalon felsorolt feltételek most teljesülnek. Nevezetesen: 1.
A nyílt szöveg nyelve magyar irodalmi nyelv.
2.
A nyílt ábécé a 32 betűs ékezetes magyar ábécé (amelyben –mint a titkosításnál szokás- nem különböztetjük meg a kis- és a nagybetűket és nem jelöljük az írásjeleket sem).
3.
A nyílt szövegre vonatkozó legfontosabb statisztikai adatokat az előzőleg közölt 2.1. és 2.4. táblázatok, valamint az előzőekben megadott szógyakoriságok jelentik.
4.
A megadott titkosított szöveg (kriptogram)a következő:
ÚÁSDR ÍRHJR XUMXT ZXDGS HJXEA UHÉLG XÜRÉR ÉÁEÁÉ XÖÜZÜ JXÍUV ŰRÉXU XVGSO ÖHÖS
RTXUX OTÉXL OŰGSÉ ÉXGSJ AÖÜUX GXUXL ÓÜHÉX ÉXUÜS ÜSZGL GHXÓÜ MXÁER ÖÉXDT
NUYHU XRSÉU HUÓXÚ XÓTHJ NGOJX MROTH ÚTSLM UÓGHX ÉXSÖÉ HHXLR OXLMG OMÜXY
SXÍÜE ÓUEÉU RSTÉX RLXUX ÜRXHR JXÖLÖ RZZRS NÖÉXÖ YUXÜR ZXSÖÉ SOÖHÖ KXEÜO
GLXÓÁ XDRSR VRXHR ŰÖELG XÍÜSS EVÖÜU XROJX LUÓXU HHXRO XROJR SXUÓÜ KXSGD
2.5. táblázat a 2.1 példa kriptogramja Az ötbetűs karaktercsoportok utáni szóközöknek az égadta világon semmi jelentőségük nincs, mármint a megfejtés szempontjából. Csak azért vannak beiktatva, hogy az egyébként zavaróan áttekinthetetlen karakterlánc mégis csak valamilyen módon rendezett legyen.
30
A korábban állítottak szerint kb. 200 karakternek elegendőnek kell lennie ahhoz, hogy a kriptogramot egyértelműen megfejthessük. Most több, mint 300 karakter áll rendelkezésre, tehát minden bizonnyal elegendően sok ahhoz, hogy szignifikáns statisztikai megállapításokat tehessünk. Alább majd összefoglaljuk azt is, hogy ilyen esetekben milyen receptet lehet adni a megfejtésre, de azt már most állíthatjuk, hogy nagy könynyebbséget jelentene, ha a kriptogramban a nyílt szöveg szóközeit is kódolták volna s ezt meg tudnánk állapítani. Nos, a 2.1. táblázat eléggé egyértelműen mutatja, hogy a szóközök relatív gyakorisága csaknem kétszer akkora, mint a legnagyobb gyakoriságú betűké és a betűgyakoriságok között nincs nagy százalékos eltérés. Mivel majdnem 300 kriptogram karakterünk van érdemes gyakoriság-elemzést végezni. Ennek az eredménye az adott példánál a következő: Sorrend
%
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
15,00 12,22 6,67 5,83 5,83 5,56 5,00 3,61 3,33 3,33 3,33 2,78 2,50 2,22 2,22 2,22
Karakter ASCII X R S U H É G L O Ö Ű J T E Ó
32 88 82 83 85 72 201 71 76 79 214 219 74 84 69 211
Sorren d
%
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
2,22 1,67 1,67 1,67 1,67 1,39 1,39 1,11 1,11 1,11 0,83 0,83 0,83 0,56 0,28
Karakter ASCII Ü Á Z D M
N Í V Ú Y Ő K A
220 193 90 68 77 13 10 78 205 86 218 89 213 75 65
2.6. táblázat A megadott kriptogram betűgyakoriságai
Legnagyobb gyakoriságú a (32) ASCII kódú szóköz karakter (15,00%), de – mint mondtuk már– a megfejtés szempontjából ennek itt semmi jelentősége sincs. 23 A következő legnagyobb gyakoriságú (12,22%) karakter az X karakter. Ráadásul az ezt követő legnagyobb gyakoriságú karakter az R (6,67%), ami23
Nem biztos, hogy a kriptogram szóköz karakterének a gyakorisága mindig a legnagyobb (különösen nagyon rövid kriptogramok esetében), de azt mindig feltétezhetjük, hogy (ha a kriptogram pl. ötbetűs csoportokba van rendezve) a szóköz karaktert és annak a gyakoriságát egyszerűen kihagyhatjuk az elemzésből.
31
nek a gyakorisága csaknem a fele az X karakterének. Joggal feltételezhetjük tehát, hogy a titkosításkor a szóközöket is titkosították s a szóköz jele a kriptogram ábécében éppen az X. Ez a továbbiakban igen nagy könnyítést jelent. Használjuk ki mindjárt ezt a felismerést és bontsuk szavakra a kriptogramot a szóközökkel. Egyúttal meg is számozzuk a szavakat, hogy a következőkben hivatkozni tudjunk rájuk.
1 2 3 4 5 ÚÁSDRDT U NUYHUS ÍÜEGL ÓÁÍRHJROTÉ
6 7 L RSÉUÓUEÉU
8 9 10 11 12 13 14 15 16 DRSR UM TOŰGSÉHUÓ ÚRSTÉ VR HRZ DGSÉ GSJ ÓTHJRL 17 18 19 20 21 22 23 24 25 U ŰŐELGHJ EANÖŰU NGOJ ŰR HR ÍÜSSUHÉLGH U LMROTHJ 26 ŐLÖEVÖŰU
27 28 29 30 ÜRÉRÓŰHÉ ÚTSLMRZZRS ROJ ÉÁEÁÉÉ
31 32 UÜSUÓGH NÖÉ
33 34 35 36 37 38 ÖLUÓ U ÖÜZÜÜSZGLÉ SÖÉYU ŰRHH ROJ
39 40 41 42 43 44 45 46 ÍUVVH ÓÜHH LRZ SÖÉ ROJRŰRÉ UM ÁERO LMGSOÖHÖS 47 48 49 50 51 52 UÓÜ VGSOÖE DTOMÜ YK EÜOK SGDÖHÖS A kriptogram betűstatisztikája szerint a szóköz karakter utáni leggyakoribb betű az R. Valószínűsíthető, hogy ez a nyílt szöveg e betűjének felel meg, tehát R → e A kriptogramot szemrevételezve látjuk azt is, hogy egybetűs szavakból mindössze kétféle van: U (2, 17, 24, 34,) és L (6,) Valószínűsíthető tehát az U → a helyettesítés is. Írjuk be ezeket a kriptogram táblázatába:
1 2 3 4 5 ÚÁSDRDT U NUYHUS ÍÜEGL ÓÁÍRHJROTÉ e a a e e
6 7 L RSÉUÓUEÉU e a a a
8 9 10 11 12 13 14 15 16 DRSR UM TOŰGSÉHUÓ ÚRSTÉ VR HRZ DGSÉ GSJ ÓTHJRL e e a e e e e
32
17 18 19 20 21 22 23 24 25 U ŰŐELGHJ EANÖŰU NGOJ ŰR HR ÍÜSSUHÉLGH U LMROTHJ a a e e a a e 26 27 28 29 30 ŐLÖEVÖŰU ÜRÉRÓŰHÉ ÚTSLMRZZRS ROJ ÉÁEÁÉÉ a e e e e e 31 32 33 34 35 36 37 38 UŰSUÓGH NÖÉ ÖLUÓ U ŐÜZŰUSZGLÉ SÖÉYU ŰRHH ROJ a a a a a a e e 39 40 41 42 43 44 45 46 ÍUVGH ÓÜHH LRZ SÖÉ ROJRŰRÉ UM ÁERO LMGSOÖHŐS a e e e e a e 47 48 49 50 51 52 UÓÜ VGSOÖE DTOMü YK EÜOK SGDÖHÖS a
A nyílt szöveg gyakoriságtáblája (2.1 táblázat) alapján az e betűt az a és a t valamint az n és az l betűk gyakorisága követi. A kriptogram gyakoriságtáblájában (2.6 táblázat) az U,S, H, É következik. 24 Esetünkben azonban a nyílt szöveg a betűjének megfelelő U betűt már azonosítottuk. Így az S, H, É kriptogram betűket kellene kipróbálni a t helyetteseként. A magyar nyelvben a tárgyragok és a múlt idő ragjai miatt a szóvégi t gyakori. Vizsgáljuk meg a szöveget abból a szempontból, hogy az S, H, É betűk közül melyik fordul elő legggyakrabban a szóvégeken. Nos ez az É betű (5, 11, 14, 27, 30, 32, 35, 42, ) A 30. szóban ráadásul kettőzve. Igaz, hogy nem nagyon valószínű, hogy a mindössze három betűs 32. szóban múlt idót jelentene vagy tárgyrag lenne. Mégis jó tippnek látszik az É → t helyettesítés. 25 Látható az is, hogy az UM (9. és 44.) kétbetűs szavak a-val kezdődnek, tehát feltételezhetjük, hogy ezek az az határozott névelőt jelölik, azaz megtippelhető az M → z helyettesítés is. A 6. egybetűs szót pedig az és kötőszó s rövid alakjának tippeljük, azaz L→s Egyébként minden ilyen helyettesítési tipp csak becslés, ami vagy bejön, vagy nem. Ki kell próbálni. Sajnos a megoldás során bizony előfordulnak téves tippek is, s akkor onnan kell folytatni, ahol még jónak (vagy legalább is elfogadhatónak) látszott az utolsó behelyettesítési változat.
24
A statisztikai adatok természetüknél fogva szóródnak. Ezért nem lehet elvárni, hogy egy szövegrészlet statisztikája legalább sorrendben kövesse egy nagyobb adathalmaz statisztikáját.
25
A nyílt szöveg betűinek gyakoriságtáblázata szerint az ábécé leggyakrabban előforduló nyolc betűje teszi ki a nyílt szöveg 38%-át. ( e, a, t, n, l, s, k, r) Ha tehát ezeket sikerül azonosítani, akkor a kriptogramnak csaknem a 40%-át már megfejtettük s könnyebb lelet a még hiányzó betűket kitalálni.
33
A helyettesítő tippek kipróbálásakor a már meglévő nyílt szöveg betűkkel létrejöhetnek olyan kombinációk is, amelyek a természetes nyelvben nem fordulhatnak elő. Az ilyesmik jelzik pl. a tévutat. Végezzük el a fentiekben megtippelt két újabb helyettesítést!
1 2 3 4 5 ÚÁSDRDT U NUYHUS ÍÜEGL ÓÁÍRHJROTÉ e a a a e e t
6 7 L RSÉUÓUEÉU s e ta a ta
8 9 10 11 12 13 14 15 16 DRSR UM TOŰGSÉHUÓ ÚRSTÉ VR HRZ DGSÉ GSJ ÓTHJRL e e az é e t e e t es 17 18 19 20 21 22 23 24 25 U ŰŐELGHJ EANÖŰU NGOJ ŰR HR ÍÜSSUHÉLGH U LMROTHJ a s a e e a ts a sze 26 27 28 29 30 ŐLÖEVÖŰU ÜRÉRÓŰHÉ ÚTSLMRZZRS ROJ ÉÁEÁÉÉ s a ete sze e e t tt 31 32 33 34 35 36 37 38 UŰSUÓGH NÖÉ ÖLUÓ U ŐÜZŰUSZGLÉ SÖÉYU ŰRHH ROJ a a t sa a a st t a e e 39 40 41 42 43 44 45 46 ÍUVGH ÓÜHH LRZ SÖÉ ROJRŰRÉ UM ÁERO LMGSOÖHŐS a se t e e et az e sz 47 48 49 50 51 52 UÓÜ VGSOÖE DTOMÜ YK EÜOK SGDÖHÖS a z Az M → z tippet a 25. 28. és 46. szavak sz betűi alátámasztják (bár a helyességét nem bizonyítják). A betűgyakoriságok annál kevésbé adnak támpontot, minél kisebb gyakoriságú betűkről van szó. Elvileg jó becslésekre vezethetnek a rövid szavak (mint pl. 12. 21. 22. kétbetűs, vagy az 50. ill. 13. 15. 29. 32. 38. 41. 42. 47. hárombetűs szavak). Sajnos a kétbetűs szavakkal itt nem megyünk sokra mert amelyeknek egyik betűje már megvan (21. és 22.) azok több kétbetűs szót is jelenthetnek. (Ld. a 28. oldalon felsoroltakat.) A legrosszabb esetben, persze, mind ki lehet próbálni. A hárombetűs szavak között azonban vannak olyanok, amelyek új tippeket sugallanak: A 13. HRZ szó pl. a sem szót. Sajnos ez tévút. A 29. és a 38. szavak, s ráadásul a 43. szó eleje (ROJ) pl. az egy szót sugallja, ami elég gyakori a magyarban. Ebből O → g és J → y. (Az utóbbi helyettesítés nyilvánvaló ellentmondásra vezet, ha a már meglévő betűk közül olyan betűt követ az y, amelyet a nyelv szabályai szerint nem követhet.)A 41. szó (LRZ) pedig a sem szót sugallja, tehát Z → m.
34
Ezeket behelyettesítve
1 2 3 4 5 ÚÁSDRDT U NUYHUS ÍÜEGL ÓÁÍRHJROTÉ e a a a s e yeg t
6 7 L RSÉUÓUEÉU s e ta a ta
8 9 10 11 12 13 14 15 16 DRSR UM TOŰGSÉHUÓ ÚRSTÉ VR HRZ DGSÉ GSJ ÓTHJRL e e az g é e t e em t y yes 17 18 19 20 21 22 23 24 25 U ŰŐELGHJ EANÖŰU NGOJ ŰR HR ÍÜSSUHÉLGH U LMROTHJ a s y a gy e e a ts a szeg y 26 27 28 29 30 ŐLÖEVÖŰU ÜRÉRÓŰHÉ ÚTSLMRZZRS ROJ ÉÁEÁÉÉ s a ete t szemme egy t tt 31 32 33 34 35 36 37 38 UŰSUÓGH NÖÉ ÖLUÓ U ŐÜZŰUSZGLÉ SÖÉYU ŰRHH ROJ a a t sa a m a m st t a e egy 39 40 41 42 43 44 45 46 ÍUVGH ÓÜHH LRZ SÖÉ ROJRŰRÉ UM ÁERO LMGSOÖHŐS a sem t egye et az eg sz g 47 48 49 50 51 52 UÓÜ VGSOÖE DTOMÜ YK EÜOK SGDÖHÖS a g z g A kriptogramban gyakori betű még a H. A 13. szó alapján tippeljük meg a H → n helyettesítést. Ezt a becslést támogatja az is, hogy az 5. és a 25. szóban így ny-et ad a már meglévő y-nal. A 25. szó viszont egyértelműen mutatja a T → é helyettesítést.
1 2 3 4 5 ÚÁSDRDT U NUYHUS ÍÜEGL ÓÁÍRHJROTÉ e é a a na s enyegét
6 7 L RSÉUÓUEÉU s e ta a ta
8 9 10 11 12 13 14 15 16 DRSR UM TOŰGSÉHUÓ ÚRSTÉ VR HRZ DGSÉ GSJ ÓTHJRL e e az ég tna e ét e nem t y ényes 17 18 19 20 21 22 23 24 25 U ŰŐELGHJ EANÖŰU NGOJ ŰR HR ÍÜSSUHÉLGH U LMROTHJ a s ny a gy e ne ants n a szegény 26 ŐLÖEVÖŰU s a
27 28 29 30 ÜRÉRÓŰHÉ ÚTSLMRZZRS ROJ ÉÁEÁÉÉ ete nt é szemme egy t tt
35
31 32 UŰSUÓGH NÖÉ a a n t
33 34 35 36 37 38 ÖLUÓ U ŐÜZŰUSZGLÉ SÖÉYU ŰRHH ROJ sa a m a m st t a enn egy
39 40 41 42 43 44 45 46 ÍUVGH ÓÜHH LRZ SÖÉ ROJRŰRÉ UM ÁERO LMGSOÖHŐS a n nn sem t egye et az eg sz g n 47 48 49 50 51 52 UÓÜ VGSOÖE DTOMÜ YK EÜOK SGDÖHÖS a g t égz g n A nyílt szöveg betűinek gyakoriságtáblájában (2.1 táblázat) a leggyakrabban előforduló betűket összesen 23 %-os gyakorisággal követi az l, s, k, r, o, i, és g, betűk csoportja. Ezek közül már megtaláltuk az l-et és az s-et, de a többit még nem. Ugyanakkor e betűk gyakoriság adatai elég kicsik (2,7 – 3,1%) és elég közel is esnek egymáshoz s ezért itt már nem igen segít az egyes betűk relatív gyakoriságának a táblázata. Vagy elő kell szedni azt, hogy melyik betű mely másik betűkkel szokott gyakrabban előfordulni, vagy az eddigieknél „bátrabb” szó-találgatásokat kipróbálni. Tekintettel arra, hogy nem szándékozunk mélyebben és részletesebben foglalkozni a megfejtések módszereivel, maradjunk az utóbbinál, vagyis a szó-találgatásoknál és vizsgáljuk meg rendre, hogy nem vezetnek-e a megtippelt helyettesítések ellentmondásokra, vagy fonetikai összeférhetetlenségre. A 20. szó pl. lehet az elég gyakori hogy kötőszó, s ebből N → h és G → o következik. Próbáljuk ki, hogy nem vezet-e összeférhetetlenségre másutt.
1 2 3 4 5 ÚÁSDRDT U NUYHUS ÍÜEGL ÓÁÍRHJROTÉ e é a ha na os enyegét
6 7 L RSÉUÓUEÉU s e ta a ta
8 9 10 11 12 13 14 15 16 DRSR UM TOŰGSÉHUÓ ÚRSTÉ VR HRZ DGSÉ GSJ ÓTHJRL e e az ég o tna e ét e nem o t o y ényes 17 18 19 20 21 22 23 24 25 U ŰŐELGHJ EANÖŰU NGOJ ŰR HR ÍÜSSUHÉLGH U LMROTHJ a s ny h a hogy e ne antson a szegény 26 ŐLÖEVÖŰU s a
27 28 29 30 ÜRÉRÓŰHÉ ÚTSLMRZZRS ROJ ÉÁEÁÉÉ ete nt é szemme egy t tt
31 32 UŰSUÓGH NÖÉ a a on h t
33 34 35 36 37 38 ÖLUÓ U ŐÜZŰUSZGLÉ SÖÉYU ŰRHH ROJ sa a m a most t a enn egy
36
39 40 41 42 43 44 45 46 ÍUVGH ÓÜHH LRZ SÖÉ ROJRŰRÉ UM ÁERO LMGSOÖHŐS a on nn sem t egye et az eg szo g n 47 48 49 50 51 52 UÓÜ VGSOÖE DTOMÜ YK EÜOK SGDÖHÖS a o g t égz g o n A 40. szó (ÓÜHH) dupla n-nel végződik és lehetne a gyakori kinn, benn, lenn, fenn határozók bármelyike, de a második betűje nem lehet e, mert azt a kriptogramban az R helyettesíti. Próbáljuk meg hát a kinn helyettesítést, azaz Ó → k és Ü → i 26
1 2 3 4 5 ÚÁSDRDT U NUYHUS ÍÜEGL ÓÁÍRHJROTÉ e é a ha na i os k enyegét
6 7 L RSÉUÓUEÉU s e taka ta
8 9 10 11 12 13 14 15 16 DRSR UM TOŰGSÉHUÓ ÚRSTÉ VR HRZ DGSÉ GSJ ÓTHJRL e e az ég o tnak e ét e nem o t o y kényes 17 18 19 20 21 22 23 24 25 U ŰŐELGHJ EANÖŰU NGOJ ŰR HR ÍÜSSUHÉLGH U LMROTHJ a s ny h a hogy e ne i antson a szegény 26 ŐLÖEVÖŰU s a
27 28 29 30 ÜRÉRÓŰHÉ ÚTSLMRZZRS ROJ ÉÁEÁÉÉ etekint é szemme egy t tt
31 32 UŰSUÓGH NÖÉ a akon h t
33 34 35 36 37 38 ÖLUÓ U ŐÜZŰUSZGLÉ SÖÉYU ŰRHH ROJ sak a im a most t a enn egy
39 40 41 42 43 44 45 46 ÍUVGH ÓÜHH LRZ SÖÉ ROJRŰRÉ UM ÁERO LMGSOÖHŐS a on kinn sem t egye et az eg szo g n 47 48 49 50 51 52 UÓÜ VGSOÖE DTOMÜ YK EÜOK SGDÖHÖS aki o g t égzi ig o n
26
A magyar ékezetes betűk esetében zavaró, hogy néhány fontkészlet ne jól, vagy egyáltalán nem különbözteti meg a rövid és a hosszú ékezetes betűket.. Az itt bemutatott helyettesítési táblázatokban pl. Courier betűtipust használtunk, hogy minden betű ugyanakkora helyet foglaljon el és pontosan egymás alá ill. fölé legyenek illeszthetőek. Ez a betűtipus azonban nem tesz különbséget a rövid és a hosszú Ü – Ű betűk között. Erre külön ügyelni kell. Ittt a táblázatban, ahol éppen a rövid Ü betűt helyettesítjük, a hosszú Ű betűket aláhúzással is megkülönböztettük. Ugyanezt tesszük alább a hosszú Ő megkülönböztetésére.
37
A 7. szóból csak két betű hiányzik és feltételezzük hogy az S → l és E → r helyettesítések beválhatnak. Mellesleg a kriptogram gyakoriságtáblázatában az S és az E gyakorisága 5,56% ill. 2,12%, a nyílt ábécé 2.1 gyakoriság táblázatában pedig az l ill. az r gyakorisága 4,4% ill. 3%. Az eltérés tehát éppen elég ahhoz, hogy eltájoljon bennünket (de ne hagyjuk. Mint említettük már, a kisebb és egymástól nem jelentősen eltérő gyakoriságú betűk esetében a statisztikai gyakoriságok már nem adnak releváns információt). Ha az S → l helyettesítés beválik, akkor a 8. szó alapján joggal feltételezhetjük, hogy a D → v helyettesítés is megfelel. Próbáljuk ki!
1 2 3 4 5 ÚÁSDRDT U NUYHUS ÍÜEGL ÓÁÍRHJROTÉ lvevé a ha nal iros k enyegét
6 7 L RSÉUÓUEÉU s eltakarta
8 9 10 11 12 13 14 15 16 DRSR UM TOŰGSÉHUÓ ÚRSTÉ VR HRZ DGSÉ GSJ ÓTHJRL vele az ég oltnak elét e nem volt oly kényes 17 18 19 20 21 22 23 24 25 U ŰŐELGHJ EANÖŰU NGOJ ŰR HR ÍÜSSUHÉLGH U LMROTHJ a rs ny r h a hogy e ne illantson a szegény 26 ŐLÖEVÖŰU s r a
27 28 29 30 ÜRÉRÓŰHÉ ÚTSLMRZZRS ROJ ÉÁEÁÉÉ etekint élszemmel egy t r tt
31 32 UŰSUÓGH NÖÉ a lakon h t
33 34 35 36 37 38 ÖLUÓ U ŐÜZŰUSZGLÉ SÖÉYU ŰRHH ROJ sak a im almost l t a enn egy
39 40 41 42 43 44 45 46 ÍUVGH ÓÜHH LRZ SÖÉ ROJRŰRÉ UM ÁERO LMGSOÖHŐS a on kinn sem l t egye et az reg szolg n l 47 48 49 50 51 52 UÓÜ VGSOÖE DTOMÜ YK EÜOK SGDÖHÖS aki olg t végzi rig lov n l További szó-kiegészítési tippek: 3: hajnal;
Y → j és E → r
4: piros;
í→p
10: égboltnak; 27: betekint 31: ablakon; Ű → b 11: felét; 28: félszemmel;
Ú→f
32: hát;
Ö→á
38
Ezeket is behelyettesítve:
1 2 3 4 5 ÚÁSDRDT U NUYHUS ÍÜEGL ÓÁÍRHJROTÉ f lvevé a hajnal piros k penyegét
6 7 L RSÉUÓUEÉU s eltakarta
8 9 10 11 12 13 14 15 16 DRSR UM TOŰGSÉHUÓ ÚRSTÉ VR HRZ DGSÉ GSJ ÓTHJRL vele az égboltnak felét e nem volt oly kényes 17 18 19 20 21 22 23 24 25 U ŰŐELGHJ EANÖŰU NGOJ ŰR HR ÍÜSSUHÉLGH U LMROTHJ a b rs ny r hába hogy be ne pillantson a szegény 26 ŐLÖEVÖŰU sár ba
27 28 29 30 ÜRÉRÓŰHÉ ÚTSLMRZZRS ROJ ÉÁEÁÉÉ betekint félszemmel egy t r tt
31 32 UŰSUÓGH NÖÉ ablakon hát
33 34 35 36 37 38 ÖLUÓ U ŐÜZŰUSZGLÉ SÖÉYU ŰRHH ROJ sak a imbalmost látja benn egy
39 40 41 42 43 44 45 46 ÍUVGH ÓÜHH LRZ SÖÉ ROJRŰRÉ UM ÁERO LMGSOÖHŐS padon kinn sem lát egyebet az reg szolgánál 47 48 49 50 51 52 UÓÜ VGSOÖE DTOMÜ YK EÜOK SGDÖHÖS aki olgát végzi j rig lovánál További szó-kiegészítési tippek: 1: fölvevé;
Á→ö
12: de;
V→d
18: bársony;
G→o
33: csak;
Ő→c
1 2 3 4 5 ÚÁSDRDT U NUYHUS ÍÜEGL ÓÁÍRHJROTÉ fölvevé a hajnal piros köpenyegét
6 7 L RSÉUÓUEÉU s eltakarta
8 9 10 11 12 13 14 15 16 DRSR UM TOŰGSÉHUÓ ÚRSTÉ VR HRZ DGSÉ GSJ ÓTHJRL vele az égboltnak felét de nem volt oly kényes 17 18 19 20 21 22 23 24 25 U ŰÖELGHJ EANÖŰU NGOJ ŰR HR ÍÜSSUHÉLGH U LMROTHJ a bársony r hába hogy be ne pillantson a szegény
39
26 ŐLÖEVÖŰU csárdába
27 28 29 30 ÜRÉRÓŰHÉ ÚTSLMRZZRS ROJ ÉÁEÁÉÉ betekint félszemmel egy törött
31 32 UŰSUÓGH NÖÉ ablakon hát
33 34 35 36 37 38 ÖLUÓ U ŐÜZŰUSZGLÉ SÖÉYU ŰRHH ROJ csak a cimbalmost látja benn egy
39 40 41 42 43 44 45 46 ÍUVGH ÓÜHH LRZ SÖÉ ROJRŰRÉ UM ÁERO LMGSOÖHŐS padon kinn sem lát egyebet az öreg szolgánál 47 48 49 50 51 52 UÓÜ VGSOÖE DTOMÜ YK EÜOK SGDÖHÖS aki dolgát végzi j rig lovánál Összesen három szóban hiányzik még egy-egy betű, de nem nehéz kitalálni, hogy ezeket a: K → ó, ill. az A → u helyettesítések adják meg. Kiegészítve a megfejtést írásjelekkel, nagybetűkkel pótolva a kisbetűket ahol kell, kapjuk a következő megfejtést: Fölvevé a hajnal piros köpenyegét, S eltakarta vele az égboltnak felét, De nem volt oly kényes a bársony ruhába', Hogy be ne pillantson a szegény csárdába. Betekint félszemmel egy törött ablakon, Hát csak a cimbalmost látja benn egy padon, Kinn sem lát egyebet az öreg szolgánál, Aki dolgát végzi jó Rigó lovánál. (Arany János: Toldi 11. ének 1.) A nyílt és a kriptogram ábécé egymáshozrendelése pedig a megtippelt és a próbáknál ellentmondásmentesnek bizonyult helyettesítések összefoglalása, azaz a következő: a
l
m
X U Ö Ű Ő V R T Ú O N Ü P Y Ó S
Z
n
o
á
b
c
d
ó ö ő p
H G K Á C
Í
e
r
é
s
f
t
g
h
i
í
u ú ü ű
E L É A F
I
j
k
v x y
B D
z
J M
40
A reciprocitás elve Némi vizsgálódással feltűnik, hogy tulajdonképpen csak a nyílt szöveg ábécé első feléhez (a szóköztől m-ig) vannak véletlenszerűen hozzárendelve a kriptogram ábécé (második felének) a betűi. A kriptogram ábécé mintegy tükörképe a nyílt ábécének. Ezt a tulajdonságot reciprocitásnak nevezik és az adott példánál szándékosan alkalmaztuk a nyílt és a kriptogram ábécé ilyen egymáshoz-rendelését. Ha az ábécék páratlan számú karaktert tartalmaztak volna, akkor lett volna olyan betű, amelynek a helyettesítő karaktere saját maga. Ez nem tiltott. A reciprocitás elve lehetővé teszi, hogy a kódoló és a dekódoló algoritmus gyakorlatilag (majdnem) azonos legyen. Ezért a harmadik, sőt a negyedik generációs rendszerekben is alkalmazták ill. alkalmazzák a reciprocitás elvét. A harmadik generációs (rotoros) titkosító gépek közül pl. az Enigma lehetővé tette, hogy ugyanazzal a géppel és beállítással mind kódolni, mind megfejteni lehessen ugyanazt az üzenetet. Ugyanakkor az Enigmánál gondoskodtak arról, hogy kódoláskor a nyílt szöveg egyetlen betűje se’ maradjon változatlanul. Ez azonban nem erősítette a titkosítást, hanem éppenséggel gyengéje volt az Enigmának. A reciprocitás elvét a negyedik generációs modern kriptorendszerekben is alkalmazták és alkalmazzák ma is. Lényegében ugyanazon okból, mint az Enigmánál. A működési sebesség növelése céljából ugyanis általában nem szoftverrel valósítják meg a kódolást és a dekódolást, hanem külön erre a célra való hardvert építenek. 27 A feltörés „receptje” Jóllehet a bemutatott példa ( a betűstatisztikák alkalmazásától eltekintve) inkább azt sugallja, hogy a kriptogram feltörése inkább rejtvényfejtéshez hasonlít mintsem valamilyen módszeres tevékenységhez, mégis csak összefoglalható, hogy mi is a feltörés „receptje”. 28 A következő, pontokba foglalt eljárás a monoalfabetikus helyettesítéssel előállított kriptogramok feltörésekor alkalmazható.
27
A célhardverekkel legalább 100-szoros sebességnövelés érhető el, de ez magától a kriptorendszertől ill. a titkosítási módszertől is erősen függ. Az azonban minden rendszerre igaz, hogy a célhardver sokkal gyorsabb, mint az általános célú számítógépen futtatott titkosító program.
28
Erről azért annyit, hogy nem egy „recept” van, hanem nagyon sokféle fogás, amelyek közül azt kell alkalmazni, ami az adott eset adott lépésében éppen a legmegfelelőbb. Végül is ezt teszik a rejtvényfejtők is. A feltöréshez alkalmazható módszer természetesen erősen függ attól, hogy milyen módszerrel titkosították az adott kriptogramot.
41
1. Határozzuk meg a kriptogramban előforduló betűk gyakoriságait. (Ezt tettük a 2.6 táblázat kiszámításakor is.) 2. Kiséreljük meg meghatározni, hogy a kriptogramban melyik karakter felel meg a nyílt szöveg szóköz karakterének, ha egyáltalán kódolták azt. 29 Ha a kriptogram nem nagyon rövid, és a szóközt is kódolták, akkor könnyű megtalálni a neki megfelelő karaktert, mert egy természetes nyelvű szöveg 30 karaktereinek mintegy 40%-a szóköz és írásjel, de a 40% túlnyomó többségét a szóközök teszik ki. Ráadásul a szóköz karaktereknek nem nagy távolságra kell követniük egymást, mert a természetes nyelvek szóhosszai azért korlátozottak. A szóköz karakterek relatív gyakorisága kb a duplája az leggyakrabban előforduló betű gyakoriságának, tehát a statisztikai eltérés nagyon is szignifikáns. 3. Miután azonosítottuk a szóköz karaktert írjuk át a kriptogramot úgy, hogy szavakra tördeljük. Az így átírt kriptogram pontosan olyan hoszszú szavakból fog állni, amilyenek a nyílt szövegben vannak és pontosan ugyanolyan sorrendben is követik egymást a szavak. Nem árt a szavakat megszámozni, mint ahogyan a példában is tettük. (Ott a hivatkozások és a demonstráció kedvéért, de a megfejtés közben is könnyebben készíthetünk jegyzeteket, ha megszámoztuk a szavakat.) 4. Törekedjünk arra, hogy meghatározzuk a kriptogramban a nyílt szöveg legnagyobb gyakoriságú betűit helyettesítő karaktereket. Ezek teszik ki a teljes szöveg mintegy 30-40%-át. A betűgyakoriság táblázatok segítenek ugyan ebben is, de a statisztikai természetük miatt szórnak és egyáltalán nem biztos, hogy a kriptogramban is ugyanaz lesz a betűgyakorisági sorrend, mint abban a nyíltszöveg-ábécé gyakorisági táblázatban, amellyel dolgozunk. A ritka betűknél pl. gyakorlatilag semmilyen segítséget sem jelent a betűgyakoriság táblázat. 31 5. Ha már vannak megfejtett szó-részleteink, akkor vegyük vizsgálat alá a rövid (két- vagy hárombetűs, az adott nyelvben gyakori) szavakat. A bemutatott példában az egybetűs szavak vizsgálata meg is előzte az előző pontbeli gyakoriságvizsgálatot és sikeresen azonosítani is tudtuk az a határozott névelőt. (Az utóbbi segítségével pedig az az névelőt.) A példában egyébként a többi kétbetűs szó nem sokat segített, mert csak a második betűiket sikerült először megtalálni (és a magyarban jónéhány e-re végződő kétbetűs szó van). Érdemes vizsgálni a gyakori szóvégződéseket is. (A példában pl. a t betű azonosításában segített ez a megközelítés.) 6. A megoldás teljessé tételekor vegyük tekintetbe a nyelv grammatikai szabályait is és a szöveg jellegét, jelentését is.
29
Ha nem, akkor a helyzet nehezebb és feltétlenül vizsgálnunk kell a betűpárokat és azokat a kombinációkat, amelyek segíthetnek a kriptogram szavakra tördelésében. Olyan kombinációkat keresünk például ami a nyílt szövegben megfelelhet az az+magánhangzó betűhármasnak, vagy keressük a gyakori szóvégi kettős betűket, stb.
30
Feltéve, hogy egyáltalán betűírásról van szó. A mondottak nyílván nem érvényesek a japán vagy a kínai írásra.
31
A bemutatott megfejtési példa is jól mutatja ezt, de egyúttal azt is, hogy legalább törekedtünk a leggyakoribb betűk helyettesítéseinek a meghatározására, mert így tudtuk a kriptogramban a legtöbb betű-megfeleltetést megtalálni és ezzel olyan töredék-szavakhoz jutni, amelyek már jó alapot adtak a még hiányzó betűk találgatására.
42
Tipikus hibák a megfejtés során a következők: a. „Elírjuk” a szöveget. Ha lehet, kerüljük el az egyébként érthetetlen, össze-vissza kriptogram kézzel való átírását. Használjunk ehhez inkább számítógépes eszközöket. (Konkatenációt a táblázatok celláiba írt betűk összefűzéséhez, a Word helyetetsítési funkcióját pl. a szavakra tördeléshez, stb. b. „Félreolvassuk” a kriptogram valamely karaktereit. Pl nem (jól) tudjuk megkülönböztetni az ékezetes és nem ékezetes betűket, vagy ugyanannak az ékezetes betűnek a rövid és a hosszú változatát. A Word helyettesítési funkciója pl. erre is megoldás lehet. Az [5] szakirodalom nagyon részletesen összefoglalja, demonstrálja és értékeli az idők során kitalált helyettesítési módszereket. Nagyon sok hivatkozást is közöl. „Természetesen” csaknem mindet angol nyelvű szövegekre. Az itt hivatkozott szakirodalom ill. az általa hivatkozott William F. Friedman szerint a kriptoanalízis szerint gyakorlatilag bármilyen kriptogram feltörésénél a következő négy művelet alkalmazható: 1) A kriptogramhoz tartozó nyílt szöveg nyelvének a meghatározása. 32 2) Az alkalmazott titkosítási eljárás általános módszerének a meghatározása. 33 3) Ha a módszer már ismert, akkor az adott esetben alkalmazott kulcs meghatározása. Kódkönyves titkosítás esetén 34 a kódkönyv legalább részleges meghatározása. 4) A nyílt szöveg meghatározása
32
Látni fogjuk, hogy ez egyáltalán nem nyilvánvaló pl. a kriptogram ábécében alkalmazott karakterek segítségével s az ismeretlen ókori írások megfejtésekor a legnagyobb probléma éppen az volt, hogy a nyelv ismeretlen volt.
33
Ami nem egyszer megelőzi az előző lépést.
34
Amikor a kriptogram egy-egy jelének vagy jelcsoportjának a szótár-szerű kódkönyvben egy-egy szó, kifejezés, vagy egész mondat felel meg. 43
Ezek a kriptoanalízis klasszikus lépései, amelyek a következő három lépésre (is) redukálhatók: I. A feltörni kívánt kriptogram olyan újra és újra rendezése, amellyel kizárhatjuk azt, hogy a kriptogram véletlenszerűnek lássék. (Gyakoriság analízis, az ismétlődő karakter-kombinációk megállapítása, az esetleges szimmetria felismerése, stb.) II. A nem-véletlenszerű tulajdonságok jellegének a megállapítása pl. statisztikai analízissel, vagy más módszerekkel. III. A véletlenszerűtől eltérő sajátságok megfogalmazása akár szöveggel, akár matematikai (leginkább statisztikai) kifejezésekkel. (Rejtvényfejtési gyakorlattal, szerencsével, intelligenciával, kitartó és ismételt próbálkozással, stb.) A legnagyobb munkát az adott esetben alkalmazott titkosítási rendszer felismerése és azonosítása jelenti. Bármilyen kriptogram megfejtésének végső fázisában egy hellyettesítési titkosítás megfejtésére kerül sor. 35 Ezért is foglalkoztunk ennyit az első generációs kriptorendszerek körében a helyettesítési titkosítással és foglalkozunk még a következőkben is valamennyit. A 2.1 megfejtési példa tanulságai A Toldi statisztikai elemzésekor nem csak az egész, 71 és fél ezer karakteres szöveg statisztikai elemzését végeztük el, hanem az Előhang és mind a 12 ének külön-külön betűgyakoriság statisztikáit is elkészítettük. Az egys szövegrészek terjedelme természetesen erősen eltérő volt, ezért aztán a terjedelemmel súlyozott átlagot számoltunk. Az egyes részek betűgyakoriság-átlagai is szóródtak s ez módot adott a statisztikai szórások kiszámítására.
35
Mármint az algoritmikus megfejtéseknél. A nyers erő módszerénél persze másról van szó.
44
Az adatok táblázatos összefoglalása a következő:
Karakterszám Betű ASCII
Átlag
TOLDI
% Összese n %
73 603 Sorrend
%
32 101 97 116 110 108 115 13 10 107 114 111 105 103 225
e a t n l s
A teljes
k r o i g á egyéb e, a, t, n, l, s k, r, o, i, g, a e, a, t, n, l, s k, r, o, i, g, a
14,61 1 7,03 2 6,33 3 5,69 4 4,43 5 4,35 6 4,07 7 3,37 8 3,37 9 3,08 10 2,96 11 2,89 12 2,75 13 2,75 14 2,55 15 29,77 Ősszesen átlag % Ősszesen átlag % 3 x relatív szórás % 3 x relatív szórás %
14,56 7,10 6,25 5,76 4,43 4,44 4,08 3,34 3,34 3,09 3,01 2,90 2,83 2,77 2,58 29,52 32,06 17,19
3x relatív szórás % 71569 % 15,95 31,97 32,04 43,73 17,42 20,54 25,71 4,61 4,61 32,84 37,91 30,21 38,44 28,32 58,07 8,87
Alsó
Felső
tolerancia-határ _tól 13,40 4,83 4,25 3,24 3,66 3,53 3,03 3,18 3,18 2,08 1,87 2,03 1,74 1,99 1,08 26,90 28,82 15,47
_ig 16,88 9,36 8,25 8,28 5,20 5,36 5,13 3,49 3,49 4,11 4,16 3,78 3,92 3,56 4,07 32,14 35,30 18,91
10,11 10,02
2.7 táblázat A Toldi szövegének statisztikai elemzési adatai „Beszédesebb” ennél a következő hisztogram: A leggyakoribb 15 karakter
Karaktergyakoriság %
40,00 35,00 30,00 25,00 20,00 15,00 10,00 5,00 0,00 1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16
Karakterek csökkenő gyakoriság-sorrendben
45
A hisztogram számozott oszlopai rendre megfelelnek a 2.7 táblázat karaktereinek. Tehát az 1. oszlop a szóköz karkter gyakorisága, a 2. oszlop az e, a harmadik az a, a negyedik a t betűé és így tovább. A hisztogram oszlopainak tetején látható sötétített (színesben barna) sávok a +,háromszoros szórás-intervallumokat ábrázolják. Igen tanulságos, hogy ezek szerint a relatív karaktergyakoriságok többsége ugyancsak átlapolódik. Szignifikánsan elkülönül a szóköz (=az 1. oszlop), de a következő három betűt (e, a, t,) már nem lehet a gyakoriságaik alapján egymástól megbízhatóan megkülönböztetni. Viszont a gyakoriságaik elég egyértelműen elválaszthatók a sorrendben őket követő többi betűétől. A negyedik (azaz az n betűtől kezdve aztán a gyakorisági értékek alapján szinte egyáltalán nem lehet megkülönböztetni egymástól az egyes betűket. Kissé más a helyzet az első és a második 6-6 betű csoportos, együttes gyakoriságainak a megkülönböztethetőségével, mint azt a következő hisztogram mutatja.
Az első és a második 6-6 betűs karaktercsoport kumulált relatív gyakoriságai és azok szórásai
50,00 A 6-6 betűcsoport összesített %os gyakoriságai
40,00 30,00
Adatsor2
20,00
Adatsor1
10,00 0,00
1 e,a,t,n,l,s
2 k,r,o,i,g,a
A hisztogramból látható, hogy a kumulált gyakoriságok alapján szignifikánsan megkülönböztethetők egymástól a betűcsoportok. Az első generációs rendszerek uniformitásai Ismételten (és nem utoljára) emlékeztetünk arra, hogy az első generációs kriptorendszerek körében alapvetően két módszert, nevezetesen a helyettesítést (szubsztitúció) és a transzpozíciót (keverést, permutációt) vezették be. Ezeket a módszereket aztán megörökölték a kriptorendszerek további generációi is. Mégis, a helyettesítés volt a domináns módszer a kriptorendsze46
rek első három generációjánál. Nehéz erre magyarázatot találni. Volt olyan vélemény, amely a transzpozíciót nem tekintette elegendően védettnek a feltörési kísérletekkel szemben s volt olyan vélemény is, amely azt állította, hogy a helyettesítés sokkal könnyebben algoritmizálható, mint a transzpozíció. Az „algoritmizálhatóság” régebben tulajdonképpen azt jelentette, hogy szerkeszthető a titkosításhoz és a megfejtéshez valamilyen gép ill. eszköz. Végül is a Cézár kerék is ilyen eszköz volt és az egyszerűsége éppenséggel indokolhatta is, hogy miért fejlesztették tovább a Cézár-féle titkosítási módszert második generációs, polialfabetikus rendszerekké. Erről azonban majd alább részletesen szólunk majd. A modern, negyedik generációs titkosító rendszerekben mind a helyettesítést, mind a keverést vegyesen, egy rendszeren belül alkalmazzák. A helyettesítésnek ráadásul egyfajta nemlineáris változatát. Egy-egy rögzített hosszúságú blokk helyettesítését egy-egy un. S dobozzal hajtják végre, ahol az S szubsztitúciót, vagyis helyettesítést jelent. Ugyanilyen alapon persze a blokkok permutációját végrehajtó egységeket P doboznak is nevezhetnénk, de ezt a megnevezést ritkábban használják. Mindezekről azonban majd a negyedik generációs (s azon belül is a szimmetrikus) kriptorendszerek kapcsán szólunk majd bővebben. Az első generációs kriptorendszerekben tehát alapvetően kétféle transzformációt alkalmaztak. Az egyik a helyettesítés volt, a másik pedig a transzpozició, vagyis a nyílt szöveg betűinek áthelyezése, összekeverése. A helyettesítés a nyílt szöveg minden egyes betűjéhez egy-egy karaktert rendelt a helyettesítő ábécéből. Tette ezt betűről betűre, folyamatosan. Ezért a titkosítással nyert kriptogramban a nyílt szöveg n-betűs szavainak n-betűs szavak feleltek meg. Ha két betű szomszédos volt a nyílt szövegben, akkor az azokat helyettesítő karakterek is szomszédosak maradtak a kriptogramban. A helyettesítési transzformáció tehát megőrzi a nyílt szöveg betűinek szomszédosságát. Ez tahát egységes (uniform) tulajdonsága mindenfajta helyettesítésnek. Innen származik az, hogy a helyettesítő transzformációnak unilaterális 36 tulajdonsága van. Az első generációs rendszerekben alkalmazott másik fajta tipikus transzformáció a betűket nem változtatja meg, hanem összekeveri azokat. Mivel a betűket latin eredetű szóval literáloknak is nevezik, ezért a keverési transzformációt uniliterális tulajdonságú transzformációnak is nevezik. Mielőtt az utóbbiakat tárgyalnánk, térjünk még vissza a helyetetsítési transzformációkra. Fontos, hogy az itt bevezetett uniliterális kifejezés semmi esetre sem jelent helyettesítési transzformációt, hanem éppenséggel a keverési transzformáció jellegzetes tulajdonságára utal.
36
A laterális latin eredetű szó és oldalirányút jelent. Valószínűleg azért vezették be itt szakszóként, mert jól összecseng a keveréses transzformációnál alkalmazott „literál” szóval, ami viszont betűt jelent.
47
A két- és több-betűs (biliterális, polyliterális) helyettesítések Az eddig bemutatott helyettesítéseknél a nyílt ábécé minden egyes betűjének egy-egy betű felelt meg a kriptogramban. Ezt az egy betű → egy betű helyettesítést a szaknyelv singleliterális 37 helyettesítésnek is nevezi. Ezzel szemben áll az az eset, amikor a nyílt ábécé egy-egy betűjét több karakter helyettesíti a kriptogramban. Kétbetűs helyettesítéskor biliterális, több betűs helyettesítéskor polyliterális rendszerről beszélhetünk. Már az ókorban kitalálták (pl. Polybios is), hogy az ábécé betűit egy mátrixba rendezzék és a nyílt szöveg karakterei helyett a mátrixnak azt a sorát és oszlopát adják meg egy-egy betűvel jelölve, amelyben a nyílt szöveg adott betűje áll. Egyszerűbb a dolgot egy példán bemutatni. Rendezzük el pl. a magyar ábécé betűit (és néhány írásjelet) egy 6 x 6 –os mátrixba a következőképp: A B C D E F A a b
c
d
e é
B
i
í
f
g
h
j
C k
l
m n o ó
D ö ő
p
r
s
E u ú
ü
ű
v y
F
,
:
?
z
.
Polybios „sakktáblája”
t
Ha megegyezünk abban, hogy minden kétbetűs helyettesítésnél az első betű a mátrix sorát, a második pedig a mátrix oszlopát jelöli, akkor pl. a nyílt szöveg p betűjét a DC betűpár helyettesíti, a szóközt pedig az FF. Természetét tekintve ez is olyan, mint a monoalfabetikus helyettesítés, de a nyílt szöveg minden egyes betűje helyett két-két betű áll a kriptogramban. A kriptogram betűstatisztikája azonban azonnal kimutatja, hogy összesen csak 6 betű fordul elő benne és az is nyilvánvaló, hogy betűpárok fognak ismétlődni, méghozzá nem azonos, hanem a nyílt szöveg karaktereinek megfelelő gyakorisággal. Ha ezt felismerjük, akkor a kriptogram már vissza is vezethető az egyszerű, monoalfabetikus helyettesítésre. Polybios a 26 betűs görög ábécében két ritka betűt azonosnak vett és egy 5x5-ös mátrixban rendezte el a nyílt ábécé betűit. Az angol biliterális rendszerekben a 26 betűs angol ábécében az i és a j betűt (vagy az u-t és a w-t) veszik azonosnak és így rendezik az ábécét ugyancsak egy 5x5-ös mátrixba.
37
Sajnos az a helyzet, hogy erre is használják a fent már bevezetett uniliterális szakkifejezést, de más értelemben, mint ahogyan az imént bevezettük.
48
Természetesen semmi különleges indok nincs arra, hogy a nyílt ábécé betűit éppen négyzetes mátrixokba rendezzük és annak sem, hogy ez az elrendezés pl sor- vagy oszlop-folytonos legyen. A 32 betűs magyar ábécé pl. egészen jól elrendezhető egy 4x8-as mátrixba is. Annak sincs különösebb jelentősége, hogy a mátrix sorait és oszlopait betűkkel, számokkal vagy másképp jelöljük Léteztek kettőnél több betűt alkalmazó helyettesítések is. Az egyik legelsőt Tritheimius abbé (Johann von Heidenberg, 1462-1516) vezette be. A lényege az, hogy három szimbólumból (pl. az 1,2 és 3 számjegyekből) összesen 33 = 27 permutáció képezhető (111, 112, … …333) és ezek nagyon jól helyettesíthetik egy 27 betűs ábécé betűit. 38 Érdekességként meg kell említeni Sir Francis Bacon (1561-1626) titkosítási rendszerét is, amely a nyílt ábécé minden egyes betűjéhez egy ötkarakteres kódot rendelt hozzá. Számunkra különösen érdekes, hogy e kódokban mindössze két szimbólumot hasznát, tehát a mai értelmezéssel tulajdonképpen ötbites bináris kódokkal helyettesítette az ábécé betűit. A dolgot tovább bonyolította azzal, hogy egy „ártatlannak” látszó fedő szövegben úgy rejtette el az ötkarakteres kódjait, hogy kisbetűvel írta a fedőszöveg betűit ott, ahol a kódban 0 állt és nagybetűvel ott, ahol 1 állt. Mire jó a szövegstatisztika? Az angol nyelvű szövegekre nagyon sok és nagyon sokféle statisztikai elemzést publikáltak. W.F.Friedman pl. kifejezetten (második világháborús) katonai szövegekre. Más idegen nyelvekre is publikáltak ilyeneket, de magyarra nem. A következőkben a teljesség igénye nélkül demonstrálni kívánjuk azt, hogy egyáltalán nem a bemutatott betűstatisztika az egyetlen statisztikai jellemző, és nem csak a helyettesítési kriptogramok megfejtésére használható. Emlékezzünk arra, hogy a helyettesítési és a transzpoziciós titkosítás között az egyik leglényegesebb különbség az, hogy a helyettesítés a nyílt ábécé minden betűjét egy-egy karakterrel helyettesíti, ami többnyire olyan betű, ami nem azonos a nyílt karakterrel. Ebből következik, hogy a kriptogram ábécé egybetűs gyakoriság statisztikája lényegesen eltér a nyílt szöveg betűinek gyakoriság statisztikájától. Ezzel szemben a transzpoziciós titkosítás egyáltalán nem változtatja meg a nyílt szöveg betűit, csak alaposan összekeveri azokat. A transzpozicióval előállított kriptogram betűstatisztikája tehát szükségképpen megegyezik a nyílt szöveg betűstatisztikájával. (A betűpároké azonban már nyilvánvalóan nem.) A kriptogram egyes betűinek relatív gyakoriság-táblázata alapján tehát egészen jól eldönthető, hogy a kriptogram helyettesítéssel vagy transzpozicióval készült-e. (Feltéve, hogy tudjuk, hogy e két módszer valamelyikével készült.)
38
Persze egy háromdimenziós tömbként is felfogható és ilyen értelemben a biliterális (kétdimenziós) helyettesítés három dimenziós (triliterális) általánosításának is tekinthető.
49
Ennél azonban többet is mond a betűgyakoriság-eloszlás. 39 Eléggé egyértelműen megmutatja, hogy monoalfabetikus vagy polyalfabetikus helyettesítésről van-e szó. A helyettesítési példák kapcsán láttuk, hogy a Cézár-féle helyettesítésnél a megszokott betűsorrend szerint rendezett (szabványos, sztenderd) ábécét használtunk, a 2.1 példánál pedig egy kevert ábécé volt a helyettesítés kulcsa. A betűgyakoriság-táblázatból kiolvasható az is, hogy a helyettesítéskor szabványos ábécét, esetleg fordított sorrendű ábécét vagy kevert ábécét használtak-e. A többetűs statisztikák még mást is megmutatnak. A természetes nyelvekben a beszédben gyakran ismétlődő ill. előforduló hangcsoportoknak bizonyos betűcsoportok felelnek meg. Az ilyenek előfordulása a több-betűs gyakoriság táblázatokban kimutatható. A titkosítási módszerek kitalálói már a második generációs kriptorendszereknél tudatosan törekedtek arra, hogy a szövegstatisztikák ne nyújtsanak segítséget a kriptogram feltöréséhez. 40 A kriptogram betűstatisztikájának eloszlási jellege is utalhat arra, hogy milyen módszert alkalmaztak a titkosításhoz. A modern, negyedik generációs kriptorendszereknél pl. teljesen véletlenszerűnek tűnik a kriptogramok betűstatisztikája. Ezeknél a betűeloszlás meglehetősen egyenletes. (Már ha egyáltalán megjelennek betűk a kriptogramban.) A betűstatisztika mindenesetre ezt is kimutatja. A statisztikák alkalmazásakor kell, hogy legyen valami sejtésünk arról, hogy azok mennyire megbízhatóak. Egy 1000 betűs szöveg statisztikája már majdnem azonos egy jóval több betűs szövegével, de ha a szöveghossz csökken, akkor a betűstatisztika egyre jobban eltér az átlagostól. Az eddig elmondott minőségi megállapítások mellet természetesen léteznek mennyiségekkel meghatározható statisztikai próbák is. Ilyen pl. az un. fí teszt, ami arra alkalmas, hogy megállapítsuk, hogy egy kriptogram monoalfabetikus titkosítással készült-e vagy sem.
39
Angol terminológiával a Single-literal Frequency Distribution rövidítéseként SFD, ill. ha a Single-literal helyett az egyébként megtévesztő Uniliteral kifejezést használják, akkor UFD. Randall K. Nichols az [5]-ben az utóbbit vezette be.
40
Újabb kutatások szerint valamikor az első ezredforduló tájékán arab matematikusok jöttek rá és írták le, hogy a titkosított szövegek karakter (ill. szimbólum) gyakoriságainak elemzése jó esélyt ad a kriptogramok megfejtésére.
50
A φ teszt Vezessük be a következő jelöléseket: N:
A vizsgált (angol) szöveg karaktereinek a száma
Φ(o)
A tesztelt kriptogram betűgyakoriság-eloszlására jellemző érték. (o → observed)
Φ(p)
Az előbbihez tartozó nyílt ábécé betűgyakoriság eloszlására jellemző érték. (p → plaintext)
Φ(r)
Ha az ábécé minden betűje azonos gyakorisággal fordulna elő, akkor nagy átlagban éppen 1/n (ahol n az ábécé betűinek a száma) lenne egy-egy betű előfordulási gyakorisága. Ha azonban a vizsgált minta N betűből áll, akkor Φ(r) egy-egy betűre jellemző statisztikai érték. Friedman alábbi képletében a 0,0385 konstans a 26 betűs angol ábécéből számított 1/26.
Friedman szerint az angol katonai szövegekre Φ(r) = 0,0385 N (N-1) Φ(p) = 0,0667 N (N-1) 2.2 Példa Számítsuk ki a fí tesztet a következő N = 50 betűs kriptogramra: O W Q W Z
A E D T D
Q H H O B
A W F T Z
W O D E Q
T U W R Q
B D Q R O
X H Q D A
G T B D H
P Z R D K
A következő táblázatban f az egyes betűk előfordulásainak számát jelöli, a megadott ábécé pedig a 26 betűs angol ábécé. f:
3 3
7 2 1 1 4
1
4 1 6 3
4 1
5 1
3
ábécé: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z f(f-1)
6 6
42 2 0 0 12
0
12 0 30 6 12 0
20 0
0
Ezekből:
ϕ (o) = ∑i =1 f i ( f i − 1) =154 26
ϕ (r ) = 0,358 N (N − 1) = 0,358 × 50 × 49 = 94 ϕ ( p ) = 0,0667 × 50 × 49 = 163
Mivel Φ(o) közelebb esik Φ(p)-hez mint Φ(r)-hez, ezért arra következtetünk, hogy a vizsgált kriptogram monoalfabetikus. Érdekes eredményt kapunk, ha kriptogramként megvizsgáljuk a nyomtatók és fontkészletek tesztelésére alkalmazott ismert szöveget:
51
A QUICK BROWN FOX JUMPS OVER THE LAZY DOG Itt N = 33; Φ(o) = 20; Φ(r) = 41 és Φ(p) = 70 , Mivel Φ(o) kevesebb, mint fele a teljesen egyenletes véletlen eloszlásra jellemző Φ(r)-nek a teszt eredménye azt sugallja, hogy a vizsgált szöveg semmilyen nyelven sem lehet nyílt szöveg. persze van más értelmezés is: Ebben a rövid szövegben legalább egyszer előfordul a 26 betűs angol ábécé minden egyes betűje. A betűeloszlás tehát meglehetősen egyenletes, azaz nagyon „véletlenszerű” A helyettesítési titkosítások körében igaz az előbbi következtetés, de pl. a mai modern kriptorendszerek éppen arra törekednek, hogy a kriptogram betűinek az eloszlása minél inkább véletlenszerű legyen, hogy a megfejtő sehol se’ találjon semmilyen rést, ahol elkezdhetné a kriptogram módszeres feltörését. A koincidencia-index Friedman az egyik alapvető cikkében a fenti φ jellemzők egy másféle értelmezését adja. Az un. koincidencia-index definició szerint a következő:
IC =
ϕ (o) ϕ (r )
Az angol nyelv esetén a koincidencia index elméleti értéke:
IC =
0,0667 = 1,73 0,0385
Teljesen véletlenszerű teszt szöveg esetén a koincidencia index értéke 1,00 Mindezt annak a szemléltetésére mutattuk be, hogy egyáltalán nem csak a betűgyakoriság-statisztikák jelentik a kriptogramok megfejtésekor alkalmazható statisztikai módszereket, vizsgálatokat. A bemutatott statisztikai elemzéseken kívül még számos más is létezik. A következőkben szólnunk kell még valamennyit az első generációs kriptorendszerek „másik”, eddig csak néhányszor említett transzformációs módszeréről, nevezetesen a transzpozicióról.
52
A transzpoziciós titkosítás A transzpozició a nyílt szöveg betűinek az eredetitől eltérő, más poziciókba való áthelyezését jelenti. Másképpen fogalmazva a betűk valamilyen kulcs szerinti összekeverését, permutációját. Emlékeztetünk arra, hogy az első generációs kriptorendszerekre jellemző transzformációk egyik alaptipusa a helyettesítés, a másik pedig a keverés. Nos, a következőkben az utóbbiról lesz szó, tehát a tárgykörünk még mindig az első generációs kriptorendszereké. Ha a nyílt szöveg (vagy annak csak a szavai) betűit fordított sorrendben írjuk le, már az is egyfajta titkosításnak tekinthető. A betűk maguk nem változnak, csak a szövegben eredetileg elfoglalt pozicióikat változtatjuk. Ez igen egyszerű „titkosítás”. Ilyen betűkeverést hajtottak végre a spártaiak által kifejlesztett szkütalira tekert szalagra írt szöveggel is. 41 A transzpoziciós titkosításról középkori feljegyzések is szólnak. Pl. a nápolyi Giovanni Porta úgy írta le a De furtivis literarum notis c. könyvében 1536-ban, mint a titkosítás alapvető módszerét. Röviddel utána azonban feledésbe merült s ismét domináns lett a helyettesítés. A XVII. században aztán nagyon népszerű rejtvényként foglalkoztak az anagrammák kitalálásával. Az anagramma egy adott szó betűit úgy rendezi át más sorrendbe, hogy lehetőleg egy másik értelmes szót kapjunk. Rejtvénynek, vagy szórakoztató játéknak jó, de titkosítási módszernek nem igazán. A geometriai titkosítás A transzpozició egy jól kezelhető, igen változatos és népszerű módja az un. geometriai titkosítás. A nyílt szöveg betűit egy (geometriai) rácsszerkezetbe írják be, és más sorrendben olvassák ki ugyanabból a rácsszerkezetből. A beírási és kiolvasási módszerek igen változatosak lehetnek és gyakran alkalmazták azt a technikát is, hogy az első összekeveréssel előállított kriptogram betűit még egyszer összekeverték vagy ugyanazzal a módszerrel, vagy valamilyen más módszerrel. Ez mindenesetre erősebbé tette a titkosítást, vagyis ellenálóbbá a feltörési kisérletek ellen.
41
Ennek a rajza látható e jegyzet elején a belső borítólapon. Thüszidédesz görög történetíró rta le az ötödik században(de az arabok is ismerték) és ezideig az első olyan eszköz, amelyet ismereteink szerint titkosításhoz ill. megfejtéshez használtak. 53
2.3
példa Írjuk be egy hatoszlopos mátrixba sorfolytonosan a következő nyílt szöveget: A gépek sohasem pótolhatják az emberi képzeletet (Tegyük ezt a titkosításnál szokásos módon, szóközök nélkül) A
G É
P
E
K
S
O H A
S
E
M P
Ó T
O L
H
A
T
J
Á
K
A
Z
E
M B
E
R
I
K
É
P
Z
E
L
E
T
E
T
A transzpozició egyszerű módja, ha a szöveget pl. oszlop-folytonosan olvassuk ki (és a szokásos módon ötös csoportokba rendezzük): ASMHA REGOP AZILÉ HÓTEK EPATJ MÉTES OÁBPE KELKE ZT123 Ebben a kriptogramban a betűgyakoriságok természetesen pontosan megegyeznek a nyílt szöveg betűgyakoriságaival. A helyettesítési módszernél megőrződő „szomszédosság” (= a nyílt szöveg szerkezete, az unilateralitás) azonban elvész. A kriptogram feltöréséhez „gyanús szavak” betűsorait keressük úgy, hogy feltételezzük, hogy azok betűi egymástól azonos távolságra kerültek az összekeveréskor. Persze a dupla transzpozició ezt is megváltoztatja. Miért geometriai ez a titkosítás? Ennek két oka is van: Először is az az alakzat, amelybe beírjuk a nyílt szöveget nem csak egy párhuzamos oldalú mátrix lehet, hanem más, mezőkre osztott síkidom is. Pl. háromszög, trapéz vagy éppenséggel hatszög is. Másodszor pedig az, hogy a kiolvasás módja (azaz a keverés) nagyon sokféle lehet. A fenti mátrixból pl. kiolvashatjuk a szöveget úgy is, hogy a páratlan oszlopokat felülről lefelé, a páros oszlopokat pedig alulról felfelé olvassuk, de lehet átlósan is kiolvasni és lehet a mátrix szerkezetét követő csigavonalban is, hogy csak néhányat említsünk.
54
Mindezek mellett és ellenére a modern kriptorendszerekben egy un. permutációs mátrix a keverés kulcsa. Ez megmutatja, hogy egy adott, megállapodás szerinti mátrixba beírt nyílt szöveg betűit a keverés egy ugyanolyan szerkezetű mátrix melyik cellájába (vagy ha sorfolytonosnak tekintjük mind a nyílt szöveget, mind a kriptogramot, akkor a kriptogram hányadik betűhelyére) viszi át a keverési kulcs. Az előző példa permutációs kulcsa például a következő: 1 8
15 22 29 36
2 9
16 23 30 37
3 10 17 24 31 38 4 11 18 25 32 39 5 12 19 26 33 40 6 13 20 27 34 41 7 14 21 28 35 42 A transzpozicióhoz persze ezt a mátrixot is sorfolytonosan kell olvasni és megadhattuk volna a kulcsot pl. az 1, 8, 15, 22, 29, 36, 2, 9, … …34, 41, 7, 14, 21, 28, 35, 42; szám sorozattal is, ami azt jelenti, hogy a nyílt szövegblokk első betűje a kriptogram első betűhelyére, a nyílt szöveg második betűje a kriptogram nyolcadik betűhelyére, a nyílt szöveg harmadik betűje a kriptogram 15. betűhelyére kerül, és így tovább. Nyilvánvaló, hogy a keverési kulcs ilyen táblázatos megadásával nagyon véletlenszerű keverési sorrendet is könnyen definiálhatunk és számítógéppel semmivel sem nehezebb egy ilyen transzpoziciót végrehajtani, mint bármelyen cseles klasszikus „geometriai” kiolvasási módszerét. Ma már tehát egyáltalán nincs is értelme geometriai transzpozicióról beszélni. A keverés egymaga ugyan ma már nem nyújt elegendően biztos titkosítást, de helyettesítésekkel kombinálva és többszörös keverést alkalmazva nagyon is beépül a modern, negyedik generációs kriptorendszerekbe is.
55
Transzpozició forgatható ráccsal Egy négyzetes mátrixba beírt szöveg egy forgatható ráccsal is összekeverhető. 42 Egy páros elemszámú négyzetes mátrixban mindig kijelölhető az elemszám egynegyedének megfelelő cella úgy, hogy a mátrix transzponálásakor egyik ilyen megjelölt elem se’ kerüljön egy másik helyére. Ezt is egyszerűbb egy példán bemutatni. 2.4
példa
1
2
1
2
3
10
3
11
19
12 4 5
7
8
28
20
13
14
6
4 21
22
15
29 30
23
31
24
32
16 17
33
25
9
18
26
27
34 35
36
A cellakijelölő mátrix négy forgatási poziciója és a nyílt szöveg beírásának betűsorrendje
A permutációs mátrix 28
10
1
19
11
2
3
20
12
29
30
21
13
22
31
4
23
14
32
5
24
15
6
33
7
16
17
34
8
25
26
35
9
27
36
18
Az Olvasó kipróbálhatja, hogy egy 6 x 6 –os négyzetrácsnak kivágja az 1. pozicióban sötétített celláit és a négyzetrács elforgatásával titkosít egy 36 betűs szöveget.
42
Ilyen titkosítást ír le Verne Gyula a Sándor Mátyás c. regényében. 56
A transzpoziciós titkosítási transzformáció jellegzetes tulajdonságai
43
1.
A nyílt szöveg betűit nem változtatja meg, csak összekeveri azok sorrendjét.
2.
A kriptogram ábécéje (és betűgyakoriságai) pontosan megegyeznek a nyílt szöveg ábécéjével és betűgyakoriságaival.
3.
A transzformáció monoalfabetikus.
4.
A nyílt szöveg betű-többeseinek gyakoriságai azonban már nem egyeznek a kriptograméval.
5.
Ez a transzformáció tehát uniliterális (a betű egyezések miatt) de nem unilaterális (a betűsorrend összekeverése miatt).
6.
Az ábécé nem kötött (mint a helyettesítésnél). Tetszőleges karakterek használhatók.
7.
Nem feltétlen kikötés ugyan 43 a nyílt szöveg egyszerre titkosított un. blokkjának a mérete, de szinte minden gyakorlati esetben azonos számú betűt tartalmazó blokkokra tördelik a szöveget és ezeket a szövegblokkokat külön-külön egymás után transzformálják. A transzpoziciós titkosítás tehát többnyire kötött hosszúságú szövegblokkokkal működik.
8.
A transzformáció kulcsa a permutációs mátrix.
Ha a 2.3 példára gondolunk, ott csak a transzpoziciós mátrix oszlopainak a száma volt megadva, a soroké nem. Hosszabb szöveghez többsoros mátrix tartozhatott volna. 57
Az ismételt transzformációk Mind a helyettesítési, mind a transzpoziciós titkosítás esetén ismételten is alkalmazható ugyanaz a tipusú transzformáció, csak minden ismétlés más-más kulccsal. 44 Könnyen belátható azonban, hogy a transzformációk megismétlése nem jelent lényegi változást. A helyettesítéskor pl. helyettesítse az A betűt B az első transzformációnál (amelynek a kulcsát jelölje K1), és helyettesítse C a B betűt a második (K2 kulcsú) transzformációnál. E két, egymásutáni helyettesítés felfogható egyetlen (valamilyen K3) kulcsú helyettesítési transzformációnak is, amely a nyílt szöveg minden A betűjét C-be viszi át. (A K3 kulcs a K1-ből és a K2-ből eredeztethető.) Két, vagy több helyettesítési transzformáció egymásutáni alkalmazása tehát egyetlen helyettesítési transzformációnak tekinthető és úgy is kezelhető. Ez igaz akkor is, ha az egymás utáni transzformációk mindegyikének más a helyettesítési kulcsa (és n betűs betűcsoportot mindig n betűs betűcsoporttal helyettesít). Mivel mindegyik helyettesítési transzformáció unilaterális (azaz megőrzi a nyílt szöveg betűinek a szomszédosságát) ezért az ismételt helyettesítési transzformációk „eredője” is unilaterális az eredeti szövegre nézve is. Ne feledjük, hogy mindez akkor, és csak akkor érvényes, ha valamennyi transzformáció kulcsa rögzített. Ha bármelyik komponens transzformáció kulcsa megváltozik, akkor változik az „eredő” transzformáció kulcsa is. Amíg a transzpoziciós titkosításokat kézi módszerrel végezték, addig valóban nehezíthette a megfejtést a permutációk ismétlése. 45 Például sorfolytonosan beírták a nyílt szöveget egy „k” oszlopos mátrixba és oszlop folytonosan kiolvasták belőle, majd a kapott kriptogramot sorfolytonosan ismét beírták egy „k” oszlopos mátrixba és átlósan kiolvasták belőle. Ez a két permutációs eljárás végeredményben egyetlen permutációként is felfogható, amelynél azonban nem érvényes a sorfolytonos beírás – oszlop-folytonos kiolvasás, hanem egy permutációs táblázattal kell megadni az „eredő” permutációt.
44
Ez magától értetődő ha az ismételt transzformációk mindegyike egy betűt egy betűvel helyettesít. A dolg azonban általánosabb ennél: Igaz akkor is, ha n betűs betűcsoportot n betűs csoporttal hellyettesítünk az egymást követő transzformációk mindegyikében. Ez a feltétel végül is a transzformációs függvények izomorfiájaként is megfogalmazható, de ebbe itt nem szándékozunk belemenni.
45
A transzpoziciós titkosítás tárgyalásakor utaltunk is az un. „geometriai” transzformációra, ami csakis annyit jelentett, hogy a nyílt szövegnek a permutációs mátrixba való beírásakor és/vagy a kiolvasásakor valamilyen „geometriai” elrendezést követtünk. Ha a permutációs kulcs táblázattal van megadva, akkor –a számítógépes megoldásoknál- nem igen van jelentősége az ilyen és ehhez hasonló geometriai mintázatoknak.
58
Az ismételt permutációkra is igaz tehát, hogy azok „eredője” egyetlen permutációval helyettesíthető és igaz az is, hogy ha valamennyi komponens permutáció uniliterális (azaz „csak” összekeveri az eredeti nyílt szöveg betűit) akkor az „eredő” transzformáció is ugyanígy uniliterális lesz az eredeti nyílt szövegre nézve. Ne feledjük azonban, hogy a permutációt mindig blokkokon hajtjuk végre. Az egymást követő transzpoziciók akkor és csakis akkor felcserélhetők, ha a blokkhosszúság mindegyik közbenső transzformációnál ugyanaz. A szorzat transzformáció és az invertálhatóság Mind a helyettesítési, mind a transzpoziciós titkosítás esetén ismételten is alkalmazható ugyanaz a tipusú transzformáció, esetenként minden ismétlés más-más kulccsal. Mind az ismételt helyettesítéseknél, mind az ismételt permutációknál felfogható az „eredő” transzformáció a komponensek szorzatakén, tehát még a komponens transzformációk végrehajtási sorrendjére nézve is invariáns az eredő transzformáció. Az ilyen tulajdonságú ismételt transzformációkat szorzat, azaz produkttranszformációknak. nevezzük. Nem kell külön bizonyítani, hogy mind a helyettesítési, mind a transzpoziciós transzformációk „visszafelé” is alkalmazhatók, azaz invertálhatók. Ennek így is kell lennie ahhoz, hogy egy velük titkosított szöveg kriptogramja visszafejthető legyen. Az invertálhatóság tehát a visszafejthetőség feltétele. A szorzat-transzformációkról eddig elmondottak értelmében a produkt transzformációk is invertálhatók, tehát visszafejthetők. 46 Mi a helyzet akkor, ha egy nyílt szövegen először egy helyettesítési, majd egy transzpoziciós transzformációt hajtunk végre? Nos, a helyettesítési transzformáció nem változtatja meg az eredeti szöveg betűinek egymásmelletiségét (mivel unilaterális) a permutáció pedig csakis az utóbbit változtatja és nem befolyásolja a szöveg betűit (mivel uniliterális). A helyettesítési és a keverési transzformációk alapvetően eltérő jellege miatt tehát az egyik semmilyen hatást sem gyakorol a másikra. Ezért egy helyettesítési és egy transzpoziciós transzformáció egymás utáni alkalmazása is produkt transzformáció, amelyben a komponens-transzformációk felcserélhetők.
46
Ez már csak azért is igaz, mert ha minden helyettesítési transzformáció invertálható, akkor ennek igaznak kell lennie a komponens transzformációk eredőjeként előálló hellyettesítési transzformációra is és nyílván ugyanez a helyzet a az ismételt permutációk eredőjeként kapott transzpoziciós transzformációra is. (Feltéve ha teljesülnek a korábban már említett izomorfia feltételek a transzformációs függvényekre.) 59
A helyettesítési transzformációk „blokk-hosszúságának (pl. egy betűt egy betűbe visz át) nem kell azonosnak lennie a permutációs transzformációk blokk-hosszúságával. Már csak azért sem, mert pl. egyetlen betűből álló „blokkot” nem is lehet keverni, de helyettesíteni igen. Ez az eredő transzformáció azonban más, se nem helyetesítési, se nem transzpoziciós, hanem a kettő keveréke. A fentiekben elmondottak miatt mind a helyettesítési transzformációk egy akárhány tagú sorozata egyetlen helyettesítési transzformációként fogható fel, amelyben az egyes komponens-transzformációk végrehajtási sorrendje közömbös és ugyanígy értelemszerűen igaz ez a permutációs transzformációkra is. (Feltéve, hogy az egymás utáni helyettesítések blokkhosszúságai egymással azonosak és az egymás utáni permutációs blokkméretek is egymással – de nem a helyettesítési blokkméretekkelazonosak.) 47 Ha az ismételt transzformációknál nem csak a kulcs, hanem pl. a blokkméretek is változnak (azaz nem teljesül az alkalmazott transzformációk izomorfia-feltétele) akkor az eredő már nem produkt transzformáció, hanem egymásba ágyazott transzformációkról. van szó, amelyek invertálhatók ugyan, de a visszafejtési sorrend egyáltalán nem közömbös és a transzformációk nem felcserélhetők. Az azonos tipusú transzformációk mondott összevonása ill. szorzatként való értelmezhetősége sőt: a helyettesítési és a transzpoziciós transzformációk szorzat-transzformációnak tekinthetősége, persze, jelentős könnyebbséget jelenthet az eredő kriptogram feltörésekor. Ettől, persze, a kriptogram feltörése még nagyon nehéz feladat, de a kriptoanalízis avatott szakemberei számára még a legkisebb fogódzók is segítséget jelenthetnek. Ennek tudatában vannak a kriptorendszerek megalkotói is. Látni fogjuk később, a negyedik generációs, iterációs kriptorendszerek tárgyalásakor, hogy a modern szimmetrikus kriptorendszerekben vegyesen és felváltva alkalmazzák mind a helyettesítési, mind a transzpoziciós transzformációkat, de az azonos tipusúaknál is törekednek arra, hogy a mondott izomorfia-feltétel ne teljesüljön, tehát egyáltalán ne legyen közömbös a visszafejtéskor az alkalmazott transzformációk sorrendje. Emellett még más, a két alaptipustól eltérő transzformációt is bevezettek némelyik rendszerbe csak azért, hogy a potenciális feltörők dolgát megnehezítsék.
47
Ez akkor teljesül, ha a helyettesített szöveg kevert képe megegyezik a kevert szöveg helyettesített képével, ami a kétféle (nevezetesen a helyettesítési és a keverési) transzformációk izomorf tulajdonságával függ össze.
60
Ha pedig az „eredők” szorzat jellegét (azaz kommutativitását) is figyelembe vesszük, akkor azt állíthatjuk, hogy ha helyettesítési és transzpoziciós transzformációk egy tetszőleges sorozatát tekintjük, akkor mindegy, hogy e sorozat komponens transzformációit milyen sorrendben hajtjuk végre, az eredmény ugyanaz lesz. Ez, persze, az inverz transzformációkra, azaz a megfejtésre is igaz. A fentiekben induktív következtetéssel kapott eredmények, persze, általánosíthatók is. Azt állítjuk, hogy mind a helyettesítési, mind a permutációs transzformációk a mondott blokkméret-feltételek mellett un. izomorf transzformációk. és egymásra nézve is teljesül az izomorfiájuk Az azonos tipusú izomorf transzformációk sorozata pedig szorzat transzformációt eredményez, amelyben –a szorzat kommutativitása miatt- a komponenstranszformációk sorrendje felcserélhető, azaz az eredő transzformáció invariáns a komponensek sorrendjére. Ha találunk két különböző lineáris transzformáció-tipust, amelyek egymásra semmilyen befolyást nem gyakorolnak, akkor ezek egymás utáni alkalmazása is szorzat transzformációt eredfményez.
61
Tárgymutató
agglutináló nyelv .......................................................................................... 16 anagramma ................................................................................................. 55 Arany János ................................................................................................ 42 aszimmetrikus kriptorendszer ...................................................................... 10 Bacon, Sir Francis ....................................................................................... 51 beágyazott transzformáció .......................................................................... 62 betűpár ........................................................................................................ 29 betű-többes ................................................................................................. 27 bigraph ........................................................................................................ 27 biliterális ...................................................................................................... 50 brute force ............................................................................................. 11, 23 cézár kerék ................................................................................................. 20 Cézár-féle titkosítás ..................................................................................... 19 Chadvick, John ............................................................................................ 14 cleartext. ........................................................................................................ 8 Codebrakers ................................................................................................ 10 cryptanalist .................................................................................................. 10 cryptosystem ............................................................................................... 10 cuneiform..................................................................................................... 15 decipherment ................................................................................................. 9 dekódolás ...................................................................................................... 9 desiffrírozás ................................................................................................... 9 duplet........................................................................................................... 27 egybetűs szavak .......................................................................................... 30 eltolásos helyettesítés ................................................................................. 30 encipherment ................................................................................................. 9 encryption ...................................................................................................... 9 Enigma ........................................................................................................ 43 fordított sorrendű ábécé .............................................................................. 52 Friedman, William F..................................................................................... 45 geometriai titkosítás. ................................................................................... 55 Grotenfeld,Georg Fridrich ............................................................................ 15 Heidenberg, Johann von ............................................................................. 51 helyettesítés .......................................................................................... 18, 48 hieratikus írás .............................................................................................. 14 hieroglif írás ................................................................................................. 14 Horapollon ................................................................................................... 14 izomorf transzformációk. ............................................................................. 63 J.F.Champollion .......................................................................................... 14 Julius Caesar ............................................................................................... 19 kétbetűs szavak ........................................................................................... 30 keverés .................................................................................................. 18, 48 kevert ábécé ................................................................................................ 52 kód(fel)törés ................................................................................................ 10 koincidencia-index ....................................................................................... 54 kompromittálódás .......................................................................................... 9
62
konkatenáció ............................................................................................... 45 krétai lineáris B írás ............................................................................... 14, 16 kriptoanalizátorok ........................................................................................ 10 kriptoanalízis ............................................................................................... 10 kriptográfia................................................................................................... 10 kriptográfiai erősség .................................................................................... 23 kriptogram ............................................................................................... 8, 10 kriptorendszer .............................................................................................. 10 kulcs .............................................................................................................. 9 kulcstér ........................................................................................................ 23 modulo n kivonás ........................................................................................ 21 modulo n összeadás.................................................................................... 21 monoalfabetikus .......................................................................................... 18 monoalfabetikus helyettesítés ..................................................................... 19 Navajo indián ................................................................................................. 5 nyers erő módszere ..................................................................................... 23 nyers erő ódszere ........................................................................................ 11 nyílt szöveg. .................................................................................................. 8 nyiltkulcsú kriptorendszer ............................................................................ 10 P doboz ....................................................................................................... 49 pemutáció .................................................................................................... 55 pentagraph .................................................................................................. 27 permutáció............................................................................................. 18, 48 permutációs kulcs ........................................................................................ 57 permutációs mátrix ...................................................................................... 57 plaintext ......................................................................................................... 8 Polybios ....................................................................................................... 50 polygraph..................................................................................................... 27 polyliterális ................................................................................................... 50 Porta, Giovanni ............................................................................................ 55 produkt transzformáció. ............................................................................... 61 Pythagoras .................................................................................................. 14 quadruplet ................................................................................................... 27 quintuplet ..................................................................................................... 27 Rasid ........................................................................................................... 14 Rawlinson, Henry Creswicke ....................................................................... 15 reciprocitás elve .......................................................................................... 43 Rónai Jácint ................................................................................................. 15 Rosette ........................................................................................................ 14 rosette-i kő................................................................................................... 14 S doboz ....................................................................................................... 49 Sándor Mátyás ............................................................................................ 58 Shannon ...................................................................................................... 23 siffrírozás ....................................................................................................... 9 singleliterális ................................................................................................ 50 singleton ...................................................................................................... 27 statisztikai tulajdonságok ............................................................................. 23 szabványos ábécé ....................................................................................... 52 szimmetrikus rendszerek ............................................................................. 10 szótag-írás................................................................................................... 16
63
szteganográfia ............................................................................................... 6 szubsztitúció ................................................................................................ 48 természetes nyelv ....................................................................................... 23 tetragraph .................................................................................................... 27 Toldi............................................................................................................. 42 transzpozició ................................................................................... 18, 48, 55 trigraph ........................................................................................................ 27 Tritheimius ................................................................................................... 51 unilaterális ................................................................................................... 49 Ventris, Michael ..................................................................................... 14, 16 Verne Gyula ................................................................................................ 58 φ teszt ......................................................................................................... 53 Szakirodalom A Budapesti Műszaki Főiskola Kandó Kálmán Villamosmérnöki Főiskolai Karának székesfehérvári Számítógéptechnikai Intézete intranet hálózatán is találhatók aktuális anyagok a következő webkikötő címén: http://www.szgti.bmf.hu További website-ok: www.ssh.fi/tech/crypto/algorithms.html amely a nyílt és a titkos kulcsú algoritmusokról ad rövid ismertetőt www.ssh.fi/tech/crypto/protocols.html amely viszont a legfontosabb kriptográfiai protokollokat sorolja fel, köztük azokat is, amelyeket ma már szabványosítottak. A számos angolnyelvű könyv közül csak néhányat említünk: [1]
Randall K. Nichols: ICSA (= International Computer Security Association) Guide to Cryptography. McGraw-Hill, 1999. ISBN 0-07-913759-8 A legjobb (és egyik legfrissebb, angolnyelvű) kézikönyv a kriptográfiáról, amelyben gyakorlatilag minden megtalálható, amit ma erről tudni kell)
[2]
Robert Churchhouse: Codes and Ciphers Cambridge University Press, 2002. ISBN: 0 521 00890 5
[3]
F.L.Bauer: Decrypted Secrets. Methods and Maxims of Cryptology. Springer Verlag 1997. ISBN: 3-540-60418-9
[4]
Randall K. Nichols, Daniel & Julie Ryan: Defending Your Digital Assets. McGraw-Hill, 2000. ISBN 0-07-212285-4
[5]
Randall K. Nichols: Classical Cryptography Course Vol.1 & Vol2. Aegean Park Press CA-USA 1996. ISBN 0-89412-263-0 & 0-89412-264-9
[6]
Bernard Sklar: Digital Communications – Fundamental and Applications Prentice Hall Inc. 1998. ISBN 0-13-212713-x025
64
[7]
Bruce Schneier: Applied Crytography. John Wiley & Sons, 1994.
[8]
David Kahn: Codebrakers.
[9]
Fred B. Wrixon: Codes, Ciphers & Other Cryptic & Clandestine Communication Black Dog & Leventhal Publishers, NY 1992. ISBN: 1-57912-040-7
Az adott témával foglalkozó kevésszámú magyarnyelvű szakirodalomból a következő könyvek ajánlhatók: [10]
Németh József: Adatvédelem számítógépes és hírközlő rendszerekben Számalk, Budapest 1984.
[11]
Nemetz Tibor - Vajda István: Az algoritmusos adatvédelem Akadémiai kiadó, 1991.
[12]
Ködmön József: Kriptográfia. Computer Books Kiadói Kft, Budapest 1999/2000. ISBN 963 618 224 8
[13]
Simon Singh: Kódkönyv.Park Könyvkiadó, Budapest 2001. ISBN: 963 530 525 7
[14]
Virasztó Tamás: Titkosítás és adatrejtés NetAcademia Kft. 2004. ISBN 963 214 253 5 A 2008 elejéig megjelent magyarnyelvű könyvek közül ez messze a legjobb átfogó kriptográfiai mű. Tankönyvként ajánlható.
ZÁRSZÓ A fentiekkel a kriptogenerációk tárgyalását egyáltalán nem tekinti befejezettnek a szerző. Ennek a segédletnek várhatóan lesz folytatása, amely majd a második és a harmadik generációs kriptorendszerekkel foglalkozik. A negyedik generációs kriptorendszerek közül „DES” címmel (és Randall K, Nichols professzorral közösen megírva) már megjelent a szimmetrikus kriptorendszerekkel foglalkozó segédlet és a szerző tollából az Aszimmetrikus kriptorendszerekről írt anyag is. Megjelent továbbá néhány nagyobb esszé pl. a digitális aláírásról, meg az adatvédelemről. Ezek hozzáférhetőek a BMFKVK távoktatási jegyzetei és segédletei között, valamint elolvashatók a www.szgti.bmf.hu/~mtoth webkikötő vonatkozó mappáiban.
Székesfehérvárott, 2002. augusztus 15-én Dr. Tóth Mihály CSC ,főiskolai tanár
65
Számos hasznos és érdekes, esetenként kipróbálható magyarázó és demo anyag található a WEB-en. Kereső kifejezésként ajánlható a következő: simple substitution Ugyancsak jó kiindulás a Wikipedia: http://en.wikipedia.org/wiki/Substitution_cipher A Cézár kerekes helyettesítéshez pl. a következő webkikötőn található program: http://spwebgames.com/crypto/
66
