double arrow

Протоколы идентификации с нулевой передачей

Знаний

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

Для безопасного использования интеллектуальных карт разработаны протоколы идентификации с нулевой передачей знаний [121]. Секретный ключ владельца карты становится неотъемлемым признаком его личности. Доказательство знания этого секретного ключа с нулевой передачей этого знания служит доказательством подлинности личности владельца карты.

5.4.1. Упрощенная схема идентификации с нулевой

передачей знаний

Схему идентификации с нулевой передачей знаний предложили в 1986 г. У.Фейге, А.Фиат и А.Шамир. Она является наиболее известным доказательством идентичности с нулевой передачей конфиденциальной информации.

Рассмотрим сначала упрощенный вариант схемы идентификации с нулевой передачей знаний для более четкого выявления ее основной концепции. Прежде всего выбирают случайное значение модуля n, который является произведением двух больших простых чисел. Модуль n должен иметь длину 512…1024 бит. Это значение n может быть представлено группе пользователей, которым придется доказывать свою подлинность. В процессе идентификации участвуют две стороны:




· сторона А, доказывающая свою подлинность,

· сторона В, проверяющая представляемое стороной А доказательство.

Для того чтобы сгенерировать открытый и секретный ключи для стороны А, доверенный арбитр (Центр) выбирает некоторое число V, которое является квадратичным вычетом по модулю n. Иначе говоря, выбирается такое число V, что сравнение

x2 º V (mod n)

имеет решение и существует целое число

V –1 mod n.

Выбранное значение V является открытым ключом для А. Затем вычисляют наименьшее значение S, для которого

S º sqrt (V –1) (mod n).

Это значение S является секретным ключом для А.

Теперь можно приступить к выполнению протокола идентификации.

1. Сторона А выбирает некоторое случайное число r, r < n. Затем она вычисляет



x = r 2 mod n

и отправляет x стороне В.

2. Сторона В посылает А случайный бит b.

3. Если b=0, тогда А отправляет r стороне В. Если b=1, то А отправляет стороне В

y = r * S mod n.

4. Если b = 0, сторона В проверяет, что

x = r2 mod n,

чтобы убедиться, что А знает sqrt (x). Если b=1, сторона В проверяет, что

x = y2 *V mod n,

чтобы быть уверенной, что А знает sqrt (V –1).

Эти шаги образуют один цикл протокола, называемый аккредитацией. Стороны А и В повторяют этот цикл t раз при разных случайных значениях r и b до тех пор, пока В не убедится, что А знает значение S.

Если сторона А не знает значения S, она может выбрать такое значение r, которое позволит ей обмануть сторону В, если В отправит ей b=0, либо А может выбрать такое r, которое позволит обмануть В, если В отправит ей b=1. Но этого невозможно сделать в обоих случаях. Вероятность того, что А обманет В в одном цикле, составляет 1/2. Вероятность обмануть В в t циклах равна (1/2)t.

Для того чтобы этот протокол работал, сторона А никогда не должна повторно использовать значение r. Если А поступила бы таким образом, а сторона В отправила бы стороне А на шаге 2 другой случайный бит b, то В имела бы оба ответа А. После этого В может вычислить значение S, и для А все закончено.

Параллельная схема идентификации с нулевой передачей

знаний

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

Как и в предыдущем случае, сначала генерируется число n как произведение двух больших чисел. Для того, чтобы сгенерировать открытый и секретный ключи для стороны А, сначала выбирают К различных чисел V1, V2, ..., VК, где каждое Vi является квадратичным вычетом по модулю n. Иначе говоря, выбирают значение Vi таким, что сравнение

x2 º Vi mod n

имеет решение и существует Vi–1 mod n. Полученная строка V1, V2, ..., VК является открытым ключом.

Затем вычисляют такие наименьшие значения Si, что

Si = sqrt (Vi–1) mod n.

Эта строка S1, S2, ..., SK является секретным ключом стороны А.

Протокол процесса идентификации имеет следую-щий вид:

1. Сторона А выбирает некоторое случайное число r, r<n. Затем она вычисляет x=r2 mod n и посылает x стороне В.

2. Сторона В отправляет стороне А некоторую случайную двоичную строку из K бит: b1, b2, ..., bK.

3. Сторона А вычисляет

y = r * (S1b1 * S2b2 * ... * SKbK) mod n.

Перемножаются только те значения Si, для которых bi=1. Например, если b1=1, то сомножитель S1 входит в произведение, если же b1=0, то S1 не входит в произведение, и т.д. Вычисленное значение y отправляется стороне В.

4. Сторона В проверяет, что

x = y2 * (V1b1 * V2b2 * ... * VKbK) mod n.

Фактически сторона В перемножает только те значения Vi, для которых bi=1. Стороны А и В повторяют этот протокол t раз, пока В не убедится, что А знает S1, S2, ..., SK.

Вероятность того, что А может обмануть В, равна (1/2)Кt. Авторы рекомендуют в качестве контрольного значения брать вероятность обмана В равной (1/2)20 при К=5 и t=4.

Схема идентификации Гиллоу – Куискуотера

Алгоритм идентификации с нулевой передачей знания, разработанный л.гиллоу и Ж.Куискуотером, имеет несколько лучшие характеристики, чем предыдущая схема идентификации. В этом алгоритме обмены между сторонами а и в и аккредитации в каждом обмене доведены до абсолютного минимума – для каждого доказательства требуется только один обмен с одной аккредитацией. Однако объем требуемых вычислений для этого алгоритма больше, чем для схемы Фейге–Фиата–Шамира.

Пусть сторона А – интеллектуальная карточка, которая должна доказать свою подлинность проверяющей стороне В. Идентификационная информация стороны А представляет собой битовую строку I, которая включает имя владельца карточки, срок действия, номер банковского счета и др. Фактически идентификационные данные могут занимать достаточно длинную строку, и тогда их хэшируют к значению I.

Строка I является аналогом открытого ключа. Другой открытой информацией, которую используют все карты, участвующие в данном приложении, являются модуль n и показатель степени V. Модуль n является произведением двух секретных простых чисел.

Секретным ключом стороны А является величина G, выбираемая таким образом, чтобы выполнялось соотношение

I * GV º 1 (mod n).

Сторона А отправляет стороне В свои идентификационные данные I. Далее ей нужно доказать стороне В, что эти идентификационные данные принадлежат именно ей. Чтобы добиться этого, сторона А должна убедить сторону В, что ей известно значение G.

Вот протокол доказательства подлинности А без передачи стороне В значения G:

1. Сторона А выбирает случайное целое r, такое, что

1 < r £ n – 1. Она вычисляет

Т = rV mod n

и отправляет это значение стороне В.

2. Сторона В выбирает случайное целое d, такое, что

1 < d £ n – 1, и отправляет это значение d стороне А.

3. Сторона А вычисляет

D = r * Gd mod n

и отправляет это значение стороне В.

4. Сторона В вычисляет значение

Т´ = DV Id mod n.

Если TºT´ (mod n),

то проверка подлинности успешно завершена.

Математические выкладки, использованные в этом протоколе, не очень сложны:

Т´= DV Id = (r Gd)V Id = rV GdV Id = r V (I GV )d = rV ºT(mod n),

поскольку G вычислялось таким образом, чтобы выполнялось соотношение

IGVº1 (mod n).







Сейчас читают про: