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

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

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

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

• сторона В, проверяющая представляемое стороной А доказательство. Для того чтобы сгенерировать открытый и секретный ключи для стороны

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

х² =V(mod n)

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

V^-1 mod n.

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

S = sqrt(V^-1)(modn).

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

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

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

х = r² mod n

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

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

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

у = r * S mod n.

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

x = r²mod n,

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

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

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

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

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

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

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

Как и в предыдущем случае, сначала генерируется число n как произведение двух больших чисел. Для того, чтобы сгенерировать открытый и

секретный ключи для стороны А, сначала выбирают К различных чисел V₁ V₂,

...,V_K, где каждое V; является квадратичным вычетом по модулю n. Иначе говоря, выбирают значение V_i таким, что сравнение

х² =V_i mod n

имеет решение и существует V_i^-1modn. Полученная строка V₁V₂,..., V_K

является открытым ключом.

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

S_i = sqrt (V_i¹) mod n.

Эта строка S₁ S₂,..., S_K является секретным ключом стороны А. Протокол процесса идентификации имеет следующий вид:

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

2. Сторона В отправляет стороне А некоторую случайную двоичную строку из К бит: b₁, b₂,.... b_к.

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

у = r * (S₁^b1 * S₂^b2 *...* S_K^bk) mod n.

Перемножаются только те значения S_i, для которых b_i = 1. Например, если b_i = 1, то сомножитель S₁ входит в произведение, если же b_i = 0, то S₁ не входит

в произведение, и т.д. Вычисленное значение у отправляется стороне В.

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

x = у² * (V₁^b1 * V₂^b2 *...*V_k^bk ) mod n.

Фактически сторона В перемножает только те значения V_i, для которых b_i = 1. Стороны А и В повторяют этот протокол t раз, пока В не убедится, что А знает S₁, S₂.....S_K.

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

Пример. Рассмотрим работу этого протокола для небольших числовых значений. Если n = 35 (n - произведение двух простых чисел 5 и 7), то возможные квадратичные вычеты будут следующими:

Таблица 2.3

14 х² = 14 (mod 35) имеет решения: х = 7, 28;

15 х² =15 (mod 35) имеет решения: х = 15, 20;

16 x²* 16 (mod 35) имеет решения: х = 4, 11, 24, 31;

29 x² = 29 (mod 35) имеет решения: х = 8, 13, 22, 27;

30 x² = 30 (mod 35) имеет решения: х - 10, 25.

Заметим, что 14, 15, 21, 25 и 30 не имеют обратных значений по модулю 35. потому что они не являются взаимно простыми с 35. Следует также отметить, что число квадратичных вычетов по модулю 35, взаимно простых с n = p*q = 5*7=35 (для которых НОД (х, 35) = 1), равно

(р -1) (q -1)/4 = (5 -1) (7-1)/4 = 6.

Составим таблицу квадратичных вычетов по модулю 35, обратных к ним значений по модулю 35 и их квадратных корней.

Таблица 2.4

Итак, сторона А получает открытый ключ, состоящий из К=4 значений V:

[4, 11, 16, 29]. Соответствующий секретный ключ, состоящий из К=4 значений S:

[3 4 9 8].

Рассмотрим один цикл протокола.

1. Сторона А выбирает некоторое случайное число r =16, вычисляет x=16² mod35=11

и посылает это значение х стороне В.

2. Сторона В отправляет стороне А некоторую случайную двоичную строку

[1, 1,0, 1].

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

у = r * (S₁^b1 * S₂^b2 *...* S_K^bk) mod n =16 * (З¹ * 4¹ * 9° * 8¹) mod 35 = 31

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

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

x = у² * (V₁^b1 * V₂^b2 *...*V_k^bk ) mod n = 31² * (4¹ *11¹ *16° * 29¹) mod 35 =11.

Стороны А и В повторяют этот протокол t раз, каждый раз с разным случайным числом r, пока сторона В не будет удовлетворена.

При малых значениях величин, как в данном примере, не достигается настоящей безопасности. Но если n представляет собой число длиной 512 бит и более, сторона В не сможет узнать ничего о секретном ключе стороны А, кроме того факта, что сторона А знает этот ключ.

В этот протокол можно включить идентификационную информацию. Пусть I-некоторая двоичная строка, представляющая иден-

тификационную информацию о владельце карты (имя, адрес, персональный идентификационный номер, физическое описание) и о карте (дата окончания действия и т.п.). Эту информацию I формируют в Центре выдачи интеллектуальных карт по заявке пользователя А.

Далее используют одностороннюю функцию f() для вычисления f(i,j), где j-некоторое двоичное число, сцепляемое со строкой i. Вычисляют значения

Vj = f(l, j)

для небольших значений j, отбирают К разных значений j, для которых Vj являются квадратичными вычетами по модулю п. Затем для отобранных квадратичных вычетов Vj вычисляют наименьшие квадратные корни из Vj^-1(mod n). Совокупность из К значений Vj образует открытый ключ, а совокупность из К значений Sj-секретный ключ пользователя А.