Teoria_chisel_i_kriptozashita

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ И КРИПТОЗАЩИТА

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

Составители: Б. Н. Воронков, А. С. Щеголеватых

Издательско-полиграфический центр Воронежского государственного университета

2008

Утверждено научно-методическим советом факультета прикладной математики, информатики и механики 27 февраля 2008 г., протокол № 6

Рецензент канд. физ.-мат. наук, доц. К. П. Лазарев

Учебное пособие подготовлено на кафедре технической кибернетики и автоматического регулирования факультета прикладной математики, информатики и механики Воронежского государственного университета.

Рекомендуется для студентов 4-го курса дневного отделения и 4-го курса вечернего отделения.

Для специальности 010501 — Прикладная математика и информатика

2

СОДЕРЖАНИЕ

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

1.Основные понятия и определения……………………………….. 6

2.Элементы теории чисел и модулярная арифметика…………….. 10

2.1.Малая теорема Ферма. Теорема Эйлера …………………... 15

2.2.Квадратичные вычеты и закон взаимности.……………….. 21

2.3.Вычисление обратных по модулю величин………………... 24

2.4.Сравнениеарифметических операцийпоихтрудоемкости...... 26

2.5.Нахождение простых чисел…………………………………. 32

3.Формальное определение криптосистемы……………………..... 35

4.Криптосистема Эль Гамаля……………………………………..... 36

5. Криптосистема RSA (R. Rivest, A. Shamir, L. Adleman)……...… 37

6.Методы распределения криптографических ключей…….……... 43

6.1.Распределение секретных ключей с обеспечением конфиденциальности и аутентификации…………………...….... 48

7.Криптография с использованием эллиптических кривых…….... 52

7.1.Аналог обмена ключами по схеме Диффи-Хеллмана ……... 59

7.2.Протокол обмена ключами по схеме Месси-Омуры…..….. 60

7.3.Протокол распределения ключей

Менезеса-Кью-Ванстона (MQV-протокол)……………………	61
7.4. Протокол Эль Гамаля для криптосистемы
с использованием эллиптических кривых…....................……...	62
7.5. Обоснование протоколов с использованием
модулярной арифметики…………………………………….........	63

8.Цифровая подпись………………………………………..……….. 65

8.1.Стандарт DSS, алгоритм DSA………………………………. 65

8.2.Обобщенная схема цифровой подписи Эль Гамаля……….. 67

8.3.Схема цифровой подписи Эль Гамаля с возвратом сооб-

щения……………………………………………………...………. 68

3

8.4. Цифровая подпись с использованием точек эллиптической кривой………………….……………………...... 69

9.Модели атаки нарушителя………………………………………... 70

10.Модель несанкционированной подмены передаваемой информации…………………...……………………………………… 71

Библиография…………………………………………………… 87

4

Предисловие

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

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

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

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

5

1. Основные понятия и определения

Источники основных понятий и определений :

ГОСТ Р 50922-96 Защита информации: термины и определения. Госстандарт России.

ГОСТ Р 51583-00 Защита информации. Порядок создания автоматизированных систем в защищенном исполнении. Общие положения. Госстандарт России.

ГОСТ Р 51624-00 Защита информации. Автоматизированные системы в защищенном исполнении. Общие требования. Госстандарт России.

ОСТ 45.127-99. Система обеспечения информационной безопасности ВзаимоувязаннойсетисвязиРоссийской Федерации. Терминыиопределения.

Информация — сведения о лицах, предметах, фактах, событиях, явлениях и процессах независимо от формы их представления.

Сообщение — информация, представленная в определенной форме. Формы представления разнообразны: письменный текст, речь, музыка, графическое изображение, электромагнитное поле, взаимное расположение предметов в пространстве и т. д.

Дискретные сообщения — сообщения, вырабатываемые дискретными источниками, среди которых выделяются источники цифровой информации.

Дискретная информация — информация, зафиксированная в дискретном сообщении.

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

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

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

Информационная безопасность — состояние информации, инфор-

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

Информационные ресурсы — документы, массивы документов (архивы, фонды), программы для ЭВМ, базы данных, существующие отдельно или в составе информационных систем.

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

6

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

Закрытая информация содержит государственную, коммерческую или иную тайну.

Секретная информация содержит государственную тайну.

Конфиденциальная информация — служебная, профессиональная,

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

Защищаемая информация — информация, являющаяся предметом собственности и подлежащая защите в соответствии с требованиями правовых документов или требованиями, устанавливаемыми собственниками информации.

Утечка информации — неконтролируемое распространение защищаемой информации.

Утечки трех видов: а) разглашение,

б) несанкционированный доступ к информации, в) разведка.

Уничтожение информации — утрата информации при невозможности ее восстановления.

Блокировка информации — невозможность ее использования при сохранности.

Модификация информации — изменение ее содержания по сравнению с первоначальной.

Цена информации — полезность информации для участников информационного рынка.

Ценность информации — полезность информации для ее владельца (пользователя).

Угрозы информации:

а) нарушение конфиденциальности — потеря ценности информации при ее раскрытии;

б) нарушение целостности — потеря ценности информации при ее модификации или уничтожении;

в) нарушение доступности — потеря ценности информации при невозможности ее оперативного использования;

г) нарушение устойчивости к ошибкам — потеря ценности информации при сбоях в информационных системах.

7

Эффективность защиты информации — мера соответствия уров-

ня информационной безопасности требованиям при заданном ресурсе на ее защиту.

Политика безопасности — набор документированных норм, правил и практических приемов, регулирующих управление, защиту и распределение информации ограниченного доступа.

Структурная схема системы связи представлена на рис. 1.

1	2	3	4
		5

Канал (среда)

Рис. 1. Общая структурная схемасистемы связи: 1 — источник информации; 2 — передатчик; 3 — приемник; 4 — адресат(получатель); 5 — источник шумаипомех.

Телекоммуникационная система — система связи, в которой пере-

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

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

Криптосистема — система, реализованная программно, аппаратно или программно-аппаратно и осуществляющая криптографическое преобразование информации.

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

Совокупность криптографии и криптоанализа образует новую нау-

ку — криптологию

8

Текст — набор элементов алфавита имеющий определенный логический смысл. Открытый текст (ОТ) — исходное, шифруемое сообщение.

Ключ — информация, необходимая для беспрепятственного шифрования или расшифрования текстов.

Обычно ключ — последовательность символов того же алфавита, в котором набрано сообщение. Пространство ключей — набор всевозможных значений ключа.

Дешифрование — нахождение ключа или открытого текста на основе шифрованного текста.

Расшифрование — нахождение открытого текста на основе известного ключа и шифра.

Криптостойкость –— характеристика шифра, определяющая его стойкость к дешифрации. Часто криптостойкость измеряется количеством операций, необходимых для перебора всех возможных ключей, или интервалом времени, необходимого для дешифрования (MIPS-годы).

MIPS (Million Instructions Per Second) — миллион инструкций в секунду.

Криптограмма — шифрованный текст (ШТ).

Основная идея шифрования — скрытие смысла передаваемого сообщения.

Выделяют два класса криптосистем:

●симметричные (одноключевые) криптосистемы;

●асимметричные (двухключевые) криптосистемы.

Методы симметричного шифрования: 1. Перестановки. 2. Подстановки. 3. Гаммирование. 4. Аналитическое преобразование шифруемых данных.

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

		7
1	2	6	3	4

5

Рис. 2. Структурная схема передачи шифрованных сообщений: 1 — отправитель; 2 — устройство шифрования; 3 — устройство расшифрования; 4 — получатель; 5 — перехватчик (злоумышленник); 6 –– канал связи; 7 –– генератор ключей.

9

Алфавит — конечное множество используемых для шифрования знаков.

Z33 — 32-буквенный русский алфавит и пробел.

Z256 — расширенный ASCII (American Standard Code for Information Interchange – Американский стандарт кодирования для обмена информаци-

ей (KOИ8)).

Z2 — {0;1}.

Иногда смешивают два понятия: шифрование и кодирование. Для шифрования надо знать открытый текст, алгоритм шифрования и секретный ключ. При кодировании нет ничего секретного, есть только замена символов открытого текста или слов на заранее определенные символы. Методы кодирования направлены на то, чтобы представить открытый текст в более удобном виде для передачи по телекоммуникационным каналам, уменьшения длины сообщения (архивация), повышения помехоустойчивости (обнаружение и исправление ошибок) и т. д. В принципе кодирование, конечно же, можно рассматривать как шифр замены, для которого «набор» возможных ключей состоит только из одного ключа (например, буква «а» в азбуке Морзе всегда кодируется знаком « · » – и это не является секретом).

2. Элементы теории чисел и модулярная арифметика [1; 7; 10]

При разработке алгоритмов шифрования используется ряд понятий теории чисел и модулярной арифметики.

Теория чисел, или высшая арифметика, изучает свойства целых чисел. Как наука она оформилась, начиная с открытий П. Ферма. Под целыми числами понимают числа …, -4, -3, -2, -1, 0, 1, 2, 3, 4, … Особое место среди целых чисел занимают натуральные числа – целые положительные числа 1, 2, 3, 4, …

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

Мы назовём одно число a делителем другого числа b, если b = a c для некоторого числа c . Примем обозначение a /b, означающее, что a делит b нацело, или a является делителем b. Если число a не является делителем другого числа b, то используем обозначение: a не делит b.

Натуральное число p называется простым, если p > 1 и не имеет положительных делителей, отличных от 1 и p. Натуральное число N называется составным, если N > 1 и имеет, по крайней мере, один положительный делитель, отличный от 1 и N.

10