7. Kryptosekuritné problémy vzorové riešenie

Muhaha ahoj Taylor,

konečne sme ťa dostali. Tvoj počítač je v našich rukách a s ním aj všetky
tvoje nevydané pesničky.

Tvoj disk sme zašifrovali neprelomiteľnou šifrou a je len na tebe, ako budeš
ďalej pokračovať. Ako výkupné požadujeme len málo. Tvoj červený šál.

S pozdravom,
Tvoji najväčší fanúšikovia.

ab
abcdd

3

Bruteforce

Prvé pozorovanie, ktoré môžeme spraviť je, že všetkých permutácií, ktorými mohol byť disk zašifrovaný, je strašne veľa. Určite teda nemôžeme vyskúšať všetky permutácie. Čo ale môžeme spraviť je, pre každú pozíciu v \(T\) vyskúšať, či sa na nej môže začínať \(P\).

To môžeme spraviť napríklad tak, že postupne prechádzame písmenkami a konštruujeme permutáciu, pre ktorú sa bude \(P\) nachádzať v \(T\) (počínajúc daným indexom). Časová zložitosť tohto algoritmu bude \(O(|T| |P|)\), čo stačí na prejdenie prvej sady.

Kanonický tvar

Jedno slovo sa nám môže zašifrovať na veľa iných. Preto by sme chceli spomedzi všetkých týchto slov nejaké vybrať a prehlásiť ho za kanonický tvar daného slova. Môžeme si všimnúť, že ak majú dve slová \(A\) a \(B\) rovnaký kanonický tvar \(K\), tak sa jedno mohlo zašifrovať na druhé.

Zo slova \(A\) vieme dostať slovo \(K\) nejakou permutáciou. Rovnako aj zo slova \(B\) vieme dostať \(K\) nejakou permutáciou. Inverz tejto permutácie je tiež permutácia, preto aj z \(K\) vieme nejakou permutáciou dostať \(B\). Keď tieto dve permutácie spolu zložíme, dostaneme ďalšiu permutáciu, ktorá z \(A\) spraví \(B\).

Ak naopak slová \(A\) a \(B\) nemajú rovnaký kanonický tvar, tak sa nemôže jedno zašifrovať na druhé. To platí preto, lebo ak by sa z \(A\) dalo vytvoriť nejakou permutáciou \(B\), tak by množina všetkých slov, na ktoré sa dá \(A\) zašifrovať, bola rovnaká ako množina slov, na ktoré sa dá zašifrovať \(B\). Keďže sú ale tieto množiny rovnaké, tak by \(A\) a \(B\) museli mať rovnaký kanonický tvar, čo je spor.

Ako si vyberieme tento kanonický tvar? Dobre napríklad funguje lexikograficky najmenší reťazec. Ten vieme dostať tak, že postupne prechádzame dané slovo a pamätáme si najmenšie nepoužité písmenko. Ak natrafíme v slove na nové písmenko, tak mu v permutácií priradíme najmenšie nepoužité písmenko a zvýšime ho o \(1\).

Optimálne riešenie

V prípade, že by disk nebol nijakým spôsobom zašifrovaný, tak by táto úloha bola celkom štandardná. Stačí len nájsť vzorku v texte, čo dokážeme pomocou KMP alebo rolling hashov (Rabin-Karp). Ak by sa nám teda podarilo nejak previesť slová na ich kanonické tvary, tak by sa z úlohy stala úloha riešiteľná jedným z týchto algoritmov.

Z týchto algoritmov si vyberieme rolling hash. Previesť reťazec \(P\) do kanonického tvaru a spočítať jeho hash je triviálne. Zaujímavejšie je, ako počítať postupne hashe úsekov reťazca \(T\).

Budeme klasicky počítať hodnoty polynómu \(T_i \cdot p^{k-1} + T_{i+1} \cdot p^{k-2} \cdots + T_{i+k-1} \cdot p^{0} \mod q\) pre každý úsek dĺžky \(|P|\). Keďže ale chceme počítať hodnotu hashu pre kanonickú reprezentáciu substringu \(T[i:i+k]\), tak si ešte potrebujeme udržiavať permutáciu, pomocou ktorej z tohto substringu dostaneme jeho kanonický tvar.

Keď sa toto okno posunie doprava nastanú dve veci. Ako prvé treba odčítať prvý člen polynómu, zvýšiť všetky exponenty o \(1\) a nakoniec pripočítať člen reprezentujúci pribudnuté písmeno. Keďže sa zmenilo prvé písmeno nového reťazca, tak sa mohla aj zmeniť permutácia, ktorou z tohto reťazca dostaneme jeho kaninocký tvar.

Táto permutácia je určená pozíciami prvých výskytov jednotlivých písmen. Preto si budeme navyše udržiavať pre každé písmeno frontu s indexmi v aktuálnom okne, na ktorých sa nachádza dané písmeno. Podľa prvých prvkov z týchto front potom usporiadame permutáciu \(1\) až \(26\), čím dostaneme hľadanú permutáciu.

Aby sme teraz vedeli zmeniť písmená, ktoré sú koeficientami v polynóme touto novou permutáciou, rozdelíme si tento polynóm na súčet \(26\) polynómov. Každý z týchto polynómov bude obsahovať rovnaké koeficienty (teda to budú členy prislúchajúce nejakému písmenu).

Keď sa hodnota nejakého písmena zmení v permutácií z \(a\) na \(b\), tak stačí polynóm tohto písmena vynásobiť hodnotou \(a^-1 \cdot b\). To platí preto, lebo všetky koeficienty majú hodnotu \(a\), teda vynásobením touto hodnotou sa zmenia všetky zmenia na \(b\). Keď potom chceme zistiť, či nastala zhoda, stačí hodnoty týchto polynómov sčítať a porovnať s hashom reťazca \(P\).

Keďže abeceda má konštantnú veľkosť, tak substringy, ktoré hashujeme, vieme posúvať v konštantnom čase. Časová zložitosť je preto \(O(|T| + |P|)\). Pamäťová zložitosť je tiež \(O(|T| + |P|)\).