Теоретический минимум и алгоритмы цифровой подписи
Н.А. Молдовян
Подробно рассмотрен минимальный математический аппарат, используемый при изучении криптосистем с открытым ключом, синтезе и анализе алгоритмов электронной цифровой подписи и коммутативного шифрования, протоколов открытого распределения ключей и открытого шифрования. Приводятся классические и новые криптосхемы с открытым ключом, их применение в информационных технологиях. Описываются стандарты ЭЦП, протоколы слепой и коллективной подписи. Рассмотрены различные способы задания конечных алгебраических структур, в том числе и некоммутативных, для синтеза алгоритмов ЭЦП и повышения их производительности. Отражены вопросы патентования криптоалгоритмов.
Для аспирантов, студентов и преподавателей высших учебных заведений.
Издательство: БХВ-Петербург, 2010 г.
ISBN 978-5-9775-0585-7
Количество страниц: 304.
Содержание книги «Теоретический минимум и алгоритмы цифровой подписи»:
- 1 Введение
- 3 Глава 1. Элементы теории чисел
- 3 1.1. Некоторые определения и утверждения
- 3 1.1.1. О существовании обратного элемента
- 4 1.1.2. О делимости остатка
- 4 1.1.3. Теорема Ферма
- 5 1.2. Функция Эйлера
- 7 1.2.1. Обобщенная теорема Эйлера
- 7 1.3. Алгоритм Евклида
- 8 1.4. Расширенный алгоритм Евклида
- 10 1.5. Показатели и первообразные корни
- 10 1.5.1. Первообразные корни
- 12 1.5.2. Индексы по модулям pα и 2pα
- 13 1.6. Теоремы о числе классов с заданным показателем
- 15 1.7. Китайская теорема об остатках
- 16 1.8. Теоремы о числе решений степенных сравнений
- 3 1.1. Некоторые определения и утверждения
- 21 Глава 2. Алгоритмы двухключевой криптографии
- 21 2.1. Генерация простых чисел
- 22 2.2. Детерминистическая генерация больших простых чисел
- 22 2.2.1. Способ на основе подбора разложения функции Эйлера
- 23 2.2.2. Способ по стандарту ГОСТ Р 34.10-94
- 25 2.3. Извлечение корней по модулю
- 25 2.3.1. Вычисление квадратных корней
- 29 2.3.2. Извлечение корней степени n > 2 по простому модулю
- 34 2.3.3. Случай модуля, равного степени простого числа
- 36 2.4. Трудный случай извлечения корней по простому модулю
- 36 2.4.1. Модуль со специальной структурой
- 38 2.4.2. Вычисление корня большой простой степени
- 42 2.4.3. Сведение трудных случаев извлечения корней к задаче дискретного логарифмирования
- 43 2.5. Алгоритмы факторизации
- 43 2.5.1. Факторизация B-гладкого модуля RSA
- 44 2.5.2. Факторизация модуля RSA с использованием метода Флойда
- 45 2.6. Методы дискретного логарифмирования
- 45 2.6.1. Оптимизация переборного метода
- 47 2.6.2. Метод вычисления индексов
- 50 2.6.3. Метод Полларда
- 52 2.6.4. Случай составного порядка
- 54 2.6.5. Специальный случай дискретного логарифмирования по составному модулю
- 55 2.7. Алгоритм возведения в степень по модулю
- 57 2.8. Выполнение модульного умножения по Монтгомери
- 59 2.9. Нахождение чисел заданного порядка
- 59 2.9.1. Нахождение первообразных корней
- 60 2.9.2. Нахождение чисел простого порядка
- 60 2.9.3. Нахождение чисел, относящихся к заданному составному показателю
- 61 Глава 3. Краткий обзор классических криптосистем с открытым ключом
- 61 3.1. Открытое распределение ключей
- 61 3.1.1. Система Диффи — Хеллмана
- 62 3.1.2. Распределение ключей в системе RSA
- 62 3.2. Криптосистема RSA
- 62 3.2.1. Криптографические преобразования в RSA
- 66 3.2.2. Вопросы выбора параметров системы RSA
- 69 3.3. Протокол бесключевого шифрования
- 70 3.3.1. Коммутативные механизмы шифрования
- 75 3.3.2. Применение в электронной игре в покер
- 77 3.4. Открытое шифрование
- 77 3.4.1. Способ Эль—Гамаля
- 78 3.4.2. Способ Рабина
- 79 3.5. Схемы ЭЦП на основе сложности дискретного логарифмирования
- 79 3.5.1. Схема Эль—Гамаля
- 79 3.5.2. Схема Эль—Гамаля с сокращенной длиной параметра S
- 80 3.5.3. Схема Эль—Гамаля с сокращенной длиной параметров S и R
- 81 3.5.4. Американский стандарт DSA
- 81 3.5.5. Российский стандарт ГОСТ Р 34.10-94
- 82 3.5.6. Схема Онга — Шнорра — Шамира
- 83 3.5.7. ЭЦП Шнорра
- 83 3.6. Доказуемо стойкие криптосистемы
- 84 3.6.1. Класс доказуемо стойких криптосистем
- 87 3.6.2. Минимизация числа расшифрованных текстов
- 88 3.7. Слепая подпись
- 88 3.7.1. Слепая подпись на основе ЭЦП Шнорра
- 88 3.7.2. Слепая подпись Чаума
- 89 3.8. Схемы ЭЦП с восстановлением сообщения
- 89 3.8.1. Схема RSA
- 90 3.8.2. Схемы на основе сложности дискретного логарифмирования
- 91 3.8.3. ЭЦП Рабина
- 92 3.9. Экзистенциальная подделка подписи и потайные каналы в системах ЭЦП
- 61 3.1. Открытое распределение ключей
- 95 Глава 4. Схемы ЭЦП с новым механизмом формирования подписи
- 95 4.1. Схемы с формированием подписи на основе решения системы сравнений
- 99 4.2. Схемы с подписью вида (k, S)
- 101 4.3. Схемы с RSA-модулем
- 106 4.4. Применение простого модуля в схемах, основанных на сложности факторизации
- 109 4.5. Схемы с восстановлением сообщения
- 115 4.6. Новые схемы ЭЦП с сокращенной длиной подписи
- 120 4.7. Подход к уменьшению размера подписи
- 126 4.8. Схемы подписи на основе сложности извлечения корней в группах известного порядка
- 126 4.8.1. Схема подписи с двухэлементным секретным ключом
- 131 4.8.2. Схема подписи с двухэлементным открытым ключом
- 132 4.8.3. Схема подписи с двухэлементным секретным ключом
- 137 Глава 5. Алгоритмы электронной цифровой подписи на основе конечных векторных пространств
- 137 5.1. Конечные группы и поля над векторными пространствами как примитив алгоритмов ЭЦП
- 140 5.2. Правила умножения базисных векторов
- 145 5.3. Таблицы умножения базисных векторов для случаев m = 6, 8, 10
- 147 5.4. Таблицы умножения базисных векторов для случаев m = 7 и m = 11
- 150 5.5. Формирование векторных полей GF(p3)
- 151 5.6. Поля многомерных векторов
- 153 5.7. Синтез алгоритмов ЭЦП
- 155 5.8. Выбор конечного кольца векторов и синтез алгоритмов ЭЦП
- 158 5.9. Алгоритмы на основе сложности вычисления корней в конечных группах векторов
- 164 5.9.1. Оценка сложности задачи извлечения корней
- 168 5.10. Гомоморфизмы групп двухмерных векторов и синтез алгоритмов ЭЦП
- 168 5.10.1. Первый вариант задания умножения векторов
- 170 5.10.2. Второй вариант задания умножения векторов
- 172 5.10.3. Задача дискретного логарифмирования в конечном кольце v двухмерных векторов
- 175 5.10.4. К вопросу построения схем ЭЦП на основе сложности задачи нахождения двухмерного логарифма в группе двухмерных векторов
- 177 5.11. Группы четырехмерных векторов частного вида
- 177 5.11.1. Построение нециклических конечных групп четырехмерных векторов
- 182 5.11.2. Оценка сложности задачи извлечения корней в группах четырехмерных векторов
- 186 5.11.3. Алгоритм электронной цифровой подписи
- 187 5.12. Строение конечных коммутативных групп векторов
- 194 5.12.1. Строение примарных подгрупп
- 197 5.13. Алгоритмы ЭЦП на основе эллиптических кривых
- 199 5.13.1. ЭК над конечными полями характеристики p≠2, 3
- 200 5.13.2. ЭК над конечными полями характеристик p=2 и p=3
- 201 5.13.3. Алгоритм ЭЦП по стандарту ГОСТ Р 34.10-2001
- 202 5.14. Алгоритмы эллиптической криптографии над векторными полями
- 205 Глава 6. Протоколы формирования коллективной ЭЦП
- 205 6.1. Коллективная ЭЦП
- 205 6.1.1. Алгоритм ЭЦП на основе сложности задачи извлечения корней по модулю
- 206 6.1.2. Протокол коллективной подписи
- 207 6.2. Коллективная подпись на основе задачи дискретного логарифмирования
- 208 6.3. Коллективная подпись на основе эллиптических кривых
- 211 6.4. Композиционная ЭЦП
- 211 6.4.1. Композиционная подпись на основе вычислений в мультипликативных группах
- 212 6.4.2. Композиционная подпись на основе эллиптических кривых
- 215 6.4.3. Применение композиционной и коллективной подписи
- 216 6.5. Коллективная подпись на основе стандартов ЭЦП
- 216 6.5.1. Реализация на основе алгоритма ГОСТ Р 34.10-94
- 220 6.5.2. Коллективная ЭЦП на основе стандарта Беларуси СТБ
- 222 6.6. Специальные протоколы слепой подписи
- 222 6.6.1. Слепая коллективная подпись
- 225 6.6.2. Слепая подпись, взлом которой требует одновременного решения двух трудных задач
- 229 6.7. Протоколы слепой подписи на основе стандартов ЭЦП
- 230 6.7.1. Схема слепой подписи на основе ГОСТ Р 34.10-94
- 232 6.7.2. Протокол слепой коллективной подписи на основе ГОСТ Р 34.10-94
- 233 6.7.3. Схема слепой подписи на основе ГОСТ Р 34.10-2001
- 235 6.7.4. Протокол слепой коллективной ЭЦП на основе ГОСТ Р 34.10-2001
- 237 6.7.5. Протокол слепой подписи на основе стандарта СТБ 1176.2-99
- 238 6.7.6. Слепая коллективная ЭЦП на основе стандарта СТБ 1176.2-99
- 239 6.8. Коллективная ЭЦП на основе сложности задачи факторизации
- 239 6.8.1. Использование алгоритма RSA
- 241 6.8.2. Коллективная ЭЦП на основе алгоритма Рабина
- 205 6.1. Коллективная ЭЦП
- 243 Глава 7. Некоммутативные группы как криптографический примитив
- 245 7.1. Новая трудная задача для синтеза криптосистем с открытым ключом
- 248 7.2. Схема открытого согласования ключа и алгоритм открытого шифрования
- 250 7.3. Алгоритм коммутативного шифрования
- 251 7.4. Конечные некоммутативные группы над четырехмерными векторными пространствами
- 256 7.5. Конечные некоммутативные группы векторов четных размерностей
- 259 7.6. Гомоморфизм конечных некоммутативных групп векторов и синтез криптосхем
- 264 7.7. Конечные группы матриц как примитив алгоритмов ЭЦП
- 266 7.7.1. Оценки относительной сложности операции матричного умножения
- 267 7.7.2. Использование конечных групп матриц над многочленами
- 268 7.7.3. Реализация алгоритмов электронной цифровой подписи
- 269 7.7.4. Использование конечных групп матриц над векторными полями
- 271 Глава 8. Как запатентовать алгоритм ЭЦП
- 271 8.1. Общие вопросы патентования
- 272 8.2. Стратегия и тактика патентования
- 274 8.3. Порядок подачи патентной заявки
- 276 8.4. Пример формулы изобретения
- 277 8.5. Пример описания изобретения
- 283 Заключение
- 285 Список литературы
- 287 Список рекомендуемой дополнительной литературы
- 287 Статьи, использованные при написании пособия
- 289 Патенты РФ на способы формирования и проверки ЭЦП
Инструкция как скачать книгу Н.А. Молдовян: Теоретический минимум и алгоритмы цифровой подписи в форматах DjVu, PDF, DOC или fb2 совершенно бесплатно.