Теоретический минимум и алгоритмы цифровой подписи : учебное пособие для студентов, обучающихся по направлению ''Прикладные математика и физика'', а также смежным направлениям и специальностям в области математики и естественных наук и в области техники и технологии

Молдовян Н.А. Теоретический минимум и алгоритмы цифровой подписи - 2010 ......Page 1
Оглавление ......Page 3
Введение ......Page 9
1.1.1. О существовании обратного элемента ......Page 11
1.1.3. Теорема Ферма ......Page 12
1.2. Функция Эйлера ......Page 13
1.3. Алгоритм Евклида ......Page 15
1.4. Расширенный алгоритм Евклида ......Page 16
1.5.1. Первообразные корни ......Page 18
1.5.2. Индексы по модулям р^а и 2р^а ......Page 20
1.6. Теоремы о числе классов с заданным показателем ......Page 21
1.7. Китайская теорема об остатках ......Page 23
1.8. Теоремы о числе решений степенных сравнений ......Page 24
2.1. Генерация простых чисел ......Page 29
2.2.1. Способ на основе подбора разложения функции Эйлера ......Page 30
2.2.2. Способ по стандарту ГОСТ Р 34.10-94 ......Page 31
2.3.1. Вычисление квадратных корней ......Page 33
2.3.2. Извлечение корней степени n > 2 по простому модулю ......Page 37
2.3.3. Случай модуля, равного степени простого числа ......Page 42
2.4.1. Модуль со специальной структурой ......Page 44
2.4.2. Вычисление корня большой простой степени ......Page 46
2.4.3. Сведение трудных случаев извлечения корней к задаче дискретного логарифмирования ......Page 50
2.5.1. Факторизация B-гладкого модуля RSA ......Page 51
2.5.2. Факторизация модуля RSA с использованием метода Флойда ......Page 52
2.6.1. Оптимизация переборного метода ......Page 53
2.6.2. Метод вычисления индексов ......Page 55
2.6.3. Метод Полларда ......Page 58
2.6.4. Случай составного порядка ......Page 60
2.6.5. Специальный случай дискретного логарифмирования по составному модулю ......Page 62
2.7. Алгоритм возведения в степень по модулю ......Page 63
2.8. Выполнение модульного умножения по Монтгомери ......Page 65
2.9.1. Нахождение первообразных корней ......Page 67
2.9.3. Нахождение чисел, относящихся к заданному составному показателю ......Page 68
3.1.1. Система Диффи — Хеллмана ......Page 69
3.2.1. Криптографические преобразования в RSA ......Page 70
3.2.2. Вопросы выбора параметров системы RSA ......Page 74
3.3. Протокол бесключевого шифрования ......Page 77
3.3.1. Коммутативные механизмы шифрования ......Page 78
3.3.2. Применение в электронной игре в покер ......Page 83
3.4.1. Способ Эль—Гамаля ......Page 85
3.4.2. Способ Рабина ......Page 86
3.5.2. Схема Эль—Гамаля с сокращенной длиной параметра S ......Page 87
3.5.3. Схема Эль—Гамаля с сокращенной длиной параметров S и R ......Page 88
3.5.5. Российский стандарт ГОСТ Р 34.10-94 ......Page 89
3.5.6. Схема Онга — Шнорра — Шамира ......Page 90
3.6. Доказуемо стойкие криптосистемы ......Page 91
3.6.1. Класс доказуемо стойких криптосистем ......Page 92
3.6.2. Минимизация числа расшифрованных текстов ......Page 95
3.7.2. Слепая подпись Чаума ......Page 96
3.8.1. Схема RSA ......Page 97
3.8.2. Схемы на основе сложности дискретного логарифмирования ......Page 98
3.8.3. ЭЦП Рабина ......Page 99
3.9. Экзистенциальная подделка подписи и потайные каналы в системах ЭЦП ......Page 100
4.1. Схемы с формированием подписи на основе решения системы сравнений ......Page 103
4.2. Схемы с подписью вида (k, S) ......Page 107
4.3. Схемы с RSA-модулем ......Page 109
4.4. Применение простого модуля в схемах, основанных на сложности факторизации ......Page 114
4.5. Схемы с восстановлением сообщения ......Page 117
4.6. Новые схемы ЭЦП с сокращенной длиной подписи ......Page 123
4.7. Подход к уменьшению размера подписи ......Page 128
4.8.1. Схема подписи с двухэлементным секретным ключом ......Page 134
4.8.2. Схема подписи с двухэлементным открытым ключом ......Page 139
4.8.3. Схема подписи с двухэлементным секретным ключом ......Page 140
5.1. Конечные группы и поля над векторными пространствами как примитив алгоритмов ЭЦП ......Page 145
5.2. Правила умножения базисных векторов ......Page 148
5.3. Таблицы умножения базисных векторов для случаев m = 6, 8, 10 ......Page 153
5.4. Таблицы умножения базисных векторов для случаев m = 7 и m = 11 ......Page 155
5.5. Формирование векторных полей GF(p^3) ......Page 158
5.6. Поля многомерных векторов ......Page 159
5.7. Синтез алгоритмов ЭЦП ......Page 161
5.8. Выбор конечного кольца векторов и синтез алгоритмов ЭЦП ......Page 163
5.9. Алгоритмы на основе сложности вычисления корней в конечных группах векторов ......Page 166
5.9.1. Оценка сложности задачи извлечения корней ......Page 172
5.10.1. Первый вариант задания умножения векторов ......Page 176
5.10.2. Второй вариант задания умножения векторов ......Page 178
5.10.3. Задача дискретного логарифмирования в конечном кольце двухмерных векторов ......Page 180
5.10.4. К вопросу построения схем ЭЦП на основе сложности задачи нахождения двухмерного логарифма в группе двухмерных векторов ......Page 183
5.11.1. Построение нециклических конечных групп четырехмерных векторов ......Page 185
5.11.2. Оценка сложности задачи извлечения корней в группах четырехмерных векторов ......Page 190
5.11.3. Алгоритм электронной цифровой подписи ......Page 194
5.12. Строение конечных коммутативных групп векторов ......Page 195
5.12.1. Строение примарных подгрупп ......Page 202
5.13. Алгоритмы ЭЦП на основе эллиптических кривых ......Page 205
5.13.1. ЭК над конечными полями характеристикир p≠2,3 ......Page 207
5.13.2. ЭК над конечными полями характеристик p=2 и p=3 ......Page 208
5.13.3. Алгоритм ЭЦП по стандарту ГОСТ Р 34.10-2001 ......Page 209
5.14. Алгоритмы эллиптической криптографии над векторными полями ......Page 210
6.1.1. Алгоритм ЭЦП на основе сложности задачи извлечения корней по модулю ......Page 213
6.1.2. Протокол коллективной подписи ......Page 214
6.2. Коллективная подпись на основе задачи дискретного логарифмирования ......Page 215
6.3. Коллективная подпись на основе эллиптических кривых ......Page 216
6.4.1. Композиционная подпись на основе вычислений в мультипликативных группах ......Page 219
6.4.2. Композиционная подпись на основе эллиптических кривых ......Page 220
6.4.3. Применение композиционной и коллективной подписи ......Page 223
6.5.1. Реализация на основе алгоритма ГОСТ Р 34.10-94 ......Page 224
6.5.2. Коллективная ЭЦП на основе стандарта Беларуси СТБ ......Page 228
6.6.1. Слепая коллективная подпись ......Page 230
6.6.2. Слепая подпись, взлом которой требует одновременного решения двух трудных задач ......Page 233
6.7. Протоколы слепой подписи на основе стандартов ЭЦП ......Page 237
6.7.1. Схема слепой подписи на основе ГОСТ Р 34.10-94 ......Page 238
6.7.2. Протокол слепой коллективной подписи на основе ГОСТ Р 34.10-94 ......Page 240
6.7.3. Схема слепой подписи на основе ГОСТ Р 34.10-2001 ......Page 241
6.7.4. Протокол слепой коллективной ЭЦП на основе ГОСТ Р 34.10-2001 ......Page 243
6.7.5. Протокол слепой подписи на основе стандарта СТБ 1176.2-99 ......Page 245
6.7.6. Слепая коллективная ЭЦП на основе стандарта СТБ 1176.2-99 ......Page 246
6.8.1. Использование алгоритма RSA ......Page 247
6.8.2. Коллективная ЭЦП на основе алгоритма Рабина ......Page 249
Глава 7. Некоммутативные группы как криптографический примитив ......Page 251
7.1. Новая трудная задача для синтеза криптосистем с открытым ключом ......Page 253
7.2. Схема открытого согласования ключа и алгоритм открытого шифрования ......Page 256
7.3. Алгоритм коммутативного шифрования ......Page 258
7.4. Конечные некоммутативные группы над четырехмерными векторными пространствами ......Page 259
7.5. Конечные некоммутативные группы векторов четных размерностей ......Page 264
7.6. Гомоморфизм конечных некоммутативных групп векторов и синтез криптосхем ......Page 267
7.7. Конечные группы матриц как примитив алгоритмов ЭЦП ......Page 272
7.7.1. Оценки относительной сложности операции матричного умножения ......Page 274
7.7.2. Использование конечных групп матриц над многочленами ......Page 275
7.7.3. Реализация алгоритмов электронной цифровой подписи ......Page 276
7.7.4. Использование конечных групп матриц над векторными полями ......Page 277
8.1. Общие вопросы патентования ......Page 279
8.2. Стратегия и тактика патентования ......Page 280
8.3. Порядок подачи патентной заявки ......Page 282
8.4. Пример формулы изобретения ......Page 284
8.5. Пример описания изобретения ......Page 285
Заключение ......Page 291
Список литературы ......Page 293
Статьи, использованные при написании пособия ......Page 295
Патенты РФ на способы формирования и проверки ЭЦП ......Page 297
Обложка ......Page 305