ГлавнаяАлгорим Адлемена — первый субэкспоненциальный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Алгоритм был предложен Леонардом Макс Адлеманом (англ. Leonard Adleman — Эйдлмен) в 1979 году. Леонард Макс Адлеман (англ. Leonard Adleman — Эйдлмен; род. 31 декабря 1945) — американский учёный-теоретик в области компьютерных наук, профессор компьютерных наук и молекулярной биологии в Университете Южной Калифорнии. Он известен как соавтор системы шифрования RSA (Rivest — Shamir — Adleman, 1977 год) и ДНК-вычислений. RSA широко используется в приложениях компьютерной безопасности, включая протокол HTTPS.
Математический аппарат
Приведённая система вычетов по модулю m — множество всех чисел полной системы вычетов по модулю m, взаимно простых с m. Приведённая система вычетов по модулю m состоит из φ(m) чисел, где φ(·) — функция Эйлера. Любые φ(m) попарно несравнимых по модулю m и взаимно простых с этим модулем чисел представляют собой приведенную систему вычетов. В качестве приведённой системы вычетов по модулю m обычно берутся взаимно простые с m числа от 1 до m − 1 {displaystyle m-1} . Если ( a , m ) = 1 {displaystyle (a,m)=1} и x пробегает приведенную систему вычетов по модулю m, то ax также принимает значения, образующие приведенную систему вычетов по этому модулю.
Приведённая система вычетов с умножением по модулю m образует группу, называемую мультипликативной группой или группой обратимых элементов кольца вычетов по модулю m, которая обозначается Z m × {displaystyle mathbb {Z} _{m}^{ imes }} или U ( Z m ) {displaystyle U(mathbb {Z} _{m})} .
Факторизация многочлена — представление данного многочлена в виде произведения многочленов меньших степеней.
Основная теорема алгебры утверждает, что каждый многочлен над полем комплексных чисел представим в виде произведения линейных многочленов, причем единственным образом с точностью до постоянного множителя и порядка следования сомножителей.
Противоположностью факторизации полиномов является их расширение, перемножение полиномиальных множителей для получения «расширенного» многочлена, записанного в виде суммы слагаемых.
Формулировка задачи
Пусть заданы полиномы α , β , f ∈ G F ( p n ) , p ⩽ n {displaystyle alpha ,eta ,fin GF(p^{n}),pleqslant n} такие, что
f {displaystyle f} — неприводимый нормированный многочлен степени n , {displaystyle n,} α {displaystyle alpha } — генератор мультипликативной группы степени меньше n , {displaystyle n,} β ≢ 0 ( mod f ) . {displaystyle eta ot equiv 0{pmod {f}}.}Необходимо найти (если такое существует) натуральное число x {displaystyle x} , удовлетворяющее сравнению
α x ≡ β ( mod f ) . {displaystyle alpha ^{x}equiv eta {pmod {f}}.}Описание алгоритма
1 этап. Положим
m = ⌈ n log n log p ⌉ . {displaystyle m=leftlceil {sqrt {frac {nlog n}{log p}}} ight ceil .}2 этап. Найдем множество T {displaystyle T} неприводимых нормированных многочленов f i ∈ G F ( p n ) {displaystyle f_{i}in GF(p^{n})} степени не выше m {displaystyle m} и пронумеруем их числами от 1 {displaystyle 1} до ω , {displaystyle omega ,} где
ω = | T | . {displaystyle omega =|T|.}3 этап. Положим z = 1. {displaystyle z=1.} Случайным образом выберем числа r {displaystyle r} и s {displaystyle s} такие, что
0 ⩽ r , s < p n − 1 , {displaystyle 0leqslant r,s<p^{n}-1,}и вычислим полином γ {displaystyle gamma } такой, что
γ ≡ α r β s ( mod f ) . {displaystyle gamma equiv alpha ^{r}eta ^{s}{pmod {f}}.}4 этап. Если полученный многочлен является произведением всех неприводимых полиномов f i {displaystyle f_{i}} из множества T , {displaystyle T,} то есть
γ = γ ~ ∏ i = 1 ω f i e i , {displaystyle gamma ={ ilde {gamma }}prod _{i=1}^{omega }{f_{i}^{e_{i}}},}где γ ~ {displaystyle { ilde {gamma }}} — старший коэффициент γ {displaystyle gamma } (для факторизации унитарных многочленов над конечным полем можно воспользоваться, например, алгоритмом Берлекэмпа), то положим r z = r , {displaystyle r_{z}=r,} s z = s , {displaystyle s_{z}=s,} v z = ⟨ e 1 , e 2 , … , e ω + 1 ⟩ . {displaystyle v_{z}=leftlangle e_{1},e_{2},dots ,e_{omega +1} ight angle .} В противном случае выберем другие случайные r {displaystyle r} и s {displaystyle s} и повторим этапы 3 и 4. После чего установим z = z + 1 {displaystyle z=z+1} и повторим этапы 3 и 4. Повторяем до тех пор, пока z ⩽ ω + 1. {displaystyle zleqslant omega +1.} Таким образом мы получим множества r i {displaystyle r_{i}} , s i {displaystyle s_{i}} и v i {displaystyle v_{i}} для 1 ⩽ i ⩽ ω + 1. {displaystyle 1leqslant ileqslant omega +1.}
5 этап. Вычислим a 1 , a 2 , … , a ω + 1 {displaystyle a_{1},a_{2},dots ,a_{omega +1}} такие, что НОД ( a 1 , a 2 , … , a ω + 1 ) = 1 {displaystyle (a_{1},a_{2},dots ,a_{omega +1})=1} и
∑ i = 1 ω + 1 a i v i ≡ ⟨ 0 , 0 , … , 0 ⟩ ( mod p n − 1 ) . {displaystyle sum limits _{i=1}^{omega +1}{a_{i}v_{i}}equiv leftlangle 0,0,dots ,0 ight angle {pmod {p^{n}-1}}.}6 этап. Вычислим число l {displaystyle l} такое, что
l = ∑ i = 1 ω + 1 s i a i . {displaystyle l=sum _{i=1}^{omega +1}s_{i}a_{i}.}7 этап. Если НОД ( l , p n − 1 ) ≠ 1 , {displaystyle (l,p^{n}-1) eq 1,} то перейдем к этапу 3 и подберем новые множества r i {displaystyle r_{i}} , s i {displaystyle s_{i}} и v i {displaystyle v_{i}} для 1 ⩽ i ⩽ ω + 1. {displaystyle 1leqslant ileqslant omega +1.} В противном случае вычислим числа k , y {displaystyle k,y} и полином s {displaystyle s} такие, что
k = ∑ i = 1 ω + 1 r i a i , {displaystyle k=sum _{i=1}^{omega +1}r_{i}a_{i},} s ≡ α k β l ( mod f ) , {displaystyle sequiv alpha ^{k}eta ^{l}{pmod {f}},} α y p n − 1 p − 1 ≡ s ( mod f ) . {displaystyle alpha ^{y{frac {p^{n}-1}{p-1}}}equiv s{pmod {f}}.}8 этап. Вычислим искомое число x {displaystyle x}
x ≡ y p n − 1 p − 1 − k l ( mod p n − 1 ) . {displaystyle xequiv {frac {y{frac {p^{n}-1}{p-1}}-k}{l}}{pmod {p^{n}-1}}.}Другая версия алгоритма
Исходные данные
Пусть задано сравнение
Необходимо найти натуральное число x, удовлетворяющее сравнению (1).
Описание алгоритма
1 этап. Сформировать факторную базу, состоящую из всех простых чисел q:
2 этап. С помощью перебора найти натуральные числа r i {displaystyle r_{i}} такие, что
то есть a r i mod p {displaystyle a^{r_{i}}mod {p}} раскладывается по факторной базе. Отсюда следует, что
3 этап. Набрав достаточно много соотношений (2), решить получившуюся систему линейных уравнений относительно неизвестных дискретных логарифмов элементов факторной базы ( log a q {displaystyle log _{a}{q}} ).
4 этап. С помощью некоторого перебора найти одно значение r, для которого
где p 1 , . . . , p k mod p {displaystyle p_{1},...,p_{k}mod {p}} — простые числа «средней» величины, то есть B < p i < B 1 {displaystyle B<p_{i}<B_{1}} , где B 1 {displaystyle B_{1}} — также некоторая субэкспоненциальная граница, B 1 = e c o n s t log p log log p . {displaystyle B_{1}=e^{const{sqrt {log {p}log {log {p}}}}}.}
5 этап. С помощью вычислений, аналогичных этапам 2 и 3 найти дискретные логарифмы log a p i {displaystyle log _{a}{p_{i}}} .
6 этап. Определить искомый дискретный логарифм:
Вычислительная сложность
Алгоритм Адлемана имеет эвристическую оценку сложности O ( exp ( c ( log p log log p ) 1 / 2 ) ) {displaystyle O(exp {(c(log {p}log {log {p}})^{1/2})})} арифметических операций, где c {displaystyle c} — некоторая константа. На практике он недостаточно эффективен.
Приложения
Задача дискретного логарифмирования является одной из основных задач, на которых базируется криптография с открытым ключом.
Дискретное логарифмирование
Дискретное логарифмирование (DLOG) — задача обращения функции g x {displaystyle g^{x}} в некоторой конечной мультипликативной группе G {displaystyle G} .
Наиболее часто задачу дискретного логарифмирования рассматривают в мультипликативной группе кольца вычетов или конечного поля, а также в группе точек эллиптической кривой над конечным полем. Эффективные алгоритмы для решения задачи дискретного логарифмирования в общем случае неизвестны.
Для заданных g и a решение x уравнения g x = a {displaystyle g^{x}=a} называется дискретным логарифмом элемента a по основанию g. В случае, когда G является мультипликативной группой кольца вычетов по модулю m, решение называют также индексом числа a по основанию g. Индекс числа a по основанию g гарантированно существует, если g является первообразным корнем по модулю m.
Криптография с открытым ключом
Криптографическая система с открытым ключом (или асимметричное шифрование, асимметричный шифр) — система шифрования и/или электронной подписи (ЭП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу и используется для проверки ЭП и для шифрования сообщения. Для генерации ЭП и для расшифровки сообщения используется закрытый ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH. Также используется в PGP, S/MIME.Классическими криптографическими схемами на её основе являются схема выработки общего ключа Диффи-Хеллмана, схема электронной подписи Эль-Гамаля, криптосистема Мэсси-Омуры для передачи сообщений. Их криптостойкость основывается на предположительно высокой вычислительной сложности обращения показательной функции.
Протокол Диффи — Хеллмана
Протокол Диффи-Хеллмана (англ. Diffie-Hellman, DH) — криптографический протокол, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищенный от прослушивания канал связи. Полученный ключ используется для шифрования дальнейшего обмена с помощью алгоритмов симметричного шифрования.
Схема открытого распределения ключей, предложенная Диффи и Хеллманом, произвела настоящую революцию в мире шифрования, так как снимала основную проблему классической криптографии — проблему распределения ключей.
В чистом виде алгоритм Диффи-Хеллмана уязвим для модификации данных в канале связи, в том числе для атаки «Человек посередине», поэтому схемы с его использованием применяют дополнительные методы односторонней или двусторонней аутентификации.
Схема Эль-Гамаля
Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).
Схема была предложена Тахером Эль-Гамалем в 1985 году. Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.