Matematika IV - 6. přednáška Okruhy polynomů, kódovania šifrování Michal Bulant Masarykova univerzita Fakulta informatiky 29. 3. 2010 □ S O Kořeny a rozklady polynomů Q Polynomy více proměnných Q Úvod do kódování • (n, k)-kódy • Lineární kódy ô Pár slov o šifrách ooooooooooooooooo Doporučene zdroje • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Předmětové záložky v IS MU □ s - • 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 Pasek, Kódování, elektronický text, MU -http://www. math.muni.cz/~paseka/ftp/lectures/kodovani.ps. Základním nástrojem pro diskusi dělitelnosti, společných dělitelů apod. v okruhu celých čísel Zje procedura dělení se zbytkem a Euklidův algoritmus pro hledání největších společných dělitelů. Tyto postupy nyní zobecníme. ooooooooooooooooo Opakování - dělení polynomů se zbytkem Základním nástrojem pro diskusi dělitelnosti, společných dělitelů apod. v okruhu celých čísel Zje procedura dělení se zbytkem a Euklidův algoritmus pro hledání největších společných dělitelů. Tyto postupy nyní zobecníme. Lemma (Věta o dělení se zbytkem pro polynomy) Necht R je komutativní okruh bez dělitelů nuly a f,g G R[x] polynomy g ^ 0. Pak existuje a G R, a 7^ 0, a polynomy q a r splňující af = qg + r, kde r = 0 nebo str < st g. Je-Ii navíc R těleso neboje aspoň vedoucí koeficient polynomu g roven jedné, potom lze volit a = 1 a polynomy q a r jsou v tomto případě určeny jednoznačně. □ s ooooooooooooooooo oooooo Opakování - dělení polynomů se zbytkem Základním nástrojem pro diskusi dělitelnosti, společných dělitelů apod. v okruhu celých čísel Zje procedura dělení se zbytkem a Euklidův algoritmus pro hledání největších společných dělitelů. Tyto postupy nyní zobecníme. Lemma (Věta o dělení se zbytkem pro polynomy) Necht R je komutativní okruh bez dělitelů nuly a f,g G R[x] polynomy g ^ 0. Pak existuje a G R, a 7^ 0, a polynomy q a r splňující af = qg + r, kde r = 0 nebo str < st g. Je-Ii navíc R těleso neboje aspoň vedoucí koeficient polynomu g roven jedné, potom lze volit a = 1 a polynomy q a r jsou v tomto případě určeny jednoznačně. Poznámka Toto tvrzení je možné aplikovat i obecněji (viz Euklidovské okruhy), je ale třeba správně definovat, jak budeme porovnávat prvky. Plán přednášky Kořeny a rozklady polynomů my více pr lých Úvod do kódování • (n, k)-kódy 9 Lineární kódy ô Pár slov o šifrách □ s Proceduru dělení se zbytkem můžeme okamžitě využít k diskusi kořenů polynomů. □ g - = Proceduru dělení se zbytkem můžeme okamžitě využít k diskusi kořenů polynomů. Uvažme polynom f(x) G R[x], st f > 0, a dělme jej polynomem x - b, b G R. □ g - = Proceduru dělení se zbytkem můžeme okamžitě využít k diskusi kořenů polynomů. Uvažme polynom f(x) G R[x], st f > 0, a dělme jej polynomem x - b, b G R. Protože je vedoucí koeficient jednička, algoritmus pro dělení dává jednoznačný výsledek. Dostáváme tedy jednoznačně zadané polynomy q a r splňující f = q{x — b) + r, kde r = 0 nebo st r = 0, tj. re/?. Tzn., že hodnota polynomu f v b G R je rovna právě f(ŕ>) = r. □ s Proceduru dělení se zbytkem můžeme okamžitě využít k diskusi kořenů polynomů. Uvažme polynom f(x) G R[x], st f > 0, a dělme jej polynomem x - b, b G R. Protože je vedoucí koeficient jednička, algoritmus pro dělení dává jednoznačný výsledek. Dostáváme tedy jednoznačně zadané polynomy q a r splňující f = q{x — b) + r, kde r = 0 nebo st r = 0, tj. r G R. Tzn., že hodnota polynomu f v b G /? je rovna právě f(b) = r. Proto je prvek b G /? kořen polynomu f právě, když (x — b)\f. Protože po vydělení polynomem stupně jedna vždy klesne stupeň výsledku alespoň o jedničku, dokázali jsme následující tvrzení: Důsledek Každý nenulový polynom f nad tělesem R má nejvýše st f kořenů. □ s Kořeny a rozklady pc o«ooooooo ooooooooooooooooo Příklad Polynom x3 má nad Zs 4 kořeny ([0]s, [2]s, [4]s, [6]s,)- Je to tím, že tento okruh není oborem integrity (a tedy ani tělesem). Důsledkem předchozího tvrzení je následující velmi důležitý fakt. Důsledek Libovolná konečná podgrupa multiplikativní grupy (Kx, •) tělesa (K, +, •) je cyklická. Speciálně existuje prvek g G Z* tak, že jeho mocniny generují celou grupu Z*. □ s Platí-li pro k > 1, že dokonce (x — b)k\f, kde k je největší možné, říkáme, že kořen b je násobnosti k. Dva polynomy nad nekonečným komutativním okruhem, které zadávají stejné zobrazení R —> R, mají rozdíl, jehož kořenem je každý prvek v R. Protože rozdíl polynomů má jen konečný stupeň, pokud není nulový, dokázali jsme tak již dříve uvedené tvrzení: Jestliže je R nekonečný okruh, pak dva polynomy f(x) a g{x) nad R jsou stejné právě, když jsou stejná příslušná zobrazení f a g. □ s Polynom h je největší společný dělitel dvou polynomů a f a g G R[x] jestliže: • h\f a zároveň h\g • jestliže k\fa zároveň k\g pak také k\h. n S - = -E -00*0 Polynom h je největší společný dělitel dvou polynomů a f a g G R[x] jestliže: • h\f a zároveň h\g • jestliže k\fa zároveň k\g pak také k\h. Věta (Bezoutova rovnost) Necht R je těleso a necht f,g 1, je a kořenem f násobnosti k — 1. □ s Poznámka Užitečná je často také tzv. lokalizace, tj. redukce koeficientů modulo zvolené prvočíslo p, příp. posunutí proměnné o konstantu. Např., že polynom x3 + 27x2 + 5x + 97 je ireducibilní, zjistíme díky redukci, ireducibilitu tzv. kruhového polynomu ,p-i + ---+X+1 díky substituci x = y + 1. J e-1 i a kořenem polynomu f nad tělesem násobnosti k > 1, je a kořenem f násobnosti k — 1. Důsledek Násobné kořeny polynomu f jsou právě kořeny (f, f). Všechny kořeny polynomu f obdržíme jako (jednoduché) kořeny polynomu Plán přednášky Kořeny a rozklady polynomů Polynomy více proměnných Úvod do kódování • (n, k)-kódy 9 Lineární kódy Q Pár slov o šifrách □ s Okruhy polynomů v proměnných x\,... ,xr definujeme induktivně vztahem /?[xi,... ,xr] := /?[xi,... ,xr_i][xr]. Např. R[x, y] = R[x][y], tzn. že uvažujeme polynomy v proměnné y nad okruhem R[x]. Snadno se ověří, že polynomy v proměnných xi,... ,xr lze chápat jako výrazy vzniklé z písmen x\,... ,xn a prvků okruhu R konečným počtem (formálního) sčítání a násobení v komutativním okruhu. Okruhy polynomů v proměnných x\,... ,xr definujeme induktivně vztahem /?[xi,... ,xr] := /?[xi,... ,xr_i][xr]. Např. R[x, y] = R[x][y], tzn. že uvažujeme polynomy v proměnné y nad okruhem R[x]. Snadno se ověří, že polynomy v proměnných xi,... ,xr lze chápat jako výrazy vzniklé z písmen x\,... ,xn a prvků okruhu R konečným počtem (formálního) sčítání a násobení v komutativním okruhu. Například prvky v /?[x,y] jsou tvaru f = an(x)yn + an_i(x)y"-1 + • • • + a0(x) = (amnxm + ■■■ + a0n)yn + ■■■ + (r>p0xp + • • • + b00) = coo + ciox + coiy + C20X2 + cnxy + c02y2 + ■■■ Jako důsledek naší definice a předchozích výsledků pro polynomy nad obecnými komutativními okruhy dostáváme: Důsledek O Jestliže v okruhu R nejsou dělitelé nuly pak také v okruhu polynomů R[x\,... ,xr] nejsou dělitelé nuly. O Je-li R obor integrity s jednoznačným rozkladem, pak také okruh polynomů R[x\,..., xr] je obor integrity s jednoznačným rozkladem. Příklad Z[x,y] je okruh s jednoznačným rozkladem. □ s ooooooooooooooooo oooooo Symetrické polynomy Definice Polynom f G R[x\,... ,xn], který se nezmění při libovolné permutaci proměnných x\,...,xn, se nazývá symetrický polynom. Elementárními symetrickými polynomy rozumíme polynomy si =xi +x2H-------\-xn, s2 = xix2 + X1X3 H--------h xn_ix„, Sn =Xi □ s Polynom f e/?[xi,.. ■,Xn], který se nezmění při libovolné permutaci proměn nýc h Xi, ... ,xn, se nazývá symetrický polynom. Elementárními symetrickými polynomy rozumíme polynomy Sl = xi +x2H--------hxn, S2 = XiX2 + X1X3 H--------h x„ -lXn, sn = Xl •• •xn Plán přednášky )řeny a rozklady polynomů my více pr lých Úvod do kódování • (n, k)-kódy • Lineární kódy Q Pár slov o šifrách □ s 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. oooooooooooooooo Kódovaní 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. □ s oooooooooooooooo Kódovaní 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ě r\n __ r\k __ r\kír\n- 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. Ú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ě. □ s Ú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 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é. □ s Ú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 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é. Navíc neumíme detekovat tak obvyklé chyby, jako je záměna dvou sousedních hodnot ve slově. □ s on. 010 111 001 101 110 100 000 □ g - = ^ -00*0 on- k 111 \ ■^^ooi \. 010 á 1 t ^ 1 |101 100 000 Definice Hammingova vzdálenost dvou slov je rovna počtu bitů, ve kterých se liší. n S - = -E -00*0 on- k 111 \ ■^^ooi \. 010 á 1 t ^ 1 |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. □ s Jak konstruovat kódová slova, abychom je sladno 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ě. □ s Jak konstruovat kódová slova, abychom je sladno 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) = b0 + b\x -\-------h bk_xxk-x. □ S Jak konstruovat kódová slova, abychom je sladno 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) = b0 + b\x H--------h bk-\x k-l Definice Nechť p(x) = ao + • • • + a„_ ■kx" G Z2 [x] je polynom s ao a„_fe = 1. Polynomiální kód generovaný polynomem p(x) je (n, k)-kód jehož slova jsou polynomy stupně menšího než n dělitelné p(x). □ s Jak konstruovat kódová slova, abychom je sladno 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) = b0 + b\x H--------h bk-\x k-l Definice Nechť p(x) = ao + • • • + a„_ ■kx" G Z2 [x] je polynom s ao a„_fe = 1. Polynomiální kód generovaný polynomem p(x) je (n, k)-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). □ s 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). □ g - = Z definice víme v(x) n-k m(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é. □ s - Z definice víme v(x) n-k m(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. Q 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ž i/(l) = 0 a to nastane tehdy, když je ve v(x) sudý počet nenulových koeficientů. Druhé je zřejmé. □ s Přenos slova v G (Z^)" dopadne příjmem polynomu u{x) = v(x) + e(x) kde e(x) je tzv. chybový polynom repzentující vektor chyby přenosu. n S - = -E -00*0 Přenos slova v G (Z^)" dopadne příjmem polynomu u{x) = v(x) + e(x) kde e(x) je tzv. chybový polynom repzentují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. □ s Přenos slova v G (Z^)" dopadne příjmem polynomu u{x) = v{x) + e(x) kde e(x) je tzv. chybový polynom repzentují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) G ^[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. □ s 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. □ s 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. □ s Tabulka dává o informace o výsledcích předchozích dvou vět pro několik polynomů: n S - = -E -00*0 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 □ s 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. □ s 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 příslušné kódové slovo. Gv □ S Každý polynomiální (n^ k)-kód je lineární kód. □ s - = ■€. -o<\(y Každý polynomiální (n, k)-kód je lineární kód. Matice příslušná k polynomu p(x) = 1 +x + x3 je /l 0 1\ 111 0 1 1 1 o o 0 1 o Vo o i/ □ s nsn Je-li g lineární kódování s maticí G-- = ( P \ßn-k )■ potom zobrazení h : (TL?)" —>■ (Z2)k S maticí H = -- (E„_fc P) má následující vlastnosti O Ker/7 = \mg, tj. O přijaté slovo u je kódové ' slovo právě, když je H u = 0 □ s - = ■€. -o<\(y nsn Je-li g lineární kódování s maticí G = WJ' potom zobrazení h : (Z^)" —>■ {1>2)k s maticí H=(En_k P) má následující vlastnosti O Ker/7 = \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řílušného (n, k)-kódu. n S - = -E -00*0 ooooooooooo«ooooo 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í e = u + v. n S - = -E -00*0 Jak jsme viděli, přenos zprávy u dává výsledek v = u + e. To je ale nad Z2 ekvivalentní 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. Jak jsme viděli, přenos zprávy u dává výsledek v = u + e. To je ale nad Z2 ekvivalentní 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í h : (Z^)" —> {JĽ2)n~k má V za jádro, proto indukuje injektivní lineární zobrazení h : (1,2)"/V —>■ (Z,2)"~k- Jeho hodnoty jsou jednoznačně určeny hodnotami H ■ u. Definice Hodnota H ■ u se nazývá syndrom slova u. □ s Definice Hodnota H ■ u se nazývá syndrom slova u. Dvě slova jsou ve stejné třídě rozkladu právě tehdy když mají 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. □ g - = Příklad Buď dán (6,3) kód nad Z2 generovaný polynomem x3 + x2 + 1. O Určete jeho generující matici a matici kontroly parity. Q Dekódujte zprávu 111101 před poklad áte-1 i, že při přenosu došlo k nejmenšímu možnému počtu chyb. □ s Příklad Buď dán (6,3) kód nad Z2 generovaný polynomem x3 + x2 + 1. O Určete jeho generující matici a matici kontroly parity. Q Dekódujte zprávu 111101 před poklad áte-1 i, že při přenosu došlo k nejmenšímu možnému počtu chyb. Řešení Protože se jedná 0 lineární kód, stačí určit jak se zakódují bázové vektory 1, 2 x a x , tedy u rčit zbytky polynomů x3, 4 5 x a x po dělení poly nomem x3 + * -2 + l. Máme x3 = x2 + 1 (mod x3 +^ -2 + l) x4 = x(x3) = x(x2 + 1) = e x2 + x + 1 (moc x3 +x: ? + l) x5 = x(x4) = x(x2 + X + 1) EE x + 1 (mod x3+x2 + 1) Ř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 A i 1\ 0 i 1 i i 0 i 0 0 0 1 0 \o 0 1/ '1 0 0 1 1 v resp. | 0 1 0 0 1 1 ,0 0 1 0 0 1, □ S Ř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 A i 1\ 0 i 1 i i 0 i 0 0 0 1 0 \o 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. □ s Syndrom Kódová slova s d aným syndromem 000 000000 110001 111010 101100 010110 001011 oiiio 100111 001 001000 111001 110010 100100 011110 000011 01010 101111 010 010000 100001 101010 111100 000110 011011 00110 110111 100 100000 010001 011010 001100 110110 101011 11110 000111 Oil 011000 101001 100010 110100 001110 010011 00010 111111 101 101000 011001 010010 000100 111110 100011 11010 001111 110 110000 000001 001010 011100 100110 111011 10110 010111 111 111000 001001 000010 010100 101110 110011 10010 011111 □ s Ř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 52 Plán přednášky )řeny a rozklady polynomů my více pr lých Úvod do kódování • (n, k)-kódy 9 Lineární kódy Q Pár slov o šifrách □ s Ron Rivest, Adi Shamir, Leonard Adieman (1977; C. Cocks,GCHQ - 1973) • každý účastník A potřebuje dvojici klíčů - veřejný V a a soukromý S a ooooooooooooooooo RSA Ron Rivest, Adi Shamir, Leonard Adieman (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, Lp{n) = (p — l)(q — 1) [n je veřejné, ale (")))• Soukromý klíč Alice je d, veřejný pak (n, e). Příklad * • Generování klíče. Alice vybere prvočísla p = 2357, q = 2551, 1 and vypočte n = p ■ q = 6012707 < 3 (")))• Soukromý klíč Alice je d, veřejný pak (n, e). • Chce-li Bob poslat Alici zprávu m = 5234673, pomoci modulárního umocňování vypočte c = me = 52346733674911 = 3650502 (mod n), a tu odešle Alici. • Alice zprávu dešifruje díky výpočtu cd = 3650502422191 = 5234673. Whitfield Diffie, Martin Hellman (1976; M. Williamson, GCHQ - 1974) Výmena klíčů pro symetrickou kryptografii bez předchozího kontaktu (tj. náhrada jednorázových klíčů, kurýru s kufříky, . ..). Whitfield Diffie, Martin Hellman (1976; M. Williamson, GCHQ - 1974) Výmena klíčů pro symetrickou kryptografii bez předchozího kontaktu (tj. náhrada jednorázových klíčů, kurýru s kufříky, . ..). • Dohoda stran na cyklické grupě G a jejím generátoru g (veřejné) Whitfield Diffie, Martin Hellman (1976; M. Williamson, GCHQ - 1974) Výmena klíčů pro symetrickou kryptografii bez předchozího kontaktu (tj. náhrada jednorázových klíčů, kurýru s kufříky, . ..). • Dohoda stran na cyklické grupě G a jejím generátoru g (veřejné) • Alice vybere náhodné a a pošle ga ooooooooooooooooo Diffie-Hellman key exchange, EIGamal Whitfield Diffie, Martin Hellman (1976; M. Williamson, GCHQ - 1974) Výměna klíčů pro symetrickou kryptografii bez předchozího kontaktu (tj. náhrada jednorázových klíčů, kurýru s kufříky, . ..). • Dohoda stran na cyklické grupě G 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 □ s - ooooooooooooooooo Diffie-Hellman key exchange, EIGamal Whitfield Diffie, Martin Hellman (1976; M. Williamson, GCHQ 1974) Výměna klíčů pro symetrickou kryptografii bez předchozího kontaktu (tj. náhrada jednorázových klíčů, kurýru s kufříky, . .. • Dohoda stran na cyklické grupě G 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 9 Společným klíčem pro komunikaci je gab. )■ □ S ooooooooooooooooo Diffie-Hellman key exchange, EIGamal Whitfield Diffie, Martin Hellman (1976; M. Williamson, GCHQ 1974) Výměna klíčů pro symetrickou kryptografii bez předchozího kontaktu (tj. náhrada jednorázových klíčů, kurýru s kufříky, . .. • Dohoda stran na cyklické grupě G 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 9 Společným klíčem pro komunikaci je gab. )■ □ S ooooooooooooooooo Diffie-Hellman key exchange, EIGamal Whitfield Diffie, Martin Hellman (1976; M. Williamson, GCHQ 1974) Výměna klíčů pro symetrickou kryptografii bez předchozího kontaktu (tj. náhrada jednorázových klíčů, kurýru s kufříky, . .. • Dohoda stran na cyklické grupě G 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 9 Společným klíčem pro komunikaci je gab. )■ Poznámka • Problém diskrétního logaritmu (DLP) • Nezbytná autentizace (man in the middle attack) Z protokolu DH na výměnu klíčů odvozen šifrovací algoritmus EIGamal: • Alice zvolí cyklickou grupu G spolu s generátorem g 9 Alice zvolí tajný klíč x, spočítá h = gx a zveřejní veřejný klíč (G,g,h) • šifrování zprávy M: Bob zvolí náhodné y a vypočte C\ = gy a C2 = M ■ hy a pošle (Q, C2) • dešifrování zprávy: OT = C2/C1 □ s Z protokolu DH na výměnu klíčů odvozen šifrovací algoritmus EIGamal: • Alice zvolí cyklickou grupu G spolu s generátorem g 9 Alice zvolí tajný klíč x, spočítá h = gx a zveřejní veřejný klíč (G,g,h) • šifrování zprávy M: Bob zvolí náhodné y a vypočte C\ = gy a C2 = M ■ hy a pošle (Q, C2) • dešifrování zprávy: OT = C2/C1 Poznámka Opět lze odvodit podepisování. ooooooooooooooooo Eliptické křivky Eliptické křivky jsou rovinné křivky o rovnici tvaru y2 = x3 + ax + b a zajímavé jsou tím, že na jejich bodech lze definovat operace tak, že výslednou strukturou bude komutativní grupa. Přitom uvedené operace lze efektivně provádět a navíc se ukazuje, že mají (nejen) pro kryprografii zajímavé vlastnosti - srovnatelné bezpečnosti jako RSA lze dosáhnout již s podstatně kratšími klíči. Výhodou je rovněž velké množství použitelných eliptických křivek (a tedy grup různé struktury) podle volby parametru a, b . ooooooooooooooooo Eliptické křivky Eliptické křivky jsou rovinné křivky o rovnici tvaru y2 = x3 + ax + b a zajímavé jsou tím, že na jejich bodech lze definovat operace tak, že výslednou strukturou bude komutativní grupa. Přitom uvedené operace lze efektivně provádět a navíc se ukazuje, že mají (nejen) pro kryprografii zajímavé vlastnosti - srovnatelné bezpečnosti jako RSA lze dosáhnout již s podstatně kratšími klíči. Výhodou je rovněž velké množství použitelných eliptických křivek (a tedy grup různé struktury) podle volby parametru a, b . Protokoly: • ECDH - přímá varianta DH na eliptické křivce (jen místo generátoru se vybere vhodný bod na křivce) • ECDSA - digitální podpis pomocí eliptických křivek. ooooooooooooooooo Eliptické křivky Eliptické křivky jsou rovinné křivky o rovnici tvaru y2 = x3 + ax + b a zajímavé jsou tím, že na jejich bodech lze definovat operace tak, že výslednou strukturou bude komutativní grupa. Přitom uvedené operace lze efektivně provádět a navíc se ukazuje, že mají (nejen) pro kryprografii zajímavé vlastnosti - srovnatelné bezpečnosti jako RSA lze dosáhnout již s podstatně kratšími klíči. Výhodou je rovněž velké množství použitelných eliptických křivek (a tedy grup různé struktury) podle volby parametru a, b . Protokoly: • ECDH - přímá varianta DH na eliptické křivce (jen místo generátoru se vybere vhodný bod na křivce) • ECDSA - digitální podpis pomocí eliptických křivek. Poznámka Problém diskrétního logaritmu (ECDLP). Navíc se ukazuje, že eliptické křivky jsou velmi dobře použitelné při faktorizaci prvočísel.