Faktorizace 6. Asymetrické šifrovací systémy neboli systémy s veřejným klíčem - Systém s veřejným klíčem se složitostí stejnou jako faktorizace Jan Paseka Ústav matematiky a statistiky Masarykova univerzita 8. listopadu 2021 O Systém s veřejným klíčem se složitostí stejnou jako faktorizace • Kongruenční rovnice a mocninné zbytky • Grupa Gm Uveďme příklad systému s veřejným klíčem, o kterém lze ukázat, že jeho složitost je ekvivalentní s problémem faktorizace. Tvůrcem systému je Rabin (1979). Každý uživatel systému vybere dvojici (p, q) velkých různých prvočísel, které uchová v tajnosti. Zároveň si vybere přirozené číslo B < N = p ■ q. Veřejný klíč bude dvojice (£, A/), soukromý klíč bude faktorizace (p, q) čísla N. Šifrovací funkce e zprávy M, kde M je reprezentovatelná jako přirozené číslo v definičním oboru {1,..., N - 1} (v případě potřeby se zpráva rozparceluje na více bloků), je e{M) = M-{M + B) (modA/). (1.1) Je-li C výsledný kryptogram, pak dešifrovací problém je nalézt M tak, že M2 + BM= C (mod N). (1.2) Faktorizace Kongruenční rovnice Grupa Gm Kongruenční rovnice a rr locninné zbytky 1 Poznamenejme nejprve, že platí následující tvrzení Věta 1.1 Kongruenční rovnice ax = b (modm). (1.3) je řešitelná právě tehdy, když (a, m)\b. V tomto případě má rovnice právě (a, m) navzájem nekongruentních řešení modulo m. Důkaz. Výše uvedená podmínka je nutná, neboť v opačném případě nemůže platit rovnost ax = b + kmv oboru celých čísel. Buď tedy d = (a, m) a nechť d\b. Faktorizace Kongruenční rovi Kongruenční rovnice a mocninné zbytky II O Nechť d = 1. Dle Bezoutovy věty existují celá čísla tv, v taková, že au + mv = 1. Existují tedy celá čísla x, y splňující ax + my = b, tj. platí ax = b (mod m). Řešení x je jednoznačně určeno modulo m, neboť je-li x' jiné řešení splňující ax' = b (mod m), máme a(x - x') = 0 (mod m) a tedy x = x' (mod m). O Nechť d > 1. Protože nutně d\b, máme po dosazení do vztahu ax = b + km za a = ád, b = b'd, m = m'd a po vydělení číslem d kongruenční rovnici á x = b' (mod m'). Z případu 1 víme, že tato kongruenční rovnice má jediné řešení x = x0 (mod m'). Všechna řešení modulo m tvoří právě d následujících čísel x = x0, x0 + /t?', ..., x0 + (d - 1 )m'', (mod m). Faktorizace Kongruenční rovnice Grupa Gm Kongruenční rovnice i a mocninné zbytky III Budeme chtít vyřešit resp. zjistit, zda následující kongruenční rovnice má řešení v celých číslech pro n > 2: ax11 = b (mod m). (1.4) Podobně jako v případě lineárních kongruečních rovnic se lze omezit na případ, kdy (a, m) = 1. Použitím Eulerovy věty pak obdržíme rovnici xn = ba^™)-1 (mod m). Buďte tedy m, n přirozená čísla taková, že m > 2, n > 2, a celé číslo takové, že (a, m) = 1. Číslo a se nazývá n-tý mocninný zbytek modulo m, je-li řešitelná kongruence xn = a (mod /t?). (1.5) Faktorizace Kongruenční rovnii Kongruenční rovnice a mocninné zbytky IV Pro zkoumání takovýchto kongruenčních rovnic využijeme následujících tvrzení. Věta 1.2 Buďte čísla m-\, m2,..., mr navzájem nesoudělná, a-\,a2,...,ar a £>i, £>2, • • •, £>r libovolná celá čísla taková, že (a^.m^) = (a2,m2) = ■■■ = (arimr) = 1. Pak má systém 3jX = b j (mod m f) (1.6) pro 1 < i < r právě jedno řešení modulo m = m-\ ■ m2l.....mr. Faktorizace Kongruenční rovnice Grupa Gm Kongruenční rovnice i a mocninné zbytky V Důkaz. Zřejmě mají jednotlivé kongruenční rovnice právě jedno řešení, které získáme z Euklidova algoritmu pro čísla a,- a m-, -a,- • u j + m j ■ v j = 1. Pronásobíme-li b; máme a,- • x-, + /t?/ • y- = £>/, tj. a,x = bj (mod at?,)) Předpokládejme, že toto řešení je ve tvaru x = C/ (mod mj) (1.7) pro 1 < i < r. Protože máme (at?/, rrij) = 1 pro / ^ y, máme i m_ m_ m_\ _ a v m-i ' m2 ' " " " ' mr > ~ Zejména tedy existují čísla /i, yfc, • • •, y/ tak, že m m yi + — • y2 + at?! /7?2 m + — yr /7?r 1 Faktorizace Kongruenční rovnii Kongruenční rovnice a mocninné zbytky VI Položme e-, = Zřejmě platí rn y-, pro 1 < i < r. e-\ + e2 H-----h er = 1 (mod /r?), e,- • ey = 0 (mod m) pro / ^ y, e,- • e,- = e-, (mod /r?), 0 (mod rrij) pro / ^ y, 1 (mod m,-) pro / = y. (1.8) (1.9) (1.10) (1.11) Totiž e-, • ey = m • c, e,- • e,- = J]/ ©y • ey = AT?/ • ď, (e/, AT?/) = 1. Položme x0 = dei + c2e2 + • 1 • ej = e,- (mod at?), + crer. Faktorizace Kongruenční rovnice Grupa Gm Kongruenční rovnice i a mocninné zbytky VII Máme pak z 1.11, že xq = q (mod mj) pro 1 < i < r. Je tedy x0 společné řešení modulo m. Pro každé jiné řešení x'Q modulo m systému 1.7 máme x0 = Xq (mod mj) pro 1 < / < r a tedy také x0 = x'Q (mod m). Připomeňme, že pro všechna přirozená čísla m tvoří zbytkové třídy [a]m pro (a, m) = 1 multiplikativní abelovskou grupu modulo m. Přitom počet prvků této grupy je právě (p(m). Tuto grupu budeme v dalším označovat jako Gm . Věnujme se pro chvíli zkoumání její algebraické struktury. Nechť m = m-\m2 ... mr, kde čísla m-\, /t?2, ..., mr jsou navzájem nesoudělná. Podle Věty 1.2 má systém kongruencí x = a j (mod m j) pro 1 < i < r právě jedno řešení a modulo m . Přitom platí, že (a, mi) = (ah mi) pro 1 < i < r. Zejména tedy (a, mi) = 1 právě tehdy, když (a,-, /t?/) = 1. Opět podle věty 1.2 máme jednoznačně určený rozklad na základě rovností 1.8, 1.9, 1.10, 1.11 tvaru [a]m = [aiei]m + --- + [arer]m. (1.12) Označme jakožto [a*]m zbytkovou třídu [ei + • • • + e/_i + a;e; + e/+i + • • • + er]m. Pak pro pevné / tvoří množina G*m. zbytkových tříd [a*]m podgrupu grupy Gm. Z rovnosti 1.12 obdržíme jednoznačně určený rozklad [a]m = [a*,]m...[a*r]m. (1.13) Provedeme-li tento rozklad pro všechna [a]m e Gm, lze výše uvedené formulovat tak, že grupa Gm je přímý součin podgrup um1' ■ ■ ■ ' umr ■ Máme zejména izomorfismus mezi grupami Gm/ a G*m. pomocí zobrazení [a*]m <—> [a/]m/. Řekneme, že a patří modulo m k exponentu d , pokud (a, m) = 1, ad = 1 (mod m), ale a" ^ 1 (mod n) pro 1 < n < d. To ale není nic jiného, než že a je prvek řádu d v multiplikativní grupě Gm. Lemma 1.3 Patří-li a modulo m k exponentu d, jsou čísla 1, a, a2,..., ad 1 modulo m nekongruentní. Je-li dále ař = 1 (mod ni), pak d\t. Důkaz. Nechť ak = ah (mod m), 0 < h < k < d. Protože (a, m) = 1, je ak~h = 1 (mod ni). To je však spor sO 1, pak platí 1 < ^ < 0. Podle Tvrzení 1.5 je pak dokonce (p(p - 1) = x(P - 1 )■ Nechť tedy existuje nějaké číslo a, které patří k exponentu d. Pak dle lemmatu 1.3 jsou čísla tvaru 1, a, a2,..., ad~J[ navzájem nekongruentní řešení rovnice xd - 1 =0 (modp). Faktorizace Kongruenční rovnice Grupa Gm Grupa Gm VIII - Pokračování důkazu Tvrzení 1.6 Toto lze přepsat pomocí polynomiální kongruence následovně xd - 1 = (x- 1)(x-a)---(x-aQÍ-1) (modp). Zároveň jsou výše uvedená čísla také všechna řešení této kongruence. Podle Lemmatu 1.4 pak i ak patří k exponentu d, pokud (c/, k) = 1. To znamená, že mezi řešení přináleží (p(d) čísel, která patří k exponentu d. Nutně pak buď x(d) = 0 nebo x(d) = 2. ^^^^ 1 Důkaz. MA Z a = g}°^a(mod m)ab = glog^(mod m) obdržíme ab = glog0a+log0Ď(mod/T?). Porovnáme-li toto s ab = g}°%9ab(mod m), obdržíme první vlastnost. Vlastnosti 2 a 3 plynou bezprostředně z vlastnosti 1. Z g = g}°^99(modm) obdržíme 4. Pátá vlastnost je založena na Fermat-Eulerově větě: - 1 = (g^ - i) (g^ + i) = 0(modAT?). Tvrzení 1.8 Buď p liché prvočíslo tak, že číslo a není dělitelné p. Kongruenční rovnice n . , r. má právě d = (n, pr~1 (p - 1)) nekongruentních řešení, pokud d dělí\ogga. Jinak je tato kongruence neřešitelná. Důkaz. Tvrzení věty se logaritmováním převede na lineární kongruenční rovnici n\oggx = \ogga (modpr-1 (p - 1)). Zbytek plyne z tvrzení 1.1. Tvrzení 1.9 Buď p liché prvočíslo tak, že číslo a není dělitelné p, d = (n, pr~1 (p - 1)). Kongruenční rovnice x11 = a (modpr) má právě řešení právě tehdy, když platí kongruenční rovnice aip-1(p-i) = -i (modp/-). (1.15) Důkaz. Buď g primitivní kořen modulo pr. Podle věty 1.8 je výše uvedená kongruence řešitelná právě tehdy, když existuje číslo h tak, že \ogga = h ■ d. Pak platí a = gXo^a = gh-d (modpr). Tedy a>"1(p-i) 9 h.ff-'{p-\) 1 (modpr). Nechť obráceně platí kongruenční rovnice 1.15. Položme [i = \ogga. Protože a = g11 (modpr), máme g^-1^-1) = 1 (modpr). Protože g je primitivní kořen modulo pr, je § celé číslo, tj. d děl Tedy dle tvrzení 1.8 je kongruenční rovnice řešitelná.