Введение в криптографию

ВВЕДЕНИЕ
В КРИПТОГРАФИЮ
КУРС ЛЕКЦИЙ

В.А. Романьков

 Рекомендовано студентам высших учебных заведений

Рекомендовано в качестве учебного пособия для студентов высших учебных 
заведений, обучающихся по направлениям подготовки 01.03.01 «Математика»,
02.03.01 «Математика и компьютерные технологии»,
01.03.02 «Прикладная математика и информатика» 
(квалификация (степень) «бакалавр»)

Москва                                        2020

ИНФРА-М

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

УДК 519.6(075.8)
ББК 22.19я73
 
Р69

Романьков В.А.
Р69 
 
Введение в криптографию. Курс лекций / В.А. Романьков. — 2-е изд., 
испр. и доп. — Москва : ФОРУМ : ИНФРА-М, 2020. — 240 с. — (Высшее образование: Бакалавриат).

ISBN 978-5-00091-493-9 (ФОРУМ)
ISBN 978-5-16-013395-9 (ИНФРА-М, print)
ISBN 978-5-16-105918-0 (ИНФРА-М, online)

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

УДК 519.6(075.8)
ББК 22.19я73

Р е ц е н з е н т ы:
Р.Т. Файзуллин, доктор технических наук, профессор;
Л.М. Мартынов, доктор физико-математических наук, профессор

ISBN 978-5-00091-493-9 (ФОРУМ)
ISBN 978-5-16-013395-9 (ИНФРА-М, print)
ISBN 978-5-16-105918-0 (ИНФРА-М, online)

© Романьков В.А., 2012
© Романьков В.А., 2017, 
с изменениями
© ФОРУМ, 2017

Содержание

Предисловие автора ко 2-му изданию 
Введение
Лекция 1. Платформы шифрования
Лекция 2. Модулярная арифметика
Лекция 3. Элементы шифрования
Лекция 4. Элементы криптоанализа
Лекция 5. Модели систем шифрования
Лекция б. Простейшие шифры
Лекция 7. Группы
Лекция 8. Конечные поля
Лекция 9. Дискретный логарифм
Лекция 10. Криптосистема с открытым ключом
Ривеста -  Шамира - Адлемана
Лекция 11. Простые числа
Лекция 12. Разложимость целых чисел на множители
Лекция 13. Алгоритмы генерации псевдослучайных
последовательностей
Лекция 14. Поточные криптосистемы
Лекция 15. Идентификация и аутентификация
Лекция 16. Электронные подписи
Лекция 17. Электронные платежи
Лекция 18. Управление ключами
Лекция 19. Эллиптические кривые
Лекция 20. Криптография, основанная
на эллиптических кривых
Лекция 21. Алгебраическое шифрование
Приложение 1. Стандарт шифрования DES
Приложение 2. Стандарты электронной подписи
Приложение 3. Стандарт шифрования AES

5
7
10
18
28
37
45
55
69
76
83

96
112
122

130
136
143
151
161
170
175

183
188
193
209
217

3

Приложение 4. Практическое использование
криптографии
Послесловие
Литература
Предметны й указатель

226
231
233
235

4

Предисловие автора ко 2-му изданию

Эта книга основана на записках лекций по курсу “Криптография”, читанных автором в Омском государственном университете 
им. Ф.М. Достоевского и ряде других университетов в течение последних 10-15 лет. Она представляет именно введение в предмет, 
не загруженное излишними деталями, компактное и информативное. Автор надеется, что ее будущие читатели не только смогут 
ориентироваться в мире криптографии и ее приложений, но также, если возникнет соответствующее желание или необходимость, 
быстро перейдут к чтению специальной литературы по криптографии и ее приложениям.

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

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

По сравнению с 1-м изданием, вышедшем в 2006 г., книга дополнена тремя новыми разделами (лекции 5, 13 и приложение 4),

5

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

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

В.А. Романьков
Омский государственный университет им. Ф.М. Достоевского 
Институт математики и информационных технологий 
romankov@omsu.ru 
Омск, 2011 г.

6

1. История

Криптография - наука о шифрах. История возникновения и 
развития криптографии восходит к древнейшим временам. Первые сведения о применении шифров в военном деле связаны с 
именем спартанского полководца Лисандра, использовавшего для 
передачи сообщений шифр «Сцитала». Известен «шифр Цезаря», 
которым пользовался Юлий Цезарь в своей переписке. В Древней 
Греции был изобретен шифр, именуемый как «квадрат Полибия».

Одна из первых книг по шифровке написана аббатом Трител- 
лием (1462-1516) из Германии. В 1566 г. знаменитый математик 
Кардано опубликовал метод шифрования, известный как «решетка Кардано». Известны шифры короля Генриха IV, кардинала Ришелье, а также «цифирная азбука», автором которой был Петр 
Великий. Шифрование на Руси существовало и до Петра, называлось оно тайнописью.

Большое влияние на развитие криптографии оказали работы 
Клода Шеннона, заложившего основы теории информации. Принято считать, что теория информации как наука родилась в 1948 г. 
после публикации знаменитой работы Шеннона «Математическая 
теория связи» (см. [14]).

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

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

Шифрование - преобразование текста с целью скрыть его содержание от несанкционированного прочтения.

Введение

7

Криптография -  искусство составления шифров и шифропротоколов.

Криптоанализ - наука (и практика ее применения) о методах 
и способах вскрытия шифров.

Криптология - наука, состоящая из двух ветвей: криптографии и криптоанализа.

Криптосистемой (системой шифрования) называется известный способ шифрования, обладающий сменными элементами - 
ключами. Обычно рассматривают ключ шифрования и ключ дешифрования. Если их необходимо хранить в секрете, то система 
называется симметричной, или системой с секретными ключами. Если ключ шифрования открыт, то есть не является секретным, то такие криптосистемы называются асимметричными, или 
системами с открытым ключом.

Шифруемый текст мы будем называть исходным текстом 
(термин английского языка - plaintext). Результат шифрования 
называется шифротекстом (иногда шифровкой, по-английски - 
ciphertext).

Система шифрования включает в себя в качестве основного 
элемента функцию шифрования. Функция шифрования преобразует исходный текст в шифровку. Она зависит от ключа шифрования.

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

Мы пришли к определению односторонней функции у = f(x), 
где вычисление у по х осуществляется достаточно просто, а нахождение (какого-либо) ж по у ~ трудная задача.

8

Уже несколько раз употреблен термин «трудная задача». Пока это неформальное понятие, связанное с возможностью решения задачи в реальное время реальными средствами. Понятие реального зависит как от важности задачи, так и от возможностей 
пытающегося ее решить.

Всем таким понятиям можно придать формальный смысл, но 
это остается за рамками предлагаемого курса лекций.

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

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

9

Лекция 1

Платформы шифрования

А - черный, белый - Е;

И - красный, У - зеленый.

О - синий; тайну их 
скажу я в свой черед.

А. Рембо. Гласные

1. Алфавит

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

Алфавит может иметь обычный смысл: 33 буквы от А до Я 
в русском языке или 26 букв от А до Z в английском. Однако в 
криптографии понятие алфавит имеет более широкий смысл. Так 
называют совокупность знаков, среди которых могут встречаться 
обычные буквы, цифры, знаки препинания, специальные знаки, 
обозначающие пробелы, и всевозможные другие знаки. Можно, 
конечно, называть все это знаковой системой.

Текст есть конечный упорядоченный набор знаков. Вовсе не 
обязательно, чтобы он имел смысл. Есть еще одно понятие - единица текста. В простейшем случае единицами текста считают 
знаки, участвующие в его записи. Однако в качестве единиц текста могут выступать более сложные образования. Например, мы 
можем считать единицами текста последовательные пары знаков 
- диграфы, или- тройки - триграфы, или наборы из к знаков - 
к-графы. При этом возникает маленькая неприятность - последний /с-граф текста может оказаться неполным. Для этого случая необходимо специальное соглашение. Например, можно дополнить последний Аьграф знаками выбранного вида.

10