Елена Ивановна Деза , Лидия Владимировна Котова - Введение в криптографию. Теоретико-числовые основы защиты информации

подстановочные шифры
(шифры простой зам ен ы )......................................................
1.1.2. Полиалфавитные подстановочные ш ифры ...........................
1.1.3. Простейшие шифры перестановки........................................
Упражнения..............................................................................
Задачи......................................................................................
1.2. Криптоанализ классических ш и ф р о в ..............................................
1.2.1. Криптоанализ шифров перестановки...................................
1.2.2. Криптоанализ шифров простой замены................................
1.2.3. Криптоанализ полиалфавитных криптосистем......................
Упражнения..............................................................................
Задачи......................................................................................
1.3. Задачи криптографических олимпиад..............................................
Примеры решения задач........................................................
Задачи......................................................................................

17
18
23
27
33
36
41
41
42
45
50
54
61
61
66

Глава 2. Простейшие симметричные криптосистемы................................

74

2.1. Аффинные криптосистемы ..............................................................
Упражнения......................................................' ......................
Задачи......................................................................................
2.2. Криптоанализ аффинных криптосистем ........................................
Упражнения..............................................................................
Задачи......................................................................................

74
80
83
85

Глава 3. Шифрующие матрицы ...................................................................

94

88

90

3.1. Алгебра матриц и аффинные
матричные криптосистемы................................................................. 94
Упражнения..............................................................................104
Задачи...................................................................................... 107

Tlgm: @it_boooks

4

Содержание

3.2. Криптоанализ аффинных матричных криптосистем..................... 111
Упражнения..............................................................................116
Задачи......................................................................................118
Глава 4. Система RSA. Дискретный логарифм...........................................123
4.1. Система RSA и ее модификации..................................................... 123
4.1.1. Криптосистема без передачи кл ю ч ей ...................................125
4.1.2. Криптосистема с открытым ключом..................................... 128
4.1.3. Электронная подпись..............................................................130
Упражнения..............................................................................133
Задачи......................................................................................135
4.2. Дискретный логарифм......................................................................138
4.2.1. Показатели, первообразные корни и индексы..................... 138
4.2.2. Метод перебора......................................................................140
4.2.3. Метод согласования................................................................ 142
4.2.4. Метод Сильвестра—Полита—Хеллмана................................ 144
4.2.5. Алгоритм исчисления п орядка............................................. 148
Упражнения..............................................................................151
Задачи......................................................................................152
Глава 5. Вычислительные алгоритмы и их трудоемкость........................ 156
5.1. Трудоемкость арифметических действий........................................ 156
5.1.1. Системы счисления................................................................ 157
5.1.2. Символ «0»-большое..............................................................160
5.1.3. Анализ трудоемкости арифметических действий................ 161
5.1.4. Классификация алгоритмов по их трудоемкости................167
Упражнения..............................................................................169
Задачи......................................................................................173
5.2. Простейшие арифметические алгоритмы
и их трудоемкость..............................................................................175
5.2.1. Алгоритм Евклида...................................................................175
5.2.2. Расширенный алгоритм Евклида...........................................179
5.2.3. Бинарный алгоритм Евклида................................................ 180
5.2.4. Расширенный бинарный алгоритм........................................ 184
5.2.5. Решение неопределенных уравнений
первой степени........................................................................ 185
5.2.6. Алгоритм возведения в степень по модулю п ..................... 188
Упражнения..............................................................................191
Задачи......................................................................................193

Tlgm: @it_boooks

Содержание

5

Глава 6 . Простые и псевдопростые ч и сл а................................................... 195
6.1. Простые числа. Критерии простоты................................................ 195
Упражнения.............................................................................. 200
Задачи...................................................................................... 202
6.2. Вероятностные тесты простоты.
Псевдопростые числа.........................................................................204
6.2.1. Тест Ф ерм --">