Úloha 4.u1: Divné psaní (4 b)

Zadáno v čísle 22.4.

Řešeno v čísle 22.6.

Zadání

Vaším úkolem je dešifrovat následující vzkaz ve finštině (text byl před zašifrováním zbaven diakritiky, takže
používá pouze anglickou abecedu). Je to substituční šifra. Úkolem není nalézt český překlad, ale možná za něj bodík navíc bude.

Cbfb wjjxjj ysfnthuvbutuz vs guxxs bz znxvs ystss. Wngsxxs cbfbh gpbksh nzuyyswgnnz wbukjz xnthus, vswsxss, tnuzss vs fjbtbs, yjhhs ynhguggs zn kbuksh wsphhss ypbg ybzucjbxugnycss fskuzhbs, wjhnz gjbysuinz fsshnhhs vs xjbzzbzzuuhhpnz wsgknvs. Gpwgpxxs cbfbh wnfssksh ksfsfskuzhbs hsxkns ksfhnz gpbysxxs gunzus, vswsxsz vs tnuzunz xugswgu. Hsxknxxs, wjz fskuzhbs bz xjbzzbggs kstnyysz, cbfbh nhguksh nzguguvsugnghu vswsxss. Cbfb cpghppwuz tsughsyssz vswsxsz ynhfuz cswgjugnz tszrnz xscu. Ypbg tnuzswsgkuh vs ksfkjh wnxcssksh cbfbvnz fskuzzbwgu, vbg vswsxss nu bxn hsfcnnwgu gsshskuxxs. Vswsxughs cbfb gjbguu csxxnfbcbfbzvswsxss. Cbfbz fjjszgjxshjg pwguzwnfhsughjj hsxknxxs vs cbhguz ynfwuhpg bz nfuhhsuz kstsuznz. Cbfb yjughjhhss hsxkuguz pwguystsughs nxsuzhs vs hsxku ynfwuhgnn cbfbxxn xsuthjyughs vs vbcs ksuz tnzruggsgbxkusyughs. Cbfb ynznhhss hsxknxxs zbfyssxughuwuz zbuz kuuinzznwgnz csuzbghssz. Zpwpuguz pxnughpzph xugsfjbwuzhs bz yjjhhszjh huxszznhhs ynfwuhhsksghu.

Řešení

Naši agenti zjistili, že ukořistěná zpráva je zašifrována substituční šifrou. Budeme předpokládat, že jde o monoalfabetickou substituční šifru – tedy takovou, že se stejná písmena původního textu nahradí všechna tím samým písmenem. Luštění takové šifry je dost jednoduché na to, aby stálo za pokus, a navíc bychom nejspíš takto krátký text ani nebyli schopni rozluštit, pokud by byl zašifrovaný polyalfabetickou substituční šifrou (při jejím použití se substituce mění s pozicí nahrazovaného písmene ve zprávě; např. Vigenèrova šifra).

Klasickým způsobem luštění substitučních šifer je frekvenční analýza. Spočítáme výskyty znaků v šifrovaném textu, podělíme počty jeho délkou a získáme relativní četnosti. Ty porovnáme se známými hodnotami1 pro domnělý jazyk zprávy (v našem případě přičteme četnosti znaků s diakritikou (ä, ö) k četnostem odpovídajících znaků bez ní (a, o)), viz tabulka 1. Pokud je zpráva dostatečně dlouhá, dokážeme rekonstruovat substituci i automaticky.

Finština

a

i

n

t

e

l

m

r

j

15,8

10,8

8,8

8,8

8,0

7,9

6,1

5,8

5,0

5,0

3,2

2,9

2,2

2,0

Šifra

h

g

b

n

x

f

w

j

y

c

17,6

9,6

8,7

8,6

7,2

7,1

6,9

6,1

4,1

4,1

3,6

3,5

3,1

2,8

Tabulka 1: Relativní četnosti 14 nejčastějších znaků ve finštině a zašifrovaném textu (v procentech).

Jenže naše zpráva zřejmě není dost dlouhá. Můžeme si být docela jistí substitucí (s $\to $ a) a (u $\to $ i), ale dále už jsou rozdíly mezi četnostmi ve finštině a v šifře příliš velké (vzhledem k rozdílům mezi sousedními četnostmi znaků v šifře) na to, aby se dala substituce spolehlivě určit. Můžeme do hry zapojit také bigramy, či obecně $n$-gramy, tedy $n$-tice sousedních znaků v textu, ale obecně pro větší $n$ potřebujeme delší zprávu, aby rozložení $n$-gramů dostatečně odpovídalo jejich rozložení v jazyce.

Bylo tedy zapotřebí dalšího snažení. Pár příkladů pro inspiraci: Dr. Klára Stefanová si všimla, že slovo vs v šifře díky známé substituci (s $\to $ a) původně končilo na a a ve finštině neexistuje jiné takové dvoupísmenné slovo než ja. Získala tak substituci (v $\to $ j). Z častých finských koncovek alla, ella, illa odvodila, že dvojice xx před koncem slov bude ll. Dr. Anna Mlezivová se zaměřila na zdvojená písmena obecně a Bc. Jana Pallová zkoumala finské spojky, krátká slova a shluky souhlásek a samohlásek.

Důležitým krokem pak většinou bylo vyhledat částečné řešení na webu nebo jej prohnat překladačem a zjistit tak substituci pro zbylá písmena, případně opravit ta už dosazená.

Viděli jsme, že ruční rekonstrukce substituce může být docela mravenčí práce. Nemohli bychom ji nechat sestrojit počítač, pokud možno bez našich zásahů?

Ukážeme si jednu nepříliš chytrou metodu, která ale alespoň v tomto případě fungovala. Nejprve si seženeme slovník – co největší seznam finských slov.2 Pomocí něj budeme odhadovat, jestli je naše substituce správná. Postupně pro každý znak $x$ vyskytující se v šifře určíme znak $y$, kterým se bude nahrazovat, následovně: Projdeme všechny znaky $y$ z finštiny, kterými se zatím nic nenahrazuje, zkusíme vždy substituci rozšířit o (x $\to $ y) a zašifrovaný text částečně přeložit. Např. pokud zatím máme částečnou substituci (u $\to $ a), (n $\to $ r), slovo ysfnthuvbutuz přeložíme na ysfrthavbataz. Pro každé částečně přeložené slovo $S$ ověříme, jestli existuje doplnění substituce takové, abychom úplně přeložené slovo našli ve slovníku. (Projdeme každé slovo ve slovníku o stejné délce jako $S$ po znacích zleva doprava. Pokud příslušný znak slova $S$ ještě není přeložen, rozšíříme substituci o tuto dvojici znaků a celé $S$ dopřeložíme. Pokud je příslušný znak $S$ již přeložen, musejí se znaky shodovat. Neshodují-li se, toto slovo nevyhovuje, zahodíme změny substituce a jdeme na další slovo. Dojdeme-li až na konec slova, našli jsme pro $S$ oporu ve slovníku. Nezapomeneme vrátit substituci do stavu před $S$.) Vybereme pro $x$ takové $y$, aby se co nejvíce slov z textu dalo při nějakém doplnění substituce najít ve slovníku.

Tento algoritmus našel substituci, která se od té správné lišila jen ve dvou málo četných znacích (r a i, celkem 4 výskyty).

Podobný přístup zvolil Bc. Jan Gocník. K zašifrovaným slovům našel ve slovníku ta, na která by se mohla přeložit (např. cbfb na aili, eini, jere, …) a pro každé písmeno vyskytující se v šifře spočítal, kterému písmenu odpovídá v kolika slovech ve slovníku. Pak rozšířil svou substituci o nahrazení ($x \to y$), které mělo největší počet výskytů; přednostně však řešil nahrazování písmene, kterému zbývalo méně než sedm možností, na co se přeložit (pokud takové bylo). Pak přepočítal výskyty po aplikování tohoto nového pravidla a určil další nahrazení.

Dr. Jan Pokorný šifru luštil pomocí knihovny pycipher pro jazyk Python. Jeho algoritmus nejprve odhadl substituci na základě frekvenční analýzy. Následně zkoušel prohazovat dva náhodné znaky substituce a prohození přijal, pokud se zvýšilo skóre – součet logaritmů relativních četností (ve finštině) jednotlivých 4-gramů v dešifrovaném textu vynásobený $-1$ (neboť $\log p < 0$ pro $p \in (0,1)$).3 Ve chvíli, kdy přeložený text dostatečně připomínal finštinu, byla správnost klíče ověřena pomocí Google Translatoru.

Správná substituce, ke které se většina došlých řešení nakonec dobrala, je v tabulce 2.

Šifra

b

c

f

g

h

i

j

n

p

r

t

w

x

y

Finština

p

r

t

d

e

y

g

a

h

i

j

l

m

n

Tabulka 2: Substituce, která zprávu dešifruje.

S ní konečně můžeme zprávu dešifrovat, doplnit diakritiku, přeložit a číst:

Poro kuuluu märehtijöihin ja sillä on neljä mahaa. Kesällä porot syövät enimmäkseen koivun lehtiä, jäkälää, heinää ja ruohoa, mutta metsissä ne voivat käyttää myös monipuolisempaa ravintoa, kuten suomaiden raatetta ja luonnonniittyjen kasveja. Syksyllä porot keräävät vararavintoa talvea varten syömällä sieniä, jäkälän ja heinien lisäksi. Talvella, kun ravintoa on luonnossa vähemmän, porot etsivät ensisijaisesti jäkälää. Poro pystyykin haistamaan jäkälän metrin paksuisen hangen läpi. Myös heinäkasvit ja varvut kelpaavat porojen ravinnoksi, jos jäkälää ei ole tarpeeksi saatavilla. Jäkälistä poro suosii palleroporonjäkälää. Poron ruuansulatus yksinkertaistuu talvella ja pötsin merkitys on erittäin vähäinen. Poro muistuttaa talvisin yksimahaista eläintä ja talvi merkitsee porolle laihtumista ja jopa vain hengissäselviämistä. Poro menettää talvella normaalistikin noin viidenneksen painostaan. Nykyisin yleistynyt lisäruokinta on muuttanut tilannetta merkittävästi.

Sob je přežvýkavec a má čtyři žaludky. V létě sobi jedí převážně březové listy, lišejníky, seno a trávu, ale v lesích mohou jejich stravu doplňovat i bažinné vachty a jiné traviny. Na podzim si vytvářejí tukové zásoby na zimu, kromě lišejníků a sena se živí i houbami. V zimě, kdy je jídla nedostatek, sobi vyhledávají hlavně lišejníky. Jsou schopni je vycítit pod metrovou vrstvou sněhu. Pokud mají nedostatek lišejníků, spokojí se i s trávou a polokeři. Ze všech lišejníků preferují Dutohlávku horskou (finský název doslova „Lišejník sobí“, pozn. překl.). V zimě je zažívání sobů zjednodušeno, bachor ztrácí svůj význam. Sobi v zimě připomínají monogastrická zvířata (s jedním žaludkem, pozn. překl.). Zima pro ně znamená úbytek na váze a pouhé přežívání. Obvykle ztratí až pětinu své tělesné hmotnosti. Dnes rozšířené přikrmování ale situaci výrazně změnilo. (Volně podle Bc. Jana Gocníka a Dr. Jana Pokorného.)

Matěj


1) Relativní četnosti znaků ve finštině: http://practicalcryptography.com/cryptanalysis/letter-frequencies-various-languages/finnish-letter-frequencies/

2) Např. z https://invokeit.wordpress.com/frequency-word-lists/

3) Toto skóre je vlastně cross-entropie (chybí jen vydělení počtem všech 4-gramů v textu), používaná na porovnání dvou pravděpodobnostních rozdělení (v našem případě rozdělení 4-gramů v textu a ve finštině). Pro diskrétní pravděpodobnostní rozdělení $p$ a $q$ je jejich cross-entropie definovaná jako $H(p,q) = -\sum _ x p(x) \log q(x)$.