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

Next: 3.3. Неотслеживаемость. Электронные деньги Up: 3. Криптографические протоколы Previous: 3.1. Введение Contents: Содержание

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

``Воротится коза, постучится в дверь и запоет:
- Козлятушки, ребятушки!
Отопритеся, отворитеся!
Ваша мать пришла - молока принесла.
Козлятки отопрут дверь и впустят мать...
Волк подслушал как поет коза. Вот раз коза ушла, волк подбежал к избушке и закричал толстым голосом:
- Вы детушки! Вы козлятушки!
Отопритеся, отворитеся,
Ваша мать пришла, молока принесла.
Козлята ему отвечают:
- Слышим, слышим - да не матушкин это голосок!...
Волку делать нечего. Пошел он в кузницу и велел себе горло перековать, чтобы петь тонюсеньким голосом...
Только коза ушла, волк опять шасть к избушке, постучался и начал причитывать тонюсеньким голосом:
- Козлятушки, ребятушки!
Отопритеся, отворитеся!
Ваша мать пришла - молока принесла.
Козлята отворили дверь, волк кинулся в избу и всех козлят съел.''

``Волк и семеро козлят''. Русская народная сказка.

Как уже отмечалось во введении, понятие целостности информации, по-видимому, не допускает математической формализации. В данном разделе мы рассмотрим методы обеспечения целостности на примере двух наиболее важных и распространенных типов криптографических протоколов - схем аутентификации и электронной подписи.

Назначение и суть протоколов аутентификации (называемых также протоколами идентификации) легко понять на следующем примере. Представим себе информационную систему, которая работает в компьютерной сети и обеспечивает доступ к некоторым данным. У администратора системы имеется список всех ее пользователей вместе с сопоставленным каждому из них набором полномочий, на основе которых осуществляется разграничение доступа к ресурсам системы. Ресурсами могут быть, например, некоторые фрагменты информации, а также функции, выполняемые системой. Одним пользователям может быть разрешено читать одну часть информации, другим - другую ее часть, а третьим - еще и вносить в нее изменения. В данном контексте под обеспечением целостности понимается предотвращение доступа к системе лиц, не являющихся ее пользователями, а также предотвращение доступа пользователей к тем ресурсам, на которые у них нет полномочий. Наиболее распространенный метод разграничения доступа, парольная защита, имеет массу недостатков. Их обсуждение стало общим местом для текстов по компьютерной безопасности, поэтому мы сразу перейдем к криптографической постановке задачи.

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

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

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

Пусть и - простые числа такие, что делит . Шнорр предлагает [1] использовать длины порядка 512 битов и - длины порядка 140 битов. Пусть $g\in Z_p$ таково, что $g^q=1 \pmod p$ , $g\neq 1$ . Пусть $x\in _RZ_q$ и $y=g^x\pmod p$ . Задача вычисления значения по заданному значению при известных , и называется задачей дискретного логарифмирования (см. главу 4). Для задачи дискретного логарифмирования на данный момент не известно эффективных алгоритмов. Поэтому в криптографии широко используется гипотеза о вычислительной трудности задачи дискретного логарифмирования. Сформулируем ее более строго. Пусть - растущий целочисленный параметр, число выбирается из множества всех простых чисел длины таких, что имеет простой делитель длины не меньше $n^\varepsilon$ для некоторой константы $\varepsilon>0$ , - из множества всех таких простых делителей числа , - из множества всех чисел таких, что $g^q=1 \pmod p$ , а $x\in Z_q$ . Тогда функция $f(x,p,q,g)= (g^x \nmod p, p, q,g)$ - односторонняя (см. главу 2). Рекомендации, данные Шнорром относительно длин чисел и , можно трактовать следующим образом. На тот момент (1989 г.) инвертирование функции считалось практически невыполнимым уже для и длины порядка 512 и 140 битов соответственно. Здесь, однако, следует учитывать, что прогресс в области вычислительной техники и в алгоритмической теории чисел (см. главу 4) может привести к необходимости пересмотра этих величин.

В качестве секретного ключа схемы аутентификации Алиса выбирает случайное число из $\{ 1,\dots ,q-1\}$ . Далее Алиса вычисляет $y=g^{-x}\nmod p$ и публикует открытый ключ . Открытые ключи всех участников схемы должны публиковаться таким образом, чтобы исключалась возможность их подмены (такое хранилище ключей называется общедоступным сертифицированным справочником). Эта проблема, называемая часто проблемой аутентичности открытых ключей, составляет отдельный предмет исследований в криптографии и в данной главе не рассматривается.