08.04.09.Печать_edit

Для случайно выбранных bi	и bj имеем Pr Ai Bj k 1 , поэтому в таб-
лицах 1 и 2, содержащих по		значений	b и			, соответственно, с
	k			b	j
			i
вероятностью 0.5 имеется пара равных значений			Ai	и Bi			(согласно пара-
			0			0

доксу о днях рождения). Таким образом, с вероятностью 0.5 алгоритм находит невычеты bi0 и b j0 , удовлетворяющие сравнению (2.7).

Далее вычисляем невычет b bi0 bj0 mod p , удовлетворяющий сравне-

нию (2.4) и затем вычисляем z ka mod p . Выполняя описанный алгоритм m раз, где m небольшое число, мы с вероятностью близкой к 1 вычислим значение z. Сложность алгоритма составляет 2m k операций модульного возведения в степень. Таким образом, сложность процедуры вычисления z

зависит экспоненциально от длины |k| и при |k| = 160 бит	равна
280 операций, что соответствует минимальному приемлемому	уровню
стойкости для систем ЭЦП.

Полезным для оценки средней сложности рассматриваемой задачи представляется вопрос о зависимости мощности подмножества вычетов a, таких

p 1

что a k 2 mod p e , где

e – некоторый заданный корень из единицы. Ответ

i

i

на этот вопрос дает следующее утверждение.

Утверждение 2.4.

Каждому корню из единицы e

соответствует ровно

p 1

различных

i

k 2

p 1

p 1

вычетов a , где m = 1, 2, ...,

, таких что a k 2

mod p e .

m

k 2

m

i

Доказательство.

p 1

p 1

Пусть для вычетов a и a выполняется условие

a

k 2

k 2

mod p ei .

a

Тогда		a
	a

	p 1
					a
	k 2 1mod p , следовательно значение		a			является вычетом k-
					a

	a					p 1
й степени, порядок которого равен	p								. Число таких вычетов
							2
	a					k

61

p 1

равно

Z1 # a : p (a)

N N (см. доказательство утверждения 2.3).

k 2

Пусть эти вычеты составляют множество a 1

, a 2 ,..., a N . Если для какого-

p 1

либо значения

существует некоторый вычет a ,

k 2

mod p ei ,

такой что a

p 1

mod p ei , причем все вы-

2

то для каждого значения z выполняется a az k

четы

a az mod p , где z = 1, 2, ..., N, являются различными. Обозначим через

N число корней из единицы ei , для которых существует хотя бы один вычет

p 1

a, такой что a k 2 mod p ei . Тогда каждому корню ei соответствует ровно N различных вычетов, удовлетворяющих последнему условию. Полное число

p 1

p 1

k , т. е. каждому из k

вычетов равно

k N

k

, следовательно

k

kN

разных корней из единицы соответствует ровно N

p 1

различных выче-

k 2

тов.

Утверждение 2.4 означает, что для случайно выбранного значения вычета a имеем следующую вероятность

Pr a

p 1

k 2

mod p 1

Pr a

p 1				1
k	2
				k .
			mod p ei

Это означает, что для атакующего нет предпочтительных значений корней из единицы, для которых он мог бы заранее (для заданных значений p и k) найти значение невычета, удовлетворяющего условию (2.4), а затем со сравнительно большой вероятностью легко бы вычислял корни из подавляющего числа вычетов a.

Сложность описанного выше алгоритма извлечения корня определяется только размером степени k и не зависит от размера модуля p (т. е. при больших размерах модуля p он не зависит от сложности задачи дискретного логарифмирования и имеет самостоятельное значение). Однако он требует использования достаточно большой памяти. Используя подход Флойда (см. раздел 2.5.2), можно разработать модификацию этого алгоритма, для которой используется память малого объема. Это можно сделать следующим образом. Определим функцию случайного отображения в виде

62

aN x z Nk mod p,			x	p 1
				2
def	i		i
xi 1 f (xi )				p 1		,
		Nk
	xi z mod p,		xi
				2

где z некоторая константа. Применяя алгоритм Флойда, найдем значение индекса m, такое что повтор x2m = xm имеет место в начале цикла, тогда с веро-

ятностью 0.5 будет выполняться

одно из двух условий 1)

x

p 1

и

m 1

2

x

p 1

или 2)

x

p 1

и

x

p 1

(если ни одно из этих условий

2m 1

2

m 1

2

2m 1

2

не выполнилось, то следует изменить начальное значение x0 и/или z). Пусть для определенности имеет место первое условие. Тогда мы имеем

xm aN xm 1 z Nk mod p и x2m x2m 1 z Nk mod p

и можем поступить следующим образом. Разделим первое уравнение на второе и получим

a	N	xm 1	z Nk		1mod p ,
	x2m 1		z

где выражение в скобках представляет собой невычет, т. е. мы нашли необходимое значение невычета в выражении (2.4) и далее можно легко вычислить корень k-ой степени из вычета a.

Смысл использования операции возведения в степень Nk состоит в том, чтобы получать значения аргумента случайной функции, лежащие во множестве корней k-ой степени из единицы. Тогда среднее число вычислительных шагов, необходимых для нахождения требуемого повтора, будет составлятьk , где небольшой коэффициент. В общем случае можно применять случайные функции следующего вида

aN F (x ) Nk mod p,			x	p 1
				2
def	i		i
xi 1 f (xi )				p 1		,
		Nk
	F (xi ) mod p,		xi
				2

где F(xi ) случайная функция общего вида. Следует отметить, что нахождение повтора именно в начале цикла, что требуется в рассматриваемом способе, связано с построением алгоритма перехода от повтора, найденного в середине цикла, к нахождению повтора в начале цикла случайной функции.

63

2.4.3. Сведение трудных случаев извлечения корней к задаче дискретного логарифмирования

Если размер простой степени k представляет собой большое число, а размер N сравнительно мал, то сложность задачи дискретного логарифмирования по модулю p имеет сложность значительно ниже сложности алгоритмов непосредственного извлечения корня, которые описаны выше. В этих случаях сложность вычисления корней определяется сложностью дискретного логарифмирования. Действительно, вычисление корней посредством решения задачи дискретного логарифмирования осуществляется следующим образом.

1.Находим некоторый первообразный корень g по модулю p.

2.Находим индекс вычета a по основанию g: indg a.

3.Делим indg a на степень корня k, в результате чего получаем индекс

корня z ka mod p : indg z = k 1indg a (такое деление может быть выполнено, так как индекс вычетов k-й степени кратен значению k).

4. Возводим (по модулю p) g в степень, равную indg z, и получаем значение корня: ka gindg z mod p .

Покажем, что индексы вычетов всегда делятся нацело на значение степени. Если a есть вычет, то существует некоторое значение x, для которого

выполняется соотношение x k = a mod p. Это соотношение можно представить в виде gindg x k g k indg x a gindg a mod p , т. е. k | indg a.

2.5. Алгоритмы факторизации

2.5.1. Факторизация B-гладкого модуля RSA

Простое число p называется B-гладким, если все делители числа p – 1 не превосходят некоторое сравнительно малое число B. Пусть имеем di B

di | p 1, где di — простой делитель p – 1. Модуль n = pq в криптосистеме RSA называется B-гладким, если хотя бы один из его делителей является B- гладким. Рассмотрим B-гладкий модуль RSA, в котором для определенности B-гладкий множитель обозначим буквой p. Составим произведение

64

D risi ,

ri B

включающее в качестве множителей значения risi , представляющие собой некоторые степени всех простых чисел ri, не превосходящих B, причем пока-

затели степени этих множителей таковы, что risi n . Значение натурального числа n' следует выбрать из условия n' ≥ p. Поскольку для достижения максимальной сложности задачи факторизации модуля RSA числа p и q выбираются такими, чтобы они имели примерно одинаковую длину и задавали

5 |n|

большую разность p – q, то можно принять n 2 9 , где | n | — битовая длина числа n. Если учитывать произвольный выбор длин чисел p и q, то можно положить n' = n.

Поскольку число p является B-гладким, то все простые множители disi ,

входящие в p – 1, и включены в произведение D. В силу условия risi n p

имеем также si si , поэтому p – 1 | D. Учитывая малую теорему Ферма, записываем:

D

2D 2 p 1 p 1 1mod p p | 2D 1.

Рассмотрим значение Z 2D mod n . Имеем:

Z 2D mod n Z 2D 1mod p p | Z 1.

Таким образом, число 2D mod n 1 делится на p, поэтому нетривиальный делитель RSA-модуля может быть найден путем вычисления с помощью расширенного алгоритма Евклида наибольшего общего делителя чисел

2D mod n 1 и n:

НОД (2D mod n 1, n) p.

Обозначим произведение D как DB, чтобы явно показать его зависимость от выбора значения B. Если нам надо разложить конкретный RSA-модуль, то мы не знаем заранее минимального значения B. Поэтому целесообразно начать разложение с малого значения B, постепенно увеличивая его, если НОД (2DB mod n 1, n) 1 . При этом следует сохранять промежуточные значения

65

ZB 2DB mod n , поскольку последующие значения ZB' получаются путем воз-

ведения ZB в некоторую степень по модулю n.

2.5.2. Факторизация модуля RSA с использованием метода Флойда

Метод Флойда используется для нахождения коллизий для функций, принимающих псевдо случайные значения из некоторой конечной области. Коллизией называется наличие двух или более значений аргумента, при которых функция принимает одинаковые значения. Смысл применения алгоритма Флойда состоит в том, что для случайных функций с большим периодом повторения значений коллизии могут быть найдены при использовании малого объема памяти. Рассмотрим случайную функцию определенную следующим соотношением

xi 1 f (xi ) , x0 a ,

где a некоторое специфицированное значение. Получаемая по указанному соотношению последовательность значений функции является в определенном смысле псевдослучайной при использовании функции с перемешивающими свойствами. Поскольку для каждого значения i > 1 имеется конечная вероятность, что функция примет значение, которое уже встречалось ранее, то при неограниченном росте i мы получим некоторый участок последовательности, который не повторяется (хвост) и периодически повторяющуюся часть последовательности (цикл). С учетом парадокса о днях рождения можно установить, что длина хвоста и длина цикла пропорциональны значению N , где N количество различных значений, которые может принять рассматриваемая функция (предполагаем, что все значения функция принимает с одинаковой вероятностью). Если взять другое начальное значение аргумента x0 a a , то будет получена другая последовательность с другой длиной хвоста и цикла (очевидно также, что эти последовательности не пересекаются, т. е. в них не содержатся одинаковые значения, если значение a не входит в первую последовательность). Коллизия соответствует переходу от последнего значения в цикле к первому. Пусть начало цикла имеет место при i = g, а конец – при i = h. Тогда имеем такую коллизию f (xh ) f (xg 1) , где

xh xg 1. Замечаем, что для нахождения коллизии требуется найти начало цикла.

66

xm 1

xm .

Метод Флойда заключается в том, что последовательно вычисляются значения «случайной» функции в соответствии с формулами

xi 1 f (xi ) и x2i 2 f f (x2i ) ,

которые сравниваются между собой на каждом шаге таких вычислений. В первом случае мы получаем все последовательные значения, принимаемые функцией, а во втором – только значения соответствующие четным индексам. С каждым шагом расстояние между первым значением и вторым возрастает на единицу. Поскольку значения, принимаемые функцией «зацикливаются», то рано или поздно оба значения попадут в цикл, а следовательно через определенное число шагов они «встретятся», т. е. при некотором значении i = m они совпадут: x2m 2 xm 1 . Это не означает автоматически, что коллизия уже найдена, поскольку в этот момент мы будем иметь x2m Однако пользуясь этим подходом можно найти совпадения при значениях быстро приближающихся к началу цикла, а затем найти совпадение в начале цикла. Это будет означать нахождение коллизии.

Рассмотрим использование метода Флойда для факторизации RSA модуля n = pq, где для определенности будем считать, что p < q. Возьмем функцию, задаваемую формулой

xi 1 f (xi ) xi2 a mod n,

где a – варьируемый параметр. Эта функция имеет хвост и цикл длиныn . С ней связана функция

xi 1 f (xi ) (xi2 a mod n) mod q,

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

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

Используя метод Флойда, для первой функции при известном q можно было бы найти значения x2m 2 mod q . Поскольку q неизвестное значение, то в качестве критерия выполнимости последнего сравнения можно использовать условие НОД x2m 2 xm 1,n 1, поскольку при выполнении ука-

67

i mod p

занного сравнения имеем q | x2m 2 xm 1 . При этом рассматриваемое сравнение имеет место с большой вероятностью одновременно с выполнением условия x2m 2 mod n xm 1 mod n , поэтому найденный наибольший общий делитель и будет равен q (или p, но поскольку мы предполагаем, что p < q, то более вероятно, что НОД будет равен q).

Трудоемкость этого способа факторизации составляет W O min{ p, q} , где O(*) – обознаение порядка и min{ p, q} 4n . Этим методом достаточно легко разложить RSA модули, имеющие длину до 256 бит.

2.6. Методы дискретного логарифмирования

2.6.1. Оптимизация переборного метода

Рассмотрим метод дискретного логарифмирования, впервые предложенный Д. Шенксом и известный под названием «шаг ребенка — шаг гиганта» (baby-step giant-step algorithm). Пусть нам требуется найти значение x

(0 ≤ x < ), удовлетворяющее условию y = a x mod p, где значения y, и p заданы, причем порядок числа равен (т. е. по модулю p относится к пока-

зателю ). Вычислим d (т. е. d является наименьшим из всех целых чи-

сел, превосходящих или равных значению ) и представим искомое значение x в виде x Qd r, где Q и r — целые числа, причем 0 ≤ r < d и 0 ≤ Q < d. С учетом этого представления имеем:

y x Qd r Qd r mod p ; y d Q r mod p .

Если найти пару значений 0 ≤ r < d и 0 ≤ Q < d, удовлетворяющих последней формуле, то значение x вычисляется по формуле x = Qd + r. Непосредственный перебор требует выполнения не более испытаний различных пар значений (Q, r). Этот способ требует использования памяти малого объема, однако при | | = 80 бит и более прямой перебор в настоящее время практически неосуществим. Вычислительную сложность нахождения требуемой пары чисел (Q, r) можно существенно уменьшить, если выполнить определенные предвычисления и построить таблицу значений для

68

i = 0, 1, 2, …, d – 1 (можно построить и использовать также и таблицу значе-

ний y d j mod p , однако при изменении значения y эту таблицу надо будет

вычислять повторно). Таблица (i, i mod p) , отсортированная по значениям

i mod p, существенно упрощает задачу нахождения дискретных логарифмов для различных значений y. При наличии этой таблицы для значений j = 0, 1, 2, …, d – 1 требуется последовательно выполнить вычисление значе-

ния y d j mod p и проверку наличия						полученного значения в		таблице
(i, i mod p).	Для	некоторого j = j0			обязательно будет найдено			значение
i0 mod p, такое что i0 mod p y d j mod p, откуда получаем
				x j0d i0 .
Таким образом, при			наличии		предварительно вычисленной			таблицы
(i, i mod p) , содержащей			d значений длиной | p |				(для ее хранения требуется
память размером d | p | бит),				вычисление		одного	логарифма потребует вы-
полнения	не	более	d	умножений		по модулю p (поскольку
y d j 1 mod p y d j d mod p ,					т. е.	последующее значение получаем,

умножая предыдущее на –d) и d log2 d операций сравнения. Сложность вы-

числения таблицы составляет d умножений по модулю p и d log2 d операций сравнения (при выполнении сортировки по значениям i mod p ). В целом сложность метода «шаг ребенка — шаг гиганта» можно оценить используемой памятью O и временем O .

Заметим, что размер модуля, по которому требуется выполнить логарифмирование, сам по себе не является определяющим в задании сложности дискретного логарифмирования. Наиболее существенным фактором является порядок числа , задающего основание дискретного логарифма. При | | = 80 бит и менее вычисление дискретных логарифмов вполне реализуемо на практике для модулей размером 103 бит и более.

69

2.6.2. Метод вычисления индексов

Рассмотрим еще один метод вычисления значения x (0 ≤ x < ), удовлетворяющего условию y = a x mod p. Используя идеи, лежащие в его основе, разработаны наиболее эффективные алгоритмы дискретного логарифмирования. В нем используется возможность построения подмножества простых чисел {p1, …, ps}, таких что i {1, …, s} имеем pi ≤ B, где B — сравнительно небольшое число, и достаточно большая доля чисел из множества {1, 2, …, p – 1} может быть представлена в виде произведения некоторых степеней чисел p1, …, ps, составляющих некоторую базу разложения (называемую B- гладкой). В дальнейшем будем полагать, что в качестве базы разложения выбраны все простые числа, не превосходящие B, а есть первообразный корень по модулю p (т. е. будем рассматривать случай = p – 1). Метод может быть представлен в виде следующих трех шагов.

1-й шаг. Случайным образом выбираются различные значения kj, для каждого из которых вычисляется значение K j k j mod p и находится кано-

ническое разложение числа Kj. Если в разложении Kj присутствуют простые множители, не входящие в базу разложения, то выбирается другое значение kj. В противном случае формируется соотношение вида Kj =

k s z

= j mod p pi ji , где zji ≥ 0. Логарифмируя последнее равенство, получа-

i 1

ем сравнение

s

log K j k j z ji log pi mod p 1.

i 1

Действуя указанным способом, построим t = s + ε (где число ε является сравнительно малым по сравнению с числом s) сравнений указанного типа и объединим их в следующую систему сравнений:

70