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

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

ОГЛАВЛЕНИЕ

Следующая >>

ты ключей пользователей. Но здесь это невозможно сделать,
поскольку открытые ключи пользователей выбираются в диа­
логовом режиме в процессе создания сертификата.
- Неявные сертификаты требуют, чтобы как ЦС, так и поль­
зователь работали на одном уровне секретности. Это обычно
считается не лучшим требованием. Как правило, ЦС работа­
ет на более высоком уровне засекреченности (скажем 2048-
битовом DSA)^ чем пользователь (1024-битовый DSA),
Однако для устройств с ограниченной пропускной способностью не­
явные сертификаты могут быть подходящей альтернативой тради­
ционных сертификатов, если последние не доступны.


12.6. Криптография идентификационной
информации
Другой способ удостоверения открытых ключей, не прибегающий к
сертификатам, состоит в использовании системы, посредством ко­
торой ключ пользователя получается из его идентификатора, на­
пример, имени. Система называется схемой шифрования с иденти­
фикационной информацией или схемой подписи с идентификацион­
ной информацией. Такие системы все еще нуждаются в доверенном
третьем лице р^ля первоначального установления подлинности поль­
зователя, но здесь уже не нужно хранить и передавать сертификаты.
Первая схема такого типа подписи разработана Шамиром в 1984 г,
хотя вплоть до 2001 г. считалось, что авторами схемы подписи с
идентификационной информацией являются Бонех и Франклин. Мы
опишем лишь оригинальную схему подписи Шамира, которая осно­
вывается на проблеме RSA,
12.6. Криптография идентификационной информации

Сначала третья доверенная сторона (ТТР) вычисляет модуль
RSA^ т.е. число Л^, храня в секрете два его простых делителя. Она
публикует открытую экспоненту Е^ оставляя в тайне соответству­
ющую расшифровывающую экспоненту d. Кроме того, фиксируется
определенное отображение
/ : {0,1}* (Z/7VZ)*,
которое переводит строку битов в элемент {Z/NZ)*. Отображение
/ может быть реализовано хэш-функцией.
Предположим, что Алиса намерена получить секретный ключ д^
соответствующий ее имени «Алиса». Тогда ТТР вычисляет этот
ключ, используя уравнение
д = 1{Алтсз,У (modiV).
Чтобы подписать сообщение М, Алиса генерирует пару (Т, S) с по­
мощью равенств
Т = г^ (modTV), S = g- r^(^ll^) (modiV),
где г — случайное целое число, а Л, — хэш-функция.
Для проверки подписи (Т, S) на сообщении М другому пользо­
вателю необходима открытая информация о ТТР и идентификатор
Алисы. Если он обладает такими данными, то убеждается в кор­
ректности следующих равенств по модулю N:
/(Алиса) . r^(^ll^) - д^ . г^^мцт) ^




Краткое содержание главы

- Цифровые сертификаты дают возможность связать открытый
ключ с другой информацией, например, с идентификатором
пользователя.
- Эта связка, в свою очередь, позволяет решить проблему рас­
пределения аутентичных открытых ключей.
- Для решения задачи распределения аутентичных ключей были
предложены различные системы инфраструктуры открытых
ключей. Все они имеют свои достоинства и недостатки.
- PGP и SPKI работают по принципу снизу-вверх, в то вре­
мя как Х509 — сверху-вниз. В системе SPKI предусмотрена
возможность делегирования полномочий.
336 Глава 12. Получение аутентичного открытого ключа

- Третья доверенная сторона привлекается как для временной
маркировки подписи, так и для условного депонирования ключей.
- Неявные сертификаты предназначены для сокраш;ения объема
удостоверений по сравнению со стандартным сертифицирова­
нием, однако они обладают большим числом недостатков.
- Криптография идентификационной информации помогает уста­
новить подлинность открытого ключа пользователя, исполь­
зуя его идентификатор как некий открытый ключ, но при этом
не исключается участие третьей доверенной стороны.

Дополнительная литература
Хороший обзор инфраструктуры открытых ключей можно найти у
Адамса и Ллойда. За дальнейшей информацией о PGP и SSL стоит
обратиться к книгам Гарфинкеля и Рескорла.
С. Adams and S. Lloyd. Understanding Public-Key Infrastructure: Con­
cepts, Standards and Deployment Considerations. New Riders Publish­
ing, 1999.
S. Garfinkel. PGP: Pretty Good Privacy. O'Reilly & Associates, 1994.
E. Rescorla. SSL and TLS: Design and Building Secure Systems. Addi-
son-Wesley, 2000.

Контрольные вопросы
12.1.1. Что предлагает центр сертификатов?

12.1.2. Почему в сертификат обычно включают срок его действия?

12.1.3. Что такое перекрестное сертифицирование и зачем оно нужно?

12.1.4. Объясните, чем отличаются PGP, Х509 и SPKI.

12.1.5. Для чего обычно применяется SSL?
ГЛАВА 13

ПРОТОКОЛЫ

Ц е л и главы
• Представить схемы обязательств.
• Рассказать о доказательствах с нулевым разглашением.
• Разобрать протокол голосования.


13.1. Введение
в этой главе мы исследуем криптографические протоколы, позво­
ляющие обеспечить высокий уровень практического обслуживания.
Фактически, мы сфокусируем внимание на протоколах А^ЛЯ
- схем обязательств,
- доказательств с нулевым разглашением.
Поскольку существует большое количество литературы, посвящен­
ной такого сорта протоколам, мы не будем углубляться в теорию,
а займемся ее приложением к реальным задачам. Для иллюстрации
работы обсуждаемых протоколов написан последний параграф этой
главы, в котором рассказано о системе электронного голосования.


13.2. Схемы обязательств
Предположим, Алиса хочет поиграть с Бобом по телефону в игру
«камень, ножницы, бумага». Идея игры состоит в том, что Алиса с
Бобом одновременно выбирают по одному предмету из множества
{камень, ножницы, бумага}. Исход выбора, т.е. кто при этом побе­
ждает, определяется по следующему правилу:
- Бумага может обернуть камень. Поэтому, если Алиса выбира­
ет бумагу, а Боб — камень, то побеждает Алиса.
- Камень тупит ножницы. Значит, Алиса, выбрав камень, опять
одержит победу, если Боб при этом возьмет ножницы.
- Ножницы режут бумагу. Стало быть, как только Алиса назо­
вет ножницы, а Боб — бумагу, победа опять достанется ей.
Глава 13. Протоколы

Если же оба игрока выберут одинаковые предметы, раунд закончит­
ся с ничейным результатом. Таким образом, если игра проводится
по телефону, то невозможно добиться одновременного оглашения
предмета. Кто-то должен первым озвучить свой выбор, предоста­
вляя тем самым полную победу второму игроку.
Один из способов преодоления возникаюш;ей проблемы состоит
в том, что начинающий игру, скажем Алиса, передает свой пред­
мет в виде «затемненного обязательства», которое соперник не смо­
жет прочесть до определенного момента. После того, как Боб назо­
вет свой предмет, Алиса открывает обязательство. При этом важно,
чтобы второй из играющих смог убедиться в неизменности обяза­
тельства в период между передачей и открытием. Такая система
называется схемой обязательств, Наиболее простой способ ее реа­
лизации состоит в использовании хэш-функции:
А • В : НА = Я(ГАII бумага),
В А : НОЖНИЦЫ,
А • В : ГА', бумага
Бобу нужно проверить, что хэш-значение НА^ переданное Алисой,
совпадает с iJ(гдЦ бумага). При положительном результате провер­
ки. Боб будет уверен, что Алиса не жульничала. В этом раунде,
конечно, Алиса проиграла, поскольку ножницы режут бумагу.
Посмотрим на перспективы Алисы в этом обмене сообщениями.
Сначала Алиса передает свой выбор «бумага», посылая Бобу хэш-
значение НА- При этом Боб не в состоянии определить скрытое
содержание обязательства, поскольку он не знает случайного зна­
чения ГА И не может обратить хэш-функцию. Свойство схемы обяза­
тельств, обеспечивающее невозможность прочтения содержащейся
в сообщении информации, называется сокрытием.
Далее Боб посылает Алисе слово «ножницы». Та, получив его по­
слание, уже знает о своем поражении, но не может сжульничать,
поскольку у нее нет возможности заменить г А на какое-нибудь дру­
гое г^, удовлетворяющее условию:
iir(r^II бумага) = 7/(гд|| камень).
Действительно, если ей удастся найти такое г^, то у соответству­
ющей хэш-функции будут повторяющиеся значения. А мы верим в
то, что функция, привлеченная к схеме, защищена от повторений.
Фактически, здесь достаточно требовать, чтобы хэш-функция бы­
ла защищена от вторых прообразов. Свойство схемы обязательств.
13.2. Схемы обязательств

благодаря которому Алиса не способна изменить содержание пере­
данного послания, называется связывающим.
Изучим скрывающее и связывающее свойства более вниматель­
но. Напомним, что шифрующая функция обладает теоретико-ин­
формационной стойкостью, если нападающий, обладая неограни­
ченными вычислительными возможностями, не сможет ее взломать.
С другой стороны, криптосистема называется вычислительно за­
щищенной, если ее нельзя вскрыть за полиномиальное время. Ана­
логично и схемы обязательств можно разделить по степени защи­
щенности, хотя здесь нужно учитывать два свойства: скрывающее
и связывающее.

Определение 13.1. Говорят, что схема обязательств
- теоретико-информационно связывающая., если передаюпщй обя­
зательство не может изменить его значение, даже обладая не­
ограниченными вычислительными возможностями;
- вычислительно связывающая^ если отправитель может изме­
нить значение обязательства, но только в результате огромно­
го количества вычислений;
- теоретико-информационно скрывающая^ если получатель не
способен определить содержание обязательства до стадии раскры­
тия вне зависимости от его вычислительных возможностей;
- вычислительно скрывающая., если получатель может узнать
содержимое обязательства до его раскрытия, но в результате
привлечения неоправданно большого, хоть и конечного, коли­
чества вычислительных ресурсов.

Непосредственно из определения вытекает следующая лемма.

Лемма 13.2. Схема обязательств if (г||с) со случайным значением
г, обязательством с и криптографической хэш-функцией Н в луч­
шем случае является
- вычислительно связывающей,
- вычислительно скрывающей.
Доказательство. Все криптографические хэш-функции, с кото­
рыми мы встречались, только лишь вычислительно защищены от
восстановления прообразов и вторых прообразов.
Связывающее свойство гарантировано только защищенностью
подлежащей хэш-функции от вторых прообразов. Следовательно,
это свойство защищено лишь в вычислительном отношении.
Глава 13. Протоколы

Аналогично, поскольку скрывающее свойство обеспечивается за­
щищенностью хэш-функции от восстановления прообразов, то и оно
защищено только по вычислениям. •
Возникает вопрос: можно ли разработать схему обязательств,
оба свойства в которой: и скрывающее, и связывающее, — будут
обладать теоретико-информационной стойкостью? Это представля­
ется трудной, если не невозможной задачей. Однако можно предло­
жить две изящных схемы, скрывающее или связывающее свойство
в которых будет обладать теоретико-информационной стойкостью.
Пусть А — конечная абелева группа простого порядка Q и обра­
зующей G, В — элемент этой группы, чей дискретный логарифм по
основанию G не известен ни одному из пользователей системы. По­
следнее свойство достаточно просто обеспечить. Рассмотрим, на­
пример, мультипликативную группу конечного поля Fp, выберем Q
среди делителей числа Р — 1 и построим О методом, аналогичным
которому можно отыскать и В:
- возьмем произвольное i? G Z,
- вычислим F = H{R) Е Fp для некоторой криптографической
хэш-функции if,
р-1
- положим G = F Q (modP). Если G = 1, то вернемся к перво­
му шагу. Если G 7^ 1, то выведем пару (Д, G).
Таким способом мы получим случайный элемент группы Fp порядка
Q, причем эта случайность гарантируется случайным выбором R.
По данной паре (G^B) мы построим две схемы: D{x) и Da{x)^
передающие целое число х по модулю Q,
D{x) = G ^ Da{x) = B^G^
где а — случайное целое число по модулю Q. Величина а называется
затемняющей^ поскольку она скрывает переданное число х даже от
нападающего с неограниченными вычислительными возможностя­
ми. Чтобы раскрыть обязательство, пользователь открывает значе­
ние X в первой схеме и пару (а, х) — во второй.

Лемма 13.3. Схема обязательств D{x) самое большее теоретико-
информационно связывающая и вычислительно скрывающая.
Доказательство. Пусть Алиса опубликовала С = D{x) = G^, и
намерена изменить элемент из Z/QZ, который передала этим обя­
зательством. Увы! вне зависимости от вычислительных возможно­
стей Алисы существует только один элемент в Z/QZ, являющийся
дискретным логарифмом от С по основанию G, а именно х. Таким
13.3. Доказательства с нулевым разглашением 341

образом, эта система несомненно теоретико-информационно связы­
вающая.
Теперь допустим, что получатель обязательства желает опреде­
лить скрытый элемент. Все, что нужно }\ля этого сделать, — это
найти дискретный логарифм по основанию G. Поэтому схема всего
лишь вычислительно скрывающая. •

Лемма 13.4. Схема обязательств Da{x) — вычислительно связы­

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

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

ОГЛАВЛЕНИЕ

Следующая >>