2. sada úloh (21b celkově, maximálně lze získat 19b)
Úloha 1 (2 body)
Buď $p$ prvočíslo, $n$ přirozené číslo. Spočtete počet matic invertibilních matic typu $n \times n$ nad $\mathbb{Z}_p$. Využijte toho, že čtvercová matice nad tělesem je invertibilní právě tehdy, když má lineárně nezávislé řádky.
Úloha 2 (6 bodů)
Velký výrobce praček ŠumavaMat se rozhodl jít s dobou a vrhnout se po hlavě do tzv. Internet of Things. V rámci tohoto rozhodnutí byly do praček přidány čipy pro bezdrátové připojení k internetu a pračky bylo možné ovládat pomocí telefonu disponujícím mobilní aplikací od výrobce. Jelikož bylo zapotřebí vydat produkt co nejdříve, tak se vedení rozhodlo nezabezpečovat přístup k pračce přes tuto aplikaci.
Bohužel se po chvíli začaly množit zprávy o pračkách "samovolně" měnících režim v průběhu praní. Bylo tedy rozhodnuto, že je zapotřebí vyvinout zabezpečovací protokol. Tento protokol byl nazván WPS (Washing-machine Protected Setup). WPS umožnil uživateli připojit se k pračce zadáním 8místného PINu (natištěn na štítku pračky) v mobilní aplikaci.
Vývojář Tomáš Frikulín měl tento protokol implementovat, ale jelikož mu zrovna vyšel nový seriál, tak si chtěl zkrátit čas strávený testováním. Protokol navrhl tak, že aplikace pošle 8 číslic (číslice 0-9), pračka ověří, jestli je první polovina číslic správně, jestli je druhá polovina správně a nakonec jestli součet prvních sedmi číslic dá číslici osmou (mod 10). Výsledek všech těchto tří testů pošle pračka zpět aplikaci. Pračka dovolí přístup jen pokud všechny tři testy dopadly úspěšně.
Spočtěte střední hodnotu počtu PINů, které musí vyzkoušet náhodně tipující útočník, aby uhádl správný PIN. Navrhněte co nejlepší způsob jak zlepšit (tj. snížit počet PINů, které musí útočník vyzkoušet v nejhorším případě) útok hrubou silou. Spočtěte kolik PINů musí při použití navrženého zlepšení útočník vyzkoušet (v nejhorším případě), aby mohl získat přístup k ovládání pračky. Celkově jsou alespoň 3 možnosti jak prohledávání zlepšit a některá jdou dohromady kombinovat.
Pozn.: Třetí test (součet číslic) probíhá jen na zaslaném PINu. Tj. zkontroluji, jestli součet prvních sedmi číslic zaslaného pinu dá osmou číslici zaslaného PINu.
Úloha 3 (6 bodů)
Ve starém archivu BBC se našlo několik šifrovaných spisů. Spisy byly nalezeny u šifrovacího zařízení značky
MP Vigenere, které je známé tím, že místo rotace abecedy používá operaci XOR (exclusive or). Návod přiložený k přístroji uvádí, že je schopen pracovat s 32 znakovou abecedou (
!',.;?ABCDEFGHIJKLMNOPQRSTUVWXYZ); interně si tyto znaky reprezentuje pořadovým číslem v abecedě (0-31) a operace XOR probíhá právě na těchto číslech. Kdybychom tedy zašifrovali zprávu "ZPRAVA" klíčem
"KLIC", pak dostaneme šifrový text
"J;TIFR".
Bohužel se historikům nepodařilo některé texty dešifrovat, a proto se rozhodli tento úkol svěřit studentům Kryptografických systémů za domácí úkol. Níže je zpráva, kterou máte za úkol dešifrovat.
NHKHY;''DKGAC!ZW'MH!.TWSZXTCGAOM,RDSE.HPYU';!HY;X'JB'XXNGNNBLQXNJ!HYUEXE.BER;GNIYTG.'GH.TG.'JNGFHDSDNYF.Q;BYYE.UA;FNTTDSE.GYC'GQHI!RMNHKHY;.JGYY;UVGNNWBO.GKESF.Q;BYYE.BZOUZBOBHNZ?ERX';E!EA;JH!Q!UBZK!TTTS';EHE.;JB?!L;HXOGHXXWGNZHE.;JBOY!VB'QNYUR;GNIYTHVV?NUFTYTN!!DRN'HLYE.UA;FNTTDSDNYLDUVHPHY;DSKIX!O,MOIQO;BZSLTTBMGNNB,URMO'HE.;JBOEYU'FNZBU,BZHZXTUVNH!UBAXGE?M;BCGNHISUUR,O!O;YAMEMD,XG!RB'KCVMOHLQXNJCG!OVYK!RM
Pozn.: Texty jsou psané v anglickém jazyce, relativní frekvence znaků ve zdrojovém textu jsou:
! | " | , | . | ; | ? | A | B | C | D | E |
0.015 | 0.01 | 0.021 | 0.022 | 0.0 | 0.005 | 0.075 | 0.016 | 0.022 | 0.034 | 0.106 |
F | G | H | I | J | K | L | M | N | O | P |
0.014 | 0.027 | 0.06 | 0.061 | 0.001 | 0.012 | 0.044 | 0.022 | 0.06 | 0.076 | 0.013 |
Q | R | S | T | U | V | W | X | Y | Z |
0.002 | 0.054 | 0.053 | 0.079 | 0.037 | 0.009 | 0.023 | 0.001 | 0.025 | 0 |
Slovník:
{'U': 0.037, 'B': 0.016, 'D': 0.034, 'M': 0.022, 'T': 0.079, 'K': 0.012, 'I': 0.061, 'R': 0.054, 'O': 0.076, 'L': 0.044, 'V': 0.009, 'H': 0.06, '.': 0.022, "'": 0.01, '?': 0.005, 'Y': 0.025, '!': 0.015, 'C': 0.022, 'N': 0.06, 'E': 0.106, 'S': 0.053, ',': 0.021, 'F': 0.014, 'Q': 0.002, 'P': 0.013, 'J': 0.001, 'A': 0.075, 'G': 0.027, 'Z': 0.0, ';': 0.0, 'W': 0.023, 'X': 0.001}
Pole četností (dle pořadí v abecedě):
[0.015, 0.01, 0.021, 0.022, 0.0, 0.005, 0.075, 0.016, 0.022, 0.034, 0.106, 0.014, 0.027, 0.06, 0.061, 0.001, 0.012, 0.044, 0.022, 0.06, 0.076, 0.013, 0.002, 0.054, 0.053, 0.079, 0.037, 0.009, 0.023, 0.001, 0.025, 0.0]
Úloha 4 (2 body)
Zpráva v anglickém jazyce byla zašifrována třemi šiframi (Hillova šifra, substituční šifra a transpoziční šifra). Dokážete přiřadit šifry k jednotlivým ciphertextům? Zdůvodněte svou odpověď.
- TTEDEHAOLEDIPIRATEOHISSNOTNINWHGDIAERTMTOAHTLEFE
- TORPQKTFBPPGVIIXVIFXKJDLFLRQAHZOMQAUSDJXSSFIOGET
- LNUFULMCVUFODUHMLCOZCWWNOEZCZLNUFCMYHMKLOLNUVUJL
Úloha 5 (2 body)
Def.: Index vzájemné koincidence dvou textových řetězců je pravděpodobnost, že náhodně vybraný znak z prvního řetězce je stejný jako náhodně vybraný znak z řetězce druhého.
Buď $e_k$ šifrovací zobrazení Caesarovy šifry s klíčem $k \in \mathbf{A}$. Dokažte, že pro libovolný plaintext $p$ a klíč $k$ platí: $I_c(p, e_k(p))\leq I_c(p, p)$, kde $I_c$ je index vzájemné koincidence. Bude se vám hodit Cauchy-Schwarzova nerovnost.
Úloha 6 (3 body)
Zachytili jsme ciphertexty dvou zpráv, které byly zašifrované Vernamovou šifrou:
- JVQ!WCRBNWKNNRKMSGLMO.YE.?MYVCPXH?ANQNEARXLCXT
- GO.UQV.;SZ?NOOS?PMNCTXCJVICF;BE'NETNXCN?JKHUMD
Pokuste se, alespoň částečně, zjistit obsah zpráv, jestliže víte, že obě zprávy jsou šifrované stejným klíčem, jsou psané v anglickém jazyce (abeceda jako v úloze 3) a druhá zpráva obsahuje slovo "JABBERWOCKY". Šifrovací přístroj používal stejnou abecedu (a převod do číselné reprezentace) jako přístroj z úlohy 3.