Предисловие | 13 |
|
Часть I. Предварительные математические сведения |
|
Глава 1. |
Арифметика остатков, группы, конечные поля и вероятность | 22 |
1.1. Арифметика остатков | 22 |
1.1.1. Группы и кольца | 24 |
1.1.2. Функция Эйлера | 26 |
1.1.3. Мультипликативные обратные по модулю N | 28 |
1.2. Конечные поля | 30 |
1.3. Основные алгоритмы | 34 |
1.3.1. Наибольший общий делитель | 34 |
1.3.2. Китайская теорема об остатках | 39 |
1.3.3. Символы Лежандра и Якоби | 41 |
1.4. Вероятность | 46 |
1.4.1. Теорема Байеса | 48 |
1.4.2. Парадокс дней рождения | 49 |
|
Глава 2. |
Эллиптические кривые | 53 |
2.1. Введение | 53 |
2.2. Групповой закон | 56 |
2.3. Эллиптические кривые над конечными полями | 60 |
2.3.1. Кривые над полем характеристики р > 3 | 62 |
2.3.2. Кривые над полем характеристики 2 | 62 |
2.4. Проективные координаты | 63 |
2.4.1. Большая характеристика | 64 |
2.4.2. Чётная характеристика | 65 |
2.5. Сжатие точек | 65 |
2.5.1. Случай большой характеристики поля | 66 |
2.5.2. Чётная характеристика | 67 |
|
Часть II. Симметричное шифрование |
|
Глава 3. |
Исторические шифры | 71 |
3.1. Введение | 71 |
3.2. Шифр сдвига | 73 |
3.3. Шифр замены | 77 |
3.4. Шифр Виженера | 81 |
3.5. Перестановочные шифры | 87 |
3.6. Одноразовый шифр-блокнот | 88 |
3.7. Роторные машины и «Энигма» | 88 |
|
Глава 4. |
Теоретико-информационная стойкость | 96 |
4.1. Введение | 96 |
4.2. Вероятность и шифры | 98 |
4.2.1. Модифицированный шифр сдвига | 105 |
4.2.2. Шифр Вернама | 105 |
4.3. Энтропия | 106 |
4.4. Ложные ключи и расстояние единственности | 113 |
|
Глава 5. |
Симметричные шифры | 122 |
5.1. Введение | 122 |
5.1.1. Упрощенная модель | 124 |
5.1.2. Поточные шифры | 125 |
5.1.3. Блочные шифры | 127 |
5.2. Шифр Фейстеля и DES | 131 |
5.2.1. Обзор действия шифра DES | 133 |
5.2.2. Разворачивание ключа в DES | 136 |
5.3. Rijndael | 138 |
5.3.1. Операции алгоритма Rijndael | 140 |
5.3.2. Структура раундов | 143 |
5.3.3. Разворачивание ключа | 144 |
5.4. Режимы работы DES | 144 |
5.4.1. Режим ECB | 145 |
5.4.2. Режим CBC | 146 |
5.4.3. Режим OFB | 147 |
5.4.4. Режим CFB | 148 |
5.5. Подлинность сообщений | 149 |
5.6. Современные поточные шифры | 151 |
5.6.1. РСЛОС | 151 |
5.6.2. Комбинирование РСЛОС | 156 |
5.6.3. RC4 | 157 |
|
Глава 6. |
Распределение симметричных ключей | 162 |
6.1. Управление ключами | 162 |
6.1.1. Распределение ключей | 163 |
6.1.2. Выбор ключа | 164 |
6.1.3. Время жизни ключа | 165 |
6.1.4. Разделение секрета | 166 |
6.2. Распределение секретных ключей | 167 |
6.2.1. Обозначения | 168 |
6.2.2. Протокол широкоротой лягушки | 169 |
6.2.3. Протокол Нидхейма-Шредера | 170 |
6.2.4. Протокол Отвэй-Риса | 172 |
6.2.5. Цербер | 173 |
6.3. Формальные методы проверки протоколов | 174 |
6.3.1. Анализ протокола широкоротой лягушки | 177 |
|
Часть III. Криптосистемы с открытым ключом и подписи |
|
Глава 7. |
Основные алгоритмы шифрования с открытым ключом | 183 |
7.1. Криптография с открытым ключом | 183 |
7.2. Односторонние функции | 185 |
7.3. RSA | 192 |
7.3.1. Шифрование RSA и одноимённая задача | 193 |
7.3.2. Секретная экспонента и проблема факторизации | 194 |
7.3.3. Значение функции Эйлера φ(N) и проблема |
факторизации | 196 |
7.3.4. Разделённый модуль | 197 |
7.3.5. Использование малых шифрующих экспонент | 198 |
7.4. Криптосистема Эль-Гамаль | 200 |
7.5. Криптосистема Рабина | 203 |
|
Глава 8. |
Тесты на простоту и факторизация | 209 |
8.1. Простые числа | 209 |
8.1.1. Пробное деление | 210 |
8.1.2. Тест Ферма | 211 |
8.1.3. Тест Миллера-Рабина | 213 |
8.1.4. Доказательство простоты | 214 |
8.2. Алгоритмы факторизации | 215 |
8.2.1. Пробное деление | 216 |
8.2.2. Гладкие числа | 217 |
8.2.3. (Р - 1)-метод Полларда | 218 |
8.2.4. Разность квадратов | 220 |
8.3. Современные методы факторизации | 221 |
8.3.1. Комбинирование соотношений | 222 |
8.4. Метод решета в числовом поле | 224 |
8.4.1. Линейное решето | 224 |
8.4.2. Решето в числовом поле | 227 |
8.4.3. Как найти множество S? | 228 |
8.4.4. Как извлекать квадратные корни? | 230 |
8.4.5. Выбор начальных многочленов | 231 |
8.4.6. Пример | 231 |
|
Глава 9. |
Дискретные логарифмы | 236 |
9.1. Введение | 236 |
9.2. Метод Полига-Хеллмана | 236 |
9.2.1. Определяем x4 | 239 |
9.2.2. Ищем x9 | 239 |
9.2.3. Определяем x11 | 240 |
9.3. Шаги младенца/шаги гиганта | 240 |
9.4. Методы Полларда | 243 |
9.4.1. ρ-метод Полларда | 243 |
9.4.2. λ-метод Полларда | 247 |
9.4.3. Параллельный р-метод | 249 |
9.5. Суб-экспоненциальные методы в числовых полях | 251 |
9.6. Специальные методы для эллиптической кривой | 253 |
|
Глава 10. |
Распределение ключей, схемы подписей и хэш-функции | 257 |
10.1. Распределение ключей Диффи-Хеллмана | 257 |
10.2. Схемы цифровой подписи | 261 |
10.3. Хэш-функции | 264 |
10.3.1. Семейство MD4 | 268 |
10.3.2. Хэш-функции и блочные шифры | 270 |
10.4. Алгоритмы цифровой подписи | 271 |
10.5. Подпись Шнорра | 276 |
10.6. Подпись Ниберга-Руппеля | 278 |
10.7. Соглашение об аутентифицированном ключе | 280 |
|
Глава 11. |
Реализация операций | 286 |
11.1. Введение | 286 |
11.2. Алгоритмы возведения в степень | 287 |
11.3. Потенцирование в RSA | 292 |
11.3.1. Шифрование (проверка подписи) в RSA | 293 |
11.3.2. Расшифровывание (подписывание) в RSA | 293 |
11.4. Потенцирование в DSA | 294 |
11.5. Арифметика многократной точности | 295 |
11.5.1. Сложение | 295 |
11.5.2. Умножение в столбик | 296 |
11.5.3. Умножение Карацубы | 297 |
11.5.4. Деление | 298 |
11.5.5. Арифметика Монтгомери | 299 |
11.6. Арифметика в конечных полях | 303 |
|
Глава 12. |
Получение аутентичного открытого ключа | 316 |
12.1. Общие сведения о цифровых подписях | 316 |
12.2. Цифровые сертификаты и PKI | 317 |
12.3. Пример приложения инфраструктуры открытых ключей | 323 |
12.3.1. PGP | 323 |
12.3.2. Протокол защищённых сокетов | 324 |
12.3.3. Сертификаты Х509 | 326 |
12.3.4. SPKI | 327 |
12.4. Другие приложения третьей доверенной стороны | 330 |
12.5. Неявные сертификаты | 332 |
12.5.1. Описание системы | 332 |
12.5.2. Запрос сертификата | 333 |
12.5.3. Обработка запроса | 333 |
12.5.4. Действия Алисы | 333 |
12.5.5. Действия пользователя | 333 |
12.6. Криптография идентификационной информации | 334 |
|
Глава 13. |
Протоколы | 337 |
13.1. Введение | 337 |
13.2. Схемы обязательств | 337 |
13.3. Доказательства с нулевым разглашением | 341 |
13.4. Система электронного голосования | 347 |
13.4.1. Установки системы | 348 |
13.4.2. Заполнение бюллетеня | 348 |
13.4.3. Распределение бюллетеней | 348 |
13.4.4. Проверка достоверности информации | 349 |
13.4.5. Подсчет голосов | 349 |
|
Часть IV. Проблемы стойкости |
|
Глава 14. |
Атаки на схемы с открытым ключом | 353 |
14.1. Введение | 353 |
14.2. Атака Винера на RSA | 354 |
14.3. Решётки и приведённые базисы | 356 |
14.4. Атаки на RSA, основанные на решётках | 362 |
14.4.1. Атака Хастада | 365 |
14.4.2. Атака Франклина-Рейтера и обобщение Копперсмита | 366 |
14.4.3. Обобщение атаки Винера | 368 |
14.5. Частичное раскрытие ключа | 369 |
14.5.1. Частичное раскрытие секретной экспоненты в RSA | 369 |
14.5.2. Частичное раскрытие простых множителей модуля RSA | 370 |
14.5.3. Частичное раскрытие младших значащих цифр |
секретной экспоненты RSA | 370 |
14.6. Анализ дефектов | 371 |
|
Глава 15. |
Определения стойкости | 375 |
15.1. Стойкость шифрования | 375 |
15.1.1. Понятия стойкости | 376 |
15.1.2. Виды атак | 378 |
15.1.3. Другие концепции стойкости | 381 |
15.2. Стойкость актуальных алгоритмов шифрования | 382 |
15.2.1. RSA | 383 |
15.2.2. Эль-Гамаль | 384 |
15.3. Семантически стойкие системы | 386 |
15.4. Стойкость подписей | 389 |
|
Глава 16. |
Теоретическая сложность | 393 |
16.1. Классы полиномиальной сложности | 393 |
16.2. Криптосистемы, основанные на задаче о рюкзаке | 398 |
16.3. Битовая стойкость | 403 |
16.3.1. Сильные предикаты для дискретных логарифмов | 404 |
16.3.2. Сильные предикаты для задачи RSA | 405 |
16.4. Случайная саморедукция | 406 |
16.5. Рандомизированные алгоритмы | 408 |
|
Глава 17. |
Доказуемая стойкость со случайным оракулом | 414 |
17.1. Введение | 414 |
17.2. Стойкость алгоритмов подписи | 417 |
17.2.1. Примеры пассивного противника | 419 |
17.2.2. Активный противник | 421 |
17.2.3. RSA-FDH | 423 |
17.2.4. RSA-PSS | 424 |
17.3. Стойкость шифрующих алгоритмов | 426 |
17.3.1. Иммунизация криптосистем, основанных на Эль-Гамаль | 426 |
17.3.2. RSA-OAEP | 430 |
17.3.3. Преобразование схем СРА в схемы ССА2 | 434 |
|
Глава 18. |
Доказуемая стойкость без случайного оракула | 438 |
18.1. Введение | 438 |
18.2. Некоторые новые задачи | 439 |
18.2.1. Сильные RSA-предположения | 439 |
18.2.2. Интерактивные хэш-предположения Диффи-Хеллмана | 440 |
18.3. Схемы подписи | 441 |
18.3.1. Схема подписи Дженнаро-Галеви-Рабина | 442 |
18.3.2. Схема подписи Крамера-Шоупа | 443 |
18.4. Алгоритмы шифрования | 445 |
18.4.1. Схема шифрования Крамера-Шоупа | 445 |
18.4.2. Схема шифрования DHIES | 448 |
|
Приложение А. |
Основная математическая терминология | 454 |
А.1. Множества | 454 |
А.2. Отношения | 455 |
А.З. Функции | 457 |
А.4. Перестановки | 460 |
А.5. Операции | 463 |
А.6. Группы | 466 |
А.6.1. Нормальные подгруппы и классы смежности | 470 |
А.6.2. Факторгруппы | 473 |
А.6.3. Гомоморфизмы | 475 |
А.7. Кольца | 479 |
А.8. Поля | 480 |
А.9. Векторные пространства | 482 |
А.9.1. Подпространства | 483 |
А.9.2. Свойства векторов | 483 |
А.9.3. Размерность и базисы | 485 |
|
Приложение Б. |
Примеры на языке Java | 489 |
Б.1. Блочные шифры | 490 |
Б.2. Шифрование с открытым ключом | 492 |
Б.З. Хэш-функции | 494 |
Б.4. Цифровые подписи | 495 |
Б.5. Доказательства с нулевым разглашением и обязательства | 499 |
Б.5.1. Parameters.java | 499 |
Б.5.2. Private_Commitment.Java | 500 |
Б.5.3. Public_Commitment.java | 501 |
Б.5.4. Commitment_Factory.java | 501 |
Б.5.5. Proof.java | 502 |
Б.5.6. prog.java | 505 |
|
Дополнение 1. |
Зашифрованные поисковые системы | 507 |
Д.1.1. Введение | 507 |
Д.1.2. Стохастическая технология и семантический анализ текста | 507 |
Д.1.3. Логический вывод на основе стохастической технологии | 509 |
Д.1.4. Семантический анализ зашифрованных текстов | 511 |
Д.1.5. Универсальность защищённых поисковых систем | 515 |
|
Дополнение 2. |
Сетевая система с абсолютной стойкостью | 518 |
Д.2.1. Процесс формирования и использования сетевых |
одноразовых ключей | 518 |
Д.2.2. Реализация одноразового режима шифрования в системе |
с применением перекодера ЦСФКП | 520 |
|
Предметный указатель | 524 |