Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Комбинируя понятия одноразового шифра и универсального хеширования [98], Марк Вегман и Ларри Картер разработали аутентификационные метки совершенно другой природы: они предложили систему аутентификации, которая является нераскрыва-емой в теоретико-информационном смысле [355]. Как и в случае классического применения одноразовых шифров, в ней количество необходимой секретной информации пропорционально числу сообщений, которые должны аутентифицироваться (хотя оно и не зависит от длины этих сообщений). Другими словами, когда какое-то сообщение аутентифицируется, то некоторые биты секретного ключа используются неоднократно. Если пользователи захотят использовать для этого t и более бит на одно сообщение, Вегман и Картер показали, что даже противник с неограниченными вычислительными ресурсами, применяющий атаку на основе выбранных сообщений, не сможет подделать никакую их метку с вероятностью успеха большей, чем 2-t. Они также доказали, что эта вероятность оптимальна.
Жиль Брассар показал, как следует скомбинировать формирование меток Вегмана-Картера с псевдослучайным генератором BBS (см. § 4.5) для того, чтобы добиться того же самого с фиксированным коротким ключом, не зависящим от числа сообщений. Однако получившаяся система оказывается секретной только относительно практически выполнимых вычислений (без неограниченных вычислительных ресурсов), и только если факторизация целых чисел действительно трудна [67]. Одедом Голдрейчем, Шафи Гольдвассер и Сильвио Микэли была предложена также вычислительно секретная аутентификационная система [192], в
Цифровая^ подпись 77
которой в качестве применения использовано введенное ими понятие полислучайного семейства функций [193] (см. также § 6.5).
§ 2. Цифровая подпись
Несмотря на то, что схема аутентификации позволяет Бобу достичь большой уверенности в том, что сообщение, которое он получил, исходило именно от Алисы, эта схема не позволяет ему убедить кого бы то ни было еще в том, что Алиса и в самом деле посылала полученное им сообщение. Таким образом, аутентификационные схемы могут использоваться в отношениях между двумя доверяющими друг другу сторонами, но они не способны обеспечивать улаживание возникающих между ними разногласий. Такая возможность предоставляется только благодаря существованию однонаправленных функций с потайным ходом и основанного на них более сильного понятия цифровой, или электронной, подписи.
Если Алиса посылает Бобу сообщение, подписанное своей электронной подписью, то Боб при его получении не только сам сможет убедиться в том, что это сообщение подписано ни кем иным, как его составителем (т.е. Алисо-й), но и будет также способен доказать в суде, что именно Алиса, и никто иной, подписала это сообщение. Понятие цифровой подписи было введено Уитфилдом Диффи и Мартином Хеллманом [157]; читайте также [307, 296, 297, 258, 201]. Цифровая подпись и электронная почта сулят значительные преимущества, которые даже в принципе неосуществимы в традиционном бумажном документообороте. Так, в § 6.5 мы покажем, что они, например, делают возможной не только электронную почту с удостоверением о получении сообщений, но и электронное заключение контрактов.
Хотелось бы пояснить, почему схема аутентификации не обеспечивает цифровой подписи. Для этого заметим, что если Алис а аутентифицирует сообщение для Боб а так, как это описано в § 1, то Бобу было бы столь же легко получить соответствующую метку и самому. Следовательно, единственной причиной для Боба. быть уверенным в том, что такое вычисление было выполнено Алисой, является то, что Боб знает, что он сам этого не делал. Разумеется, что это не должно быть столь же очевидно и судье.
Криптосхема с открытым ключом позволяет обеспечить воз-
78 Аутентификация и подпись
Глава $
можностъ цифровой подписи, если для каждого ключа к ? /С, Мк —С к и если ffc(Dfc(m)) = т для каждого сообщения т&Мк (второе условие является следствием первого, если Мк конечное множество). Для осуществления цифровой подписи такая схема используется следующим образом. Пусть а — некоторый секретный ключ Алисы и пусть Еа и Da — ее функции шифрования и, соответственно, дешифрования. Тогда, если криптосистема является секретной, то только Алиса сможет вычислить Da эффективно, хотя при этом каждый знает, как вычислять Еа.
Рассмотрим далее некоторый открытый текст т и положим s = Da(m). Очевидно, что любой пользователь криптосистемы может эффективно вычислить Ea(s) и выяснить, что ее значением является т. Однако только Алиса обладает теми знаниями, которые необходимы, чтобы получить такое s, что Ea(s) — т. В этом смысле s может рассматриваться как подпись самой Алисы под сообщением т. Если Боб покажет s судье, и если Ea (s) = Я должна Бобу тысячу долларов, судья вынужден будет согласиться, что никто другой, кроме Алисы, не мог подписать этого утверждения. Другими словами, секретный алгоритм дешифрования Dk может рассматриваться в этом случае как алгоритм, осуществляющий цифровую подпись, а открытый алгоритм шифрования Ек — как соответствующий алгоритм подтверждения этой подписи.
