Читать онлайн «Решетки, алгоритмы и современная криптография»
Автор С. А. Фомин
Решетки, алгоритмы и современная
криптография
Шокуров А. В, Кузюрин Н. Н, Фомин С. А
22 октября 2011 г. Оглавление
Введение 4
0. 1 Введение. История криптографии . . . . . . . . . . . . . . 4
1 Основные понятия криптографии и теории сложности 8
1. 1 Дискретный логарифм. Обмен ключами. . . . . . . . . . . 8
1. 2 Дискретный логарифм и криптосистема Эль Гамаля . . . . 10
1. 3 Односторонние функции . . . . . . . . . . . . . . . . . . . 11
1. 4 Система RSA и ее анализ . . . . . . . . . . . . . . . . . . . . 14
1. 5 Основные понятия теории сложности . . . . . . . . . . . . 20
2 Кольца, поля, решетки 42
2. 1 Кольца . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2. 1. 1 Кольца. Основные определения . . . . . . . . . . . 42
2. 1. 2 Идеалы и гомоморфизмы колец . . . . . . . . . . . 46
2. 1. 3 Коммутативные кольца . . . . . . . . . . . . . . . . 51
2. 1. 4 Факториальные кольца . . . . . . . . . . . . . . . . 53
2. 1. 5 Кольца многочленов . . . . . . . . . . . . . . . . . 56
2. 1. 6 Однозначность разложения на простые множители
в кольце многочленов . . . . . . . . . . . . . . . . . 57
2. 1. 7 Кратные корни . . . . . . . . . . . . . . . . . . . . . 61
2. 2 Поля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2. 2. 1 Расширения полей . . . . . . . . . . . . . . . . . . 62
2. 2. 2 Алгебраическое замыкание . . . . . . . . . . . . . 66
2. 2. 3 Конечные поля . . . . . . . . . . . . . . . . . . . . . 69
2. 2. 4 Корни из единицы . . . . . . . . .
. . . . . . . . . . 72
2
Оглавление 3
2. 3 Решетки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
2. 3. 1 Введение в решетки . . . . . . . . . . . . . . . . . . 75
2. 3. 2 Критерий полноты решетки. Теорема Минковского 81
2. 4 Применение алгебры. Полиномиальный алгоритм провер-
ки простоты чисел . . . . . . . . . . . . . . . . . . . . . . . 85
2. 5 Полиномиальная проверка простоты . . . . . . . . . . . . 85
3 Алгоритмические аспекты теории решеток 97
3. 1 Кратчайший ненулевой вектор решетки . . . . . . . . . . . 97
3. 1. 1 Некоторые задачи на решетках . . . . . . . . . . . . 98
3. 1. 2 Алгоритм Гаусса . . . . . . . . . . . . . . . . . . . . 99
3. 1. 3 LLL-алгоритм . . . . . . . . . . . . . . . . . . . . . . 104
3. 2 Результаты Айтаи . . . . . . . . . . . . . . . . . . . . . . . . 109
3. 3 Результаты Айтаи . . . . . . . . . . . . . . . . . . . . . . . . 112
4 Некоторые криптосистемы на решетках 117
4. 1 NTRU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
4. 1. 1 Описание NTRU-шифрования . . . . . . . . . . . . . 118
4. 1. 2 Выбор параметров. . . . . . . . . . . . . . . . . . . 121
4. 1. 3 Дешифрование. . . . . . . . . . . . . . . . . . . . . 123
4. 1. 4 Атаки. . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5 Обзор современных результатов по алгоритмическим аспектам
теории решеток 125
Предметный указатель 126
Списки иллюстраций 128
Список алгоритмов 129
Введение
0. 1 Введение.
