Algoritmul lui Adleman

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 27 iulie 2017; verificările necesită 3 modificări .

Algoritmul lui Adleman este primul algoritm subexponențial cu logaritm discret din inelul de reziduuri modulo un număr prim . Algoritmul a fost propus de Leonard Max Adleman (n. Leonard Adleman - Aidlman ) în 1979 . Leonard Max Adleman ( născut la 31 decembrie 1945 ) este un informatician american și profesor de informatică și biologie moleculară la Universitatea din California de Sud . El este cunoscut ca co-inventatorul sistemului de criptare RSA (Rivest-Shamir-Adleman, 1977 ) și al calculului ADN . RSA este utilizat pe scară largă în aplicațiile de securitate informatică , inclusiv protocolul HTTPS .

Aparat matematic

Sistemul redus de reziduuri modulo m este mulțimea tuturor numerelor sistemului complet de reziduuri modulo m care sunt relativ prime pentru m . Sistemul redus de reziduuri modulo m constă din φ( m ) numere, unde φ( ) este funcția Euler . Orice numere φ(m) care sunt perechi incomparabile modulo m și coprime cu acest modul reprezintă un sistem redus de reziduuri. Ca sistem redus de reziduuri modulo m , sunt luate de obicei numere de la 1 la , coprime la m . Dacă x trece și prin sistemul redus de reziduuri modulo m, atunci ax ia și valori care formează sistemul redus de reziduuri modulo this [1] . $m-1$ $(a,m)=1$

Sistemul redus de reziduuri cu înmulțire modulo m formează un grup numit grup multiplicativ sau grupul de elemente inversabile ale inelului de reziduuri modulo m , care este notat cu sau . ${\mathbb {Z}}_{m}^{{\times }}$ $U({\mathbb {Z}}_{m})$

Factorizarea unui polinom este o reprezentare a unui polinom dat ca produs al polinoamelor de grade inferioare.

Teorema fundamentală a algebrei afirmă că fiecare polinom din câmpul numerelor complexe poate fi reprezentat ca produs de polinoame liniare și într-un mod unic până la un factor constant și ordinea factorilor.

Opusul factorizării polinoamelor este extinderea acestora , înmulțirea factorilor polinomii pentru a produce un polinom „extins” scris ca o sumă de termeni.

Declarația problemei

Fie date polinoame astfel încât $\alpha,\beta,f\in GF(p^{n}),p\leqslant n$

f

este un polinom normalizat ireductibil de grad

n,

\alfa

este generatorul grupului multiplicativ de grad mai mic decât

n,

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

Este necesar să găsim (dacă există) un număr natural care să satisfacă comparația $X$

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

Descrierea algoritmului

Etapa 1. Sa punem

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

Etapa 2. Găsiți mulțimea de polinoame normalizate ireductibile de cel mult grad și numerotați-le după numere de la unde $T$ $f_{i}\in GF(p^{n})$ $m$ $unu$ $\omega ,$

\omega =|T|.

Etapa 3. Să alegem la întâmplare numere și așa $z=1.$ $r$ $s$

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

și calculați un polinom astfel încât $\gamma$

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

Etapa 4. Dacă polinomul rezultat este produsul tuturor polinoamelor ireductibile din mulțime , adică $f_{i}$ $T,$

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

unde este coeficientul principal (pentru a factoriza polinoame unitare pe un câmp finit , puteți folosi, de exemplu, algoritmul Berlekamp ), apoi setăm Altfel, alegem alte aleatorii și repetați pașii 3 și 4. După aceea, stabiliți și repetați pașii 3 și 4. Repetați până când cele atât timp cât În acest fel obținem seturile , și pentru ${\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}$ $si}$ $v_{i}$ $1\leqslant i\leqslant \omega +1.$

Etapa 5 Calculăm astfel încât gcd și $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}}.

Etapa 6 Să calculăm un număr astfel încât $l$

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

Etapa 7. Dacă gcd , atunci mergeți la pasul 3 și selectați seturi noi și , în caz contrar, calculați numere și un polinom astfel încât $(l,p^{n}-1)\neq 1,$ $r_{i}$ $si}$ $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)).

Etapa 8. Calculați numărul dorit $X$

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

O altă versiune a algoritmului

Date inițiale

Să se facă comparația

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

((unu))

Este necesar să găsim un număr natural x care să satisfacă comparația (1).

Descrierea algoritmului

Etapa 1. Formați o bază de factori formată din toate numerele prime q :

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

Etapa 2. Folosind enumerarea, găsiți numere naturale astfel încât $r_{i}$

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

adică se descompune după baza factorilor. De aici rezultă că $a^{r_{i}}\mod {p}$

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

((2))

Etapa 3. După ce ați tastat o mulțime de relații (2), rezolvați sistemul rezultat de ecuații liniare în raport cu logaritmi discreti necunoscuti ai elementelor bazei factorilor ( ). $\log _{a}{q)$

Etapa 4. Folosind o enumerare, găsiți o valoare a lui r pentru care

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

unde sunt numere prime de valoare „medie”, adică unde este și o limită subexponențială, $p_{1},...,p_{k}\mod {p)$ $B<p_{i}<B_{1)$ $B_1$ $B_{1}=e^{const{\sqrt {\log {p}\log {\log {p}))}}.$

Etapa 5 Folosind calcule similare cu pașii 2 și 3, găsiți logaritmii discreti ai . $\log _{a}{p_{i)}$

Etapa 6 Determinați logaritmul discret dorit:

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

Complexitate computațională

Algoritmul lui Adleman are o estimare euristică a complexității operațiilor aritmetice, unde este o constantă. În practică, nu este suficient de eficient. $O(\exp {(c(\log {p}\log {\log {p}))^{1/2})})$ $c$

Aplicații

Problema logaritmului discret este una dintre principalele probleme pe care se bazează criptografia cu cheie publică .

Logaritm discret

Logaritmul discret (DLOG) este problema inversării unei funcții într-un grup multiplicativ finit . $g^{x}$ $G$

Cel mai adesea, problema logaritmului discret este considerată în grupul multiplicativ al unui inel rezidual sau al unui câmp finit , precum și în grupul de puncte ale unei curbe eliptice peste un câmp finit. Algoritmii eficienți pentru rezolvarea problemei logaritmului discret sunt în general necunoscuți.

Pentru g și a dat, soluția x a ecuației se numește logaritmul discret al elementului a în baza g . În cazul în care G este grupul multiplicativ al inelului de reziduuri modulo m , soluția se mai numește și indicele numărului a față de baza g . Un indice de la a la baza g este garantat să existe dacă g este o rădăcină primitivă modulo m . $g^{x}=a$

Criptografia cu cheie publică

Sistem criptografic cu cheie publică (sau criptare asimetrică , cifru asimetric ) - un sistem de criptare și/sau semnătură electronică (ES) în care cheia publică este transmisă pe un canal deschis (adică nesecurizat, observabil) și este utilizată pentru a verifica ES și pentru mesajele de criptare. Pentru a genera un ES și pentru a decripta mesajul, se folosește o cheie privată [2] . Sistemele criptografice cu cheie publică sunt acum utilizate pe scară largă în diferite protocoale de rețea , în special protocoalele TLS și predecesorul său SSL (subiacent HTTPS ), SSH . De asemenea, utilizate în PGP , S/MIME Schemele criptografice clasice bazate pe acesta sunt schema de generare a cheilor partajate Diffie-Hellman, schema de semnătură electronică ElGamal, criptosistemul Massey-Omura pentru transmiterea mesajelor. Puterea lor criptografică se bazează pe complexitatea computațională presupusă mare a inversării funcției exponențiale .

Protocolul Diffie-Hellman

Protocolul Diffie-Hellman ( ing. Diffie-Hellman , DH ) este un protocol criptografic care permite două sau mai multe părți să obțină o cheie secretă partajată folosind un canal de comunicare care nu este protejat de ascultare. Cheia rezultată este utilizată pentru a cripta schimburile ulterioare folosind algoritmi de criptare simetrică .

Schema de distribuție a cheilor publice propusă de Diffie și Hellman a făcut o adevărată revoluție în lumea criptării, deoarece a eliminat principala problemă a criptografiei clasice - problema distribuției cheilor.

În forma sa pură, algoritmul Diffie-Hellman este vulnerabil la modificarea datelor în canalul de comunicare, inclusiv la atacul „ Man in the middle ”, astfel încât schemele care îl folosesc folosesc metode suplimentare de autentificare unidirecțională sau bidirecțională.

Schema lui ElGamal

Schema Elgamal este un criptosistem cu cheie publică bazat pe dificultatea de a calcula logaritmi discreti într-un câmp finit . Criptosistemul include un algoritm de criptare și un algoritm de semnătură digitală. Schema ElGamal stă la baza fostelor standarde de semnătură digitală din Statele Unite ( DSA ) și Rusia ( GOST R 34.10-94 ).

Schema a fost propusă de Taher El-Gamal în 1985 . [3] El-Gamal a dezvoltat o variantă a algoritmului Diffie-Hellman . El a îmbunătățit sistemul Diffie-Hellman și a obținut doi algoritmi care au fost folosiți pentru criptare și pentru autentificare. Spre deosebire de RSA, algoritmul ElGamal nu a fost brevetat și, prin urmare, a devenit o alternativă mai ieftină, deoarece nu erau necesare taxe de licență. Se crede că algoritmul este acoperit de brevetul Diffie-Hellman.

Note

↑ Bukhshtab, A. A. Teoria numerelor. - M .: Educaţie, 1966. - 385 p.
↑ Bruce Schneier. Criptografia aplicată. a 2-a ed. Protocoale, algoritmi și texte sursă în limbaj C. Capitolul 2.7 Semnături digitale și criptare.
↑ Taher ElGamal. Un criptosistem cu cheie publică și o schemă de semnătură bazată pe logaritmi discreti // Tranzacții IEEE pe teoria informației : jurnal. - 1985. - Vol. 31 , nr. 4 . - P. 469-472 . - doi : 10.1109/TIT.1985.1057074 .

Literatură

Leonard M. Adleman, Jonathan Demarrais. Un algoritm subexponențial pentru logaritmi discreti peste toate câmpurile finite // Matematica calculului. — 1993.
Vasilenko O.N. Algoritmi teoretici de numere în criptografie . - 2003. (Rusă) (link inaccesibil)
Coppersmith D. Evaluarea rapidă a logaritmilor discreti în câmpurile caracteristicii doi . — 1984.