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

открытого ключа Алисы. Если подписанное значение хэш-функции совпадает с рассчитанным, подпись правильна.

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

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

Алгоритмы и терминология

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

В общем случае я буду ссылаться на процессы подписи и проверки , не вдаваясь в подробности алгоритмов. Подпись сообщения с закрытым ключом К будет обозначаться как:

Sk(M)

а проверка подписи с помощью соответствующего открытого ключа как : Vk(M)

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

Несколько подписей

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

С помощью однонаправленных реализовать несколько подписей просто :

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

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

(3) Боб посылает свою подпись Алисе.

(4) Алиса посылает Кэрол документ, свою подпись и подпись Боба.

(5) Кэрол проверяет подписи Алисы и Боба.

Алиса и Боб могут выполнить этапа (1) и (2) или параллельно, или последовательно . На этапе (5) Кэрол может проверить любую подпись независимо от другой .