А.В. Рожков, О.В. Ниссенбаум - Теоретико-числовые методы в криптографии (1127102), страница 22

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 22)

Общий подход к поиску чисел x, y таков: выбирается факторная база S={p₁, p₂, … , p_t}. Как правило, это t первых простых чисел.

Случайно выбирается несколько чисел a_i, вычисляются числа b_i=a_i² mod n и разлагается по факторной базе b_i= . Те числа b_i, которые разложить по базе S не удалось, из дальнейшего рассмотрения исключаются. Всего требуется t+1 пара (a_i, b_i).

Затем из чисел b_i составляется такое произведение B= , c_i {0,1}, что B оказывается полным квадратом (то есть mod 2=0 для всех j). Вектор c находится путем решения соответствующей системы сравнений. Тогда

x= , y= .

Очевидно, данная пара удовлетворяет сравнению x²≡y²(mod n). Если она удовлетворяет еще и условию x ±y(mod n), то НОД(x—y,n) есть нетривиальный делитель n. Иначе следует повторить данный метод, выбрав другие пары (a_i, b_i).

§3. Алгоритмы дискретного логарифмирования.

Проблема дискретного логарифмирования в группе Z_p^* состоит в следующем: пусть p – простое число, g – порождающий элемент группы Z_p^* (или, иначе, примитивный корень по модулю p), a=g^x (mod p). Пусть известны g, p, a, но неизвестно x. Требуется найти x, или, иначе, log_ga mod (p—1), то есть вычислить дискретный логарифм.

В отличие от логарифма непрерывного, дискретный логарифм не является дифференцируемой монотонной функцией, его нельзя найти приближенно, разложив в ряд Тейлора, и вообще никакого приближенного значения здесь не может быть, ведь x – целое число.

Дискретное логарифмирование считается сложной проблемой. С этой проблемой связаны и другие теоретико-числовые проблемы, такие как проблема Диффи-Хеллмана, логарифмирование в Z_n. Если удастся решить проблему дискретного логарифма, то приведенные задачи решаются за полиномиальное время.

3.1. Метод прямого поиска.

Этот наивный метод является самым трудоемким, он требует O(n) умножений, то есть обладает экспоненциальной сложностью. Состоит он в следующем: вычисляются g⁰, g¹, g²,…, g^p—1 пока не попадется gⁱ≡a(mod p). Полученное i будет искомым дискретным логарифмом i=log_ga (mod p—1).

Пример

p=23, g=5, a=19.

Ответ: log₅19 mod 22 = 15.

3.2. Шаг младенца – шаг великана.

В открытой литературе этот метод впервые был описан Шенксом (Daniel Shanks), ссылки на него известны с 1973 года. Это был один из первых методов, более быстрый чем метод прямого перебора.

Общая схема алгоритма такова:

Берем два целых числа m и k, таких что mk>p (как правило, m=k= ). Затем вычисляются два ряда чисел:

a, ga, g²a, … , g^m—1a (mod p)

g^m, g^2m, g^3m, … , g^km (mod p)

(все вычисления произведены по модулю p).

Найдем такие i и j, для которых gⁱa=g^jm. Тогда x=jm—i.

Справедливость последнего равенства подтверждается следующей цепочкой, все вычисления в которой произведены по модулю p:

g^x=g^jm-i=g^jm(gⁱ)^-1=g^jma(gⁱa)^-1=g^jma(g^jm)^-1=a.

Заметим, что числа i и j непременно будут найдены, поскольку при i= , j= выполняется jm—i= , причем km>p. То есть среди всех чисел вида jm—i обязательно содержится 0 < x ≤ p.

Замечание: Указанный метод можно применять для разыскания дискретных логарифмов в любой циклической группе порядка n.

Приведем этот метод в форме алгоритма.

Алгоритм «Шаг младенца-шаг великана»:

Вход: g - порождающий элемент конечной группы G порядка n; a G.

Ш.1. Вычислить m= .

Ш.2. Вычислить b=g^m.

Ш.3. Вычислить последовательности u_i=bⁱ, v_j=ag^j Для i,j= .

Ш.4. Найти i, j такие что u_i=v_j. x=mi—j mod n. Идти на Выход.

Выход: log_ga=x.

Одна из трудоемких частей этого алгоритма – это поиск на Шаге 4. Он может быть осуществлен несколькими способами:

1. Сначала построить таблицу (i, u_i), отсортировать ее по второй компоненте а затем произволить сравнения по мере нахождения компонент v_j.

2. Построить две таблицы (i, u_i) и (j, v_j), отсортировать каждую из них, а затем произвести поиск совпадений.

3. Объединить u, v в одну таблицу, снабдив их номером в соответствующей последовательности и битом принадлежности к одной из двух последовательностей, а затем применить совместную сортировку. И т. п.

Сложность данного алгоритма составляет O( ) умножений по модулю и O( log n) операций сравнения.

Пример.

Пусть n=229 (простое число), g=6, a=12.

Ш.1. m=16.

Ш.2. b=g^a mod n =6¹² mod 229 = 183.

Ш.3. В этом примере вычислим сначала ряд u_i, а затем будем вычислять компоненты v_j до тех пор, пока не найдется совпадение.

i=16, j=6. x=mi—j mod n = 250 mod 228 = 22.

Проверка: 6²² mod 229= 12.

Ответ: log₆12 mod 228 = 22.

3.3. Ро-метод Полларда для дискретного логарифмирования.

Этот алгоритм осуществляет случайный поиск дискретных логарифмов, как и метод «шаг ребенка – шаг великана», но он требует меньшего объема памяти для хранения данных, поэтому предпочтительней для практических целей. В основе данного метода лежит та же идея, что и в основе ро-метода для факторизации – строится псевдослучайная последовательность, в которой находятся совпадающие элементы при помощи метода Флойда, а затем на основании полученной величины вычисляется искомый дискретный логарифм.

Пусть требуется вычислить log_ga в конечной группе G порядка n.

Группа G разбивается на три непересекающихся подмножества примерно равной мощности: G=S₁US₂US₃, так чтобы 1 S₂. Причем разбиение должно быть построено таким образом, чтобы проверка, к какому подмножеству принадлежит данный элемент x, была простой.

Например, если G=Z_p, где p – простое число, то можно задать разбиение S₁={1,…, }, S₂={ ,…, }, S₃={ , … , p—1}, или разбиение может быть таким: если x mod 3=1, то x S₁, если x mod 3=2, то x S₂, если x mod 3=0, то x S₃.

Далее на G задается последовательность x₀, x₁, x₂, … , где x₀=1, x_i+1 вычисляется по x_i посредством функции f для i≥0:

x_i+1=f(x_i)=

Вычисления проводятся в группе G, то есть если G=Z_m, то вычисления следует производить по модулю m.

Такая последовательность групповых элементов может быть представлена двумя последовательностями u₀, u₁, u₂,… и v₀, v₁, v₂,… такими, что x_i= , u₀=v₀=0,

u_i+1= , v_i+1=

Вычисления в последовательностях u и v производятся по модулю n.

В силу того, что группа G – конечная, при помощи метода Флойда можно найти такие x_i и x_2i, что x_i = x_2i. Тогда = . Логарифмируя по основанию g обе части данного уравнения, получим

(v_i—v_2i)log_ga≡(u_2i—u_i) (mod n)

Решая это сравнение, получим искомый логарифм. (Заметим, что если G=Z^*_m, то n=φ(m)).

Сложность данного метода составляет O( ) , где n – порядок группы G.

Замечание. Метод может дать отказ в том случае, когда v_i =v_2i. Тогда следует назначить случайные значения от 0 до n—1 переменным u₀, v₀ , вычислить x₀= и повторить все шаги алгоритма.

Замечание. В том случае, когда имеется достаточно места для хранения данных в процессе вычислений (например, когда G невелико или вычисления производятся вручную), можно обойтись без метода Флойда. Тогда следует хранить все члены последовательностей x, u и v до того, как x_i = x_j и дискретный логарифм находится из сравнения (v_i—v_j)log_ga≡(u_j—u_i) (mod n).

Пример.

G=Z^*₁₉, a=8, g=2.

Характеристики

Список файлов книги