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 22. listopadu 2021 Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm • Kvadratické kongruence O Systém s veřejným klíčem A se složitostí stejnou jako ^ Ja se naPacla faktorizace RSA-algoritmus. • Kongruenční rovnice a mocninné zbytky Algebraické vlastnosti a • Grupa Gm iterovaný útok Faktorizace Napadání RSA Algebraické vlastnosti Kvadráty Grupa G m 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. Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty írupa 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). Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty írupa 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. Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty írupa 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 (B, A/), soukromý klíč bude faktorizace (p, q) čísla N. 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 (B, 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) (mod N), ^ „ , „ t (1.1) Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm 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 Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice a mocninné zbytky I 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. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice a mocninné zbytky I Poznamenejme nejprve, že platí následující tvrzení Věta 1.1 Kongruenční rovnice ax = b (modm). 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. ■ (1.3) 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 Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice a mocninné zbytky II O Nechť d = 1. Dle Bezoutovy věty existují celá čísla u, v taková, že au + mv = 1. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice a mocninné zbytky II O Nechť d = 1. Dle Bezoutovy věty existují celá čísla u, v taková, že au + mv = 1. Existují tedy celá čísla x, y splňující ax + my = b, tj. platí ax = b (mod m). Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice a mocninné zbytky II O Nechť d = 1. Dle Bezoutovy věty existují celá čísla u, 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 - xf) = 0 (mod rn) a tedy x = x' (mod m). Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice a mocninné zbytky II Nechť d = 1. Dle Bezoutovy vety existují celá čísla u, 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 - xf) = 0 (mod rn) a tedy x = x' (mod m). O Nechť d > 1. Protože nutně č/|ď, máme po dosazení do vztahu ax = b + km za a = a'd, ď = //d, m = m7c/ a po vydělení číslem d kongruenční rovnici a'x = £/ (mod m7). Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice a mocninné zbytky II Nechť d = 1. Dle Bezoutovy vety existují celá čísla u, 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ě č/|ď, máme po dosazení do vztahu ax = b + km za a = a;d, Ď = //d, m = m7c/ a po vydělení číslem d kongruenční rovnici a;x = £/ (mod m7). Z případu 1 víme, že tato kongruenční rovnice má jediné řešení x = x0 (mod mf). Všechna řešení modulo m tvoří právě d následujících čísel X = X0,X0 + A77/,...,X0 + (cy- 1)^, (glOd/77). -= , Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice 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: ax" = b(modm). (1-4) Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice 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^171^^ (mod m). Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice 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^171^^ (mod m). Buďte tedy m, n přirozená čísla taková, že m > 2, n > 2, a celé číslo takové, že (a, m) = 1. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice 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^171^^ (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 x11 = a (mod m). (1.5) Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm 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 m1, m2,..., mr navzájem nesoudělná, a-i, a2,..., ar ab^,b2, ...,br libovolná celá čísla taková, že (ai ,mi) = (a2, m2) = • • • = (ar, mr) = 1. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm 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 m1, m2,..., mr navzájem nesoudělná, a-i, a2,..., ar ab\,bz, ...,br libovolná celá čísla taková, že (ai ,mi) = (a2, m2) = • • • = (ar, mr) = 1. Pa/c má systém SjX = £>/ (modm,-) (1.6) pro 1 < i < r právě jedno řešení modulo m = m-i • rn2,...../77r. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice 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 j -a, • u j + m j • v, = 1. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice 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 j -a, • u j + m j • v, = 1. Pronásobíme-li b\ máme a, • x, + m\ • y, = £>,, tj. a/x = bj (mod m,)) Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice 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 j -a, • u j + m j • v, = 1. Pronásobíme-li b\ máme a, • x, + m\ • y, = £>,, tj. a/x = bj (mod m,)) Předpokládejme, že toto řešení je ve tvaru x = Cj (mod A77/) (1.7) pro 1 < i < r. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice 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 j -a, • u j + m j • v, = 1. Pronásobíme-li b\ máme a, • x, + m\ • y, = £>,, tj. a/x = bj (mod m,)) Předpokládejme, že toto řešení je ve tvaru x = Cj (mod A77/) (1.7) pro 1 < i < r. Protože máme (mh rrij) = 1 pro / ^ y, máme ŕ m_ m_ m_\ _ h v /77-I ' A772 ' * * * ' mr' ~ Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice 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 j -a, • u j + m j • v, = 1. Pronásobíme-li b\ máme a, • x, + m\ • y, = £>,, tj. a/x = bj (mod m,)) Předpokládejme, že toto řešení je ve tvaru x = Cj (mod A77/) (1.7) pro 1 < i < r. Protože máme (mh rrij) = 1 pro / ^ y, máme ŕ m_ m_ m_\ _ h v /77-I ' A772 ' * * * ' mr' ~ Zejména tedy existují čísla , y2,..., yr tak, že mm m --7H---/2 H-----1---/r = 1 • Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice a mocninné zbytky VI Položme e,• = £ • y, pro 1 < i < r. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice a mocninné zbytky VI Položme e, = ™. ■ V\ pro 1 < / < r. Zřejmě platí e-i + £2 H-----h er = 1 (mod m), (1.8) Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice a mocninné zbytky VI Položme e, = ™. ■ V\ pro 1 < / < r. Zřejmě platí e-i + £2 H-----h er = 1 (mod m), (1.8) e, • e,- = 0 (mod m) pro / ^ y, (1.9) Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice a mocninné zbytky VI Položme e,• = ^ • y, pro 1 < i < r. Zřejmě platí e-i + £2 H-----h er = 1 (mod m), (1.8) e, • ey = 0 (mod m) pro / ^ y, (1.9) e, • e, = e, (mod m), (1-10) Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice a mocninné zbytky VI Položme e,• = £ • y, pro 1 < i < r. m Zřejmě platí e^ + e2-\-----h er = 1 (mod m), (1.8) e, • ey = 0 (mod m) pro / ^ y, (1.9) e, • e, = e, (mod m), (1-10) r 0 (mod m/) pro i ý j l 1 (mod /n,-) pro / = y. v 7 Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice a mocninné zbytky VI Položme e,• = ^ • y, pro 1 < i < r. Zrejmé platí e-i + £2 H-----h er = 1 (mod m), e, • ey = 0 (mod m) pro / ^ y, e, • e, = e, (mod m), _ í 0 (mod m j) pro / ^ y, 1 ~ \ 1 (mod rrij) pro / = y. Totiž e, • ey = m • c, e, • e, = ey- • e, = 1 • e, = e, (mod m), ey = rrij • ď, (e,-, mi) = 1. (1.8) (1.9) (1.10) (1.11) Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice a mocninné zbytky VI Položme e,• = ^ • y, pro 1 < i < r. Zrejmé platí e-i + £2 H-----h er = 1 (mod m), (1.8) e, • ey = 0 (mod m) pro / ^ y, (1.9) e, • e, = e, (mod m), (1-10) f 0 (mod m/) pro/V y, [ 1 (mod A77,) pro / = y. v 1 Totiž e, • ey- = m • c, e, • e, = ey • e, = 1 • e, = e, (mod m), ey = /r?/ • ď, (e/? m/) = 1. Položme x0 = c^e^+ c2e2 H-----h crer. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice a mocninné zbytky VII Máme pak z 1.11, že x0 = a (mod m i) pro 1 < i < r. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice a mocninné zbytky VII Máme pak z 1.11, že x0 = a (mod m i) pro 1 < i < r. Je tedy x0 společné řešení modulo m. Pro každé jiné řešení x'0 modulo m systému 1.7 máme x0 = Xq (mod mi) pro 1 < / < r a tedy také x0 = xL (mod m). Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice a mocninné zbytky VII Máme pak z 1.11, že x0 = a (mod m i) pro 1 < i < r. Je tedy x0 společné řešení modulo m. Pro každé jiné řešení x'0 modulo m systému 1.7 máme x0 = Xq (mod mi) pro 1 < / < r a tedy také x0 = Xq (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. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Kongruenční rovnice a mocninné zbytky VII Máme pak z 1.11, že x0 = a (mod m i) pro 1 < i < r. Je tedy x0 společné řešení modulo m. Pro každé jiné řešení x'0 modulo m systému 1.7 máme x0 = x'0 (mod mi) pro 1 < / < r a tedy také x0 = Xq (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ě ľa/Im... Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Řekneme, že a patří modulo m k exponentu d , pokud (a, m) = 1, ad = 1 (mod m), ale an ^ 1 (mod n) pro 1 < n < d. To ale není nic jiného, než že a je prvek rádu d v multiplikativní grupě Gm. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Lemma 1.3 Patří-li a modulo m k exponentu d, jsou čísla 1, a, a2,..., ad~ modulo m nekongruentní Je-li dále af = 1 (mod m), pak d\t. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Lemma 1.3 Patří-li a modulo m k exponentu d, jsou čísla 1, a, a2,..., aó~A modulo m nekongruentní. Je-li dále af = 1 (mod m), pak d\t. Důkaz. Nechť ak = ah (mod m), 0 < h < k < d. Protože (a, m) = 1, je ak~h = 1 (mod m). Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Patří-li a modulo m k exponentu d, jsou čísla 1, a, a2,..., ad~ modulo m nekongruentní Je-li dále af = 1 (mod m), pak d\t. Důkaz. Nechť ak = ah (mod m), 0 < h < k < d. Protože (a, m) = 1, je ak~h = 1 (mod m). To je však spor sO 1, pak platí 1 < ^ < (p(m) (g^)^1 = (g^)i = 1 (modm). Pak ale nemůže být gv primitivní kořen moc^Q X i ► < i ► i Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty irupa Gm Buď p prvočíslo. Pak Gp je cyklická. Zejména tedy existuje primitivní kořen modulo p. Důkaz. Pro p = 2 je tvrzení věty triviální. Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty irupa Gm Buď p prvočíslo. Pak Gp je cyklická. Zejména tedy existuje primitivní kořen modulo p. Důkaz. Pro p = 2 je tvrzení věty triviální. Nechť p je v dalším liché prvočíslo. Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty irupa Gm Buď p prvočíslo. Pak Gp je cyklická. Zejména tedy existuje primitivní kořen modulo p. Důkaz. Pro p = 2 je tvrzení věty triviální. Nechť p je v dalším liché prvočíslo. Pro d\(p - 1) označme x(d) počet zbytkových tříd z Gp, které patří k exponentu d modulo p. Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty irupa Gm Buď p prvočíslo. Pak Gp je cyklická. Zejména tedy existuje primitivní kořen modulo p. Důkaz. Pro p = 2 je tvrzení věty triviální. Nechť p je v dalším liché prvočíslo. Pro d\(p - 1) označme x(d) počet zbytkových tříd z Gp, které patří k exponentu d modulo p. Máme ukázat, že x(p - 1) > 0. Podle Tvrzení 1.5 je pak dokonce (p(p - 1) = x(p - 1). Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty irupa Gm Buď p prvočíslo. Pak Gp je cyklická. Zejména tedy existuje primitivní kořen modulo p. Důkaz. Pro p = 2 je tvrzení věty triviální. Nechť p je v dalším liché prvočíslo. Pro d\(p - 1) označme x(d) počet zbytkových tříd z Gp, které patří k exponentu d modulo p. Máme ukázat, že x(p - 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. Buď p prvočíslo. Pak Gp je cyklická. Zejména tedy existuje primitivní kořen modulo p. Důkaz. Pro p = 2 je tvrzení věty triviální. Nechť p je v dalším liché prvočíslo. Pro d\(p - 1) označme x(d) počet zbytkových tříd z Gp, které patří k exponentu d modulo p. Máme ukázat, že x(p - 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,..., aó~A navzájem nekongruentní řešení rovnice xd -n1 =,0 (modp). t Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty 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 - aó~A) (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 (oř, k) = 1. To znamená, že mezi řešení přináleží 2. i Důkaz. MA Z a = glog0a(mod m) a b = glog0Ď(mod m) obdržíme ab = glog9a+log9Ď(modm). 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 = ^^(mod m) obdržíme 4. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Pátá vlastnost je založena na Fermat-Eulerově větě: Tvrzení 1.8 Buď p liché prvočíslo tak, že číslo a není dělitelné p. Kongruenční rovnice n t rx má právě d = (n, pr_1 (p - 1)) nekongruentních řešení, pokud d dělílogga. Jinak je tato kongruence neřešitelná. Důkaz. Tvrzení věty se logaritmováním převede na lineární kongruenční rovnici nlog^x = log^a (modpr-1 (p _ == _ == > Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Tvrzení 1.9 Buď p liché prvočíslo tak, že číslo a není dělitelné p, d = (n,p^-1(p-1)). Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Tvrzení 1.9 Buď p liché prvočíslo tak, že číslo a není dělitelné p, d = (a?. pr_1 (p - 1)). Kongruenční rovnice x11 = a (modpr) má právě řešení právě tehdy, když platí kongruenční rovnice a>'-1(P-i) = 1 (modp^). (1.15) Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Tvrzení 1.9 Buď p liché prvočíslo tak, že číslo a není dělitelné p, d = (a?. pr_1 (p - 1)). Kongruenční rovnice x11 = a (modpr) má právě řešení právě tehdy, když platí kongruenční rovnice a>'-1(P-i) = 1 (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 log^a = h- d. Pak platí a = gl°Š9a = gh'd (modpr). Tedy Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Nechť obráceně platí kongruenční rovnice (1.15). Položme \± = logga. Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty irupa Gm Nechť obráceně platí kongruenční rovnice (1.15). Položme [i = log^a. Protože a = (modpr), máme gd'Pr~^P-^ = 1 (modpr). Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty irupa Gm Nechť obráceně platí kongruenční rovnice (1.15). Položme [i = log^a. Protože a = (modpr), máme gd'Pr~^P-^ = 1 (modpr). Protože g je primitivní kořen modulo pr, je ^ celé číslo, tj. d dělí li. Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty irupa Gm Nechť obráceně platí kongruenční rovnice (1.15). Položme [i = log^a. Protože a = (modpr), máme gd'Pr~^P~^ = 1 (modpr). Protože g je primitivní kořen modulo pr, je ^ celé číslo, tj. d dělí li. Tedy dle Tvrzení 1.8 je kongruenční rovnice řešitelná. Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty irupa Gm Věta 1.10 Buď f(x) polynom v proměnné x s celočíselnými koeficienty. Pak počet řešení kongruenční rovnice f(x) = 0 (mod m), m = ľl^pf (1.16) je číslo N = ni n2.....nr, přičemž n-, je počet řešení rovnice f(x) = 0 (mod pf) (1.17) pro 1 < i < r. Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty irupa Gm Věta 1.10 Buď f{x) polynom v proměnné x s celočíselnými koeficienty Pak počet řešení kongruenční rovnice f{x) = 0 (modm), m = l~lf=1 pf' (1.16) je číslo N = n-i n2.....nr, přičemž n j je počet řešení rovnice f(x) = 0 (modpf) (1.17) pro 1 < i < r. Důkaz. Řešitelnost kongruenční rovnice (1.16) nastává právě tehdy, když je systém kongruečních rovnic (1.17) řešitelný. Věta 1.10 Buď f (x) polynom v proměnné x s celočíselnými koeficienty Pak počet řešení kongruenční rovnice f{x) = 0 (modm), m = l~lf=1 pf' (1.16) je číslo N = n-i n2.....nr, přičemž n j je počet řešení rovnice f(x) = 0 (modpf) (1.17) pro 1 < i < r. Důkaz. Řešitelnost kongruenční rovnice (1.16) nastává právě tehdy, když je systém kongruečních rovnic (1.17) řešitelný. V případě řešitelnosti každé jednotlivé kongruenční rovnice označme x = c, (mod pf) řešení /-té kongrunční rovnice. Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty irupa Gm Obdržíme pak lineární systém kongruencí, který má dle Věty 1.2 jednoznačně určené řešení (mod m). Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Obdržíme pak lineární systém kongruencí, který má dle Věty 1.2 jednoznačně určené řešení (mod m). Probíhají-li c, všechna nekongruentní řešení (těch je n,), získáme celkem N řešení (mod m). Důsledek 1.11 Počet řešení kongruenční rovnice xs = x (modm). m = V\rl=^p) Si (1.18) je číslo N = n-i n2 nr, přičemž nf je počet řešení rovnice xs = x (modpf) (1.19) pro 1 < i < r. Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty irupa Gm Tvrzení 1.12 Počet řešení kongruenční rovnice xs = x (modp), (1.20) kde p je prvočíslo, je roven 1 + (p - 1, s - 1). Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty irupa Gm Tvrzení 1.12 Počet řešení kongruenční rovnice xs = x (modp), (1.20) kde p je prvočíslo, je roven 1 + (p - 1, s - 1). Důkaz. Uvažme dva případy. Nechť x je číslo soudělné s p tj. x = p (mod p) - takové x je pouze jedno (p) a je řešením. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Tvrzení 1.12 Počet řešení kongruenční rovnice xs = x {modp), (1.20) kde p je prvočíslo, je roven 1 + (p - 1, s - 1). Důkaz. Uvažme dva případy. Nechť x je číslo soudělné s p tj. x = p (mod p) - takové x je pouze jedno (p) a je řešením. Nechť x je nesoudělné s p. Množina všech nesoudělných čísel s p tvoří cyklickou grupu stupně p - 1 a z předchozího víme, že existuje právě (p - 1, s - 1) prvků této grupy splňujících (1.20). Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty irupa Gm ' Důsledek 1.13 Počet řešení kongruenční rovnice xs = x (modm). m = n-=1p;- (1.21) je číslo N = nf=1 (1 + (pí - 1, s - 1)). Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty írupa Gm Uvažme pro celá čísla a,b,c,m {m> 1, a ^ 0 (mod m)) kvadratickou kongruenci ax2 + b • x + c = 0 (mod m). (1.22) Vynásobením 4a převedeme rovnici na tvar (2ax + bf = b2 - 4ac (mod m). (1.23) Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Uvažme pro celá čísla a,b,c,m {m> 1, a ^ 0 (mod m)) kvadratickou kongruenci ax2 + b • x + c = 0 (mod m). (1.22) Vynásobením 4a převedeme rovnici na tvar (2ax + bf = b2 - 4ac (mod m). (1.23) To znamená, že jsme schopni plně vyřešit kvadratickou kongruenci (1.22), jestliže umíme vyřešit speciální případ x2 = a (mod m). (1.24) Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty írupa Gm Tím se celá problematika převede na problém kvadratických zbytků. Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty írupa Gm Tím se celá problematika převede na problém kvadratických zbytků. Z důkazu Věty 1.10 víme, že se lze dále omezit na řešení rovnice x2 = a(modps), (1.25) kde p je prvočíslo. Zároveň lze předpokládat, že (a, p) = 1. Totiž v případě, že p dělí a máme © * = 0 (modp), pokud je s = 1, O v případě s > 1 by muselo být x = py tj. py2 = a; (modps_1), a = pa'. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Tím se celá problematika převede na problém kvadratických zbytků. Z důkazu Věty 1.10 víme, že se lze dále omezit na řešení rovnice x2 = a(modps), (1.25) kde p je prvočíslo. Zároveň lze předpokládat, že (a, p) = 1. Totiž v případě, že p dělí a máme © * = 0 (modp), pokud je s = 1, O v případě s > 1 by muselo být x = py tj. py2 = a; (modps_1), a = pa'. Nutně pak á = pa" tj. získáme kongruenční rovnici y2 = a (modps~2). Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty írupa Gm Uvažme nyní kongruenční rovnici tvaru x2 = a (modps), (a, p) = 1. (1.26) Snadným ověřením získáme řešení pro p = 2. Uvažme nyní kongruenční rovnici tvaru x2 = a (modps), (a, p) = 1. Snadným ověřením získáme řešení pro p = 2. O s = 1 : Existuje právě jedno řešení a to x = 1. O S = 2 : O a = 1 (mod 4) : Existují právě dvě řešení. O a = -1 (mod 4) : Neexistuje žádné řešení. O S > 3 : O a = 1 (mod 8) : Existují právě čtyři řešení. O a 1 (mod 8) : Neexistuje žádné řešení. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Theorem 1.14 Je-li p liché prvočíslo, pak má kongruence (1.26) buď žádné nebo právě dvě řešení Je-li a kvadratický zbytek modulo p, je také kvadratický zbytek modulo ps a obráceně. Důkaz. Víme, že (2, ps"1 (p - 1) = 2. Podle Věty 1.8 má pak kongruenční rovnice (1.26) právě dvě řešení, pokud loga = 0 (mod 2) a žádné řešení, pokud loga = 1 (mod 2). Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Theorem 1.14 Je-li p liché prvočíslo, pak má kongruence (1.26) buď žádné nebo právě dvě řešení Je-li a kvadratický zbytek modulo p, je také kvadratický zbytek modulo ps a obráceně. Důkaz. Víme, že (2, ps"1 (p - 1) = 2. Podle Věty 1.8 má pak kongruenční rovnice (1.26) právě dvě řešení, pokud loga = 0 (mod 2) a žádné řešení, pokud loga = 1 (mod 2). Musíme ještě ukázat, že loga je nezávisle na s dělitelné 2 nebo ne. MA Theorem 1.14 Je-li p liché prvočíslo, pak má kongruence (1.26) buď žádné nebo právě dvě řešení Je-li a kvadratický zbytek modulo p, je také kvadratický zbytek modulo ps a obráceně. Důkaz. Víme, že (2, ps"1 (p - 1) = 2. Podle Věty 1.8 má pak kongruenční rovnice (1.26) právě dvě řešení, pokud loga = 0 (mod 2) a žádné řešení, pokud loga = 1 (mod 2). Musíme ještě ukázat, že loga je nezávisle na s dělitelné 2 nebo ne. Buď g primitivní kořen modulo ps pro libovolné s > 1 a fis = log^a vzhledem k modulu ps. Ze vztahu a = g^s (mod ps), a = g^s = g^ (mod p), plyne = ^ (mod p - 1) a proto = ^ (mod 2). ■ Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Stačí se tedy zřejmě omezit na případ, že s = 1. Věta 1.15 Je-li p liché prvočíslo, pak máme práve tolik kvadratických zbytků jako nezbytků. Kvadratické zbytky modulo p jsou určeny 2 o2 P-1 2 a= -K2' i ' ' ' i 2 modp. Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty írupa Gm Stačí se tedy zřejmě omezit na případ, že s = 1. Je-li p liché prvočíslo, pak máme právě tolik kvadratických zbytků jako nezbytků. Kvadratické zbytky modulo p jsou určeny a = 12,22,...,^2 modp. Důkaz. Uvedená čísla jsou zřejmě modulo p nekongruentní. Totiž je-li b2 = c2 (modp), kde 1 < b,c < máme (b - c){b + c) = 0 (modp). Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Stačí se tedy zřejmě omezit na případ, že s = 1. Věta 1.15 Je-li p liché prvočíslo, pak máme práve tolik kvadratických zbytků jako nezbytků. Kvadratické zbytky modulo p jsou určeny 2 o2 P-1 2 a= -K2' i ' ' ' i 2 modp. Důkaz. Uvedená čísla jsou zřejmě modulo p nekongruentní. Totiž je-li b2 = c2 (modp), kde 1 < b, c < máme (b - c){b + c) = 0 (modp). Protože 1 < b + c < p, máme b - c = 0 (mod p), tj. b = c. Stačí se tedy zřejmě omezit na případ, že s = 1. Věta 1.15 Je-li p liché prvočíslo, pak máme právě tolik kvadratických zbytků jako nezbytků. Kvadratické zbytky modulo p jsou určeny a = 12,22,...,^2 modp. Důkaz. Uvedená čísla jsou zřejmě modulo p nekongruentní. Totiž je-li b2 = c2 (modp), kde 1 < b,c < máme (b - c){b + c) = 0 (modp). Protože 1 < b + c < p, máme b - c = 0 (mod p), tj. b = c. Protože dále (p - k)2 = k2 (mod p), musí být každý kvadratický zbytek kongruentní s jedním z výše uvedených čísel. Tímto je tvrzení dokázáno. ^ Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Lemma 1.16 Řešení rovnice Fl x2 + B. x = c (modp. q) lze obdržet jako kombinaci řešení u, v rovnic x2 + B- x = C (mod p) x2 + B • x = C (mod q) a přirozených čísel a, b splňujících a b a pak splňuje (1.27). 1 (mod p), a = 0 (mod q), 0 (mod p) Ď = 1 (mod q), x = a • L/ + Ď • v (1.27) (1.28) (1.29) (1.30) Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Lemma 1.16 Řešení rovnice Fl x2 + B. x = c (modp. q) lze obdržet jako kombinaci řešení u, v rovnic x2 + B- x = C (mod p) x2 + B • x = C (mod q) a přirozených čísel a, b splňujících a b a pak splňuje (1.27). 1 (mod p), a = 0 (mod q), 0 (mod p) Ď = 1 (mod q), x = a • L/ + Ď • v (1.27) (1.28) (1.29) (1.30) Důkaz. MA Plyne bezprostředně z předchozích tvrzení. □ Čpi - = ! Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Buď p liché prvočíslo, p nedelí číslo a. Legendruv symbol | j definujeme jako a P +1 pokud je a kvadratický zbytek modulo p, -1 pokud je a kvadratický nezbytek modulo p. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Buď p liché prvočíslo, p nedělí číslo a. Legendrův symbol (j^ definujeme jako / a\ _ j +1 pokud je a kvadratický zbytek modulo p, \pj ~ \ -1 pokud je a kvadratický nezbytek modulo p. Mimo jiné je vhodné vytvořit pravidla pro výpočet Legendrova symbolu. Evidentní jsou následující vlastnosti (p) = (p) Pro^ = a (modp) = 1 Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty írupa Gm MA Z Fermat-Eulerovy věty víme, že ap_1 = 1 (modp) a proto platí a V = ±1 (modp). Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty írupa Gm MA Z Fermat-Eulerovy věty víme, že ap_1 = 1 (modp) a proto platí a V = ±1 (modp). Podle Věty 1.9 je podmínka a V = 1 (modp) dostatečná a nutná pro řešitelnost kongruenční rovnice x2 = a (modp), (a, p) = 1. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm MA Z Fermat-Eulerovy věty víme, že ap_1 = 1 (modp) a proto platí a V = ±1 (modp). Podle Věty 1.9 je podmínka a V = 1 (modp) dostatečná a nutná pro řešitelnost kongruenční rovnice x2 = a (modp), (a, p) = 1. Fl Máme tedy tzv. Eulerovo kritérium: ' Věta 1.17 _' I ) = a 2 modp. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm MA Z Fermat-Eulerovy věty víme, že ap_1 = 1 (modp) a proto platí a V = ±1 (modp). Podle Věty 1.9 je podmínka a V = 1 (modp) dostatečná a nutná pro řešitelnost kongruenční rovnice x2 = a (modp), (a, p) = 1. Fl Máme tedy tzv. Eulerovo kritérium: ' Věta 1.17_' I ) = a 2 modp. Z tohoto kritéria lze odvodit řadu důležitých faktů:MA Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty írupa Gm Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm p ' -) = (-d p2-i 8 Důkaz. První vztah plyne bezprostředně z Eulerova kritéria. Abychom dokázali druhý vztah, uvažme součin p-1 2 p-1 II(-1)/í/( = (^V)!(-i) p2-1 8 /C=1 Je-li v součinu číslo k liché, zaměníme (-/c) modulo p číslem (p - k) o obdržíme rovnost p-1 2 JJ(-1 = 2 • 4 • 6 • • • • (p - 1) = (^—*-)!2V modp. /c=1 Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty írupa Gm Kvadratické kongruence X - Pokračování důkazu Tvrzení 1.19 Protože ale p nedělí {^-)\, máme po vykráčení a z Eulerova kritéria (-j =2-r=(-1)-r. Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty írupa Gm Kvadratické kongruence X - Pokračování důkazu Tvrzení 1.19 Protože ale p nedělí {^-)\, máme po vykráčení a z Eulerova kritéria (-j =2-r=(-1)-r. Lemma 1.20 Je-// p prvočíslo tvaru 4/c - 1 ad kvadratický zbytek modulo p, řešení kongruenční rovnice tvaru y2 = c/(modp) (1.31) je dáno předpisem y = dk (modp). (1.32) Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Důkaz. Z Eulerova kritéria máme, že -)=1= c/V modp. P Důkaz. Z Eulerova kritéria máme, že -)=1= c/V modp. P Protože k = \{p + 1), máme Gfi(p+i)afi(p+i) = c/>+1) = d^P-^d = oř modp. Zkombinujeme-li předchozí úvahy, dostaneme následují tvrzení Tvrzení 1.21 Za předpokladu, že jak p tak q jsou kongruentní s 3 modulo 4, lze dešifrovací proceduru provést v polynomiálním čase. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Zkombinujeme-li předchozí úvahy, dostaneme následují tvrzení Tvrzení 1.21 Za předpokladu, že jak p tak q jsou kongruentní s 3 modulo 4, lze dešifrovací proceduru provést v polynomiálním čase. Důkaz. Příjemci, který zná faktory p a q a ví, že kryptogram je kvadratický zbytek, stačí jenom aplikovat předchozí lemmata. ■ Rabin ve skutečnosti dokázal víc než Tvrzení 1.21. Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty írupa Gm Fl Rabin ve skutečnosti dokázal víc než Tvrzení 1.21. Totiž dokázal, že i v případě, že prvočísla p a q nejsou v tomto speciálním tvaru, kongruenční rovnice modulo p a modulo q lze řešit náhodným algoritmem v polynomiálním čase. Faktorizace Napadání RSA Algebraické vlastnosti bngruenční rovnice Kvadráty írupa Gm Fl Rabin ve skutečnosti dokázal víc než Tvrzení 1.21. Totiž dokázal, že i v případě, že prvočísla p a q nejsou v tomto speciálním tvaru, kongruenční rovnice modulo p a modulo q lze řešit náhodným algoritmem v polynomiálním čase. Poznamenejme, že praktickou nevýhodou Rabínova schématu je, že příjemce obdrží čtyři možné zprávy, z nichž má vybrat tu správnou. Obvykle to lze provést tím, že má nějakou dodatečnou informaci - např. že po převedení z binárního do textového tvaru je zpráva psaná v angličtině. Fl Rabin ve skutečnosti dokázal víc než Tvrzení 1.21. Totiž dokázal, že i v případě, že prvočísla p a q nejsou v tomto speciálním tvaru, kongruenční rovnice modulo p a modulo q lze řešit náhodným algoritmem v polynomiálním čase. Poznamenejme, že praktickou nevýhodou Rabínova schématu je, že příjemce obdrží čtyři možné zprávy, z nichž má vybrat tu správnou. Obvykle to lze provést tím, že má nějakou dodatečnou informaci - např. že po převedení z binárního do textového tvaru je zpráva psaná v angličtině. Mr. x však nezná faktory p a q čísla N a musí se zabývat mnohonásobně obtížnějším problémem. Že je tomu skutečně tak, plyne z níže uvedené druhé Rabínovy věty. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Věta 1.22 Označme DN množinu všech takových d, 0 < d < N, že existuje řešení kongruenční rovnice i y2 = d (mod A/). (1.33) Dt Jestliže pro alespoň \Jq^\ takovýchto d jsme schopni najít takové y, pak jsme schopni najít faktor N v náhodné polynomiální době. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Lemma 1.23 Jsou-li x, y g Z/v celá čísla modulo N taková, že x2 = y2 (mod A/), x 7^ ±y (mod A/) /sol/ pa/c (x + y, A/) a (x - y, A/) dělitelé N. (1.34) Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Lemma 1.23 Jsou-li x, y g Z/v celá čísla modulo N taková, že x2 = y2 (mod A/), x 7^ ±y (mod A/) /sol/ pa/c (x + y, A/) a (x - y, A/) dělitelé N. (1.34) Zejména pro N = p- q, p aq prvočísla je (x + y, N) prvočíselný dělitel N. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Lemma 1.23 Jsou-li x, y g Z/v celá čísla modulo N taková, že x2 = y2 (mod A/), x 7^ ±y (mod A/) ysoL/ pa/c (x + y, A/) a (x - y, A/) dělitelé N. (1.34) Zejména pro N = p- q, p aq prvočísla je (x + y, N) prvočíselný dělitel N. Důkaz, x2 = y2 (mod A/) implikuje x2 = y2 + rA/5 kde r g Z. Tudíž (x - y)(x + y) = rA/. Faktorizace Napadání RSA Algebraické vlastnosti Kongruenční rovnice Kvadráty Grupa Gm Lemma 1.23 Jsou-li x, y g Z/v celá čísla modulo N taková, že x2 = y2 (mod A/), x 7^ ±y (mod A/) /sol/ pa/c (x + y, A/) a (x - y, A/) dělitelé N. (1.34) Zejména pro N = p- q, p aq prvočísla je (x + y, N) prvočíselný dělitel N. Důkaz, x2 = y2 (mod N) implikuje x2 = y2 + rA/5 kde r e Z. Tudíž (x - y)(x + y) = rN. Větu 1.22 lze neformálně přepsat do tvaru Rozšifrování Rabínova systému s veřejným klíčem je ekvivalentní nalezení efektivního algoritmu pro faktorizaci. Rozšifrování Rabínova systému s veřejným klíčem je ekvivalentní nalezení efektivního algoritmu pro faktorizaci. Důkaz. Předpokládejme, že máme algoritmus A, který pro dané (g, N) a pro [j^g^l takovýchto q dává na výstupu odmocninu z q modulo N. Rozšifrování Rabínova systému s veřejným klíčem je ekvivalentní nalezení efektivního algoritmu pro faktorizaci. Důkaz. Předpokládejme, že máme algoritmus A, který pro dané (g, N) a pro [j^g^l takovýchto q dává na výstupu odmocninu z q modulo N. Pak můžeme faktorizovat N iterováním následujících kroků: Vyberme náhodně z ze ZN tak, že (z, N) = 1 a vypočtěme q = z2 (mod A/). Rozšifrování Rabínova systému s veřejným klíčem je ekvivalentní nalezení efektivního algoritmu pro faktorizaci. Důkaz. Předpokládejme, že máme algoritmus A, který pro dané (q, N) a pro [j^g^l takovýchto q dává na výstupu odmocninu z q modulo N. Pak můžeme faktorizovat N iterováním následujících kroků: Vyberme náhodně z ze ZN tak, že (z, N) = 1 a vypočtěme q = z2 (mod A/). Vložme na vstup algoritmu A dvojici (q, A/). Pokud A má za výstup druhou odmocninu z q různou od z nebo -z modulo A/, pak Lemma 1.23 nám dává, že jsme schopni faktorizovat N. Rozšifrování Rabínova systému s veřejným klíčem je ekvivalentní nalezení efektivního algoritmu pro faktorizaci. Důkaz. Předpokládejme, že máme algoritmus A, který pro dané (q, N) a pro [j^g^l takovýchto q dává na výstupu odmocninu z q modulo N. Pak můžeme faktorizovat N iterováním následujících kroků: Vyberme náhodně z ze ZN tak, že (z, N) = 1 a vypočtěme q = z2 (mod A/). Vložme na vstup algoritmu A dvojici (q, A/). Pokud A má za výstup druhou odmocninu z q různou od z nebo -z modulo A/, pak Lemma 1.23 nám dává, že jsme schopni faktorizovat N. Očekávaný počet iterací algoritmu bude malý, protože je -t-L---ní šance na faktorizaci N v každé iteraci. 2log N ^ *0 O* Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Fermat Důsledky Další možné útoky Speciální přístupy D čem to bude uy oici 11 o v^i^jiiyiii r\ 11 v_/ v_7111 J J fp ktnrÍ7ppp IQlVlUl IĺQvC O Jak se napadá RSA-algoritmus? • Narušení RSA-algoritmu prostřednictvím faktorizace modulu • Pollardova rho-metoda • Fermatova faktorizace • Důsledky nových faktorizačních algoritmů • Další možné útoky • Speciální přístupy k dešifrování tok Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Dalsi mozne útoky Fermat Speciální přístupy Narušení RSA faktorizací modulu N = p • q\ Faktorizace modulu N je nepoměrně obtížnější než jeho konstrukce, tj. nalezení prvočísel p a q. Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Dalsi mozne útoky Fermat Speciální přístupy Narušení RSA faktorizací modulu N = p • q\ Faktorizace modulu N je nepoměrně obtížnější než jeho konstrukce, tj. nalezení prvočísel p a q. V době vzniku RSA-algoritmu (1978) byla 50-místná prvočísla bezpečná, což dnes už není pravda. Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Dalsi mozne útoky Fermat Speciální přístupy Narušení RSA faktorizací modulu N = p • q\ Faktorizace modulu N je nepoměrně obtížnější než jeho konstrukce, tj. nalezení prvočísel p a q. V době vzniku RSA-algoritmu (1978) byla 50-místná prvočísla bezpečná, což dnes už není pravda. Proto se v současné době pracuje se 100-místnými prvočísly. Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Dalsi mozne útoky Fermat Speciální přístupy Narušení RSA faktorizací modulu N = p • q\ Faktorizace modulu N je nepoměrně obtížnější než jeho konstrukce, tj. nalezení prvočísel p a q. V době vzniku RSA-algoritmu (1978) byla 50-místná prvočísla bezpečná, což dnes už není pravda. Proto se v současné době pracuje se 100-místnými prvočísly. Přitom není vyloučené, že bude možno najít algoritmus na faktorizaci, který pracuje v polynomiálmím čase. Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Dalsi mozne útoky Fermat Speciální přístupy Narušení RSA faktorizací modulu N = p • q\ Faktorizace modulu N je nepoměrně obtížnější než jeho konstrukce, tj. nalezení prvočísel p a q. V době vzniku RSA-algoritmu (1978) byla 50-místná prvočísla bezpečná, což dnes už není pravda. Proto se v současné době pracuje se 100-místnými prvočísly. Přitom není vyloučené, že bude možno najít algoritmus na faktorizaci, který pracuje v polynomiálmím čase. Zároveň se nepodařilo dokázat, že by faktorizace šifrovacího modulu byla ekvivalentní s bezpečností RSA-systému. Mohla by se totiž najít metoda, jak tento systém narušit bez faktorizace N. Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Dalsi mozne útoky Fermat Speciální přístupy Narušení RSA faktorizací modulu N = p • q\ Faktorizace modulu N je nepoměrně obtížnější než jeho konstrukce, tj. nalezení prvočísel p a q. V době vzniku RSA-algoritmu (1978) byla 50-místná prvočísla bezpečná, což dnes už není pravda. Proto se v současné době pracuje se 100-místnými prvočísly. Přitom není vyloučené, že bude možno najít algoritmus na faktorizaci, který pracuje v polynomiálmím čase. Zároveň se nepodařilo dokázat, že by faktorizace šifrovacího modulu byla ekvivalentní s bezpečností RSA-systému. Mohla by se totiž najít metoda, jak tento systém narušit bez faktorizace N. Zatím jsou však pokusy o narušení bezpečnosti RSA-systému založeny hlavně na faktorizaci. Lze například dokázat, že výpočet dešifrovacího exponentu ř je ekvivalentní faktorizaci Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Dalsi mozne útoky Fermat Speciální přístupy Narušení RSA faktorizací modulu N = p • q II Prvním algoritmem, který nás napadne, je tzv. pokusné dělení (Trial Division) čísly 2,3,..., [VAŽ]. Postup lze urychlit tak, že dělíme jen čísly 2,3 a pak čísly tvaru 6/c - 1,6/c + 1 pro k = 15 2,.... Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Dalsi mozne útoky Fermat Speciální přístupy Narušení RSA faktorizací modulu N = p • q II Prvním algoritmem, který nás napadne, je tzv. pokusné dělení (Trial Division) čísly 2,3,..., [VAŽ]. Postup lze urychlit tak, že dělíme jen čísly 2,3 a pak čísly tvaru 6/c - 1,6/c + 1 pro k = 15 2,.... Další používanou metodou je Pollardova p - 1 a p + 1 metoda. Základem metody je následující tvrzení: Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Dalsi mozne útoky Fermat Speciální přístupy Narušení RSA faktorizací modulu N = p • q II Prvním algoritmem, který nás napadne, je tzv. pokusné dělení (Trial Division) čísly 2,3,..., [VAŽ]. Postup lze urychlit tak, že dělíme jen čísly 2,3 a pak čísly tvaru 6/c - 1,6/c + 1 pro k = 15 2,.... Další používanou metodou je Pollardova p - 1 a p + 1 metoda. Základem metody je následující tvrzení: rTheorem2.1 Si/ď n = p- q, p,qj prvočísla, r - 1 Ď, r Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Dalsi mozne útoky Fermat Speciální přístupy Narušení RSA faktorizací modulu N = p • q II Prvním algoritmem, který nás napadne, je tzv. pokusné dělení (Trial Division) čísly 2,3,..., [VAŽ]. Postup lze urychlit tak, že dělíme jen čísly 2,3 a pak čísly tvaru 6/c - 1,6/c + 1 pro k = 15 2,.... Další používanou metodou je Pollardova p -1 a p + 1 metoda. Základem metody je následující tvrzení: rTheorem2.1 Si/ď n = p - q, p,qj prvočísla, r - 1 Ď, r Důkaz. Podle Fermatovy věty platí ar_1 = 1 mod r a tedy i ab = 1 mod r tj. r\(ab - 1). Zároveň však r\n. Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Dalsi mozne útoky Fermat Speciální přístupy Narušení RSA faktorizací modulu N = p • q III Aby se výše uvedená věta dala využít, je nutno najít vhodná čísla a, b. Nalezení a je snadné. Stačí zvolit nějaké malé prvočíslo a přesvědčit, zda je či není dělitelem n - pokud by bylo dělitelem, našli bychom faktorizaci čísla n a tím byli hotovi. Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Dalsi mozne útoky Fermat Speciální přístupy Narušení RSA faktorizací modulu N = p • q III Aby se výše uvedená věta dala využít, je nutno najít vhodná čísla a, b. Nalezení a je snadné. Stačí zvolit nějaké malé prvočíslo a přesvědčit, zda je či není dělitelem n - pokud by bylo dělitelem, našli bychom faktorizaci čísla n a tím byli hotovi Volba Ď je obtížnější, je třeba ho najít postupným zkoušením. Přitom se obvykle za b volí čísla tvaru bj = nsn(1,2,...,/). Tato čísla je vhodné volit z toho důvodu, že mají mnoho vlastních dělitelů a je tedy velká šance na splnění podmínky r- 1 b. Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Dalsi mozne útoky Fermat Speciální přístupy Narušení RSA faktorizací modulu N = p • q III Aby se výše uvedená věta dala využít, je nutno najít vhodná čísla a, b. Nalezení a je snadné. Stačí zvolit nějaké malé prvočíslo a přesvědčit, zda je či není dělitelem n - pokud by bylo dělitelem, našli bychom faktorizaci čísla n a tím byli hotovi. Volba Ď je obtížnější, je třeba ho najít postupným zkoušením. Přitom se obvykle za b volí čísla tvaru bj = nsn(1,2,...,/). Tato čísla je vhodné volit z toho důvodu, že mají mnoho vlastních dělitelů a je tedy velká šance na splnění podmínky r-J\\b. Algoritmus se hodí na nalezení menších prvočíselných dělitelů čísla n. Touto metodou bylo např. faktorizované číslo 2257 - 1 jako součin tří různých prvočísel. <*><*><*> i ^ Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Fermat Důsledky Další možné útoky Speciální přístupy Pollardova rho-metoda I Další známou metodou je Pollardova rho-metoda (Monte Carlo), kterou se obvykle najdou malé prvočíselné dělitele modulu N asi po ^/P cyklech programu. Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Fermat Důsledky Další možné útoky Speciální přístupy Pollardova rho-metoda I Další známou metodou je Pollardova rho-metoda (Monte Carlo), kterou se obvykle najdou malé prvočíselné dělitele modulu N asi po ^/P cyklech programu. Metoda začíná výběrem libovolné nelineární funkce f s celočíselnými koeficienty, nejčastěji f(x) = x2 + c, c ^ 0, -2 a volbou počáteční hodnoty x0, kterou lze zvolit náhodně. V dalších krocích se rekurentně počítají hodnoty posloupnosti xy+1 = f(Xj) mod N, j = 0,1,2,____ Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Fermat Důsledky Další možné útoky Speciální přístupy Pollardova rho-metoda I Další známou metodou je Pollardova rho-metoda (Monte Carlo), kterou se obvykle najdou malé prvočíselné dělitele modulu N asi po ^/p cyklech programu. Metoda začíná výběrem libovolné nelineární funkce f s celočíselnými koeficienty, nejčastěji f(x) = x2 + c, c ^ 0, -2 a volbou počáteční hodnoty x0, kterou lze zvolit náhodně. V dalších krocích se rekurentně počítají hodnoty posloupnosti xy+1 = f(Xj) mod A/, j = 0,1,2,____ Pomocí pravděpodobnostních úvah lze dokázat, že výsledná posloupnost bude skoroperiodická. To znamená, že po jisté době lze očekávat výskyt dvou hodnot xj,xk, pro které platí Xj ^ xk mod A/, N = p • q x; = xk mod p. Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Fermat Důsledky Další možné útoky Speciální přístupy Pollardova rho-metoda II To ale znamená, že (xy - xkl N) = p. Hledání největšího společného dělitele lze však provést Euklidovým algoritmem s malou složitostí. Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Fermat Důsledky Další možné útoky Speciální přístupy Pollardova rho-metoda II To ale znamená, že (xy - xkl N) = p. Hledání největšího společného dělitele lze však provést Euklidovým algoritmem s malou složitostí. Algoritmus se ještě trochu upraví: kdyby se tímto způsobem porovnávaly všechny rozdíly xk - xy pro všechna j < k, počet operací by neúměrně narůstal. Proto postupujeme následovně: Faktorizace Napadání RSA Algebraické vlastnosti Faktorizace Pollard Fermat Důsledky Další možné útoky Speciální přístupy Pollardova rho-metoda II To ale znamená, že (xy- - xkl N) = p. Hledání největšího společného dělitele lze však provést Euklidovým algoritmem s malou složitostí. Algoritmus se ještě trochu upraví: kdyby se tímto způsobem porovnávaly všechny rozdíly xk - xy pro všechna j < k, počet operací by neúměrně narůstal. Proto postupujeme následovně: Předpokládejme, že máme už spočítané xk, přičemž k je h + 1 -bitové číslo, 2h Protože p a q jsou různá prvočísla, nemusíme se bát toho, že by N bylo úplným čtvercem nějakého prvočísla. Pokud jsou prvočísla p a q blízko, resp. rozdíl |p - q\ je malý, je číslo ^ jen o málo větší než \fŇ. Věnujme se pro okamžik tzv. Fermatově faktorizaci, která je založena na Tvrzení 1.23 tj. že x - y je pravděpodobně netriviální dělitel čísla N. Je-li navíc N = p • g, je pak i N = p + q p-q (2.1) Protože p a q jsou různá prvočísla, nemusíme se bát toho, že by N bylo úplným čtvercem nějakého prvočísla. Pokud jsou prvočísla p a q blízko, resp. rozdíl |p - q\ je malý, je číslo ^ jen o málo větší než \fŇ. Pak ale stačí pro x = 1 + [VAŽ], 2 + \VŇ],... počítat x2 - N = u. Je-li u — y2 úplný čtverec, bude p = x - y hledané prvočíslo. Další z možných metod je metoda tzv. řetězových zlomků. Na základě této metody lze navrhnout procesor v ceně asi 1000000 $, který rozloží 100-místné dekadické číslo asi za 1 měsíc. Pro 200-místné dekadické číslo je ale odhad 3.8 miliónů let, což garantuje postačující bezpečnost celého systému. Další z možných metod je metoda tzv. řetězových zlomků. Na základě této metody lze navrhnout procesor v ceně asi 1000000 $, který rozloží 100-místné dekadické číslo asi za 1 měsíc. Pro 200-místné dekadické číslo je ale odhad 3.8 miliónů let, což garantuje postačující bezpečnost celého systému. Připomeňme si, že tvůrci RSA vsadili 100 USD na to, že nikdo nerozluští jejich anglický text zašifrovaný algoritmem RSA s veřejným modulem e = 9007 a známým modulem A/, který je součinem dvou 64- a 65-ciferných prvočísel. Další z možných metod je metoda tzv. řetězových zlomků. Na základě této metody lze navrhnout procesor v ceně asi 1000000 $, který rozloží 100-místné dekadické číslo asi za 1 měsíc. Pro 200-místné dekadické číslo je ale odhad 3.8 miliónů let, což garantuje postačující bezpečnost celého systému. Připomeňme si, že tvůrci RSA vsadili 100 USD na to, že nikdo nerozluští jejich anglický text zašifrovaný algoritmem RSA s veřejným modulem e = 9007 a známým modulem A/, který je součinem dvou 64- a 65-ciferných prvočísel. Rivest v roce 1977 spočítal, že na faktorizaci uvedeného modulu N by bylo nejlepší faktorizační metodou potřeba 40 000 000 000 000 000 let. Proto se nebáli "investovat" 100 USD do sázky. V dubnu 1994 bylo však oznámeno, že se toto 129-ciferné číslo N podařilo rozložit. Zároveň tak byl odhalen otevřený text zašifrované zprávy, která neměla nikdy spatřit světlo světa: "The magie words are squemish ossifrage". V dubnu 1994 bylo však oznámeno, že se toto 129-ciferné číslo N podařilo rozložit. Zároveň tak byl odhalen otevřený text zašifrované zprávy, která neměla nikdy spatřit světlo světa: "The magie words are squemish ossifrage". Poznamenejme k výše uvedenému, že v roce 1873 se zdálo nemožné faktorizovat deseticiferné číslo. V roce 1977 byla však už známá Pollardova rho metoda faktorizace. S její výkonností také Rivest počítal při odhadu uvedeného času na faktorizaci našeho čísla N. V dubnu 1994 bylo však oznámeno, že se toto 129-ciferné číslo N podařilo rozložit. Zároveň tak byl odhalen otevřený text zašifrované zprávy, která neměla nikdy spatřit světlo světa: "The magic words are squemish ossifrage". Poznamenejme k výše uvedenému, že v roce 1873 se zdálo nemožné faktorizovat deseticiferné číslo. V roce 1977 byla však už známá Pollardova rho metoda faktorizace. S její výkonností také Rivest počítal při odhadu uvedeného času na faktorizaci našeho čísla N. Od té doby se však objevily další metody faktorizace: ECM (elliptic curve method), QS (quadratic sieve factoring) a NFS (number field sieve factoring algorithm). Pollardova rho metoda na nalezení 64-ciferného součinitele potřebovala odhadem 4 x 1032 modulárního násobení, tj. asi 1.3 x 1016 let - Rivest uvažoval, že by jedno modulární násobení mohlo trvat jednu nanosekundu. Pollardova rho metoda na nalezení 64-ciferného součinitele potřebovala odhadem 4 x 1032 modulárního násobení, tj. asi 1.3 x 1016 let - Rivest uvažoval, že by jedno modulární násobení mohlo trvat jednu nanosekundu. ECM však už dnes potřebuje už jen 5 x 1015 modulárního násobení, tj. asi 2 měsíce. Pollardova rho metoda na nalezení 64-ciferného součinitele potřebovala odhadem 4 x 1032 modulárního násobení, tj. asi 1.3 x 1016 let - Rivest uvažoval, že by jedno modulární násobení mohlo trvat jednu nanosekundu. ECM však už dnes potřebuje už jen 5 x 1015 modulárního násobení, tj. asi 2 měsíce. Ve skutečnosti se takovéto rychlosti modulárního násobení nedosahuje a reálný odhad by byl cca 15 000 let, což je však obrovský pokrok oproti 1016 letům. Pollardova rho metoda na nalezení 64-ciferného součinitele potřebovala odhadem 4 x 1032 modulárního násobení, tj. asi 1.3 x 1016 let - Rivest uvažoval, že by jedno modulární násobení mohlo trvat jednu nanosekundu. ECM však už dnes potřebuje už jen 5 x 1015 modulárního násobení, tj. asi 2 měsíce. Ve skutečnosti se takovéto rychlosti modulárního násobení nedosahuje a reálný odhad by byl cca 15 000 let, což je však obrovský pokrok oproti 1016 letům. Na rozdíl od ECM a Pollardovy rho metody metoda QS, použitá k nalezení 64-ciferného součinitele u našeho čísla A/, závisí mnohem více na přístupu do paměti než na výkonu procesoru. Na základě analýzy reálně použitých typů počítačů a jimi spotřebovaného času na faktorizaci bylo spočítáno, že k nalezení 64-ciferného součinitele se spotřebovalo celkem 4000 až 6000 tzv. MIPS roků. Na základě analýzy reálně použitých typů počítačů a jimi spotřebovaného času na faktorizaci bylo spočítáno, že k nalezení 64-ciferného součinitele se spotřebovalo celkem 4000 až 6000 tzv. MIPS roků. Přitom jeden MIPS rok je množství operací, které zajeden rok vykoná počítač s výkonem jeden milion operací za vteřinu. Je to tedy 365,25 x 24 x 3600 x 1000000 =cca. 3.16 • 1013 operací. Na základě analýzy reálně použitých typů počítačů a jimi spotřebovaného času na faktorizaci bylo spočítáno, že k nalezení 64-ciferného součinitele se spotřebovalo celkem 4000 až 6000 tzv. MIPS roků. Přitom jeden MIPS rok je množství operací, které zajeden rok vykoná počítač s výkonem jeden milion operací za vteřinu. Je to tedy 365,25 x 24 x 3600 x 1000000 =cca. 3.16 • 1013 operací. Počítáme-li průměrný výkon jednoho počítače v experimentu 10 MIPS s tím, že na experimentu pracoval jen polovinu dne tj. s reálným výkonem pouze 5 MIPS, bylo k faktorizaci použito cca. 1000 let práce. Na základě analýzy reálně použitých typů počítačů a jimi spotřebovaného času na faktorizaci bylo spočítáno, že k nalezení 64-ciferného součinitele se spotřebovalo celkem 4000 až 6000 tzv. MIPS roků. Přitom jeden MIPS rok je množství operací, které zajeden rok vykoná počítač s výkonem jeden milion operací za vteřinu. Je to tedy 365,25 x 24 x 3600 x 1000000 =cca. 3.16 • 1013 operací. Počítáme-li průměrný výkon jednoho počítače v experimentu 10 MIPS s tím, že na experimentu pracoval jen polovinu dne tj. s reálným výkonem pouze 5 MIPS, bylo k faktorizaci použito cca. 1000 let práce. Zároveň je z výše uvedeného vidět úžasný nárůst výkonnosti faktorizačních metod v posledních letech. Faktorizaci 154-místného čísla (512 bitů) pak bude trvat cca 500000 MIPS let. Faktorizaci 154-místného čísla (512 bitů) pak bude trvat cca 500000 MIPS let. Tento výkon by mohli zajistit všichni účastníci sítě INTERNET. Dostáváme pak výpočetní kapacitu 20 miliónů MIPS - tj. faktorizace by proběhla během devíti dní. Faktorizace Napadání RSA Algebraické vlastnosti Důsledky Pollard Dalsi mozne útoky Fermat Speciální přístupy Důsledky nových faktorizačních algoritmů I Nespolehlivější cesta, jak narušit veřejnou síť využívající RSA-kryptosystém, je nalezení dešifrovacího exponentu, označme si ho třeba t. Faktorizace Napadání RS/ Algebraické vlastnosti Faktorizace Důsledky Pollard Další možné útoky Fermat Speciální přístupy Důsledky r íovýcf fa ki tor iza .Cl n \c\ ~) a Igoritmů 1 Nespolehlivější cesta, jak narušit veřejnou síť využívající RSA-kryptosystém, je nalezení dešifrovacího exponentu, označme si ho třeba t. Jednou z takovýchto možností je poznání čísel p - 1 a q - 1, tj. faktorizace šifrového modulu N = pq. Slabým místem Pollardovy p - 1 a p + 1 metody je nalezení vhodného čísla b. Faktorizace Napadání RS/ Algebraické vlastnosti Faktorizace Důsledky Pollard Další možné útoky Fermat Speciální přístupy Důsledky r íovýcf fa ki tor iza .Cl n \c\ ~) a Igoritmů 1 Nespolehlivější cesta, jak narušit veřejnou síť využívající RSA-kryptosystém, je nalezení dešifrovacího exponentu, označme si ho třeba t. Jednou z takovýchto možností je poznání čísel p - 1 a q - 1, tj. faktorizace šifrového modulu N = pq. Slabým místem Pollardovy p - 1 a p + 1 metody je nalezení vhodného čísla b. Abychom úlohu faktorizace čísla N pro nekompetentní osobu zkomplikovali, musíme zvolit prvočísla p a q tak, aby p - 1 {q - 1) mělo velký prvočíselného dělitel r a p + 1 {q + 1) velký prvočíselný dělitel d. Faktorizace Napadání RS/ Algebraické vlastnosti Faktorizace Důsledky Pollard Další možné útoky Fermat Speciální přístupy Důsledky r íovýcf fa ki tor iza .01 n \c\ ~) a Igoritmů 1 Nespolehlivější cesta, jak narušit veřejnou síť využívající RSA-kryptosystém, je nalezení dešifrovacího exponentu, označme si ho třeba t. Jednou z takovýchto možností je poznání čísel p - 1 a q - 1, tj. faktorizace šifrového modulu N = pq. Slabým místem Pollardovy p - 1 a p + 1 metody je nalezení vhodného čísla b. Abychom úlohu faktorizace čísla N pro nekompetentní osobu zkomplikovali, musíme zvolit prvočísla p a q tak, aby p - 1 {q - 1) mělo velký prvočíselného dělitel r a p + 1 {q + 1) velký prvočíselný dělitel d. Zároveň je vhodné požadovat, aby číslo r - 1 mělo rovněž velký prvočíselný dělitel e. Faktorizace Napadání RS/ Algebraické vlastnosti Faktorizace Důsledky Pollard Další možné útoky Fermat Speciální přístupy Důsledky r íovýcf fa ki tor iza .01 n \c\ ~) a Jgoritmů II Proto prvočísla splňující kongruenční rovnice p = 1 mod r p = d - 1 mod d (2.2) r = 1 mod e. (kde r, d a e jsou velká náhodná prvočísla) se nazývají silná prvočísla. Faktorizace Napadání RS/ Algebraické vlastnosti Faktorizace Důsledky Pollard Další možné útoky Fermat Speciální přístupy Důsledky r íovýcf fa ki tor iza .Cl n \c\ ~) a Igoritmů II Proto prvočísla splňující kongruenční rovnice p = 1 mod r p = d - 1 mod d (2.2) r = 1 mod e. (kde r, d a e jsou velká náhodná prvočísla) se nazývají silná prvočísla. Abychom se zabezpečili i proti metodám založeným na Fermatově faktorizaci, musíme zvolit silná náhodná prvočísla p a q tak, aby rozdíl |p - q\ byl několik řádů. Faktorizace Napadání RS/ Algebraické vlastnosti Faktorizace Důsledky Pollard Další možné útoky Fermat Speciální přístupy Důsledky r íovýcf fa ki tor iza .Cl n \c\ ~) a Igoritmů II Proto prvočísla splňující kongruencní rovnice p = 1 mod r p = d - 1 mod d r = 1 mod e. (2.2) (kde r, d a e jsou velká náhodná prvočísla) se nazývají silná prvočísla. Abychom se zabezpečili i proti metodám založeným na Fermatově faktorizaci, musíme zvolit silná náhodná prvočísla p a q tak, aby rozdíl |p - q\ byl několik řádů. Pokud budeme mít efektivní metodu na nalezení silných náhodných prvočísel, pak splnění poslední podmínky nám nezpůsobí žádné komplikace. Takováto metoda byla poprvé navržená Gordonem v roce 1985. Faktorizace Napadání RSA Algebraické vlastnosti Důsledky Pollard Dalsi mozne útoky Fermat Speciální přístupy Další možné útoky na RSA-šifrovací systém I Ukážeme, že dva účastníci RSA-šifrovacího systému nemohou mít stejný šifrovací modul N. Uvažujme účastníky A a 6, NA = NB = N. Pak musí platit {sA, 0. Pak v • sa = 1 - u • n = 1 mod (p(N) (2.7) tA • sA = 1 mod(^(A/). (2.8) Faktorizace Napadání RSA Algebraické vlastnosti Důsledky Pollard Dalsi mozne útoky Fermat Speciální přístupy Další možné útoky na RSA-šifrovací systém III Bez újmy na obecnosti lze předpokládat, že v > 0. Pak v • sa = 1 - u • n = 1 mod (p(N) (2.7) tA • sA = 1 mod v?(/V) (2.8) Zejména tedy (v - tA) • sA = 0 mod v?(/V) (2.9) v = ía vr\od(p(N). (2.10) Faktorizace Napadání RSA Algebraické vlastnosti Důsledky Pollard Dalsi mozne útoky Fermat Speciální přístupy Další možné útoky na RSA-šifrovací systém IV Takovéto v je dešifrovacím exponentem zpráv, které jsou zasílány účastníkovi A. Totiž, je-li y = xsa mod(A/), (2.11) zpráva určená pro A, pak platí yv = xSa'v = xSa'v+Sa'''^ = x mod (A/), (2.12) pro vhodné / e Z. Faktorizace Napadání RSA Algebraické vlastnosti Důsledky Pollard Dalsi mozne útoky Fermat Speciální přístupy Další možné útoky na RSA-šifrovací systém IV Takovéto v je dešifrovacím exponentem zpráv, které jsou zasílány účastníkovi A. Totiž, je-li y = xsa mod(A/), (2.11) zpráva určená pro A, pak platí yv = xSa'v = xSa'v+Sa'''^ = x mod (A/), (2.12) pro vhodné / e Z. Pokud chce B odeslat zprávu jinému účastníkovi C, stačí podepsat zprávu místo dešifrovacím exponentem účastníka A exponentem v. Faktorizace Napadání RSA Algebraické vlastnosti Důsledky Pollard Dalsi mozne útoky Fermat Speciální přístupy Další možné útoky na RSA-šifrovací systém V Jinou z možných příčin narušení RSA-šifrovacího systému by mohla být skutečnost, že tatáž zpráva je odeslána více účastníkům šifrovacího systému tak, že je zašifrovaná různými šiframi tohoto systému. RSA-algoritmus nemůže používat stejné šifrovací exponenty. Faktorizace Napadání RSA Algebraické vlastnosti Důsledky Pollard Dalsi mozne útoky Fermat Speciální přístupy Další možné útoky na RSA-šifrovací systém V Jinou z možných příčin narušení RSA-šifrovacího systému by mohla být skutečnost, že tatáž zpráva je odeslána více účastníkům šifrovacího systému tak, že je zašifrovaná různými šiframi tohoto systému. RSA-algoritmus nemůže používat stejné šifrovací exponenty. Z důvodu jednoduchosti uvažujme tři účastníky šifrovacího systému, kteří mají šifrovací klíče (s, A/,), / = 1,2,3. Můžeme bez újmy na obecnosti předpokládat, že moduly jsou navzájem nesoudělné. Pokud by tomu tak nebylo, našli bychom faktorizaci a tím byli hotovi. Faktorizace Napadání RSA Algebraické vlastnosti Důsledky Pollard Dalsi mozne útoky Fermat Speciální přístupy Další možné útoky na RSA-šifrovací systém V Jinou z možných příčin narušení RSA-šifrovacího systému by mohla být skutečnost, že tatáž zpráva je odeslána více účastníkům šifrovacího systému tak, že je zašifrovaná různými šiframi tohoto systému. RSA-algoritmus nemůže používat stejné šifrovací exponenty. Z důvodu jednoduchosti uvažujme tři účastníky šifrovacího systému, kteří mají šifrovací klíče (s, A/,), / = 1,2,3. Můžeme bez újmy na obecnosti předpokládat, že moduly jsou navzájem nesoudělné. Pokud by tomu tak nebylo, našli bychom faktorizaci a tím byli hotovi. Zašleme-li těmto třem účastníkům stejnou zprávu x, x < min Nj, pak Mr. X, který zachytí její zašifrované varianty y,, i = 1,2,3, může zprávu x lehce dešifrovat. Faktorizace Napadání RSA Algebraické vlastnosti Důsledky Pollard Dalsi mozne útoky Fermat Speciální přístupy Další možné útoky na RSA-šifrovací systém VI Postup Mr. X bude následovný. Z kongruenčních rovníc yA = xs modA/1 (2.13) y2 = xs mod N2 (2.14) y3 = xs mod A/3 (2.15) dostaneme pro N = A/-| A/2A/3 y, A/2A/3 = xsN2N3 mod A/ y2A/-| A/3 = xsA/-| A/3 mod N y3A/-| A/2 = xsN^ N2 mod A/. Po jejich sečtení obdržíme (2.16) (2.17) (2.18) y-i A/2A/3 + y2A/1 A/3 + y3A/1 A/2 = xs • (A/2A/3 + A/1A/3 + A/1A/2) mod A/. °9 1 Ch Faktorizace Napadání RSA Algebraické vlastnosti Důsledky Pollard Dalsi mozne útoky Fermat Speciální přístupy Další možné útoky na RSA-šifrovací systém VII Je-li s = 3, pak xs < N a Mr. X může z poslední kongruence přímo vypočítat zprávu x - vynásobením prvkem inverzním k prvku (A/2A/3 + N^N3 + A/-| A/2) a standardním odmocněním. Výsledek lze zobecnit na d účastníků šifrovacího systému. Faktorizace Napadání RSA Algebraické vlastnosti Pollard Dalsi mozne útoky Fermat Speciální přístupy peciální přístupy k dešifrování RSA I Můžeme-li počítat s jistou neopatrností účastníka sítě, zašle Mr. X účastníkovi A zprávu xs • as, kde xs je zašifrovaná zpráva, kterou Mr. X zachytil a pozměnil ji pronásobením číslem as. Faktorizace Napadání RSA Algebraické vlastnosti Pollard Dalsi mozne útoky Fermat Speciální přístupy peciální přístupy k dešifrování RSA I Můžeme-li počítat s jistou neopatrností účastníka sítě, zašle Mr. X účastníkovi A zprávu xs • as, kde xs je zašifrovaná zpráva, kterou Mr. X zachytil a pozměnil ji pronásobením číslem as. Veřejný šifrovací klíč je dvojice (s, N). Tedy účastník A obdrží zprávu y1 = as • xs mod N (2.20) a po dešifrování x' = (y'y = xa mod A/. Faktorizace Napadání RSA Algebraické vlastnosti Pollard Dalsi mozne útoky Fermat Speciální přístupy peciální přístupy k dešifrování RSA I Můžeme-li počítat s jistou neopatrností účastníka sítě, zašle Mr. X účastníkovi A zprávu xs • as, kde xs je zašifrovaná zpráva, kterou Mr. X zachytil a pozměnil ji pronásobením číslem as. Veřejný šifrovací klíč je dvojice (s, A/). Tedy účastník A obdrží zprávu y1 = as • xs mod N (2.20) a po dešifrování x' = (y;)ř = xa mod N. Pokud bude A neopatrný a umožní přístup k číslu x', můžeme jednoduše spočítat pak x = a 1 • x; mod A/. (2.21) Faktorizace Napadání RSA Algebraické vlastnosti Pollard Dalsi mozne útoky Fermat Speciální přístupy Speciální přístupy k dešifrování RSA II Další možný přístup souvisí s protokolem při vytváření spojení mezi účastníky, kdy se A i B navzájem identifikují. Faktorizace Napadání RSA Algebraické vlastnosti Pollard Dalsi mozne útoky Fermat Speciální přístupy peciální přístupy k dešifrování RSA II Další možný přístup souvisí s protokolem při vytváření spojení mezi účastníky, kdy se A i B navzájem identifikují. Pokud chce účastník B navázat spojení s účastníkem A, zvolí libovolnou zprávu x a vyšle pomocí dešifrovacího exponentu tB šifru y = xxb mod NB. Faktorizace Napadání RSA Algebraické vlastnosti Pollard Dalsi mozne útoky Fermat Speciální přístupy peciální přístupy k dešifrování RSA II Další možný přístup souvisí s protokolem při vytváření spojení mezi účastníky, kdy se A i B navzájem identifikují. Pokud chce účastník B navázat spojení s účastníkem A, zvolí libovolnou zprávu x a vyšle pomocí dešifrovacího exponentu tB šifru y = xxb mod NB. Účastník A zná šifrovací exponent účastníka B a proto si může zkontrolovat ySB = xtB'SB = x mod NB. Faktorizace Napadání RSA Algebraické vlastnosti Pollard Dalsi mozne útoky Fermat Speciální přístupy peciální přístupy k dešifrování RSA II Další možný přístup souvisí s protokolem při vytváření spojení mezi účastníky, kdy se A i B navzájem identifikují. Pokud chce účastník B navázat spojení s účastníkem A, zvolí libovolnou zprávu x a vyšle pomocí dešifrovacího exponentu tB šifru y = xxb mod NB. Účastník A zná šifrovací exponent účastníka B a proto si může zkontrolovat ySB = xtB'SB = x mod NB. Nyní použije účastník A svůj dešifrovací exponent t& a výše uvedený postup zopakuje. Zřejmě je x < min {Na, Nb}. Faktorizace Napadání RSA Algebraické vlastnosti Pollard Dalsi mozne útoky Fermat Speciální přístupy peciální přístupy k dešifrování RSA II Další možný přístup souvisí s protokolem při vytváření spojení mezi účastníky, kdy se A i B navzájem identifikují. Pokud chce účastník B navázat spojení s účastníkem A, zvolí libovolnou zprávu x a vyšle pomocí dešifrovacího exponentu tB šifru y = xxb mod NB. Účastník A zná šifrovací exponent účastníka B a proto si může zkontrolovat ySB = xtB'SB = x mod NB. Nyní použije účastník A svůj dešifrovací exponent t& a výše uvedený postup zopakuje. Zřejmě je x < min {Na, Nb}. Jak bude probíhat vlastní útok? Faktorizace Napadání RSA Algebraické vlastnosti Pollard Dalsi mozne útoky Fermat Speciální přístupy Speciální přístupy k dešifrování RSA III Pokud účastník B získá dva takovéto podpisy od účastníka A = x\A m od NAl (2.22) = x!f mod NAl (2.23) je pak schopný vytvořit třetí hodnověrný podpis účastníka A bez znalosti jeho dešifrovacího exponentu t& y = {x^x2yA mod/V^ (2.24) a ten zneužít při podpisu nějaké zprávy (B zná jak x1 tak x2). Proto je vhodné doplnit při podpisování zprávu x nějakou aktuální redundantní a nepředvídanou informací.^ Faktorizace Napadání RSA Algebraické vlastnosti Pollard Dalsi mozne útoky Fermat Speciální přístupy peciální přístupy k dešifrování RSA IV Třetí z možných přístupů je následující. Faktorizace Napadání RSA Algebraické vlastnosti Pollard Dalsi mozne útoky Fermat Speciální přístupy peciální přístupy k dešifrování RSA IV Třetí z možných přístupů je následující. Nechť šifrovací modul N = p • q má n-bitovou reprezentaci a prvočísla p a q mají ^-bitovou reprezentaci. Faktorizace Napadání RSA Algebraické vlastnosti Pollard Dalsi mozne útoky Fermat Speciální přístupy peciální přístupy k dešifrování RSA IV Třetí z možných přístupů je následující. Nechť šifrovací modul N = p • q má n-bitovou reprezentaci a prvočísla p a q mají ^-bitovou reprezentaci. Předpokládejme, že Mr. X má možnost získat nějakým způsobem ^-bitovou informaci o modulu N. Potom ho samozřejmě může faktorizovat - přímo se zeptá na jedno z prvočísel p a q. Faktorizace Napadání RSA Algebraické vlastnosti Pollard Dalsi mozne útoky Fermat Speciální přístupy peciální přístupy k dešifrování RSA IV Třetí z možných přístupů je následující. Nechť šifrovací modul N = p • q má n-bitovou reprezentaci a prvočísla p a q mají ^-bitovou reprezentaci. Předpokládejme, že Mr. X má možnost získat nějakým způsobem ^-bitovou informaci o modulu N. Potom ho samozřejmě může faktorizovat - přímo se zeptá na jedno z prvočísel p a q. Dá se ukázat, že šifrovací modul N je možno faktorizovat polynomiálním algoritmem, pokud má Mr. X možnost získat jen § bitů. Faktorizace Napadání RSA Algebraické vlastnosti Pollard Dalsi mozne útoky Fermat Speciální přístupy Speciální přístupy k dešifrování RSA IV Třetí z možných přístupů je následující. Nechť šifrovací modul N = p • q má n-bitovou reprezentaci a prvočísla p a q mají ^-bitovou reprezentaci. Předpokládejme, že Mr. X má možnost získat nějakým způsobem ^-bitovou informaci o modulu N. Potom ho samozřejmě může faktorizovat - přímo se zeptá na jedno z prvočísel p a q. Dá se ukázat, že šifrovací modul N je možno faktorizovat polynomiálním algoritmem, pokud má Mr. X možnost získat jen § bitů. Na poslední z přístupů k rozšifrování RSA-šifry poukázali jako první G.J. Simmons a M.J. Norris. Tento přístup využívá algebraické vlastnosti RSA-kryptosystému. v ■ r i i r v Q Algebraické vlastnosti a iterovaný útok • Algebraický popis RSA • Iterovaný útok Uvažujme množinu zpráv rozšířenou o nulový prvek, tj M= {0,1,2,..., N- 1}. □ S1 Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný utok Uvažujme množinu zpráv rozšířenou o nulový prvek, tj. M= {0,1,2,..., N- 1}. Pro každé s, (s, (N)) = 1 je zobrazení 7~(s, x) = xs mod N (3.1) permutací množiny M, která nechává nulový prvek na místě. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný utok Uvažujme množinu zpráv rozšířenou o nulový prvek, tj M = {0,1,2,..., N- 1}. Pro každé s, (s, 0(A/)) = 1 je zobrazení 7(s, x) = xs mod N (3-1) permutací množiny M, která nechává nulový prvek na místě. Permutace T(s, -) tvoří konečnou komutativní grupu s neutrálním prvkem 7(1, -), kterým je identické zobrazení. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný utok Uvažujme množinu zpráv rozšířenou o nulový prvek, tj M = {0,1,2,..., N- 1}. Pro každé s, (s, 0(A/)) = 1 je zobrazení 7(s, x) = xs mod N (3-1) permutací množiny M, která nechává nulový prvek na místě. Permutace T(s, -) tvoří konečnou komutativní grupu s neutrálním prvkem 7(1, -), kterým je identické zobrazení. Platí 7(s, -) o r(ř, -) = T(s • ř, -) = 7(f, -) o 7(s, -) a 7(s, = 7(ř, -), kde ř • s = 1 mod 0(A/). * * Lze tedy množinu M s násobením považovat za konečnou komutativní pologrupu s nulovým prvkem, Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný utok Lze tedy množinu M s násobením považovat za konečnou komutativní pologrupu s nulovým prvkem, T(s, -) : M -> M je homomorfismus pologrup zachovávající nulový prvek. Ukažme si možnost narušení systému iterovaným šifrováním. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Ukažme si možnost narušení systému iterovaným šifrováním. Zvolme N = 3 • 59 = 177, s = 17. Pak M = {0,1,2,..., 176}. Uvažujme zprávu x = 5. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Ukažme si možnost narušení systému iterovaným šifrováním. Příklad 3.1 Zvolme N = 3 • 59 = 177, s = 17. Pak M = {0,1,2,... ,176}. Uvažujme zprávu x = 5. Postupně iterováním dostaneme 7(17,5) = 517mod177 = 95, Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Ukažme si možnost narušení systému iterovaným šifrováním. Příklad 3.1 Zvolme N = 3 • 59 = 177, s = 17. Pak M = {0,1,2,... ,176}. Uvažujme zprávu x = 5. Postupně iterováním dostaneme 7(17,5) = 517moaM77 = 95, 7(17, 7(17,5)) = 7(17,95) = 9517 modJ\ 77 = 71, I Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Ukažme si možnost narušení systému iterovaným šifrováním. Příklad 3.1 Zvolme N = 3 • 59 = 177, s = 17. Pak M = {0,1,2,... ,176}. Uvažujme zprávu x = 5. Postupně iterováním dostaneme 7(17,5) = 517moc/177 = 95, 7(17,7(17,5)) = 7(17,95) = 9517 moc/177 = 71, 7(17,7(17,7(17,5))) = 7(17,71) = 7117 moc/177 = 41, I Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Ukažme si možnost narušení systému iterovaným šifrováním. Příklad 3.1 Zvolme N = 3 • 59 = 177, s = 17. Pak M = {0,1,2,... ,176}. Uvažujme zprávu x = 5. Postupně iterováním dostaneme I 7(17,5) 7(17, 7(17,5)) 7(17, 7(17, 7(17,5))) 7(17,-)4(5) 517 modMl = 95, 7(17,95) = 9517 moc/177 7(17,71) = 7117 moc/177 4117 moc/177 = 5, 71 41 Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Ukažme si možnost narušení systému iterovaným šifrováním. Zvolme N = 3 • 59 = 177, s = 17. Pak M = {0,1,2,..., 176}. Uvažujme zprávu x = 5. Postupně iterováním dostaneme 7(17,5) = 517moaM77 = 95, 7(17,7(17,5)) = 7(17,95) = 9517mod177 = 71, 7(17,7(17,7(17,5))) = 7(17,71) = 7117 mod\77 = 41, 7(17,-)4(5) = 4117 modl 77 = 5, 7(17,-)5(5) = 517mod177 = 95, Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Ukažme si možnost narušení systému iterovaným šifrováním. Příklad 3.1 Zvolme N = 3 • 59 = 177, s = 17. Pak M = {0,1,2,... ,176}. Uvažujme zprávu x = 5. Postupně iterováním dostaneme I 7(17,5) 7(17, 7(17,5)) 7(17, 7(17, 7(17,5))) 7(17,-)4(5) 7(17,-)5(5) 517 moc/177 = 95, 7(17,95) = 9517 moc/177 7(17,71) = 7117 moc/177 4117 moc/177 = 5, 517moc/177 = 95, 71 41 Protože jak N tak s známe, takovéto iterované šifrování může provést každv. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Z konečnosti množiny M víme, že existuje číslo h tak, že 7(s, = 7(s, -) (3.2) a tedy pro každé zprávu x platí 7(s, x)17 = x. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Z konečnosti množiny M víme, že existuje číslo h tak, že r(s,-y+1 = t(s,-) (3.2) a tedy pro každé zprávu x platí T(s, x)17 = x. Navíc lze pro konkrétní zprávu najít takové minimální h - tj. délku cyklu, který obsahuje zprávu x. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Z konečnosti množiny M víme, že existuje číslo h tak, že r(s,-)"+1 = T(s,-) (3.2) a tedy pro každé zprávu x platí T(s, x)17 = x. Navíc lze pro konkrétní zprávu najít takové minimální h - tj. délku cyklu, který obsahuje zprávu x. Tento postup je však prakticky realizovatelný jen v případě, když h bude relativně malé číslo, např. menší než milión. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Z konečnosti množiny M víme, že existuje číslo h tak, že 7(s, = 7(s, -) (3.2) a tedy pro každé zprávu x platí 7(s, x)17 = x. Navíc lze pro konkrétní zprávu najít takové minimální h - tj. délku cyklu, který obsahuje zprávu x. Tento postup je však prakticky realizovatelný jen v případě, když h bude relativně malé číslo, např. menší než milión. Je přitom dokázáno, že při vhodném výběru prvočísel p a q je pravděpodobnost nalezení takovéhoto malého h menší než 10"90. Vzhledem k tomu, že počet elementárních částic v nám známém vesmíru je řádově 1080, lze každou pravděpodobnost menší než 10~80 považovat za nulovou. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Vzhledem k tomu, že počet elementárních částic v nám známém vesmíru je řádově 1080, lze každou pravděpodobnost menší než 10~80 považovat za nulovou. Popišme si nyní pologrupu M. Ta je sjednocením čtyř disjunktních grup a obsahuje přesně čtyři idempotenty -0,1, e-i, e2. Poslední dva idempotenty dostaneme jako řešení rovnic • p = 1 mod q, resp. a2 • q = 1 mod p, (3.3) kde a\ • p = e-i a a2 • q = e2 leží v M, 1 < a^ < q a 1 < a2 < p. Příslušné grupy jsou tedy G(0) = {0}, G(1) = {x : (x,p- G(eO = {x : x = p • a mod g. a = 1 2 1,4-,... ,q- G(e2) = {x : x = q • b mod p. £> = 1,2,.. -,p- □ s Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok G(0) = {0}, G(1) = {x:(x,p.g) = 1}, G(e1) = {x : x = p • a mod g, a = 1,2,..., q - 1}, G(e2) = {x : x = q • Ď mod p, Ď = 1,2,..., p - 1}. To znamená, že počet prvků v jednotlivých grupách je 1,(P-1)(q-1),q-1 ap-1. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok G(0) = {0}, G(1) = {x:(x,p.g) = 1}, G(e1) = {x : x = p • a mod g, a = 1,2,..., q - 1}, G(e2) = {x : x = q • ď mod p, ď = 1,2,..., p - 1}. To znamená, že počet prvků v jednotlivých grupách je 1,(p-1)(Q-1),Q-1ap-1. Nejprve určeme počet těch zpráv x e M, které zůstanou při permutaci T(s, -) = Ts na místě. Ptáme se tedy na počet řešení rovnice 7(s, x) = xs = x mod N. (3.4) Lze dokázat, že všechna takováto řešení tvoří podpologrupu Z| pologrupy M, která obsahuje přesně \Z,\ = [1 +(s-1,p-1)][1 +(s-1,q-1)] (3.5) prvků. Lze dokázat, že všechna takováto řešení tvoří podpologrupu Z| pologrupy M, která obsahuje přesně \Z,\ = [1 +(s-1,p-1)][1 +(s-1,q-1)] (3.5) prvků. v případě, že zvolíme parametry s, p, q tak, že s = 2r + 1, p = 2p1 + 1, q = 2q1 + 1, (3.6) kde Pí, Qi ar jsou navzájem různá prvočísla, je |Z11 = 9 a to je zřejmě nejmenší možný počet zpráv, které se nezašifrují. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Příklad 3.2 Nechť p = 5, q = 7. Potom a-i * 5 = 1 mod 7, tj. a-\ = 3, e-i =15. Dále a2 * 7 = 1 mod 5, tj. a2 = 3, e2 = 21. Odtud G(0) = {0}, G(1) = {x | 1 < x < 34,(x,35) = 1}, G(15) = {5,10,15,20,25,30} G(21) = {7,14,21,28}. Podívejme se nyní, jak to vypadá při iterovaném šifrování. Chceme vědět, kolik různých zašifrovaných zpráv můžeme tímto způsobem přečíst, zopakujeme-li šifrování h+ 1 -krát. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Podívejme se nyní, jak to vypadá při iterovaném šifrování. Chceme vědět, kolik různých zašifrovaných zpráv můžeme tímto způsobem přečíst, zopakujeme-li šifrování h+ 1 -krát. Rovnost (3.2) přepíšeme na tvar xs/7+1 = xs mod A/, resp. xsh = x mod N. (3.7) Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Podívejme se nyní, jak to vypadá při iterovaném šifrování. Chceme vědět, kolik různých zašifrovaných zpráv můžeme tímto způsobem přečíst, zopakujeme-li šifrování h+ 1 -krát. Rovnost (3.2) přepíšeme na tvar xs/7+1 = xs mod A/, resp. xsh = x mod N. (3.7) Všechna takováto řešení opět tvoří podpologrupu Zh pologrupy M, která obsahuje přesně Zh\ = [1 + (s/7-1,p-1)][1 +(s"-1,q-1)] (3.8) h prvků. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Lemma 3.3 a) ZinZh = Zd,kded = (l,h), b) Dělí-li číslo 1 číslo h, je Z\ QZh. Důkaz, a) Nechť x e G(/% kde f ^ 0 je jeden z idempotentů pologrupy M. Rovnice xs' 1 = f mod N a xsh 1 = f mod A/, (3.9) které získáme vydělením vztahu (3.7) v příslušné grupě G(f), mají společné řešení právě tehdy, když (s1 - 1, sh - 1) = sd - 1, kde d = (/, /?). Tvrzení b) je speciálním případem pro / = (/, h). Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Lemma 3.4 Označme Z% = {x : x = xs\xs' ^ x pro všechna I < h}, Dh = {d : d/h,d ^ h}. Pak a) Zl = Zh- [j{Zd : d/h, d ŕ h}, Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Lemma 3.4 Označme Z*h = {x-.x = xs\ xs' ^ x pro všechna I < ti), Dh = {d : d/h,d^ h}. Pak a) Z*h =Zh- [j{Zd : d/h, d ŕ h}, b) Z*h\ = \Zh\ - \Ei\Zn\: d e Dh} -Eíl^i nZd2\ : d^,d2 e Dh,d1^d2} + ... + (-1)1^1 |f|{2^ :d e Dh} Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Lemma 3.4 Označme Z% = {x : x = xs\xs' ^ x pro všechna 1 < h}, Dh = {d : d/h,d ^ h}. Pak a) Zl = Zh- [j{Zd : d/h, d ŕ h}, b) 2ft = \Zh\-\Ľi\Zd -deDh} - E{|2dl r\Zdz\ : d^d2 e Dh, d^ ^ d2} + ... + (-l)m\f){Zd;deDh}}1 c) Pokud je h = pa, p prvočíslo, je Z% = Zh- Zh. p Faktorizace ľ slapadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Iterovaný i ú tol kr ia RSAX- D o U kaz Lemmatu 3.4 a) Nechť x e Z%, pak x g Z\ pro libovolné / < h, (/, h) ^ 1. Tedy Zň*CZ/7-U{Z/:/ 2, jestliže n = 2,4,pa, p- liché prvočíslo, jinak. Přitom A je tzv. Carmichaelova funkce, která číslu n = p^1 • p^2 • -p?r přiřadí číslo ' 1 jestliže n = 1, X(n) = < pa-2 , nsn{\(p?),...,A(p?')} jestliže n = 2a, a > 2, jestliže n = 2,4,pa, p- liché prvočíslo, jinak. Zároveň lze dokázat, že tento univerzální dešifrovací exponent h0 nelze nahradit menším číslem. Je zřejmé, že permutace Ts tvoří grupu. Faktorizace Napadání RSA Algebraické vlastnosti raický popis Iterovaný útok Je zřejmé, že permutace Ts tvoří grupu. Lze dokázat, že počet prvků této grupy je fy = cp(X(N)) Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Je zřejmé, že permutace Ts tvoří grupu. Lze dokázat, že počet prvků této grupy je fy = ^(A(A/)). Každá z permutací Ts generuje v této grupě nějakou konečnou cyklickou podgrupu {Ts, 7f,...}. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Je zřejmé, že permutace Ts tvoří grupu. Lze dokázat, že počet prvků této grupy je fy = , , > t Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Aby toto číslo bylo co největší, můžeme zvolit Pi=a2p2 + 1 a Qi=ď2Q2 + 1, kde a2, b2 jsou libovolná náhodně zvolená malá čísla a p2 a g2 jsou přibližně 90-ti ciferná prvočísla. Pak bude h0 = p2 • g2 • a, pro vhodné celé číslo a. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Aby toto číslo bylo co největší, můžeme zvolit Pi=a2p2 + 1 a 9i=62q2 + 1, kde a2, b2 jsou libovolná náhodně zvolená malá čísla a p2 a g2 jsou přibližně 90-ti ciferná prvočísla. Pak bude h0 = p2 • g2 • a, pro vhodné celé číslo a. Dále dokážeme, že toto h0 je pro většinu transformací Ts nejmenším exponentem v příslušné grupě. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Aby toto číslo bylo co největší, můžeme zvolit Pi=a2p2 + 1 a 9i=62q2 + 1, kde a2, b2 jsou libovolná náhodně zvolená malá čísla a p2 a g2 jsou přibližně 90-ti ciferná prvočísla. Pak bude h0 = p2 • g2 • a, pro vhodné celé číslo a. Dále dokážeme, že toto h0 je pro většinu transformací Ts nejmenším exponentem v příslušné grupě. Zabývejme se nyní exponentem zpráv x e M. Zpráva x nebude z grupy G(1) c M právě tehdy, když bude násobkem prvočísla p nebo q. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Pravděpodobnost takovéto situace, že (x, N) = (x, pq) ^ 1 pro náhodně zvolené x bude <3(e0| + |<3(e2)l + 1 N P+q~' < 1 + 1 < 10-9° N ~ p q~ (3.13) což je možno považovat za nulovou pravděpodobnost. Tento výsledek podtrhuje spolehlivost RSA-systému při vhodné volbě klíče. Tvrdí, že pro odesilatele zprávy nemá praktický význam, aby počítal číslo (x, N), které může být rovné 1, p nebo q. Předpokládejme tedy, že (x, N) = 1 a prvočísla jsou vybraná výše uvedeným způsobem p = ai • pí + 1, q = ďi • gi + 1 (3-14) Pí = a2 • p2 + 1, kde a,-, by jsou libovolná náhodně zvolená malá čísla, p, g, pí, Qi, P2, Q2 jsou náhodně zvolená prvočísla, P2,Q2> 1090. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Předpokládejme tedy, že (x, N) = 1 a prvočísla jsou vybraná výše uvedeným způsobem p = a^■p^+^, q = ďi • gi + 1 (3-14) Pi = a2 ■ P2 + 1, kde a,-, by jsou libovolná náhodně zvolená malá čísla, p, g, pí, Qi, P2, Q2 jsou náhodně zvolená prvočísla, P2,Q2> 1090. Ukážeme, že pro většinu zpráv x je jejich exponent násobkem čísla p-i q-i. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Připomeňme si následující známou větu z obecné algebry. Věta 3.7 (L. Sylow) Nechť G je abelovská grupa, \ G\ = n. Nechť dále pa je největší mocnina prvočísla p, která dělí n. Pak grupa G obsahuje jedinou podgrupu, která má přesně pa prvků. Tato podgrupa se nazývá Sylowovská. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Připomeňme si následující známou větu z obecné algebry. Věta 3.7 (L. Sylow) Nechť G je abelovská grupa, \ G\ = n. Nechť dále pa je největší mocnina prvočísla p, která dělí n. Pak grupa G obsahuje jedinou podgrupu, která má přesně pa prvků. Tato podgrupa se nazývá Sylowovská. Důsledek 3.8 PT je Nechť G je abelovská grupa a \ G\ = p^1 • p%2 — kanonický rozklad čísla n = \G\. Pak G je izomorfní s kartézským součinem všech svých Sylowovských podgrup GPi Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Připomeňme si následující známou větu z obecné algebry. Věta 3.7 (L. Sylow) Nechť G je abelovská grupa, \ G\ = n. Nechť dále pa je největší mocnina prvočísla p, která dělí n. Pak grupa G obsahuje jedinou podgrupu, která má přesně pa prvků. Tato podgrupa se nazývá Sylowovská. Důsledek 3.8 PT je Nechť G je abelovská grupa a \ G\ = p^1 • p%2 — kanonický rozklad čísla n = \G\. Pak G je izomorfní s kartézským součinem všech svých Sylowovských podgrup GPi. Aplikujeme-li předchozí důsledek na naši situaci, dostáváme, že pro podgrupu G(1) platí |G(1 )| = ^ • £2 w • • ■ ťkk _p, ^. == Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Je tedy grupa G(1) izomorfní s kartézským součinem grup G x GP1 x GP2, kde G = Gt^ x Gř«2 x • • • x Gt<*k- 12 k Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Je tedy grupa g(1) izomorfní s kartézským součinem grup G x gp1 x gp2, kde G = Gt^ x gř«2 x • • • x Gt<*k- 12 k Počet prvků x e g(1), jejichž exponent nebude soudělný se součinem p1Q1 je Proto pravděpodobnost, že náhodně zvolené x e g(1) nebude mít exponent h, který je násobek p1 • q1 , bude rovna \G • (Pí + Qi ) - a _p^+q^-^ Q ■p^■q^ Pí • Qi < 10 -90 (3.15) 1_F Naprostá většina prvků pologrupy M má tedy exponent, který je násobkem prvočísel p^ & q^,\]. h = a-p^ - q^. Naprostá většina prvků pologrupy M má tedy exponent, který je násobkem prvočísel p^ & q^,\]. h = a-p^ - q^. Aplikujeme-li tedy tento postup na grupu r různých transformací Ts pro pevně zvolený modul A/, víme, že se jedná o komutativní grupu, která má přesně (nsn{ai,f>i}) = a2 • b2 • 9?(nsn{a-|,£>-|}) • p2 • q2- Snadno lze spočítat prvky x e G(1), jejichž exponent není dělitelný součinem p2q2. Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Snadno lze spočítat prvky x e G(1), jejichž exponent není dělitelný součinem p2Q2- Pak pravděpodobnost, že při iterovaném šifrování budeme úspěšní, je Faktorizace Napadání RSA Algebraické vlastnosti Algebraický popis Iterovaný útok Snadno lze spočítat prvky x e G(1), jejichž exponent není dělitelný součinem p2Q2- Pak pravděpodobnost, že při iterovaném šifrování budeme úspěšní, je Navíc exponent h pro většinu transformací Ts je řádově 10180. Poznámka. Poznamenejme, že existuje ještě další zřejmá možnost, jak úspěšně narušit RSA-algoritmus a to za předpokladu, že známe