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

Предисловие

Обозначения

Глава 1. Теория чисел
1.1. Сравнимость и алгоритм Евклида
1.2. Функция Эйлера
1.3. Квадратичные вычеты
1.4. Плотность простых чисел
1.5. Непредвиденные дроби
1.6. Конечные поля
1.7. Замечания и бибилиография
1.8. Упражнения

Глава 2. Криптография с секретным ключом
2.1. Исторические примеры
2.2. Система Вернама или "одноразовый блокнот"
2.3. Зашифрование с секретным ключом
2.4. Теория Шеннона
2.5. Проблема аутентичности: система подписи
2.6. Передача с аутентификацией
2.7. Разделение секрета: пороговые схемы
2.8. Замечания и бибилиография
2.9. Упражнения

Глава 3. Псевдослучайные порождающие
3.1. Случайные последовательности
3.2. Псевдослучайные последовательности
3.3. m-последовательности и регистры сдвига
3.4. Алгебраическое представление m-последовательностей
3.5. Линейная сложность
3.6. Комбинация порождающих
3.7. Сопротивляемость корреляции
3.8. Нелинейность
3.9. Замечания и бибилиография
3.10. Упражнения

Глава 4. Современная криптография: односторонние функции
4.1. Понятие односторонней функции
4.2. Возведение в степень по модулю
4.3. Функция "степени": система RSA
4.4. Функция возведения в квадрат по модулю
4.5. Функция сгущения
4.6. Замечания и бибилиография
4.7. Упражнения

Глава 5. Простые числа и разложение на множители
5.1. Генерация простых чисел
5.2. Задача о разложении на множители
5.3. Применение непрерывных дробей
5.4. Квадратичное решето
5.5. Решето с числовым полем
5.6. Замечания и бибилиография
5.7. Разложение на множители многочленов
5.8. Упражнения

Глава 6. Вокруг возведения в степень
6.1. Задача о логарифме
6.2. DSS
6.3. Гибридное зашифрование
6.4. Эллиптические кривые
6.5. Некоммутативное обобщение
6.6. Замечания и бибилиография
6.7. Приложение: задача о логарифмев конечных полях F_2n
6.8. Упражнения

Глава 7. Сложность и криптография
7.1. Введение в теорию сложности
7.2. Вычислимость в смысле Тьюринга: классы P и NP
7.3. Классы RP
7.4. Классы NP ∩ coNP
7.5. Односторонние функции и класс NP
7.6. Более широкие классы сложности: класс PSPACE
7.7. Сложность в контурах
7.8. Влияние на криптографию
7.9. Замечания и бибилиография
7.10. Упражнения

Глава 8. Протоколы: проблема идентификации
8.1. Игра в орел и решку по телефону
8.2. Слепые подписи: анонимные цифровые деньги
8.3. Как идентифицировать себя
8.4. Точка зрения теории сложности: класс IP
8.5. Точка зрения криптографии: отсутствие разглашения
8.6. Бессознательное разглашение
8.7. Замечания и бибилиография
8.8. Упражнения

Глава 9. Коды с исправлением ошибок и криптография
9.1. Краткое введение в коды с исправлением ошибок
9.2. Диффузия случайного
9.3. Канал с подслушиванием (wire-tap channel), первая версия
9.4. Канал с подслушиванием (wire-tap channel), вторая версия
9.5. Система МакЭлиса с открыиым ключом
9.6. Протокол идентификации Штерна
9.7. Бессознательное разглашение и коды с пересечением
9.8. Разделение секрета и пороговые схемы
9.9. Коды аутентификации
9.10. Охота на пиратов
9.11. Замечания и бибилиография
9.12. Упражнения

Советы по дальнейшему чтению

Литература

Предметный указатель