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

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