4. sada úloh (celkem 22b, max 16b za tuto sadu)
Úloha 1 (6 bodů)
Předpokládejme, že máme šifru lDES, která se od šifry DES liší pouze v tom, že používá jiné S-boxy. A to takové, že každý S-box $S:\mathbb{Z}^6_2 \rightarrow \mathbb{Z}^4_2$ šifry lDES je lineární. Dokažte, že šifra lDES je afinní v klíči i plaintextu, neboli
\[
\forall k_1,\,k_2,\,p \in \mathbb{Z}^{64}_2: lDES_{k_1+k_2}(0) = lDES_{k_1}(p) + lDES_{k_2}(p)
\]
\[
\forall p_1,\,p_2,\,k \in \mathbb{Z}^{64}_2: lDES_{0}(p_1+p_2) = lDES_{k}(p_1) + lDES_{k}(p_2)
\]
Zkuste to třeba tak, že afinitu dokážete pro základní funkce (bitová rotace, bitový výběr, přičtení klíče), potom pro části šifry (odvození klíče, Feistelova funkce, runda) a nakonec pro celou šifru. Využijte toho, že funkce je lineární nad $\mathbb{Z}_2$, pokud každý výstupní bit funkce je lineární kombinací vstupních bitů.
Úloha 2 (2 + 2 body)
Napište funkci
invert, která najde v tělese $\mathbb{Z}_2[x]/(x^8+x^7+x^2+x+1)$ pro prvek, který dostane jako parametr, jeho inverz. Pokud inverz pro tento prvek neexistuje, pak vyhodí chybu. Prvky tohoto tělesa na vstupu/výstupu budou reprezentovány jako 8-bitové číslo (podobný trik jako u Rijndael S-boxu šifry AES).
Uvažme Rijndael S-box šifry AES nad tímto tělesem (tj. matice zůstává, jen výpočet inverzu bude jiný). Zjistěte, jakou hodnotu dostaneme z tohoto S-boxu, když na jeho vstupu bude číslo
0xf3. Na tuto část můžete (ale nemusíte) využít funkci
invert z předchozího odstavce.
Pozn.: Hlavička funkce by měla býti následující (opět C# notace, jiné jazyky analogicky):
byte invert(byte element)
Úloha 3 (0 + 6 bodů)
export2DES
Klíčem této šifry je blok o šesti bajtech
\[
k_1:k_2:k_3:k_4:k_5:k_6
\]
takový, že jednotlivé bajty $k_i$ mají lichou paritu (tedy lichý počet bitů s hodnotou jedna). Šifrování probíhá následovně: Nejprve jsou odvozeny klíče
\[
a=k_1:k_2:k_3:01:01:01:01:01
\]
\[
b=k_4:k_5:k_6:01:01:01:01:01
\]
Ciphertextem plaintextu $p$ je potom $DES^{-1}_b(DES_a(p))$.
Plaintext (hexadecimálně)
00:01:02:03:04:05:06:07 byl šifrou export2DES zašifrován na
B0:20:23:51:D7:0E:AF:D7. Najděte odpovídající klíč.
Na
této stránce najdete návod, jak implementovat DES v různých programovacích jazycích. Upozorňuji, že útok může, v závislosti na jeho implementaci a zvoleném programovacím jazyce, trvat i několik minut.
Úloha 4 (1 bod)
Ze standardu jsem vypustil jedno omezení pro k. Dokážete přijít na to jaké?
Úloha 5 (2 body)
Ukažte, že neexistují dvě různé zprávy, které by se shodovaly po přidání paddingu.
Úloha 6 (3 body)
Předpokládejme, že blok má délku 8 bajtů. Jaká je pravděpodobnost, že uniformně náhodně zvolená zpráva o dvou blocích bude mít korektní padding? Kolik bajtů bude padding nejpravděpodobněji mít?
1. Osmice bitů, tedy jeden bajt.