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

Протокол связи

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

Если А - это имя Алисы, Hn - значение хэш-функции, для которого Алиса хочет зафиксировать время, а Tn-1 -предыдущая метка времени, то протокол имеет следующий вид :

(1)Алиса посылает Тренту Hn и А.

(2)Трент посылает Алисе обратно:

Tn=SK(n,A,Hn, Tn*In-1* Hn-1,Tn-1,Ln)

где состоит Ln - это информация о следующей хэшированной связи:

Ln =H(In-bHn-bTn-bLn-l)

SK указывает, что сообщение подписано открытым ключом Трента. Имя Алисы определяет ее как отпр а-вителя запроса. Параметр n указывает последовательность запросов. Это n-ая метка времени, которую создал Трент. Параметр Tn - это время. Дополнительно используется информация об идентификаторе, ор и-гинального значения хэш-функции, времени и хэшированной метка предыдущего документа, помеченного Трентом.

(3)Когда Трент помечает следующий документ, он посылает Алисе идентификатор отправителя этого док у-мента: In-1.

Если кто-то оспаривает метку времени Алисы, ей надо только связаться с отправителями предыдущего и следующего документов: In-1 н In+1. Если и их свидетельство под вопросом, можно обратиться к авторам документов In-1 н In+1 и т.д. Любой может показать, что его документ был помечен после одного документа и перед другим.

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

Распределенный протокол

Люди умирают, метки времени теряются. Между пометкой документа и его оспариванием может произойти многое, что помешает Алисе получить копию метки времени In-1. Эта проблема может быть частично снята вставкой меток времени предыдущих 10 человек в метку Алисы и последующей передаче Алисе имен следу ю-щих 10 человек. Так у Алисы появится гораздо больше возможностей найти людей, все еще хранящих свои метки времени.

Развивая эту идею, следующий протокол позволяет обойтись и без Трента:

(1)Используя в качестве входа Hn, Алиса генерирует последовательность случайных чисел с помощью кри п-тографически безопасного генератора случайных чисел.

V1, V2, Уз, ... vk

(2)Алиса рассматривает каждое из этих чисел как идентификатор , I, другого человека и посылает каждому из этих людей Hn.

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

обратно Алисе.

(4) Алиса собирает и хранит все подписи как метку времени.

Криптографически безопасный генератор случайных чисел , используемый на этапе (1), позволяет Алисе избежать преднамеренного выбора коррумпированных I в качестве свидетелей. Даже если она сделает простейшие изменения в своем документе, пытаясь создать набор коррумпированных I, ее шансы добиться этого пренебрежимо малы. Хэш-функция рандомизирует значения, и Алиса не может на них воздействовать .

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

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

Дальнейшая работа

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

Эти протоколы меток времени запатентованы [684, 685, 686]. Патенты принадлежат дочерней компании Bellcore, названной Surety Technologies, которая продает Систему цифрового нотариата, поддерживающую эти протоколы. В первой версии клиенты посылали запросы о "заверении" на центральный координирующий центр . Следуя методике Меркла по использованию хэш-функций для построения деревьев [1066], сервер строит дерево значений хэш-функции, листья которого представляют собой все запросы, полученные в течение данной секу н-ды, и посылает каждому автору запроса список значений хэш-функции, описывающий путь от его листа до ко р-ня. Клиентская часть программного обеспечения сохраняет этот список и может выдать "сертификат" Цифров ого нотариата для любого файла, который был сертифицирован . Последовательность корней этих деревьев обр а-зует "Запись универсального подтверждения" ("Universal Validation Record"), которая будет доступна в электронном виде во многих хранилищах (и также выпущена на CD-ROM). Клиентская часть также содержит фун к-цию "подтверждения", позволяющую пользователю проверить, был ли заверена именно текущая форма файла (запросив из хранилища корень соответствующего дерева и сравнив его со значением хэш-функции, соответс т-вующим образом рассчитанным для файла, и сертификатом ). За дальнейшей информацией обращайтесь в Surety Technologies, 1 Main St., Chatham, NJ, 07928; (201) 701-0600; Fax: (201) 701-0601.

4.2 Подсознательный канал

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

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

Простым подсознательным каналом может быть число слов в предложении. Нечетное число слов в предл о-жении может соответствовать "1", а четное число слов -"0". Так, пока вы читаете этот самый обычный абзац, я передал вам сообщение "110" . Проблематичность этого метода в том, что он является обычной стеганографией (см. раздел 1.2), ключ не используется и безопасность зависит от секретности алгоритма .

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

сообщения. В общем случае протокол выглядит примерно так:

(1)Алиса создает безобидное сообщение, все равно какое.

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

(3)Алиса посылает подписанное сообщение Бобу через Уолтера.

(4)Уолтер читает безобидное сообщение и проверяет подпись. Не обнаружив ничего подозрительного, он п е-редает подписанное сообщение Бобу.

(5)Боб проверяет подпись под безобидным сообщением, убеждаясь, что сообщение получено от Алисы.

(6)Боб игнорирует безобидное сообщение и, используя общий с Алисой секретный ключ, извлекает подсозн а-тельное сообщение.

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

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

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

Применения подсознательного канала

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

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

Подписи, свободные от подсознательного канала

Алиса и Боб обмениваются подписанными сообщениями, обговаривая сроки контракта. Они используют протокол цифровой подписи. Однако, эти переговоры на самом деле маскируют шпионскую деятельность Ал и-сы и Боба. Используя алгоритм цифровой подписи, они не волнуются о подписываемых ими сообщениях. Для обмена секретной информацией они используют подсознательный канал в подписях под документами . Контрразведка, однако, не знает, что переговоры о контракте и используемые подписанные сообщения являются тол ь-ко прикрытием. Для противодействия подобной схеме были разработаны схемы подписи, свободной от подсо з-нательного канала. Используемые в этих схемах цифровые подписи невозможно изменить для организации подсознательного канала. Подробности см. в [480, 481].

4.3 Неотрицаемые цифровые подписи

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