Теория чисел в криптографии

 
 
 
 
 
 
 
 
 
 
ТЕОРИЯ ЧИСЕЛ  
В КРИПТОГРАФИИ 
 
 
 
 
 
Допущено Учебно-методическим объединением вузов 
 по университетскому политехническому образованию  
в качестве учебного пособия  
для студентов высших учебных заведений, обучающихся  
по направлению «Информатика и вычислительная техника» 
 
 
 
 
 
 
 

им. Н.Э. Баумана
МГТУ

ИЗДАТЕЛЬСТВО

 
 
Москва 2011 

УДК 511:003.26 (075.8) 
ББК 22.18 
        Т 33 

Авторы: 

В.А. Орлов, Н.В. Медведев, 
Н.А. Шимко, А.Б. Домрачева 

Рецензенты:  

д-р физ.-мат. наук, проф. В.К. Леонтьев;  
д-р техн. наук, проф. Е.Е. Тимонина, 

Теория чисел в криптографии : учеб. пособие / В. А. Ор- 
Т 33 лов, Н. В. Медведев, Н. А. Шимко, А. Б. Домрачева. – М. : 

 
Изд-во МГТУ им. Н. Э. Баумана, 2011. – 223, [1] с.  
 
ISBN 978-5-7038-3520-3 
 
Изложены основы математического аппарата, используемого в 
современной криптографии; показано его применение при анализе 
криптосистем и выборе их параметров. Особое внимание уделено 
вопросам построения криптосистем с открытым ключом. Описание 
большинства рассмотренных алгоритмов приведено в виде программ 
на языке программирования Си.  
Пособие соответствует курсам лекций, которые авторы читают в 
МГТУ им. Н.Э. Баумана и в МФТИ. 
Для студентов и аспирантов, изучающих дисциплины по ин-
формационной безопасности. 
 

УДК 511:003.26 (075.8)  
                                                                   ББК 22.18 

 
© Оформление. Издательство  
ISBN 978-5-7038-3520-3 
 
 
 
         МГТУ им. Н. Э. Баумана, 2011 

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

 

ПРЕДИСЛОВИЕ 

Цель учебного пособия – ознакомить читателей с основами ма-
тематического аппарата, используемого в современной криптогра-
фии, и продемонстрировать его применение при анализе крипто-
систем и выборе их параметров. 
Материал изложен в соответствии со стандартом дисциплины 
«Теоретико-числовые методы в криптографии» специальности 
«Компьютерная безопасность». 
Пособие состоит из семи глав. 
В криптографии важную роль играют простые числа. В главе 1 
рассмотрены основы теории делимости. Приведены простые (с 
методической точки зрения) алгоритмы выявления простоты числа 
и алгоритм нахождения всех простых чисел, не превосходящих 
заданного числа. Рассмотрены алгоритмы нахождения наибольше-
го общего делителя и представления наибольшего общего делите-
ля двух чисел в виде линейной комбинации (с целыми коэффици-
ентами) этих чисел. Показаны области использования непрерыв-
ных дробей в криптографии. Описаны важнейшие функции теории 
чисел, в том числе широко используемая в криптографии функция 
Эйлера. 
Важнейшим разделом теории чисел в современной криптогра-
фии является теория сравнения. В главе 2 доказаны важные для 
криптографии с открытым ключом теоремы Ферма и Эйлера о 
свойстве операции возведения в степень по заданному модулю. 
Исследовано нахождение решений сравнений первой степени и 
систем таких сравнений. В частности, доказана широко использу-
емая в современной криптографии Китайская теорема об остатках. 
Приведены алгоритмы нахождения символов Лежандра и Якоби, 
значения которых позволяют решить вопрос о разрешимости 
сравнений второй степени по простому модулю. 

В современной криптографии объектами преобразований яв-
ляются не только вычеты по простому модулю, но и более слож-

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

ные образования – конечные поля. В главе 3 рассмотрены основ-
ные свойства конечных полей. Для облегчения усвоения материала 
вначале даны более простые математические понятия. 

Оценки сложности алгоритмов, реализующих криптопреобра-
зования, и алгоритмов, используемых для нахождения параметров 
криптосистем, исследованы в главе 4. В основном в пособии кри-
терием сложности алгоритма является число используемых для его 
реализации двоичных операций. 
При построении современных криптосистем требуются очень 
большие простые числа. Например, в криптосистеме RSA и раз-
личных системах, основанных на задаче дискретного логарифми-
рования в конечных полях, используются «случайные» простые 
числа, записи которых в десятичной системе счисления состоят из 
сотен цифр. В главе 5 доказана теорема Чебышева о доле простых 
чисел и приведены другие результаты о распределении простых 
чисел в натуральном ряде. Затем определены различные понятия 
псевдопростоты числа. 
Вопросы применения теоретико-числовых методов в крипто-
графии рассмотрены в главе 6. На содержательном уровне описа-
ны основные проблемы и понятия криптографии. В традицион-
ной криптографии довольно часто используют преобразование 
(mod
),
y
ax
b
m
=
+
 которое называют линейным. Рассмотрено ис-
пользование таких преобразований для генерации псевдослучай-
ных последовательностей. 
Исследованы проблемы криптографии с открытым ключом и 
математический аппарат, на котором основана современная крип-
тография, – односторонние функции. Проведен анализ криптоси-
стем Эль-Гамаля и Рабина. 
Подробный анализ широко используемой криптосистемы RSA 
приведен в главе 7. 
Изучение курсов по информационной безопасности предпо-
лагает проведение практических занятий. В связи с этим в посо-
бии даны тексты программ, реализующих рассмотренные алго-
ритмы. Приведенные программы написаны на языке программи-
рования Си.  
Решение предлагаемых в пособии упражнений поможет более 
глубокому усвоению изложенного материала. 
В заключение отметим, что защита информации (особенно с 
использованием криптографии) является наиболее наукоемким 

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

разделом информатики. В связи с этим читатель должен прило-
жить усилия при освоении изложенного материала. 
При написании пособия использован опыт преподавания ряда 
дисциплин по информационной безопасности в МФТИ (ТУ) (Мос-
ковском физико-техническом институте) и в МГТУ им. Н.Э. Бау-
мана.  
Глава 3 написана Н.А. Шимко, глава 5 – Н.В. Медведевым, 
А.Б. Домрачевой, остальные главы написаны В.А. Орловым.  
Авторы выражают благодарность В.А. Конявскому, М.П. Сы-
чеву, А.С. Кузьмину за замечания, высказанные при подготовке 
учебного пособия. 
 

Введение 
6 

 

ВВЕДЕНИЕ 

Наибольший практический интерес представляет защита ин-
формации, находящейся в компьютере, с использованием про-
граммного обеспечения. 
При компьютерной обработке информация представляется в 
виде наборов из 0 и 1 (двоичных наборов). Каждому такому набо-
ру ставится в соответствие натуральное число, запись которого в 
двоичной системе счисления (двоичная запись) совпадает с этим 
набором. Таким образом, компьютерная обработка информации 
сводится к обработке натуральных чисел. 
В современной криптографии сообщения представляются сим-
волами некоторого конечного алфавита (или последовательностя-
ми таких символов). Этим символам ставят в соответствие числа 
от 0 до N – 1, где N – число элементов (мощность) алфавита. По-
этому шифрование и расшифровывание сообщений представляют 
собой преобразование натуральных чисел, меньших N. Разделом 
математики, предметная область которого – натуральные числа, 
является теория чисел. 
Таким образом, современная криптография связана с использованием 
результатов теории чисел, имеющей долгую историю развития. 
Ввиду конечности алфавитов сообщений важную роль играет 
раздел теории чисел – сравнения, в котором числа, имеющие 
одинаковые остатки от деления на фиксированное число (модуль), 
считаются одинаковыми. В качестве модуля естественно выбрать 
мощность алфавита сообщений. 
В традиционной криптографии с несложными преобразованиями (
простая замена, перестановка, гаммирование), не было 
необходимости применять глубокие результаты теории чисел. 
Ситуация изменилась с появлением криптосистем с открытым 
ключом, в основе которых лежат односторонние преобразования, 
например операция возведения в степень по огромным модулям. 

Введение 
7 

Аргументом преобразования шифрования является открытое 
сообщение, а функцией – зашифрованное сообщение (криптограмма). 

Авторами криптосистем с открытым ключом были американские 
ученые У. Диффи и М. Хеллман. Однако впервые она была 
реализована в виде системы RSA, название которой образовано 
начальными буквами фамилий авторов: Р. Райвест, А. Шамир, Л. Ад-
леман. 
В криптосистеме RSA используется степенная функция 

(mod
)
e
y
x
N
=
. 

При этом возникает задача выбора модуля N и степени e, та-
ких, что существует степень d, удовлетворяющая условию 

(mod
)
d
y
x
N
=
 

для любого 0
1.
x
N
≤
≤
−
 Кроме того, алгоритм вычисления по N и 
e степени d должен иметь очень большую сложность. 
Диффи и Хэллман предложили использовать показательную 
функцию  

(mod
).
x
y
a
N
=
 

В этом случае актуальна задача о подборе параметров a и N, 
обеспечивающих взаимную однозначность этой функции. Кроме 
того, алгоритм вычисления по N, a и y аргумента x должен иметь 
очень большую сложность. 
В криптографии важную роль играет умение строить алго-
ритмы, реализующие достаточно сложные преобразования и 
имеющие малую сложность. В пособии эти вопросы рассмотрены 
подробно. 
В современной криптографии обеспечение конфиденциально-
сти информации является самой простой задачей. Более сложной 
является, например, задача подписания электронного сообщения, 
придающая сообщению статус документа. С использованием 
криптосистемы RSA эта задача решается следующим образом.  

Введение 
8 

Для простоты изложения рассмотрим процедуру подписания 
сообщения, оставляя в стороне обеспечение его конфиденциаль-
ности. Пользователям, которые могут проверить подпись, числа 
N и e известны. Им посылается сообщение 
||
(mod
),
d
M
M
N
 где 
M – сообщение, а через || обозначена операция конкатенации 
(присоединения). Проверяющий вычисляет значение выражения 
(
(mod
)) (mod
)
d
e
M
N
N  и в случае совпадения этого значения с M 
признает подпись подлинной. Напомним, что нахождение по N и e 
степени d требует очень много времени. 
Недостатком описанной процедуры являются большие наклад-
ные расходы (размер подписи равен размеру подписываемого со-
общения). Для устранения этого недостатка используют крипто-
графические хэш-функции, при построении которых используются 
также теоретико-числовые методы. 
Конечно, при создании криптосистем важную роль играет тео-
рия вероятностей. Мы должны оценить вероятность того, что слу-
чайно выбранное число совпадет, например, со степенью расшиф-
ровывания в криптосистеме RSA. В пособии использованы только 
общеизвестные результаты теории вероятностей. 
Информация может являться очень ценным продуктом, в этом 
случае ее защита весьма актуальна. Как известно, защиту информации 
можно осуществить двумя способами: ограничить доступ к 
неизменяемой информации или преобразовать информацию известным 
только законным пользователям способом (зашифровать). 
В современных условиях глобализации бизнеса информацию приходится 
передавать по незащищенным каналам связи и второй 
способ имеет несомненное преимущество. 
В пособии рассмотрены теоретико-числовые методы, используемые 
при создании современных систем защиты конфиденциальной 
информации. Особое внимание уделено вопросам построения криптосистем 
с открытым ключом. Эти криптосистемы помимо стойкой 
защиты данных от попыток ознакомления с ними позволяют решать 
более сложные задачи: проверку целостности данных, установление 
источника сообщений (аутентификация) и, таким образом, невозможность 
отказа от авторства сообщения (цифровая подпись). Цифровая 
подпись играет важную роль в обеспечении надежного оборота 
электронных документов. 

1.2. Простые числа 
9 

 

ГЛАВА 1. ОСНОВЫ ТЕОРИИ ДЕЛИМОСТИ 

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

1.1. Основные понятия и теоремы 

Под числом, если не оговорено иное, будем понимать целое 
число, т. е. натуральное число (положительное целое), нуль и 
натуральное число со знаком минус (отрицательное целое). 
Сумма, разность и произведение двух целых чисел являются 
целыми числами. Частное от деления двух целых чисел (делитель 
отличен от нуля) может быть как целым, так и нецелым. 
Если частное от деления a на b – целое число, то, обозначая его 
через c, получаем a = bc. В этом случае говорят, что a делится на b 
или b делит a. 

Глава 1. Основы теории делимости 
10

То обстоятельство, что b является делителем числа a, записывается 
так: b│a. При этом также говорят, что a кратно b. 
Отметим, что нуль кратен любому целому числу a, так как 0 =  
= a·0. 
Приведем две следующие теоремы. 
Теорема 1.1. Если a кратно b, b кратно c, то a кратно c. 
Доказательство. Из условия теоремы имеем a = a1b и b = b1c, 
где a1 и b1 – целые. Отсюда получаем a = a1b1c, где a1b1 – целое. 
Теорема доказана. 
Теорема 1.2. Если в равенстве вида k +l + … + n = p + q + 
+ … + s все члены, кроме какого-либо одного, кратны b, то и этот 
член кратен b. 
Доказательство. Пусть таким членом будет k. Имеем 
l = l1b, …, n = n1b, p = p1b, q = q1b, …, s = s1b, 
k = p + q +… + s – l – … – n = (p1 + q1 + s1 – l1 – … – n1)b. 
Теорема доказана. 
В теории чисел широко используется следующая теорема. 
Теорема 1.3. Любое целое число a представляется единствен-
ным образом через произвольное натуральное число b в виде 

a = kb + r, 0 ≤ r < b. 

Доказательство. Одно из представлений числа a в такой форме 
получим, положив kb равным наибольшему кратному числа b, не 
превосходящему a. Допустим, что имеется другое представление 
числа a такого вида: a = k1b + r1, 0 ≤ r1 < b. Почленным вычитанием 
этих представлений получаем соотношение 0 = (k – k1)b + r –  
– r1. Из этого соотношения по теореме 1.2 следует, что r – r1 крат-
но b (0 кратен любому целому числу). Очевидно, что |r – r1| < b. 
Следовательно, r – r1 = 0, т. е. r = r1. Отсюда вытекает равенство k =  
= k1. Теорема доказана. 
Число k в представлении a = kb + r, 0 ≤ r < b, называется не-
полным частным, а число r – остатком от деления a на b. Отме-
тим, что во всех универсальных языках программирования име-
ются операторы нахождения неполного частного и остатка от де-
ления. 
Пример. Пусть b = 14. Имеем 

177 = 12 ⋅14 + 9, 0 ≤ 9 < 14,