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

Комбинируя понятия одноразового шифра и универсального хеширования [98], Марк Вегман и Ларри Картер разработали ау-тентификационные метки совершенно другой природы: они предложили систему аутентификации, которая является нераскрыва-емой в теоретико-информационном смысле [355]. Как и в случае классического применения одноразовых шифров, в ней количество необходимой секретной информации пропорционально числу сообщений, которые должны аутентифицироваться (хотя оно и не зависит от длины этих сообщений). Другими словами, когда какое-то сообщение аутентифицируется, то некоторые биты секретного ключа используются неоднократно. Если пользователи захотят использовать для этого t и более бит на одно сообщение, Вегман и Картер показали, что даже противник с неограниченными вычислительными ресурсами, применяющий атаку на основе выбранных сообщений, не сможет подделать никакую их метку с вероятностью успеха большей, чем 2~*. Они также доказали, что эта вероятность оптимальна.

Жиль Брассар показал, как следует скомбинировать формирование меток Вегмана-Картера с псевдослучайным генератором BBS (см. § 4.5) для того, чтобы добиться того же самого с фиксированным коротким ключом, не зависянщм от числа сообщений. Однако получившаяся система оказывается секретной только относительно практически выполнимых вычислений (без неограниченных вычислительных ресурсов), и только если факторизация целых чисел действительно трудна [67]. Одедом Голдрейчем, Шафи Гольдвассер и Сильвио Микэли была предложена также вычислительно секретная аутентификационная система [192], в

§ 2 Цифрова1Аподдвсь 77

которой в качестве применения использовано введенное ими понятие полислучг1йного семейства функций [193] (см. также § 6.5).

§ 2. Цифровая подпись

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

Если Алиса посылает Бобу сообщение, подписанное своей электронной подписью, то Боб при его получении не только сам сможет убедиться в том, что это сообщение подписано ни кем иным, как его составителем (т.е. Алисой), но и будет также способен доказать в суде, что именно Алиса, и никто иной, подписала это сообщение. Понятие цифровой подписи было введено Уитфилдом Диффи и Мартином Хеллманом [157]; читайте также [307, 296, 297, 258, 201]. Цифровая подпись и электронная почта сулят значительные преимущества, которые даже в принципе неосуществимы в традиционном бумажном документообороте. Так, в § 6.5 мы покажем, что они, например, делают возможной не только электронную почту с удостоверением о получении сообщений, но и электронное заключение контрактов.

Хотелось бы пояснить, почему схема аутентификации не обеспечивает цифровой подписи. Для этого заметим, что если Алиса аутентифицирует сообщение для Боба так, как это описано в § 1, то Бобу было бы столь же легко получить соответствующую метку и самому. Следовательно, единственной причиной для Боба быть уверенным в том, что такое вычисление было выполнено Алисой, является то, что Боб знает, что он сам этого не делал. Разумеется, что это не должно быть столь же очевидно и судье.

Криптосхема с открытым ключом позволяет обеспечить воз-

можность цифровой подписи, если для каждого ключа к Е 1С, Мк = Cft и если Ek(Dk(m)) = m для каждого сообщения га €Л4к (второе условие является следствием первого, если Мк конечное множество). Для осуществления цифровой подписи такая схема используется следующим образом. Пусть а - некоторый секретный ключ Алисы и пусть Еа я Da - ее функции шифрования и, соответственно, дешифрования. Тогда, если криптосистема является секретной, то только Алиса сможет вычислить Da эффективно, хотя при этом каждый знает, как вычислять Ед.

Рассмотрим далее некоторый открытый текст га и положим S = Оа(т). Очевидно, что любой пользователь криптосистемы может эффективно вычислить Ea{s) и выяснить, что ее значением является т. Однако только Алиса обладает теми знаниями, которые необходимы, чтобы получить такое s, что Ea{s) - га. В этом смысле s может рассматриваться как подпись самой Алисы под сообщением га. Если Боб покажет s судье, и если Ea(s) = Я должна Бобу тысячу долларов, судья вынужден будет согласиться, что никто другой, кроме Алисы, не мог подписать этого утверждения. Другими словами, секретный алгоритм дешифрования Dk может рассматриваться в этом случае как алгоритм, осуществляющий цифровую подпись, а открытый алгоритм шифрования Ек - как соответствующий алгоритм подтверждения этой подписи.

В криптосистемах с открытым ключом цифровая подпись может использоваться совместно с шифрованием, если требуется также соблюдать и секретность. Предположим, что Ь - секретный ключ Боба. Тогда, если Алиса захочет послать Бобу подписанное секретное сообщение га, то она использует свой секретный алгоритм подписи Da и его открытый алгоритм шифрования Еь, чтобы получить с = Eb{Da{m)). Если Алиса пошлет сообщение с Бобу по несекретному каналу, то тот сможет вычислить подпись Алисы под этим сообщением как s = Оь{с), а затем восстановить его в открытом виде как га = Ea{s). При этом предполагается, конечно, что в заголовке сообщения явно говорится, что оно исходит от Алисы, так что Боб знает, чей алгоритм подтверждения подписи применять для того, чтобы получить открытый текст. Более того, если Боб сохранит s, то, как мы уже объясняли ранее, он сможет доказать судье, что именно Алиса, и никто другой, послала ему сообщение тп.