Теоретический минимум и алгоритмы цифровой подписи

Содержание книги «Теоретический минимум и алгоритмы цифровой подписи»:

• 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. Теоремы о числе решений степенных сравнений
• 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. Экзистенциальная подделка подписи и потайные каналы в системах ЭЦП
• 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(p³)
  • 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. Коллективная ЭЦП на основе алгоритма Рабина
• 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 Патенты РФ на способы формирования и проверки ЭЦП