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

Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография. — М., Изд. Профессионал, 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 = 5 (mod 8), q = 9 (mod 16)......162 7.5.3. Извлечение квадратного корня в общем случае для нечетного q......163 7.5.4. Извлечение квадратного корня в случае четного q...........................163 7.5.5. Решение квадратного уравнения.....163 7.5.6. Извлечение кубического корня в конечном поле.............................164 7.6. Вычисление символа Якоби.........................165 7.7. Проверка чисел и полиномов на простоту..................................165 7.8. Разложение чисел в мнимом квадратичном порядке Z[√-D].................166 7.9. Приведение числа по модулю решетки......169 7.10. Умножение точки эллиптической кривой на число..................171 7.11. Вычисление функции Вейля........................172 7.12. Сложение элементов якобиана гиперэллиптической кривой....................173 7.13. Арифметика группы классов мнимых квадратичных порядков....................174 Упражнения к главе 7..............................................175 Литература к главе 7................................................176 ГЛАВА 8. КРИПТОГРАФИЯ И ЗАЩИТА ИНФОРМАЦИИ.......................................177 8.1. Основные понятия защиты информации.... 178 8.2. Исчисление атак............................................181 8.2.1. Упорядоченность моделей нарушителя и безопасных систем ... 181 8.2.2. Множества возможностей нарушителя........................................182 8.2.3. Тривиальная модель нарушителя.... 184 8.2.4. Нетривиальная модель нарушителя.......................................186 8.2.5. Место криптографии в защите информации.......................188 8.3. Основные понятия и определения криптографической защиты данных...........189 8.3.1. Криптографические примитивы.....189 8.3.2. Хэш-функция....................................190 8.3.3. Шифр.................................................191 8.3.4. Понятие стойкости криптографических алгоритмов......191 8.4. Шифрование.................................................192 8.4.1. Симметричное и несимметричное шифрование................................193 8.4.2. Способы шифрования......................194 8.5. Аутентификация...........................................195 8.5.1. Опознавание......................................197 8.5.2. Контроль целостности и подлинности данных........................198 8.6. Управление ключами...................................198 8.7. Задачи, положенные в основу безопасности криптографических алгоритмов........199 Упражнения к главе 8..............................................201 Литература к главе 8................................................202 ГЛАВА 9. СИСТЕМА RSA И ЗАДАЧА РАЗЛОЖЕНИЯ......................................203 9.1. Безопасность системы RSA и задача разложения на множители............203 9.2. Детерминированные методы разложения.. 204 9.2.1. Метод пробного деления.................204 9.2.2. Метод «giant step — baby step».......205 9.2.3. Метод Ферма....................................205 9.2.4. Метод диофантовой аппроксимации.................................206 9.3. Вероятностные методы разложения...........207 9.3.1. р-метод Полларда (метод «Монте-Карло»)...................207 9.3.2. Метод непрерывных дробей............207 9.3.3. Метод квадратичного решета..........209 9.3.4. (р — 1)-метод......................................210 9.3.5. Разложение на эллиптической кривой......................................210 9.3.6. Разложение на квантовом компьютере.......................................212 9.4. Атаки на систему RSA, не требующие разложения..........213 9.4.1. Случай малого секретного показателя.....................................213 9.4.2. Случаи специальных открытых показателей.................................214 9.4.3. Атаки на основе эндоморфизмов.... 215 Упражнения к главе 9..............................................216 Литература к главе 9................................................217 ГЛАВА 10. ДИСКРЕТНОЕ ЛОГАРИФМИРОВАНИЕ В КОНЕЧНОМ ПОЛЕ И СМЕЖНЫЕ ЗАДАЧИ.......218 10.1. Метод базы разложения...............................218 10.2. Логарифмирование в простом поле методом решета числового поля..........222 10.2.1. Подготовительные теоретико-числовые результаты.....222 10.2.2. Метод решета числового поля.........223 10.3. Логарифмирование в расширенном поле.....227 10.4. Группа классов мнимого квадратичного порядка....................228 10.5. Логарифмирование в группе функций Лукаша.....................229 10.6. Связь между задачами Диффи-Хеллмана и дискретного логарифмирования.....229 Упражнения к главе 10............................................230 Литература к главе 10..............................................231 ГЛАВА 11. ЗАДАЧА ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ НА ЭЛЛИПТИЧЕСКОЙ КРИВОЙ........233 11.1. Универсальные методы логарифмирования...............................233 11.1.1. Метод Гельфонда..............................233 11.1.2. Методы встречи посередине и «giant step — baby step»...............234 11.1.3. Метод Полларда................................235 11.1.4. Метод встречи на случайном дереве.........................235 11.1.5. Сравнение сложности логарифмирования на эллиптической кривой и в конечном поле.......238 11.1.6. Логарифмирование с помощью квантового компьютера....................239 11.2. Влияние комплексного умножения на сложность логарифмирования.....................240 11.3. Логарифмирование с использованием функции Вейля...........................241 11.4. Другие задачи, связанные с логарифмированием..............243 11.5. Время жизни параметров криптосистемы, основанной на дискретном логарифмировании...246 11.5.1. Мультипликативная группа поля....247 11.5.2. Группа точек эллиптической кривой......................247 11.6. Логарифмирование в якобиане гиперэллиптической кривой..................248 11.7. Требования к эллиптической кривой..........249 Упражнения к главе 11............................................250 Литература к главе 11..............................................251 ГЛАВА 12. ШИФРОВАНИЕ С ОТКРЫТЫМ КЛЮЧОМ..........................252 12.1. Шифрование с открытым ключом для группы вычислимого порядка.........252 12.1.1. Бесключевое шифрование Месси-Омуры.........................253 12.1.2. Протокол Эль-Гамаля шифрования с открытым ключом....................254 12.2. Шифрование с открытым ключом для группы трудновычислимого порядка...255 12.2.1. Протокол шифрования Рабина........256 12.2.2. Вероятностное шифрование............256 12.3. Ранцевые алгоритмы шифрования с открытым ключом....................258 12.4. Генераторы псевдослучайной последовательности............260 Упражнения к главе 12............................................261 Литература к главе 12..............................................262 ГЛАВА 13. ЦИФРОВАЯ ПОДПИСЬ.................263 13.1. Подпись на группе трудновычислимого порядка..................263 13.1.1. Схема подписи RSA.........................264 13.1.2. Схема подписи Рабина.....................264 13.1.3. Схема подписи Фиата-Шамира......265 13.2. Подпись на группе вычислимого порядка..........................265 13.2.1. Схема подписи Эль-Гамаля.............265 13.2.2. Схема подписи Шнорра...................267 13.2.3. ГОСТ Р 34.10-94 и DSS...................268 13.3. Сравнительный анализ представленных схем подписи.................269 13.4. Скрытый канал..............................................270 13.5. Другие схемы подписи.................................271 13.5.1. Схема «неоспоримой» подписи......271 13.5.2. Схема подписи «вслепую». Электронные платежи......................273 13.5.3. Схема подписи с восстановлением сообщения.......................274 13.5.4. Инкрементальная подпись...............274 Упражнения к главе 13............................................275 Литература к главе 13..............................................276 ГЛАВА 14. ДРУГИЕ КРИПТОГРАФИЧЕСКИЕ ПРОТОКОЛЫ...............................278 14.1. Схемы предъявления битов.........................278 14.2. Диалоговые доказательства с нулевым разглашением..................279 14.2.1. Доказательство знания изоморфизма графов........................279 14.2.2. Доказательство знания разложения составного числа...............280 14.2.3. Доказательство знания дискретного логарифма...................281 14.2.4. Доказательство правильности выбора составного числа.................281 14.3. Бездиалоговые доказательства с нулевым разглашением................283 14.4. Передача информации со стиранием.........................285 14.5. Разделение секрета.......................................287 14.6. Протоколы управления ключами................288 14.6.1. Установление ключа на основе симметричных методов...............289 14.6.2. Доставка ключа.................................290 14.7. Временная метка.............................................291 14.7.1. Централизованная реализация временной метки......................291 14.7.2. Децентрализованная реализация временной метки....................292 Упражнения к главе 14............................................293 Литература к главе 14..............................................293 ГЛАВА 15. КРИПТОСИСТЕМЫ НА ЭЛЛИПТИЧЕСКИХ И ГИПЕРЭЛЛИПТИЧЕСКИХ КРИВЫХ.........294 15.1. Расчет числа точек эллиптической кривой в общем случае...............294 15.1.1. Предварительные сведения..............295 15.1.2. Полиномы деления...........................296 15.1.3. Алгоритм Чуфа.................................297 15.2. Расчет числа точек эллиптической кривой над расширенным полем........299 15.3. Расчет числа точек эллиптических кривых с7 = 0, 1728 над простыми полями......301 15.3.1. Кривая у2 = х3 + В..............................301 15.3.2. Кривая у2 = х3 + Aх............................303 15.4. Эллиптические кривые с комплексным умножением....................305 15.4.1. Генерация эллиптических кривых с комплексным умножением............306 15.4.2. Влияние комплексного умножения на скорость вычислений...................308 15.5. Эллиптические кривые над расширенными полями специальных характеристик...........311 15.6. Протоколы на эллиптических кривых........314 15.6.1. Встраивание открытого текста в координату точки...........................314 15.6.2. Аналог криптосистемы RSА............315 15.6.3. Установление сеансового ключа.....316 15.6.4. Шифрование......................................317 15.6.5. Цифровая подпись............................318 15.6.6. Опознавание, канал со стиранием и доказательства с нулевым разглашением...321 15.6.7. Вычислимая в одну сторону функция, свободная от коллизий.....324 15.6.8. Генераторы псевдослучайной последовательности..........................325 15.6.9. Протоколы для электронных платежей.....................................326 15.7. Криптосистемы на гиперэллиптических кривых..................329 15.8. Криптосистемы на изогениях эллиптических кривых..........................331 15.8.1. Задача вычисления изогении и квантовый компьютер......................331 15.8.2. Криптографические протоколы на изогенных кривых........................332 Упражнения к главе 15............................................334 Литература к главе 15..............................................335 ГЛАВА 16. ОБЩИЕ СВЕДЕНИЯ ОБ ИТЕРИРОВАННЫХ КРИПТОАЛГОРИТМАХ...............336 16.1. Основные понятия классической криптографии......................336 16.2. Некоторые положения теории секретности Шеннона.................336 16.2.1. Объем текстов, однозначно определяющих ключ....................339 16.2.2. Теория аутентификации Симмонса.... 340 16.3. Булевы функции и булевы формулы...........340 16.4. Аффинно эквивалентные булевы функции и подстановки............342 16.5. Задача вскрытия ключа и математические задачи................344 16.5.1. Задача вскрытия ключа и NP-полные задачи.....................345 16.5.2. Задача о выполнимости...................345 16.6. Требования к шифрам..................................347 16.7. Шифры замены и перестановки..................350 16.7.1. Моноалфавитная замена..................350 16.7.2. Полиалфавитная замена...................351 16.8. Операторы, используемые при построении блочных шифров........353 16.9. Описание итерированных шифров в терминах булевых функций.......356 Упражнения к главе 16............................................357 Литература к главе 16..............................................358 ГЛАВА 17. АЛГЕБРАИЧЕСКИЕ МЕТОДЫ КРИПТОАНАЛИЗА.......................359 17.1. Метод обобщения и редукции. Метод гомоморфизмов.............359 17.2. Замкнутые и чистые шифры........................360 17.2.1. Вскрытие ключей замкнутых и чистых шифров..................360 17.2.2. Проверка шифра на замкнутость и чистоту....................361 17.3. Решеточный криптоанализ..........................362 17.3.1. Решеточно продолженные булевы функции и решеточные полиномы .. 362 17.3.2. Метод криптоанализа.......................365 17.4. Метод арифметического продолжения булевых функций.............369 17.5. Анализ шифров с малым порядком нелинейности...................375 17.6. Криптоанализ на основе рационального продолжения полиномов Жегалкина....377 17.6.1. Теоретические основы.....................377 17.6.2. Метод криптоанализа.......................379 17.7. Криптоанализ на основе 2-адического продолжения полиномов Жегалкина..........383 17.7.1. Теоретические основы.....................383 17.7.2. Метод криптоанализа.......................384 17.8. Максимизация числа совпавших разрядов промежуточных текстов..............385 17.9. Анализ с использованием сжимающих гомоморфизмов.......................386 17.10. Поиск коллизий хэш-функции....................388 17.11. Компромисс время/память...........................389 17.12. Сочетание перебора и вычисления ключа... 390 17.13. Отбраковка классов ключей........................391 17.14. Задачи, к которым сводится задача вскрытия ключа......................392 17.15. Вскрытие ключа на квантовом компьютере............................393 Упражнения к главе 17............................................394 Литература к главе 17..............................................395 ГЛАВА 18. СТАТИСТИЧЕСКИЕ МЕТОДЫ КРИПТОАНАЛИЗА...........................396 18.1. Некоторые определения...............................396 18.2. Дифференциальный криптоанализ..............397 18.2.1. Конечные разности...........................397 18.2.2. Метод криптоанализа.......................398 18.2.3. Анализ с помощью усеченных дифференциалов............................405 18.2.4. Анализ с помощью дифференциалов высших порядков.......................406 18.2.5. Атака «бумеранг».............................406 18.3. Криптоанализ на основе списка ключей и связанных ключей...............407 18.4. Линейный криптоанализ..............................408 18.5. Анализ степенных шифров методом сдвига...............................416 18.6. Генерация экстремальных подстановок для шифров......................418 18.6.1. Экстремальные подстановки...........418 18.6.2. Булевы функции для экстремальных подстановок............419 18.6.3. Примеры экстремальных подстановок....................................420 Упражнения к главе 18............................................422 Литература к главе 18..............................................423 ГЛАВА 19. ПРИМЕНЕНИЕ ИТЕРИРОВАННЫХ ШИФРОВ И ХЭШ-ФУНКЦИЙ...............425 19.1. Режимы шифрования....................................425 19.1.1. Режим простой замены.....................425 19.1.2. Режим гаммирования........................425 19.1.3. Режим гаммирования с обратной связью.............................426 19.1.4. Режим сцепления блоков. Выработка имитовставки.................426 19.2. Некоторые вопросы применения шифров.............................427 19.3. DES.................................................................429 19.4. FEAL..............................................................431 19.5. IDEA...............................................................432 19.6. ГОСТ 28147-89.............................................433 19.6.1. Стойкость шифра ГОСТ 28147-89 ....435 19.6.2. Стойкость шифра ГОСТ 28147-89 при наличии у нарушителя лабораторных возможностей......435 19.7. RC5.................................................................436 19.8. Blowfish..........................................................438 19.9. SAFER............................................................439 19.10. RIJNDAEL (AES)...........................................440 19.11. MD5................................................................441 19.12. ГОСТ P 34.11-94...........................................442 Упражнения к главе 19............................................444 Литература к главе 19..............................................445 ОТВЕТЫ И УКАЗАНИЯ К УПРАЖНЕНИЯМ..............................................447

загрузка...
Поделиться ссылкой:
  • Добавить ВКонтакте заметку об этой странице
  • Мой Мир
  • Facebook
  • Twitter
  • LiveJournal
  • В закладки Google
  • Яндекс.Закладки
  • Сто закладок
  • Blogger
  • Блог Li.ру
  • Блог Я.ру
  • Одноклассники
  • RSS

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Наш сайт находят по фразам: