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

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

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

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

Рассмотрим сначала упрощенный вариант схемы идентификации с нулевой передачей знаний для более четкого выявления ее основной концепции.

Но прежде всего определимся с терминологией.

Пусть а, b, d, g О Z (множество целых чисел), n О N (множество натуральных чисел, т.е. положительных целых чисел).

Определение 1. Число а сравнимо с b по модулю n, если а и b при делении на n дают одинаковые остатки, т.е.

a mod n = b mod n.

Принятое обозначение:

a є b ( mod n ) .

Определение 2. Число d называют обратным к a по модулю n, если произведение a*d при делении на n дает в остатке 1, т.е.

a*d mod n = 1 .

Принятое обозначение:

b = a-1 ( mod n ) .

Примите к сведению, что целое число a-1 ( mod n ) существует тогда и только тогда, когда a является взаимно простым с n, т.е. имеет с модулем n наибольший общий делитель, равный единице.

Тех, кому интересно, почему это действительно так, отсылаю к расширенному алгоритму Евклида. В Интернете вы найдете не один сайт, посвященный этой теме.

Определение 3. Число g называют квадратным корнем из a по модулю n, если произведение g*g при делении на n дает в остатке a, т.е.

g*g mod n = a .

Принятое обозначение:

g = sqrt ( a ) ( mod n ) .

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

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

Для того, чтобы сгенерировать открытый и секретный ключи для стороны A, доверенный арбитр (Центр) выбирает такое число V, что сравнение

х2 º V ( mod n )

имеет решение. Число V при этом называют квадратичным вычетом по модулю n.

Кроме того должно существовать целое число

V-1 ( mod n ) .

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

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

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

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

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

х = r2 mod n

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

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

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

у = r * S mod n .

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

х = r2 mod n ,

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

х = у2 * 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, ..., VK, где каждое Vi , является квадратичным вычетом по модулю n. Иначе говоря, выбирают значение V, таким, что сравнение

х2 º Vi ( mod n )

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

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

Si = sqrt (Vi-1) ( mod n ) .

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

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

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

х = r2 mod n

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

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

b1, b2, ..., bK.

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

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

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

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

х = у2 * (V1b1 * V2b2 * ... * VKbK) mod n .

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

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

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

1: х2 º 1 (mod 35) имеет решения: х = 1, 6, 29, 34;
4: х2 º 4 (mod 35) имеет решения: х = 2, 12, 23, 33;
9: х2 º 9 (mod 35) имеет решения: х = 3, 17, 18, 32;
11: x2 º 11 (mod 35) имеет решения: х = 9, 16, 19, 26;
14: x2 º 14 (mod 35) имеет решения: х = 7, 28;
15: x2 º 15 (mod 35) имеет решения: х = 15, 20;
16: x2 º 16 (mod 35) имеет решения: х = 4, 11, 24, 31;
21: x2 º 21 (mod 35) имеет решения: х = 14, 21;
25: x2 º 25 (mod 35) имеет решения: х = 5, 30;
29: x2 º 29 (mod 35) имеет решения: х = 8, 13, 22, 27;
30: x2 º 30 (mod 35) имеет решения: х = 10, 25.

Заметим, что 14, 15, 21, 25 и 30 не имеют обратных значений по модулю 35, потому что они не являются взаимно простыми с 35.

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

VV-1S = sqrt (V-1)
111
49 *3
942
11164
16119 **
29298
Пояснения:
* (4 * 9) mod 35 = 1; ** (9 * 9) mod 35 = 11

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

[4, 11, 16, 29] .

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

[3, 4, 9, 8] .

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

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

х = 162 mod 35 = 11

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

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

[1, 1, 0, 1] .

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

у = r * (S1b1 * S2b2 * ...* SKbK) mod n = 16 * (31 * 41 * 90 * 81) mod 35 = 31

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

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

х = y2 * (V1b1 * V2b2 * ... * VKbK) mod n = 312 * (41 * 111 * 160 * 291) mod 35 = 11 .

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

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

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

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

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

Vj = f(I, j)

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

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

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

Пусть сторона А - интеллектуальная карточка, которая должна доказать свою подлинность проверяющей стороне В. Идентификационная информация стороны А представляет собой битовую строку 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. Сторона В вычисляет значение

T' = DV Id mod n .

Если Т º Т' (mod n), то проверка подлинности успешно завершена.

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

T' = DV * Id = (r * Gd)V * Id = rV * GdV * Id = rV * (I * GV)d = rV º T (mod n) .

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

I*GV º 1 (mod n) .
Оглавление


© Колесников Дмитрий Геннадьевич Rambler's Top100 Учебник по СайтоСтроению