ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

Глава 1. МНОЖЕСТВА, АЛГОРИТМЫ, СЛУЧАЙНЫЕ ОТОБРАЖЕНИЯ
1.1. Сведения из теории множеств
1.2. Сведения из теории алгоритмов
1.2.1. Алгоритм и исчисление
1.2.2. Сложность алгоритма
1.3. Нестандартные вычислительные модели
1.3.1. Молекулярный компьютер
1.3.2. Квантовый компьютер
1.4. Случайные последовательности и случайные отображения
1.4.1. Понятие случайности
1.4.2. Свойства случайного отображения
Упражнения к главе 1
Литература к главе 1

Глава 2. ГРУППЫ
2.1. Понятие группы
2.2. Подгруппы
2.3. Гомоморфизмы и изоморфизмы
2.4. Действие группы на множестве
2.5. Группа подстановок
2.6. Вложимость коммутативной полугруппы в группу
2.7. Прямые произведения групп
2.8. Категории
Упражнения к главе 2
Литература к главе 2

Глава 3. КОММУТАТИВНЫЕ КОЛЬЦА
3.1. Понятие кольца
3.2. Гомоморфизмы колец
3.3. Частные
3.4. Предварительные сведения о полиномах
3.5. Идеалы и классы вычетов
3.6. Делимость идеалов
3.7. Евклидовы кольца и кольца главных идеалов
3.8. Разложение на множители
3.9. Кольцо эндоморфизмов модуля. Модули над кольцами
3.10. Свойства полиномов
3.11. Производная и кратные корни
3.12. Симметрические функции
3.13. Разложение на множители полиномов от нескольких переменных
3.14. Полукольца и решетки
3.15. Кольцо полиномов Жегалкина
3.15.1. Полиномы Жегалкина
3.15.2. Разложение на множители в кольце Gn
3.15.3. Симметрические функции кольца Gn
3.15.4. Кольцо дифференциальных операторов кольца Gn
3.15.5. Эндоморфизмы кольца Gn
Упражнения к главе 3
Литература к главе 3

Глава 4. ПОЛЯ
4.1. Общие сведения о полях. Простые поля
4.2. Расширения полей
4.2.1. Простые расширения
4.2.2. Конечные расширения
4.2.3. Целые элементы поля
4.3. Конечные поля
4.3.1. Строение конечных полей
4.3.2. Автоморфизмы конечных полей
4.3.3. Норма и след в конечных полях
4.4. Элементы теории Галуа
4.5. Поля деления круга
4.6. Дискретное преобразование Фурье
4.7. Нормирования
4.8. Пополнения поля Р и p-адические числа
Упражнения к главе 4
Литература к главе 4

Глава 5. СВЕДЕНИЯ ИЗ ТЕОРИИ ЧИСЕЛ
5.1. Однозначное разложение на множители в кольце Щ
5.2. Некоторые числовые функции
5.3. Кольцо Щ/nЩ
5.4. Квадратичные и кубические вычеты. Квадратичный закон взаимности
5.5. Суммы Гаусса и Якоби
5.6. Квадратичные числа и квадратичные формы
5.6.1. Кольцо целых квадратичных чисел
5.6.2. Идеалы квадратичных порядков
5.6.3. Квадратичные формы
5.7. Алгебраические числа
Упражнения к главе 5
Литература к главе 5

Глава 6. ЭЛЕМЕНТЫ АЛГЕБРАИЧЕСКОЙ ГЕОМЕТРИИ. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ
6.1. Аффинные алгебраические многообразия
6.2. Проективная плоскость и проективное пространство
6.3. Сложение точек на конике
6.4. Кубические кривые. Закон сложения
6.5. Особые и неособые кубики
6.6. Касательные и точки перегиба алгебраической кривой
6.7. Нормальные формы эллиптической кривой
6.8. Группа неособых точек кубики
6.9. Невозможность рациональной параметризации эллиптической кривой
6.10. Параметризация эллиптической кривой с помощью эллиптических функций
6.10.1. Эллиптические функции
6.10.2. Функция Вейерштрасса
6.10.3. Параметризация эллиптической кривой над полем В
6.11. Дискриминант и j-инвариант
6.12. Закон сложения точек эллиптической кривой
6.13. Эллиптические кривые над числовыми полями
6.14. Изоморфизмы и эндоморфизмы эллиптических кривых
6.14.1. Изоморфизмы над полями характеристики, отличной от 2 и 3
6.14.2. Изоморфизмы над полями характеристики 3
6.14.3. Изоморфизмы над полями характеристики 2
6.14.4. Бирациональный изоморфизм кривых
6.14.5. Эндоморфизмы эллиптических кривых
6.14.6. Изоморфизмы эллиптических кривых над алгебраически незамкнутым полем
6.15. Отображения алгебраических кривых
6.15.1. Регулярные функции и отображения
6.15.2. Рациональные функции и рациональные отображения
6.15.3. Проективные кривые
6.15.4. Изогении эллиптических кривых
6.15.5. Полиномы Жегалкина как функции на поверхности единичного куба
6.16. Дивизоры на алгебраических кривых
6.16.1. Локальное кольцо точки и нормирование
6.16.2. Дивизоры
6.16.3. Спаривание Вейля
6.17. Эллиптические кривые над конечными полями
6.18. Гиперэллиптические кривые
Упражнения к главе 6
Литература к главе 6

Глава 7. ВЫЧИСЛИТЕЛЬНЫЕ АЛГОРИТМЫ АЛГЕБРЫ И ТЕОРИИ ЧИСЕЛ
7.1. Алгоритмы умножения
7.1.1. Алгоритм умножения Карацубы-Офмана
7.1.2. Умножение в классах вычетов
7.1.3. Умножение с помощью быстрого преобразования Фурье
7.1.4. Модульное умножение. Метод Монтгомери
7.1.5. Деление
7.2. Алгоритмы обращения и вычисления наибольшего общего делителя
7.3. Минимизация базиса решетки
7.4. Разложение над конечным полем полиномов от одной переменной
7.5. Извлечение квадратных и кубических корней в конечном поле
7.5.1. Извлечение квадратного корня в случае q 3 (mod 4)
7.5.2. Извлечение квадратного корня в случае q 5 (mod 8), q 9 (mod 16)
7.5.3. Извлечение квадратного корня в общем случае для нечетного q
7.5.4. Извлечение квадратного корня в случае четного q
7.5.5. Решение квадратного уравнения
7.5.6. Извлечение кубического корня в конечном поле
7.6. Вычисление символа Якоби
7.7. Проверка чисел и полиномов на простоту
7.8. Разложение чисел в мнимом квадратичном порядке
7.9. Приведение числа по модулю решетки
7.10. Умножение точки эллиптической кривой на число
7.11. Вычисление функции Вейля
7.12. Сложение элементов якобиана гиперэллиптической кривой
7.13. Арифметика группы классов мнимых квадратичных порядков
Упражнения к главе 7
Литература к главе 7

Глава 8. КРИПТОГРАФИЯ И ЗАЩИТА ИНФОРМАЦИИ
8.1. Основные понятия защиты информации
8.2. Исчисление атак
8.2.1. Упорядоченность моделей нарушителя и безопасных систем
8.2.2. Множества возможностей нарушителя
8.2.3. Тривиальная модель нарушителя
8.2.4. Нетривиальная модель нарушителя
8.2.5. Место криптографии в защите информации
8.3. Основные понятия и определения криптографической защиты данных
8.3.1. Криптографические примитивы
8.3.2. Хэш-функция
8.3.3. Шифр
8.3.4. Понятие стойкости криптографических алгоритмов
8.4. Шифрование
8.4.1. Симметричное и несимметричное шифрование
8.4.2. Способы шифрования
8.5. Аутентификация
8.5.1. Опознавание
8.5.2. Контроль целостности и подлинности данных
8.6. Управление ключами
8.7. Задачи, положенные в основу безопасности криптографических алгоритмов
Упражнения к главе 8
Литература к главе 8

Глава 9. СИСТЕМА RSA И ЗАДАЧА РАЗЛОЖЕНИЯ
9.1. Безопасность системы RSA и задача разложения на множители
9.2. Детерминированные методы разложения
9.2.1. Метод пробного деления
9.2.2. Метод "giant step - baby step"
9.2.3. Метод Ферма
9.2.4. Метод диофантовой аппроксимации
9.3. Вероятностные методы разложения
9.3.1. Метод Полларда (метод "Монте-Карло")
9.3.2. Метод непрерывных дробей
9.3.3. Метод квадратичного решета
9.3.4. (p - 1)-метод
9.3.5. Разложение на эллиптической кривой
9.3.6. Разложение на квантовом компьютере
9.4. Атаки на систему RSA, не требующие разложения
9.4.1. Случай малого секретного показателя
9.4.2. Случаи специальных открытых показателей
9.4.3. Атаки на основе эндоморфизмов
Упражнения к главе 9
Литература к главе 9

Глава 10. ДИСКРЕТНОЕ ЛОГАРИФМИРОВАНИЕ В КОНЕЧНОМ ПОЛЕ И СМЕЖНЫЕ ЗАДАЧИ
10.1. Метод базы разложения
10.2. Логарифмирование в простом поле методом решета числового поля
10.2.1. Подготовительные теоретико-числовые результаты
10.2.2. Метод решета числового поля
10.3. Логарифмирование в расширенном поле
10.4. Группа классов мнимого квадратичного порядка
10.5. Логарифмирование в группе функций Лукаша
10.6. Связь между задачами Диффи-Хеллмана и дискретного логарифмирования
Упражнения к главе 10
Литература к главе 10

Глава 11. ЗАДАЧА ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ НА ЭЛЛИПТИЧЕСКОЙ КРИВОЙ
11.1. Универсальные методы логарифмирования
11.1.1. Метод Гельфонда
11.1.2. Методы встречи посередине и "giant step - baby step"
11.1.3. Метод Полларда
11.1.4. Метод встречи на случайном дереве
11.1.5. Сравнение сложности логарифмирования на эллиптической кривой и в конечном поле
11.1.6. Логарифмирование с помощью квантового компьютера
11.2. Влияние комплексного умножения на сложность логарифмирования
11.3. Логарифмирование с использованием функции Вейля
11.4. Другие задачи, связанные с логарифмированием
11.5. Время жизни параметров криптосистемы, основанной на дискретном логарифмировании
11.5.1. Мультипликативная группа поля
11.5.2. Группа точек эллиптической кривой
11.6. Логарифмирование в якобиане гиперэллиптической кривой
11.7. Требования к эллиптической кривой
Упражнения к главе 11
Литература к главе 11

Глава 12. ШИФРОВАНИЕ С ОТКРЫТЫМ КЛЮЧОМ
12.1. Шифрование с открытым ключом для группы вычислимого порядка
12.1.1. Бесключевое шифрование Месси-Омуры
12.1.2. Протокол Эль-Гамаля шифрования с открытым ключом
12.2. Шифрование с открытым ключом для группы трудновычислимого порядка
12.2.1. Протокол шифрования Рабина
12.2.2. Вероятностное шифрование
12.3. Ранцевые алгоритмы шифрования с открытым ключом
12.4. Генераторы псевдослучайной последовательности
Упражнения к главе 12
Литература к главе 12

Глава 13. ЦИФРОВАЯ ПОДПИСЬ
13.1. Подпись на группе трудновычислимого порядка
13.1.1. Схема подписи RSA
13.1.2. Схема подписи Рабина
13.1.3. Схема подписи Фиата-Шамира
13.2. Подпись на группе вычислимого порядка
13.2.1. Схема подписи Эль-Гамаля
13.2.2. Схема подписи Шнорра
13.2.3. ГОСТ Р 34.10-94 и DSS
13.3. Сравнительный анализ представленных схем подписи
13.4. Скрытый канал
13.5. Другие схемы подписи
13.5.1. Схема "неоспоримой" подписи
13.5.2. Схема подписи "вслепую". Электронные платежи
13.5.3. Схема подписи с восстановлением сообщения
13.5.4. Инкрементальная подпись
Упражнения к главе 13
Литература к главе 13

Глава 14. ДРУГИЕ КРИПТОГРАФИЧЕСКИЕ ПРОТОКОЛЫ
14.1. Схемы предъявления битов
14.2. Диалоговые доказательства с нулевым разглашением
14.2.1. Доказательство знания изоморфизма графов
14.2.2. Доказательство знания разложениясоставного числа
14.2.3. Доказательство знания дискретного логарифма
14.2.4. Доказательство правильности выбора составного числа
14.3. Бездиалоговые доказательства с нулевым разглашением
14.4. Передача информации со стиранием
14.5. Разделение секрета
14.6. Протоколы управления ключами
14.6.1. Установление ключа на основе симметричных методов
14.6.2. Доставка ключа
14.7. Временная метка
14.7.1. Централизованная реализация временной метки
14.7.2. Децентрализованная реализация временной метки
Упражнения к главе 14
Литература к главе 14

Глава 15. КРИПТОСИСТЕМЫ НА ЭЛЛИПТИЧЕСКИХ И ГИПЕРЭЛЛИПТИЧЕСКИХ КРИВЫХ
15.1. Расчет числа точек эллиптической кривой в общем случае
15.1.1. Предварительные сведения
15.1.2. Полиномы деления
15.1.3. Алгоритм Чуфа
15.2. Расчет числа точек эллиптической кривой над расширенным полем
15.3. Расчет числа точек эллиптических кривых с j = 0, 1728 над простыми полями
15.3.1. Кривая y2 = x3 + B
15.3.2. Кривая y2 = x3 + Ax
15.4. Эллиптические кривые с комплексным умножением
15.4.1. Генерация эллиптических кривых с комплексным умножением
15.4.2. Влияние комплексного умножения на скорость вычислений
15.5. Эллиптические кривые над расширенными полями специальных характеристик
15.6. Протоколы на эллиптических кривых
15.6.1. Встраивание открытого текста в координату точки
15.6.2. Аналог криптосистемы RSA
15.6.3. Установление сеансового ключа
15.6.4. Шифрование
15.6.5. Цифровая подпись
15.6.6. Опознавание, канал со стиранием и доказательства с нулевым разглашением
15.6.7. Вычислимая в одну сторону функция, свободная от коллизий
15.6.8. Генераторы псевдослучайной последовательности
15.6.9. Протоколы для электронных платежей
15.7. Криптосистемы на гиперэллиптических кривых
15.8. Криптосистемы на изогениях эллиптических кривых
15.8.1. Задача вычисления изогении и квантовый компьютер
15.8.2. Криптографические протоколы на изогенных кривых
Упражнения к главе 15
Литература к главе 15

Глава 16. ОБЩИЕ СВЕДЕНИЯ ОБ ИТЕРИРОВАННЫХ КРИПТОАЛГОРИТМАХ
16.1. Основные понятия классической криптографии
16.2. Некоторые положения теории секретности Шеннона
16.2.1. Объем текстов, однозначно определяющих ключ
16.2.2. Теория аутентификации Симмонса
16.3. Булевы функции и булевы формулы
16.4. Аффинно эквивалентные булевы функции и подстановки
16.5. Задача вскрытия ключа и математические задачи
16.5.1. Задача вскрытия ключа и NP-полные задачи
16.5.2. Задача о выполнимости
16.6. Требования к шифрам
16.7. Шифры замены и перестановки
16.7.1. Моноалфавитная замена
16.7.2. Полиалфавитная замена
16.8. Операторы, используемые при построении блочных шифров
16.9. Описание итерированных шифров в терминах булевых функций
Упражнения к главе 16
Литература к главе 16

Глава 17. АЛГЕБРАИЧЕСКИЕ МЕТОДЫ КРИПТОАНАЛИЗА
17.1. Метод обобщения и редукции. Метод гомоморфизмов
17.2. Замкнутые и чистые шифры
17.2.1. Вскрытие ключей замкнутых и чистых шифров
17.2.2. Проверка шифра на замкнутость и чистоту
17.3. Решеточный криптоанализ
17.3.1. Решеточно продолженные булевы функции и решеточные полиномы
17.3.2. Метод криптоанализа
17.4. Метод арифметического продолжения булевых функций
17.5. Анализ шифров с малым порядком нелинейности
17.6. Криптоанализ на основе рационального продолжения полиномов Жегалкина
17.6.1. Теоретические основы
17.6.2. Метод криптоанализа
17.7. Криптоанализ на основе 2-адического продолжения полиномов Жегалкина
17.7.1. Теоретические основы
17.7.2. Метод криптоанализа
17.8. Максимизация числа совпавших разрядов промежуточных текстов
17.9. Анализ с использованием сжимающих гомоморфизмов
17.10. Поиск коллизий хэш-функции
17.11. Компромисс время/память
17.12. Сочетание перебора и вычисления ключа
17.13. Отбраковка классов ключей
17.14. Задачи, к которым сводится задача вскрытия ключа
17.15. Вскрытие ключа на квантовом компьютере
Упражнения к главе 17
Литература к главе 17

Глава 18. СТАТИСТИЧЕСКИЕ МЕТОДЫ КРИПТОАНАЛИЗА
18.1. Некоторые определения
18.2. Дифференциальный криптоанализ
18.2.1. Конечные разности
18.2.2. Метод криптоанализа
18.2.3. Анализ с помощью усеченных дифференциалов
18.2.4. Анализ с помощью дифференциалов высших порядков
18.2.5. Атака "бумеранг"
18.3. Криптоанализ на основе списка ключей и связанных ключей
18.4. Линейный криптоанализ
18.5. Анализ степенных шифров методом сдвига
18.6. Генерация экстремальных подстановок для шифров
18.6.1. Экстремальные подстановки
18.6.2. Булевы функции для экстремальныхподстановок
18.6.3. Примеры экстремальных подстановок
Упражнения к главе 18
Литература к главе 18

Глава 19. ПРИМЕНЕНИЕ ИТЕРИРОВАННЫХ ШИФРОВ И ХЭШ-ФУНКЦИЙ
19.1. Режимы шифрования
19.1.1. Режим простой замены
19.1.2. Режим гаммирования
19.1.3. Режим гаммирования с обратной связью
19.1.4. Режим сцепления блоков. Выработка имитовставки
19.2. Некоторые вопросы применения шифров
19.3. DES
19.4. FEAL
19.5. IDEA
19.6. ГОСТ 28147-89
19.6.1. Стойкость шифра ГОСТ 28147-89
19.6.2. Стойкость шифра ГОСТ 28147-89 при наличии у нарушителя лабораторных возможностей
19.7. RC5
19.8. Blowfish
19.9. SAFER
19.10. RIJNDAEL (AES)
19.11. MD5
19.12. ГОСТ Р 34.11-94
Упражнения к главе 19
Литература к главе 19

ОТВЕТЫ И УКАЗАНИЯ К УПРАЖНЕНИЯМ

ПРИЛОЖЕНИЕ. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ ДЛЯ СТАНДАРТА ПОДПИСИ ГОСТ Р 34.10 2001
УКАЗАТЕЛЬ

НАЗАД