Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Книги
 Обсудить в форуме  Добавить новое сообщение
Next: 3.3. Неотслеживаемость. Электронные деньги Up: 3. Криптографические протоколы Previous: 3.1. Введение Contents: Содержание

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

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

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

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

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

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

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

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

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

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


Схема аутентификации Шнорра

  • Алиса выбирает случайное число $ k$ из множества $ \{ 1,\dots ,q-1\}$, вычисляет $ r=g^k\nmod p$ и посылает $ r$ Бобу.

  • Боб выбирает случайный запрос $ e$ из множества $ \{ 0,\dots ,2^t-1\}$, где $ t$ - некоторый параметр, и посылает $ e$ Алисе.

  • Алиса вычисляет $ s=(k+xe) \nmod q$ и посылает $ s$ Бобу.

  • Боб проверяет соотношение $ r=g^sy^e\nmod p$ и, если оно выполняется, принимает доказательство, в противном случае - отвергает.


    • Отметим одно существенное отличие этого протокола от протокола доказательства для задачи ИЗОМОРФИЗМ ГРАФОВ, приведенного в главе 2: последний протокол многораундовый, в нем количество раундов, т.е. посылок сообщений от Алисы Бобу и обратно, возрастает с ростом размерности задачи (количества вершин графа). А в протоколе Шнорра количество раундов равно трем, вне зависимости от значений других параметров. Поэтому с практической точки зрения протокол Шнорра является значительно более эффективным.

    Первое из требований к стойкости протоколов аутентификации, корректность, означает, что противник, знающий только открытый ключ $ y$, может пройти аутентификацию лишь с пренебрежимо малой вероятностью. Несложный анализ показывает, что корректность протокола Шнорра зависит от выбранного значения параметра $ t$. В самом деле, если $ t$ невелико, то противник имеет хорошие шансы просто угадать тот запрос $ e$, который он получит от Боба на шаге 2. Пусть для простоты $ t=1$. Тогда противник, не знающий секретного ключа $ x$, может действовать следующим образом. Подбросив монету, он выбирает равновероятным образом одно из значений 0 или 1. Обозначим его через $ e'$. Далее противник выбирает произвольное $ s$ из $ \{ 0,\dots ,q-1\}$, вычисляет $ r=g^sy^{e'}\nmod p$ и посылает $ r$ Бобу. Ясно, что запрос $ e$, полученный от Боба на шаге 2, совпадет с $ e'$ с вероятностью $ 1/2$, и именно с такой вероятностью противник пройдет аутентификацию.

    Если же значение $ t$ достаточно велико, то шансы угадать запрос $ e$ малы. Шнорр [1] рекомендует $ t=72$. Разумеется, вероятность $ 2^{-72}$, а именно такой будет вероятность простого угадывания, можно считать пренебрежимо малой. Но что будет, если противник атакует схему, используя более изощренные методы? Задача теоретической криптографии в том и состоит, чтобы исследовать стойкость криптографических схем против любых (эффективных) атак противника.

    Если в схеме Шнорра Алиса является противником, то на шаге 1 вместо действий, предписанных протоколом, она может выбирать $ r$ произвольным (но эффективным) образом. Иными словами, Алиса использует некоторый полиномиальный вероятностный алгоритм, который для каждого конкретного значения $ r$ определяет вероятность его выбора.

    Пусть $ r$ - некоторое значение, которое Алиса передала Бобу на шаге 1. Предположим, что нам удалось найти два запроса $ e_1, e_2\in\{ 0,\dots ,2^t-1\}$, $ e_1\neq e_2$, такие, что Алиса может для каждого из них найти соответствующие значения $ s$, для которых проверка на шаге 4 даст положительный результат. Обозначим эти значения $ s$ через $ s_1$ и $ s_2$ соответственно. Мы имеем:
    \begin{gather*} r=g^{s_1}y^{e_1}\pmod p,\ r=g^{s_2}y^{e_2}\pmod p. \end{gather*}
    Отсюда

    \begin{displaymath}g^{s_1}y^{e_1}=g^{s_2}y^{e_2}\pmod p,\end{displaymath}

    или

    \begin{displaymath}g^{s_1-s_2}=y^{e_2-e_1}\pmod p.\end{displaymath}

    Поскольку $ e_1\neq e_2$, существует $ (e_2-e_1)^{-1}\nmod q$ и, следовательно, $ (s_1-s_2)(e_2-e_1)^{-1}$ - дискретный логарифм $ y$, т.е. $ (s_1-s_2)(e_2-e_1)^{-1}\hph=x \pmod q$.

    Таким образом, либо запросы $ e_1$, $ e_2$, $ e_1\neq e_2$, такие, что Алиса может ответить надлежащим образом на оба из них (при одном и том же $ r$) на шаге 3 протокола, встречаются ``достаточно редко'', и это означает, что атака Алисы успешна лишь с пренебрежимо малой вероятностью. Либо такие значения попадаются ``достаточно часто'', и тогда тот алгоритм, который применяет Алиса, можно использовать для вычисления дискретных логарифмов.

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

    Отметим, что вопреки весьма распространенному мнению, этот результат, как и большинство подобных результатов в теоретической криптографии, не является асимптотическим: если задача дискретного логарифмирования трудна для чисел ($ p$ и $ q$) данной длины, то схема Шнорра является корректной при использовании чисел той же длины.

    Активный противник может провести некоторое количество сеансов выполнения протокола в качестве проверяющего с честным доказывающим (или подслушать такие выполнения) и после этого попытаться атаковать схему аутентификации. Для стойкости против активного противника достаточно, чтобы протокол аутентификации был доказательством с нулевым разглашением. Однако свойство нулевого разглашения для схемы Шнорра до сих пор никому доказать не удалось. Более того, на данный момент известен единственный метод доказательства свойства нулевого разглашения - так называемый метод ``черного ящика''. В этом методе моделирующая машина использует алгоритм проверяющего (машину Тьюринга $ V^*$ - в обозначениях из главы 2) лишь в качестве оракула, т.е. не анализируя сам этот алгоритм, подает ему на вход любые значения по своему выбору и получает соответствующие выходные значения. Гольдрайх и Кравчик доказали [2], что трехраундовые доказательства с нулевым разглашением, в которых последнее свойство устанавливается методом ``черного ящика'', существуют лишь в тривиальном случае, т.е. когда проверяющий может самостоятельно, без всякой помощи доказывающего, проверить истинность утверждаемого. В отношении схемы Шнорра из этого результата следует, что либо существует эффективный алгоритм дискретного логарифмирования, либо свойство нулевого разглашения этого протокола не может быть доказано методом ``черного ящика''. Вопрос о существовании доказательств с нулевым разглашением, для которых свойство нулевого разглашения не может быть доказано методом ``черного ящика'', остается открытым.

    Нетрудно показать, что схема Шнорра обладает несколько более слабым свойством - свойством нулевого разглашения относительно честного проверяющего. В этом случае достаточно построить моделирующую машину только для честного проверяющего, который на шаге 2 и в самом деле выбирает случайный запрос $ e$ из множества $ \{ 0,\dots ,2^t-1\}$.

    Вся информация, которую получает Боб в результате выполнения протокола - это тройка чисел $ (r,e,s)$ такая, что $ r=g^sy^e\pmod p$ и $ r\neq 1$. Обозначим множество всех таких троек через $ \Omega$. В этой тройке число $ e$ выбирается случайным образом из $ \{ 0,\dots ,2^t-1\}$, а $ r=g^k\nmod p$, где $ k$ - случайное число из множества $ \{ 1,\dots ,q-1\}$. Ясно, что при таком выборе $ k$ значение $ r$ будет распределено равновероятным образом среди всех отличных от единицы элементов группы, порожденной $ g$. Значение $ s$ вычисляется согласно шагу 3 протокола и определяется величинами $ e$ и $ r$ однозначно. Таким образом, распределение вероятностей на множестве $ \Omega$ определяется случайным выбором чисел $ e$ и $ k$.

    Моделирующая машина должна создать на множестве $ \Omega$ такое же распределение вероятностей как в протоколе. Но при этом она не может использовать формулу из шага 3, поскольку в нее входит секретный ключ $ x$. Вместо этого моделирующая машина выбирает случайные $ e$ и $ s$ из $ \{ 0,\dots ,2^t-1\}$ и $ \{ 0,\dots ,q-1\}$ соответственно и вычисляет $ r=g^sy^e\nmod p$. Если $ r=1$, то попытка неудачна и выбираются новые $ e$ и $ s$. В противном случае моделирующая машина выдает тройку $ (r,e,s)$. Напомним, что моделирующая машина строится только для честного доказывающего. Из этого, в частности, следует, что открытый ключ $ y$ принадлежит группе, порожденной $ g$, т.е. существует число $ x\in \{1,\dots ,q-1\}$ такое, что $ g^{-x}=y\pmod p$. Поэтому при любых $ e$ и $ s$ число $ r=g^sy^e=g^sg^{-xe}=g^{s-xe}\pmod p$ также принадлежит этой группе. Остается лишь заметить, что поскольку моделирующая машина выбирает число $ s$ случайным образом и независимо от значения $ e$, величина $ (s-xe)\nmod q$ - случайный элемент множества $ \{ 0,\dots ,q-1\}$, также не зависящий от $ e$. Поэтому число $ r$, сгенерированное моделирующей машиной, является случайным элементом группы, порожденной $ g$, не зависящим от $ e$, т.е. имеет такое же распределение, как в протоколе. Иными словами, одно и то же распределение вероятностей на множестве $ \Omega$ можно создать двумя способами: либо выбрать случайное $ k$ (а, следовательно, и $ r$) и вычислить $ s=(k+xe) \nmod q$, либо выбрать случайное $ s$ и получить $ r=g^{s-xe}\nmod p$.

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

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

    Прежде чем завершить разговор о протоколах аутентификации необходимо подчеркнуть, что никакое математически строго доказанное свойство криптографического протокола не может гарантировать его безопасности во всех случаях жизни. В самом деле, даже протокол доказательства с нулевым разглашением не защищает от следующей атаки на схему аутентификации, известной в криптографической литературе под названием ``мафиозная угроза''. В данном сценарии имеются четыре участника: $ A$, $ B$, $ C$ и $ D$. Предположим, что $ A$ зашел в кафе выпить чашечку кофе и расплачивается с помощью кредитной карточки. Для выполнения любой банковской операции карточка должна идентифицировать себя, т.е. выполнить протокол аутентификации. Но владелец кафе, $ B$, - мафиози, сообщник которого $ C$ в тот же самый момент находится в магазине ювелира $ D$ и пытается купить бриллиант, также с помощью кредитной карточки. При этом $ C$ ``представляется'' как $ A$, а $ D$ просит доказать это с помощью протокола аутентификации. Устройство считывания для карточек у $ B$ и карточка у $ C$ - это специально изготовленные приемо-передающие устройства, которые лишь пересылают сообщения между $ A$ и $ D$. В результате $ A$, обмениваясь сообщениями с $ B$, на самом деле идентифицирует себя для $ D$.

    Мы здесь не затрагиваем вопроса о практической осуществимости ``мафиозной угрозы''. Мы привели ее просто как пример, показывающий, что только математического обоснования стойкости того или иного криптографического протокола недостаточно. Для практического применения конкретного протокола требуются еще усилия специалистов в области информационной безопасности по анализу условий его применения.

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

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

    Как обычно, математическая формализация рассматривает схему электронной подписи как бесконечное семейство схем, зависящих от целочисленного параметра $ n$, $ n>0$, называемого параметром безопасности.

    Схема электронной подписи - это тройка алгоритмов $ (G,S,V)$, где

    $ G$ - полиномиальный вероятностный алгоритм генерации ключей. На входе $ 1^n$ алгоритм $ G$ выдает пару $ (K_1,K_2)$, где $ K_1$ - открытый ключ схемы подписи, а $ K_2$ - соответствующий ему секретный ключ. Ключ $ K_1$ помещается в общедоступный сертифицированный справочник;

    $ S$ - полиномиальный вероятностный алгоритм генерации подписей. На входе $ (m,K_2)$, где $ m$ - сообщение, алгоритм $ S$ выдает подпись $ s$ для сообщения $ m$;

    $ V$ - полиномиальный алгоритм проверки подписи. Если $ V(K_1, m, s)=1$, то подпись $ s$ для сообщения $ m$ принимается. В этом случае говорят, что $ s$ - корректная подпись для сообщения $ m$. Если $ V(K_1,m,s)=0$, то подпись $ s$ отвергается. Если подпись $ s$ для сообщения $ m$ сгенерирована на ключе $ K_2$ с помощью алгоритма $ S$, то всегда должно быть $ V(K_1, m, s)=1$.

    Здесь $ K_1$, $ K_2$, $ m$ и $ s$ - двоичные строки, длины которых ограничены некоторыми фиксированными полиномами от $ n$.

    Для определения стойкости схемы электронной подписи необходимо принять некоторые предположения о противнике. Последний может пытаться подделывать подписи, зная только открытый ключ схемы. Такой противник называется пассивным и является самым слабым из всех возможных противников, так как открытый ключ схемы подписи всегда общедоступен. Разумеется, пассивный противник, как и любой другой, знает описание схемы подписи, поскольку предполагается, что алгоритмы $ G$, $ S$ и $ V$ общедоступны.

    Более изобретательный противник может попытаться собрать некоторую дополнительную информацию о схеме подписи, набрав некоторое количество пар (сообщение, подпись). Здесь имеются два основных варианта. Атака с известными сообщениями состоит в том, что противник перехватывает некоторое (ограниченное фиксированным полиномом от $ n$) количество подписанных сообщений. При этом противник никак не влияет на выбор этих сообщений. По существу это - разновидность пассивного противника, так как подписанные сообщения обычно пересылаются по общедоступному каналу связи (в некоторых работах по теоретической криптографии принимается математическая модель, в которой подписанные сообщения просто публикуются).

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

    Помимо атаки необходимо также определить ту угрозу безопасности схемы электронной подписи, против которой мы желаем защищаться. Самая сильная угроза - полное раскрытие, т.е. вычисление противником секретного ключа $ K_2$. Ясно, что если противник может осуществить подобную угрозу, то схема нестойкая. С другой стороны, нетрудно понять, что стойкости против полного раскрытия недостаточно для того, чтобы считать схему подписи стойкой на практике. Достаточно рассмотреть следующую вырожденную схему. Алгоритм $ G$ выбирает случайный секретный ключ $ K_2$ и вычисляет $ K_1=f(K_2)$, где $ f$ - некоторая односторонняя функция. Подпись для сообщения $ m$ алгоритм $ S$ вычисляет в виде $ s=g(m)$, где $ g$ - некоторая легко вычислимая функция. Функция $ g$ публикуется как часть открытого ключа, и проверка подписи состоит в вычислении $ g(m)$ и сравнении подписи $ s$ с этим значением. Ясно, что такая схема будет стойкой против полного раскрытия, поскольку для вычисления секретного ключа $ K_2$ требуется инвертировать одностороннюю функцию $ f$. Но всякий желающий может вычислить подпись для любого сообщения. Этот пример поучителен еще и потому, что в криптографической литературе встречаются статьи, в которых анализ стойкости схем электронной подписи подменяется рассуждениями о сложности задачи полного раскрытия.

    На другом полюсе находится самая слабая из угроз - угроза экзистенцианальной подделки. Такая угроза осуществима, если после проведения атаки на схему электронной подписи противник может подделать подпись хотя бы для одного, пусть даже бессмысленного, сообщения.

    Стойкость схемы электронной подписи определяется относительно пары (атака, угроза). Наиболее стойкими являются схемы, стойкие против самой слабой из угроз на основе самой сильной из атак, т.е. против экзистенцианальной подделки на основе атаки с выбором сообщений. Опишем эти атаку и угрозу на несколько более строгом уровне. Систематическое изложение атак и угроз для схем электронной подписи см. в [3].

    Под противником мы понимаем вероятностную машину Тьюринга $ A$, которая получает на входе $ 1^n$ и $ K_1$ и завершает свою работу за полиномиальное (от $ n$) время. Машина $ A$ имеет доступ к алгоритму $ S$ генерации подписей (знающему секретный ключ $ K_2$) как к оракулу. Тем самым $ A$ может выбрать сообщения $ m_1,\dots ,m_l$, где $ l\leq p(n)$ для некоторого полинома $ p$, и получить для них корректные подписи $ s_1,\dots ,s_l$ соответственно. При оценке времени работы машины $ A$ каждое обращение к оракулу считается одной командой. Можно считать, что к моменту выбора сообщения $ m_i$ машина $ A$ уже знает подписи $ s_1,\dots ,s_{i-1}$ для всех предшествующих сообщений. Такая атака называется адаптивной. После этого машина $ A$ должна найти пару $ (m,s)$, где $ m\neq m_i$ для всех $ i=1,\dots ,l$ такую, что $ s$ - корректная подпись для сообщения $ m$. Обозначим через $ A(1^n,K_1)\rightarrow (m,s)$ событие, состоящее в том, что $ A$ находит такую пару. Схема электронной подписи $ (G,S,V)$ называется стойкой против экзистенцианальной подделки на основе (адаптивной) атаки с выбором сообщений, если для любой машины Тьюринга $ A$ указанного выше вида, для любого полинома $ P$ и для всех достаточно больших $ n$

    \begin{displaymath}Pr\{A(1^n,K_1)\rightarrow (m,s)\}<1/P(n).\end{displaymath}

    Вероятность здесь определяется случайными величинами алгоритмов $ G$, $ S$ и $ A$.

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

    Рассмотрим вначале схему электронной подписи Лампорта[4]. Пусть $ f\colon \Sigma ^n\rightarrow \Sigma^n$, где $ \Sigma=\{0,1\}$, - односторонняя функция и пусть $ \Sigma ^r$ - множество, из которого выбираются подписываемые сообщения (т.е. каждое сообщение $ m=m_1\dots m_r$ рассматривается как $ r$-битовая строка). Алгоритм вычисления функции $ f$ считается общедоступным.

    Алгоритм генерации ключей выбирает $ 2r$ случайных строк из $ \Sigma^n$: $ x_1^0, x_1^1, x_2^0,x_2^1,\dots ,x_r^0, x_r^1$. Совокупность этих $ 2r$ строк составляет секретный ключ схемы подписи. Далее алгоритм вычисляет

    \begin{displaymath}y_1^0=f(x_1^0), y_1^1 =f(x_1^1), \dots, y_r^0=f(x_r^0), y_r^1=f(x_r^1).\end{displaymath}

    Совокупность строк $ y_1^0, y_1^1,\dots, y_r^0, y_r^1$ публикуется как открытый ключ схемы.

    Подписью для сообщения $ m=m_1\dots m_r$ служит последовательность строк $ (x_1^{m_1},\dots ,x_r^{m_r})$. Иными словами, для $ i$-го бита сообщения $ m$ открывается одно из значений $ x_i^0$ или $ x_i^1$ в зависимости от того, чему равен $ i$-ый бит $ m_i$ - нулю или единице. Проверка подписи $ s=(s_1,\dots ,s_r)$ очевидна: для каждого $ i=1,\dots ,r$ вычисляется значение $ f(s_i)$ и сравнивается с соответствующей строкой $ y_i^{m_i}$ из открытого ключа.

    Схема Лампорта ``одноразовая'', она позволяет подписать одно $ r$-битовое сообщение, после чего надо сгенерировать новые ключи и заменить открытый ключ в сертифицированном справочнике. Но с другой стороны, эта схема уже обладает тем свойством, которого мы добиваемся: если $ f$ - односторонняя функция, то схема стойкая. В самом деле, пусть $ Y=(y_1^0, y_1^1,\dots ,y_r^0, y_r^1)$ - открытый ключ, а $ (m,s)$ - сообщение и корректная подпись для него, вычисленная на секретном ключе $ X=(x_1^0, x_1^1,\dots,x_r^0, x_r^1)$, соответствующем открытому ключу $ Y$. Предположим, что противник может за полиномиальное время с вероятностью по крайней мере $ 1/P(n)$ для некоторого полинома $ P$ найти пару $ (m',s')$, где $ m'\neq m$, а $ s'$ - корректная подпись для $ m'$. Пусть $ i_0$ - номер бита, в котором отличаются сообщения $ m$ и $ m'$, и предположим для определенности, что $ m_{i_0}=0$, а $ m'_{i_0}=1$. Тогда в подписи $ s$ отсутствует значение $ x^1_{i_0}$, а в $ s'$ должно присутствовать какое-либо значение $ x$ такое, что $ f(x)=y^1_{i_0}=f(x^1_{i_0})$. Следовательно, алгоритм $ A$, которым пользуется противник для вычисления $ s'$, должен уметь инвертировать функцию $ f$ на этом значении $ y_{i_0}$. Тогда следующий алгоритм будет противоречить предположению о том, что функция $ f$ односторонняя. Пусть $ u$ выбрано наудачу из $ \Sigma^n$ и $ v=f(u)$ задано нам в качестве входного значения. Выбираем случайное $ j$ из множества $ \{ 1,\dots ,2r\}$. Для всех $ i=1,\dots ,2r$, $ i\neq j$, генерируем соответствующие компоненты ключей $ X$ и $ Y$ с помощью алгоритма $ G$, а вместо $ j$-го элемента ключа $ Y$ подставляем $ v$. Далее вызываем алгоритм $ A$, подавая ему на вход ключ $ Y$. Когда $ A$ запросит подпись для некоторого сообщения $ m$, проверяем, требуется ли для подписания этого сообщения прообраз значения $ v$. Если да, то попытка неудачна (вероятность этого $ 1/2$). В противном случае создаем подпись $ s$ для $ m$ и передаем ее алгоритму $ A$.

    Если $ A$ успешно подделывает подпись для некоторого сообщения $ m'$, $ m'\neq m$, то проверяем, не содержит ли эта подпись прообраз значения $ v$. Если да, то выдаем этот прообраз.

    Ясно, что в случае успеха описанный алгоритм инвертирует функцию $ f$. Очевидно также, что этот алгоритм работает за полиномиальное время. Оценим теперь вероятность успеха. Прежде всего заметим, что алгоритм $ A$ получает на вход только открытый ключ $ Y$ и распределение вероятностей на множестве всех возможных значений $ Y$ такое же как в том случае, когда $ A$ атакует схему подписи. Поэтому мы угадаем $ i_0$ и $ m'_{i_0}$ (т.е. произойдет событие $ j=2\cdot i_0+m'_{i_0}$) с вероятностью $ 1/2r$. Общая вероятность успеха будет по крайней мере $ \dfrac{1}{4rP(n)}$, что не меньше, чем $ 1/Q(n)$ для некоторого полинома $ Q$ (напомним, что по определению $ r$ не превосходит некоторого полинома от параметра безопасности $ n$).

    В качестве своеобразного криптографического курьеза укажем, что если в схеме Лампорта разрешить подписывать любые сообщения, длина которых не превосходит $ r$, то из подписи для сообщения $ m$ можно легко создать подпись для любого его префикса. Например, из подписи для сообщения, представляющего собой знаменитую фразу ``казнить нельзя, помиловать'' можно изготовить подпись для сообщения ``казнить''. Конечно, в данном случае можно предложить простые и эффективные контрмеры. Например, можно потребовать, чтобы короткие сообщения дополнялись справа двоичными нулями до длины $ r$. Но этот курьез служит хорошей иллюстрацией следующего общего принципа: всякое утверждение о стойкости какой-либо криптографической схемы требует точной спецификации значений всех ее параметров и зачастую даже незначительное отступление от установленных значений полностью разрушает стойкость схемы.

    Теперь осталось только преобразовать схему Лампорта в ``многоразовую''. Идея такого преобразования достаточно очевидна: в момент подписания очередного сообщения $ m$ нужно выбрать новые секретный и открытый ключи $ X$ и $ Y$ и отправить получателю тройку $ (m,Y,s)$, где $ s$ - подпись для сообщения $ m\Vert Y$. В результате возникает цепочка открытых ключей $ Y_1, Y_2,\dots ,Y_j,\dots$ и соответствующих им подписей $ s_2, \dots ,s_j, \dots $. Здесь $ Y_1$ - открытый ключ, хранящийся в сертифицированном справочнике, а $ s_j$ - подпись для ключа $ Y_j$, сгенерированная с помощью секретного ключа $ X_{j-1}$, соответствующего открытому ключу $ Y_{j-1}$. Таким образом, каждый открытый ключ $ Y_j$ будет аутентифицирован посредством цепочки подписей $ s_2,\dots ,s_j$ и, следовательно, может использоваться совместно с секретным ключом $ X_j$ для генерации и проверки подписей для сообщений. Проблема, однако, в том, что с помощью одной пары ключей $ (X,Y)$ можно подписать только $ r$ битов сообщения, а длина одного только нового открытого ключа равна $ 2rn$ битам.

    Для описания способа решения этой проблемы нам потребуется новое понятие - понятие криптографической хэш-функции. Хэш-функции - весьма любопытный криптографический примитив, заслуживающий отдельного разговора. Здесь же мы лишь кратко обсудим это понятие. Говоря неформально, криптографическая хэш-функция - это легко вычислимая функция, сжимающая входные значения, для которой не существует эффективного алгоритма поиска коллизий. Коллизией для функции $ h$ называется пара значений $ x$, $ y$, $ x\neq y$, такая, что $ h(x)=h(y)$. Поскольку хэш-функция сжимает входные значения, коллизии заведомо существуют и их можно найти полным перебором. Но, по определению, никакой полиномиальный алгоритм не найдет коллизий у криптографической хэш-функции.

    Следующее определение семейства односторонних хэш-функций было дано Наором и Юнгом [4]. Пусть $ n$ - целочисленный параметр, $ n>0$ и $ H_n$ - множество функций $ h\colon\Sigma ^n\rightarrow \Sigma ^k$, где $ k=k(n)<n$. При этом предполагается, что $ n<p(k)$ для некоторого полинома $ p$. Далее, каждая функция $ h\in H_n$ имеет описание $ \bar h$ и существует полиномиальный вероятностный алгоритм, который на входе $ 1^n$ выбирает равновероятным образом из множества всех описаний функций из $ H_n$. Предполагается также, что существует полиномиальный алгоритм, который, получив на вход описание $ \bar h$ функции из $ H_n$ и $ x\in \Sigma ^n$, выдает значение $ h(x)$. Под противником, который пытается отыскать коллизии, понимается полиномиальный вероятностный алгоритм $ B$, работающий в два этапа. Сначала он получает на вход $ 1^n$ и должен выдать какое-нибудь значение $ x$ из $ \Sigma^n$. После этого $ B$ получает $ \bar h$, выбранное наудачу из множества всех описаний функций из $ H_n$. Семейство $ \{ H_n\}$ называется семейством односторонних хэш-функций, если для любого такого алгоритма $ B$, для любого полинома $ P$ и для всех достаточно больших $ n$

    \begin{displaymath}Pr\{B(\bar h)=y\mid y\in \Sigma ^n, y\neq x\mathop{\&}h(x)=h(y)\} <1/P(n).\end{displaymath}

    Предположим, что существует семейство односторонних хэш-функций $ \{ H_{2nr}\}$, где $ H_{2nr}=\{ h\colon\Sigma ^{2nr}\rightarrow \Sigma ^k, k<n\}$. Как показали Наор и Юнг [4], с помощью такого семейства схему Лампорта можно превратить в ``многоразовую'' следующим образом. Подписывающий выбирает случайное описание $ \bar h$ функции $ h\in H_{2nr}$ и помещает это описание в сертифицированный справочник вместе с открытым ключом $ Y_1$. Подписываемые сообщения имеют длину $ n-k$. Когда подписывается первое сообщение, генерируется новая пара ключей $ (X_2,Y_2)$ и вычисляется значение $ h(Y_2)$. Далее, с помощью первых $ n-k$ элементов ключа $ X_1$ подписывается сообщение, а с помощью последних $ k$ элементов - значение $ h(Y_2)$. После этого сообщение, новый открытый ключ $ Y_2$ и подписи посылаются получателю. Аналогичным образом подписываются все последующие сообщения. Для проверки подписи нужно либо проверять всю цепочку, начиная с $ Y_1$, либо помнить последний аутентифицированный подписывающим открытый ключ.

    Анализ этой схемы (подробности см. в [4]) показывает, что для подделки подписей противник должен уметь либо подменять открытый ключ $ Y_j$, не меняя значения $ h(Y_j)$, а значит, находить коллизии для функции $ h$, либо инвертировать функцию $ f$.

    Остается еще понять, почему указанная возможность находить коллизии противоречит определению семейства односторонних хэш-функций. Ведь противник заранее знает описание $ \bar h$ и только потом получает значение, для которого требуется найти коллизию; а значит, задача противника при атаке на схему подписи кажется более легкой, чем та, которая указана в определении семейства односторонних хэш-функций. Но дело в том, что подписывающий выбирает $ \bar h$ и все $ X_j$ равновероятным образом и независимо друг от друга. Следовательно, и все $ Y_j$ будут независимы от $ \bar h$. Поэтому противник, атакующий хэш-функцию, может сам выбрать значение $ Y$ таким же образом, как это делает подписывающий, и после этого получить случайное описание $ \bar h$. Легко понять, что вероятность успеха атаки при этом не изменится.

    Наор и Юнг [4] построили семейство односторонних хэш-функций, исходя из предположения о существовании односторонней перестановки. Ромпель [5] усилил этот результат, доказав, что достаточно (любой) односторонней функции. Тем самым установлено, что схемы электронной подписи, стойкие против экзистенцианальной подделки на основе атаки с выбором сообщений, существуют тогда и только тогда, когда существуют односторонние функции.

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

    К сожалению, эта схема подписи слишком неэффективна, чтобы ее можно было использовать на практике. Во-первых, подписи имеют слишком большую длину. На каждый подписываемый бит требуется $ n$ битов подписи. Во-вторых, получатель должен хранить всю цепочку открытых ключей, начиная с $ Y_1$, и всю последовательность подписанных сообщений для предъявления их арбитру в случае возникновения споров о подлинности подписей. С помощью некоторых ухищрений можно несколько сократить длины цепочек и уменьшить размер подписи, но полностью избавиться от этих недостатков не удается. Вопрос о возможности построения практически эффективных схем электронной подписи, исходя из одного только предположения о существования односторонней функции, остается открытым.

    Рассмотрим теперь пример практической схемы электронной подписи. Вернемся к схеме аутентификации Шнорра. В этом протоколе интерактивность требуется только для того, чтобы получить от проверяющего случайный запрос $ e$. Поэтому если бы у доказывающего был надежный источник случайности, пользующийся доверием проверяющего, то протокол можно было бы сделать неинтерактивным. Фиат и Шамир [6] предложили способ преобразования протокола аутентификации в схему электронной подписи путем замены случайного запроса неким ``суррогатом''. А именно, пусть $ m$ - подписываемое сообщение и $ h$ - криптографическая хэш-функция. Тогда вместо обращения к проверяющему (он же - получатель сообщения) доказывающий (он же - подписывающий) вычисляет величину $ h(m)$ и использует ее в качестве запроса $ e$. Этот метод универсален, так как применим к широкому классу протоколов аутентификации. Опишем теперь получаемую в результате такого преобразования схему электронной подписи Шнорра [1]. Открытый и секретный ключи подписывающего генерируются в этой схеме таким же образом, как в схеме аутентификации Шнорра. Открытый ключ помещается в общедоступный сертифицированный справочник.


    Схема электронной подписи Шнорра

  • Подписывающий выбирает случайное число $ k\in \{ 1,\dots ,q-1\}$ и вычисляет $ r=g^k\nmod p$.

  • Подписывающий вычисляет $ e=h(r,m)$, где $ m$ - подписываемое сообщение.

  • Подписывающий вычисляет $ s=(k+xe) \nmod q$ и посылает сообщение $ m$ с подписью $ (e,s)$ получателю.

  • Получатель вычисляет $ r'=g^sy^e \nmod p$ и проверяет, выполняется ли равенство $ e=h(r',m)$. Если да, то подпись принимается, в противном случае - отвергается.


    • Предполагается, что хэш-функция $ h$ отображает пары значений $ (r,m)$ в множество $ \{ 0,\dots ,2^t-1\}$.

    Легко проверить, что для подписи, сгенерированной согласно протоколу, проверка п.4 всегда будет выполнена.

    Стойкость схемы Шнорра в значительной степени зависит от свойств функции $ h$. Если противник умеет отыскивать коллизии специального вида, т.е. по заданной паре $ (r,m)$ находить другое сообщение $ m'$, $ m'\neq m$, такое, что $ h(r,m)=h(r,m')$, то он может осуществлять экзистенцианальную подделку подписей. Для этого достаточно перехватить сообщение $ m$ и подпись $ (e,s)$ для него, а также найти коллизию указанного вида. Тогда пара $ (e,s)$ будет также подписью и для сообщения $ m'$.

    Хэш-функции являются неотъемлемой частью конструкции схем электронной подписи. Это является следствием необходимости подписывать сообщения различной длины. Конечно, длинные сообщения можно разбивать на блоки, имеющие требуемую для схемы подписи длину, и подписывать каждый блок. Но это решение неэффективно. На практике используются хэш-функции, которые преобразуют сообщения произвольной длины в хэш-значения требуемой длины. Ясно, что такая хэш-функция должна быть в каком-то смысле стойкой против попыток найти коллизии. Но поскольку практические хэш-функции конструируются для конкретных длин хэш-значений (скажем, 256 битов), формализовать это требование не удается.

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

    Стойкость схем электронной подписи против пассивного противника, который, зная только открытый ключ, пытается подделывать подписи, может быть доказана в так называемой модели со случайным оракулом. В этой модели подписывающий и проверяющий вместо вычисления функции $ h$ обращаются к оракулу, который для каждого входного значения $ \alpha$ выбирает случайное выходное значение $ \beta$ и выдает его в качестве ответа. При этом пара $ (\alpha ,\beta )$ запоминается и в случае повторного обращения с входным значением $ \alpha$ оракул снова выдаст значение $ \beta$. Как заметили Фиат и Шамир [6], изложенная выше идея доказательства корректности схем аутентификации применима в данной модели для доказательства стойкости схем подписи против пассивного противника. Этот результат справедлив для широкого класса схем подписи, включающего схему Шнорра. Фактически это означает, что схемы подписи являются стойкими (против указанного выше пассивного противника), если хэш-функция ведет себя, как случайная функция. Это утверждение является по-существу единственным результатом теоретической криптографии, касающимся стойкости практических схем электронной подписи, если не считать работы [8], где то же самое доказано в предположении, что хэш-функция ведет себя, как функция дешифрования стойкой, в некотором смысле, криптосистемы.

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

    Проект осуществляется при поддержке:
     Геологического факультета МГУ,
    РФФИ
    		    
    TopList Rambler's Top100