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

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

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


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

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


 Пусть заданы полиномы α,β,fGF(pn),pn такие, что

f — неприводимый нормированный многочлен степени n,
α — генератор мультипликативной группы степени меньше n,
β0(modf).
  Необходимо найти (если такое существует) натуральное число x, удовлетворяющее сравнению

αxβ(modf).

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


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

m=nlognlogp.
2 этап. Найдем множество T неприводимых нормированных многочленов fiGF(pn) степени не выше m и пронумеруем их числами от 1 до ω, где

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

0r,s<pn1,
  и вычислим полином γ такой, что

γαrβs(modf).
4 этап. Если полученный многочлен является произведением всех неприводимых полиномов fi из множества T, то есть

γ=γ~i=1ωfiei,
  где γ~ — старший коэффициент γ (для факторизации унитарных многочленов над конечным полем можно воспользоваться, например, алгоритмом Берлекэмпа), то положим rz=r, sz=s,vz=e1,e2,,eω+1. В противном случае выберем другие случайные r и s и повторим этапы 3 и 4. После чего установим z=z+1 и повторим этапы 3 и 4. Повторяем до тех пор, пока zω+1. Таким образом мы получим множества ri, si и vi для 1iω+1.
5 этап. Вычислим a1,a2,,aω+1 такие, что НОД(a1,a2,,aω+1)=1 и

ω+1i=1aivi0,0,,0\pmodpn1.
6 этап. Вычислим число l такое, что

l=i=1ω+1siai.
7 этап. Если НОД(l,pn1)1, то перейдем к этапу 3 и подберем новые множества ri, si и vi для 1iω+1. В противном случае вычислим числа k,y и полином s такие, что

k=i=1ω+1riai,
sαkβl(modf),
\alpha^y\frac{p^n-1p-1\equiv s\pmod f.
8 этап. Вычислим искомое число x

x\equiv\frac{y\frac{p^n-1p-1-kl\pmod p^n-1.

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


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


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

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


1 этап. Сформировать факторную базу, состоящую из всех простых чисел q: \}\}\}\}
2 этап. С помощью перебора найти натуральные числа ri такие, что \{}pmod\{p\},\}\}
 то есть air\modp раскладывается по факторной базе. Отсюда следует, что
3 этап. Набрав достаточно много соотношений (2), решить получившуюся систему линейных уравнений относительно неизвестных дискретных логарифмов элементов факторной базы (logaq).
4 этап. С помощью некоторого перебора найти одно начение r, для которого
 где p1,...,pk\modp — простые числа «средней» величины, то есть $B5 этап. С помощью вычислений, аналогичных этапам 2 и 3 найти дискретные логарифмы logapi.
6 этап. Определить искомый дискретный логарифм:

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


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

Приложения


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

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


Дискретное логарифмирование (DLOG) — задача обращения функции gx в некоторой конечной мультипликативной группе G.
 Наиболее часто задачу дискретного логарифмирования рассматривают в мультипликативной группе кольца вычетов или конечного поля, а также в группе точек эллиптической кривой над конечным полем. Эффективные алгоритмы для решения задачи дискретного логарифмирования в общем случае неизвестны.
 Для заданных g и a решение x уравнения gx=a называется дискретным логарифмом элемента a по основанию g. В случае, когда G является мультипликативной группой кольца вычетов по модулю m, решение называют также индексом числа a по основанию g. Индекс числа a по основанию g гарантированно существует, если g является первообразным корнем по модулю m.

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


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

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


Протокол Диффи-Хеллмана (, DH) — криптографический протокол, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищенный от прослушивания канал связи. Полученный ключ используется для шифрования дальнейшего обмена с помощью алгоритмов симметричного шифрования.
 Схема открытого распределения ключей, предложенная Диффи и Хеллманом, произвела настоящую революцию в мире шифрования, так как снимала основную проблему классической криптографии — проблему распределения ключей.
 В чистом виде алгоритм Диффи-Хеллмана уязвим для модификации данных в канале связи, в том числе для атаки «Человек посередине», поэтому схемы с его использованием применяют дополнительные методы односторонней или двусторонней аутентификации.

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


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