Криптографические методы защиты информации

Криптографические методы защиты информации

2-е издание, исправленное

Ушаков Ю.Ю.
Жданов О.Н.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Криптографические методы защиты информации/ Ю.Ю. Ушаков, О.Н. Жданов - М.: Национальный
Открытый Университет “ИНТУИТ”, 2016

В курсе дан необходимый теоретический минимум по основным вопросам современной
криптографии.

(c) ООО “ИНТУИТ.РУ”, 2017-2016
(c) Ушаков Ю.Ю., Жданов О.Н., 2017-2016

3

Основы теории чисел

В первой лекции мы приводим основные понятия теории чисел. Вводим определение
сравнимости по модулю и формулируем основные свойства сравнений. Таким образом
мы подготавливаем учащегося к освоению собственно криптографических тем.

1.1 Основы теории чисел

При необходимости более глубокого знакомства с материалом можно воспользоваться
любым из университетских учебников алгебры и теории чисел. Кроме того, имеются
пособия по криптографии, содержащие необходимый минимум теоретических
сведений в указанных областях. В частности, отметим пособие [1], особенно
полезными мы считаем главы 2 и 3 этой книги. Мы приводим краткие сведения из
теории и примеры решения некоторых задач по теории чисел.

1.1.1 Делимость

Будем считать известными свойства операций над целыми числами (сложения,
вычитания, умножения), понятие модуля целого числа и свойства модуля.

Рассмотрим свойства отношения делимости во множестве целых чисел, это множество
обозначается 
.

Определение 1.1 Целое число  делится на целое число , если существует такое целое
число , что 
. Число  называется делимым,  - делителем,  - частным.

Если число  делится на , то пишут 
 (  кратно ).

Отношение делимости 
 в 
 обладает следующими свойствами:

1. Для любого 
 имеем 
.

2. Отношение делимости транзитивно, т. е. из 
 и 
 следует 
.

3. Если 
, то 
, 
 и 
, т. е. отношение делимости сохраняется при

изменении знаков делимого и делителя.

4. Если 
 и 
, то 
.

5. Если 
 и 
, то 
.

Отметим, что утверждения, обратные 4 и 5, ложны: из делимости суммы не
вытекает делимость слагаемых, а из делимости произведения не вытекает
делимость сомножителей.

Например, 
 делится на 12, но ни 35, ни 13 не делятся на 12; 

делится на 12, но ни 3, ни 8 на 12 не делятся.

6. Если 
, а  не делится на , то 
 не делится на .

4

7. Нуль делится на любое число .
8. Любое число  делится на 1.
9. Если 
, то не существует такого , что 
.

10. Если 
, то 
.

1.1.2 Деление с остатком

Определение 1.2 Разделить целое число  на целое число 
 с остатком - это значит

найти два таких целых числа  и , чтобы выполнялись условия:

1. 
2. 
.

Число  называется неполным частным, а число  - остатком от деления  на .

Заметим, что остаток - всегда есть число неотрицательное, а вот неполное частное
может быть каким угодно целым числом. Поэтому на вопрос: “Сколько будет минус
пять поделить на три с остатком?”, правильный ответ: “Неполное частное минус два,
остаток - один”.

Теорема 1.1 Каковы бы ни были целое число a и целое число 
, всегда возможно, и

притом единственным способом, разделить  на  с остатком.

1.1.3 Наибольший общий делитель

Определение 1.3 Целое число 
 называется общим делителем целых чисел 

, если каждое из этих чисел делится на .

Определение 1.4 Целое число  называется наибольшим общим делителем чисел 

, если:

1. 
 является общим делителем этих чисел;

2. 
 делится на любой общий делитель чисел 
.

Теорема 1.2 Наибольший общий делитель чисел 
 определён однозначно с

точностью до знака (т.е. если 
 и 
 наибольшие общие делители чисел 
,

то либо 
, либо 
).

Условимся всегда рассматривать положительное значение наибольшего общего
делителя чисел 
. Обозначение: 
.

Пример 1.1 

Действительно, множество положительных делителей числа 
 есть 

, а для числа 
 такое множество имеет вид 

5

. Пересечение этих множеств 

. Число 
 является общим делителем чисел 
 и 
 и

делится на все остальные общие делители этих чисел. Значит, 
.

Заметим, что 
 - наибольший по величине положительный общий делитель чисел 

и 
.

Для любых целых чисел 
 их наибольший общий делитель является

наибольшим по величине положительным общим делителем.

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

1.1.4 Алгоритм Евклида

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

Алгоритм Евклида состоит в следующем. Сначала  делят на  (
). Если 
,

то 
. В противном случае 
. Делим  на 
. Если 
, то 

, но тогда и 
. Если  не делится на 
, то

получится остаток 
. Делим 
 на 
 и т.д.

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

Последний не равный нулю остаток является наибольшим общим делителем чисел  и

. Сформулируем это утверждение в виде теоремы.

Теорема 1.3 Если

, 

то 

Пример 1.2 Найдём 

6

.

Отсюда 
.

Следствие 1.1 (Следствие из теоремы 1.3) Пусть 
, 
, тогда

существуют такие целые числа  и , что 
. Другими словами, наибольший

общий делитель двух чисел можно представить в виде линейной комбинации этих
чисел с целыми коэффициентами.

Продолжение примера 1.2.

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

Теорема 1.4 Если 
 и 
, то 
.

Отметим еще одно свойство НОД. Если каждое из чисел  и  умножить на одно и то
же число 
, то их наибольший общий делитель умножится на .

1.1.5 Взаимно простые числа и их основные свойства

Определение 1.5 Если 
, то числа 
 называются

взаимно простыми.

Например, числа 30 и 77 взаимно просты, а числа 30 и 72 не являются взаимно
простыми, так как 
.

Теорема 1.5 Для того, чтобы числа  и  были взаимно простыми, необходимо и
достаточно, чтобы существовали такие целые числа  и , что 
.

Следствие 1.2 Если числа  и  взаимно просты и 
, 
, то числа 
 и 
 взаимно

просты.

И еще одно свойство: частные от деления чисел  и  на 
 взаимно просты.

1.1.6 Наименьшее общее кратное

Определение 1.6 Пусть 
 - целые числа, отличные от нуля. Целое число 

называется общим кратным этих чисел, если оно делится на каждое из данных чисел.

Например, произведение 
 - общее кратное всех своих сомножителей.

7

Определение 1.7 Целое число 
 называется наименьшим общим кратным чисел 

,если оно является их общим кратным и при этом любое общее кратное

этих чисел делится на 
.

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

Имеет место важная теорема.

Теорема 1.6 Число 
, где 
 - наибольший общий делитель двух

натуральных чисел  и , является наименьшим общим кратным этих чисел.

Рассмотрим основные свойства наименьшего общего кратного.

1. Если каждое из чисел  и  умножить на одно и то же число 
, то их НОК

умножится на .

2. Если 
 и 
, то

Пример 1.3 Найдем 
.

Разделим каждое из данных чисел на 
 (очевидный делитель) и найдём 
.

Имеем:

Тогда 
.

Для нахождения НОК нескольких чисел имеет правило, аналогичное рассмотренному
выше правилу нахождения НОД нескольких чисел.

Теорема 1.7 Если

то 
.

Иными словами, для нахождения НОК чисел 
 надо сначала найти 

, потом 
, и т.д. вплоть до 
. На каждом шаге

нам придется находить НОК двух чисел, а это мы уже умеем делать.

Пример 1.4 Найдем 
.

8

Ответ. 
.

Теорема 1.8 НОК попарно взаимно простых чисел равно их произведению.

Пример 1.5 Найдём 
.

Имеем 
, 
, 
. Следовательно, 

.

1.1.7 Простые и составные числа

Определение 1.8 Натуральное число  называется простым, если оно больше  и не
имеет положительных делителей, отличных от  и .

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

Согласно определению 1.2, если  - составное, то существует такой делитель , что 

, где 
, 
.

Число 1 не относят ни к простым, ни к составным числам.

Первыми простыми числами в натуральном ряду чисел являются 2, 3, 5, 7, 11, 13, 17,
19, 23, 31, 37, 41…

Среди простых чисел имеется лишь одно четное число 2.

Итак, множество всех натуральных чисел разбивается на три подмножества: 1) простые
числа, 2) составные числа, 3) число 1.

1.1.8 Разложение составных чисел на простые множители

Теорема 1.9 (основная теорема арифметики) Всякое натуральное число 
 либо

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

Отметим, что среди простых множителей числа могут встречаться одинаковые. Пусть,
например, 
 встречается 
 раз, 
 встречается 
 раз, …, 
 встречается 
 раз;

тогда разложение числа  на простые множители можно записать следующим
образом:

(1.1)

9

Множители 
 обычно располагают в порядке возрастания.

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

Пример 1.6 
.

Из канонического представления числа вытекают следующие предложения.

Следствие 1.3 Если 
 - каноническое разложение числа , то все

делители этого числа имеют вид:

где 
 
.

Пусть даны натуральные числа  и . Их каноническое разложение всегда можно
записать в виде:

Мы предполагаем здесь, что 
 и 
 могут принимать и нулевые значения. Это

позволит писать в обоих разложениях одни и те же простые числа 
, а

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

Следствие 1.4 Наибольший общий делитель чисел  и  имеет вид:

где 

Следствие 1.5 Наименьшее общее кратное чисел  и  имеет вид:

где 
.

Из этих свойств непосредственно следует тождество 
. Эти

утверждения переносятся и на случай более чем двух чисел.

1.1.9 Бесконечность множества простых чисел

Теорема 1.10 (Евклида) Множество простых чисел бесконечно.

Поучительно сравнить эту теорему и следующую.

10