Adleman Algorithm

Adlemen Algorithm - the first sub-exponential discrete logarithm algorithm in the residue ring modulo a prime number . The algorithm was proposed by Leonard Max Adleman (born Leonard Adleman - Aidleman ) in 1979 . Leonard Max Adleman ( born Leonard Adleman - Aidleman ; born December 31, 1945 ) is an American computer science theorist , professor of computer science and molecular biology at the University of Southern California . He is known as a co-author of the RSA encryption system (Rivest - Shamir - Adleman, 1977 ) and DNA computing . RSA is widely used in computer security applications, including the HTTPS protocol .

Content

Mathematical apparatus

The reduced residue system modulo m is the set of all numbers of the complete residue system modulo m coprime to m . The reduced residue system modulo m consists of φ ( m ) numbers, where φ (·) is the Euler function . Any φ (m) pairwise incomparable modulo m and mutually prime numbers with this module represent a reduced system of residues. As a reduced system of residues modulo m, we usually take mutually prime numbers from m from 1 to $m-1$ ${\ displaystyle m-1}$ . If a $(a,m)=1$ ${\ displaystyle (a, m) = 1}$ and x runs through the reduced residue system modulo m, then ax also takes the values that form the reduced residue system modulo ^[1] .

The reduced residue system with multiplication modulo m forms a group called the multiplicative group or the group of invertible elements of the residue ring modulo m , which is denoted by $\mathbb {Z} _{m}^{\times }$ ${\ displaystyle \ mathbb {Z} _ {m} ^ {\ times}}$ or $U(\mathbb {Z} _{m})$ ${\ displaystyle U (\ mathbb {Z} _ {m})}$ .

Factorization of a polynomial is a representation of a given polynomial in the form of a product of polynomials of lower degrees.

The basic theorem of algebra states that each polynomial over the field of complex numbers can be represented as a product of linear polynomials, moreover, uniquely up to a constant factor and order of factors.

The opposite of factorization of polynomials is their extension , multiplication of polynomial factors to obtain an “extended” polynomial written as the sum of summands.

Task

Let polynomials be given $\alpha ,\beta ,f\in GF(p^{n}),p\leqslant n$ ${\ displaystyle \ alpha, \ beta, f \ in GF (p ^ {n}), p \ leqslant n}$ such that

f

{\ displaystyle f}

- irreducible normalized polynomial of degree

n,

{\ displaystyle n,}

\alpha

{\ displaystyle \ alpha}

- generator of a multiplicative group of degree less

n,

{\ displaystyle n,}

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

{\ displaystyle \ beta \ not \ equiv 0 {\ pmod {f}}.}

It is necessary to find (if such exists) a natural number $x$ ${\ displaystyle x}$ satisfying comparison

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

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

Algorithm Description

Stage 1. Put

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

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

2 stage. Find a lot $T$ ${\ displaystyle T}$ irreducible normalized polynomials $f_{i}\in GF(p^{n})$ ${\ displaystyle f_ {i} \ in GF (p ^ {n})}$ degree no higher $m$ ${\ displaystyle m}$ and number them with numbers from $one$ ${\ displaystyle 1}$ before $\omega ,$ ${\ displaystyle \ omega,}$ Where

\omega =|T|.

{\ displaystyle \ omega = | T |.}

3 stage. Put $z=1.$ ${\ displaystyle z = 1.}$ Randomly select numbers $r$ ${\ displaystyle r}$ and $s$ ${\ displaystyle s}$ such that

{\displaystyle 0\leqslant r,s<semantics><mrow class=

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

and calculate the polynomial $\gamma$ ${\ displaystyle \ gamma}$ such that

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

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

4th stage. If the polynomial obtained is the product of all irreducible polynomials $f_{i}$ ${\ displaystyle f_ {i}}$ out of many $T,$ ${\ displaystyle T,}$ i.e

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

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

Where ${\tilde {\gamma }}$ ${\ displaystyle {\ tilde {\ gamma}}}$ - senior coefficient $\gamma$ ${\ displaystyle \ gamma}$ (to factorize unitary polynomials over a finite field, you can use, for example, the Berlekamp algorithm ), then put $r_{z}=r,$ ${\ displaystyle r_ {z} = r,}$ $s_{z}=s,$ ${\ displaystyle s_ {z} = s,}$ $v_{z}=\left\langle e_{1},e_{2},\dots ,e_{\omega +1}\right\rangle .$ ${\ displaystyle v_ {z} = \ left \ langle e_ {1}, e_ {2}, \ dots, e _ {\ omega +1} \ right \ rangle.}$ Otherwise, we choose other random $r$ ${\ displaystyle r}$ and $s$ ${\ displaystyle s}$ and repeat steps 3 and 4. Then set $z=z+1$ ${\ displaystyle z = z + 1}$ and repeat steps 3 and 4. Repeat until $z\leqslant \omega +1.$ ${\ displaystyle z \ leqslant \ omega +1.}$ Thus we get the sets $r_{i}$ ${\ displaystyle r_ {i}}$ , $s_{i}$ ${\ displaystyle s_ {i}}$ and $v_{i}$ ${\ displaystyle v_ {i}}$ for $1\leqslant i\leqslant \omega +1.$ ${\ displaystyle 1 \ leqslant i \ leqslant \ omega +1.}$

5 stage. We calculate $a_{1},a_{2},\dots ,a_{\omega +1}$ ${\ displaystyle a_ {1}, a_ {2}, \ dots, a _ {\ omega +1}}$ such that GCD $(a_{1},a_{2},\dots ,a_{\omega +1})=1$ ${\ displaystyle (a_ {1}, a_ {2}, \ dots, a _ {\ omega +1}) = 1}$ and

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

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

6 stage. Calculate the number $l$ ${\ displaystyle l}$ such that

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

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

7th stage. If GCD $(l,p^{n}-1)\neq 1,$ ${\ displaystyle (l, p ^ {n} -1) \ neq 1,}$ then we go to step 3 and pick up new sets $r_{i}$ ${\ displaystyle r_ {i}}$ , $s_{i}$ ${\ displaystyle s_ {i}}$ and $v_{i}$ ${\ displaystyle v_ {i}}$ for $1\leqslant i\leqslant \omega +1.$ ${\ displaystyle 1 \ leqslant i \ leqslant \ omega +1.}$ Otherwise, calculate the numbers $k, y$ ${\ displaystyle k, y}$ and polynomial $s$ ${\ displaystyle s}$ such that

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

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

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

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

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

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

8 stage. We calculate the desired number $x$ ${\ displaystyle x}$

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

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

Another version of the algorithm

Source data

Let a comparison be given

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

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

((one))

It is necessary to find a natural number x satisfying the comparison (1).

Algorithm Description

Stage 1. Form a factor base consisting of all primes q :

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

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

2 stage. Using enumeration, find natural numbers $r_{i}$ ${\ displaystyle r_ {i}}$ such that

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

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

i.e $a^{r_{i}}\mod {p}$ ${\ displaystyle a ^ {r_ {i}} \ mod {p}}$ laid out on a factor basis. It follows that

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

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

((2))

3 stage. Having collected a lot of relations (2), solve the resulting system of linear equations for unknown discrete logarithms of the elements of the factor base ( $\log _{a}{q}$ ${\ displaystyle \ log _ {a} {q}}$ )

4th stage. Using some enumeration, find one value of r for which

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

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

Where $p_{1},...,p_{k}\mod {p}$ ${\ displaystyle p_ {1}, ..., p_ {k} \ mod {p}}$ - prime numbers of "average" size, that is $B<p_{i}<B_{1}$ ${\ displaystyle B <p_ {i} <B_ {1}}$ where $B_{1}$ ${\ displaystyle B_ {1}}$ - also some subexponential boundary, $B_{1}=e^{const{\sqrt {\log {p}\log {\log {p}}}}}.$ ${\ displaystyle B_ {1} = e ^ {const {\ sqrt {\ log {p} \ log {\ log {p}}}}}.$

5 stage. Using calculations similar to steps 2 and 3, find discrete logarithms $\log _{a}{p_{i}}$ ${\ displaystyle \ log _ {a} {p_ {i}}}$ .

6 stage. Determine the desired discrete logarithm:

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

{\ displaystyle 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}}.}

Computational complexity

Adleman's algorithm has a heuristic complexity estimate $O(\exp {(c(\log {p}\log {\log {p}})^{1/2})})$ ${\ displaystyle O (\ exp {(c (\ log {p} \ log {\ log {p}}) ^ {1/2})})}$ arithmetic operations where $c$ ${\ displaystyle c}$ Is some constant. In practice, it is not effective enough.

Applications

The discrete logarithm problem is one of the main tasks on which public key cryptography is based.

Discrete Logarithm

Discrete Logarithm (DLOG) - Function Inversion Problem $g^{x}$ ${\ displaystyle g ^ {x}}$ in some finite multiplicative group $G$ ${\ displaystyle G}$ .

Most often, the discrete logarithm problem is considered in the multiplicative group of residue rings or a finite field , as well as in the group of points of an elliptic curve above a finite field. Effective algorithms for solving the discrete logarithm problem are generally unknown.

For given g and a, the solution x of the equation $g^{x}=a$ ${\ displaystyle g ^ {x} = a}$ is called the discrete logarithm of the element a at the base g . In the case when G is a multiplicative group of the residue ring modulo m , the solution is also called the index of the number a along the base g . The base number index a is guaranteed to exist if g is a primitive root modulo m .

Public Key Cryptography

A public key cryptographic system (or asymmetric encryption , asymmetric cipher ) is an encryption and / or electronic signature (ES) system in which the public key is transmitted over an open (i.e., insecure, observable) channel and is used to verify ES and for encryption messages. To generate the electronic signature and to decrypt the message, the private key is used ^[2] . Public key cryptographic systems are now widely used in various network protocols , in particular, in the TLS protocols and its predecessor SSL (underlying HTTPS ), in SSH . Also used in PGP , S / MIME. Classical cryptographic schemes based on it are the Diffie-Hellman common key generation scheme, El-Gamal electronic signature scheme, the Massey-Omura cryptosystem for transmitting messages. Their cryptographic strength is based on the supposedly high computational complexity of the exponential function .

Diffie-Hellman Protocol

The Diffie-Hellman Protocol ( Diffie-Hellman , DH ) is a cryptographic protocol that allows two or more parties to obtain a shared secret key using an unprotected communication channel. The received key is used to encrypt further exchanges using symmetric encryption algorithms.

The open key distribution scheme proposed by Diffie and Hellman made a real revolution in the encryption world, as it removed the main problem of classical cryptography - the problem of key distribution.

In its pure form, the Diffie-Hellman algorithm is vulnerable to data modification in the communication channel, including the Man in the Middle attack, therefore, schemes using it use additional methods of one-way or two-way authentication.

El Gamal Scheme

The Elgamal scheme is an open-key cryptosystem based on the difficulty of computing discrete logarithms in a finite field . The cryptosystem includes an encryption algorithm and a digital signature algorithm. The El-Gamal scheme is the basis of the former standards of electronic digital signature in the USA ( DSA ) and Russia ( GOST R 34.10-94 ).

The scheme was proposed by Taher El-Gamal in 1985 . ^[3] El-Gamal developed one of the variants of the Diffie-Hellman algorithm . He improved the Diffie-Hellman system and obtained two algorithms that were used for encryption and for authentication. Unlike RSA, the El-Gamal algorithm was not patented and, therefore, became a cheaper alternative, since it did not require payment of license fees. It is believed that the algorithm is subject to the Diffie-Hellman patent.

Notes

↑ Buchstaff, A.A. Number Theory. - M.: Education, 1966 .-- 385 p.
↑ Bruce Schneier. Applied cryptography. 2nd ed. Protocols, algorithms and source codes in the C language. Chapter 2.7 Digital Signatures and Encryption.
↑ Taher ElGamal. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (English) // IEEE Transactions on Information Theory : journal. - 1985. - Vol. 31 , no. 4 . - P. 469-472 . - DOI : 10.1109 / TIT.1985.1057074 .

Literature

Leonard M. Adleman, Jonathan Demarrais. A subexponential algorithm for discrete logarithms over all finite fields (English) // Mathematics of computation. - 1993.
Vasilenko O.N. Number-theoretic algorithms in cryptography (Russian) . - 2003. (unavailable link)
Coppersmith D. Fast evaluation of discrete logarithms in fields of characteristic two. - 1984.

[1] Buchstaff, A.A. Number Theory. - M.: Education, 1966 .-- 385 p.

[2] Bruce Schneier. Applied cryptography. 2nd ed. Protocols, algorithms and source codes in the C language. Chapter 2.7 Digital Signatures and Encryption.

[3] Taher ElGamal. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (English) // IEEE Transactions on Information Theory : journal. - 1985. - Vol. 31 , no. 4 . - P. 469-472 . - DOI : 10.1109 / TIT.1985.1057074 .

Adleman Algorithm

Content

Mathematical apparatus

Task

Algorithm Description

Another version of the algorithm

Source data

Algorithm Description

Computational complexity

Applications

Discrete Logarithm

Public Key Cryptography

Diffie-Hellman Protocol

El Gamal Scheme

Notes

Literature

More articles: