Алгорим Адлемана — первый субэкспоненциальный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа . Алгоритм был предложен Леонардом Максом Адлеманом (англ. 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 также принимает значения, образующие приведённую систему вычетов по этому модулю .

Приведённая система вычетов с умножением по модулю 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}}.}$

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

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

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

Необходимо найти натуральное число 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}}$ раскладывается по факторной базе. Отсюда следует, что

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 .

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

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

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

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

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

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

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

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

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

Примечания

Литература

• Adleman L. M., Demarrais J. (англ.) // Mathematics of computation. — 1993.
• Василенко О.Н. (рус.) . — 2003. (недоступная ссылка)
• Coppersmith D. Fast evaluation of discrete logarithms in fields of characteristic two (англ.) . — 1984.