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

Приведённая система вычетов по модулю 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 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 алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.

• Leonard M. Adleman, Jonathan Demarrais. 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.