Úvod do kódování ooooooooooooooooo Pár slov o šifrách oooooo Matematika IV - 6. přednáška Kódování a šifrování Michal Bulant Masarykova univerzita Fakulta informatiky 6. 4. 2011 Úvod do kódování ooooooooooooooooo Obsah přednášky Pár slov o šifrách oooooo Q Úvod do kódování • (n, /c)-kódy • Lineární kódy ©Pár slov o šifrách Úvod do kódování Pár slov o šifrách ooooooooooooooooo oooooo Doporučené zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové záložky v IS MU Úvod do kódování Pár slov o šifrách ooooooooooooooooo oooooo Doporučené zdroje • 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. • Jiří Rosický, Algebra, PřF MU, 2002. • Peter J. Cameron. Introduction to algebra, Oxford University Press, 2001, 295 s. (Dostupné v knihovně PřF). • 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. Úvod do kódování ooooooooooooooooo Plán přednášky Pár slov o šifrách oooooo Q Úvod do kódování • (n, /c)-kódy • Lineární kódy O Pár slov o šifrách Úvod do kódování Pár slov o šifrách •oooooooooooooooo oooooo Kódování Při přenosu informace zpravidla dochází k její deformaci. Budeme pro jednoduchost pracovat s modelem, kdy jednotlivé částečky informace jsou buď nuly nebo jedničky (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. Úvod do kódování Pár slov o šifrách •oooooooooooooooo oooooo Kódování Při přenosu informace zpravidla dochází k její deformaci. Budeme pro jednoduchost pracovat s modelem, kdy jednotlivé částečky informace jsou buď nuly nebo jedničky (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. Úvod do kódování Pár slov o šifrách •oooooooooooooooo oooooo Kódování Při přenosu informace zpravidla dochází k její deformaci. Budeme pro jednoduchost pracovat s modelem, kdy jednotlivé částečky informace jsou buď nuly nebo jedničky (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. 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ě 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«ooooooooooooooo Pár slov o šifrách oooooo Úplně 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ě. Úvod do kódování o«ooooooooooooooo Pár slov o šifrách oooooo Úplně 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ě. Úvod do kódování o«ooooooooooooooo Pár slov o šifrách oooooo Úplně 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«oooooooooooooo Pár slov o šifrách oooooo Úvod do kódování oo«oooooooooooooo Pár slov o šifrách oooooo 011 010 ^^001 i 110 |101 100 000 Definice Hammingova vzdálenost dvou slov je rovna počtu bitů, ve kterých se liší. Úvod do kódování oo«oooooooooooooo Pár slov o šifrách oooooo 011 010 ^^001 i 110 |101 100 000 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. Q 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. Úvod do kódování ooo«ooooooooooooo Pár slov o šifrách oooooo 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ě. Úvod do kódování ooo«ooooooooooooo Pár slov o šifrách oooooo 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 bob\... bk-i je reprezentována jako polynom m(x) = bo + b\x H-----h bk_xxk-x. Úvod do kódování ooo«ooooooooooooo Pár slov o šifrách oooooo 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 bob\... bk-i je reprezentována jako polynom m(x) = bo + b\x H-----h bk_xxk-x. Definice Nechť p(x) = ao + a\x + • • • + an-kx"~k e 2^[x] je polynom s ao = 1, an-k = 1- Polynomiální kód generovaný polynomem p(x) je (n, /c)-kód jehož slova jsou polynomy stupně menšího než n dělitelné p(x). Úvod do kódování ooo«ooooooooooooo Pár slov o šifrách oooooo 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 bob\... bk-i je reprezentována jako polynom m(x) = bo + b\x H-----h bk_xxk-x. Definice Nechť p(x) = ao + a\x + • • • + an-kx"~k e 2^[x] je polynom s ao = 1, an-k = 1- Polynomiální kód generovaný polynomem p(x) je (n, /c)-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) + x"~km(x), kde r(x) je zbytek po dělení polynomu x"~km(x) polynomem p(x). Úvod do kódování oooo»oooooooooooo Pár slov o šifrách oooooo Z definice víme v(x) = x"-km(x) + r(x) = q{x)p{x) + r{x) + r(x) = q{x)p{x). Budou tedy všechna kódová slova dělitelná p(x). Úvod do kódování oooo»oooooooooooo Pár slov o šifrách oooooo Z definice víme v(x) = x"-km(x) + r(x) = q{x)p{x) + r{x) + r(x) = q{x)p{x). Budou tedy všechna kódová slova dělitelná p(x). Původní zpráva je obsažena přímo v polynomu v(x), takže dekódování správného slova je snadné. Úvod do kódování oooo»oooooooooooo Pár slov o šifrách oooooo Z definice víme v(x) = x"-km(x) + r(x) = q{x)p{x) + r{x) + r(x) = q{x)p{x). Budou tedy všechna kódová slova dělitelná p(x). Původní zpráva je obsažena přímo v polynomu v(x), takže dekódování správného slova je snadné. Příklad O Polynom p(x) = 1 + x generuje (n, n — l)-kód kontroly parity pro všechna n > 3. O Polynom p(x) = 1 + x + x2 generuje (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«ooooooooooo Pár slov o šifrách oooooo Přenos slova v e Z£ dopadne příjmem polynomu u{x) = v{x) + e(x) kde e(x) je tzv. chybový polynom reprezentující vektor chyby přenosu. Úvod do kódování ooooo«ooooooooooo Pár slov o šifrách oooooo Přenos slova v e Z£ 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é zbytečně často. Úvod do kódování ooooo«ooooooooooo Pár slov o šifrách oooooo Přenos slova v e Z£ 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é zbytečně často. Definice Ireducibilní polynom p(x) e ^[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í oooooo»oooooooooo Pár slov o šifrách oooooo 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. Úvod do kódování oooooo»oooooooooo Pár slov o šifrách oooooo 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) = g(x)(l + x) všechny dvojité chyby a všechna slova s lichým počtem chyb. Úvod do kódování ooooooo«ooooooooo Tabulka dává o informace o výsledcích předchozích dvou vět pro několik polynomů: Úvod do kódování ooooooo«ooooooooo Pár slov o šifrách oooooo Tabulka dává o 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 1 + X4 + X9 9 511 l+x3+x10 10 1023 Úvod do kódování OOOOOOOO0OOOOOOOO Pár slov o šifrách oooooo Definice Lineární kód je injektivní lineární zobrazení g : {JL-i)k —> (^2)". Matice G typu k/n reprezentující toto zobrazení v standardních bazích se nazývá generující matice kódu. Úvod do kódování OOOOOOOO0OOOOOOOO Pár slov o šifrách oooooo Definice Lineární kód je injektivní lineární zobrazení g : {JL-i)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í ooooooooo«ooooooo Každý polynomiální (n^ k)-kód je lineární kód. Úvod do kódování ooooooooo«ooooooo Pár slov o šifrách oooooo 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 G = A 1 1 0 1 1 1 i 1 0 1 i 0 0 0 0 1 0 0 0 0 1 0 \o 0 0 1/ Úvod do kódování OOOOOOOOOO0OOOOOO Pár slov o šifrách oooooo Věta Je-li g lineární kódovánís potom zobrazeníh : (Z^)" - H má následující vlastnosti O Ker h = \mg, tj. O přijaté slovo u je kódo< {J^2)k s maticí {^n-k P) slovo právě, když je H ■ u = Úvod do kódování OOOOOOOOOO0OOOOOO Věta Je-li g lineární kódování s maticí potom zobrazení h : (Z^)" —> {1>2)k s maticí H=(En_k P) má následující vlastnosti O Ker h = \mg, tj. O přijaté slovo u je kódové slovo právě, když je H ■ u = 0 Matici H z věty se říká matice kontroly parity příslušného (n, /c)-kódu. Úvod do kódování Pár slov o šifrách ooooooooooo«ooooo oooooo Samoopravné kódy 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. Úvod do kódování Pár slov o šifrách ooooooooooo«ooooo oooooo Samoopravné kódy 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 (2yn 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 v prostoru (z2y/v. Úvod do kódování Pár slov o šifrách ooooooooooo«ooooo oooooo Samoopravné kódy 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 (2yn 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 v prostoru (z2y/v. Zobrazení (homomorfismus grup) h : (Z^)" —> (jĹ2)n~k má V za jádro, proto indukuje injektivní lineární zobrazení h : (Z2)"/V —> (Z2)"~k. Jeho hodnoty jsou jednoznačně určeny hodnotami H ■ u. Úvod do kódování OOOOOOOOOOOO0OOOO Pár slov o šifrách oooooo Definice Hodnota H ■ u se nazývá syndrom slova u. Úvod do kódování OOOOOOOOOOOO0OOOO Pár slov o šifrách oooooo 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í ooooooooooooo«ooo Pár slov o šifrách oooooo Příklad Buď dán (6,3) kód nad Z2 generovaný polynomem x3 + x2 + 1. Q Určete jeho generující matici a matici kontroly parity. Q Dekódujte zprávu 111101 před pokladáte-1i, že při přenosu došlo k nejmenšímu možnému počtu chyb. Úvod do kódování ooooooooooooo«ooo Pár slov o šifrách oooooo Příklad Buď dán (6,3) kód nad Z2 generovaný polynomem x3 + x2 + 1. Q Určete jeho generující matici a matici kontroly parity. Q Dekódujte zprávu 111101 před pokladáte-1i, ž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í oooooooooooooo»oo Pár slov o šifrách oooooo Ř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 /l 1 1\ 0 1 1 1 1 0 1 0 o 0 1 o \0 0 1/ '1 0 0 1 1 v resp. | 0 1 0 0 1 1 ,0 0 1 0 0 1, Úvod do kódování oooooooooooooo»oo Ř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 /l 1 1\ 0 1 1 1 1 0 1 0 o 0 1 o \0 0 1/ '1 0 0 1 1 v resp. | 0 1 0 0 1 1 ,0 0 1 0 0 1, Vynásobíme-li přijatou 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. TTTTTO TOTOOT TTOOTT OTTTOT OOTOTO OTOOOO TOOTOO OOOTTT TTT TTTOTO TOTTOT TTOTTT OTTOOT OOTTTO OTOTOO TOOOOO 0000T T OTT TTTTOO TOTOTT TTOOOT OTTTTT OOTOOO OTOOTO TOOTTO OOOTOT TOT TTTTTT T0T000 TTOOTO OTTTOO OOTOTT OTOOOT TOOTOT OOOTTO TTO TTTOOO TOTTTT TTOTOT OTTOTT OOTTOO OTOTTO TOOOTO OOOOOT OOT TTTOTT TOTTOO TTOTTO OTTOOO OOTTTT OTOTOT TOOOOT OOOOTO OTO TTTTOT TOTOTO TTOOOO OTTTTO OOTOOT OTOOTT TOOTTT OOOTOO TOO TTTOOT TOTTTO TTOTOO OTTOTO OOTTOT OTOTTT TOOOTT 000000 000 LU3LUOJ puÄs ujÄuep S EAO|S eAopo^i ujojpuÁc; oooooo Lpej^jS O AO|S JEJ o«ooooooooooooooo JUEAOpC»! Op pOA|-| Úvod do kódování 0OOOOOOOOOOOOOOO« Pár slov o šifrách oooooo Ř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. □ s - ■ * ■O 0. o- Úvod do kódování ooooooooooooooooo Plán přednášky Pár slov o šifrách oooooo 9 Úvod do kódování • (n, /c)-kódy a Lineární kódy Q Pár slov o šifrách Úvod do kódování Pár slov o šifrách OOOOOOOOOOOOOOOOO »00000 RSA Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks,GCHQ - 1973) • každý účastník A potřebuje dvojici klíčů - veřejný V a a soukromý Sa Úvod do kódování ooooooooooooooooo Pár slov o šifrách •ooooo RSA Ron Rivest, Adi Shamir, Leonard Adleman (1977; C. Cocks,GCHQ - 1973) • každý účastník A potřebuje dvojici klíčů - veřejný V a a soukromý S a • generování klíčů: zvolí dvě velká prvočísla p,q, vypočte n = pq, ip(n) = (p — l)(q — 1) [n je veřejné, ale