Широкое распространение смарт-карт (интеллектуальных карт) для разнообразных коммерческих, гражданских и военных применений (кредитные карты, карты социального страхования, карты доступа в охраняемые помещения, компьютерные пароли и ключи и т.д.) потребовало обеспечение безопасности идентификации таких карт и их владельцев. Во многих приложениях главная проблема заключается в том, чтобы при предъявлении смарт-карты оперативно обнаружить обман и отказать обманщику в допуске, ответе и обслуживании.
Для безопасного использования смарт-карт разработаны протоколы идентификации с нулевой передачей знаний. Секретный ключ владельца карты становится неотъемлемым признаком его личности. Доказательство знания этого секретного ключа с нулевой передачей этого знания служит доказательством подлинности личности владельца карты.
Схему идентификации с нулевой передачей знаний предложили в 1986 г. У.Фейге, А.Фиат и А.Шамир. Она является наиболее известным доказательством идентичности с нулевой передачей конфиденциальной информации.
Рассмотрим сначала упрощенный вариант схемы идентификации с нулевой передачей знаний для более четкого выявления ее основной концепции.
Но прежде всего определимся с терминологией.
Пусть а, b, d, g О Z (множество целых чисел), n О N (множество натуральных чисел, т.е. положительных целых чисел).
Определение 1. Число а сравнимо с b по модулю n, если а и b при делении на n дают одинаковые остатки, т.е.
Принятое обозначение:
Определение 2. Число d называют обратным к a по модулю n, если произведение a*d при делении на n дает в остатке 1, т.е.
Принятое обозначение:
Примите к сведению, что целое число a-1 ( mod n ) существует тогда и только тогда, когда a является взаимно простым с n, т.е. имеет с модулем n наибольший общий делитель, равный единице.
Тех, кому интересно, почему это действительно так, отсылаю к расширенному алгоритму Евклида. В Интернете вы найдете не один сайт, посвященный этой теме.
Определение 3. Число g называют квадратным корнем из a по модулю n, если произведение g*g при делении на n дает в остатке a, т.е.
Принятое обозначение:
Прежде всего выбирается значение модуля n, который является произведением двух больших простых чисел. Модуль n должен иметь длину 512...1024 бит. Это значение n представляют группе пользователей, которым придется доказывать свою подлинность. В процессе идентификации участвуют две стороны:
Для того, чтобы сгенерировать открытый и секретный ключи для стороны A, доверенный арбитр (Центр) выбирает такое число V, что сравнение
Кроме того должно существовать целое число
Выбранное значение V является открытым ключом для А. Затем вычисляют наименьшее значение S, для которого
Это значение S является секретным ключом для А.
Теперь можно приступить к выполнению протокола идентификации.
1. Сторона А выбирает некоторое случайное число r, r < n. Затем она вычисляет
2. Сторона В посылает А случайный бит b.
3. Если b = 0, тогда А отправляет r стороне В. Если b = 1, то А отправляет стороне В
4. Если b = 0, сторона В проверяет, что
Эти шаги образуют один цикл протокола, называемый аккредитацией. Стороны А и В повторяют этот цикл 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, таким, что сравнение
Затем вычисляют такие наименьшие значения Si, что
Эта строка S1, S2, ..., SK является секретным ключом стороны А.
Протокол процесса идентификации имеет следующий вид:
1. Сторона А выбирает некоторое случайное число r, r<n. Затем она вычисляет
2. Сторона В отправляет стороне А некоторую случайную двоичную строку из К бит:
3. Сторона А вычисляет
4. Сторона В проверяет, что
Фактически сторона В перемножает только те значения 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 и их квадратных корней.
| V | V-1 | S = sqrt (V-1) |
| 1 | 1 | 1 |
| 4 | 9 * | 3 |
| 9 | 4 | 2 |
| 11 | 16 | 4 |
| 16 | 11 | 9 ** |
| 29 | 29 | 8 |
| Пояснения:
* (4 * 9) mod 35 = 1; ** (9 * 9) mod 35 = 11 | ||
Итак, сторона А получает открытый ключ, состоящий из К = 4 значений V:
Соответствующий секретный ключ, состоящий из К = 4 значений S:
Рассмотрим один цикл протокола.
1. Сторона А выбирает некоторое случайное число r = 16, вычисляет
2. Сторона В отправляет стороне А некоторую случайную двоичную строку
3. Сторона А вычисляет значение
4. Сторона В проверяет, что
Стороны А и В повторяют этот протокол t раз, каждый раз с разным случайным числом r, пока сторона В не будет удовлетворена.
При малых значениях величин, как в данном примере, не достигается настоящей безопасности. Но если n представляет собой число длиной 512 бит и более, сторона В не сможет узнать ничего о секретном ключе стороны А, кроме того факта, что сторона А знает этот ключ.
В этот протокол можно включить идентификационную информацию.
Пусть I - некоторая двоичная строка, представляющая идентификационную информацию о владельце карты (имя, адрес, персональный идентификационный номер, физическое описание) и о карте (дата окончания действия и т.п.). Эту информацию I формируют в Центре выдачи интеллектуальных карт по заявке пользователя А.
Далее используют одностороннюю функцию f(·) для вычисления f(I, j), где j - некоторое двоичное число, сцепляемое со строкой I. Вычисляют значения
Алгоритм идентификации с нулевой передачей знания, разработанный Л.Гиллоу и Ж.Куискуотером, имеет несколько лучшие характеристики, чем предыдущая схема идентификации. В этом алгоритме обмены между сторонами А и В и аккредитации в каждом обмене доведены до абсолютного минимума - для каждого доказательства требуется только один обмен с одной аккредитацией. Однако обьем требуемых вычислении для этого алгоритма больше, чем для схемы Фейге-Фиата-Шамира.
Пусть сторона А - интеллектуальная карточка, которая должна доказать свою подлинность проверяющей стороне В. Идентификационная информация стороны А представляет собой битовую строку I, которая включает имя владельца карточки, срок действия, номер банковского счета и др. Фактически идентификационные данные могут занимать достаточно длинную строку, и тогда их хэшируют к значению I.
Строка I является аналогом открытого ключа. Другой открытой информацией, которую используют все карты, участвующие в данном приложении, являются модуль n и показатель степени V. Модуль n является произведением двух секретных простых чисел.
Секретным ключом стороны А является величина G, выбираемая таким образом. чтобы выполнялось соотношение
Сторона А отправляет стороне В свои идентификационные данные I. Далее ей нужно доказать стороне В, что эти идентификационные данные принадлежат именно ей. Чтобы добиться этого, сторона А должна убедить сторону В, что ей известно значение G.
Вот протокол доказательства подлинности А без передачи стороне В значения G:
1. Сторона А выбирает случайное целое r, такое, что 1 < r £ n - 1. Она вычисляет
2. Сторона В выбирает случайное целое d, такое, что 1 < d £ n - 1, и отправляет это значение d стороне А.
3. Сторона А вычисляет
4. Сторона В вычисляет значение
Математические выкладки, использованные в этом протоколе не очень сложны:
|
-
Бубновский лордоз |