ФПМИ: Криптология : учебник / Ю. С. Харин

	Криптология : учебник / Ю. С. Харин [и др.]. - Минск: БГУ, 2013. -511 с. - (Классическое университетское издание). ISBN 978-985-518-962-7. Изложены математические и компьютерные основы криптографической защиты информации в сетях и системах связи. Для студентов учреждений высшего образования, обучающихся по математическим и техническим специальностям.
Оглавление

Предисловие	7
Основные обозначения	9
Часть I. МАТЕМАТИЧЕСКИЕ И КОМПЬЮТЕРНЫЕ ОСНОВЫ КРИПТОЛОГИИ
Глава 1. Введение в криптологию	12
1.1. Предмет криптологии	12
1.2. История развития криптологии	13
1.3. Задачи криптографии и криптоанализа	14
1.4. Задания	18
Глава 2. Арифметические основы	19
2.1.Алгоритм деления с остатком	19
2.2.Наибольший общий делитель	19
2.3.Взаимно простые числа	20
2.4.Расширенный алгоритм Евклида	21
2.5.Наименьшее общее кратное	22
2.6.Простые числа	22
2.7.Сравнения	23
2.8.Классы вычетов	24
2.9.Функция Эйлера	25

2.10.Сравнения первой степени	26
2.11.Система сравнений первой степени	27
2.12.Первообразные корни	28
2.13.Существование первообразных корней	29
2.14.Индексы по модулям/)* и 2р^к	30
2.15.Символ Лежандра	30
2.16.Квадратичный закон взаимности	31
2.17.Символ Якоби	33
2.18.Цепные дроби	34
2.19.Подходящие дроби	35
2.20.Подходящие дроби в качестве наилучших приближений	37
2.21.Задания	39
Глава 3. Алгебраические основы	42
3.1.Понятие группы	42
3.2.Подгруппы групп	43
3.3.Циклические группы	45
3.4.Гомоморфизмы групп	46
3.5.Группы подстановок	48
3.6.Действие группы на множестве	50
3.7.Кольца и поля	51
3.8.Подкольца	52
3.9.Гомоморфизмы колец	54
3.10.Евклидовы кольца	55
3.11.Простые и максимальные идеалы	56
3.12.Конечные расширения полей	58
3.13.Поле разложения	60
3.14.Конечные поля	61
3.15.Порядки неприводимых многочленов	63
3.16.Число неприводимых многочленов	64
3.17.Линейные рекуррентные последовательности	65
3.18.Последовательности максимального периода	67
3.19.Задания	68
Глава 4. Эллиптические кривые	74
4.1.Уравнение Вейерштрасса эллиптической кривой	74
4.2.j-инвариант и дискриминант эллиптической кривой	75
4.3.Сложение точек эллиптической кривой	76
4.4.Эллиптические кривые над конечными полями нечетной характеристики	78
4.5.Эллиптические кривые над конечными полями характеристики 2	79
4.6.Многочлены деления	79
4.7.Изогении и эндоморфизм Фробениуса	82
4.8.Вычисление порядка группы точек эллиптической кривой	84
4.9.Задания	87
Глава 5. Вероятностные модели случайных последовательностей	88
5.1.Дискретные временные ряды, их модели и вероятностные характеристики	88
5.2.Равномерно распределенная случайная последовательность и ее свойства	92
5.3.Цепь Маркова и ее свойства	94
5.4.Цепь Маркова порядка s	100
5.5.Модель Джекобса - Льюиса	102
5.6.MTD-модель Рафтери	104
5.7.Цепь Маркова с частичными связями ЦМ(5, г)	105
5.8.Другие малопараметрические модели цепей Маркова высокого порядка	106
5.9. Задания	107
Глава 6. Статистическое тестирование случайных и псевдослучайных последовательностей	108
6.1. Проблема статистического тестирования в криптологии и батареи тестов	108
6.2.Универсальный алгоритм статистического тестирования случайных и псевдослучайных последовательностей	111
6.3.Тест и-серий	113
6.4.Тест интервалов	114
6.5.Обобщенный покер-тест	115
6.6.Тест «собирателя купонов»	116
6.7.Тест перестановок	116
6.8.Тест пересекающихся га-грамм	117
6.9.Тест, основанный на рангах двоичных матриц	118

6.10.Спектральные тесты	119
6.11.Тесты случайного блуждания	123
6.12.Универсальный статистический тест Маурера	124
6.13.Тесты на основе приращений энтропии	126
6.14.Тест, основанный на алгоритме сжатия Лемпеля -Зива	128
6.15.Тест, основанный на линейной сложности	129
6.16.Тест на основе экстремальной статистики скалярного произведения	131
6.17.Тест на основе экстремальной статистики дельта-произведения	134
6.18.Об алгоритмическом определении случайности	136
6.19.Тест выявления марковской зависимости	140
6.20.Тест на основе модели Джекобса - Льюиса	140
6.21.Тест на основе MTD-модели	142
6.22.Тест на основе цепей Маркова с частичными связями	143
6.23.Задания	145
Глава 7. Методы теории информации в криптологии	150
7.1.Источники дискретных сообщений и их вероятностные модели	150
7.2.Функционал энтропии и его свойства	152
7.3.Условная энтропия и ее свойства	154
7.4.Удельная энтропия стационарной символьной последовательности	160
7.5.Энтропийные характеристики марковских символьных последовательностей	165
7.6.Источники непрерывных сообщений и их энтропийные свойства	170
7.7.Оптимизация функционала энтропии на классе вероятностных распределений	179
7.8.Асимптотические свойства стационарного источника дискретных сообщений	184
7.9. Энтропийная устойчивость случайных символьных последовательностей	189

7.10.Количество информации по Шеннону и его свойства	193
7.11.Шенноновские модели криптосистем	199
7.12.Теоретико-информационные оценки стойкости симметричных криптосистем	205
7.13.Задания	210
Глава 8. Элементы теории сложности вычислений	214
8.1.Вычислительные задачи	214
8.2. Задачи распознавания и поиска	215
8.3. Машина Тьюринга	216
8.4. Разрешимые и неразрешимые задачи	218
8.5.Ресурсы	219
8.6.Вероятностные машины	221
8.7.Алгоритмы Лас-Вегас и Монте-Карло	223
8.8.Сведение	225
8.9.Классы сложности	227

8.10.Язык PRIMES	229
8.11.Односторонние функции	231
8.12.Функции с лазейкой	233
8.13.Функция Рабина	234
8.14.Задания	235
Глава 9. Базовые алгоритмы	239
9.1.Алгоритмы арифметики больших чисел	239
9.2.Операция Монтгомери и редукция Баррета	241
9.3. Вероятностные и детерминированные алгоритмы тестирования на простоту	242
9.4.Построение больших простых чисел	247
9.5.Алгоритмы сложения точек эллиптической кривой	249
9.6.Вычисление кратной точки эллиптической кривой	253
9.7.Задания	254
Часть II. КРИПТОГРАФИЧЕСКИЕ СИСТЕМЫ И МЕТОДЫ КРИПТОАНАЛИЗА
Глава 10. Генерация случайных и псевдослучайных последовательностей	258
10.1.Классификация алгоритмов генерации	258
10.2. Физические генераторы случайных последовательностей	260
10.3. Линейные и мультипликативные конгруэнтные генераторы	264
10.4. Нелинейные конгруэнтные генераторы	266
10.5. Генераторы на основе регистров сдвига с линейной, нелинейной и случайной обратной связью	267
10.6. Криптостойкие генераторы на основе односторонних функций	271
10.7.Криптостойкие генераторы, основанные на проблемах теории чисел	275
10.8.Методы «улучшения» свойств элементарных псевдослучайных последовательностей	276
10.9. Фильтрующие генераторы	278
10.10. Комбинирование алгоритмов генерации методом Макларена - Марсальи	279
10.11.Комбинирование LFSR-генераторов	280
10.12.Конгруэнтный генератор со случайными параметрами	283
10.13.Задания	283
Глава 11. Поточные криптосистемы	286
11.1.Основные понятия и классификация поточных криптосистем	286
11.2.Рекуррентные последовательностии регистры сдвига	291
11.3.Алгоритмы Берлекэмпа - Месси и линейная сложность	294
11.4.Комбинирование последовательностей	296
11.5.Статистическое оценивание начального состояния ЛРП	298
11.6.Криптоанализ поточных шифров	300
11.7.Задания	306
Глава 12. Блочные криптосистемы	309
12.1.Блочное шифрование	309
12.2. Задачи криптоанализа	311
12.3.Блочно-итерационные криптосистемы	313
12.4.Операции над двоичными словами	315
12.5.Булевы функции и отображения	318
12.6.Криптосистемы подстановки-перестановки	332
12.7.Криптосистема AES	334
12.8.т-инволютивные подстановки	336
12.9.Криптосистемы Фейстеля	338

12.10.Криптосистема Belt	340
12.11.Атака «грубой силой»	342
12.12.Разностная атака	346
12.13.Линейная атака	351
12.14.Режимы шифрования	355
12.15.Имитозащита	357
12.16.Задания	360
Глава 13. Функции хэширования	369
13.1.Определение и использование	369
13.2.Задачи криптоанализа	371
13.3. Блочно-итерационные функции хэширования	373
13.4. Шаговые функции хэширования	375
13.5.Атака «дней рождения»	377
13.6.Модернизированная атака «дней рождения»	380
13.7.Задания	383
Глава 14. Криптосистемы с открытым ключом	386
14.1. RSA-криптосистема	386
14.2. Возможные атаки на криптосистему RSA	388
14.3. Стойкость RSA против атаки повторного шифрования	389
14.4. Поиск секретного ключа dи факторизация модуля N	390
14.5. Биты ключей в RSA-криптосистеме	392
14.6. Теорема М. Винера о малой секретной экспоненте	393
14.7. Об одном обобщении RSA-криптосистемы	394
14.8. Рюкзачный метод шифрования	397
14.9. Стойкость рюкзачного шифра	399

14.10. Криптосистема Эль-Гамаля	400
14.11.Криптосистема Мак-Элиса	401
14.12. Криптосистема Блюма - Гольдвассер	402
14.13. Задания	404
Глава 15. Электронная цифровая подпись	406
15.1. Обобщенная модель ЭЦП	406
15.2. Схема ЭЦП Рабина	408
15.3. Схема ЭЦП Эль-Гамаля	409
15.4. ЭЦП DSS	410
15.5. ЭЦП ГОСТ Р 34.10-94	412
15.6. Эквивалентность задач фальсификации подписи в DSS и схеме Эль-Гамаля	419
15.7. ЭЦП СТБ 1176.2-99	420
15.8. Цифровая подпись на эллиптических кривых	422
15.9. Особенности скалярного умножения на эллиптических кривых	425
15.10. Криптоанализ алгоритмов ЭЦП, основанных на факторизации и дискретном логарифмировании	426
15.11. Задания	431
Глава 16. Протоколы формирования общего ключа	433
16.1. Головоломки Меркля	433
16.2. Протокол Диффи - Хеллмана	434
16.3. Атака «противник посередине»	436
16.4. Сертификаты открытых ключей	437
16.5. Протокол с сертификатами	439
16.6. Протоколы MTI	440
16.7. Аутентификация	443
16.8. Протокол MQV	445
16.9. Протокол TLS	446
16.10. Задания	448
Глава 17. Методы и алгоритмы разделения секрета	450
17.1. Общая задача о разделении секрета	450
17.2. Критерии качества схем разделения секрета	452
17.3. Схема Шамира	453
17.4. Линейное разделение секрета	455
17.5. Модулярный подход	457
17.6.Генерация модулей для пороговых схем в кольце целых чисел	458
17.7. Пороговые схемы над кольцом многочленов	461
17.8.Совершенные модулярные схемы	464
17.9.Модулярная реализация произвольных структур доступа	467

17.10.Разделение секрета в кольце многочленов от нескольких переменных	468
17.11.Реализация произвольных структур доступа	470
17.12.Максимальные идеалы одинаковых степеней	471
17.13. Нульмерные радикальные идеалы	473
17.14. Об идеальных схемах в кольце многочленов от нескольких переменных.	474
17.15.Задания	476
Глава 18. О новых направлениях в криптологии	477
18.1.О возможностях квантовой криптографии	477
18.2.Стеганография и ее применение	480
18.3.Активный криптоанализ	483
Библиографические ссылки	487
Приложения	496
1. Архив дискретных последовательностей	496
2. Таблицы	498
Предметный указатель	500