Adlemanů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é 27. července 2017; kontroly vyžadují 3 úpravy .

Adlemanův algoritmus je první subexponenciální diskrétní logaritmický algoritmus v kruhu zbytků modulo prvočíslo . Algoritmus navrhl Leonard Max Adleman (narozený jako Leonard Adleman-Aidlman ) v roce 1979 . Leonard Max Adleman ( narozený 31. prosince 1945 ) je americký počítačový vědec a profesor informatiky a molekulární biologie na University of Southern California . Je známý jako spoluvynálezce šifrovacího systému RSA (Rivest-Shamir-Adleman, 1977 ) a DNA computingu . RSA je široce používán v aplikacích počítačové bezpečnosti , včetně protokolu HTTPS .

Matematický aparát

Redukovaný systém zbytků modulo m je množina všech čísel úplného systému zbytků modulo m , která jsou relativně prvočísla k m . Redukovaný systém reziduí modulo m se skládá z φ( m ) čísel, kde φ( ) je Eulerova funkce . Jakákoli φ(m) čísla, která jsou párově nesrovnatelná modulo m a jsou shodná s tímto modulem, představují redukovaný systém zbytků. Jako redukovaný systém zbytků modulo m se obvykle berou čísla od 1 do , coprime až m . Pokud x prochází také redukovaným systémem zbytků modulo m, pak ax nabývá také hodnot, které tvoří redukovaný systém zbytků modulo this [1] . $m-1$ $(a, m) = 1$

Redukovaný systém zbytků s multiplikačním modulem tvoří skupinu zvanou multiplikativní skupina nebo skupinu invertibilních prvků reziduálního kruhu modulo m , která se označuje nebo . ${\mathbb {Z}}_{m}^{{\times }}$ $U({\mathbb {Z}}_{m})$

Faktorizace polynomu je zobrazením daného polynomu jako součinu polynomů nižších stupňů.

Základní věta algebry říká, že každý polynom na poli komplexních čísel může být reprezentován jako součin lineárních polynomů a jedinečným způsobem až do konstantního faktoru a pořadí faktorů.

Opakem faktoringu polynomů je jejich rozšiřování , násobení polynomiálních faktorů k vytvoření "rozšířeného" polynomu zapsaného jako součet členů.

Problémové prohlášení

Nechť jsou polynomy dány tak, že $\alpha ,\beta ,f\in GF(p^{n}),p\leqslant n$

F

je neredukovatelný normalizovaný polynom stupně

n,

\alpha

je generátorem multiplikativní grupy stupně menší než

n,

\beta \not \equiv 0{\pmod {f)).

Je nutné najít (pokud takové existuje) přirozené číslo vyhovující srovnání $X$

\alpha ^{x}\equiv \beta {\pmod {f)).

Popis algoritmu

Fáze 1. Položme

m=\left\lceil {\sqrt {\frac {n\log n}{\log p))}\right\rceil .

Fáze 2. Najděte množinu neredukovatelných normalizovaných polynomů stupně nejvýše a očíslujte je čísly odkud $T$ $f_{i}\in GF(p^{n})$ $m$ $jeden$ $\omega ,$

\omega =|T|.

Fáze 3. Vyberme náhodně čísla a podobně $z=1.$ $r$ $s$

0\leqslant r,s<p^{n}-1,

a vypočítat polynom takový, že $\gamma$

\gamma \equiv \alpha ^{r}\beta ^{s}{\pmod {f)).

Fáze 4. Pokud je výsledný polynom součinem všech ireducibilních polynomů z množiny , tzn $f_{i}$ $T,$

\gamma ={\tilde {\gamma }}\prod _{i=1}^{\omega }{f_{i}^{e_{i}}},

kde je vedoucí koeficient (pro rozklad unitárních polynomů nad konečným polem můžete použít např. Berlekampův algoritmus ), pak nastavíme Jinak zvolte jiný náhodný a opakujte kroky 3 a 4. Poté vytvořte a opakujte kroky 3 a 4. Opakujte, dokud ti, dokud Tímto způsobem dostaneme sady , a pro ${\tilde {\gamma ))$ $\gamma$ $r_{z}=r,$ $s_{z}=s,$ $v_{z}=\left\langle e_{1},e_{2},\tečky ,e_{\omega +1}\right\rangle .$ $r$ $s$ $z=z+1$ $z\leqslant \omega +1.$ $r_{i}$ $s_{i}$ $v_{i}$ $1\leqslant i\leqslant \omega +1.$

Fáze 5 Počítáme tak, že gcd a ${\displaystyle a_{1},a_{2},\tečky ,a_{\omega +1))$ $(a_{1},a_{2},\tečky ,a_{\omega +1})=1$

\sum \limits _{i=1}^{\omega +1}{a_{i}v_{i}}\equiv \left\langle 0,0,\tečky ,0\right\rangle {\ pmod {p^{n}-1}}.

Fáze 6 Vypočítejme takové číslo $l$

l=\sum _{i=1}^{\omega +1}s_{i}a_{i}.

Fáze 7. Pokud gcd , přejděte ke kroku 3 a vyberte nové sady a jinak vypočítejte čísla a polynom tak, že $(l,p^{n}-1)\neq 1,$ $r_{i}$ $s_{i}$ $v_{i}$ $1\leqslant i\leqslant \omega +1.$ $k,y$ $s$

k=\sum _{i=1}^{\omega +1}r_{i}a_{i},

s\equiv \alpha ^{k}\beta ^{l}{\pmod {f)),

\alpha ^{y{\frac {p^{n}-1}{p-1))}\equiv s{\pmod {f)).

Fáze 8. Vypočítejte požadované číslo $X$

x\equiv {\frac {y{\frac {p^{n}-1}{p-1}}-k}{l}}{\pmod {p^{n}-1}}.

Další verze algoritmu

Počáteční údaje

Nechť je uvedeno srovnání

a^{x}\equiv b{\pmod {p)),

((jeden))

Je třeba najít přirozené číslo x , které vyhovuje srovnání (1).

Popis algoritmu

Fáze 1. Vytvořte faktorovou základnu sestávající ze všech prvočísel q :

{\displaystyle q\leq B=e^{const{\sqrt {\log {p}\log {\log {p)))))))

Fáze 2. Pomocí výčtu najděte přirozená čísla taková, že $r_{i}$

a^{r_{i}}\equiv \prod \limits _{q\leq B}q^{\alpha _{iq}}{\pmod {p)),

to znamená, že se rozkládá podle faktorové báze. Z toho tedy vyplývá $a^{r_{i}}\mod {p}$

r_{i}\equiv \sum \limits _{q\leq B}\alpha _{iq}\log _{a}{q}{\pmod {p-1)).

((2))

Fáze 3. Po napsání mnoha vztahů (2) řešte výslednou soustavu lineárních rovnic s ohledem na neznámé diskrétní logaritmy prvků faktorové báze ( ). ${\displaystyle \log _{a}{q))$

Fáze 4. Pomocí nějakého výčtu najděte jednu hodnotu r , pro kterou

a^{r}\equiv \prod \limits _{q\leq B}q^{\beta _{q}}p_{1}\cdot ...\cdot p_{k}{\pmod { p}},

kde jsou prvočísla „průměrné“ hodnoty, tj . kde je také nějaká subexponenciální mez, ${\displaystyle p_{1},...,p_{k}\mod {p))$ ${\displaystyle B<p_{i}<B_{1))$ $B_1$ $B_{1}=e^{const{\sqrt {\log {p}\log {\log {p))))}.$

Fáze 5 Pomocí výpočtů podobných krokům 2 a 3 najděte diskrétní logaritmy . $\log _{a}{p_{i))$

Fáze 6 Určete požadovaný diskrétní logaritmus:

x\equiv \log _{a}{b}\equiv \sum \limits _{q\leq B}\beta _{q}\log _{a}{q}+\sum \limits _{ i=1}^{k}\log _{a}{p_{i}}{\pmod {p-1}}.

Výpočetní složitost

Adlemanův algoritmus má heuristický odhad složitosti aritmetických operací, kde je nějaká konstanta. V praxi to není dostatečně efektivní. $O(\exp {(c(\log {p}\log {\log {p)))^{1/2})})$ $C$

Aplikace

Problém diskrétního logaritmu je jedním z hlavních problémů, na kterých je založena kryptografie s veřejným klíčem .

Diskrétní logaritmus

Diskrétní logaritmus (DLOG) je problém invertování funkce v nějaké konečné multiplikativní grupě . $g^{x}$ $G$

Nejčastěji je problém diskrétního logaritmu uvažován v multiplikativní skupině zbytkového kruhu nebo konečného pole , stejně jako ve skupině bodů eliptické křivky nad konečným polem. Účinné algoritmy pro řešení problému diskrétního logaritmu jsou obecně neznámé.

Pro dané g a a se řešení x rovnice nazývá diskrétní logaritmus prvku a v základu g . V případě, že G je multiplikativní skupina zbytkového kruhu modulo m , řešení se také nazývá index čísla a vzhledem k bázi g . Je zaručena existence indexu a až základu g , pokud g je primitivní kořen modulo m . $g^{x}=a$

Kryptografie veřejného klíče

Kryptografický systém s veřejným klíčem (nebo asymetrické šifrování , asymetrická šifra ) – systém šifrování a/nebo elektronického podpisu (ES), ve kterém je veřejný klíč přenášen přes otevřený (tj. nezabezpečený, pozorovatelný) kanál a používá se k ověření ES a pro šifrované zprávy. Pro vygenerování ES a dešifrování zprávy se používá soukromý klíč [2] . Kryptografické systémy s veřejným klíčem jsou nyní široce používány v různých síťových protokolech , zejména protokolech TLS a jeho předchůdci SSL (podkladem HTTPS ), SSH . Používá se také v PGP , S/MIME.Klasická kryptografická schémata na něm založená jsou schéma generování sdíleného klíče Diffie-Hellman , schéma elektronického podpisu ElGamal, kryptosystém Massey-Omura pro přenos zpráv. Jejich kryptografická síla je založena na údajně vysoké výpočetní složitosti invertování exponenciální funkce .

Protokol Diffie-Hellman

Protokol Diffie-Hellman ( anglicky Diffie-Hellman , DH ) je šifrovací protokol , který umožňuje dvěma nebo více stranám získat sdílený tajný klíč pomocí komunikačního kanálu, který není chráněn před nasloucháním. Výsledný klíč se používá k šifrování dalších výměn pomocí symetrických šifrovacích algoritmů .

Schéma distribuce veřejného klíče navržené Diffiem a Hellmanem způsobilo skutečnou revoluci ve světě šifrování, protože odstranilo hlavní problém klasické kryptografie – problém distribuce klíčů.

Ve své čisté podobě je algoritmus Diffie-Hellman zranitelný vůči změnám dat v komunikačním kanálu, včetně útoku „ Man in the middle “, takže schémata, která jej používají, používají další metody jednosměrné nebo obousměrné autentizace.

Schéma ElGamal

Schéma Elgamal je kryptosystém s veřejným klíčem založený na obtížnosti výpočtu diskrétních logaritmů v konečném poli . Šifrovací systém zahrnuje šifrovací algoritmus a algoritmus digitálního podpisu. Schéma ElGamal je základem dřívějších standardů digitálního podpisu ve Spojených státech ( DSA ) a Rusku ( GOST R 34.10-94 ).

Schéma navrhl Taher El-Gamal v roce 1985 . [3] El-Gamal vyvinul variantu Diffie-Hellmanova algoritmu . Vylepšil systém Diffie-Hellman a získal dva algoritmy, které byly použity pro šifrování a pro autentizaci. Algoritmus ElGamal nebyl na rozdíl od RSA patentován, a proto se stal levnější alternativou, protože nebyly vyžadovány žádné licenční poplatky. Předpokládá se, že algoritmus je pokryt patentem Diffie-Hellman.

Poznámky

↑ Bukhshtab, A. A. Teorie čísel. - M .: Vzdělávání, 1966. - 385 s.
↑ Bruce Schneier. Aplikovaná kryptografie. 2. vyd. Protokoly, algoritmy a zdrojové texty v jazyce C. Kapitola 2.7 Digitální podpisy a šifrování.
↑ Taher ElGamal. Kryptosystém s veřejným klíčem a schéma podpisu založené na diskrétních logaritmech // Transakce IEEE na teorii informací : deník. - 1985. - Sv. 31 , č. 4 . - str. 469-472 . - doi : 10.1109/TIT.1985.1057074 .

Literatura

Leonard M. Adleman, Jonathan Demarrais. Subexponenciální algoritmus pro diskrétní logaritmy přes všechna konečná tělesa // Matematika počítání. — 1993.
Vasilenko O.N. Číselné teoretické algoritmy v kryptografii . - 2003. (Ruština) (nepřístupný odkaz)
Coppersmith D. Rychlé vyhodnocení diskrétních logaritmů v polích charakteristiky dvě . — 1984.