38.9. Модифицированный протокол Фиата-Шамира

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

.

Эти значения предоставляются А в ЦСК. Так как ЦСК знает секретное разложение , он может легко вычислить значения . Протокол заключается в выполнении следующих шагов.

1. А передает на компьютер. Компьютер вычисляет ;

2. А выбирает случайное секретное число , вычисляет и передает на компьютер;

3. компьютер выбирает случайную строку из бит , и передает эту строку А;

4. А вычисляет , передает на компьютер;

5. компьютер проверяет равенство

.

Шаги протокола 2)-5) могут быть повторены раз. Если все сравнений из п.5) выполнены, то А получает доступ.

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

38.10. Схема идентификации Шнорра

Пусть – такие простые числа, что делит . Пусть также такой вычет по , что порядок группы порожденной элементом равен q, . Секретный ключ А есть , где – вычет по . Открытый ключ А есть , где . Протокол заключается в выполнении следующих шагов.

1. А выбирает случайное секретное число , вычисляет и передает на компьютер;

2. компьютер передает А случайное число ;

3. А вычисляет , передает на компьютер;

4. компьютер проверяет сравнение . Если это сравнение имеет место, то А получает доступ.

Число должно быть секретным. В противном случае секретный ключ может быть вычислен из сравнения . Числа не должны повторяться. Если, например, , то система сравнений

однозначно разрешима относительно при .

Для вычисления секретного ключа из открытого или вычета из надо решить проблему дискретного логарифмирования в подгруппе порядка , что при достаточно большом составляет трудную задачу. Не зная секретного ключа, противник сможет выдать себя за А с вероятностью , t – параметр протокола, его рекомендуемое значение t=72. В качестве рекомендуют выбирать числа, состоящие из 512 и 160 битов соответственно. Этот протокол, также как протокол Фиата-Шамира, является протоколом с нулевым разглашением.

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

В этом алгоритме обмены между сторонами А и В и аккредитации в каждом обмене доведены до абсолютного минимума – для каждого доказательства требуется только один обмен с одной аккредитацией.

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

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

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

I∙G^V  1 (mod n).

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

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

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

Т = r^V mod n

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

2. Сторона В выбирает случайное целое d, такое, что 1 < d  n – 1, и отправляет это значение d стороне А.

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

D = r ∙ G^d mod n

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

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

Т´ = D^V I^d mod n.

Если TT´ (mod n), то проверка подлинности успешно завершена.

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

Т´= D^V ^d = (r G^d)^V I^d = r^V G^dV I^d = r ^V (I G^V )^d = r^V T(mod n),

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

IG^V1 (mod n).