Diskrétní matematika - cvičení 5. týden Lukáš Vokřínek Masarykova univerzita Fakulta informatiky jaro 2020 Pětice modulů 3; 5; 7; 11; 13 umožňuje jednoznačně reprezentovat čísla menší než jejich součin (tedy menší než 15015) a efektivně provádět (v případě potřeby distribuovane) běžné aritmetické operace. Určete reprezentaci čísel 1234 a 5678 v této modulární soustavě a pomocí této reprezentace vypočtěte jejich součet a součin. ■v Řešení 1234 = 1 (mod3) 5678 = 2 (mod 3) 1234 = 4 (mod5) 5678 = 3 (mod 5) 1234 = 2 (mod7) 5678 = 1 (mod 7) 1234 = 2 (modli) 5678 = 2 (modli) 1234 = 12 (mod 13) 5678 = 10 (mod 13) ■v Řešení 1234 = 1 (mod3) 5678 = 2 (mod 3) 1234 = 4 (mod5) 5678 = 3 (mod 5) 1234 = 2 (mod7) 5678 = 1 (mod 7) 1234 = 2 (modli) 5678 = 2 (modli) 1234 = 12 (mod 13) 5678 = 10 (mod 13) Reprezentujeme tedy číslo 1234 pomocí pětice zbytků (1,4, 2, 2,12) a číslo 5678 pomocí pětice zbytků (2, 3,1, 2,10). Součet a součin jsou pak reprezentovány 1234 + 5678 - (3,7, 3,4, 22) = (0, 2, 3,4,9) 1234 • 5678 - (2,12, 2, 4,120) = (2, 2, 2,4, 3) Řešení 1234 + 5678 - (0,2,3,4,9) Převeďme nyní tyto reprezentace zpět na čísla, řešme tedy v prvním případě soustavu kongruencí x x x x x 0 (mod3) 2 (mod5) 3 (mod7) 4 (modli) 9 (mod 13) Z první kongruence máme x = 3ŕ, dosazením do druhé dostaneme kongruenci 3r = 2 (mod 5), tedy t = 4 (mod 5), tj. t = 5s + 4 a x = 15s + 12. Dosadíme do třetí kongruence: 15s = —9 (mod 7), tedy s = 5 (mod 7), tj. s = 7r + 5 x = 105r + 87. ■v Řešení x = O (mod 3) x = 2 (mod 5) x = 3 (mod 7) x = 4 (mod 11) x = 9 (mod 13) Dosadíme x = 105r + 87 do čtvrté kongruence a dostaneme 105r = -83 (mod 11), tedy 6r = 5 (mod 11) r = 10 (mod 11), tj. r = lig + 10 a x = 1155q + 1137. Dosadíme do poslední kongruence a dostaneme 1155q = —1128 (mod 13), tedy lig = 3 (mod 13): Řešení 13c/ = 0 lig = 3 2g = 10 lq = 5 (mod 13) 0g = 0 Máme tak q = 13p + 5 a dosazením x = 15015p + 6912, tj. x = 6912 (mod 15015). Protože je součet menší než 15015, musí nutně být roven 6912. ■v Řešení Podobně v případě součinu 1234 • 5678 - (2, 2, 2, 4, 3): x = 2 (mod3) x = 2 (mod5) x = 2 (mod7) x = 4 (mod 11) x = 3 (mod 13) dostáváme z prvních tří kongruencí x = 105r + 2 (protože je pravá strana stejná), dosadíme do čtvrté: 105r = 6r = 2 (mod 11), tedy r = 4 (mod 11), tj. r = lig + 4 a x = 1155q + 422. Dosadíme do poslední kongruence a dostaneme 1155q = —419 (mod 13), tedy Uq= 10 (mod 13): Řešení 13c/ = 0 llq = 10 2q = 3 lq = 8 (modl3) 0c/ = 0 Máme tak q = 13p + 8 a dosazením x = 15015p + 9662, tj. x = 9662 (m od 15015). Kdyby byl součin menší než 15015, musel by nutně být roven 9662; ve skutečnosti ale došlo k "přetečení'. Ukažte, že jsou čísla 2n — 1; 2n; 2n + 1 po dvou nesoudělná a určete, kolik bitů mohou mít jimi určená čísla. Spočtěte reprezentaci čísla 118 v této soustavě s n = 3. Zapřemýšlejte o efeketivní realizaci této modulární aritmetiky. ■v Řešení Ukážeme nesoudělnost 2n — 1 a 2n + 1, nesoudělnost dvou po sobě jdoucích čísel je ještě snazší. Počítejme: (2" - 1, 2n + 1) = (2" -1,2) = (-1, 2) = (1, 2) = 1 (od 2n + 1 lze odečíst 2n — 1 a zbude 2, v dalším kroku lze od 2n — 1 odečíst 2n, protože se jedná o násobek 2). Ukažte, že jsou čísla 2n — 1; 2n; 2n + 1 po dvou nesoudělná a určete, kolik bitů mohou mít jimi určená čísla. Spočtěte reprezentaci čísla 118 v této soustavě s n = 3. Zapřemýšlejte o efeketivní realizaci této modulární aritmetiky. ■v Řešení Podle CRT pak trojice zbytků jednoznačně reprezentuje čísla modulo [2n - 1, 2", 2n + 1] = (2" - 1) • 2n • (2" + 1) = 23" - 2", tedy téměř všechna čísla čítající 3n bitů. ■v Řešení Pišme nyní vše ve dvojkové soustavě: máme tak spočítat zbytek po dělení čísla sto osmnáct, tedy 1110 110, modulo sedm, osm, devět, tedy 111, 1000, 1001. Přesněji pišme dané číslo po trojicích cifer jako 1110 110 = 1 • 10002 + 110 • 1000 + 110 Pak modulo 1000 je jistě 1110110 = 110 (mod 1000). Protože je 1000 = 1 (mod 111), dostáváme 1110 110 = 1 + 110 + 110 = 1101 = 110 (mod 111). Protože je 1 000 = —1 (mod 1 001), dostáváme 1110 110 = 1 — 110 + 110 = 1 (mod 1001). Príklad Šifrou RSA s veřejným klíčem e = 7, n — p - q — 33 byly poslány tři zprávy 29, 7, 21. Prolomte šifru a zprávy dešifrujte. Řešení Zatímco n — p - q ]e veřejným klíčem, jednotlivá prvočísla p, q jsou soukromým klíčem. Rozklad se využije k výpočtu Eulerovy funkce iP(n) = (p-l)(q-l)1 pomocí níž je určen soukromý klíč d\ e • d = 1 (mod (f(n)). Šifrování čísla m (mod n) je dáno umocňováním na e, tj. c = me (mod n). Dešifrování je pak dáno umocňováním na d, tj m = cd (mod n), protože díky Eulerově větě platí: cd = (me)a = mea = mL = m (mod n). .e\d _ ___e-d _ _1 _ Príklad Šifrou RSA s veřejným klíčem e = 7, n — p - q — 33 byly poslány tři zprávy 29, 7, 21. Prolomte šifru a zprávy dešifrujte. Řešení Prolomení šifry spočívá ve faktorizaci čísla 33, tj. v nalezení prvočísel p, q. V našem případě je to jednoduché: p = 3, g = 11, zejména tak ¥>(p • <7) = (p - 1)(<7 - 1) = 2 • 10 = 20. Nyní můžeme spočítat inverzi d k e = 7 (mod <£(/))), totiž 20d = 0 7c/ = 1 6d = -2 ld = 3 (mod 20) Šifrou RSA s veřejným klíčem e = 7, n — p - q — 33 byly poslány tři zprávy 29, 7, 21. Prolomte šifru a zprávy dešifrujte. Řešení Dešifrování se tedy provádí umocňováním na třetí modulo n, pro jednotlivé zprávy vychází mi = 293 = 2 (mod 33) m2 = 73 = 13 (mod 33) m3 = 213 = 21 (mod 33) (u poslední zprávy je nicméně jak původní tak zašifrovaná zpráva soudělná s modulem, což je velmi nevhodné, protože tak lze pomocí největšího společného dělitele rozložit modul). Demonstrujte RSA protokol se zvolenými prvočísly 23 a 29 s vhodnou volbou veřejného klíče e. Zašifrujte a odšifrujte několik zpráv m pro ne moc velká m. Řešení Máme n — p ■ q — 667. Budeme volit e = 487 a m = 25 (mod 667). Zašifrovaná zpráva pak je c = 25487 (mod 667). Ukážeme, jak lze mocninu (snadněji?) počítat zvlášť modulo 23 a 29 (to samozřejmě bez znalosti faktorizace nelze, jde jen o zjednodušení pro účely příkladu): c = 25487 = 23 = 8 (mod 23) c = 25487 = (-4)11 = -5 (mod 29) (exponenty lze redukovat modulo (p(23), resp. cp(29)). Príklad Demonstrujte RSA protokol se zvolenými prvočísly 23 a 29 s vhodnou volbou veřejného klíče e. Zašifrujte a odšifrujte několik zpráv m pro ne moc velká m. Rešení Nyní dáme tyto dva mezivýsledky, c = 8 (mod 23), c = —5 (mod 29), dohromady modulo 667: -5-23 29c = 8 • 29 23c = 6c = 8 • 29 + 5 • 23 5c = -24 • 29 - 20 • 23 = -1 • 29 + 9 • 23 c = 9 • 29 - 4 • 23 = 169 Řešení Podobně budeme i dešifrovat, prvně potřebujeme k veřejnému klíči e = 487 spočítat soukromý klíč d, tj. inverzi modulo