Вычисление дискретного логарифма. Дайджест последних достижений в области криптографии
Пример 13.13
Для какого значения n группа имеет примитивные корни: 17, 20, 38 и 50 ?
Решение
a. 
имеет примитивные корни, потому что 17
- простое число (p t
, где t
равно 1
).
b. 
не имеет никаких примитивных корней.
c. 
и 19
- простое число.
d. 
имеет первообразные
корни, потому что 
, а 5
- простое число.
Если группа имеет примитивный корень, то обычно она имеет несколько таких корней. Число примитивных корней может быть вычислено как - . Например, число примитивных корней - это - . Обращаем внимание, что нужно сначала проверить, имеет ли группа какой-либо примитивный корень, прежде чем находить число корней.
Если группа G = < Z n* , x > имеет хотя бы один примитивный корень, то число примитивных корней - ( (n))
Рассмотрим три вопроса:
1. Если дан элемент a и группа , как можно определить, является ли a примитивным корнем G ? Это не такая легкая задача.
а. Мы должны найти , - эта задача по сложности подобна задаче разложения на множители числа n .
б. Мы должны найти 
.
2. Если дана группа , как найти все примитивные корни ? Эта задача более трудная, чем первая задача, потому что мы должны повторить вычисления по п.1.б для всей группы.
3. Если дана группа , то как выбирать примитивный корень G ? В криптографии мы должны найти, по крайней мере, один примитивный корень в группе. Однако в этом случае значение n выбирается пользователем, и пользователь знает . Пользователь пробует последовательно несколько элементов, пока не находит первый из них.
Циклическая группа . Циклические группы уже обсуждались в лекциях 5-6. Обратите внимание на то, что, если группа имеет примитивные корни, то они циклически повторяются. Каждый примитивный корень - генератор и может использоваться для создания целого набора. Другими словами, если g - примитивный корень в группе, мы можем генерировать набор Z n * как
Пример 13.14
Группа 
имеет два примитивных корня, потому что и 
. Можно найти примитивные корни - это 3
и 7
. Ниже показано, как можно создать целый набор Z 10*
, использующий каждый примитивный корень.
g = 3 -> g 1 mod 10 = 3 g 2 mod 10 = 9 g 3 mod 10 = 7 g 4 mod 10 = 1 g = 7 -> g 1 mod 10 = 7 g 2 mod 10 = 9 g 3 mod 10 = 3 g 4 mod 10 = 1
Обратите внимание, что группа 
всегда циклическая, потому что p
- простое.
Группа G = < Z n * , x > является циклической группой, если она имеет примитивные корни. Группа G = < Z p * , x > всегда является циклической.
Идея дискретного логарифма
. Группа 
имеет несколько интересных свойств.
Решение модульного логарифма с использованием дискретных логарифмов
Теперь рассмотрим, как решаются задачи типа y = a x (mod n) , т. е. дано y , а мы должны найти x .
Табулирование дискретных логарифмов . Один из способов решения вышеупомянутой проблемы - использовать таблицу для каждого Z p* и различных оснований. Этот тип таблицы может быть предварительно рассчитан и сохранен. Например, таблица 13.4 показывает значения дискретного логарифма для Z 7* . Мы знаем, что мы имеем два примитивных корня или основания в данном множестве.
| y | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| x = L 3 y | 6 | 2 | 1 | 4 | 5 | 3 |
| x = L 5 y | 6 | 4 | 5 | 2 | 1 | 3 |
Составив таблицы для других дискретных логарифмов для всех групп и всех возможных оснований, мы можем решить любую дискретную логарифмическую проблему. Этот подход подобен изучаемым в прошлом традиционным логарифмам. До появления калькуляторов и компьютеров таблицы использовались, чтобы вычислять логарифмы по основанию 10 .
Пример 13.15
Найдите x в каждом из следующих случаев:
a. 
b. 
Мы можем легко использовать таблицу 13.4 дискретного логарифма .
Группа исследователей из EPFL и Университета Лейпцига смогла посчитать логарифм по основанию простого числа размером 768 бит . Для этого им понадобилось 200 ядер и время с февраля 2015 года. Использовали они вариант цифрового решета. Таким образом логарифмирование сравнялось с факторизацией где рекорд для обычных чисел тоже 768 битКстати, после завтрашнего апдейта можно будет прикручивать бесплатный TLS к dyndns хостам! Это суперкруто, все хомяки теперь будут с сертификатами.
Защищаемся от Side channel атак
Не секрет, что нынче информацию о ключах шифрования можно удаленно снимать чуть ли не через вентилятор. Поэтому, все большую популярность обретают constant-time алгоритмы, которые не зависят от входных данных. Немцы выпустили минимальные требования для реализаций, выполнение которых усложнит задачу получения секретных данных через побочные каналы данных. , советую ознакомиться.
На этом у меня всё, до новых встреч!
130 Глава 10. АЛГОРИТМ СИЛЬВЕРА - ПОЛЛИГА - ХЭЛЛМАНА
Запись показателя в виде дроби корректна, поскольку один из сомножителей числителя, а именно u , делится наp , т.е. дробь является обычным целым числом.
Очевидно, r p p , j = b ju = 1 , следовательно, элементыr p , j - корни степениp
из единицы. Аналогичным образом заполним все строки таблицы R .
Дальнейшая работа сводится к вычислениям, в результате которых появляются элементы, являющиеся корнями степени p из единицы в поле.
Для каждого такого элемента будет необходимо определить его позицию
j (номер колонки) в строке таблицыR с меткой | ||||||||
Поскольку в каждой строке элементы различны, то для данного числа |
||||||||
соответствующую ему позицию мы определим однозначно. | ||||||||
Для этого, | конечно, мы должны быстро просмотреть строку таблицы R , |
|||||||
что возможно, поскольку число q − 1 - гладкое. | ||||||||
10.3. Алгоритм дискретного логарифмирования | ||||||||
Предположим, что x представлен в | p -ичной системе счисления. Тогда |
|||||||
его вычет по | модулю p a | имеет вид | x = x | X p +K+x | a− 1 | p a − 1 modp a , |
||
0 ≤x i ≤p −1 . | ||||||||
Обозначим | y0 = y. | определения | x k, | k = 0, K , a− 1 , |
||||
предложим следующую процедуру, которую обсудим позже. | ||||||||
Прежде всего, определяем x | как позицию | y u p | в строке с номером p |
|||||
таблицы R .
Алгоритм дискретного логарифмирования 131
k > 0 коэффициентx k | определяем как позицию элемента | yk u | p k+ 1 | |||||||||||||||||||||
yk = y0 | b h(k) , | |||||||||||||||||||||||
h(k) = x+ x p+K+ x | p k− 1 . | |||||||||||||||||||||||
k − 1 | ||||||||||||||||||||||||
Повторив процедуру | делящего | q − 1 , | получаем |
|||||||||||||||||||||
значения | x modp a , | помощью китайской | остатках |
|||||||||||||||||||||
восстанавливаем x mod (q − 1 ) . | ||||||||||||||||||||||||
Обоснуем процедуру определения x k . | ||||||||||||||||||||||||
Вычислим y 0 u p . Очевидно, | y 0 u p- | корень степени | p из единицы, причем |
|||||||||||||||||||||
y u p= y u | p = b xu p= b x0 u p+ (x− x0 ) u | x − x | X p +K+x | a− 1 | p a − 1. | |||||||||||||||||||
Кроме того, число x 0 u | p является целым, т.к.u делится на | |||||||||||||||||||||||
В выражении (x − x 0 ) u p оба сомножителя делятся на | p . Разделив на | |||||||||||||||||||||||
сомножитель, | получаем, | что (x − x | p = ku, | B x 0 u | ||||||||||||||||||||
Сравнив с обозначением r | p , получаем, чтоy u p | j = x. | ||||||||||||||||||||||
Это позволяет определить | Как позицию | y u p в строке таблицы | R с |
|||||||||||||||||||||
меткой p . | ||||||||||||||||||||||||
Уничтожим теперь x | в показателе степени b x , | разделив | b x 0. |
|||||||||||||||||||||
Обозначим результат через y 1 :y 1 = y 0 b x 0 p 0 и вычислимy 1 u p 2 = b u (x − x 0 ) p 2 .
члены, кроме ux 1 p p 2 , кратныu и на значениеb u (x − x 0 ) p 2 не влияют.
132 Глава 10. АЛГОРИТМ СИЛЬВЕРА - ПОЛЛИГА - ХЭЛЛМАНА
Поскольку u делится на | также целое, |
|||||||||||||||||
откуда y u | p2 = b x1 u p= r | j = x . Таким образом, | x равен позиции | y u p2 |
||||||||||||||
в строке с меткой p таблицыR . | ||||||||||||||||||
Для определения | уничтожим | в показателе степени b x − x 0 , разделив |
||||||||||||||||
b x1 p1 . | b x0 p0 + x1 p1 | B d , | ||||||||||||||||
d = x2 p2 +K+ xa − 1 pa − 1 . | ||||||||||||||||||
Вычисляем y u p 3 | B x2 u p= r | j = x , что позволяет определитьx |
||||||||||||||||
по таблице R и т.д., пока не определимx a − 1 . | ||||||||||||||||||
10.3.1. Пример вычисления дискретного логарифма | ||||||||||||||||||
В поле F 37 , приb = 2 , найти дискретный логарифм элемента 28. | ||||||||||||||||||
Решение. Задача сводится к решению в поле F | уравнения 28 = 2 x . | |||||||||||||||||
q = 37 | является | степенью | простого | числа, поэтому |
||||||||||||||
операции в поле совпадают с операциями в поле вычетов по модулю 37, в частности, деление есть умножение на обратный элемент.
u = q − 1= 36= 22 32 , | следовательно, | имеем два | |||||||||
делителя: 2 и 3. | |||||||||||
Составим таблицу | со строки с меткой p = 2 . | Вычислим |
|||||||||
B j (q − 1 )2 | для j = 0,1 | 2 (q − 1 ) 2 ≡ −1 (37 ) . | |||||||||
2, j | |||||||||||
Элементами строки с меткой 3 | являются числа: | B j (q − 1 )3 , | j = 0,1,2, |
||||||||
3, j | |||||||||||
т.е. r 3,0 = 1 ,r 3,1 = 2 36 3 ≡ 26 (37 ) ,r 3,2 = 2 2 36 3 ≡ 2 24 ≡ 10 (37 ) . ТаблицаR имеет следующий вид.
Алгоритм дискретного логарифмирования 133
Таблица 4. Корни из единицы степеней 2 и 3
Найдем вычет | x = x | X p +K+x | a− 1 | pa − 1 | mod p a , | при p = 2 ,a = 2 . |
Число шагов равно | a = 2 . Итак, необходимо определить | x 0 , x 1 . Найдемx 0 . |
||||
Вычислим y 0 u p = 28 18 ≡ 1 (37 ) . Позиция единицы в строке 2 таблицыR равна
0, следовательно, x 0 = 0 .
Вычислим y , | уничтожив член с | в показателе числа b x : | y = y | b x0 p0 . |
|||||||||||
Поскольку x | то y = y . | Возводим y | в степень u | p 2, | p 2= 4 : |
||||||||||
y u 4= 28 36 4= − 1 (37 ) . | |||||||||||||||
Позиция числа (-1) в строке 2 таблицыR равна 1, следовательно, | x 1= 1 . |
||||||||||||||
Итак x = x 0 + x 1 p = 2 mod 4. | |||||||||||||||
Найдем вычет | x mod p a , при | p = 3 ,a = 2 . Число шагов равноa = 2 . |
|||||||||||||
y 0 u p = 28 12 ≡ 26 (37 ) . Позиция | 26 в строке 3 таблицы | ||||||||||||||
следовательно, | x = 1 , поэтому | y = y | b x 0 p 0 = 14. | ||||||||||||
Возводим | в степень | p 2, | p 2= 9 : | y u9 | 1436 9 = 10(37) , |
||||||||||
следовательно x 1 = 2 . Итак, | x = 7 mod9. | ||||||||||||||
Z p r Z
134 Глава 10. АЛГОРИТМ СИЛЬВЕРА - ПОЛЛИГА - ХЭЛЛМАНА
систему сравнений x = 2 mod4 ,x = 7 mod9 :9 − 1 (4 ) = 1 , |
|
4− 1 (9) = 7, | x ≡ 2 9(9− 1 mod 4) + 7 4(4− 1 mod 9) = 214, т.е. |
x ≡ 34 mod36.
10.3.2. Логарифмирование в группе единиц кольца вычетов по модулю pr .
Существование частных методов дискретного логарифмирования в конечном поле приводит к необходимости построения больших простых чисел со специальными свойствами. В качестве подхода, позволяющего снизить величины генерируемых простых чисел, можно, в принципе, рассмотреть использование в протоколе Диффи-Хэллмана операцию приведения по модулю
существует первообразный элемент γ , степени которого представляют все вычеты, взаимно простые с модулем. Эти вычеты образуют вмультипликативную группуU (p r ) изϕ (p r ) элементов (т.н. группу единиц).
Можно показать , что если γ p - первообразный корень в поле
GF (p ) , то одно из чиселγ = γ p + kp , гдеk { 0,1 } , удовлетворяет условию
(γ p + kp ) p − 1 ≠ 1 (mod p 2 ) и является первообразным корнем по любому модулюp α ,α > 1 . Заметим, что пары чиселa ,p , для которых выполняется соотношениеa p − 1 = 1mod p 2 , встречаются редко. Поэтому будем считать, что
γ = γp .
Таким образом, любой из ϕ (p r ) = p r − 1 (p − 1 ) вычетовb U (p r ) можно
представить в виде b = γ x mod p r .
Алгоритм дискретного логарифмирования в группе единиц… 135
Соответственно, задача дискретного логарифмирования в группе единиц кольца Z p r Z состоит в определении вычетаx поmod ϕ (p r ) , исходя изb и
γ .
К сожалению, использование модуля p r не дает преимуществ, поскольку
при наличии эффективного алгоритма логарифмирования в простом поле
GF (p ) логарифмирование в группе единиц кольца вычетов по модулюp r ,r > 1 , практически всегда можно осуществить, воспользовавшись свойствами так называемого обобщенного отношения ФермаL m (a ) .
Областью определения отображения L m (a ) является группаU (m )
вычетов по модулю m , взаимно простых с модулем. По теореме Эйлера,
существует λ :a ϕ (m ) − 1 = λ m . ЗначениеL m (a ) определяется как вычет числаλ по модулюm :L m (a ) = a ϕ (m m ) − 1 (mod m ) .
Легко убедиться, что отношение Ферма обладает следующими замечательными свойствами.
Lm (ab) = Lm (a) + Lm (b)(mod m) ,
Lm (a+ mc) = Lm (a) + ϕ (m) ca- 1 (mod m) ,
где a, b U(m) , c ZmZ.
r > 1 . Заметим, | что в этом случае, |
|||||
(a+ mc) = L(a) + (pr − pr − 1 ) ca- 1 (mod m) = L(a) (mod pr − 1 ) . | ||||||
образом, если a ≡ b (mod m ) , то | L (a) ≡ L(b) (mod pr − 1 ) . | |||||
L (γ ) = 0(modp r − 1 ) , | определения | L (γ ) следует, что |
||||
γ ϕ (m ) = 1(modp 2 r − − 2 ≤ r − 1 , т.е.
r ≤ 1 , что противоречит
Если L
(γ )= 0 (mod m ), то
(γ ) = 0(modp r − 1 ) и r ≤ 1 .
Аналогично, при L
(γ ) = pt (modp r − 1 ) ,
получаем
γ ϕ (m ) = 1(modp r + 1 ) ,
что невозможно, т.к. ϕ (p r + 1 ) > ϕ (m ) .
Таким образом, элемент L m (γ )
p и, следовательно,
обратим по модулю p r − 1 .
Рассмотрим задачу логарифмирования
в группе единиц кольца
Z mZ ,
эффективный алгоритм
логарифмирования в кольце
известен.
Из соотношения b = γ x mod p r
b = γ x mod p,
известно значение x по модулю
p − 1 . Если мы найдемx (mod p r − 1 ) , то
значение
по модулю ϕ (m ) = p r − 1 (p − 1 )
можно вычислить по китайской
теореме об остатках.
Очевидно,
что значение x (mod p r − 1 )
легко определить
из сравнения
L (b) = xL(γ ) (mod pr − 1 ) .
необходимо
вычислять
значения
h = Lm (a) (mod pr − 1 ) .
Дискретный логарифм
Дискретное логарифмирование (DLOG) – задача обращения функции g x в некоторой конечной мультипликативной группе G .
Наиболее часто задачу дискетного логарифмирования рассматривают в группе обратимых элементов кольца вычетов , в мультипликативной группе конечного поля , или в группе точек на эллиптической кривой над конечным полем. Эффективные алгоритмы для решения задачи дискетного логарифмирования в общем случае неизвестны.
Для заданных g и a решение x уравнения g x = a называется дискретным логарифмом элемента a по основанию g . В случае, когда G является группой обратимых элементов кольца вычетов по модулю m , решение называют также индексом числа a по основанию g . Индекс числа a по основанию g гарантированно существует, если g является первообразным корнем по модулю m .
Решение задачи дискретного логарифмирования состоит в нахождении некоторого целого неотрицательного числа x , удовлетворяющего уравнению (1). Если оно разрешимо, у него должно быть хотя бы одно натуральное решение, не превышающее порядок группы. Это сразу даёт грубую оценку сложности алгоритма поиска решений сверху - алгоритм полного перебора нашел бы решение за число шагов, не выше порядка данной группы.
Чаще всего рассматривается случай, когда , то есть группа является циклической , порождённой элементом g . В этом случае уравнение всегда имеет решение. В случае же произвольной группы, вопрос о разрешимости задачи дискретного логарифмирования, то есть вопрос о существовании решений уравнения (1), требует отдельного рассмотрения.
Пример
Проще всего рассмотреть задачу дискретного логарифмирования в кольце вычетов по модулю простого числа.
Пусть задано сравнение
Будем решать задачу методом перебора. Выпишем таблицу всех степеней числа 3. Каждый раз мы вычисляем остаток от деления на 17 (например, 3 3 ≡27 - остаток от деления на 17 равен 10).
| 3 1 ≡ 3 | 3 2 ≡ 9 | 3 3 ≡ 10 | 3 4 ≡ 13 | 3 5 ≡ 5 | 3 6 ≡ 15 | 3 7 ≡ 11 | 3 8 ≡ 16 |
| 3 9 ≡ 14 | 3 10 ≡ 8 | 3 11 ≡ 7 | 3 12 ≡ 4 | 3 13 ≡ 12 | 3 14 ≡ 2 | 3 15 ≡ 6 | 3 16 ≡ 1 |
Теперь легко увидеть, что решением рассматриваемого сравнения является x=4 , поскольку 3 4 ≡13.
На практике модуль обычно является достаточно большим числом, и метод перебора является слишком медленным, поэтому возникает потребность в более быстрых алгоритмах.
Алгоритмы решения
В произвольной мультипликативной группе
Разрешимости и решению задачи дискретного логарифмирования в произвольной конечной абелевой группе посвящена статья BuchmannJ., Jacobson M.J., Teske E. On some computational problems in finite abelian groups . В алгоритме используется таблица, состоящая из пар элементов и выполняется умножений. Данный алгоритм медленный и не пригоден для практического использования. Для конкретных групп существуют свои, более эффективные, алгоритмы.
Другая возможность эффективного решения задачи вычисления дискретного логарифма связана с квантовыми вычислениями . Теоретически доказано, что, используя их, дискретный логарифм может быть вычислен за полиномиальное время . В любом случае, если полиномиальный алгоритм вычисления дискретного логарифма будет реализован, это будет означать практическую непригодность криптосистем на его основе.
Классическими криптографическими схемами, базирующимися на сложности задачи дискретного логарифмирования, являются схема выработки общего ключа Диффи-Хеллмана , схема электронной подписи Эль-Гамаля , криптосистема Мэсси-Омуры для передачи сообщений.
Ссылки
- Василенко О. Н. Теоретико-числовые алгоритмы в криптографии . - Москва: МЦНМО , 2003. - 328 с. - ISBN 5-94057-103-4
- Коблиц Н. Курс теории чисел и криптографии . - Москва: ТВПб, 2001. - 254 с. - ISBN 5-85484-014-6
- Odlyzko A. M. Discrete logarithms in finite fields and their cryptographic significance // LNCS . - 1984. - Т. 209. - С. 224-316.
- Buchmann J., Jacobson M.J., Teske E. On some computational problems in finite abelian groups // Mathematics of Computation . - 1997. - Т. 66. - № 220. - С. 1663-1687.
- Статья Дискретное логарифмирование на сайте Научная сеть
- Обзор методов вычисления дискретного логарифма (на английском)
- Нечаев В.И. К вопросу о сложности детерминированного алгоритма для дискретного логарифма // Математические заметки . - 1994. - В. 2. - Т. 55. - С. 91-101.
Wikimedia Foundation . 2010 .
Смотреть что такое "Дискретный логарифм" в других словарях:
дискретный логарифм - В группе два элемента d; g таковы, что имеется целое число r, удовлетворяющее условию gr = d; r называется дискретным логарифмом d по основанию g. Тематики информационные технологии в целом EN discrete logarithm … Справочник технического переводчика
Алгоритм Полига Хеллмана (также называемый алгоритм Сильвера Полига Хеллмана) детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Одной из особенностью алгоритма является то,… … Википедия
- (англ. Baby step giant step; также называемый алгоритм больших и малых шагов) в теории групп, детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный… … Википедия
