Схема непрерывной проверки подлинности отправителя

Другой вариант непрерывной проверки подлинности использует вместо идентификатора отправителя его секретный пароль. Заранее подготовленные пароли известны обеим сторонам. Пусть Р_А и Р_В – пароли пользователей А и В соответственно. Тогда пользователь А создает криптограмму

С = Е_К (Р_А, М).

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

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

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

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

38.7. Упрощенный вариант схемы идентификации
с нулевой передачей знаний.
Протокол Фиата-Шамира

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

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

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

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

x² º V (mod n)

имеет решение и существует обратное число к V относительно умножения по модулю n

V ^–1 mod n.

Любое решение сравнения x² º V (mod n) обозначают через sqrt V.

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

S º sqrt V^-1 mod n.

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

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

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

x = r ² mod n

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

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

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

y = r∙ S mod n.

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

x = r² mod n,

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

x = y² ∙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, и для А все закончено.

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

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

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

x² º V_i mod n

имеет решение. Кроме того, значение V_i выбирают так, чтобы существовало V_i^–1mod n. Полученная строка V₁, V₂,..., V_К является открытым ключом.

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

S_i º sqrt (V^-1) mod n.

Эта строка S₁, S₂,..., S_K является секретным ключом стороны А.

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

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

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

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

y = r ∙ (S₁^b1 ∙ S₂^b2 ∙... ∙ S_K^bK) mod n.

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

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

x = y² ∙ (V₁^b1 ∙ V₂^b2 ∙... ∙ V_K^bK) mod n.

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

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

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

1: x² º1 (mod 35) имеет решения: x =1, 6, 29, 34;

4: x² º 4 (mod 35) имеет решения: x = 2, 12, 23, 33;

9: x² º 9 (mod 35) имеет решения: x = 3, 17, 18, 32;

11: x² º11 (mod 35) имеет решения: x = 9, 16, 19, 26;

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

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

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

21: x² º 21 (mod 35) имеет решения: x =14, 21;

25: x² º 25 (mod 35) имеет решения: x = 5, 30;

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

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

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

(p –1) (q –1)/4 = (5 –1) (7 –1)/4 = 6.

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

V	V –1	S = sqrt (V –1)

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

[4, 11, 16, 29].

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

[3 4 9 8].

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

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

x =16² mod 35 =11

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

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

[1, 1, 0, 1].

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

y = r ∙ ( ∙ ∙...∙ ) mod n =16 ∙ (3¹ ∙ 4¹ ∙ 9⁰ ∙ 8¹) mod 35 = 31

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

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

x = y² ∙ ∙ ∙...∙ ) mod n = 31² ∙ (4¹ ∙11¹ ∙16⁰ ∙ 29¹) mod 35 =11.

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

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

В этот протокол можно включить идентификационную информацию.

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

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

V_j = f (I, j)

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