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

(1)Боб создает 220 (другими словами, больше миллиона) сообщений типа: "Это головоломка номер x. Это секретный ключ номер у.", где x - случайное число, а у - случайный секретный ключ. И x, и y отличаются в каждом сообщении. Используя симметричный алгоритм, он шифрует каждое сообщение своим 20 би т-ным ключом и все их отправляет Алисе.

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

(3)Алиса шифрует свое секретное сообщение при помощи некоторого симметричного алгоритма полученным ею ключом и посылает это сообщение Бобу вместе с x.

(4)Боб знает, какой секретный ключ y он использовал в сообщении x, следовательно он может расшифровать сообщение Алисы.

Ева может взломать эту систему, но ей придется выполнить гораздо больше работы чем Алисе и Бобу . Для раскрытия сообщения на этапе (3) она должна будет вскрыть грубой силой каждое из 220 сообщений, отправленных Бобом на этапе (1). Сложность этого вскрытия составит 2 40. Значения x также не помогут Еве, ведь они на этапе (1) присвоены случайным образом . В общем случае, вычислительные затраты Евы будут равны возв еденным в квадрат вычислительным затратам Алисы .

Это выигрыш (n по отношению к n2) невелик по криптографическим стандартам, но при определенных усл о-виях может быть достаточен. Если Алиса и Боб могут проверить десять тысяч ключей в секунду, каждому из них потребуется минута для выполнения своих действий и еще одна минута для передачи головоломок от Боба к Алисе по линии связи 1.544 Мбит/с. Если вычислительные возможности Евы сравнимы с приведенными, ей потребуется около года для взлома системы. Другие алгоритмы еще более устойчивы к вскрытию .

2.6 Цифровые подписи

Рукописные подписи издавна используются как доказательство авторства документа или, по крайней мере, согласия с ним. Что же так притягательно в подписи [1392]?

1.Подпись достоверна. Она убеждает получателя документа в том, что подписавший сознательно подп и-сал документ.

2.Подпись неподдельна. Она доказывает, что именно подписавший, и никто иной, сознательно подписал документ.

3.Подпись не может быть использована повторно. Она является частью документа, жулик не сможет перенести подпись на другой документ.

4.Подписанный документ нельзя изменить. После того, как документ подписан, его невозможно изм е-нить.

5.От подписи не возможно отречься. Подпись и документ материальны. Подписавший не сможет вп о-следствии утверждать, что он не подписывал документ.

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

Хотелось бы реализовать что-нибудь подобное и на компьютерах, но есть ряд проблем . Во первых, компьютерные файлы скопировать не просто, а очень просто . Даже если подпись человека трудно подделать (например, графическое изображение рукописной подписи), можно легко вырезать правильную подпись из одного докуме н-та и вставить в другой. Простое наличие такой подписи ничего не означает. Во вторых, компьютерные файлы очень легко можно изменить после того, как они подписаны, не оставляя ни малейшего следа изменения .

Подпись документа с помощью симметричных криптосистем и посредника

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

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

(1) Алиса шифрует свое сообщение Бобу ключом KA и посылает его Тренту.

(2)Трент, зная ключ Ka, расшифровывает сообщение.

(3)Трент добавляет к расшифрованному сообщению утверждение, что он получил это сообщение от Алисы, и шифрует это новое сообщение ключом Kb.

(4)Трент посылает новое сообщение Бобу.

(5)Боб расшифровывает сообщение ключом Kb. Он может прочитать и сообщение Алисы, и подтверждение Трента, что сообщение отправлено именно Алисой.

Откуда Трент узнает, что сообщение пришло именно от Алисы, а не от какого-то самозванца ? Он делает этот вывод из шифрования сообщения.

Также ли это хорошо, как подпись на бумаге? Посмотрим на требуемые свойства:

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

2.Эта подпись неподдельна. Только Алиса (и Трент, но ему все верят) знает Ka, поэтому только Алиса могла послать Тренту сообщение, зашифрованное ключом Ka. Если кто-нибудь попытается выдать себя за Алису, Трент сразу заметит это на этапе (2) и не заверит подлинность.

3.Эту подпись нельзя использовать повторно. Если Боб попытается взять подтверждение Трента и пр и-соединить его к другому сообщению, Алиса закричит "Караул!" Посредник (Трент или кто-то совсем другой, имеющий доступ к той же информации) попросит Боба предъявить его сообщение и шифр о-ванное сообщение Алисы. Затем посредник зашифрует сообщение ключом Ka и увидит, что оно не соответствует шифрованному сообщению, переданному Бобом. Боб, конечно же, не сможет создать пр а-вильное шифрованное сообщение, потому что он не знает кл юча Ka.

4.Подписанный документ нельзя изменить. Если Боб попытается, получив документ, изменить его, Трент обнаружит мошенничество уже описанным способом.

5.От подписи невозможно отказаться. Если впоследствии Алиса заявит, что она никогда не посылала сообщение, подтверждение Трента докажет обратное. Помните, все доверяют Тренту, все, сказанное им - истина.

Если Боб захочет показать Кэрол документ, подписанный Алисой, он не сможет раскрыть ей свой секретный ключ. Ему придется снова обратиться к Тренту:

(1)Боб берет сообщение и утверждение Трента, что сообщение получено от Алисы, шифрует их ключом Kb и посылает обратно Тренту.

(2)Трент расшифровывает полученный пакет с помощью ключа Kb.

(3)Трент проверяет свою базу данных и подтверждает, что отправителем оригинального сообщения была Алиса.

(4)Трент шифрует полученный от Боба пакет ключом Kc, который он выделил для Кэрол, и посылает Кэрол шифрованный пакет.

(5)Трент расшифровывает полученный пакет с помощью ключа Kc. Теперь она может прочитать и сообщ е-ние, и подтверждение Трента, что сообщение отправлено Алисой.

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

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

Деревья цифровых подписей

Ральф Меркл предложил систему цифровых подписей, основанную на криптографии с секретным ключом, создающей бесконечное количество одноразовых подписей, используя древовидную структуру [1067,1068]. Основной идеей этой схемы является поместить корень дерева в некий открытый файл , удостоверяя его таким об-

разом. Корень подписывает одно сообщение и удостоверяет подузлы дерева . Каждый из этих узлов подписывает одно сообщение и удостоверяет свои подузлы, и так далее .

Подпись документа с помощью криптографии с открытыми ключами

Существуют алгоритмы с открытыми ключами, которые можно использовать для цифровых подписей. В н е-которых алгоритмах - примером является RSA (см. раздел 19.3) - для шифрования может быть использован или открытый, или закрытый ключ . Зашифруйте документ своим закрытым ключом, и вы получите надежную ци ф-ровую подпись. В других случаях - примером является DSA (см. раздел 20.1) - для цифровых подписей используется отдельный алгоритм, который невозможно использовать для шифрования . Эта идея впервые была изобретена Диффи и Хеллманом [496] и в дальнейшем была расширена и углублена в других работах [1282, 1328, 1024, 1283, 426]. Хороший обзор этой области приведен в [1099]. Основной протокол прост:

(1)Алиса шифрует документ своим закрытым ключом, таким образом подписывая его.

(2)Алиса посылает подписанный документ Бобу.

(3)Боб расшифровывает документ, используя открытый ключ Алисы, таким образом проверяя подпись.

Этот протокол гораздо лучше предыдущего. Трент не нужен ни для подписи документов, ни для ее проверки. (Он нужен для подтверждения, что открытый ключ принадлежит именно Алисе .) Трент не нужен сторонам даже для разрешения споров: Если Боб не смог осуществить этап (3), то он знает, что подпись неправильна. Такая подпись соответствует всем требованиям :

1.Эта подпись достоверна. Когда Боб расшифровывает сообщение с помощью открытого ключа Алисы, он знает что она подписала это сообщение.

2.Эта подпись неподдельна. Только Алиса знает свой закрытый ключ.

3.Эту подпись нельзя использовать повторно. Подпись является функцией документа и не может быть перенесена на другой документ.

4.Подписанный документ нельзя изменить. После любого изменения документа подпись не сможет больше подтверждаться открытым ключом Алисы.

5.От подписи невозможно отказаться. Бобу не требуется помощь Алисы при проверке ее подписи. Подпись документа и метки времени

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

Предположим, что Алиса послала Бобу подписанный чек на $100. Боб отнес чек в банк, который проверил подпись и перевел деньги с одного счета на другой. Боб, выступающий в роли жулика, сохранил копию эле к-тронного чека. На следующей неделе он снова отнес его в этот или другой банк . Банк подтвердил подпись и перевел деньги с одного счета на другой . Если Алиса не проверяет свою чековую книжку, Боб сможет продел ы-вать это годами.

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

Подпись документа с помощью криптографии с открытыми ключами и однонаправленных хэш-функций

На практике алгоритмы с открытыми ключами часто недостаточно эффективны для подписи больших док у-ментов. Для экономии времени протоколы цифровой подписи нередко используют вместе с однонаправленными хэш-функциями [432, 433]. Алиса подписывает не документ, а значение хэш-функции для данного документа . В этом протоколе однонаправленная хэш-функция и алгоритм цифровой подписи согласовываются заранее .

(1)Алиса получает значение однонаправленной хэш-функции для документа.

(2)Алиса шифрует это значение своим закрытым ключом, таким образом подписывая документ.

(3)Алиса посылает Бобу документ и подписанное значение хэш-функции.

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