Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография

Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография. - М., 2005. - 490 стр.
Данное издание включает в себя материалы книг "Алгебраические основы криптографии", "Введение в криптографию с открытым ключом", "Введение в теорию итерированных шифров", выпущенных в издательстве "Мир и Семья" в 2000 2003 гг. Книга состоит из трех частей. Первая часть содержит сведения из алгебры, теории чисел, алгебраической геометрии. Вторая часть посвящена алгоритмам криптографии с открытым ключом, особое внимание уделено эллиптическим кривым. Третья часть содержит основные сведения из области итерированных шифров и хэш-функций. В приложении приведены эллиптические кривые для стандарта цифровой подписи ГОСТ Р 34.10-2001.
Книга может быть использована в качестве учебного пособия для углубленного изучения криптографии. В отличие от большинства изданий по криптографии, основное внимание уделено методам криптоанализа.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ.............................................................3
ГЛАВА 1. МНОЖЕСТВА, АЛГОРИТМЫ, СЛУЧАЙНЫЕ ОТОБРАЖЕНИЯ......................6
1.1. Сведения из теории множеств.....................6
1.2. Сведения из теории алгоритмов..................8
1.2.1. Алгоритм и исчисление...................8
1.2.2. Сложность алгоритма......................10
1.3. Нестандартные вычислительные модели... 12
1.3.1. Молекулярный компьютер..............13
1.3.2. Квантовый компьютер.....................14
1.4. Случайные последовательности и случайные отображения...........................16
1.4.1. Понятие случайности.......................16
1.4.2. Свойства случайного отображения... 17
Упражнения к главе 1..............................................20
Литература к главе 1................................................20
ГЛАВА 2. ГРУППЫ..............................................22
2.1. Понятие группы............................................22
2.2. Подгруппы....................................................23
2.3. Гомоморфизмы и изоморфизмы.................26
2.4. Действие группы на множестве..................28
2.5. Группа подстановок.....................................28
2.6. Вложимость коммутативной полугруппы в группу...................31
2.7. Прямые произведения групп.......................31
2.8. Категории......................................................32
Упражнения к главе 2..............................................33
Литература к главе 2................................................33
ГЛАВА 3. КОММУТАТИВНЫЕ КОЛЬЦА......34
3.1. Понятие кольца.............................................34
3.2. Гомоморфизмы колец..................................36
3.3. Частные.........................................................36
3.4. Предварительные сведения о полиномах... 37
3.5. Идеалы и классы вычетов............................38
3.6. Делимость идеалов.......................................41
3.7. Евклидовы кольца и кольца главных идеалов..............42
3.8. Разложение на множители...........................43
3.9. Кольцо эндоморфизмов модуля. Модули над кольцами........45
3.10. Свойства полиномов....................................46
3.11. Производная и кратные корни.....................46
3.12. Симметрические функции...........................47
3.13. Разложение на множители полиномов от нескольких переменных..........48
3.14. Полукольца и решетки.................................50
3.15. Кольцо полиномов Жегалкина....................51
3.15.1. Полиномы Жегалкина......................51
3.15.2. Разложение на множители в кольце Gn......................53
3.15.3. Симметрические функции кольца Gn...................54
3.15.4. Кольцо дифференциальных операторов кольца Gn.......................54
3.15.5. Эндоморфизмы кольца Gn................55
Упражнения к главе 3..............................................56
Литература к главе 3................................................57
ГЛАВА 4. ПОЛЯ.....................................................58
4.1. Общие сведения о полях. Простые поля.....58
4.2. Расширения полей.........................................59
4.2.1. Простые расширения........................60
4.2.2. Конечные расширения......................62
4.2.3. Целые элементы поля.......................64
4.3. Конечные поля..............................................65
4.3.1. Строение конечных полей................65
4.3.2. Автоморфизмы конечных полей.....67
4.3.3. Норма и след в конечных полях......69
4.4. Элементы теории Галуа................................70
4.5. Поля деления круга.......................................72
4.6. Дискретное преобразование Фурье.............73
4.7. Нормирования...............................................74
4.8. Пополнения поля Q и р-адические числа ...75
Упражнения к главе 4..............................................77
Литература к главе 4................................................78
ГЛАВА 5. СВЕДЕНИЯ ИЗ ТЕОРИИ ЧИСЕЛ. .79
5.1. Однозначное разложение на множители в кольце Z...............79
5.2. Некоторые числовые функции.....................79
5.3. Кольцо Z/nZ..................................................81
5.4. Квадратичные и кубические вычеты. Квадратичный закон взаимности.......83
5.5. Суммы Гаусса и Якоби.................................87
5.6. Квадратичные числа и квадратичные формы....................89
5.6.1. Кольцо целых квадратичных чисел..........................89
5.6.2. Идеалы квадратичных порядков.....91
5.6.3. Квадратичные формы.......................93
5.7. Алгебраические числа..................................95
Упражнения к главе 5..............................................98
Литература к главе 5................................................98
ГЛАВА 6. ЭЛЕМЕНТЫ АЛГЕБРАИЧЕСКОЙ ГЕОМЕТРИИ. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ ...99
6.1. Аффинные алгебраические многообразия ...99
6.2. Проективная плоскость и проективное пространство..............100
6.3. Сложение точек на конике...........................102
6.4. Кубические кривые. Закон сложения.........102
6.5. Особые и неособые кубики.........................105
6.6. Касательные и точки перегиба алгебраической кривой............106
6.7. Нормальные формы эллиптической кривой........................107
6.8. Группа неособых точек кубики...................108
6.9. Невозможность рациональной параметризации эллиптической кривой.....109
6.10. Параметризация эллиптической кривой с помощью эллиптических функций....110
6.10.1. Эллиптические функции..................110
6.10.2. Функция Вейерштрасса...................112
6.10.3. Параметризация эллиптической кривой над полем С..............113
6.11. Дискриминант и j-инвариант.......................115
6.12. Закон сложения точек эллиптической кривой........................115
6.13. Эллиптические кривые над числовыми полями.......................117
6.14. Изоморфизмы и эндоморфизмы эллиптических кривых.................119
6.14.1. Изоморфизмы над полями характеристики, отличной от 2 и 3 .. 119
6.14.2. Изоморфизмы над полями характеристики 3..............................120
6.14.3. Изоморфизмы надполями характеристики 2..............................121
6.14.4. Бирациональный изоморфизм кривых...................................121
6.14.5. Эндоморфизмы эллиптических кривых...................................123
6.14.6. Изоморфизмы эллиптических кривых над алгебраически незамкнутым полем.....124
6.15. Отображения алгебраических кривых........128
6.15.1. Регулярные функции и отображения......................................128
6.15.2. Рациональные функции и рациональные отображения............130
6.15.3. Проективные кривые........................131
6.15.4. Изогении эллиптических кривых.....................................132
6.15.5. Полиномы Жегалкина как функции на поверхности единичного куба............133
6.16. Дивизоры на алгебраических кривых.........134
6.16.1. Локальное кольцо точки и нормирование...................................134
6.16.2. Дивизоры...........................................135
6.16.3. Спаривание Вейля............................137
6.17. Эллиптические кривые над конечными полями................................139
6.18. Гиперэллиптические кривые.......................141
6.18.1. Функции на кривых
6.18.2. Якобиан
Упражнения к главе 6..............................................148
Литература к главе 6................................................149
ГЛАВА 7. ВЫЧИСЛИТЕЛЬНЫЕ АЛГОРИТМЫ АЛГЕБРЫ И ТЕОРИИ ЧИСЕЛ..........................151
7.1. Алгоритмы умножения.................................151
7.1.1. Алгоритм умножения Карацубы-Офмана............................151
7.1.2. Умножение в классах вычетов.........151
7.1.3. Умножение с помощью быстрого преобразования Фурье......................153
7.1.4. Модульное умножение. Метод Монтгомери...................................155
7.1.5. Деление..............................................157
7.2. Алгоритмы обращения и вычисления наибольшего общего делителя............158
7.3. Минимизация базиса решетки.....................160
7.4. Разложение над конечным полем полиномов от одной переменной................161
7.5. Извлечение квадратных и кубических корней в конечном поле.................161
7.5.1. Извлечение квадратного корня в случае q = 3 (mod 4).......................162
7.5.2. Извлечение квадратного корня в случае <7 >