Введение в криптографию
[an error occurred while processing this directive]

Целостность. Протоколы аутентификации и электронной подписи - часть 2


В протоколе имеются два участника - Алиса, которая должна доказать свою аутентичность, и Боб, который эту аутентичность должен проверить. У Алисы имеются два ключа - общедоступный открытый и секретный . Фактически, Алисе нужно доказать, что она знает , и сделать это таким образом, чтобы это доказательство можно было проверить, зная только .

Задача аутентификации уже обсуждалась в главе . Там же были сформулированы основные требования, которым должен удовлетворять стойкий протокол аутентификации. Напомним, что для удовлетворения этих требований достаточно, чтобы протокол аутентификации был доказательством с нулевым разглашением. В главе  приведен протокол доказательства с абсолютно нулевым разглашением для задачи ИЗОМОРФИЗМ ГРАФОВ. Но этот протокол имеет неприемлемо большое с практической точки зрения количество раундов обмена сообщениями между Алисой и Бобом.

Ниже мы приводим протокол Шнорра [], один из наиболее эффективных практических протоколов аутентификации. Для его описания нам потребуются некоторые обозначения, которые будут использоваться и в последующих разделах данной главы.

Пусть и - простые числа такие, что делит . Шнорр предлагает [] использовать длины порядка 512 битов и - длины порядка 140 битов. Пусть таково, что , . Пусть и . Задача вычисления значения по заданному значению при известных , и называется задачей дискретного логарифмирования (см. главу ). Для задачи дискретного логарифмирования на данный момент не известно эффективных алгоритмов. Поэтому в криптографии широко используется гипотеза о вычислительной трудности задачи дискретного логарифмирования. Сформулируем ее более строго. Пусть - растущий целочисленный параметр, число выбирается из множества всех простых чисел длины таких, что имеет простой делитель длины не меньше для некоторой константы 0$" width="41" height="28" >, - из множества всех таких простых делителей числа ,  - из множества всех чисел таких, что , а . Тогда функция - односторонняя (см. главу ). Рекомендации, данные Шнорром относительно длин чисел и , можно трактовать следующим образом. На тот момент (1989 г.) считалось практически невыполнимым уже для и длины порядка 512 и 140 битов соответственно. Здесь, однако, следует учитывать, что прогресс в области вычислительной техники и в алгоритмической теории чисел (см. главу ) может привести к необходимости пересмотра этих величин.

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

Next: 3.3. Неотслеживаемость. Электронные деньги

Up: 3. Криптографические протоколы

Previous: 3.1. Введение

Contents:




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]