<< Предыдущая

стр. 2
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

12.1. Обилие сведения о цифровых подписях 316
12.2. Цифровые сертификаты и PKI 317
12.3. Пример приложения инфраструктуры открытых ключей . 323
12.3.1. PGP 323
12.3.2. Протокол защиш;енных сокетов 324
12.3.3. Сертификаты X50S/ 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. Сильные i?S'Л-пpeдпoлoжeния 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.
Заы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
Предисловие

Можно спросить: зачем нужен еще один учебник по криптогра­
фии? Уже написано множество книг, одни из которых дают общее
представление обо всех областях криптографии, например Шнайер
(Schneier), в то время как другие посвящены энциклопедическому
изложению предмета, подобно «Справочнику прикладной крипто­
графии» {Handbook of Applied Cryptography или НАС). Однако ни
одна из них не подходит д^ля начального курса. Кроме того, тех­
нический подход к алгоритмам с открытым ключом заметно изме­
нился за последние несколько лет, в частности, появилось понятие
«доказуемой стойкости». Теперь криптографы не пускаются в длин­
ные интуитивные обоснования безопасности своих шифров. Сейчас
есть система понятий и методов, которая позволяет свести вопрос о
безопасности криптосистемы к другим хорошо изученным задачам.
Курсы по криптографии в настоящее время читаются во всех
ведущих университетах. Иногда их включают в программу мате­
матических факультетов, иногда — в программу факультетов вы­
числительной техники или электронного машиностроения. Действи­
тельно, как правило, отдельный курс по этой науке необходим сту­
дентам всех трех упомянутых специальностей, плюс некоторым уча­
щимся, слушающим этот раздел науки в качестве дополнительного
спецкурса. Подготовка студентов на этих факультетах, как и цели,
стоящие перед ними, различны. Некоторым из них достаточно крат­
кого обзора существующих алгоритмов и умения их применять, в
то время как других необходимо подвести к переднему краю мно­
гообразных современных исследований. Следовательно, возникает
насущная потребность в учебнике, начинающемся с самых основ и
ведущего студентов сквозь дебри понятий и методов до тех пор, по­
ка они не смогут свободно пользоваться специальной литературой.
Настоящий учебник предназначен студентам третьего - четвер­
того года обучения по специальности «вычислительная техника и
информатика». Предполагается, что читатель знаком с основами
дискретной математики (в частности, с арифметикой остатков) и
имеет представление о задачах и методах теории вероятностей. Кро­
ме того, автор надеется, что читатель прошел (хотя и плохо по­
мнит) начальный курс математического анализа. Не то, чтобы ма-
Предисловие

тематический анализ был так уж необходим ^\ля изучения крипто­
графии, но умение свободно оперировать формулами и символами
безусловно полезно. Тем не менее, вся необходимая предваритель­
ная информация будет здесь представлена, так что учебник может
читать даже тот, кто все основательно забыл или не знал вовсе.
Студентам, желающим углубиться в необходимую для криптогра­
фии математику или нуждающимся в дополнительной информации,
предназначено приложение А, в котором содержится выжимка из
основ алгебры и приведены все понятия, необходимые для изучения
современных криптосистем с отрытым ключом.
Это довольно стандартный курс для будущих специалистов в
вычислительной технике и информатике, не включающий в себя
многого из теории сложности и формальных методов. Большинство
аналогичных курсов сконцентрировано на разработке программно­
го обеспечения и приложениях вычислительной техники к таким
областям, как графика, распознавание образов или искусственный
интеллект. Главная цель этих курсов состоит скорее в подготов­
ке специалистов-прикладников, чем в воспитании любителей поко­
паться в теоретических аспектах предмета. Поэтому я рассказываю
о некоторых разделах теории вычислительных систем и информа­
тики там, где они требуются. В результате одна глава посвящена
приложениям теории сложности в криптографии, а другая имеет
дело с формальными подходами к разработке протоколов. Обе эти
главы можно читать без какой-либо предварительной подготовки в
теории сложности и формальных методах.
Многие из подходов этой книги к алгоритмам с открытым клю­
чом редукционны по своей природе, что является обычным для со­
временной разработки протоколов и составляет главное отличие мо­
его учебника от остальных курсов криптографии. Редукционный
подход — следствие техники, применяемой в теории сложности, где
принято доказывать сводимость одной сложной задачи к другой.
Это делается в предположении, что трудноразрешимость второй
задачи — непререкаемая истина, и показывается, как это свойство
можно использовать при решении первой. В настоящей книге стой­
кость криптографических схем неоднократно исследуется именно
таким способом, а в конце ее приводится краткий обзор доказуе­
мой стойкости.
Учитывая интересы потенциального читателя, многие места в
книге лишены абсолютной математической строгости. Часто, на­
пример, вместо полных доказательств приводятся лишь их схемы.
Предисловие

Тем не менее я стремился показать привлекательность используемой
математики. Я пытался доступно объяснить, почему протокол был
разработан именно таким, а не другим способом. ^1итатели, предпо­
читающие более глубокое и математически обоснованное изучение
всех пропущенных или вскользь упомянутых моментов, могут обра­
титься к учебникам, подходящий к теме список которых приводится
в разделе «Дополнительная литература» в конце каждой главы.
С другой стороны, терминология групп и конечных полей упо­
требляется практически с самого начала книги. Делается это по
двум причинам. Во-первых, терминология снабдит читателя необ­
ходимым словарем, чтобы он мог самостоятельно изучать отчеты
о последних достижениях в области криптологии и, как следствие,
приступил к самостоятельным изысканиям. Во-вторых, студенты,
даже не стремящиеся продвинуться в изучении предмета до аспи­
рантского уровня, при столкновении с «реальным миром», напри­
мер при описании программных интерфейсов (API) и стандартов
документов, найдут эту терминологию очень полезной. Предлагае­
мый курс опробован в Бристоле на студентах, у которых не было
никакой подготовки в этой области математики. Практика показа­
ла, что соседство абстрактных понятий с реальными конкретными
примерами и мотивациями дает очень хорошие результаты.
Я всегда полагал, что трудности при первом знакомстве с про­
токолами и криптосистемами заключаются в отделении открытой
части алгоритма от той, которую пользователи стремятся хранить
в тайне. Особенно явно убеждаешься в этом, когда впервые сталки­
ваешься с шифрующим алгоритмом с открытым ключом или пред­
принимаешь попытки расколоть шифр замены. Чтобы помочь чи­
тателю преодолеть указанные трудности, открытые чисти шифра
или шифрограммы, как правило, набираются прописными буквами,
а секретные (исходное сообщение, ключ) — строчными. Такое выде­
ление будет применяться всюду, где оно может помочь разобрать­
ся в объяснениях. В других ситуациях, когда смысл написанного
прозрачен или все упоминающиеся данные секретны, набор текста
имеет стандартный вид.
Каждая глава организована таким образом, чтобы любой жела­
ющий мог изучать книгу самостоятельно, а именно:
- краткий список тем, раскрываемых в главе, с самого начала
дающий представление о том, с чем Вам предстоит столкнуться,
- текст главы,
- краткое содержание главы, которое представлено в виде те-
предисловие

<< Предыдущая

стр. 2
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>