Šifra XYZ

Tato šifra potrápila účastníky hry TMOU nejvíc. I když je jasné jak ji řešit, postup byl natolik pracný, že nad ní některé týmy strávily i čtyři hodiny a stejně to nakonec museli vzdát.

Všechny týmy (alespoň podle informací, které máme) luštili šifru první metodou, která se přímo nabízí:

METODA STROMU

Touto metodou lze začít luštit šifru v kterémkoliv místě, ale nejjednodušší je to od začátku nebo z míst, kde začíná slovo. Lze tak lépe hodnotit, kterou větví postupovat dál. Princip je jednoduchý. Zapíšeme písmena, která by mohla být zapsána v daném bodě šifry. Podle toho z kolika znaků se každé písmeno skládá na něj navazují další možná písmena. Tyto se tedy opět připíší... a tak stále dál. Písmen přibývá a strom se větví. I když mnoho větví postupně zaniká, protože nedávají smysluplná slova, těch "nadějných" je stále víc a víc.
 

Tab. 1

J T U V
J K L A B H R A I S J T Y
A B H R A I S J T Y A I S J T Y J O E J T Y J O E E J T Y Z J T Y Z

Ukázalo se, že i pětičlenný tým, který si ideálně rozdělil práci si s tím nedokázal rychle poradit.

V okamžiku, kdy si tým toto uvědomil a začal přemýšlet o problému novým způsobem, mohl dosáhnout ve srovnání s ostatními zajímavých výsledků. Jedniný tým, o kterém víme, že toto udělal, byl FIMAN. (Z jejich dopisu není zřejmý přesný postup, ale to co jsem na jejich námět napsal zřejmě funguje :o) - Radek)

Úkol zněl, jak urychlit řešení této šifry??? A řešení bylo překvapivě jednoduché!

Při pohledu na výše uvedenou tabulku je vidět, že mnoho písmen se ve stromu opakuje (např. sekvence JTY v třetím řádku). Stačilo tedy změnit způsob zápisu, tak aby se tyto sekvence na papíře zbytečně neopakovaly. Ideální se ukázala být tabulka, kdy nad každým místem šifry byly postupně zapsány všechny znaky, které mohly v daném místě začínat. Tento způsob se ukázal jako velmi úsporný na prostor. Horší to je s orientací v textu při hledání slov. Je totiž třeba přeskakovat mezi sloupci podle toho jak je poslední znak dlouhý. V tabulce se však objevila zajímavá závislost, která může řešení velmi urychlit.
 

Tab.2

Délka zašifrovaného znaku
4 V R Z M
3 U L H S Y Y P N L C N
2 T K B I T O T O F I K D F I K B D K D F
1 J J A A J J E J J E A J A E A J A A E J A E A
Šifra -->  Z Z X X Z Z Y Z Z Y X Z X Y X Z X X Y Z X Y X

Po vyznačení textu řešení do tabulky mne zarazilo, že se písmena řešený vyskytují, až na jedinné, na vrcholcích sloupců. Zkusil jsem další slova šifry.
 

Tab. 3

Délka zašifrovaného znaku
4 M R V M
3 L C L H S U L H L C
2 K B D F I K B I T K B B I K B D
1 J A A E A J A A J J A A A J A A E E
Šifra --> Z X X Y X Z X X Z Z X X X Z X X Y Y

Tab. 4

Délka zašifrovaného znaku
4 M R
3 L C P N C H S U
2 K I K B D O F D K D B D B I T T T K
1 J A J A A E J E A E J A E A A E A A J J J J A
Šifra --> Z X Z X X Y Z Y X Y Z X Y X X Y X X Z Z Z Z X

Je jasné, že výskyt řešení na vrcholcích sloupců není náhoda. Důvodem je zřejmě nízká pravděpodobnost výskytu smysluplného dlouhého řetězce v šifře, jinými slovy, když už čtyři znaky za sebou mohou být písmeno, tak to není náhoda, ale většinou právě toto písmeno. Existují samozřejmě výjimky (např. viz. Tab. 3 a Tab. 4) pravděpodobnost jejich výskytu je však výrazně nižší.
Tuto závislost nelze brát jako stoprocentní, vymyslel jsem i slova, kde tohle neplatilo, ale zřejmě je lepší od písmen na vrcholcích začít.

Vaše případné komentáře, nápady a matematická zdůvodnění jsou očekávány :o) - Radek