Gelfond-Shanksův algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. prosince 2019; kontroly vyžadují 9 úprav .

Algoritmus Gelfond-Shanks ( ang. Baby-step gigant-step ; také nazývaný algoritmus velkých a malých kroků ; velmi často se také můžete setkat s názvem párovací algoritmus , například ve Vasilenkově knize "Number-Theoretic Algorithms of Cryptography" ) - v teorii grup deterministický algoritmus diskrétních logaritmů v multiplikativní grupě zbytkového kruhu modulo prvočíslo. Navrhli to sovětský matematik Alexander Gelfond v roce 1962 a Daniel Shanks v roce 1972 [1] [2] [3] .

Metoda teoreticky zjednodušuje řešení problému diskrétního logaritmu, na jehož výpočetní složitosti je postaveno mnoho kryptosystémů s veřejným klíčem . Odkazuje na metody setkání uprostřed .

Rozsah

Problém diskrétního logaritmu je velmi zajímavý pro konstrukci kryptosystémů s veřejným klíčem . Za předpokladu extrémně vysoké výpočetní náročnosti řešení tohoto problému jsou takovéto kryptoalgoritmy založeny např. RSA , DSA , Elgamal , Diffie-Hellman , ECDSA , GOST R 34.10-2001 , Rabin a další. V nich může kryptoanalytik získat soukromý klíč tím, že vezme diskrétní logaritmus veřejného klíče (známý všem) a použije jej k převedení šifrovaného textu na text zprávy. Čím je však obtížnější jej najít (čím více operací musíte provést, abyste našli diskrétní logaritmus), tím bezpečnější je kryptosystém. Jedním ze způsobů, jak zvýšit složitost problému diskrétního logaritmu, je vytvořit kryptosystém založený na skupině s velkým řádem (kde logaritmus bude modulo velké prvočíslo). V obecném případě je takový problém vyřešen vyčerpávajícím výčtem , ale tento algoritmus v některých případech umožňuje zjednodušit nalezení exponentu (snížit počet kroků) při výpočtu modulo prvočíslo, v nejvýhodnějším případě odmocninou. krát [4] , ale tato redukce stále nestačí k vyřešení problému na elektronickém počítači v rozumném čase (otázka řešení problému diskrétního logaritmu v polynomiálním čase na osobním počítači je stále otevřená) [5] .

Problém diskrétního logaritmu

Nechť je dána cyklická skupina s generátorem obsahující prvky. Celé číslo (v rozsahu od do ) se nazývá diskrétní základní logaritmus prvku , pokud je vztah pravdivý: $G$ $G$ $n$ $X$ $0$ $n-1$ $h\v G$ $G$

g^{x}=h.

Úkolem diskrétního logaritmu je určit pro daný . $h$ $G$ $X$

Formálně je problém diskrétního logaritmu položen následovně [6] :

{\begin{cases}{\text{Input:}}\quad &g,h,n\in \mathbb {N} \\{\text{Output:}}\quad &x\in \mathbb {N } :\ g^{x}\equiv h{\pmod {n}}\\\end{cases}}

za předpokladu, že nemusí existovat a může to být také prvočíslo nebo složené číslo. $X$ $n$

Teorie

Myšlenkou algoritmu je zvolit optimální poměr času a paměti , konkrétně ve vylepšeném hledání exponentu.

Nechť je uvedena cyklická skupina řádu , generátor skupiny a nějaký prvek skupiny . Úkol je redukován na nalezení celého čísla, pro které $G$ $n$ $\alpha$ $\beta$ $X$

\alpha^x = \beta\,.

Algoritmus Gelfond-Shanks je založen na reprezentaci ve formě , where , a výčtu a . Omezení a vyplývá z toho, že pořadí skupiny nepřesahuje , což znamená, že uvedené rozsahy jsou dostatečné pro získání všech možných z polovičního intervalu . Tato reprezentace je ekvivalentní rovnosti $X$ $x=i\cdot mj$ $m = \left\lfloor \sqrt{n} \right\rfloor + 1$ $1 \leq i \leq m$ $0 \leq j < m$ $i$ $j$ $m$ $X$ $\left[0; m\vpravo)$

$\alpha^{im} = \beta \alpha^j\,.$

(jeden)

Algoritmus předem vypočítá různé hodnoty a uloží je do datové struktury , která umožňuje efektivní vyhledávání, a poté iteruje všechny možné hodnoty a zkontroluje, zda odpovídají nějaké hodnotě . Jsou tedy nalezeny indexy a , které splňují vztah (1) a umožňují vypočítat hodnotu [7] . $\alpha^{im}$ $i$ $j$ ${\displaystyle \beta \alpha ^{j))$ $i$ $i$ $j$ $x=i\cdot mj$

Algoritmus

Vstup : Skupina cyklického řádu , generátor a nějaký prvek . $G$ $n$ $\alpha$ $\beta$

Výstup : Číslo , které vyhovuje . $X$ $\alpha^{x}=\beta$

$m$ ← $\left\lfloor {\sqrt {n}}\right\rfloor +1$
Vypočítejte ← . $\gamma$ ${\displaystyle \alpha ^{m))$
Pro libovolné , kde ≤ ≤ : $i$ $jeden$ $i$ $m$
1. Napište do tabulky ( , ). (Viz část Implementace) $i$ $\gamma$
2. $\gamma$ ← • $\gamma$ ${\displaystyle \alpha ^{m))$
Pro libovolné , kde ≤ ≤ : $j$ $0$ $j$ $m-1$
1. Vypočítejte . ${\displaystyle \beta \alpha ^{j))$
2. Zkontrolujte, zda tabulka obsahuje. ${\displaystyle \beta \alpha ^{j))$
3. Pokud ano, vraťte - . $im$ $j$
4. Pokud ne, pokračujte smyčkou [1] [2] [7] .

Zdůvodnění algoritmu

Je třeba dokázat, že stejné prvky v tabulkách nutně existují, tedy existují takové a , že . Tato rovnost nastává v případě , nebo . Pro , nerovnost platí . Pro různé páry a máme , protože jinak by se ukázalo , že s uvedenou volbou je to možné pouze v případě , a tedy . Výrazy tedy nabývají všech hodnot v rozsahu od do , což vzhledem k tomu, že obsahuje všechny možné hodnoty od do . Pro některé tedy platí i rovnost [2] . $i$ $j$ ${\displaystyle g^{mi}=\beta \cdot g^{j}=g^{x+j))$ $mi=x+j{\pmod {n}}$ $x=mi-j{\pmod {n))$ $1\leq i\leq m$ $1\leq j\leq m$ $0\leq mi-j\leq m^{2}-1$ $(i_{1},j_{1})$ $(i_{2},j_{2})$ ${\displaystyle mi_{1}-j_{1}\neq mi_{2}-j_{2))$ $m(i_{1}-i_{2})=(j_{1}-j_{2})$ $i_{1},i_{2}$ $i_{1}=i_{2}$ ${\displaystyle j_{1}=j_{2))$ $mi-j$ $0$ $m^{2}-1$ $m^{2}>n$ $X$ $0$ $n-1$ $i$ $j$ $x=mi-j{\pmod {n))$

Odhad složitosti algoritmu

Předpokládejme, že potřebujeme vyřešit , kde a jsou kladná celá čísla menší než . Jedním ze způsobů je iterovat postupně od do a porovnávat hodnotu s . V nejhorším případě potřebujeme kroky (když ). V průměru to udělá kroky. Jinak můžeme reprezentovat jako . Problém je tedy redukován na nalezení a . V tomto případě můžete úkol přepsat jako nebo . Nyní můžeme iterovat přes všechny možné hodnoty na pravé straně výrazu. V tomto případě se jedná o všechna čísla od do . To jsou takzvané velké kroky. Je známo, že jedna ze získaných hodnot pro je požadovaná. Všechny hodnoty pravé strany výrazu můžeme zaznamenat do tabulky. Poté můžeme vypočítat možné hodnoty pro levou stranu pro různé hodnoty . Toto jsou všechna čísla od do , z nichž jedno je požadované a spolu se správnou hodnotou pravé strany dává požadovaný výsledek pro . Úkol je tedy redukován na třídění různých hodnot na levé straně a jejich vyhledávání v tabulce. Pokud je požadovaná hodnota nalezena v tabulce, pak jsme našli , a tedy odpovídající . Tento obrázek ukazuje rychlost algoritmu. V průměru se provádějí operace. V nejhorším případě jsou nutné operace [3] . $h=ng$ $h$ $G$ $100$ $n$ $jeden$ $100$ $n \cdot g$ $h$ $100$ $n=99$ $padesáti$ $n$ $n = 10a-b$ $A$ $b$ $h = (10a-b)g$ $h+bg=10ag$ $A$ $jeden$ $deset$ $A$ $b$ $0$ $9$ $n$ $b$ $n=10a+b$ $1.5{\sqrt {n))$ $2{\sqrt {n))$

Příklad

Níže je uveden příklad řešení problému diskrétního logaritmu s objednávkou malé skupiny. V praxi kryptosystémy používají skupiny vyššího řádu ke zlepšení kryptografické síly .

Dejte to vědět . Na začátku si vytvoříme a vyplníme tabulku pro „velké kroky“. Vyberme ← ( ). Poté poběží od do . $5^{x}\equiv 3{\pmod {23}}$ $m=5$ ${\sqrt {16}}+1$ $i$ $jeden$ $5$

$i$	jeden	2	3	čtyři	5
${\displaystyle 5^{im}=20^{i))$	dvacet	9	19	12	deset

Pojďme najít vhodnou hodnotu pro , aby se hodnoty v obou tabulkách shodovaly $j$ $3\cdot 5^{j}\ {\bmod {\ }}23$

$j$	jeden	2	3	čtyři
$\beta \alpha ^{j}=3$ · $5^{j}$	patnáct	6	7	12

Je vidět, že ve druhé tabulce pro je taková hodnota již v první tabulce. Najít [2] . $j=4$ $x=mi-j=5\cdot 4-4=16$

Implementace

Existuje způsob, jak zlepšit výkon algoritmu Gelfond-Shanks. Spočívá v použití efektivního schématu přístupu k tabulce. Nejlepším způsobem je použít hashovací tabulku . Měli byste hashovat druhou komponentu a poté provést vyhledávání hashů v tabulce v hlavní smyčce na . Protože přístup a přidávání prvků do hashovací tabulky vyžaduje čas ( konstanta ), asymptoticky to nezpomaluje algoritmus. $\gamma$ $O(1)$

Doba běhu algoritmu se odhaduje jako , což je mnohem lepší než doba běhu vyčerpávajícího výčtu exponentů [4] . $O({\sqrt {n)))$ $Na)$

Funkce

Gelfond-Shanksův algoritmus pracuje pro libovolnou konečnou cyklickou grupu [7] [3] .
Pořadí skupiny není potřeba znát předem. Algoritmus také funguje, pokud je horní mez řádu skupiny [7] . $G$ $n$
Algoritmus Gelfond-Shanks se obvykle používá pro skupiny , jejichž pořadí je prvočíslo . Pokud je objednávka složené číslo , pak se doporučuje použít Polig-Hellmanův algoritmus [7] .
Algoritmus Gelfond-Shanks vyžaduje paměť. V prvním kroku algoritmu je možné zvolit menší . Tím se prodlouží doba běhu programu na . Pro diskrétní logaritmus je také možné použít Pollardovu ρ-metodu , která pracuje ve stejnou dobu, ale vyžaduje malé množství paměti [7] . $Na)$ $m$ $O(n/m)$

Poznámky

↑ 1 2 D. Shanks. Infrastruktura reálného kvadratického pole a její aplikace. Sborník příspěvků z konference Teorie čísel. - University of Colorado, Boulder, 1972. - S. pp. 217-224. .
↑ 1 2 3 4 I. A. Pankratová. Číselné teoretické metody v kryptografii: Učebnice. - Tomsk: TSU, 2009. - S. 90-98. — 120 s. .
↑ 1 2 3 V.I. Něčajev. Prvky kryptografie. Základy teorie informační bezpečnosti . - M . : Vyšší škola, 1999. - S. 61 -67. — 109 s. — ISBN 5-06-003644-8 . .
↑ 12 D.C. Terr . Modifikace Shanksova algoritmu baby-step gigant-step . — Matematika počítání. - 2000. - T. 69. - S. 767-773. .
↑ Vasilenko O. N. Číselné teoretické algoritmy v kryptografii . - Moskva: MTSNMO , 2003. - S. 163-185. — 328 s. — ISBN 5-94057-103-4 . Archivovaná kopie (nedostupný odkaz) . Datum přístupu: 23. listopadu 2016. Archivováno z originálu 27. ledna 2007. (neurčitý) .
↑ Yan, Song Y. Testování primality a faktorizace celých čísel v kryptografii s veřejným klíčem . - 2. - Springer, 2009. - S. 257-260. — 374 s. — ISBN 978-0-387-77267-7 . .
↑ 1 2 3 4 5 6 Glukhov M. M., Kruglov I. A., Pichkur A. B., Cheremushkin A. V. Úvod do číselně-teoretických metod kryptografie. - 1. vyd. - Petrohrad. : Lan, 2010. - S. 279-298. — 400 s. S. - ISBN 978-5-8114-1116-0 . .

Literatura

A.O. Gelfond, Yu.V. Linnik. Elementární metody v analytické teorii čísel. - M. : Fizmatgiz, 1962. - 272 s.

Číselné teoretické algoritmy
Testy jednoduchosti	Mlynář Miller - Rabin Luca - Lemaire pepina Agravala - Kayala - Sasko Slavík - Strassen
Hledání prvočísel	Iterace přes dělitele Eratosthenovo síto Atkinovo síto Síto Sundarama
Faktorizace	Iterace přes dělitele Fermatova metoda p −1 Pollardova metoda Pollardův ρ-algoritmus Lehmannova metoda Metoda eliptické křivky (Lenstrův algoritmus) Dixonův algoritmus Čtvercové síto
Diskrétní logaritmus	Gelfond-Shanksův algoritmus Polig-Hellmanův algoritmus Pollardova ρ-metoda Pollardův algoritmus klokana Adlemanův algoritmus COS algoritmus
Hledání GCD	Euklidův algoritmus Pokročilý algoritmus Binární algoritmus
Modulová aritmetika	Montgomeryho algoritmus Čínská věta o zbytku
Násobení a dělení čísel	Algoritmus Karatsuba Toom-Cookův algoritmus Schönhage-Strassenův algoritmus Fuhrerův algoritmus Algoritmus Harvey-van der Hoeven Burnickel-Zieglerův algoritmus
Výpočet druhé odmocniny	Tonelli-Shanksův algoritmus Algoritmus Berlekamp-Rabin