Русская Википедия:Алгоритм Адлемана
Алгорим Адлемена — первый субэкспоненциальный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Алгоритм был предложен Леонардом Макс Адлеманом (англ. Leonard Adleman — Эйдлмен) в 1979 году. Леонард Макс Адлеман (Шаблон:Lang-en — Эйдлмен; род. 31 декабря 1945) — американский учёный-теоретик в области компьютерных наук, профессор компьютерных наук и молекулярной биологии в Университете Южной Калифорнии. Он известен как соавтор системы шифрования RSA (Rivest — Shamir — Adleman, 1977 год) и ДНК-вычислений. RSA широко используется в приложениях компьютерной безопасности, включая протокол HTTPS.
Математический аппарат
Приведённая система вычетов по модулю m — множество всех чисел полной системы вычетов по модулю m, взаимно простых с m. Приведённая система вычетов по модулю m состоит из φ(m) чисел, где φ(·) — функция Эйлера. Любые φ(m) попарно несравнимых по модулю m и взаимно простых с этим модулем чисел представляют собой приведенную систему вычетов. В качестве приведённой системы вычетов по модулю m обычно берутся взаимно простые с m числа от 1 до <math>m-1</math>. Если <math>(a,m)=1</math> и x пробегает приведенную систему вычетов по модулю m, то ax также принимает значения, образующие приведенную систему вычетов по этому модулю[1].
Приведённая система вычетов с умножением по модулю m образует группу, называемую мультипликативной группой или группой обратимых элементов кольца вычетов по модулю m, которая обозначается <math>\mathbb{Z}_m^{\times}</math> или <math>U(\mathbb{Z}_m)</math>.
Факторизация многочлена — представление данного многочлена в виде произведения многочленов меньших степеней.
Основная теорема алгебры утверждает, что каждый многочлен над полем комплексных чисел представим в виде произведения линейных многочленов, причем единственным образом с точностью до постоянного множителя и порядка следования сомножителей.
Противоположностью факторизации полиномов является их расширение, перемножение полиномиальных множителей для получения «расширенного» многочлена, записанного в виде суммы слагаемых.
Формулировка задачи
Пусть заданы полиномы <math>\alpha, \beta, f\in GF(p^n),p\leqslant n</math> такие, что
- <math>f</math> — неприводимый нормированный многочлен степени <math>n,</math>
- <math>\alpha</math> — генератор мультипликативной группы степени меньше <math>n,</math>
- <math>\beta\not\equiv0\pmod f.</math>
Необходимо найти (если такое существует) натуральное число <math>x</math>, удовлетворяющее сравнению
- <math>\alpha^x\equiv \beta\pmod{f}.</math>
Описание алгоритма
1 этап. Положим
- <math>m=\left\lceil\sqrt{\frac{n\log n}{\log p}}\right\rceil.</math>
2 этап. Найдем множество <math>T</math> неприводимых нормированных многочленов <math>f_i\in GF(p^n)</math> степени не выше <math>m</math> и пронумеруем их числами от <math>1</math> до <math>\omega,</math> где
- <math>\omega=|T|.</math>
3 этап. Положим <math>z=1.</math> Случайным образом выберем числа <math>r</math> и <math>s</math> такие, что
- <math>0\leqslant r,s < p^n-1,</math>
и вычислим полином <math>\gamma</math> такой, что
- <math>\gamma\equiv\alpha^r\beta^s\pmod{f}.</math>
4 этап. Если полученный многочлен является произведением всех неприводимых полиномов <math>f_i</math> из множества <math>T,</math> то есть
- <math>\gamma=\tilde{\gamma} \prod^\omega_{i=1}{f_i^{e_i}},</math>
где <math>\tilde{\gamma}</math> — старший коэффициент <math>\gamma</math> (для факторизации унитарных многочленов над конечным полем можно воспользоваться, например, алгоритмом Берлекэмпа), то положим <math>r_z=r,</math> <math>s_z=s,</math><math>v_z=\left \langle e_1, e_2, \dots , e_{\omega+1} \right \rangle.</math> В противном случае выберем другие случайные <math>r</math> и <math>s</math> и повторим этапы 3 и 4. После чего установим <math>z=z+1</math> и повторим этапы 3 и 4. Повторяем до тех пор, пока <math>z\leqslant\omega+1.</math> Таким образом мы получим множества <math>r_i</math>, <math>s_i</math> и <math>v_i</math> для <math>1\leqslant i\leqslant\omega+1.</math>
5 этап. Вычислим <math>a_1,a_2,\dots,a_{\omega+1}</math> такие, что НОД<math>(a_1,a_2,\dots,a_{\omega+1}) = 1</math> и
- <math>\sum\limits^{\omega+1}_{i=1} {a_iv_i}\equiv\left\langle 0,0,\dots,0\right\rangle\pmod{p^n-1}.</math>
6 этап. Вычислим число <math>l</math> такое, что
- <math>l=\sum_{i=1}^{\omega+1}s_ia_i.</math>
7 этап. Если НОД<math>(l,p^n-1)\ne1,</math> то перейдем к этапу 3 и подберем новые множества <math>r_i</math>, <math>s_i</math> и <math>v_i</math> для <math>1\leqslant i\leqslant\omega+1.</math> В противном случае вычислим числа <math>k,y</math> и полином <math>s</math> такие, что
- <math>k=\sum_{i=1}^{\omega+1}r_ia_i,</math>
- <math>s\equiv\alpha^k\beta^l\pmod f,</math>
- <math>\alpha^{y\frac{p^n-1}{p-1}}\equiv s\pmod f.</math>
8 этап. Вычислим искомое число <math>x</math>
- <math>x\equiv\frac{y\frac{p^n-1}{p-1}-k}{l}\pmod {p^n-1}.</math>
Другая версия алгоритма
Исходные данные
Пусть задано сравнение Шаблон:Формула
Необходимо найти натуральное число x, удовлетворяющее сравнению (1).
Описание алгоритма
1 этап. Сформировать факторную базу, состоящую из всех простых чисел q: Шаблон:Формула}}</math>}}
2 этап. С помощью перебора найти натуральные числа <math>r_i</math> такие, что Шаблон:Формула\pmod{p},</math>}}
то есть <math>a^{r_i}\mod{p}</math> раскладывается по факторной базе. Отсюда следует, что
3 этап. Набрав достаточно много соотношений (2), решить получившуюся систему линейных уравнений относительно неизвестных дискретных логарифмов элементов факторной базы (<math>\log_a{q}</math>).
4 этап. С помощью некоторого перебора найти одно значение r, для которого Шаблон:Формула
где <math>p_1,...,p_k\mod{p}</math> — простые числа «средней» величины, то есть <math>B<p_i<B_1</math>, где <math>B_1</math> — также некоторая субэкспоненциальная граница, <math>B_1 = e^{const\sqrt{\log{p}\log{\log{p}}}}.</math>
5 этап. С помощью вычислений, аналогичных этапам 2 и 3 найти дискретные логарифмы <math>\log_a{p_i}</math>.
6 этап. Определить искомый дискретный логарифм:
Вычислительная сложность
Алгоритм Адлемана имеет эвристическую оценку сложности <math>O(\exp{(c(\log{p}\log{\log{p}})^{1/2})})</math> арифметических операций, где <math>c</math> — некоторая константа. На практике он недостаточно эффективен.
Приложения
Задача дискретного логарифмирования является одной из основных задач, на которых базируется криптография с открытым ключом.
Дискретное логарифмирование
Дискретное логарифмирование (DLOG) — задача обращения функции <math>g^x</math> в некоторой конечной мультипликативной группе <math>G</math>.
Наиболее часто задачу дискретного логарифмирования рассматривают в мультипликативной группе кольца вычетов или конечного поля, а также в группе точек эллиптической кривой над конечным полем. Эффективные алгоритмы для решения задачи дискретного логарифмирования в общем случае неизвестны.
Для заданных g и a решение x уравнения <math>g^x = a</math> называется дискретным логарифмом элемента a по основанию g. В случае, когда G является мультипликативной группой кольца вычетов по модулю m, решение называют также индексом числа a по основанию g. Индекс числа a по основанию g гарантированно существует, если g является первообразным корнем по модулю m.
Криптография с открытым ключом
Криптографическая система с открытым ключом (или асимметричное шифрование, асимметричный шифр) — система шифрования и/или электронной подписи (ЭП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу и используется для проверки ЭП и для шифрования сообщения. Для генерации ЭП и для расшифровки сообщения используется закрытый ключ[2]. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH. Также используется в PGP, S/MIME.Классическими криптографическими схемами на её основе являются схема выработки общего ключа Диффи-Хеллмана, схема электронной подписи Эль-Гамаля, криптосистема Мэсси-Омуры для передачи сообщений. Их криптостойкость основывается на предположительно высокой вычислительной сложности обращения показательной функции.
Протокол Диффи — Хеллмана
Протокол Ди́ффи-Хе́ллмана (Шаблон:Lang-en, DH) — криптографический протокол, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищенный от прослушивания канал связи. Полученный ключ используется для шифрования дальнейшего обмена с помощью алгоритмов симметричного шифрования.
Схема открытого распределения ключей, предложенная Диффи и Хеллманом, произвела настоящую революцию в мире шифрования, так как снимала основную проблему классической криптографии — проблему распределения ключей.
В чистом виде алгоритм Диффи-Хеллмана уязвим для модификации данных в канале связи, в том числе для атаки «Человек посередине», поэтому схемы с его использованием применяют дополнительные методы односторонней или двусторонней аутентификации.
Схема Эль-Гамаля
Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).
Схема была предложена Тахером Эль-Гамалем в 1985 году.[3] Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.
Примечания
Литература
- ↑ Бухштаб, А. А. Теория чисел. — М.: Просвещение, 1966. — 385 с.
- ↑ Брюс Шнайер. Прикладная криптография. 2-е изд. Протоколы, алгоритмы и исходные тексты на языке Си. Глава 2.7 Цифровые подписи и шифрование.
- ↑ Шаблон:Статья
