Cvičení 7: Aplikace: kódování a kryptografie
Teorie:
(n, k)—kody: přenášíme slova o k bitech, přičemž potřebujeme rozpoznávat/opravovat přenosové chyby a za tím účelem přidaváme dodatečných n — k bitu informace pro pevne zvolene n > k.
Hammingova vzdálenost (bitovách slov): pocet bitu, v nichz se dve bitová slova liší. Kád odhaluje r a mene chyb práve, kdyz je minimalní Hammingova vzdalenost kódových slov prave r + 1. Kod opravuje r a mene chyb prave, kdyz je minimalní Hammingova vzdalenost kOdových slov práve 2r + 1.
Polynomiální kódy: Polynomialní kod geneřovaný polynomem p(x) je (n, k)-kod jehoz slova jsou polynomy stupne mensího nez n delitelne p(x). Zpráva m(x) je zakodovana jako v (x) = r(x) + xn-k m(x), kde r(x) je zbytek po delení polynomu xn-k m(x) polynomem p(x).
Zprávu bob\... bk-1 reprezentujeme polynomem m(x) = bo + &ix + • • • + bk-1xfc-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í kodove slovo, ve standardních bazích, se nazíva generující matice kodu.
Veta 1. Je-li g lineárni kódováni s matici
potom zobrazeni h : (Z2)n —>■ (Z2)k s matici
H = (En_k P)
mi následujici vlastnosti
1. Ker h = Im g, tj.
2. prijaté .slovo u je kidove .slovo prive, kdyz je H • u = 0
Matice H se nazéyvé matice kontroly parity kédu. Hoidnota H • u se nazéyva syndrom slova u.
RSA:
• kazdí ucastník A potřebuje dvojici klícu - veřejní VA a soukromí SA
• geneřování klícu: zvolí dve velkí prvocísla p, q, vypocte n = pq, t/?(n) = (p —       — 1) [n je veřejne, ale t/?(n) nelze snadno spocítat ]
• zvolí verejná klíč e a oveří, ze (e, </?(n)) = 1
• např. pomocí Euklidova algoritmu spocítá tajná klíč d tak, aby e• d = 1 (mod </?(n))
1
• zašifrování numerického kódu zprávy M: C = Ce(M) = Me (mod n)
• dešifrování zprávy C: OT = Dd(C) = Cd (mod n)
Obdobné je možné zprávy podepisovat - vytvorí še tzv. hašh zprávy (my v prokladech budeme pro jednoduchost pouzívat krátke zprávy, ktere budou švym vlastním hašhem), ten še „zašifruje" pomocí d a pripojí ke zpríve. Overení podpisu še deje analogicky jako pri dešifrovóní zprávy.
Výměna klíčů Diffie-Hellman
• Dohoda štran na cýklickě grůpě G (obvykle Zp) a jejím generátoru g (verejne)
• Alice vybere náhodne a a pošle ga
• Bob vybere níhodne b a pošle gb
• Spolecním klíccem pro komunikaci je gab. Šifrovaní ElGamal:
• kazdí ucaštník A potrebuje dvojici klícu - verejní VA a šoukromí SA
• generovíní klíccu: zvolí velke prvoďšlo p, generítor g grupy     , dále níhodne 1 < a < p — 1a vypocte e = ga (mod p). Zverejní [p, g, e], tajny klíc je a.
• zašifrovíní numerickeho kodu zprávy M: zvolí níhodne 1 < k < p — 1a vypocte 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.
Príklad 112. Urcete polynom, ktery generuje (4,1)-kod opakovíní bitu.
Príklad 113. Urcete nejakí ireducibilní polynom štupne 4 nad Z2 a zíkodujte pomocí nej zprávu 11010.
Príklad 114.     1. Urcete matici lineárního kodu generovaneho polynomem p (x) = 1 + x2 + x3. Zapište príšlušnou kontrolní matici.
2. Dekídujte zprávu 111101, predpokládáte-li, ze pri prenošu došlo k nejmenšímu moznemu poctu chyb.
Príklad 115. Binární šlovo delky 11 je zakódováno pomocí polynomu p(x) = x4 + x3 + 1. Príjemce obdrzel šlovo 011101110111001.
1. Ukazte, ze pri prenošu došlo k chybe.
2. Urcete puvodní šlovo za predpokladu, ze chyba pri prenošu byla jediná.
Príklad 116. Uzivatel Adam ši zvolil prvocíšla p = 31, q = 83, vypocetl n = 31 • 83 = 2573 a verejní klíc e = 77.
2
1. Zašifrujte zprávu m =14 pro Adama.
2. Adam pošlal zprávu m = 5, kterou podepsal číšlem 56. Overte, ze je to jeho podpiš a Ze zprava nebyla pozmenena.
3. V pozici Adama vypočtete tajný klíč d a zpravu z 1. dešifrujte.
Příklad 117. Martin a Honza chtejí komunikovat, preštoze še došud nemeli šanci potkat. Verejne še domluvili na cyklicke grupe Z^. Martin ši zvolil generator grupy 11a číšlo 10 a zverejnil trojici (41,11, e), kde e = 1110 (mod 41).
1. V roli Honzy dokoncete DH protokol vymeny klíce a urcete klíc pro našlednou komunikaci.
2. Honza pošlal Martinovi dvojici [22, 6]. V roli Martina zpravu zašifrovanou protokolem ElGamal dešifrujte.
3. Se znaloští zprývy (viz výšledek predchozího ýkolu) ukazte, jak Honza šifroval (moznoští šifrovíní zpravy je více, pracujte š k = 23; dokazali byšte toto k šnadno urcit še znaloští c a g?).
3