Algoritmy teorie čísel Radan Kučera, doplněk, podzimní semestr 2021 Motivace Někdy (například při řešení diofantických rovnic) potřebujeme pracovat v okruhu R celých algebraických čísel tělesa algebraických čísel K (tj. K je konečné rozšíření Q). Obecně R není okruh s jednoznačným rozkladem, ale je to Dedekindův okruh, a tedy každý nenulový ideál okruhu R lze jednoznačně rozložit na součin prvoideálů. Místo rozkládání celého algebraického čísla a ∈ R na součin ireducibilních prvků okruhu R můžeme rozkládat hlavní ideál aR na součin prvoideálů. Pak ale v jisté chvíli se potřebujeme vrátit zpět od ideálu k číslu, které jej generuje, což je však možné jen v případě, že jde o hlavní ideál. V tom případě je generátor tohoto hlavního ideálu určen až na násobení jednotkou. Obstrukce kontrolující, zda je daný ideál hlavní, je skryta v grupě tříd ideálů ClK , kterou lze definovat jako faktorgrupu grupy všech lomených ideálů okruhu R podle podgrupy hlavních lomených ideálů. Proto potřebujeme popsat následující aritmetické objekty okruhu R: jeho grupu tříd ideálů ClK a jeho grupu jednotek R×. Grupa jednotek R× je konečně generovaná Torzní část WK grupy R× je konečná cyklická grupa obsahující všechny odmocniny z jedné patřící do K. Z-rank grupy R× je dán Dirichletovou větou: R× ∼= WK × Zr , kde r := rankZ R× = s + t − 1, přičemž s je počet reálných vnoření tělesa K a t je počet párů nereálných vnoření tělesa K. Tudíž stupeň [K : Q] = s + 2t. Tato vnoření mohou být určena například takto: existuje α ∈ K takové, že K = Q(α). Minimální polynom f (X) ∈ Q[X] čísla α má s reálných kořenů α1, . . . , αs a t dvojic komplexně sdružených kořenů αs+1, αs+1, . . . , αs+t, αs+t. Nechť σi je vnoření určené α → αi . Pak σi je reálné, právě když i ≤ s. Tudíž známe Z-rank r grupy R×, ale nalezení fundamentálních jednotek, tj. generátorů grupy R×/WK , je velmi obtížný problém. Přestože je znám algoritmus, jeho časová náročnost se stupněm [K : Q] roste velmi rychle. Geometrie jednotek Logaritmické zobrazení : R× → Rr+1 je definováno předpisem (ε) = (. . . , δi log |σi (ε)|, . . . ), kde δi = 1 pro i ≤ s a δi = 2 jinak. Pak ker = WK a (R×) ⊂ H = (x1, . . . , xr+1) | r+1 i=1 xi = 0 . Pro libovolnou r-tici η1, . . . , ηr ∈ R× definujeme regulátor R(η1, . . . ηr ) = det(δi log |σi (ηj )|)i,j=1,...,r . Tudíž regulátor R(η1, . . . ηr ) je dán r-rozměrným objemem rovnoběžnostěnu daného obrazy (η1), . . . , (ηr ) v H. Proto R(η1, . . . ηr ) = 0, právě když jednotky η1, . . . , ηr jsou (multiplikativně) závislé. Regulátor RK tělesa K je definován jako regulátor libovolného systému fundamentálních jednotek (tj. r-tice jednotek generujících spolu s WK grupu všech jednotek R×). Platí [R× : Wk ∪ {η1, . . . , ηr } ] = R(η1,...ηr ) RK , je-li R(η1, . . . ηr ) = 0. Dedekindova ζ-funkce ζK tělesa K Dedekindova ζ-funkce ζK tělesa K je definována v oblasti z ∈ C, (z) > 1, absolutně konvergentní řadou ζK (z) = A (N(A))−z , kde A probíhá množinu všech nenulových ideálů okruhu R a N(A) = |R/A| je absolutní norma A. Protože R je Dedekindův okruh, každý nenulový ideál A je jednoznačně dán jako součin prvoideálů. Absolutní norma ideálů je multiplikativní, a tedy funkce ζK (z) je dána Eulerovým součinem přes všechny prvoideály okruhu R: je-li (z) > 1, pak ζK (z) = P (1 − N(P)−z )−1 . Grupa tříd ideálů ClK je konečná grupa Erich Hecke dokázal, že funkce ζK (z) má meromorfní prodloužení na celé C s jediným pólem v z = 1. Tento pól je jednoduchý a jeho residuum je lim z→1 (z − 1)ζK (z) = 2s(2π)thK RK |WK | · |DK | , kde hK = | ClK | je počet tříd ideálů a DK je diskriminant tělesa K, který je definován takto: Aditivní grupa (R, +) je volná komutativní grupa ranku rankZ R = [K : Q] = s + 2t. Nechť b1, . . . , bs+2t je systém nezávislých generátorů grupy (R,+), pak diskriminant DK je druhá mocnina determinantu det σ1(bj ), . . . , σs+t(bj ), σs+1(bj ), . . . , σs+t(bj ) j=1,...,s+2t . Odhad součinu hK RK Speciálně pro těleso Q je Dedekindova ζ-funkce ζQ rovna Riemannově ζ-funkci a platí limz→1(z − 1)ζQ(z) = 1. Proto 2s(2π)thK RK |WK | · |DK | = lim z→1 ζK (z) ζQ(z) = lim z→1 p 1 − p−z P|pR (1 − N(P)−z) , kde ve vnějším součinu probíhá p všechna prvočísla, zatímco vnitřní součin je vzat přes konečně mnoho prvoideálů P vystupujících v rozkladu ideálu pR. Proto spočítáme-li rozklady všech ideálů pR pro všechna prvočísla p < L pro jistou dostatečně velkou hranici L, platí přibližně hK RK ˙= |WK | · |DK | 2s(2π)t p 1, (e, λ) = 1, (e − 1, λ) = 1 (doporučuje se e > 216) a spočítat f ∈ Z, f > 0, ef ≡ 1 (mod λ). Veřejný klíč: n, e. Tajný klíč: f (také p, q, pomocí nichž lze f snadno spočítat). Šifrování: Zpráva je m ∈ Z, 1 < m < n. Odesílající použije veřejný klíč a odešle zbytek po dělení čísla me číslem n, tj. odešle x ∈ Z, 0 < x < n, x ≡ me (mod n). Dešifrování: Příjemce použije tajný klíč, zpráva m je zbytek po dělení čísla xf číslem n, neboť m ≡ xf (mod n). Protože příjemce zná prvočísla p, q, může výpočet zrychlit tím, že postupně najde zbytky po dělení čísla xf čísly p a q a pak m určí pomocí Čínské zbytkové věty. Okruh Z[i] Z[i] = {a + bi; a, b ∈ Z} je okruh s jednoznačným rozkladem (dokonce eukleidovský vzhledem k normě N(a + bi) = a2 + b2 ). Grupa jednotek Z[i]× = {1, i, −1, −i}. Libovolný ideál je hlavní, nenulové prvoideály jsou generovány ireducibilními prvky. Každý ireducibilní prvek se vyskytne v rozkladu právě jednoho prvočísla. Prvočíslo 2 = −i(1 + i)2, N(1 + i) = 2. Prvočísla q ≡ 3 (mod 4) jsou ireducibilní prvky, N(q) = q2. Prvočísla p ≡ 1 (mod 4) se rozkládají na součin dvou nesoudělných ireducibilních prvků: p = ππ, N(π) = N(π) = p. Ireducibilní prvek λ se nazývá primární, jestliže λ ≡ 1 (mod 2+2i). Pro každý ireducibilní prvek λ 2 existuje jediný asociovaný prvek, který je primární. Pro libovolný ireducibilní prvek λ 2 a libovolné α ∈ Z[i], λ α definujme čtvrtý mocninný symbol (α λ )4 čísla α vzhledem k λ podmínkou (α λ )4 ∈ {1, i, −1, −i}, (α λ )4 ≡ α(N(λ)−1)/4 (mod λ). Zákon bikvadratické reciprocity v okruhu Z[i] Ireducibilní prvek λ se nazývá primární, jestliže λ ≡ 1 (mod 2+2i). Pro libovolný ireducibilní prvek λ 2 a libovolné α ∈ Z[i], λ α definujeme čtvrtý mocninný symbol (α λ )4 čísla α vzhledem k λ podmínkou (α λ )4 ∈ {1, i, −1, −i}, (α λ )4 ≡ α(N(λ)−1)/4 (mod λ). Existence a jednoznačnost mocninného symbolu (α λ )4 plyne z toho, že Z[i]/(λ) je těleso mající N(λ) prvků, v němž polynom x4 − 1 má čtyři různé kořeny (třídy obsahující čísla 1, i, −1, −i). Z λ α plyne αN(λ)−1 ≡ 1 (mod λ), a tedy α(N(λ)−1)/4 je jeden z kořenů. Věta 1. Nechť λ ∈ Z[i] je ireducibilní, λ 2, α, β ∈ Z[i], λ αβ. Pak x4 ≡ α (mod λ) má řešení v Z[i] ⇐⇒ (α λ )4 = 1, (αβ λ )4 = (α λ )4(β λ )4, α ≡ β (mod λ) =⇒ (α λ )4 = (β λ )4. Věta 2. Jestliže π a λ jsou nesoudělné primární ireducibilní prvky, pak (π λ )4 = (λ π )4 · (−1)(N(π)−1)(N(λ)−1)/16) . Počet bodů na eliptické křivce y2 = x3 − ax nad Zp Věta 3. Nechť p je prvočíslo, a ∈ Z, přičemž p = 2, p a. Nechť N je počet bodů na eliptické křivce y2 = x3 − ax nad Zp. Je-li p ≡ 3 (mod 4), pak N = p + 1. Je-li p ≡ 1 (mod 4) a p = ππ je rozklad čísla p na součin dvou primárních ireducibilních prvků v Z[i], pak N = p + 1 − ( a π )4 · π − ( a π )4 · π. Dokažme větu jen pro lehčí první případ: je-li p ≡ 3 (mod 4), pak Legendreův symbol (−1 p ) = −1. Na eliptické křivce leží nevlastní bod O a bod [0, 0]. Pro každé u = 1, . . . , p−1 2 spočítejme počet bodů, jejichž x-ová souřadnice je ±u. Označme v = u3 − au. Je-li v = 0, máme dva body [u, 0], [−u, 0]. Je-li v = 0, je právě jedno z čísel v, −v kvadratický zbytek modulo p, a tedy z kongruencí y2 ≡ v (mod p) a y2 ≡ −v (mod p) má jedna dvě řešení a druhá žádné. Proto opět dostáváme dva body, jejichž x-ová souřadnice je ±u. Příklad: eliptická křivka y2 = x3 − 2x nad Z101 Rozložme p = 101 v Z[i]. Platí p = 101 = (10 + i)(10 − i) = (1 + 10i)(1 − 10i). Označme π = −1 + 10i, pak π je primární. Víme, že ( 2 π )4 ∈ {1, i, −1, −i}, ( 2 π )4 ≡ 2(N(π)−1)/4 = 225 (mod π). Protože 225 ≡ 10 (mod 101), je ( 2 π )4 ≡ 10 ≡ 100i ≡ −i (mod π), a tedy ( 2 π )4 = −i. Podle věty 3 pro počet N bodů na eliptické křivce y2 = x3 − 2x nad Z101 platí N = p + 1 − ( 2 π )4 · π − ( 2 π )4 · π = 102 − i · π + i · π = 122. Okruh Z[ω], kde ω = −1 2 + √ 3 2 i Z[ω] = {a + bω; a, b ∈ Z} je okruh s jednoznačným rozkladem (dokonce eukleidovský vzhledem k N(a + bω) = a2 − ab + b2 ). Grupa jednotek Z[i]× = {1, ω, ω2, −1, −ω, −ω2}. Libovolný ideál je hlavní, nenulové prvoideály jsou generovány ireducibilními prvky. Každý ireducibilní prvek se vyskytne v rozkladu právě jednoho prvočísla. Prvočíslo 3 = −ω2(1 − ω)2, N(1 − ω) = 3. Prvočísla q ≡ 2 (mod 3) jsou ireducibilní prvky, N(q) = q2. Prvočísla p ≡ 1 (mod 3) se rozkládají na součin dvou nesoudělných ireducibilních prvků: p = ππ, N(π) = N(π) = p. Ireducibilní prvek λ se nazývá primární, jestliže λ ≡ 2 (mod 3). Pro každý ireducibilní prvek λ 3 existuje jediný asociovaný prvek, který je primární. Pro libovolný ireducibilní prvek λ 6 a libovolné α ∈ Z[ω], λ α definujme šestý mocninný symbol (α λ )6 čísla α vzhledem k λ podmínkou (α λ )6 ∈ {±1, ±ω, ±ω2 }, (α λ )6 ≡ α(N(λ)−1)/6 (mod λ). Zákon kubické reciprocity v okruhu Z[ω] Ireducibilní prvek λ se nazývá primární, jestliže λ ≡ 2 (mod 3). Pro libovolný ireducibilní prvek λ 6 a libovolné α ∈ Z[ω], λ α definujeme šestý mocninný symbol (α λ )6 čísla α vzhledem k λ podmínkou (α λ )6 ∈ {±1, ±ω, ±ω2}, (α λ )6 ≡ α(N(λ)−1)/6 (mod λ). Existence a jednoznačnost mocninného symbolu (α λ )6 plyne z toho, že těleso Z[ω]/(λ) má N(λ) prvků a polynom x6 − 1 v něm má šest různých kořenů (třídy obsahující čísla ±1, ±ω, ±ω2). Z λ α plyne αN(λ)−1 ≡ 1 (mod λ), a tedy α(N(λ)−1)/6 je jeden z kořenů. Věta 4. Nechť λ ∈ Z[ω] je ireducibilní, λ 3, α, β ∈ Z[ω], λ αβ. Pak x6 ≡ α (mod λ) má řešení v Z[ω] ⇐⇒ (α λ )6 = 1, x3 ≡ α (mod λ) má řešení v Z[ω] ⇐⇒ (α λ )6 = ±1, (αβ λ )6 = (α λ )6(β λ )6, α ≡ β (mod λ) =⇒ (α λ )6 = (β λ )6. Věta 5. Jestliže π a λ jsou primární ireducibilní prvky takové, že N(π) = N(λ), pak (π λ )6 = ±(λ π )6. Počet bodů na eliptické křivce y2 = x3 + b nad Zp Věta 6. Nechť p je prvočíslo, b ∈ Z, přičemž p > 3, p b. Nechť N je počet bodů na eliptické křivce y2 = x3 + b nad Zp. Je-li p ≡ 2 (mod 3), pak N = p + 1. Je-li p ≡ 1 (mod 3) a p = ππ je rozklad čísla p na součin dvou primárních ireducibilních prvků v Z[ω], pak N = p + 1 + (4b π )6 · π + (4b π )6 · π. Dokažme větu jen pro lehčí první případ: je-li p ≡ 2 (mod 3), pak zobrazení f : Zp → Zp určené předpisem f (t) = t3 je bijekce, neboť na nulu se zobrazí jen nula a zúžení f na Z× p je homorfismus grup s triviálním jádrem. Proto pro každé y ∈ Zp existuje jediné x ∈ Zp splňující f (x) = y2 − b. Pro každé y ∈ Zp tedy existuje jediné x ∈ Zp tak, že [x, y] leží na eliptické křivce. Kromě nevlastního bodu O existuje na eliptické křivce tedy právě p bodů. Příklad: eliptická křivka y2 = x3 + 2 nad Z103 Rozložme p = 103 v Z[ω]. Hledáme tedy u, v ∈ Z, aby u2 − uv + v2 = p. Pak 4p = (2u − v)2 + 3v2, lze tedy postupovat dosazováním malých přirozených čísel za v. V našem případě 4p = 412 = 202 + 3 · 22. Proto 11 + 2ω je ireducibilní prvek dělící p, není však primární. Je třeba jej vynásobit vhodnou mocninou ω, abychom dostali koeficient u ω dělitelný třemi. Platí (11 + 2ω)ω = 11ω + 2(−1 − ω) = −2 + 9ω, což také není primární, ale vynásobením −1 dostaneme hledaný primární ireducibilní prvek π = 2 − 9ω. Potřebujeme spočítat (4b π )6, v tomto případě je 4b = 8 třetí mocnina, a tak můžeme použít Legendreův symbol 8(p−1)/6 = 2(p−1)/2 ≡ (2 p ) (mod p). Je tedy ( 8 π )6 = ( 2 103) = 1. Podle věty 6 pro počet N bodů na eliptické křivce y2 = x3 + 2 nad Z103 platí N = p+1+( 8 π )6·π+( 8 π )6·π = 104+π+π = 104+4−9ω−9ω2 = 117. KMOV – základní myšlenka Nechť n = pq pro velká prvočísla p = q, kde p ≡ q ≡ 2 (mod 3). Libovolnou dvojici A = [u, v], kde u, v ∈ Z jsou taková, že b = v2 − u3 je nesoudělné s n, lze interpretovat jako bod ležící současně na dvou eliptických křivkách daných rovnicí y2 = x3 + b, totiž na Ep nad Zp a na Eq nad Zq. Podle věty 6 platí |Ep| = p + 1 a |Eq| = q + 1. I v případě, že neznáme p a q, lze pomocí výpočtů prováděných modulo n takové dvojice reprezentující body na obou křivkách sčítat, problémy vzniknou jen v případě, že výsledný bod je neutrální prvek na právě jedné z těchto dvou křivek. Avšak jsou-li prvočísla p, q opravdu velká, nalezení takového bodu je krajně nepravděpodobné (víme, že znalost takového bodu znamená znalost rozkladu n na součin prvočísel). Nechť λ je společný násobek čísel p + 1 a q + 1. Pak pro každé přirozené číslo t ≡ 1 (mod λ) platí t · A = A. KMOV – použití Generování klíčů: Je nutné zvolit velká prvočísla p ≡ q ≡ 2 (mod 3) (přibližně stejně velká, např. p < q < 2p, ale s velkým rozdílem q − p), n = pq, λ je (nejmenší) společný násobek čísel p + 1 a q + 1 (je možné vzít λ = (p + 1)(q + 1) ). Dále je nutné zvolit e ∈ Z, e > 1, (e, λ) = 1, (e − 1, λ) = 1 a spočítat f ∈ Z, f > 0, ef ≡ 1 (mod λ). Veřejný klíč: n, e. Tajný klíč: f (také p, q, pomocí nichž lze f snadno spočítat). Šifrování: Zpráva je dvojice [m1, m2], kde m1, m2 ∈ Z, 1 < m1 < n, 1 < m2 < n. Odesílající interpretuje dvojici A = [m1, m2] jako bod ležící současně na eliptických křivkách Ep nad Zp a na Eq nad Zq daných rovnicí y2 = x3 + b, kde b = m2 2 − m3 1 (případ b soudělného s n je nepravděpodobný). Použije veřejný klíč a spočítá bod B = e · A, který pak odešle (výpočty provádí modulo n). Dešifrování: Příjemce použije tajný klíč a spočítá zprávu A = f · B (výpočty může provádět modulo n, anebo postup zrychlit tak, že počítá postupně modulo p a modulo q, pak užije Čínskou zbytkovou větu). Kryptosystém Alshehhi-Nitaj – základní myšlenka Nechť pro přirozená čísla r, s je p = (4r + 3)2 + (4s + 2)2 prvočíslo. Pak p ≡ 5 (mod 8) a p se v Z[i] rozkládá na součin p = ππ, kde π = (4r + 3) + (4s + 2)i je primární ireducibilní prvek. Označme u = 4r + 3, v = 4s + 2, tedy π = u + iv, najdeme c ∈ Z, aby cv ≡ u (mod p). Protože c2v2 ≡ u2 ≡ −v2 (mod p), je c2 ≡ −1 (mod p). Zvolme libovolně a ∈ Z, p a. Podle věty 3 pro počet N bodů na eliptické křivce y2 = x3 − ax platí N = p + 1 − ( a π )4 · π − ( a π )4 · π. Víme, že ( a π )4 ∈ {1, i, −1, −i}, ( a π )4 ≡ a(p−1)/4 (mod π). Rozlišme a(p−1)/4 ≡ 1 (mod p), pak ( a π )4 = 1 a N = p + 1 − 2u. a(p−1)/4 ≡ −1 (mod p), pak ( a π )4 = −1 a N = p + 1 + 2u. a(p−1)/4 ≡ c (mod p), pak ( a π )4 ≡ c (mod π), a tedy ( a π )4 · π + ( a π )4 · π ≡ c(u − iv) ≡ 2cu ≡ 2c2v ≡ −2v (mod π). Protože ( a π )4 · π + ( a π )4 · π ∈ Z, je ( a π )4 · π + ( a π )4 · π ≡ −2v (mod p). Platí |π| = |π| = √ p < p 4 , |2v| < 2 √ p < p 2 , tedy ( a π )4 · π + ( a π )4 · π = −2v, a proto N = p + 1 + 2v. a(p−1)/4 ≡ −c (mod p), pak analogicky N = p + 1 − 2v. Kryptosystém Alshehhi-Nitaj – použití Generování klíčů: Je nutné zvolit velká přirozená čísla r1, s1, r2, s2, aby pro u1 = 4r1 + 3, v1 = 4s1 + 2, u2 = 4r2 + 3, v2 = 4s2 + 2 byla p1 = u2 1 + v2 1 a p2 = u2 2 + v2 2 různá prvočísla. Pak n = p1p2. Dále je nutné zvolit e ∈ Z, e > 1, tak, aby čísla e i e − 1 byla nesoudělná s každým z čísel (pi + 1)2 − 4u2 i , (pi + 1)2 − 4v2 i , i = 1, 2. Veřejný klíč: n, e. Tajný klíč: u1, v1, u2, v2, p1, p2. Šifrování: Zpráva je číslo m ∈ Z, 0 < m < n. Odesílající zvolí náhodné r ∈ Z, 0 < r < n (je možné toto r použít k podpisu zprávy), může ověřit, že (m, n) = 1, (r, n) = 1, (m2 − r3, n) = 1, což skoro jistě platí, jinak by „uhádl rozklad n (s výjimkou případu n | m2 − r3) a spočítá a ∈ Z splňující ra ≡ m2 − r3 (mod n). Platí (a, n) = 1 a lze interpretovat dvojici A = [r, m] jako bod ležící současně na eliptických křivkách Ep1 nad Zp1 a na Ep2 nad Zp2 daných rovnicí y2 = x3 + ax. Odesílající pak spočítá bod B = e · A, který odešle (výpočty provádí modulo n). Kryptosystém Alshehhi-Nitaj – dešifrování Příjemce použije tajný klíč a najde zbytky po dělení obou souřadnic bodu B prvočísly p1 a p2, tím získá bod B1 = [x1, y1] na Ep1 a bod B2 = [x2, y2] na Ep2 . Díky podmínkám při volbě e je násobení číslem e automorfismem na obou křivkách, a proto body B1, B2 nemají řád 2, a tedy obě souřadnice těchto bodů jsou nenulové. Pro každé i = 1, 2 určí ai z kongruence ai xi ≡ y2 i − x3 i (mod pi ). Toto ai ≡ a ≡ 0 (mod pi ). Spočítá a (pi −1)/4 i modulo pi , čímž získá počet Ni bodů na eliptické křivce Epi , neboť Je-li a (pi −1)/4 i ≡ ±1 (mod pi ), pak Ni = pi + 1 2ui . Je-li vi · a (pi −1)/4 i ≡ ±ui (mod pi ), pak Ni = pi + 1 ± 2vi . Najde fi , aby e · fi ≡ 1 (mod Ni ) a spočítá bod Ci = fi · Bi na Epi . Pak užije Čínskou zbytkovou větu, aby našel bod C, jehož souřadnice modulo p1 dávají C1 a modulo p2 dávají C2. Platí C = A (pro získání zprávy m stačí spočítat y-ovou souřadnici, pro případné ověření podpisu je nutné určit i x-ovou). Kryptosystém Alshehhi-Nitaj – možnost podpisu Možností, jak podepsat zprávu, je hodně, probereme jednu z nich. Obě strany se předem dohodnou na metodě, jak vhodně odvodit číslo z ∈ Z ze znalosti n, aby z2 > n > 2z, například z = [100 √ n ]. Předpokládejme, že odesílatel si vytvořil veřejný a tajný klíč pro RSA, jehož modul ˜n = ˜p · ˜q splňuje 2z < ˜n < n. Tajný klíč ˜f , ˜p, ˜q zná jen odesílatel, veřejný klíč ˜n, ˜e zná i příjemce (a je si jist, že skutečně patří odesílateli, tj. že klíč není podvržen). Odesílatel vyjádří zprávu m v z-adické poziční soustavě jako m = tz + s a užitím svého tajného klíče spočítá zbytek w po dělení čísla (t + s + 1) ˜f číslem ˜n. Při šifrování volí náhodně celé číslo g ≥ 0 tak, aby r = g ˜n + w < n. Pak r ≡ (t + s + 1) ˜f (mod ˜n). Příjemce tím, že spočítá bod C, najde čísla r, m. Určí pak z, t, s stejným postupem jako odesílatel a zjistí, zda r ˜e ≡ t + s + 1 (mod ˜n). Pokud ano, uvěří, že zpráva pochází opravdu od odesílatele, neboť jen on znal číslo ˜f (platí 1 < t + s + 1 < ˜n). Diskrétní logaritmus Nechť (G, ·) je konečná grupa, g ∈ G prvek řádu n. Pak pro každé h ∈ g existuje c ∈ Z tak, že h = gc. Toto celé číslo c je určeno jednoznačně modulo n a dotyčná zbytková třída [c]n se nazývá diskrétní logaritmus prvku h o základu g, píšeme [c]n = logg h (někdy se diskrétním logaritmem rozumí celé číslo c, pak je nutno mít na paměti, že je určeno jen modulo n). Přestože jsou všechny n-prvkové cyklické grupy izomorfní, v některých grupách je úloha nalezení diskrétního logaritmu snadná, v jiných obtížná. Záleží totiž na tom, jak jsou označeny jednotlivé prvky dané grupy. Příklad. V grupě (Zm, +) je g = [a]m, h = [b]m. Při hledání diskrétního logaritmu řešíme kongruenci ax ≡ b (mod m), pomocí Eukleidova algoritmu nalezneme Bezoutovu rovnost, což dá hledaný diskrétní logaritmus (jde o algoritmus kvadratické časové náročnosti). Diskrétní logaritmus v grupě (Z× p , ·) pro prvočíslo p Grupa (Z× p , ·) je cyklická; označme g primitivní kořen modulo p. Ve starší literatuře bývají definována celá čísla gi podmínkou gi ≡ gi (mod p), 0 < gi < p, pak log[g]p [gi ]p = [i]p−1, proto se dříve diskrétnímu logaritmu v této grupě říkalo index. Nejrychlejší známý algoritmus na počítání diskrétních logaritmů v této grupě je proto nazýván „index calculus . Má subexponenciální časovou náročnost. Tento algoritmus si popíšeme podrobněji, některé jeho části jsou podobné metodě kvadratického síta. V roce 2001 A. Joux a R. Lecier ukázali, že tento algoritmus lze užít k počítání diskrétních logaritmů v grupě (Z× p , ·), kde p je 120-ciferné prvočíslo (v bázi faktorizace měli milión nejmenších prvočísel). Analogický algoritmus je možné použít i pro výpočet diskrétního logaritmu v multiplikativní grupě libovolného konečného tělesa. Index calculus Nechť p1, . . . , pr je báze faktorizace složená z „malých prvočísel. Hledáme kongruence tvaru gai ≡ (−1)ei,0 · r j=1 p eij j (mod p), které znamenají (pro jednoduchost pišme čísla místo zbytkových tříd) ai ≡ ei,0 · p−1 2 + r j=1 eij · logg pj (mod p − 1). Máme-li takových kongruencí dost, určíme z nich logg pj pro každé j = 1, . . . , r. Pak stačí jediná kongruence tvaru h · gb ≡ (−1)f0 · r j=1 p fj j (mod p), odkud logg h ≡ −b + f0 · p−1 2 + r j=1 fj · logg pj (mod p − 1). Algoritmy pro hledání diskrétního logaritmu v obecné grupě Předchozí algoritmus „index calculus využíval toho, že každou zbytkovou třídu reprezentuje celé číslo, jehož absolutní hodnotu můžeme jednoznačně rozložit na součin prvočísel. Nyní vysvětlíme následující algoritmy, které je možné použít na výpočet logg h v libovolné konečné grupě: Shanksova metoda „Baby steps, giant steps , Pollardova ρ-metoda, Pollardova λ-metoda. Všechny tři metody mají exponenciální časovou náročnost O( √ n). Shanksova metoda je deterministická, vyžaduje však uložit O( √ n) informace do paměti. Není nutné znát řád n základu g diskrétního logaritmu, postačí horní odhad tohoto řádu. Je schopna zjistit, že h /∈ g . Pollardovy metody jsou nedeterministické, jde tedy o odhadovanou časovou náročnost. Nejsou náročné na paměť, vyžadují však, aby h ∈ g a aby řád n základu g diskrétního logaritmu byl znám. Shanksova metoda „Baby steps, giant steps Předpokládejme, že řád n prvku g v grupě (G, ·) splňuje n ≤ m2 pro známé celé číslo m > 0. Pro dané h ∈ G chceme zjistit, zda h ∈ g , a pokud ano, chceme najít c ∈ Z, pro které h = gc. Není nutné znát přesnou hodnotu n, pokud nám stačí najít jen jedno řešení c a ne všechna. Každé c = 0, 1, . . . , n − 1 můžeme psát ve tvaru c = um + v, kde u, v ∈ {0, 1, . . . , m − 1}. Je-li tedy h = gc, pak h · g−um = gv . Nejprve spočítáme g0, g, g2, . . . , gm (postupným násobením prvkem g) a uložíme g0, g, g2, . . . , gm−1 tak, abychom mohli v tomto seznamu rychle vyhledávat. Pak postupně hledáme, zda v našem seznamu je h, h · g−m, h · g−2m, . . . , h · g−(m−1)m (postupným násobením inverzním prvkem g−m k již spočítanému prvku gm). Jakmile v seznamu objevíme první z nich, můžeme skončit, neboť z rovnosti h · g−um = gv plyne h = gum+v . Úprava Shanksovy metody pro eliptické křivky Je-li dána eliptická křivka E nad konečným tělesem Fq, pak z Hasseho věty plyne |E| ≤ q + 1 + 2 √ q. Proto pro výpočet diskrétního logaritmu logP Q o základu P ∈ E lze volit přirozené číslo m s vlastností q + 1 + 2 √ q ≤ m2. Protože body a jejich inverze na eliptické křivce mají stejnou x-ovou souřadnici a opačnou y-ovou souřadnici, stačí v seznamu mít jen body O, P, 2P, . . . , tP, kde t = [m 2 ], a testovat, zda Q − umP = ±vP. Pak Q = cP pro c = um ± v. Na rozdíl od obvyklého c ≥ 0 nyní platí jen c ≥ −t, ale to ve většině aplikací nevadí (je-li dokonce řád bodu P znám, je to nepodstatné). Pollardova ρ-metoda výpočtu logg h pro h ∈ g Tuto metodu jsme už poznali při hledání netriviálního dělitele. Potřebujeme znát řád n základu g diskrétního logaritmu a vědět, že h ∈ g . Označme G = g . Sestrojíme zobrazení f : G → G, pro které by mohlo platit, že se chová jako náhodné, abychom mohli odhadnout, že rekurentní posloupnost určená předpisem xi = f (xi−1) má pro libovolné počáteční x0 předperiodu i periodu délky O( √ n). Vhodnou funkci můžeme definovat například takto: grupu G rozložíme na několik tříd C1, . . . , Ct. Zvolíme náhodná čísla a0, a1, . . . , at, b0, b1, . . . , bt ∈ {1, 2, . . . , n − 1}. Položíme yj = gaj · hbj a definujeme posloupnost předpisem x0 = y0, xi = f (xi−1), kde f (x) = x · yj , je-li x ∈ Cj . Pak každé vypočtené xi je tvaru xi = gui · hvi , přitom celá čísla ui , vi počítáme modulo n. Pollardova ρ-metoda výpočtu logg h pro h ∈ g yj = gaj · hbj , x0 = y0, xi = f (xi−1), f (x) = x · yj pro x ∈ Cj . Při výpočtu neuchováváme hodnoty všech už vypočtených členů posloupnosti, ale jen dvojici xi , x2i spolu s ui , vi , u2i , v2i . Jestliže platí xi = x2i , což by mělo nastat po O( √ n) krocích, máme rovnost gui · hvi = gu2i · hv2i , tedy gui −u2i = hv2i −vi . Pro hledaný diskrétní logaritmus logg h tedy platí (v2i − vi ) · logg h ≡ ui − u2i (mod n). Je-li v2i − vi nesoudělné s n, je touto kongruencí logg h určen. Je-li největší společný dělitel d = (v2i − vi , n) malý, můžeme vyzkoušet všech d řešení této kongruence. Je-li d velké, můžeme začít znovu s jinými aj , bj (získanou informaci o hodnotě logg h modulo n d uchováme, abychom ji mohli využít, pokud ani další podobná kongruence neurčí logg h jednoznačně). V kryptografických aplikacích však bývá n prvočíslo. Pollardova λ-metoda výpočtu logg h pro h ∈ g Jde o metodu počítanou paralelně na několika počítačích. Používá funkci f definovanou stejně jako u Pollardovy ρ-metody. Několik počítačů počítá hodnoty rekurentních posloupností daných stejnou funkcí f pro různé počáteční hodnoty x0. Hodnoty xi splňující jistou zvolenou podmínku (například patří do třídy C1) jsou hlášeny do centrálního počítače (spolu s jejich vyjádřením ve tvaru součinu mocnin prvků g a h). Centrální počítač nahlášené hodnoty ukládá a porovnává. Vyhodnotí, pokud obdržel stejnou hodnotu podruhé, a následně ze dvojího vyjádření této hodnoty získá stejně jako u Pollardovy ρ-metody informaci o logg h. Metoda Pohlig-Hellman výpočtu logg h pro h ∈ g Tato metoda vysvětluje, proč v kryptografických aplikacích diskrétního logaritmu mívá generátor g prvočíselný řád n. Jestliže řád n generátoru g není prvočíslo a známe jeho rozklad na součin mocnin různých prvočísel n = i qei i , můžeme hledaný diskrétní logaritmus logg h nalézt pomocí Čínské zbytkové věty poté, co pro každé i určíme jeho zbytek po dělení číslem qei i . Nechť k = logg h a pro prvočíslo q | n platí qe | n, qe+1 n; v q-adické poziční soustavě zapišme k = k0 + k1q + k2q2 + . . . , kde 0 ≤ ki < q. Postupně nalezneme ki pro i = 0, 1, . . . , e − 1. Označme ˜g = gn/q. Pak k0 = log˜g hn/q a pro každé i = 1, . . . , e − 1 platí ki = log˜g (h · g−k0−qk1−···−qi−1ki−1 )n/qi+1 . Přitom ˜g má řád q a logaritmy o základu ˜g můžeme nalézt Shanksovou metodou „Baby steps, giant steps v O( √ q) krocích. Praktická využití faktu, že výpočet diskrétního logaritmu na elipticé křivce je obtížný Pokud na eliptické křivce nad konečným tělesem dán bod P, jehož řád n je velké prvočíslo, výpočet diskrétního logaritmu v grupě P bývá obtížný. Na tom jsou založeny následující kryptosystémy pro komunikaci odposlouchávatelným kanálem, při kterých je předem (veřejně) dohodnuta eliptická křivka a bod na ní: Diffie-Hellman – výroba společného tajemství, Massey-Omura – přenos tajné zprávy (je poslána třikrát: tam, zpět a znovu tam) pomocí tajných klíčů příjemce i odesílatele, El Gamal – přenos tajné zprávy pomocí tajného a veřejného klíče, které vytvořil příjemce zprávy. Kryptosystém Diffie-Hellman Obě strany se (veřejně) dohodnou na eliptické křivce nad konečným tělesem a bodu P na ní tak, aby problém diskrétního logaritmu o základu P byl obtížný (obvykle jsou křivka a bod zvoleny tak, aby řád bodu P bylo velké prvočíslo). Strana A zvolí své tajné přirozené číslo a, spočítá bod Pa = aP, který odešle straně B. Strana B zvolí své tajné přirozené číslo b, spočítá bod Pb = bP, který odešle straně A. Strana A použije číslo a k výpočtu bodu aPb. Strana B použije číslo b k výpočtu bodu bPa. Protože aPb = abP = bPa, sdílí obě strany týž tajný bod. Problém Diffie-Hellman: Ze znalosti bodů P, aP, bP nalezni abP. Je jasné, že výpočet diskrétního logaritmu a = logP(aP) nebo b = logP(bP) tento problém vyřeší. Neví se, zda existuje metoda, která by vyřešila tento problém bez výpočtu diskrétního logaritmu. Kryptosystém Massey-Omura Tento kryptosystém by se dal popsat následovně: Alice chce Bobovi poslat tajnou zprávu. Tak ji sepsanou dá do krabice, na kterou umístí svůj zámek, a pošle Bobovi. Ten na krabici připevní ještě svůj zámek, a odešle zpět. Alice odemkne svůj zámek a krabici zamknutou pouze zámkem Boba odešle Bobovi, aby si mohl krabici odemknout a přečíst zprávu. Jak to implementovat matematicky? Alice se s Bobem (veřejně) dohodnou na eliptické křivce nad konečným tělesem tak, aby problém diskrétního logaritmu byl na ní obtížný (křivka může být například zvolena tak, že její řád je velké prvočíslo nebo dvojnásobek velkého prvočísla). Dále se dohodnou, jak reprezentovat zprávu jako bod na této křivce. Jeden způsob, jak snadno přiřadit zprávě bod na dané eliptické křivce, aby bylo možné ze znalosti tohoto bodu zprávu zpětně zrekonstruovat, si později vysvětlíme. Kryptosystém Massey-Omura Alice se s Bobem dohodli na eliptické křivce nad konečným tělesem i na postupu, jak libovolné zprávě přiřadit bod na této křivce. Označme n řád dohodnuté eliptické křivky. Alice svou zprávu reprezentuje jako bod M na dohodnuté eliptické křivce. Alice zvolí své tajné přirozené číslo u nesoudělné s n, spočítá bod M1 = uM, který odešle Bobovi. Bob zvolí své tajné přirozené číslo v nesoudělné s n, spočítá bod M2 = vM1, který odešle Alici. Alice najde celé číslo ˜u, které je řešení kongruence ux ≡ 1 (mod n), a spočítá bod M3 = ˜uM2, který odešle Bobovi. Bob najde celé číslo ˜v, které je řešení kongruence vx ≡ 1 (mod n), a spočítá bod M4 = ˜vM3. Protože M4 = ˜v ˜uvuM, přičemž platí ˜v ˜uvu ≡ 1 (mod n) a nM = O, je M4 = M. Jak přiřadit zprávě bod na dané eliptické křivce Jde-li o křivku danou rovnicí y2 = x3 + ax + b nad Zp pro prvočíslo p ≡ 3 (mod 4), lze postupovat například takto: Nechť zprávou je celé číslo m, kde 0 ≤ m < p 100. Pro j = 0, 1, . . . , 99 označme xj = 100m + j, sj = x3 j + axj + b. Protože sj vznikají v podstatě náhodně, lze jevy ( sj p ) = 1 považovat za nezávislé, přičemž pravděpodobnost každého z nich je 1 2. Rychle lze najít j tak, že ( sj p ) = 1, a spočítat yj ≡ s (p+1)/4 j (mod p). Pak y2 j ≡ s (p+1)/2 j ≡ ( sj p ) · sj (mod p). Proto bod [xj , yj ] leží na dané křivce. Ze znalosti tohoto bodu získáme zprávu m výpočtem m = [ xj 100]. Kryptosystém El Gamal Alice chce poslat zprávu Bobovi, Bob si proto nachystá tajný a veřejný klíč. Bob zvolí eliptickou křivku E nad konečným tělesem Fq a bod P na ní tak, aby problém diskrétního logaritmu o základu P byl obtížný (obvykle jsou křivka a bod zvoleny tak, aby řád bodu P bylo velké prvočíslo). Bob zvolí své tajné přirozené číslo v nesoudělné s řádem bodu P a na E spočítá bod B = vP. Veřejný klíč: eliptická křivka E nad Fq, body P, B. Tajný klíč: číslo v (které je diskrétním logaritmem v = logP B). Alice si zjistí Bobův veřejný klíč a vyjádří svou zprávu jako bod M na E. Dále zvolí své tajné přirozené číslo u. Pak na E spočítá body M1 = uP, M2 = M + uB. Alice se ujistí, že uP = O (tj. u není dělitelné řádem bodu P) a odešle body M1, M2 Bobovi. Bob spočítá M2 − vM1 = (M + uB) − v(uP) = M a tím určí zprávu, kterou odesílala Alice. Podepisování zprávy kryptosystémem El Gamal Alice chce poslat podepsanou zprávu Bobovi, pro jednoduchost předpokládejme, že tuto zprávu není nutné utajit šifrováním. Alice si proto nachystá tajný a veřejný klíč. Alice zvolí eliptickou křivku E nad konečným tělesem Fq a bod P na ní tak, aby problém diskrétního logaritmu o základu P byl obtížný (obvykle jsou křivka a bod zvoleny tak, aby řád n bodu P bylo velké prvočíslo). Alice zvolí své tajné přirozené číslo u nesoudělné s n a na E spočítá bod B = uP. Dále zvolí funkci f : E → Z, aby f (E) ∩ nZ = ∅. Například, je-li q prvočíslo (a ne mocnina prvočísla), q < n, může f (C) být nejmenší přirozené číslo ze zbytkové třídy modulo q, která je x-ovou souřadnicí daného bodu C. Veřejný klíč: eliptická křivka E nad Fq, body P, B, funkce f : E → Z. Tajný klíč: číslo u (které je diskrétním logaritmem u = logP B). Podepisování zprávy kryptosystémem El Gamal Veřejný klíč: eliptická křivka E nad Fq, body P, B, funkce f : E → Z. Tajný klíč: číslo u (které je diskrétním logaritmem u = logP B). Zpráva, kterou chce Alice podepsat, je přirozené číslo m ≤ n (kde n je řád bodu P). Alice pro tuto zprávu zvolí tajné přirozené číslo k nesoudělné s n, spočítá bod R = kP a najde celé číslo s, které je řešení kongruence kx ≡ m − u · f (R) (mod n). Alice Bobovi odešle trojici (m, R, s). Bob na E spočítá body V = f (R) · B + sR, W = mP. Jestliže platí V = W , uvěří Bob, že je zpráva skutečně od Alice, neboť f (R) · B + sR = f (R) · uP + skP = (f (R) · u + sk)P = mP. Je třeba si uvědomit, že pro výpočet podpisu s bylo třeba využít nejen tajného klíče u (a tedy mohl podpis s spočítat jen ten, kdo tajný klíč znal), ale i zprávy m (a tedy nelze podpis s podvrhnout podpisem jiné zprávy). MOV útok na kryptosystémy využívající obtížnost výpočtu diskrétního logaritmu na eliptické křivce Menezes, Okamoto a Vanstone navrhli, jak užít tzv. Weilovo párování na zrychlení výpočtu diskrétního logaritmu na eliptické křivce E nad konečným tělesem Fq. Protože jsme nevysvětlili, co je to Weilovo párování, zmiňme jen, že jejich metoda převádí výpočet diskrétního logaritmu na E na výpočet diskrétního logaritmu v multiplikativní grupě tělesa Fqm , kde je možné použít zobecnění metody „index calculus . To může tento výpočet zrychlit v případě, kdy m je malé. Pro křivky splňující |E| = q + 1 dokonce stačí vzít m = 2. To je v jistém smyslu škoda, protože právě pro tyto křivky existuje metoda výpočtu násobku bodu, která je rychlejší než obvyklá metoda rychlého umocňování v grupě (kterou lze použít pro všechny eliptické křivky).