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

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

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

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

 
 
Москва 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,