МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
( ФГБОУ ВО «ВГУ» )
КОНСПЕКТ ЛЕКЦИЙ
по курсу
«Математические основы защиты информации и
информационной безопасности»
ЭЛЕКТРОННОЕ УЧЕБНОЕ ПОСОБИЕ
Составители: Б. Н. Воронков,
Ю. А. Крыжановская
ВОРОНЕЖ
2017
Стр.1
Содержание
Предисловие……………………………………………………..…..………. 4
1. Основные понятия и определения……………………………………… 5
2. Элементы теории чисел и модулярная арифметика………………........ 12
2.1. Теорема Эйлера и малая теорема Ферма………….………………. 16
2.2. Квадратичные вычеты……………………………………………… 17
2.3. Вычисление обратных по модулю величин………………………. 18
3. Китайская теорема об остатках…………………………………………. 23
4. Алгоритм Гарнера………………………………………………………... 24
5. Алгоритм Евклида и расширенный алгоритм Евклида…..…………… 25
6. Алгоритм быстрого возведения в степень по модулю………………… 30
7. Алгоритмы факторизации………………………………………………. 32
8. Формальное определение криптосистемы……………………………… 42
9. Криптосистема Эль Гамаля…………………………………………….... 43
10. Криптосистема RSA (Rivest R., Shamir A., Adleman L.)…………....... 50
11. Однонаправленные функции…….…………………………………….. 64
12. Аутентификация сообщений и цифровая подпись ...……………........ 65
13. Однонаправленные хэш–функции ………………………………...…... 69
14. Алгоритм цифровой подписи RSA…………………………..………… 70
11. Алгоритм Диффи – Хеллмана…………………………………………. 71
Библиография………………….……………………….……..…...……...… 75
3
Стр.3
Защита информации –
деятельность, направленная на
предотвращение утечки защищаемой информации, несанкционированных
и непреднамеренных воздействий на защищаемую информацию. Или подругому
– совокупность технических и организационных мер,
обеспечивающих информационную безопасность.
Закрытая информация содержит государственную, коммерческую
или иную тайну.
Секретная информация содержит государственную тайну.
Конфиденциальная информация – служебная, профессиональная,
промышленная, коммерческая или иная информация, правовой режим
которой устанавливается ее собственниками на основе законов о
коммерческой, профессиональной тайне, государственной службе и других
законодательных актов.
Защищаемая информация – информация, являющаяся предметом
собственности и подлежащая защите в соответствии с требованиями
правовых
документов
или
требованиями,
устанавливаемыми
собственниками информации.
Утечка информации – неконтролируемое распространение
защищаемой информации.
Утечки бывают трех видов:
а) разглашение,
б) несанкционированный доступ к информации,
в) разведка.
Уничтожение информации –
утрата информации при
невозможности ее восстановления.
Блокировка информации – невозможность ее использования при
сохранности.
Модификация информации – изменение ее содержания по
сравнению с первоначальной.
6
Стр.6
Цена информации – полезность информации для участников
информационного рынка.
Ценность информации – полезность информации для ее владельца
(пользователя).
Угрозы информации:
а) нарушение конфиденциальности – потеря ценности информации
при ее раскрытии;
б) нарушение целостности – потеря ценности информации при ее
модификации или уничтожении;
в) нарушение доступности – потеря ценности информации при
невозможности ее оперативного использования;
Эффективность защиты информации – мера соответствия уровня
информационной безопасности требованиям при заданном ресурсе на ее
защиту.
Политика безопасности – это набор документированных норм,
правил и практических приемов, регулирующих управление, защиту и
распределение информации ограниченного доступа.
Телекоммуникационная система – система связи, в которой перенос
информации осуществляется сигналами, однозначно отображающими
сообщения, при этом сообщение является формой представления
информации и задает закон изменения, т.е. модуляции тех или иных
информационных признаков сигнала (амплитуды, фазы, частоты).
Алфавит – конечное множество используемых для шифрования
знаков.
Z33 – 32 буквенный русский алфавит и пробел.
Z256 – расширенный ASCII (American Standard Code for Information
Interchange – Американский стандарт кодирования для обмена
информацией).
Z2 – {0;1}.
7
Стр.7
Текст – набор элементов алфавита имеющий определенный
логический смысл. Открытый текст (ОТ) – исходное, шифруемое
сообщение.
Ключ – информация, необходимая для беспрепятственного
шифрования или расшифрования текстов.
Обычно, ключ – последовательность символов того же алфавита, в
котором набрано сообщение.
Пространство ключей – набор всевозможных значений ключа.
Криптография – раздел прикладной математики, в котором
изучаются модели, методы, алгоритмы, программные и аппаратные
средства преобразования информации в целях сокрытия ее содержания,
проверки
подлинности,
предотвращения,
видоизменения
или
несанкционированного использования.
Задачи криптографии:
1. Шифрование и расшифрование.
2. Аутентификация.
3. Хеширование.
4. Формирование, хранение и распределение ключей.
Аутентификация – процедура проверки подлинности.
Хеширование – преобразование по определённому алгоритму
входного массива данных произвольной длины в выходную битовую
строку фиксированной длины.
Основная идея шифрования – скрытие содержимого (смысла)
передаваемого секретного сообщения.
Расшифрование – нахождение открытого текста на основе известного
секретного ключа и шифрованного текста.
Дешифрование – нахождение закрытого ключа или открытого текста
на основе шифрованного текста.
Криптограмма – шифрованный текст (ШТ).
8
Стр.8
аппаратно
Криптосистема – это система, реализованная программно,
или
программно-аппаратно
и
осуществляющая
криптографическое преобразование информации.
Криптоанализ (наука о дешифрации) – это раздел прикладной
математики, в котором изучаются модели, методы, алгоритмы,
программные и аппаратные средства анализа криптосистемы или ее
входных и выходных сигналов с целью извлечения конфиденциальных
параметров, включая открытый текст.
Совокупность криптографии и криптоанализа образует новую науку
криптологию.
Принцип Керкгоффса – правило разработки криптографических
систем, согласно которому в засекреченном виде держится только
определённый набор параметров алгоритма, называемый ключом, а сам
алгоритм шифрования должен быть открытым (Огюст Керкгоффс –
великий нидерландский криптограф, лингвист, историк, математик (1835 –
1903)).
Криптостойкость – характеристика шифра, определяющая его
стойкость к дешифрации. Часто криптостойкость измеряется количеством
операций, необходимых для перебора всех возможных ключей (если длина
ключа в битах равна n, то криптостойкость шифра определяется величиной
n
2 или интервалом времени, необходимого для дешифрования (MIPSгоды).
MIPS
(Million Instructions Per Second) – миллион инструкций в
секунду.
Иногда смешивают два понятия: шифрование и кодирование. Для
шифрования надо знать открытый текст, алгоритм шифрования и
секретный ключ для симметричных (одноключевых) криптосистем или
открытый (публичный) ключ для асимметричных (двухключевых)
криптосистем. При кодировании нет ничего секретного, есть только замена
9
Стр.9
символов открытого текста или слов на заранее определенные символы.
Методы кодирования направлены на то, чтобы представить открытый
текст в более удобном виде для передачи по телекоммуникационным
каналам, для уменьшения длины сообщения (архивация), для повышения
помехоустойчивости (обнаружение и исправление ошибок) и т. д. В
принципе, кодирование, конечно же, можно рассматривать как шифр
замены, для которого «набор» возможных ключей состоит только из
одного ключа (например, буква «а» в азбуке Морзе всегда кодируется
знаком «. – » и это не является секретом).
Стеганография – наука о методах и средствах скрытия самого факта
существования сообщения.
Наибольший общий делитель (НОД) двух натуральных чисел –
наибольшее натуральное число, делящее одновременно каждое из этих
чисел. Запись
( , ) 1=nai
то есть ia и n – взаимно простые числа.
Наименьшее общее кратное (НОК) двух и более натуральных чисел –
наименьшее натуральное число, которое само делится нацело на каждое
из этих чисел.
НОК (a,b)=[a,b]=
( ba
a b⋅
,
)
.
Основная теорема арифметики
Каждое натуральное число
, где
n > 1 можно представить в виде
– простые числа, причём такое
представление единственно с точностью до порядка следования
сомножителей.
Так как некоторые из простых чисел в произведении могут
повторяться, то справедливо каноническое разложение
означает, что НОД чисел ia и n равен единице,
10
Стр.10