Пример интерактивной системы доказательств

Интерактивные системы доказательств предполагают взаимодействие двух участиков в режиме реального времени. Наиболее адекватной моделью сторон — участников интерактивного доказательства является все та же вероятностная машина Тьюринга. Для прикладных схем обычно рассматривается система (V, Р), в которой время работы обеих машин V и Р ограничено некоторым полиномом от длины входных аргументов, а в качестве инструмента используются простые теоретико-числовые конструкции (см. пример на рис. 3.8).

Рис. 3.8. Пример интерактивной системы доказательства знания квадратичного вычета.

Вопросы практики Прикладные интерактивные системы доказательств с нулевым разглашением и их разновидности могут использоваться при интерактивной идентификации пользователя системы.

Протоколы интерактивной идентификации в таком случае позволяют предупредить противника от сбора некоторой специальной информации, которой пользуется законный абонент системы в процессе доказательства своих полномочий (например, в процессе предъявления пароля при входе в систему). Рассматриваемые ниже схемы интерактивной идентификации позволяют создавать высоконадежные системы контроля доступа, удобные для практической реализации. В таких системах одна сторона гарантированно доказывает другой стороне наличие у себя конфиденциальных сведений для разрешения каких-либо действий таким образом, что первая при этом не раскрывает никакой информации об этих сведениях.

Протоколы, рассматриваемые далее, являются схемами, основанными на идентификационной информации. Каждую из этих схем целесообразно использовать для решения перечисленных выше задач, если они будут обладать приемлемыми пространственновременными характеристиками.

Легко увидеть, что любую из схем электронной подписи, например, рассматриваемых в параграфе 3.3, легко и естественно можно преобразовать в протоколы интерактивной идентификации, заменяя хэш-код подписываемого сообщения или само сообщение заменяется на зарос проверяющего.

Например, рассмотрим, как преобразовывается схема подписи Эль-Гамаля в протокол интерактивной идентификации^[1] (рис. 3.9). Теоретико-информационные соглашения здесь такие же, как и в схеме электронной подписи Эль-Гамаля. Указанные на рисунке четыре шага протокола выполняются в четырех циклах.

Рис. 3.9. Протокол интерактивной идентификации Бета.

Кроме доказывающего Р и проверяющего V, протокол предусматривает наличие третьего необходимого элемента — центра аутентификации (ЦА), который осуществляет управляющие функции по распространению между Р и V достоверной информации. Протокол начинается с того, что ЦА выбирает криптоконстанты, например для протокола Шнорра это могут быть простые числа р, q и г такие, что qr р — 1, где размерности этих чисел в битах составляют q> 140, г > 140 и р > 512, затем находит такое g е Z_p, что g^q = 1 (mod p), g* 1.

Участник Р приходит для регистрации в ЦА и вместе с ЦА выбирает секретные и открытые ключи любой схемы электронной подписи. Далее для Р центр аутентификации составляет идентификационную строку I, состоящую из имени, уровня полномочий и т. п. Далее для них ЦА генерирует подпись s_y Участнику Р выдаются подписи, открытые и секретные ключи и строка I. Процесс аутентификации, в котором участник Р сначала будет доказывать, что он обладает подписями ЦА, а затем доказывать обладание секретными ключами в вышеописанном протоколе интерактивной идентификации участнику П без раскрытия секретных значений d и k, начинается с отсылки подписей и значения 7 участнику V, который с помощью открытого ключа ЦА верифицирует идентификационную строку I и открытые ключи участника Р. Подтверждение подлинности / может быть также подтверждено посредством открытого справочника, сертифицированного ЦЛ.

Для сведения Точно так же строятся протоколы интерактивной идентификации Бета^[2], Брикелла — МакКарли^[3], Фиата — Шамира^[4], Шнорра^[5], Казарина — Ухлинова^[6] и др.

Подобные протоколы ярко демонстрируют пример, как работает парадигма интерактивных систем доказательств с нулевым разглашением на практике и как сами протоколы могут применяться: при доступе к удаленным ресурсам автоматизированных систем, для разграничения доступа к объекту доступа при помощи интеллектуальных карточек (смарт-карт); для взаимной аутентификации абонентов сети, в системах распознавания «свой-чужой» и др.

• [1] Например, с некоторыми небольшими изменениям в протоколы интерактивной идентификации Бета или Шнорра.
• [2] ' Beth Т. Efficient zero-knowledge identification scheme for smart cards //Advances in Cryptology — CRYPTO'88: Lecture Notes in Computer Science. 1988.Vol. 330. P. 77−84.
• [3] Brickell E. F., McCurley K. S. Interactive identification and digital signatures //AT&T Technical Journal. 1991. Vol. 70. № 6. P. 73−86.
• [4] Fiat A., Shamir A. IIow to prove yourself: practical solutions to identification andsignature problems // Advances in Cryptology — CRYPTO'86: Lecture Notes inComputer Science. 1998. Vol. 263. P. 186—194.
• [5] 1 Schnorr С. P. Efficient identification and signatures for smart cards // Advances inCryptology — CRYPTO'89: Lecture Notes in Computer Science. 1990. Vol. 434.P. 239−252.
• [6] Казарин О. В., Ухлинов Л. М. Интерактивная система доказательств для интел-лектуальных средств контроля доступа к информационно-вычислительным ресурсам // Автоматика и телемеханика. 1993. № 11. С. 167—175.