8.2. Klasszikus titkosítási eljárások

A titkosítás több ezer éves múltra tekint vissza. Államférfiak és hadvezérek tudták, hogy ellenfeleik mindent megtesznek azért, hogy terveiket mielőbb megtudják és megelőzzék a lépéseiket. Elképzeléseiket ezért csak közvetlen bizalmasaikkal tárgyalták meg és utasításaikat a lehető legkésőbbi időben juttatták el alvezéreikhez. Modern terminológiával élve, a kommunikációra bizalmas csatornát, megbízható küldöncöt használtak. Még ezt sem tartották elég biztonságosnak, mert az üzenetet is kódolva adták át a küldöncnek. A címzett persze csak akkor tudta megfejteni az üzenetet, ha korábban közölték vele a visszafejtő eljárást.

Julius Caesar római császárról jegyezték fel, hogy üzeneteit úgy kódolta, hogy a szövegben előforduló betűket az abc-ben az adott betűtől előre megállapított távolságban levő másik betűvel helyettesítette. A helyettesítést úgy kell persze elképzelni, hogy az abc betűit egy kör kerületére írjuk fel, így az abc végén álló karakterek helyett az abc elején állókat kell írni. Ezt a módszert ma Caesar titkosításnak nevezzük. Tekintsük például az angol abc-t és tegyük fel, hogy a távolság 7 akkor a megfelelő helyettesítést az alábbi táblázat mutatja:

A következő üzenet: „tizenegy orakor tamadunk” kódolt formája tehát így alakul: „apglnlnf vyhrvy ahthkbur”. A 8.1 fejezetben bevezetett terminológiát használva a Ceasar titkosítás a következőképpen írható le. A P és C az angol abc betűinek halmaza, míg K = {0,1,…, 25}. Az E kódoló függvény értékét az u üzenetre és a kt kulcsra úgy kell kiszámítani, hogy meghatározzuk u sorszámát az abc-ben, ehhez hozzáadjuk kt –t. Ha a kapott érték nagyobb, mint 26, akkor levonunk belőle 26-ot. Ezek után megkeressük az így kapott sorszámú betűt az abc-ben. A dekódoló kulcs megegyezik kt –vel, ha az 0 és 26 - kt –vel különben.

Az előbbi leírás egy ember számára érthető, de számítógépnek nehézkes. Sokkal jobb eredményt érhetünk el, ha figyelembe vesszük, hogy a P és C halmazok végesek, így nem a betűket, hanem csak az abc-beli sorszámaikat vesszük figyelembe. A sorszámozást 0-val kezdve P = C = K = {0,1,…, 25} és ekkor E(u, kt) = u + kt mod 26. Továbbá kd = 26 - kt mod 26 és D(m, kd ) = m + kd mod 26.

Világos, hogy a Caesar titkosítás kulcstere nagyon kicsi, csak 26 elemet tartalmaz, így számítógéppel nagyon gyorsan ki lehet próbálni az összes lehetőséget. Nagyobb kulcsterű eljárás az affin titkosítás, amelyre

P = C = {0,1,…, 25} és K = {(a,b) : 0 <= a,b, <= 25,(a,26) = 1}.

A titkosító függvény E(u,(a,b)) = au + b mod 26. Jelölje a- azt a 0 és 25 közötti egész számot, melyre aa- mod 26 = 1. Ilyen szám a xx fejezet szerint létezik és a kiterjesztett euklideszi algoritmussal meghatározható. A dekódoló kulcs (a-,b) és a visszafejtő függvény D(m,( a-,b) ) = a- (m-b) mod 26. Ebben az esetben a kulcstér mérete 26 φ(26) = 26 13 = 338, ami lényegesen nagyobb, mint a Caesar titkosításnál, de a gyakorlatban még mindig nagyon kicsi.

A Caesar és az affin titkosítás közös általánosítása a helyettesítéses titkosítás. Ekkor is teljesül, hogy P = C a kulcstér pedig a P permutációinak, azaz kölcsönösen egyértelmű leképezéseinek halmaza. Ha π a P egy permutációját jelenti, akkor E(u,π) = π(u). jelölje π- a π inverzét, akkor ez lesz a dekódoló kulcs és így D(m, π- ) = π- (m). Helyettesítéses titkosításnál a kulcstér nagy; ha |P| jelöli a P elemeinek számát, akkor K elemszáma nyilván |P|! A korábbi példáinkat tovább folytatva, ha P az angol abc betűinek halmaza, akkor |P| =26 és így K 26! = 403291461126605635584000000 ≈ 4,03 1027 . Ez már a gyakorlatban is elegendően nagy lenne, ha csak a kulcstér méretét tekintjük. Természetes nyelvekben készült szövegekre azonban a helyettesítéses titkosítás nem elég biztonságos, mert a karakterek előfordulásának a gyakorisága szigorú szabályoknak tesznek eleget, amelyek egyszerűvé teszik a kulcs és meghatározását és így a szöveg visszafejtését is. A részletekbe, a jegyzet keretei miatt nem térünk ki.

Az eddigiekben a betűnkénti, más terminológiával monoalfabetikus, titkosítás néhány egyszerű módszerét ismertettük. Ezek hiányosságai már a középkor végén is ismertek voltak, ezért biztonságosabb módszereket kerestek. Egy ilyen a Vigenére titkosítás, amelyet Blaise de Vigenére (1523–1596) francia diplomatáról neveztek el. A helyettesítéses titkosítás fő hibája, hogy a betűknek, azok minden előfordulásakor, ugyanazt a betűt feleltetik meg. Ki lehetne küszöbölni ezt a hiányosságot például úgy, hogy nem betűket, hanem betűcsoportokat helyettesítünk. Az ilyenek előfordulási gyakorisága már egyenletesebb, de a kódolás, különösen, ha azt kézzel végzik, nagyon elbonyolódik.

A Vigenére titkosítás során a simítást sokkal egyszerűbb eszközzel érjük el. A módszert ismét az angol abc-re ismertetjük. Készítsünk el egy olyan 26x26-os táblázatot, amelynek i-dik sora az abc i-dik betűjével kezdődik és az abc többi betűjével folytatódik úgy, mint azt a 8.2 ábrán bemutattuk. A kódoláshoz szükségünk van egy kulcsra, amely egy magunk választotta n betűs szó. Az üzenetet bontsuk fel n karakterből álló blokkokra úgy, hogy a szóközöket figyelmen kívül hagyjuk. Ha az üzenet hossza nem n többszöröse, akkor az utolsó blokk nem teljes. Írjuk a kódszót annyiszor egymás után az üzenet alá, ahány blokkot kaptunk (beleértve a nem teljes blokkot is). Ezek után egy blokkot úgy kódolunk, hogy megkeressük a blokk aktuális karakterét a táblázat első sorában, majd az alatta levő kódszó karaktert keressük meg a táblázat első oszlopában. Az a betű, amelyik a kiválasztott sor és oszlop találkozásában van, lesz a titkosított szöveg következő karaktere.

Tekintsük példaként ismét a „tizenegy orakor tamadunk” üzenetet és legyen a kulcs: „roham”. A kódolás eredményét a következő táblázatban találjuk:

A titkosított üzenetet az utolsó sorban találjuk. Látható, hogy most ugyanazon betű különböző előfordulásaihoz más betűt rendeltünk. Például a t betű első előfordulásához a k-t, míg a másodikhoz az f-et. Bár a Vigenére titkosítás során lényegesen egyenletesebb lesz a betűk előfordulásának gyakorisága, mit a helyettesítéses titkosítás után, a kódszó periodikus alkalmazása mégis elegendő statisztikai információt szolgáltat ahhoz, hogy finomabb elemzéssel nagyon gyorsan feltörhető legyen.

A Vigenére titkosítás formális leírásakor a betűk helyett, ugyanúgy, mint a Caesar titkosításnál, azok sorszámai halmazával dolgozunk. Ha az abc-ben m karakter van, akkor az abc-t azonosíthatjuk a {0,1,…,m-1} halmazzal, így P = C = K = {0,1,…,m-1}*, azaz az abc feletti véges szavak halmazával. Ha a titkosító kulcs, kt , hossza n, és az üzenet, u, hossza h, akkor bontsuk fel u-t n hosszúságú szavak konkatenációjára, azaz legyen u=u1…uk . Ekkor teljesül, hogy n(k-1) < h <= nk. Tegyük fel, hogy kt = kt1…ktn . Ha az u egyik részszava ui = ui1…uin , akkor

E(ui,kt) = (ui1 + kt1 mod m) … (uin + ktn mod m).

Az E függvényt minden egyes részszóra alkalmazni kell és az eredmények konkatenációja adja a titkosított szöveget. A dekódolás nyilvánvalóan ugyanúgy történik, mint a kódolás azzal a különbséggel, hogy nem hozzáadjuk, hanem kivonjuk a kódszó egyes „karaktereit”.

A 4. fejezetben említettük a Jefferson kereket, amely az első mechanikus titkosító eszköz volt. A XIX. majd a XX. században ezt az eszközt lényegesen tovább fejlesztették. A II. világháborúban a német hadsereg híres titkosító berendezése volt az ENIGMA. A szövetséges hadsered Normandiai partraszállásának sikerében fontos szerepet játszott, hogy az angol hadsereg zsákmányolt egy ENIGMÁ-t. A kriptoanalitikusoknak sikerült megérteni a működési elvét és így egyrészt megfejthették a németek üzeneteit, másrészt félrevezető üzeneteket küldhettek nekik. Teljesen más módszert választott az amerikai hadsereg a Csendes Óceáni hadműveletek során. Egy kis indián törzs, a navajok, tagjait alkalmazták üzenetek titkosítására. A törzs nyelvét nagyon kevesen beszélték, de elég kifejező volt ahhoz, hogy a hadvezetés üzeneteit le lehetett fordítani a navajo nyelvre. A fontos kommunikációs központokba tehát egy-egy navajo indiánt küldtek. Ők lefordították a parancsokat és elküldték azokat. A vevő oldalon is volt egy indián, aki megértette az üzenetet és visszafordította angolra, amit a helyi parancsnokok végre tudtak hajtani. Az amerikai hadsereg titkosítási módszerét nem tudták feltörni a világháborúban. Hasonlóan „titkosított” édesanyám és nagymamám. Amikor olyanról beszélgettek, amit nem akartak a gyerekek orrára kötni, akkor németre fordították a szót. Persze ez már nem működött akkor, amikor mi is megtanultunk németül. A titkosítás művészetéről szól Simon Singh nagyon olvasmányos könyve 16 .