08.04.09.Печать_edit

Федеральное агентство по образованию

–––––––——————————–––––––

Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»

————————————————————

Е. С. ДЕРНОВА, Н. А. МОЛДОВЯН, П. А. МОЛДОВЯНУ

Элементы теоретических основ криптографии

Учебное пособие

Санкт-Петербург Издательство СПбГЭТУ «ЛЭТИ»

2009

Дернова Е. С., Молдовян Н. А., Молдовяну П. А.

Элементы теоретических основ криптографии: Учеб. Пособие. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2009. 96 с.

ISBN 0-0000-0000-0

Данное учебное пособие ориентировано на использование в учебном процессе по подготовке специалистов в области компьютерной безопасности, информационных технологий и систем телекоммуникаций при преподавании дисциплин «Теоретические основы криптографии», «Криптографические протоколы» и «Криптографические методы защиты информации». Оно включает минимум сведений из теории чисел и алгоритмов решения сложных вычислительных задач, используемых для построения криптосистем с открытым ключом. Освоение данного материала позволяет понять детали синтеза алгоритмов открытого шифрования и электронной цифровой подписи, нашедших широкое применение в практике информационной безопасности и технологиях электронного документооборота. Для закрепления теоретических знаний включен раздел, содержащий список задач для решения на практических занятиях и примеры решения задач.

Рецензенты:

Учреждено

редакционно-издательским советом СПбГЭТУ «ЛЭТИ» в качестве учебного пособия

2

Содержание
ГЛАВА 1. Элементы теории чисел .................................................................	5
1.1. Некоторые определения и утверждения ................................................	5
1.2. Функция Эйлера .......................................................................................	8
1.3. Алгоритм Евклида..................................................................................	11
1.4. Расширенный алгоритм Евклида..........................................................	12
1.5. Показатели и первообразные корни.....................................................	14
1.6. Теоремы о числе классов с заданным показателем ............................	19
1.7. Китайская теорема об остатках ............................................................	23
1.8. Алгоритм возведения в степень по модулю........................................	25
1.9. Нахождение чисел, относящихся к заданному простому показателю27
1.10. Теоремы о числе решений степенных сравнений.............................	29
ГЛАВА 2. Алгоритмы двухключевой криптографии ..............................	37
2.1. Генерация простых чисел......................................................................	37
2.2. Детерминистическая генерация больших простых чисел .................	39
2.3. Извлечение корней по модулю .............................................................	42
2.3.1. Вычисление квадратных корней..................................................	42
2.3.2. Извлечение корней степени n > 2 по простому модулю ...........	48
2.3.3. Случай модуля, равного степени простого числа......................	54
2.4. Трудный случай извлечения корней по простому модулю ...............	57
2.4.1. Модуль со специальной структурой ...........................................	57
2.4.2. Вычисление корня большой простой степени ...........................	58
2.4.3. Сведение трудных случаев извлечения корней к задаче
дискретного логарифмирования ....................................................	64
2.5. Алгоритмы факторизации .....................................................................	64
2.5.1. Факторизация B-гладкого модуля RSA......................................	64
2.5.2. Факторизация модуля RSA с использованием метода Флойда 66
2.6. Методы дискретного логарифмирования ............................................	68
2.6.1. Оптимизация переборного метода ..............................................	68
2.6.2. Метод вычисления индексов........................................................	70
2.6.3. Метод Полларда ............................................................................	73
2.6.4. Случай составного порядка..........................................................	75
Глава 3. Задачник.............................................................................................	78
3.1. Примеры решения задач........................................................................	78
3.2. Задачи для самостоятельного решения................................................	83

3

Cписок литературы..........................................................................................

95

4

ГЛАВА 1. Элементы теории чисел

1.1. Некоторые определения и утверждения

Детальное рассмотрение приводимых здесь фрагментов теории чисел можно найти в работах [1, 2].

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

единицу и само на себя. Иными словами, простым называется число p 3,

которое не делится без остатка ни на одно из следующих чисел 2, 3, …, p – 1. Число 2 также является простым.

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

Сокращение в сравнениях множителей, являющихся взаимно простыми с модулем, основано на следующем утверждении.

Утверждение 1

Если НОД(a, n) = 1 и (a b) (a c) mod n, то b c mod n.

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

Из сравнения (a b) (a c) mod n следует: ab – ac 0 mod n a(b – c) = Qn, где Q — целое положительное число или 0. Если Q = 0, то утверждение выполняется. Если Q 0, из равенства a(b – c) = Qn следует, что в правой части содержится множитель n, который может содержаться только в значении b – c, поскольку a и n являются взаимно простыми числами, т. е. не содержат общих множителей, кроме 1. Таким образом, b – c = qn, где q — целое положительное число, т. е. b c mod n.

Пользуясь доказанным выше утверждением, докажем следующее.

О существовании обратного элемента

Утверждение 2

5

Для любого целого числа a 0 взаимно простого с модулем n существу-

ет обратное по mod n число, обозначаемое знаком a –1, такое что a a –1

1 mod n. Число a –1 называется мультипликативно обратным по модулю n.

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

Рассмотрим множество значений {1, 2, …, n – 1}. Умножая каждое из них на a по mod n, получаем множество {(a mod n), (2a mod n), …, ((n – 1) a mod n)}, которое содержит по одному разу числа 1, 2, …, n – 1, т. е. для некоторого значения i выполняется условие ia mod n = 1. Это вытекает из противоречия, возникающего при предположении о существовании двух одинаковых значений. Пусть, например, ha mod n = ka mod n. Тогда с учетом условия НОД(a, n) = 1 из последнего условия получаем h k mod n h = k. Последнее противоречит тому, что мы умножали на a только различные числа. Указанное значение i и является мультипликативно обратным (к числу a) элементом по модулю n.

Следствие 1

Если модуль p является простым числом, то для любого числа 0 a p существует мультипликативно обратный элемент по модулю p.

Можно показать, что если НОД(a, n) 1, то не существует числа b, такого что ab 1 mod n. Действительно, пусть НОД(a, n) = d, т. е. a = dq и n = dp. Умножая на a по модулю n каждое число из множества значений {1, 2, …, dp – 1}, получим следующий ряд остатков {(a mod n), (2a mod n), …, ((dp – 1) a mod n)}. Покажем, что каждый из этих остатков делится без остатка на d, т. е. содержит множитель d. Возьмем любое число b, такое что 0 b dp, и вычислим остаток от деления ab на n: r = ab – Qn = dqb – Qdp = d(qb – Qp), где Q — некоторое натуральное число. Из равенства r = d(qb – Qp) следует, что остаток r делится на d. (Одновременно мы доказали утверждение о делимости остатка, которое сформулировано ниже.) Таким образом, в указанном ряде n – 1 остатков содержатся только остатки, делящиеся нацело на d. Поскольку среди них нет 1, то это означает, что не существует числа b, при котором ab 1 mod n. Что мы и хотели показать.

6

О делимости остатка

Утверждение 3

Пусть для целых положительных чисел a и b имеем a b и НОД(a, b) = d,

тогда для остатка r от деления a на b выполняется равенство НОД(b, r)= d.

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

Теорема Ферма

Теорема Ферма утверждает следующее: для любого простого числа p и любого положительного числа a, которое не делится на p, выполняется сравнение

a p –1 1 mod p.

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

Рассмотрим множество чисел {1,2, …, p – 1}, которое обозначим как Zp.

Если все элементы Zp умножить на a по модулю p, то, используя утверждение 1, легко показать, что в результате получим некоторую перестановку

элементов	Zp. Иными	словами,	в наборе	{a mod p, 2a mod p, ..., (p –
1)a mod p}	содержится (p – 1) различных чисел, т. е. каждое из				чисел
1, 2, ..., p – 1	встречается	ровно по	одному	разу. Перемножая	числа

a, 2a, ..., (p – 1)a, получаем:

a 2a … (p – 1)a = (p – 1)! a p –1.

Поделив на p левую и правую части последнего соотношения, получим:

[a 2a … (p – 1)a] mod p (p – 1)! a p –1 mod p;

[(a mod p) (2a mod p) … ((p – 1)a mod p)] mod p (p – 1)! a p –1 mod p.

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

[(a mod p) (2a mod p) … ((p – 1)a mod p)] = = 1 2 … (p – 1) = (p – 1)!

7

Из последних двух соотношений следует

(p – 1)! (p – 1)! a p – 1 mod p.

Числа (p – 1)! и p являются взаимно простыми, поэтому в последнем выражении на основании утверждения 1 можно левую и правую части сократить на (p – 1)!, откуда вытекает сравнение

a p –1 1 mod p.

Теперь не представляет труда вывести следующие формулы: a p a mod p и

b c mod (p – 1) a b a c mod p.

1.2.Функция Эйлера

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

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

Очевидно, что для простого p имеем (p) = p – 1. Используя утверждение о мультипликативности функции Эйлера, для числа n = pq, являющегося произведением двух простых чисел p и q, можно легко получить

(n) = (pq) = (p) (q) = (p – 1) (q – 1).

Эту частную формулу легко получить и без использования свойства мультипликативности функции Эйлера. Действительно, рассмотрим множе-

ство чисел {1, 2, …, (pq – 1)}. Нетрудно заметить, что все числа, которые не превышают значение pq и не являются взаимно простыми с pq = n, составляют следующие два множества {p, 2p, …,(q – 1)p} и {q, 2q, …, (p – 1)q}. В

первом содержится q – 1, а во втором p – 1 различных чисел. Вычитая из n – 1

значения q – 1 и p – 1, получим

(n) = pq – 1 – (q – 1) – (p – 1) = pq – (p + q) + 1 = (p – 1) (q – 1).

Однако в общем случае, когда в каноническом разложении числа n содержится сравнительно большое число простых сомножителей и их степеней,

8

при вычислении функции Эйлера используется то, что она является мультипликативной функцией, т. е. для двух взаимно простых чисел a и b выполняется соотношение (ab) = (a) (b).

Поскольку в каноническом разложении произвольного числа n содержатся только взаимно простые сомножители вида p s, где s 1, то для вычисления функции Эйлера достаточно научиться вычислять функцию Эйлера от

чисел вида p s и уметь разлагать число n на простые множители.
Пусть	дано	число	p s.	Рассмотрим	множество	чисел

{1, 2, …, p, …, 2p, …, 3p, …, p s –1p}. Нетрудно заметить, что все числа, вхо-

дящие в это множество и не являющиеся взаимно простыми с p s, составляют

подмножество {p, 2p, 3p,…, p s –1p} из p s –1 чисел. Отсюда получаем

(p s) = p s – p s –1 = p s –1(p – 1).

Используя эту формулу и свойство мультипликативности, можно легко вычислить функцию Эйлера от произвольного заданного числа, если нам удастся разложить его на множители.

Теорема Эйлера

Теорема Эйлера, являющаяся обобщением теоремы Ферма, утверждает, что для любых взаимно простых чисел a и n выполняется сравнение

a (n) 1 mod n.

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

Доказательство аналогично доказательству теоремы Ферма. Поскольку для простого n имеем (n) = (n – 1), то в этом случае сравнение

a (n) 1 mod n непосредственно следует из теоремы Ферма (является просто другой формой записи последней). Доказательство для произвольного n опирается на определение функции Эйлера: (n) равно числу положительных целых чисел, меньших n и взаимно простых с n. Множество таких целых чисел включает (n) значений, которые можно пронумеровать следующим образом:

= {x1, x2, …, x (n)}.

9

Умножая каждый элемент этого множества на a по модулю n, получим множество

= {(ax1 mod n), (ax2 mod n), … , (ax (n) mod n)}.

Покажем, что последние два множества включают одни и те же элементы. Действительно, для всех значений i = 1, 2, …, (n) числа a и xi являются вза-

имно простыми с n, поэтому число axi тоже является взаимно простым с n. Следовательно, все элементы являются целыми числами, меньшими n (умножение мы выполняли по модулю n) и взаимно простыми с n. В множественет повторений, так как если (a b) (a c) mod n, то b с mod n, поскольку по условию доказываемой теоремы a и n являются взаимно простыми числами. Действительно, из условия axi mod n = axj mod n следует xi = xj, что противоречит тому, что в множестве все числа различны. Таким образом, множества и содержат одни и те же элементы. Перемножая все элементы множества , а затем все элементы множества , получаем равенство

		n		n
		axi mod n xi ,
		i 1		i 1
из которого следуют сравнения
n	n	n		n	a (n) 1 (mod n).
axi xi mod n ,		a n xi		xi mod n ,
i 1	i 1			i 1
		i 1
Из последнего сравнения вытекают следующие соотношения:
	a (n) +1 a mod n и		b c mod (n) a b a c mod n.

Обобщенная теорема Эйлера

Обобщенной функцией Эйлера называется функция L(n), определенная для всех натуральных чисел следующим образом: L(1) = 1, а при n > 1

L n HOK p1 1 1 p1 1 ; p2 2 1 p2 1 ; ... ; pk k 1 pk 1 ,

где n p1 1 p2 2 ... pk k и НОК — наименьшее общее кратное.

Обобщенная теорема Эйлера гласит: Если НОД(a, n) = 1, то

aL n 1 mod n .

10