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

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

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

Приведённая система вычетов по модулю m — множество всех чисел полной системы вычетов по модулю m, взаимно простых с m. Приведённая система вычетов по модулю m состоит из φ(m) чисел, где φ(·) — функция Эйлера. Любые φ(m) попарно несравнимых по модулю m и взаимно простых с этим модулем чисел представляют собой приведенную систему вычетов. В качестве приведённой системы вычетов по модулю m обычно берутся взаимно простые с m числа от 1 до . Если и x пробегает приведенную систему вычетов по модулю m, то ax также принимает значения, образующие приведенную систему вычетов по этому модулю[1].

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

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

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

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

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

Пусть заданы полиномы такие, что

 — неприводимый нормированный многочлен степени
 — генератор мультипликативной группы степени меньше

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

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

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

2 этап. Найдем множество неприводимых нормированных многочленов степени не выше и пронумеруем их числами от до где

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

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

4 этап. Если полученный многочлен является произведением всех неприводимых полиномов из множества то есть

где  — старший коэффициент (для факторизации унитарных многочленов над конечным полем можно воспользоваться, например, алгоритмом Берлекэмпа), то положим В противном случае выберем другие случайные и и повторим этапы 3 и 4. После чего установим и повторим этапы 3 и 4. Повторяем до тех пор, пока Таким образом мы получим множества , и для

5 этап. Вычислим такие, что НОД и

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

7 этап. Если НОД то перейдем к этапу 3 и подберем новые множества , и для В противном случае вычислим числа и полином такие, что

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

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

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

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

((1))

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

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

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

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

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

((2))

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

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

где  — простые числа «средней» величины, то есть , где  — также некоторая субэкспоненциальная граница,

5 этап. С помощью вычислений, аналогичных этапам 2 и 3 найти дискретные логарифмы .

6 этап. Определить искомый дискретный логарифм:

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

Алгоритм Адлемана имеет эвристическую оценку сложности арифметических операций, где  — некоторая константа. На практике он недостаточно эффективен.

Приложения

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

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

Дискретное логарифмирование (DLOG) — задача обращения функции в некоторой конечной мультипликативной группе .

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

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

Примечания

  1. Бухштаб, А. А. Теория чисел. — М.: Просвещение, 1966. — 385 с.
  2. Брюс Шнайер. Прикладная криптография. 2-е изд. Протоколы, алгоритмы и исходные тексты на языке Си. Глава 2.7 Цифровые подписи и шифрование.
  3. Taher ElGamal. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (англ.) // IEEE Transactions on Information Theory : journal. — 1985. Vol. 31, no. 4. P. 469—472. doi:10.1109/TIT.1985.1057074.

Литература

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.