Алгоритм Адлемана

Алгоритм Адлемана — первый субэкспоненциальный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Алгоритм был предложен Леонардом Максом Адлеманом (англ. Leonard Adleman — Эйдлмен) в 1979 году. Леонард Макс Адлеман (англ. Leonard Adleman — Эйдлмен; род. 31 декабря 1945) — американский учёный-теоретик в области компьютерных наук, профессор компьютерных наук и молекулярной биологии в Университете Южной Калифорнии. Он известен как соавтор системы шифрования RSA (Rivest — Shamir — Adleman, 1977 год) и ДНК-вычислений. RSA широко используется в приложениях компьютерной безопасности, включая протокол HTTPS.

Приведённая система вычетов по модулю m — множество всех чисел полной системы вычетов по модулю m, взаимно простых с m. Приведённая система вычетов по модулю m состоит из φ(m) чисел, где φ(·) — функция Эйлера. Любые φ(m) попарно несравнимых по модулю m и взаимно простых с этим модулем чисел представляют собой приведённую систему вычетов. В качестве приведённой системы вычетов по модулю m обычно берутся взаимно простые с m числа от 1 до ${\displaystyle m-1}$. Если ${\displaystyle (a,m)=1}$ и x пробегает приведенную систему вычетов по модулю m, то ax также принимает значения, образующие приведённую систему вычетов по этому модулю^[1].

Приведённая система вычетов с умножением по модулю m образует группу, называемую мультипликативной группой или группой обратимых элементов кольца вычетов по модулю m, которая обозначается ${\displaystyle \mathbb {Z} _{m}^{\times }}$ или ${\displaystyle U(\mathbb {Z} _{m})}$.

Факторизация многочлена — представление данного многочлена в виде произведения многочленов меньших степеней.

Основная теорема алгебры утверждает, что каждый многочлен над полем комплексных чисел представим в виде произведения линейных многочленов, причем единственным образом с точностью до постоянного множителя и порядка следования сомножителей.

Противоположностью факторизации полиномов является их расширение, перемножение полиномиальных множителей для получения «расширенного» многочлена, записанного в виде суммы слагаемых.

Пусть заданы полиномы ${\displaystyle \alpha ,\beta ,f\in GF(p^{n}),p\leqslant n}$ такие, что

${\displaystyle f}$ — неприводимый нормированный многочлен степени ${\displaystyle n,}$

${\displaystyle \alpha }$ — генератор мультипликативной группы степени меньше ${\displaystyle n,}$

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

Необходимо найти (если такое существует) натуральное число ${\displaystyle x}$, удовлетворяющее сравнению

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

1 этап. Положим

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

2 этап. Найдем множество ${\displaystyle T}$ неприводимых нормированных многочленов ${\displaystyle f_{i}\in GF(p^{n})}$ степени не выше ${\displaystyle m}$ и пронумеруем их числами от ${\displaystyle 1}$ до ${\displaystyle \omega ,}$ где

${\displaystyle \omega =|T|.}$

3 этап. Положим ${\displaystyle z=1.}$ Случайным образом выберем числа ${\displaystyle r}$ и ${\displaystyle s}$ такие, что

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

и вычислим полином ${\displaystyle \gamma }$ такой, что

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

4 этап. Если полученный многочлен является произведением всех неприводимых полиномов ${\displaystyle f_{i}}$ из множества ${\displaystyle T,}$ то есть

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

где ${\displaystyle {\tilde {\gamma }}}$ — старший коэффициент ${\displaystyle \gamma }$ (для факторизации унитарных многочленов над конечным полем можно воспользоваться, например, алгоритмом Берлекэмпа), то положим ${\displaystyle r_{z}=r,}$ ${\displaystyle s_{z}=s,}$${\displaystyle v_{z}=\left\langle e_{1},e_{2},\dots ,e_{\omega +1}\right\rangle .}$ В противном случае выберем другие случайные ${\displaystyle r}$ и ${\displaystyle s}$ и повторим этапы 3 и 4. После чего установим ${\displaystyle z=z+1}$ и повторим этапы 3 и 4. Повторяем до тех пор, пока ${\displaystyle z\leqslant \omega +1.}$ Таким образом мы получим множества ${\displaystyle r_{i}}$, ${\displaystyle s_{i}}$ и ${\displaystyle v_{i}}$ для ${\displaystyle 1\leqslant i\leqslant \omega +1.}$

5 этап. Вычислим ${\displaystyle a_{1},a_{2},\dots ,a_{\omega +1}}$ такие, что НОД${\displaystyle (a_{1},a_{2},\dots ,a_{\omega +1})=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 этап. Вычислим число ${\displaystyle l}$ такое, что

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

7 этап. Если НОД${\displaystyle (l,p^{n}-1)\neq 1,}$ то перейдём к этапу 3 и подберем новые множества ${\displaystyle r_{i}}$, ${\displaystyle s_{i}}$ и ${\displaystyle v_{i}}$ для ${\displaystyle 1\leqslant i\leqslant \omega +1.}$ В противном случае вычислим числа ${\displaystyle k,y}$ и полином ${\displaystyle s}$ такие, что

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

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

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

8 этап. Вычислим искомое число ${\displaystyle x}$

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

Пусть задано сравнение

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

(1)

Необходимо найти натуральное число x, удовлетворяющее сравнению (1).

1 этап. Сформировать факторную базу, состоящую из всех простых чисел q:

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

2 этап. С помощью перебора найти натуральные числа ${\displaystyle r_{i}}$ такие, что

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

то есть ${\displaystyle a^{r_{i}}\mod {p}}$ раскладывается по факторной базе. Отсюда следует, что

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

(2)

3 этап. Набрав достаточно много соотношений (2), решить получившуюся систему линейных уравнений относительно неизвестных дискретных логарифмов элементов факторной базы (${\displaystyle \log _{a}{q}}$).

4 этап. С помощью некоторого перебора найти одно значение r, для которого

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

где ${\displaystyle p_{1},...,p_{k}\mod {p}}$ — простые числа «средней» величины, то есть ${\displaystyle B<p_{i}<B_{1}}$, где ${\displaystyle B_{1}}$ — также некоторая субэкспоненциальная граница, ${\displaystyle B_{1}=e^{{\text{const}}{\sqrt {\log {p}\log {\log {p}}}}}.}$

5 этап. С помощью вычислений, аналогичных этапам 2 и 3 найти дискретные логарифмы ${\displaystyle \log _{a}{p_{i}}}$.

6 этап. Определить искомый дискретный логарифм:

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

Алгоритм Адлемана имеет эвристическую оценку сложности ${\displaystyle O(\exp {(c(\log {p}\log {\log {p}})^{1/2})})}$ арифметических операций, где ${\displaystyle c}$ — некоторая константа. На практике он недостаточно эффективен.

Задача дискретного логарифмирования является одной из основных задач, на которых базируется криптография с открытым ключом.

Дискретное логарифмирование (DLOG) — задача обращения функции ${\displaystyle g^{x}}$ в некоторой конечной мультипликативной группе ${\displaystyle G}$.

Наиболее часто задачу дискретного логарифмирования рассматривают в мультипликативной группе кольца вычетов или конечного поля, а также в группе точек эллиптической кривой над конечным полем. Эффективные алгоритмы для решения задачи дискретного логарифмирования в общем случае неизвестны.

Для заданных g и a решение x уравнения ${\displaystyle g^{x}=a}$ называется дискретным логарифмом элемента a по основанию g. В случае, когда G является мультипликативной группой кольца вычетов по модулю m, решение называют также индексом числа a по основанию g. Индекс числа a по основанию g гарантированно существует, если g является первообразным корнем по модулю m.

Криптографическая система с открытым ключом (или асимметричное шифрование, асимметричный шифр) — система шифрования и/или электронной подписи (ЭП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу и используется для проверки ЭП и для шифрования сообщения. Для генерации ЭП и для расшифровки сообщения используется закрытый ключ^[2]. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH. Также используется в PGP, S/MIME.Классическими криптографическими схемами на её основе являются схема выработки общего ключа Диффи-Хеллмана, схема электронной подписи Эль-Гамаля, криптосистема Мэсси-Омуры для передачи сообщений. Их криптостойкость основывается на предположительно высокой вычислительной сложности обращения показательной функции.

Протокол Ди́ффи — Хе́ллмана (англ. Diffie-Hellman, DH) — криптографический протокол, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищенный от прослушивания канал связи. Полученный ключ используется для шифрования дальнейшего обмена с помощью алгоритмов симметричного шифрования.

Схема открытого распределения ключей, предложенная Диффи и Хеллманом, произвела настоящую революцию в мире шифрования, так как снимала основную проблему классической криптографии — проблему распределения ключей.

В чистом виде алгоритм Диффи — Хеллмана уязвим для модификации данных в канале связи, в том числе для атаки «Человек посередине», поэтому схемы с его использованием применяют дополнительные методы односторонней или двусторонней аутентификации.

Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).

Схема была предложена Тахером Эль-Гамалем в 1985 году^[3]. Эль-Гамаль разработал один из вариантов алгоритма Диффи — Хеллмана. Он усовершенствовал систему Диффи — Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и поэтому стал более дешёвой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи — Хеллмана.

• Adleman L. M., Demarrais J. A subexponential algorithm for discrete logarithms over all finite fields (англ.) // Mathematics of computation. — 1993.
• Василенко О.Н. Теоретико-числовые алгоритмы в криптографии (рус.). — 2003. (недоступная ссылка)
• Coppersmith D. Fast evaluation of discrete logarithms in fields of characteristic two (англ.). — 1984.