Иванов М.А. КМЗИ сети

1)прикладные протоколы, решающие конкретную задачу, которая может возникнуть на практике;

2)примитивные протоколы, используемые в качестве своеобразных строительных блоков при создании прикладных протоколов.

Протокол чаще всего интерактивен, т.е. предусматривает многораундовый обмен сообщениями между участниками, и включает в себя:

распределенный алгоритм, т.е. описание характера и последовательности действий каждого из участников;

спецификацию форматов пересылаемых сообщений; спецификацию синхронизации действий участников; описание действий при возникновении сбоев [4].

6.2. Доказательства с нулевым разглашением

Существенное влияние на разработку многих криптографических протоколов оказали исследования двух математических моделей – интерактивной системы доказательств (Interactive Proof System) и доказательств с нулевым разглашением знаний

(Zero-Knowledge Proofs).

Интерактивная система доказательств суть протокол (P, V, S) взаимодействия двух субъектов: доказывающего (претендента) P и проверяющего (верификатора) V. Абонент P хочет доказать V, что утверждение S истинно. При этом считается, что абонент V самостоятельно проверить утверждение S не в состоянии, что абонент V не может быть противником, а абонент P может быть противником, пытающимся доказать истинность ложного утверждения S. Протокол, состоящий из некоторого числа раундов обмена сообщениями между P и V, должен удовлетворять двум условиям:

1)полнота – если S действительно истинно, то доказывающий убедит проверяющего признать это;

2)корректность – если S ложно, то доказывающий не сможет убедить проверяющего в обратном.

181

Если предположить, что V может быть противником, который хочет получить информацию об утверждении S, необходим протокол (P, V, S), называемый доказательством с нулевым разглашением, удовлетворяющий, помимо перечисленных, еще и следующему условию:

3) нулевое разглашение – в результате работы протокола абонент V не увеличит своих знаний об утверждении S.

Иными словами, в результате реализации протокола абонент P сможет доказать абоненту V, что он владеет некоторой секретной информацией, не разглашая ее сути.

Упрощенно процедуру доказательства с нулевым разглашением можно представить следующим образом. Проверяющий задает серию случайных вопросов, каждый из которых допускает ответ «да» или «нет». После первого вопроса проверяющий убеждается в том, что доказывающий заблуждается с вероятностью 1/2. После второго вопроса проверяющий убеждается в том, что доказывающий заблуждается с вероятностью 1/4 и т.д. (после каждого вопроса знаменатель удваивается). После 100 вопросов вероятность того, что доказывающий заблуждается или не располагает доказательством (не владеет секретной информацией), становится настолько близкой к нулю, что даже у самого «недоверчивого» проверяющего не должно остаться сомнений в справедливости доказываемого утверждения. После 300 вопросов знаменатель достигает величины, которая превосходит число атомов во Вселенной.

Роль доказательств с нулевым разглашением особенно велика при реализации протоколов аутентификации. Пусть, например, Р – алгоритм, реализованный в интеллектуальной карточке клиента (абонент А) банка; V – программа, выполняемая компьютером банка (абонент В). Перед выполнением любой операции банк должен убедиться в подлинности карточки и идентифицировать ее владельца. Если для этой цели использовать протокол (P, V, S), свойство полноты позволит карточке доказать свою аутентичность; свойство корректности защитит интересы банка от злоумышленника, который попытается воспользоваться

182

фальшивой карточкой; свойство нулевого разглашения защитит клиента от злоумышленника, который попытается пройти аутентификацию под именем абонента А, воспользовавшись информацией, перехваченной во время предыдущих раундов аутентификационного обмена. Аналогичных результатов можно добиться, используя протоколы доказательств с нулевым разглашением для создания не поддающихся подделке удостоверений личности, как для военных так и гражданских целей [4].

6.2.1. Пещера нулевого знания

На рис. 6.1 показана физическая реализация протокола доказательства с нулевым разглашением с помощью так называемой «пещеры нулевого знания» [32]. В пещере имеется дверь Д, от которой у участника протокола P (доказывающего) есть секретный ключ. P хочет доказать другому участнику протокола V (проверяющему) свою способность проходить через дверь (наличие секретного ключа), не демонстрируя сам факт прохождения через дверь. Показаны две итерации протокола.

Работу генератора ПСЧ в этой реализации имитирует процедура подбрасывания монеты, которую на определенных шагах протокола выполняют обе стороны.

6.2.2. Протокол Фиата–Шамира

Примером протокола доказательства с нулевым разглашением может являться схема Фиата–Шамира, показанная на рис. 6.2. Доверенный третий участник протокола выбирает два больших простых числа p и q, затем вычисляет n = pq. Величина n откры-

то публикуется. Абонент A выбирает случайное число s Zn ,

вычисляет Θ s2 modn . А хранит s в качестве своего секретного ключа и объявляет ν своим открытым ключом.

183

Рис. 6.1. Пещера нулевого знания (начало)

184

P V V

Итерация 3, шаг 4:

P и V возвращаются в исходную ситуацию - в точку А Результат:

С вероятностью 7/8 можно утверждать, что P владеет секретом прохождения через дверь Д

Рис. 6.1. Пещера нулевого знания (окончание)

185

Протокол включает шесть шагов:

1) абонент A выбирает случайное число xA; А вычисляет yA xA2 mod n ;

2)А посылает yA абоненту В;

3)абонент В, проверяющий, посылает А в качестве запроса случайный бит b 0, 1`;

5)А посылает ответ В, чтобы доказать, что он знает свой секретный ключ s;

6)абонент В вычисляет yA' 2 и yAΘb . Если эти два числа сравнимы по модулю n, то либо абонент А знает число s, либо вычислил значение y каким-либо другим способом. Доказательство этого факта элементарно:

Эти шесть шагов образуют один раунд. Проверка осуществляется несколько раз с выбираемыми случайно значениями b.

186

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

Если А знает s, он пройдет проверку во всех раундах. Если А не является тем, за кого он себя выдает, т.е. не знает s, он может попытаться пройти раундовую проверку, правильно предсказав

Таким образом, абонент, не знающий числа s, успешно пройдет раундовую проверку с вероятностью 1/2. Если процесс повторяется 20 раз, вероятность успеха снижается до

1/ 2 20 | 9,5υ10 -7.

6.2.3. Протокол Фейга–Фиата–Шамира

Особенностью данного протокола (рис. 6.3) является использование вектора секретных ключей, вектора открытых ключей и вектора запросов. Секретные ключи выбираются случайно, но при этом они должны быть взаимно простые с n. Открытые клю-

187

Рис. 6.3. Протокол Фейга–Фиата–Шамира

6.3. Протоколы подбрасывания монеты

Классическим примером задачи, решаемой двумя удаленными абонентами, является бросание жребия с помощью подбрасывания монеты. Это необходимо сделать так, чтобы абонент А, подбрасывающий монету, не мог изменить результат после получения догадки от абонента В, угадывающего этот результат. Протокол решения данной задачи называют протоколом подбрасывания монеты. Этот примитив (по сути, протокол генера-

188

ции случайного бита) используют в своем составе многие прикладные протоколы.

Примером такого протокола является схема Блюма–Микали, предполагающая наличие у двух его участников односторонней функции F : X ο Y, удовлетворяющая следующим требованиям:

X – конечное множество целых чисел, содержащее одинаковое количество четных и нечетных чисел;

любые числа x1, x2 X , такие, что F x1 F x2 , имеют одинаковую четность;

по заданному значению F(x) невозможно определить четность аргумента x.

Протокол подбрасывания монеты (схема Блюма–Микали)

1.Абонент А выбирает случайное число xA X (подбрасывает монету), вычисляет yA F xA и посылает yA абоненту В.

2.Абонент В, получив yA , пытается угадать четность xA и посылает свою догадку А.

3.Абонент А, получив догадку от В, сообщает последнему, угадал ли он, посылая ему выбранное число xA .

4.Абонент В, получив xA , проверяет, не обманывает ли А, вычисляя значение F xA и сравнивая его с полученным на втором шаге значением yA .

Суть протокола состоит в том, что абонент А связывает себя с числом xA , так как он сообщает абоненту В значение

yA F xA , однако абонент В не может самостоятельно вычислить xA , так как F x является односторонней функцией.

Следующий протокол подбрасывания монеты (рис. 6.4) основан на предположении о вычислительной неразрешимости задачи дискретного логарифмирования. Пусть p и q – простые числа, причем q делит p – 1. Найдем такое g Z p , что

gq 1mod p, g ζ 1.

189

Рис. 6.4. Протокол подбрасывания монеты

Протокол подбрасывания монеты (схема Блюма)

1. Абонент А выбирает случайное число xA Zq , вычисляет yA gxA mod p .

2.Абонент А посылает yA абоненту В.

3.Абонент В выбирает случайный бит b и случайное число

xB Zq , вычисляет yB ybAg xB mod p .

4.Абонент В посылает yB абоненту А.

5.Абонент А выбирает случайный бит a и посылает его абоненту В.

6.Абонент В посылает абоненту А бит b и число xB .

7. Абонент А проверяет равенство yB ybAg xB mod p. При по-

ложительном исходе результатом выполнения протокола будет бит c a b.

190