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

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

Математический аппарат

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

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

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

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

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

Формулировка задачи

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

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

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

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

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

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

Описание алгоритма

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

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

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

$\omega =|T|.$

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

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

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

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

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

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

где ${\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$ и повторим этапы 3 и 4. После чего установим $z=z+1$ и повторим этапы 3 и 4. Повторяем до тех пор, пока $z\leqslant \omega +1.$ Таким образом мы получим множества $r_{i}$, $s_{i}$ и $v_{i}$ для $1\leqslant i\leqslant \omega +1.$

5 этап. Вычислим $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 этап. Вычислим число $l$ такое, что

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

7 этап. Если НОД$(l,p^{n}-1)\neq 1,$ то перейдём к этапу 3 и подберем новые множества $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 этап. Вычислим искомое число $x$

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

Другая версия алгоритма

Исходные данные

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

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

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

Описание алгоритма

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

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

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

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

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

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

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

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

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

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

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

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

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

Вычислительная сложность

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

Приложения

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

Дискретное логарифмирование

Основная статья: Дискретное логарифмирование

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

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

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

Криптография с открытым ключом

Основная статья: Криптография с открытым ключом

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

Протокол Диффи — Хеллмана

Основная статья: Протокол Диффи — Хеллмана

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

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

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

Схема Эль-Гамаля

Основная статья: Схема Эль-Гамаля

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

Схема была предложена Тахером Эль-Гамалем в 1985 году. Эль-Гамаль разработал один из вариантов алгоритма Диффи — Хеллмана. Он усовершенствовал систему Диффи — Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от 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.