3. sada úloh (23b, maximálně je možné obdržet 18b)

Úloha 1 (3 body)

Pro každý z následujících kódů najděte náhodnou veličinu, jejímž Huffmanovým kódem daný kód je, nebo dokažte, že taková veličina neexistuje.

Úloha 2 (4 body)

Ukažte, že každý Huffmanův kód $\mathcal{C}$ je prefix-free, tj. $\forall x, y \in \mathcal{C}\ \forall z \in \{0,1\}^*\backslash\varepsilon: x \neq y || z$.

Úloha 3 (0 + 5 body)

Naimplementujte jednotlivé součásti SPN (tj. permutace na bitech, S-Box, přičítání klíče). Délka bloku je 16 bitů, vrstva S-Boxů obsahuje 4 S-Boxy (každý s šířkou 4 bity) a klíče má stejnou délku jako blok. Složte pak tyto funkce v pořadí key_addition, sbox, permutation, abyste vytvořili rundovní funkci.
Permutace pošle bit z pozice $i$ (zleva) na pozici $(i\ div\ 4) + (i\ mod\ 4) \times 4$. Pokud vstupní 4 bity do S-Boxu interpretujeme jako číslo (nejnižší bit vpravo), pak S-Box zobrazí posloupnost $(0,\,1,\dots,\,15)$ na posloupnost $(0,\, 4,\, 8,\, 12,\, 1,\, 5,\, 9,\, 13,\, 2,\, 6,\, 10,\, 14,\, 3,\, 7,\, 11,\, 15)$. Aplikujte tuto rundovní funkci na hodnotu 0xf00d pro libovolný klíč.

Pozn.: Testovat implementace budu mj. vybranými vstupy. Hlavičky funkcí k naimplementování (C# notace, pro ostatní jazyky analogické datové typy; word je ekvivalent ushort pro Pascal) by měly vypadat následovně:

Doporučuji si vyzkoušet tzv. bit-twiddling, tj. místo pole bitů používat bitové operace (např. ((input & 0x00f0) >> 4) mi získá druhou čtveřici bitů (zprava) z proměnné input; operátor & provede operaci AND po bitech, operátor >> mi posune všechny bity doprava o uvedený počet pozic a zleva "doplní" nulami).

Úloha 4 (5 body)

Def.: Latinský čtverec
Mějme $n \in \mathbb{N}$ a zobrazení $L:\{1,\dots,n\}\times\{1,\dots,n\} \rightarrow {1,\dots,n}$. Pro každé $i \in \{1,\dots,n\}$ definujme zobrazení $L_i(x):=L(i,x)$ a $L^i(x):=L(x,i)$. Pak řekneme, že L je latinský čtverec, jestliže pro všechna $i \in \{1,\dots,n\}$ jsou zobrazení $L_i$ a $L^i$ bijekce.
Latinský čtverec velikosti $n$ si můžeme představit jako tabulku velikosti $n \times n$, která má na pozici $(i,j)$ číslo $L(i,\, j)$, tj. v každém řádku i sloupci obsahuje každé číslo z množiny $\{1,\dots,n\}$ právě jednou.
Def.: Latinský kryptosystém
Mějme latinský čtverec L velikosti $n \in \mathbb{N}$. Latinský kryptosystém odvozený z L je kryptosystém $(\mathbb{P}, \mathbb{C}, \mathbb{K}, E, D)$, kde $\mathbb{P}=\mathbb{C}=\mathbb{K}=\{1,\dots,n\}$ a $E_k(c)=L(k,c)$ pro všechna $k \in \mathbb{K}$ a $c \in \mathbb{C}$.

Buď $n \in \mathbb{N}$, mějme kryptosystém $(\mathbb{P}, \mathbb{C}, \mathbb{K}, E, D)$, kde $\mathbb{P}=\mathbb{C}=\mathbb{K}=\{1,\dots,n\}$. Předpokládejme, že každý klíč je používám se stejnou pravděpodobností $\frac{1}{n}$. Dokažte, že tento kryptosystém je absolutně bezpečný právě tehdy, když je Latinským kryptosystémem. Nezapomeňte, že plaintexty mohou mít jakoukoliv distribuci.

Úloha 5 (3 body)

Najděte šest poloslabých klíčů šifry DES. Dvojice klíčů $(k_1,\ k_2)$ se nazývá poloslabá, pokud $DES_{k_1}\circ DES_{k_2}=Id$.
Mějte na mysli, že dešifrování probíhá podobně jako šifrování, ale rundovní klíče se používají v opačném pořadí.

Úloha 6 (3 body)

Vezměme číslo 0xf00dbeef1334. Jakou hodnotu dostaneme, když toto číslo použijeme jako vstup do 8 paralelně zapojených DES S-boxů? (Tj. jaký výstup dostaneme z vrstvy S-boxů ve funkci $f$ v DES, když jako vstup do této vrstvy použijeme právě číslo 0xf00dbeef1334?)