LUŠTĚNÍ MONOALFABETICKÉ SUBSTITUCE
V minulé Výhni jsem vám dost nerozvážně slíbil, že vám napíšu
něco o luštění monoalfabetické substituce, a tak to tady po nocích
píšu, abyste se nebouřili.
Monoalfabetická substituce je nejjednodušší šifra, a proto by
měla být lehce luštitelná. Pamatujete-li si Ceasarovu šifru tak víte,
že její luštění je velice jednoduché. Stačí vyzkoušet jen tolik
kombinací, kolik je písmen v použité abecedě. Ale použijeme-li jinou
metodu šifrování, s luštěním bude problém, kombinací by totiž mělo
být n!, kde n je počet písmen abecedy. Několik kombinací bude dávat
smysl, ale jen jedna bude správná.
Na luštění je několik metod, které se různě kombinují, podle
typu zašifrování. Jsou-li v textu zašifrována jen písmena, můžeme
určit slova podle vzhledu textu. Můžeme použít speciálního umístění
oslovení, podpisu nebo v anglosaských jazycích umístění členu.
Máme-li např. v angličtině trojpísmenné slovo je vysoká
pravděpodobnost, že půjde o určitý člen "the". U tohoto dešifrování
se používá testování krátkých slov jako zájmen, spojek či předložek.
Je-li zašifrována i mezera je situace podobná, protože potom je
mezera nejčetnější znak textu. Problémy nastanou, až když jsou
vypuštěny mezery, čárky a interpunkční znamínka.
Jinou metodou luštění je metoda luštění podle četnosti znaků.
Známe-li jazyk zprávy a zpráva je dostatečně dlouhá na to, aby se
v ní minimalizovaly statistické odchylky, můžeme podle četnosti znaků
určit skupinu znaků, které to či ono písmeno zastupuje. Dešifrování
probíhá tak, že správu vyhodnotíme, zjistíme četnosti znaků, srovnáme
je podle velikosti a porovnáme s tabulkou. Znak neurčíme
stoprocentně, protože několik znaků má stejnou pravděpodobnost
výskytu. K dešifrování je potřeba lidské kreativity, a odhalovat
zprávu písmeno po písmenu, doplňovat nedokončená slova a tím získávat
další znaky. Je potřeba dobrá znalost jazyka a velká slovní zásoba.
Samozřejmě, že člověka může zastoupit počítač s lexikonem výrazů
a slovních spojení. Předkládám vám sem tabulku četnosti písmen
v textu anglickém a českém. Luštit se dá i podle četnosti dvojic,
trojic až n-tic znaků. Tyto tabulky nemám ale v Technické knihovně se
dají sehnat knihy, které je obsahují.
+------------------------------------------------+
| Četnosti znaků |
+-------------------+----------------------------+
| S DIAKRITIKOU | BEZ DIAKRITIKY |
+-------------------+-------------------+--------+
| česky | česky s mezerou |anglicky|
| | | |
|a 0,054 | a 0,065 | 0,0856 |
|á 0,021 | b 0,012 | 0,0139 |
|b 0,014 | c 0,024 | 0,0279 |
|c 0,019 | d 0,031 | 0,0378 |
|č 0,008 | e 0,107 | 0,1304 |
|d 0,026 | f 0,023 | 0,0289 |
|ď 0,005 | g 0,013 | 0,0199 |
|e 0,073 | h 0,043 | 0,0526 |
|é 0,01 | i 0,056 | 0,0627 |
|ě 0,007 | j 0,001 | 0,0019 |
|f 0,002 | k 0,003 | 0,0042 |
|g 0,002 | l 0,028 | 0,0339 |
|h 0,02 | m 0,02 | 0,0249 |
|i 0,034 | n 0,058 | 0,0707 |
|í 0,025 | o 0,067 | 0,0797 |
|j 0,022 | p 0,016 | 0,0199 |
|k 0,033 | q 0,001 | 0,0012 |
|l 0,034 | r 0,052 | 0,0977 |
|m 0,029 | s 0,05 | 0,0607 |
|n 0,04 | t 0,086 | 0,1045 |
|ň 0,015 | u 0,021 | 0,0249 |
|o 0,068 | v 0,008 | 0,0092 |
|ó 0 | w 0,016 | 0,0149 |
|p 0,027 | x 0,001 | 0,0017 |
|q 0 | y 0,016 | 0,0199 |
|r 0,029 | z 0,001 | 0,0008 |
|ř 0,009 | mezera 0,182 | |
|s 0,04 | | |
|š 0,008 | | |
|t 0,039 | | |
|ť 0,007 | | |
|u 0,03 | | |
|ů 0,005 | | |
|v 0,039 | | |
|w 0 | | |
|x 0,001 | | |
|y 0,016 | | |
|ý 0,008 | | |
|z 0,019 | | |
|ž 0,009 | | |
|mezera 0,163 | | |
+-------------------+-------------------+--------+
Luštění polyalfabetických šifer je mnohem složitější. Zde musíme mít
několik zpráv zašifrovaných stejným klíčem. Máme-li totiž několik
zpráv můžeme je luštit jako monoalfabetické. Vezmeme-li totiž např.
všechna n-tá písmena tak ty jsou zašifrovány pomocí stejného znaku,
takže můžeme postupovat jako u šifry monoalfabetické. Dá se také
luštit polyalfabetická šifra s krátkým klíčem. Zjistíme-li totiž
délku klíče, můžeme vzít znaky v intervalu délky klíče a zase
dostaneme monalfabetickou šifru. Délka klíče se dá určit pomocí
opakování n-tic znaků. Zjistíme-li vzdálenosti opakováni n-tic znaků,
něco zanedbáme a vypočteme jejich největšího společného dělitele,
výsledek by nám měl dát délku klíče. Ale u těchto metod může být
odchylka od tabulek natolik vysoká, že bude nepoužitelná. A to je asi
tak všechno co jsem vám chtěl prozradit, chcete-li se dovědět něco
navíc, můžete se mně zeptat nebo si to nastudovat sami z knihovny.
HIPP
výheň