Cvičení 7: Aplikace: kódování a kryptografie
Teorie:
(n, k)—kódy: přenášíme slova o k bitech, přičemž potřebujeme rozpoznávat/opravovat přenosové chyby a za tím účelem přidáváme dodatečných n — k bitů informace pro pevně zvolené n > k.
Hammingova vzdálenost (bitových slov): počet bitů, v nichž se dvě bitová slova liší. Kód odhaluje r a méně chyb právě, když je minimální Hammingova vzdálenost kódových slov právě r + 1. Kód opravuje r a méně chyb právě, když je minimální Hammingova vzdálenost kódových slov právě 2r + 1.
Polynomiální kódy: Polynomiální kód generovaný polynomem p(x) je (n, A;)-kód jehož slova jsou polynomy stupně menšího než n dělitelné p(x). Zpráva m(x) je zakódována jako v(x) = r(x) + xn~km(x), kde r(x) je zbytek po dělení polynomu xn~km(x) polynomem p{x).
Zprávu b^bi... bk-i reprezentujeme polynomem m{x) = Ďq + b\x + • • • + 6fc-i^fc_1-Lineární kódy: matice G typu k/n reprezentující zobrazení u = G-v, kde v je zpráva, u odpovídající kódové slovo, ve standardních bazích, se nazývá generující matice kódu.
Věta 1. Je-li g lineární kódováni s maticí
má následující vlastnosti
1. Ker h = Ira g, tj.
2. přijaté slovo u je kódové slovo právě, když je H ■ u = 0
Matice H se nazývá matice kontroly parity kódu. Hoidnota H ■ u se nazývá syndrom
• každý účastník A potřebuje dvojici klíčů - veřejný Va a soukromý Sa
• generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, tp(n) = (p—l)(q— 1) [n je veřejné, ale íp(ri) nelze snadno spočítat ]
• zvolí veřejný klíč e a ověří, že (e, f(n)) = 1
• např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e-d = 1 (mod f(n))
potom zobrazení h : (Z2)n —> (Z2)fc s maticí
H = (En_fc P)
slova u.
RSA:
1
• zašifrování numerického kódu zprávy M: C = Ce(M) = Me (mod n)
• dešifrování zprávy C: OT = D^C) = Cd (mod n)
Obdobně je možné zprávy podepisovat - vytvoří se tzv. hash zprávy (my v příkladech budeme pro jednoduchost používat krátké zprávy, které budou svým vlastním hashem), ten se „zašifruje" pomocí d a připojí ke zprávě. Ověření podpisu se děje analogicky jako při dešifrování zprávy.
Výměna klíčů Diffie-Hellman
• Dohoda stran na cyklické grupě G (obvykle Zp) a jejím generátoru g (veřejné)
• Alice vybere náhodné a a pošle ga
• Bob vybere náhodné b a pošle gb
• Společným klíčem pro komunikaci je gab. Šifrování ElGamal:
• každý účastník A potřebuje dvojici klíčů - veřejný Va a soukromý Sa
• generování klíčů: zvolí velké prvočíslo p, generátor g grupy Z*, dále náhodné 1 < a < p — 1 a vypočte e = ga (mod p). Zveřejní [p, g, e], tajný klíč je a.
• zašifrování numerického kódu zprávy M: zvolí náhodně 1 < k < p — la vypočte c = gk (mod p) a C = M ■ ek (mod p). Pošle [c, C].
• dešifrování zprávy [c, C\. OT = c~a ■ C.
Příklad 112. Určete polynom, který generuje (4, l)-kód opakování bitů.
Příklad 113. Určete nějaký ireducibilní polynom stupně 4 nad Z2 a zakódujte pomocí něj zprávu 11010.
Příklad 114.     1. Určete matici lineárního kódu generovaného polynomem p(x) = 1 + x2 + x3. Zapište příslušnou kontrolní matici.
2. Dekódujte zprávu 111101, předpokládáte-li, že při přenosu došlo k nejmenšímu možnému počtu chyb.
Příklad 115. Binární slovo délky 11 je zakódováno pomocí polynomu p(x) = x4 + x3 + 1. Příjemce obdržel slovo 011101110111001.
1. Ukažte, že při přenosu došlo k chybě.
2. Určete původní slovo za předpokladu, že chyba při přenosu byla jediná.
Příklad 116. Uživatel Adam si zvolil prvočísla p = 31, q = 83, vypočetl n = 31 -83 = 2573 a veřejný klíč e = 77.
2
1. Zašifrujte zprávu m = 14 pro Adama.
2. Adam poslal zprávu m = 5, kterou podepsal číslem 56. Ověřte, že je to jeho podpis a že zpráva nebyla pozměněna.
3. V pozici Adama vypočtěte tajný klíč d a zprávu z 1. dešifrujte.
Příklad 117. Martin a Honza chtějí komunikovat, přestože se dosud neměli šanci potkat. Veřejně se domluvili na cyklické grupě Z^. Martin si zvolil generátor grupy 11a číslo 10 a zveřejnil trojici (41,11, e), kde e = ll10 (mod 41).
1. V roli Honzy dokončete DH protokol výměny klíče a určete klíč pro následnou komunikaci.
2. Honza poslal Martinovi dvojici [22, 6]. V roli Martina zprávu zašifrovanou protokolem ElGamal dešifrujte.
3. Se znalostí zprávy (viz výsledek předchozího úkolu) ukažte, jak Honza šifroval (možností šifrování zprávy je více, pracujte s k = 23; dokázali byste toto k snadno určit se znalostí c a gl).
3