Adleman algoritmusa

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2017. július 27-én felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

Az Adleman-algoritmus az első szubexponenciális diszkrét logaritmus -algoritmus a maradékok gyűrűjében prímszám modulo . Az algoritmust Leonard Max Adleman (született: Leonard Adleman - Aidlman ) javasolta 1979 -ben . Leonard Max Adleman ( 1945. december 31. ) amerikai informatikus , a Dél - Kaliforniai Egyetem számítástechnika és molekuláris biológia professzora . Az RSA titkosítási rendszer (Rivest-Shamir-Adleman, 1977 ) és a DNS -számítógép társfeltalálójaként ismert . Az RSA -t széles körben használják számítógépes biztonsági alkalmazásokban , beleértve a HTTPS protokollt is .

Matematikai apparátus

A modulo m maradékok redukált rendszere a modulo m maradékrendszer összes olyan számának halmaza , amelyek viszonylag prímek m -hez képest . A modulo m redukált maradékrendszer φ( m ) számokból áll, ahol φ( ) az Euler-függvény . Bármely φ(m) szám, amely páronként összehasonlíthatatlan modulo m és ezzel a modulussal együtt prím, a maradékok redukált rendszerét jelenti. A modulo m maradékok redukált rendszereként általában 1-től m-ig terjedő számokat vesznek fel . Ha x is átmegy a modulo m redukált maradékrendszeren, akkor az ax is olyan értékeket vesz fel, amelyek a redukált maradékrendszert alkotják modulo this [1] . $m-1$ $(a,m)=1$

A redukált reziduumok rendszere a modulo m szorzóval egy csoportot alkot, amelyet multiplikatív csoportnak vagy a modulo m maradékgyűrű invertálható elemeinek csoportját alkotnak , amelyet vagy jelöl . ${\mathbb {Z}}_{m}^{{\times }}$ $U({\mathbb {Z}}_{m})$

A polinom faktorizálása egy adott polinom reprezentációja alacsonyabb fokú polinomok szorzataként.

Az algebra alaptétele kimondja, hogy a komplex számok területén minden polinom ábrázolható lineáris polinomok szorzataként, és egyedi módon egy állandó tényezőig és a tényezők sorrendjéig.

A faktorálási polinomok ellentéte a kibővítésük , a polinomtényezők szorzása, hogy egy "kibővített" polinomot kapjunk, amely kifejezések összegeként van írva.

Problémafelvetés

Adjuk meg a polinomokat úgy , hogy $\alpha ,\beta ,f\in GF(p^{n}),p\leqslant n$

f

egy irreducibilis normalizált fokszámú polinom

n,

\alpha

a kisebb fokozatú multiplikatív csoport generátora

n,

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

Meg kell találni (ha van ilyen) az összehasonlítást kielégítő természetes számot $x$

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

Az algoritmus leírása

1. szakasz. Tegyük fel

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

2. szakasz. Keresse meg legfeljebb az irreducibilis normalizált fokszámú polinomok halmazát, és számozza meg őket számokkal, honnan hova $T$ $f_{i}\in GF(p^{n})$ $m$ $egy$ $\omega,$

\omega =|T|.

3. szakasz. Válasszunk véletlenszerűen számokat és hasonlókat $z=1.$ $r$ $s$

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

és számítsunk ki egy polinomot úgy, hogy $\gamma$

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

4. szakasz. Ha a kapott polinom a halmaz összes irreducibilis polinomjának szorzata , akkor az $f_{i}$ $T,$

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

hol van a vezető együttható ( véges mező feletti unitáris polinomok faktorizálásához használhatja például a Berlekamp algoritmust ), majd beállítjuk az Ellenkező esetben válasszon más véletlenszerűséget , és ismételje meg a 3. és 4. lépést. Ezután állítsa be és ismételje meg a lépéseket . 3 és 4. Addig ismételjük, amíg Ily módon megkapjuk a halmazokat , és for ${\tilde {\gamma ))$ $\gamma$ $r_{z}=r,$ $s_{z}=s,$ $v_{z}=\left\langle e_{1},e_{2},\dots ,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.$

5. szakasz Kiszámoljuk úgy, hogy a gcd és ${\displaystyle a_{1},a_{2},\dots ,a_{\omega +1))$ $(a_{1},a_{2},\dots ,a_{\omega +1})=1$

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

6. szakasz Számítsunk ki egy olyan számot $l$

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

7. szakasz. Ha gcd , akkor lépjen a 3. lépésre, és válasszon új halmazokat , és egyébként számítson ki számokat és egy polinomot úgy, hogy $(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)).

8. szakasz. Számítsa ki a kívánt számot $x$

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

Az algoritmus másik változata

Kiinduló adatok

Legyen megadva az összehasonlítás

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

((egy))

Meg kell találni egy x természetes számot , amely kielégíti az (1) összehasonlítást.

Az algoritmus leírása

1. szakasz. Alkossunk egy tényezőbázist, amely az összes q prímből áll :

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

2. szakasz. A felsorolás segítségével keress olyan természetes számokat , amelyek $r_{i}$

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

vagyis a faktorbázis szerint bontják. Ebből következik tehát $a^{r_{i}}\mod {p}$

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

(2)

3. szakasz. Sok reláció (2) beírása után oldja meg a kapott lineáris egyenletrendszert a faktorbázis ( ) elemeinek ismeretlen diszkrét logaritmusaira vonatkoztatva. ${\displaystyle \log _{a}{q))$

4. szakasz. Némi felsorolás segítségével keresse meg az r egyik értékét, amelyre

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

hol vannak az „átlagos” prímszámok, azaz ahol van valamilyen szubexponenciális korlát is, ${\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))))}.$

5. szakasz A 2. és 3. lépéshez hasonló számítások segítségével keresse meg a diszkrét logaritmusát . $\log _{a}{p_{i))$

6. szakasz Határozza meg a kívánt diszkrét logaritmust:

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}}.

Számítási összetettség

Az Adleman-algoritmusnak van egy heurisztikus becslése az aritmetikai műveletek összetettségére, ahol van valamilyen állandó. A gyakorlatban nem elég hatékony. $O(\exp {(c(\log {p}\log {\log {p)))^{1/2})})$ $c$

Alkalmazások

A diszkrét logaritmus probléma az egyik fő probléma, amelyen a nyilvános kulcsú kriptográfia alapul .

Diszkrét logaritmus

A diszkrét logaritmus (DLOG) egy függvény invertálásának problémája valamilyen véges multiplikatív csoportban . $g^{x}$ $G$

Leggyakrabban a diszkrét logaritmus problémát egy maradékgyűrű vagy egy véges mező multiplikatív csoportjában , valamint egy véges mező feletti elliptikus görbe pontjainak csoportjában veszik figyelembe. A diszkrét logaritmus probléma megoldására szolgáló hatékony algoritmusok általában nem ismertek.

Adott g és a esetén az egyenlet x megoldását az a elem diszkrét logaritmusának nevezzük g bázisban . Abban az esetben, ha G a modulo m maradékgyűrű multiplikatív csoportja, a megoldást az a szám indexének is nevezzük a g bázishoz képest . Egy index a g bázishoz garantáltan létezik, ha g primitív modulo m gyök . $g^{x}=a$

Nyilvános kulcsú titkosítás

Nyilvános kulcsú kriptográfiai rendszer (vagy aszimmetrikus titkosítás , aszimmetrikus titkosítás ) - olyan titkosító és/vagy elektronikus aláírási (ES) rendszer, amelyben a nyilvános kulcsot egy nyílt (azaz nem biztonságos, megfigyelhető) csatornán továbbítják, és az ES ellenőrzésére használják. és a titkosítási üzenetekhez. Az ES generálásához és az üzenet visszafejtéséhez privát kulcsot használnak [2] . A nyilvános kulcsú kriptográfiai rendszereket ma már széles körben használják különféle hálózati protokollokban , különösen a TLS-protokollokban és elődjében, az SSL -ben (a mögöttes HTTPS ), az SSH -ban . A PGP -ben, S/MIME -ben is használatos . Az erre épülő klasszikus kriptográfiai sémák a Diffie-Hellman megosztott kulcsgenerálási séma , az ElGamal elektronikus aláírási séma, az üzenetátvitelhez Massey-Omura kriptorendszer. A kriptográfiai erősségük az exponenciális függvény invertálásának állítólagos nagy számítási bonyolultságán alapul .

Diffie-Hellman protokoll

A Diffie-Hellman protokoll ( eng. Diffie-Hellman , DH ) egy kriptográfiai protokoll , amely lehetővé teszi két vagy több fél számára, hogy megosztott titkos kulcsot szerezzenek olyan kommunikációs csatorna használatával, amely nem védett a meghallgatástól. Az így kapott kulcsot a további cserék titkosítására használják szimmetrikus titkosítási algoritmusok segítségével .

A Diffie és Hellman által javasolt nyilvános kulcs-elosztási séma igazi forradalmat hozott a titkosítás világában, mivel megszüntette a klasszikus kriptográfia fő problémáját - a kulcselosztás problémáját.

A Diffie-Hellman algoritmus tiszta formájában sebezhető a kommunikációs csatornában történő adatmódosításokkal szemben, beleértve a " Man in the middle " támadást is, így az ezt használó sémák további egy- vagy kétirányú hitelesítési módszereket alkalmaznak.

Az ElGamal sémája

Az Elgamal-séma egy nyilvános kulcsú kriptorendszer , amely a diszkrét logaritmusok véges mezőben történő kiszámításának nehézségén alapul . A kriptorendszer tartalmaz egy titkosítási algoritmust és egy digitális aláírási algoritmust. Az ElGamal-séma a korábbi digitális aláírási szabványok alapja az Egyesült Államokban ( DSA ) és Oroszországban ( GOST R 34.10-94 ).

A sémát Taher El-Gamal javasolta 1985 - ben . [3] El-Gamal kifejlesztette a Diffie-Hellman algoritmus egy változatát . Javította a Diffie-Hellman rendszert, és kapott két algoritmust, amelyeket titkosításra és hitelesítésre használtak. Az RSA-val ellentétben az ElGamal algoritmust nem szabadalmazták, ezért olcsóbb alternatívává vált, mivel nem kellett licencdíjat fizetni. Úgy gondolják, hogy az algoritmus a Diffie-Hellman szabadalom hatálya alá tartozik.

Jegyzetek

↑ Bukhshtab, A. A. Számelmélet. - M .: Nevelés, 1966. - 385 p.
↑ Bruce Schneier. Alkalmazott kriptográfia. 2. kiadás Protokollok, algoritmusok és forrásszövegek C nyelven. 2.7. fejezet Digitális aláírás és titkosítás.
↑ Taher ElGamal. Egy nyilvános kulcsú kriptorendszer és egy diszkrét logaritmuson alapuló aláírási séma // IEEE Transactions on Information Theory : folyóirat. - 1985. - 1. évf. 31 , sz. 4 . - P. 469-472 . - doi : 10.1109/TIT.1985.1057074 .

Irodalom

Leonard M. Adleman, Jonathan Demarrais. Szubexponenciális algoritmus diszkrét logaritmusokhoz minden véges mezőre // A számítás matematikája. – 1993.
Vasilenko O.N. Számelméleti algoritmusok a kriptográfiában . - 2003. (Orosz) (elérhetetlen link)
Coppersmith D. Diszkrét logaritmusok gyors kiértékelése a ketteskarakterisztikus mezőkben . – 1984.