Úloha 1 (3 body)

Uvažme abecedu $\mathbb{A}=\mathbb{Z}_{27}$. Najděte čísla $k,\,l \in \mathbb{Z}_{27}\backslash\{0\}$ taková, že existují dvě různé zprávy takové, že se při použití dvojice $(k, l)$ jako klíče afinní šifry zašifrují na stejný šifrový text. Pokud neexistuje takováto dvojice čísel, pak zdůvodněte proč.

Úloha 2 (3 + 2 body)

Def.: (Izomorfismus šifer)
Nechť $S_1=(\mathcal{P},\mathcal{C},\mathcal{K}_1,E_1,D_1)$ a $S_2=(\mathcal{P},\mathcal{C},\mathcal{K}_2,E_2,D_2)$ jsou šifry. Řekneme, že $S_1$ a $S_2$ jsou izomorfní, jestliže existují zobrazení $f:\mathcal{K}_1\rightarrow\mathcal{K}_2$ a $g:\mathcal{K}_2\rightarrow\mathcal{K}_1$ taková, že
$\forall k \in \mathcal{K}_1\forall x\in\mathcal{P}:E_1(k,x)=E_2(f(k),x)$
$\forall k \in \mathcal{K}_2\forall x\in\mathcal{P}:E_2(k,x)=E_1(g(k),x)$

Jelikož se šifrování stává velice popularizovaným tématem, tak svou šanci zavětřil i obratný obchodník Kolík Aťsepicnu. Ovšem běžně šifry jako AES nebo DES se mu zdají zbytečně komplikované a obskurní, proto se rozhodl vytvořit svůj vlastní šifrovací algoritmus — KAS (Kohlik Advanced Security). Tento algoritmus má klíč složený ze 3 čísel: $a,\,b \in \mathbb{Z}_{256},\ c \in \mathbb{Z}_{256}^*$. Šifruje znak po znaku a to tak, že prvně aplikuje na znak $x$ Caesarovu šifru s klíčem $a$ a následně aplikuje afinní šifru se zbylými parametry $b,\,c$ ($y \mapsto yc + b$). Všechny tyto operace probíhají v $\mathbb{Z}_{256}$ (tj. Caesarova šifra je nad 256 znakovou abecedou).
Rozhodněte, zda-li je KAS izomorfní (neformálně řečeno: je v podstatě stejná) s nějakou ze šifer, ze kterých je konstruována. Naimplementuje tuto šifru ve vašem oblíbeném programovacím jazyce. Krom odpovědi na otázku týkající se složení šifer odevzdejte i zdrojový kód.
Pozn.: Pokud budete pracovat v silně typovaném jazyce, pak problém s modulární aritmetikou za vás vyřeší dostatečně malý (8 bitů — např. v C++ unsigned char) datový typ.

Pozn.: Implementace budu testovat mj. vybranými vstupy. Hlavičky funkcí k naimplementování (C# notace, pro ostatní jazyky analogické datové typy) by měly vypadat následovně:

• byte[] encrypt(byte[] plaintext, byte key_a, byte key_b, byte key_c)
• byte[] decrypt(byte[] ciphertext, byte key_a, byte key_b, byte key_c)

Úloha 3 (2 + 2 body)

Def.: (Index koincidence)
Nechť $x=(x_1,\,x_2,\dots,\,x_n)$ je posloupnost znaků. Index koincidence $I_c$ definujeme jako pravděpodobnost, že dva náhodně vybrané znaky $x_i$ a $x_j$, pro $i \neq j$, jsou stejné.

Spočtěte index koincidence pro náhodný textový řetězec (tj. pravděpodobnosti výskytu jsou pro všechny znaky stejné) složený ze znaků anglické abecedy $\mathbb{A}=\{A,\,B,\dots,\,Z\}, |\mathbb{A}|=26$.
Napište program, který pro zadaný text (standardní vstup) spočte a vypíše index koincidence s přesností na 3 desetinná místa. Pro jednoduchost můžete uvažovat text složený pouze z velkých písmen anglické abecedy.