ИНФОРМАЦИОННАЯ БЕЗОПАСНОСТЬ: КРИПТОГРАФИЯ

Институт проблем информационной безопасности МГУ

О. Н. ВАСИЛЕНКО

ТЕОРЕТИКО-ЧИСЛОВЫЕ АЛГОРИТМЫ В КРИПТОГРАФИИ

МЦНМО, 2003

УДК 511+519.719.2	Издание осуществлено при поддержке РФФИ
ББК 32.81в6	(издательский проект № 03-01-14110).
В19

Василенко О. Н.

В19 Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с.

ISBN 5-94057-103-4

В монографии представлено современное состояние алгоритмической теории чисел, имеющей важные приложения в криптографии.

Предназначено для студентов старших курсов и аспирантов математических факультетов вузов, а также для специалистов, желающих познакомиться с последними достижениями в данной области.

ББК 32.81в6

	© О. Н. Василенко, 2003.
ISBN 5-94057-103-4	© МЦНМО, 2003.

Оглавление

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		7
Обозначения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		10
Глава 1. Тестирование чисел на простоту и построение
	больших простых чисел . . . . . . . . . . . . . . . . . . . . . . . . .	12
§ 1.1.	Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	12
§ 1.2.	Элементарные методы проверки простоты чисел . . . . .	12
§ 1.3.	Тесты на простоту для чисел специального вида . . . . .	15
§ 1.4. (N ± 1)-методы проверки простоты чисел и построения
	больших простых чисел . . . . . . . . . . . . . . . . . . . . . . . . . . .	22
§ 1.5.	Алгоритм Конягина—Померанса . . . . . . . . . . . . . . . . . . .	28
§ 1.6.	Алгоритм Миллера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	32
§ 1.7.	Вероятностные тесты на простоту . . . . . . . . . . . . . . . . . .	37
§ 1.8.	Современные методы проверки простоты чисел . . . . . .	43
§ 1.9.	Заключение. Детерминированный полиномиальный
	алгоритм проверки простоты чисел . . . . . . . . . . . . . . . . .	48
Глава 2. Факторизация целых чисел с экспоненциальной
	сложностью . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	57
§ 2.1.	Введение. Метод Ферма . . . . . . . . . . . . . . . . . . . . . . . . . .	57
§ 2.2.	(P − 1)-метод Полларда . . . . . . . . . . . . . . . . . . . . . . . . . . .	60
§ 2.3.	-метод Полларда . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	62
§ 2.4.	Метод Шермана—Лемана . . . . . . . . . . . . . . . . . . . . . . . . .	65
§ 2.5.	Алгоритм Ленстры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	67
§ 2.6.	Алгоритм Полларда—Штрассена . . . . . . . . . . . . . . . . . .	73
§ 2.7.	(P + 1)-метод Уильямса и его обобщения . . . . . . . . . . .	74
§ 2.8.	Методы Шэнкса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	75
§ 2.9.	Прочие методы. Заключение . . . . . . . . . . . . . . . . . . . . . . .	76
Глава 3.	Факторизация целых чисел с субэкспоненциальной
	сложностью . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	77
§ 3.1.	Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	77
§ 3.2.	Метод Диксона. Дополнительные стратегии . . . . . . . . .	78
§ 3.3.	Алгоритм Бриллхарта—Моррисона . . . . . . . . . . . . . . . .	83
§ 3.4.	Квадратичное решето . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	87

4	Оглавление

§ 3.5.	Методы Шнорра—Ленстры и Ленстры—Померанса . .		92
§ 3.6.	Алгоритмы решета числового поля . . . . . . . . . . . . . . . . .		93
§ 3.7.	Заключение . . . . . . . . . . .	. . . . . . . . . . . . . . . . . . . . . . . . . .	107
Глава 4.	Применение кривых	для проверки простоты
	и факторизации . . . . . . .	. . . . . . . . . . . . . . . . . . . . . . . . . .	108
§ 4.1.	Введение. Эллиптические кривые и их свойства . . . . . .		108
§ 4.2.	Алгоритм Ленстры для	факторизации целых чисел
	с помощью эллиптических кривых . . . . . . . . . . . . . . . . . .		110
§ 4.3. Вычисление порядка группы точек эллиптической кри-
	вой над конечным полем .	. . . . . . . . . . . . . . . . . . . . . . . . .	115
§ 4.4.	Тестирование чисел на простоту с помощью эллипти-
	ческих кривых . . . . . . . . . .	. . . . . . . . . . . . . . . . . . . . . . . . .	124
§ 4.5.	Заключение . . . . . . . . . . . .	. . . . . . . . . . . . . . . . . . . . . . . . .	129
Глава 5.	Алгоритмы дискретного логарифмирования . . . . . .		130
§ 5.1.	Введение. Детерминированные методы . . . . . . . . . . . . . .		130
§ 5.2.	-метод Полларда для дискретного логарифмирования		132
§ 5.3.	Дискретное логарифмирование в простых полях . . . . .		134
§ 5.4.	Дискретное логарифмирование в полях Галуа . . . . . . . .		138

§5.5. Дискретное логарифмирование и решето числового поля 141

§5.6. Частное Ферма и дискретное логарифмирование по со-

ставному модулю . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 § 5.7. Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

Глава 6.	Факторизация многочленов над конечными полями 163
§ 6.1.	Введение. Вероятностный алгоритм решения алгебра-
	ических уравнений в конечных полях . . . . .	. . . . . . . . . . 163
§ 6.2.	Решение квадратных уравнений . . . . . . . . . . .	. . . . . . . . . 167
§ 6.3.	Алгоритм Берлекэмпа . . . . . . . . . . . . . . . . . . .	. . . . . . . . . 171
§ 6.4.	Метод Кантора—Цассенхауза . . . . . . . . . . . .	. . . . . . . . . 176
§ 6.5.	Некоторые другие усовершенствования	алгоритма
	Берлекэмпа . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . . . . . . . 179
§ 6.6.	Вероятностный алгоритм проверки неприводимости
	многочленов над конечными полями . . . . . . .	. . . . . . . . . 182
§ 6.7.	Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . . . . . . . 185

Глава 7.	Приведенные базисы решеток и их приложения . .	187
§ 7.1.	Введение. Решетки и базисы . . . . . . . . . . . . . . . . . . . . . .	187
§ 7.2.	LLL-приведенный базис и его свойства . . . . . . . . . . . . .	189

	Оглавление	5
§ 7.3.	Алгоритм построения LLL-приведенного базиса	ре-
	шетки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . . 191
§ 7.4.	Алгоритм Шнорра—Ойхнера и целочисленный LLL-
	алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 195
§ 7.5.	Некоторые приложения LLL-алгоритма . . . . . . . . . .	. . . 199
§ 7.6.	Алгоритм Фергюсона—Форкейда . . . . . . . . . . . . . . .	. . . 204
§ 7.7.	Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 217
Глава 8.	Факторизация многочленов над полем рациональ-
	ных чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 218
§ 8.1.	Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 218
§ 8.2.	LLL-алгоритм факторизации: разложение по простому
	модулю . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 220
§ 8.3.	LLL-алгоритм факторизации: использование решеток 221
§ 8.4.	LLL-алгоритм факторизации: подъем разложения .	. . . 226
§ 8.5.	LLL-алгоритм факторизации: полное описание . . . .	. . . 229
§ 8.6.	Практичный алгоритм факторизации . . . . . . . . . . . . .	. . . 231
§ 8.7.	Факторизация многочленов с использованием прибли-
	женных вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 233
§ 8.8.	Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 239
Глава 9.	Дискретное преобразование Фурье . . . . . . . . . . .	. . . 240
§ 9.1.	Введение. Дискретное преобразование Фурье и	его
	свойства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	. . . 240

§9.2. Вычисление дискретного преобразования Фурье . . . . . 242

§9.3. Дискретное преобразование Фурье и умножение мно-

гочленов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 § 9.4. Дискретное преобразование Фурье и деление много-

членов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 § 9.5. Применение дискретного преобразования Фурье в ал-

горитме Полларда—Штрассена . . . . . . . . . . . . . . . . . . . . 252 § 9.6. Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254

Глава 10. Целочисленная арифметика многократной точности 255

§ 10.1. Введение. Сложение и вычитание . . . . . . . . . . . . . . . . . .	255
§ 10.2. Умножение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	256
§ 10.3. Деление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	260
§ 10.4. Некоторые алгоритмы модулярной арифметики . . . . . .	271

6	Оглавление

Глава 11. Решение систем линейных уравнений над конеч-
ными полями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	275
§ 11.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	275

§11.2. Решение систем линейных уравнений в целых числах . 276

§11.3. Гауссово и структурированное гауссово исключение . . 281

§ 11.4. Алгоритм Ланцоша . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 § 11.5. Алгоритм Видемана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 § 11.6. Другие методы. Заключение . . . . . . . . . . . . . . . . . . . . . . . 292

Приложение. Сведения из теории чисел . . . . . . . . . . . . . . . . . . . 293 Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323

Предисловие

Данная книга посвящена алгоритмической теории чисел — интенсивно развивающемуся последние тридцать лет направлению в теории чисел, имеющему важные приложения в криптографии. Актуальность этого направления неизмеримо увеличилась в 70-е годы XX века в связи с появлением криптосистем Диффи—Хеллмана и RSA. В настоящее время, по некоторым оценкам, практически весь мировой парк средств асимметричной криптографии в математическом плане основан на тео- ретико-числовых задачах.

Для целей криптографии (как для практической реализации и обоснования стойкости криптографических средств, так и для разработки методов их вскрытия) необходимо в первую очередь повышать эффективность следующих методов и алгоритмов:

•алгоритмы проверки простоты целых чисел;

•методы факторизации (т. е. методы поиска разложения целых чисел на множители);

•вычисления, использующие эллиптические кривые над конечными полями;

•алгоритмы дискретного логарифмирования;

•методы разложения многочленов на множители над конечными полями и над полем рациональных чисел;

•способы решения систем линейных уравнений над конечными полями;

•алгоритмы для выполнения арифметических операций с большими целыми числами;

•алгоритмы полиномиальной арифметики.

В нашей книге мы стремились представить современное состояние алгоритмической теории чисел, стараясь при этом дать достаточно аккуратные обоснования описываемых алгоритмов. Некоторые наиболее сложные и объемные алгоритмы и методы (такие, как проверка простоты чисел с помощью тригонометрических сумм, алгоритмы решета числового поля) мы приводим лишь на идейном уровне, в виде некоторых общих схем. Мы также старались (хотя бы обзорно) охватить современные работы по данной тематике как можно более

8 Предисловие

полно. Заинтересованный читатель может пополнить наш список литературы, обратившись к книгам [60; 101], а также к интернет-сайтам www.cryptography.ru; www.math.uga.edu/~ntheory.

Данная книга написана на основе спецкурсов по алгоритмической теории чисел, которые автор читал на механико-математическом факультете МГУ им. М. В. Ломоносова с 1993 по 2001 год. Кроме того, в течение ряда лет автор руководил спецсеминарами по теорети- ко-числовым алгоритмам в МГУ, последние годы — межведомственным спецсеминаром «Теоретико-числовые алгоритмы в криптографии» на кафедре информационной безопасности МГУ (совместно с академиком Академии криптографии Российской Федерации В. М. Сидельниковым). Ряд результатов, приведенных в данной книге, был получен автором в сотрудничестве с лабораторией по математическим проблемам криптографии МГУ им. М. В. Ломоносова.

Эта книга не является книгой по элементарной математике. Для ее чтения требуется достаточно серьезная подготовка, например, в объеме первых двух-трех курсов математического факультета университета.

Мы предполагаем, что читатель знаком с теорией чисел в объеме книги И. М. Виноградова «Основы теории чисел» (любое издание). Для чтения некоторых параграфов требуется знание теории непрерывных (цепных) дробей, см., например, книги [41; 29]. Для удобства читателя мы поместили основные определения и факты в Приложение. Для чтения некоторых параграфов требуется знание основ теории конечных полей, изложенной, например, в книге [31], а также знание основ алгебраической теории чисел, см., например, книгу [9]. В некоторых параграфах требуется более глубокое знание алгебраической теории чисел; в таких местах мы даем ссылки на соответствующую литературу. Из учебных пособий по криптографии мы рекомендуем книгу [3].

Во многих описываемых алгоритмах в качестве вспомогательных используются алгоритмы нахождения наибольшего общего делителя целых чисел и алгоритмы возведения в натуральную степень. Эти алгоритмы общеизвестны и изложены в различных книгах, см., например, [25; 89; 60]. Мы приводим эти алгоритмы в Приложении, некоторые без обоснования корректности.

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

Сложность алгоритма — это количество выполняемых им арифметических операций. Обычно сложность алгоритма представляют

Предисловие

9

в виде какой-либо функции от длины входа, т. е. от количества битов N, требуемых для записи входных данных. Если эта функция — многочлен от N, то говорят, что алгоритм имеет полиномиальную

сложность (полиномиальный алгоритм);		если эта функция име-
ет вид	LN [ ; c] = e(c+o(1)) (log N) (log log N)1− ,	где 0 < < 1, c = const,
c > 0, то	оценка сложности алгоритма называется субэкспоненци-

альной с показателем ; если функция имеет вид ecN, где c = const, то алгоритм имеет экспоненциальную сложность. Пусть, например, n N и мы хотим разложить n на множители. Длина входа равна N = [log2 n] + 1 = O(log n). Полиномиальный алгоритм факторизации имеет поэтому сложность O((log n)c), субэкспоненциальный — сложность e(c+o(1)) (log n) (log log n)1− , экспоненциальный — сложность O(nc).

Мы называем число B-гладким, если все его простые делители не превосходят B (здесь B — некоторое положительное число, называемое границей гладкости). Целое число называется B-степенно- гладким, если все его примарные делители (степени простых чисел) не превосходят B.

Через log x мы обозначаем натуральный логарифм положительного числа x.

Автор благодарит А. А. Сальникова, В. В. Ященко и Д. В. Матюхина за помощь в работе над книгой, неоднократные обсуждения и многочисленные советы по улучшению содержания рукописи.

Автор также благодарит Д. В. Матюхина за огромную работу по научному редактированию рукописи.

Обозначения

N			множество натуральных чисел;
Z			кольцо целых чисел;
Z a			множество целых чисел, больших или равных a;
R			поле действительных чисел;
R a			множество действительных чисел, больших или рав-
			ных a;
C			поле комплексных чисел;
P			множество простых чисел;
|S|, #S			количество элементов в множестве S;
Re			действительная часть числа ;
Im			мнимая часть числа ;
a | b			a делит b;
a b			a не делит b;
p	k		p	k	делит a, но p	k+1	не делит a;
		. a
b		.	b делится на a (нацело);
		. a
a (b)			наибольшее k Z 0 такое, что ak | b;

(a, b), НОД(a, b) наибольший общий делитель a и b, где a и b— целые

	числа или многочлены над некоторым полем;
[a, b], НОК(a, b) наименьшее общее кратное a и b;
[a]	целая часть числа a;
a	целая часть сверху, т. е. наименьшее n Z, для ко-
{a}	торого n a;
	дробная часть числа a;
const	какая-либо положительная постоянная;
n 10k	натуральное число n записывается k десятичными
a ≡ b (mod c)	цифрами;
	a − b делится на c в рассматриваемом кольце (це-
a ≡ b (mod c)	лых чисел или многочленов);
	a − b не делится на c;

Обозначения

11

Z/pZ, GF(p), Zp

GF(q)

Z/nZ

(Z/nZ)

R

g n

ord a char K

(n)

a , a p m

(x)

log x

i j

Lx [ ; c]

MT rank M

Lоб (b1, . . . , bn)

L

K [x1, . . . , xn]

deg f(x)

Res(f(x), g(x)) y := x

поле из p элементов, где p — простое число;

поле из q элементов, где q — степень простого числа;

кольцо вычетов по модулю n;

группа обратимых по умножению элементов кольца

Z/nZ;

группа обратимых по умножению элементов кольца R;

циклическая группа из n элементов с образующим g;

порядок элемента a в конечной группе; характеристика поля K;

функция Эйлера от натурального числа n;

символы Лежандра и Якоби;

функция Чебышёва, равная количеству простых чисел, не превосходящих x;

натуральный логарифм x;

биномиальный коэффициент, число сочетаний из i по j;

e(c+o(1)) (log x) (log log x)1− , o(1) →0 при x→+∞, c и —

постоянные;

транспонированная матрица (или вектор) M;

ранг матрицы M;

линейная оболочка векторов b1, . . . , bn;

ортогональное дополнение к линейному подпространству L в евклидовом пространстве;

кольцо многочленов от переменных x1, . . . , xn над кольцом K;

степень многочлена f(x);

результант многочленов f(x) и g(x);

y присвоить значение x.