Úvod do kódování oooooooooooooooooo Pár slov o šifrách ooooooooo Matematika IV - 6. přednáška Kódování a šifrování Michal Bulant Masarykova univerzita Fakulta informatiky 27. 3. 2013 Úvod do kódování Pár slov o šifrách oooooooooooooooooo ooooooooo Obsah přednášky Q| Úvod do kódování • (n, k)-kódy • Lineární kódy Qi Pár slov o šifrách Martin Panák, Jan Slovák, Drsná matematika, e-text. Předmětové záložky v IS MU R. B. Ash, Abstract algebra, http://www.math.uiuc.edu/~r-ash/Algebra.html. Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone , Handbook of Applied Cryptography, CRC Press, 2001, 780 p., http://www.cacr.math.uwaterloo.ca/hac/ Jan Paseka, Kódování, elektronický text, MU - http://www. math.muni.cz/~paseka/ftp/lectures/kodovani.ps. Při přenosu informace zpravidla dochází k její deformaci. Budeme pro jednoduchost pracovat s modelem, kdy jednotlivé částečky informace jsou bud' nuly nebo jedničky (bity, tj. prvky v Z2) a přenášíme slova o k bitech. Obdobné postupy jsou možné i nad ostatními konečnými tělesy. Přenosové chyby chceme O rozpoznávat O opravovat a za tím účelem přidáváme dodatečných n — k bitů informace pro pevně zvolené n > k. Tak dostaneme tzv. (n, /c)-kód. Všech slov o k bitech je 2k a každé z nich má jednoznačně určovat jedno kódové slovo z 2" možných. Máme tedy ještě 2"_2^_2^(2" k_1) slov, která jsou chybová. Lze tedy tušit, že pro veliké k nám i malý počet přidaných bitů (tj. n — k) dává hodně redundantní informace. Úvod do kódování o»oooooooooooooooo Pár slov o šifrách ooooooooo Jednoduchým příkladem je kód kontrolující paritu. Kódové slovo o k + 1 bitech je určené tak, aby přidáním prvního bitu byl zaručen sudý počet jedniček ve slově. Pokud při přenosu dojde k lichému počtu chyb, přijdeme na to. Dvě různá kódová slova se při tomto kódu vždy liší alespoň ve dvou pozicích, chybové slovo se ale od dvou různých (vhodných) kódových slov liší pouze v pozici jedné. Nemůžeme proto umět chyby opravovat, ani kdybychom věděli, že došlo k právě jedné chybě. Navíc neumíme detekovat tak obvyklé chyby, jako je záměna dvou sousedních bitů ve slově. Úvod do kódování oo»ooooooooooooooo Pár slov o šifrách ooooooooo 011 010 ^^001 á 110 000 |101 100 Definice Hammingova vzdálenost dvou slov je rovna počtu bitů, ve kterých se liší. O 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. O Kód opravuje r a méně chyb, právě když je minimální Hammingova vzdálenost kódových slov právě 2 r + 1. Úvod do kódování ooo#oooooooooooooo Pár slov o šifrách ooooooooo Jak konstruovat kódová slova, abychom je snadno rozpoznali? Kontrolu parity jsme už viděli, další triviální možnost je prosté opakování bitů - např. (3, l)-kód bere jednotlivé bity a posílá je třikrát po sobě. Systematickou cestou je pak využití dělitelnosti polynomů. Zpráva fao^i • • • bk-i Je reprezentována jako polynom m(x) = bQ + bix H-----h bk^xk^. Definice Nechť p(x) = ao + a\x + • • • + an-i 3. O Polynom p(x) = 1 + x + x2 generuje pro k = 1 (3, l)-kód opakování bitů. První tvrzení plyne z toho, že 1 + x dělí polynom v(x) tehdy a jen tehdy, když v(l) = 0 a to nastane tehdy, když je ve v(x) sudý počet nenulových koeficientů. Druhé je zřejmé. Úvod do kódování ooooo»oooooooooooo Pár slov o šifrách ooooooooo ' Příklad Uvažme polynom p(x) = 1 + x + x2 pro n = 5,/c = 3. Kódovými slovy jsou 0 • p(x), 1 • p(x), x • p(x), (x + 1) • p(x),... ,(x2+x + l)-p(x), tj. kódování slov je následující 000 ^ 000 00 001 ^ 00111 010 ^ 010 01 011 ^ 01110 100 ^ 100 10 101 ^ 10101 110 ^ 11011 111 ^ 11100 Úvod do kódování Pár slov o šifrách oooooo^ooooooooooo ooooooooo Přenos slova veZJ dopadne příjmem polynomu u(x) = v(x) + e(x) kde e(x) je tzv. chybový polynom reprezentující vektor chyby přenosu. Chyba je rozpoznatelná pouze, když generátor kódu p(x) nedělí e(x). Máme proto zájem o polynomy, které nevystupují jako dělitelé příliš často. Definice Ireducibilní polynom p(x) £ 2^[x] stupně m se nazývá primitivní, jestliže p(x) dělí polynom xk — 1 pro k = 2m — 1 ale nedělí jej pro žádná menší k. Úvod do kódování ooooooo»oooooooooo Pár slov o šifrách ooooooooo Věta Je-li p(x) primitivní polynom stupně m, pak pro všechna n < 2m — 1 rozpoznává příslušný (n, n — m)-kód všechny jednoduché a dvojité chyby. Důsledek Je-li q(x) primitivní polynom stupně m, pak pro všechna n < 2m — 1 rozpoznává (n, n — m — l)-kód generovaný polynomem p(x) = q(x)(l + x) všechny dvojité chyby a všechna slova s lichým počtem chyb. Úvod do kódování oooooooosooooooooo Pár slov o šifrách ooooooooo Tabulka dává informace o výsledcích předchozích dvou vět pro několik polynomů: primitivní polynom kontrolní bity délka slova 1 + x + x2 2 3 1 + x + x3 3 7 1 + x + x4 4 15 1 + x2 + x5 5 31 1 + x + x6 6 63 1 + x3 + x7 7 127 1 + x2 + x3 + x4 + x8 8 255 l+x4 + x9 9 511 l+x3 + x10 10 1023 Definice Lineární kód je injektivní lineární zobrazení g : {1>2)k —> (^2)"-Matice G typu k/n reprezentující toto zobrazení v standardních bazích se nazývá generující matice kódu. Pro každé slovo v je u = G ■ v příslušné kódové slovo. Úvod do kódování Pár slov o šifrách oooooooooo«ooooooo ooooooooo Věta Každý polynomiální (n, k)-kód je lineární kód. Generující matice (7,4)-kódu příslušná k polynomu p(x) = 1 + x2 + x3 je 1 1 o\ 0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 \o 0 0 1/ Úvod do kódování Pár slov o šifrách 00000000000*000000 ooooooooo Věta Je-li g : {1>2)k —> (^2)" lineární kódování s maticí 6 O- potom zobrazení h : (Z2)" —> (^2)'lk s maticí H = (E„-/r P) má následující vlastnosti O Ker h = \mg, tj. @ přijaté slovo u je kódové slovo, právě když je H ■ u = 0 Matici H z věty se říká kontrolní matice příslušného (n, /c)-kódu. Jak jsme viděli, přenos zprávy u dává výsledek v = u + e. To je ale nad Z2 ekvivalentní s e = u + v. Pokud tedy známe podprostor V c (Z2)" správných kódových slov, víme u každého výsledku, že správné slovo (s opravenými případnými chybami) je ve třídě rozkladu v + V prostoru (Z2)"/V. Zobrazení (homomorfismus grup) h : (Z2)" —>■ {1^2)" k má V za jádro, proto indukuje injektivní lineární zobrazení h : (7j2)n/V —> [%2)nk- Jeho hodnoty jsou jednoznačně určeny hodnotami H • u. Úvod do kódování ooooooooooooo»oooo Pár slov o šifrách ooooooooo Definice Hodnota H ■ u se nazývá syndrom slova u. Věta Dvě slova jsou ve stejné třídě rozkladu právě tehdy, když mají týž syndrom. Samoopravné kódy lze konstruovat tak, že pro každý syndrom určíme prvek v příslušné třídě, který je nejvhodnějším slovem. Úvod do kódování oooooooooooooo»ooo Pár slov o šifrách ooooooooo Příklad Bud' dán (6,3)-kód nad Z2 generovaný polynomem x3 + x2 + 1. 9 Určete jeho generující matici a matici kontroly parity. O 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. Řešení Protože se jedná o lineární kód, stačí určit jak se zakódují bázové vektory 1, x a x2, tedy určit zbytky polynomů x3, x4 a x5 po dělení polynomem x3 + x2 + 1. Máme x3 = x2 + 1 (mod x3 +x2 + 1) x4 = x(x3) = x(x2 + 1) = x2 + x + 1 (mod x3 + x2 + 1) x5 = x(x4) = x(x2 + x + l)=x + l (mod x3 + x2 + 1) Úvod do kódování ooooooooooooooo»oo Pár slov o šifrách ooooooooo Řešení (pokr.) Bázové vektory (zprávy) 100, 010 a 001 se tedy zakódují do vektorů (kódů) 101100, 111010 a 110001, generující matice, resp. matice kontroly parity kódu jsou tedy '1 0 0 1 1 r resp. H = [ 0 1 0 0 1 1 ,0 0 1 0 0 1, n 1 1\ 0 1 1 1 1 0 1 0 0 0 1 0 Vo 0 1/ Vynásobíme-li prijatou zprávu 111101 maticí kontroly parity, dostáváme syndrom 100 a víme, že při přenosu došlo k chybě. Sestavme tabulku všech syndromů a jim odpovídajících kódových slov. Úvod do kódování oooooooooooooooo»o Pár slov o šifrách ooooooooo Syndrom Slova s daným syndromem 000 000000 110001 111010 101100 010110 001011 011101 100111 001 001000 111001 110010 100100 011110 000011 010101 101111 010 010000 100001 101010 111100 000110 011011 001101 110111 100 100000 010001 011010 001100 110110 101011 111101 000111 011 011000 101001 100010 110100 001110 010011 000101 111111 101 101000 011001 010010 000100 111110 100011 110101 001111 110 110000 000001 001010 011100 100110 111011 101101 010111 111 111000 001001 000010 010100 101110 110011 100101 011111 Úvod do kódování 00000000000000000» Pár slov o šifrách ooooooooo Řešení (dokončení) Syndrom 000 mají všechna kódová slova. Počínaje druhým řádkem, je každý řádek tabulky afinním prostorem jehož zaměřením je vektorový prostor daný prvním řádkem. Zejména je tedy rozdíl každých dvou slov ve stejném řádku nějakým kódovým slovem. Všechna slova s daným syndromem dostaneme přičtením syndromu (doplněného nulami na délku kódového slova) ke všem kódovým slovům. Tzv. vedoucím reprezentantem třídy (řádku, afinního prostoru) odpovídající danému syndromu je slovo s nejmenším počtem jedniček v řádku, a tedy i nejmenším počtem bitových změn, jež je třeba provést, abychom dostali kódové slovo -v našem případě jde o slovo 100000 a jeho odečtením od obdrženého slova dostaneme platné kódové slovo 011101. Je to platné kódové slovo s nejmenší Hammingovou vzdáleností od obdrženého slova. Odeslaná zpráva tedy byla 101. Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks,GCHQ - 1973) • každý účastník A potřebuje dvojici klíčů - veřejný a soukromý S a • 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 tp(n) nelze snadno spočítat ] • zvolí veřejný klíč e a ověří, že (e,ip(n)) = 1 • např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e • d = 1 (mod tp(n)) • zašifrování numerického kódu zprávy M: C = Ce(M) = Me (mod n) 9 dešifrování šifry C: OT = Dcj(C) = Cd (mod n) Důkaz. Fermatova, resp. Eulerova věta. □ Podepisování (např. DSA O Vygeneruje se otisk (hash) Hm zprávy pevně stanovené délky (např. 160 nebo 256 bitů). O Podpis zprávy Sa{Hm) je vytvořen (pomocí dešifrování) z tohoto hashe s nutností znalosti soukromého klíče podepisujícího. O Zpráva M (případně zašifrovaná veřejným klíčem příjemce) je spolu s podpisem odeslána. Ověření podpisu O K přijaté zprávě M se (po jejím případném dešifrování) vygeneruje otisk H'M O S pomocí veřejného klíče (deklarovaného) odesílatele zprávy se rekonstruuje původní otisk zprávy Va(Sa{Hm)) = Hm-O Oba otisky se porovnají Hm = H'M1. Úvod do kódování oooooooooooooooooo Pár slov o šifrách oosoooooo • Generování klíče. Alice vybere prvočísla p = 2357, q = 2551, a vypočte n = p • q = 6012707 a