Domácí úkoly z předmětu Kryptoanalytické útoky
Lineární kryptoanalýza 1
Jednoduchá šifra
V následujícím úkolu budeme pracovat s velice jednoduchou blokovou šifrou, která má velikost bloku pouhé 4 bity. Klíč sestává ze tří čtyřbitových podklíčů k1, k2, k3, což dohromady dává 12 bitů klíče. Šifra dále využívá jeden S-box se čtyřbitovým vstupem i výstupem.
Šifrový text y se z otevřeného textu x spočítá podle předpisu:
y = k3 ⊕ S-box(k2 ⊕ S-box(k1 ⊕ x)).
Vzorová implementace šifry zde.
Domácí úkol č. 4
E-mailem dostanete dvojice otevřeného a šifrového textu, které byly všechny zašifrované stejným klíčem. Společně s těmito dvojicemi dostanete lineární aproximační tabulku S-boxu šifry. Samotný S-box však neznáte. Vašim úkolem je určit všechny tři podklíče. Použijte Matsuiho první algoritmus k sestavení soustavy lineárních rovnic o 12 neznámých (bity klíče). Tyto potom můžete vyřešit například v Mathematice nebo v GAPu (viz níže).
Všechna zadání mají vlastnost, že když při sestavování rovnic budete vycházet z aproximací S-boxu, které mají v absolutní hodnotě bias alespoň 4/16, pak lze klíč určit jednoznačně.
Příkladem zadání, které odpovídá shora uvedené vzorové implementaci je uvedeno níže. S-box bude samozřejmě jiný. Důvod, proč nemáte k dispozici S-box je pouze, abyste nemohli provést útok hrubou silou.
Dvojice otevreneho a sifroveho textu:
0 9
1 b
2 1
3 0
4 e
5 5
6 2
7 f
8 4
9 d
a a
b 8
c 3
d c
e 7
f 6
Linearni aproximacni tabulka S-boxu
0 1 2 3 4 5 6 7 8 9 a b c d e f
0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 2 -2 2 -2 2 2 2 2 -4 0 4 0
2 0 0 0 0 -4 0 0 4 0 4 4 0 0 0 0 0
3 0 4 0 4 2 -2 -2 2 2 2 -2 -2 0 0 0 0
4 0 0 2 2 0 -4 2 -2 -4 0 2 -2 0 0 -2 -2
5 0 -4 2 -2 2 -2 -4 0 2 2 0 0 0 0 -2 -2
6 0 0 -6 2 0 0 -2 -2 0 0 2 2 0 0 -2 -2
7 0 0 2 2 -2 2 -4 0 -2 -2 0 0 -4 0 2 -2
8 0 -2 2 4 0 2 2 0 0 2 -2 4 0 -2 -2 0
9 0 2 2 0 -2 0 0 -2 2 0 0 2 0 6 -2 0
a 0 2 2 0 0 2 -2 -4 0 2 2 0 4 -2 2 0
b 0 2 2 0 2 0 0 2 2 -4 4 2 0 -2 -2 0
c 0 2 0 -2 0 2 0 -2 0 2 0 -2 -4 -2 -4 2
d 0 2 0 -2 -2 -4 -2 0 -2 0 -2 4 0 -2 0 2
e 0 -2 0 2 -4 -2 0 -2 4 -2 0 -2 0 -2 0 2
f 0 2 0 -2 -2 0 2 0 2 0 -2 0 0 -2 0 -6
Soustavy lineárních rovnic
V Mathematice
K řešení soustavy lineárních rovnic nad konečným tělesem můžete v Mathematice použít příkaz:
LinearSolve[matice_soustavy, vektor_pravych_stran, Modulus->2]
Tento příkaz najde pouze partikulární řešení. Nezapomeňte tedy ověřit, že řešení je jednoznačně určeno. Nejjednodušší je zkontrolovat hodnost matice:
MatrixRank[matice_soustavy, Modulus -> 2]
V GAPu
V GAPu najdete partikulární řešení příkazem:
IntVecFFE(SolutionMat(TransposedMat(matice_soustavy * One(GF(2))), vektor_pravych_stran * One(GF(2))));
Hodnost zjistíte příkazem:
RankMat(matice_soustavy * One(GF(2)));
Vysvětlení GAPu
Vektory a matice se v GAPu vytvářejí pomocí hranatých závorek, např. [[1,0,1],[0,1,1]] je matice typu 2×3.
Operátor přiřazení je stejně jako v Pascalu := a každý příkaz se zakončuje středníkem.
Příkaz One(GF(q)) vrací jednotkový prvek tělesa Fq. Když tímto prvkem přenásobíme vektor nebo matici hodnot, dostaneme matici nad Fq.
Autoři GAPu vyznávají Bicanovu filozofii řádkových vektorů. Příkaz SolutionMat(A, b) tedy řeší soustavu ve tvaru xA = b. Matice soustavy se proto musí oproti našemu zvyku transponovat.
IntVecFFE převádí vektor prvků konečného tělesa na celá čísla.
Python
Při vaší práci vám může přijít vhod následující funkce, která vrací paritu 16 nejnižších bitů zadaného čísla.
def parity16(a):
a ^= a >> 8
a ^= a >> 4
a ^= a >> 2
return (a ^ (a >> 1)) & 1
Pokud budete potřebovat převést 12bitové číslo na seznam bitů od nejvýznamnějšího k nejméně významnému bitu, můžete seznam vytvořit například takto:
[cislo >> i & 1 for i in range(11,-1,-1)]
© 2007–2024 Andrew Kozlík