Matematika IV - demonstrační cvičení
Michal Bulant 4. dubna 2011
7. demonstrační cvičení
Polynomiální kód generovaný polynomem p(x) je (n, k)-kod jehož slova jsou polynomy stupne menšího než n delitelne p(x). Zprava m(x) je žakodovóna jako v(x) = r (x) + xn_k m(x), kde r (x) je žbytek po delení polynomu xn_km(x) polynomem p(x).
Pozor, konvence: Zpravu bo&i • • • bk_i reprezentujeme polynomem m(x) = b0 + b1x + • • • + bk_1xk_1.
Príklad 1. Zakódujte zprávu 1101 pomoci (6,4) kodu generovaného polynomem 1 + x + x2.
i
Matice G typu n/k reprezentující zobrazení u = G • v, kde v je zpráva, u odpovídající kódove slovo, ve standardních bazích, se nazyva generující matice kodu.
Je-li g linearní kódovaní s maticí
kde P je matice typu (n — k)/k, potom zobrazení h : (Z2)n —>• (Z2)n k s maticí
H = (En—k P)
mía níasledující vlastnosti
1. Ker h = Im g, tj.
2. prijate slovo u je kídove slovo prave, kdyz je H • u = 0
Matice H se nazíví matice kontroly parity kídu. Hodnota H • u se nazyívía syndrom slova u.
Příklad 2. Určete generující matici a matici kontroly parity pro lineární kod (7,4) generovaný polynomem
x3 + x2 + 1.
2
Příklad 3. a) Určete generující matici a matici kontroly parity pro lineární kod (9,4) generovaný polynomem
1 + x2 + x4 + x5.
b) Vypočtete čast tabulky syndromů a vedoucích reprezentantů pro tento kod. Kolik bude mít radku?
c) Jakí nejvyssí pocet chyb detekuje/opravuje tento kod?
d) Dekódujte slova 100110010,100100101,111101100 a 000111110.
3
RSA:
• každý účastník A potřebuje dvojici klíčů - veřejný VA a soukromý
S a;
• generovaní klíčů: žvolí dve velka prvočísla p, q, výpočte n = pq, </?(n) = (p—1)(q—1) [n je veřejne, ale </?(n) nelže snadno spočítat.];
• žvolí veřejný klíč e a oveří, že (e, </?(n)) = 1;
• např. pomočí Euklidova algoritmu spočíta tajný klíč d tak, abý e • d = 1 (mod ^(n));
• žasifrovaní numeričkeho kodu žprívý M: C = Ce(M) = Me (mod n);
• dešifrovím sifřý C: OT = Dd(C) = Cd (mod n).
Příklad 4. Alice si za parametry svého RSA klice zvolila p = 23, q = 31, e = 17. Dopočítejte jejésoukromý kléc a pomocémoduiarného umocňované na druhou (s mocným pouňitém kalkulačky) zašifrujte (a poté dešifrujte) zprávu m = 12.
4
Diffie-Hellman key exchange, ElGamal
Výměna klíčů pro symetrickou kryptografii bez předchozího kontaktu (tj. náhrada jednorýzových klíčů, kuryrU s kufríky, ...).
• Dohoda stran na cyklicke grupe G a jejím generátoru g (verejne)
• Alice vybere nýhodne a a posle ga
• Bob vybere nýhodne b a posle gb
• Spolecným klícem pro komunikaci je gab.
• Puvodní (a nejobvyklejsí) volba G je multipliktivní grupa inver-tibilních zbytkových tríd modulo prvocíslo p, její generýtor byva take nazývam primitivní kořen modulo p .
• Problem diskretnýho logaritmu (DLP)
• Nezbytna autentizace (man in the middle attack)
Z protokolu DH na výmenu klýcu odvozen šifrovací' algoritmus ElGamal:
• Alice zvolí cyklickou grupu G spolu s generýtorem g
• Alice zvolí tajný klíc x, spocítý h = gx a zverejní veřejný klíc
• sifrovaní zpravy M: Bob zvolí nahodne y a vypocte C\ = gy a C2 = M • hy a posle (Ci,C2)
• desifrovýní zprývy: OT = C2/Cf
Příklad 5. Demonstrujte dohodu Alice a Boba na tajnem klíči v DH systému na výměnu klíčů se (všem,) známými parametry G = (Z23, •), g = 5.
5
Příklad 6. Alice zvolila za parametry v kryptosystému ElGamal p = 23, g = 5, za svůj soukromý klíc zvolila x = 13 a zveřejnila veřejný klíc (p,g,gx). Ukažte, jak Bob zašifruje zprávu M = 17 určenou Alici a jak tuto zpmvu nasledne Alice dešifruje.
6