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

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

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

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

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

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

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

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

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

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

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

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

$\beta \equiv ̸0(\mathrm{mod}f).$

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

${\alpha }^x\equiv \beta (\mathrm{mod}f).$

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

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

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

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

$\omega =|T|.$

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

$0⩽r,s<p^n-1,$

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

$\gamma \equiv {\alpha }^r{\beta }^s(\mathrm{mod}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=⟨e_1,e_2,\dots ,e_{\omega +1}⟩.$ В противном случае выберем другие случайные $r$ и $s$ и повторим этапы 3 и 4. После чего установим $z=z+1$ и повторим этапы 3 и 4. Повторяем до тех пор, пока $z⩽\omega +1.$ Таким образом мы получим множества $r_i$, $s_i$ и $v_i$ для $1⩽i⩽\omega +1.$

5 этап. Вычислим $a_1,a_2,\dots ,a_{\omega +1}$ такие, что НОД$(a_1,a_2,\dots ,a_{\omega +1})=1$ и

$\sum _{i=1}^{\omega +1}{a}_i{v}_i\equiv ⟨0,0,\dots ,0⟩(\mathrm{mod}{p}^n-1).$

6 этап. Вычислим число $l$ такое, что

$l=\sum _{i=1}^{\omega +1}{s}_i{a}_i.$

7 этап. Если НОД$(l,p^n-1)\ne 1,$ то перейдём к этапу 3 и подберем новые множества $r_i$, $s_i$ и $v_i$ для $1⩽i⩽\omega +1.$ В противном случае вычислим числа $k,y$ и полином $s$ такие, что

$k=\sum _{i=1}^{\omega +1}{r}_i{a}_i,$

$s\equiv {\alpha }^k{\beta }^l(\mathrm{mod}f),$

${\alpha }^{y\frac{p^n-1}{p-1}}\equiv s(\mathrm{mod}f).$

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

$x\equiv \frac{y\frac{p^n-1}{p-1}-k}{l}(\mathrm{mod}{p}^n-1).$

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

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

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

Шаблон:EF

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

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

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

2 этап. С помощью перебора найти натуральные числа $r_i$ такие, что Шаблон:EF

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

Шаблон:EF

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

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

где $p_1,...,p_{k}modp$ — простые числа «средней» величины, то есть $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 этап. Определить искомый дискретный логарифм: Шаблон:EF

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

• Шаблон:Статья
• Шаблон:СтатьяШаблон:Недоступная ссылка
• Шаблон:Статья