Отправитель и получатель. Сообщения и шифрование 7 глава

Несмотря на эту критику БАН-логика достигла определенных успехов. Ей удалось обнаружить "дыры" в нескольких протоколах, включая Needham-Schroeder и раннюю черновую версию протокола CCITT X.509 [303]. Она обнаружила избыточность во многих протоколах, включая Yahalom, Needham-Schroeder и Kerberos. Во многих опубликованных работах БАН-логика используется для заявления претензии о безопасности описываемых протоколов [40, 1162, 73].

Были опубликованы и другие логические системы, некоторые из них разрабатывались как расширения БАН-логики [645, 586, 1556, 828], а другие основывались на БАН-логике для исправления ощутимых слабостей [1488, 1002]. Из них наиболее успешной оказалась CNY [645], хотя у нее есть ряд изъянов [40]. В [292,474] к БАН-логике с переменным успехом были добавлены вероятностные доверия. Другие формальные логики описаны в [156, 798,288]. [1514] пытается объединить черты нескольких логик. А в [1124, 1511] представлены логики, в которых доверия изменяются со временем.

Четвертый подход к анализу криптографических протоколов предлагает моделировать протокол как алгебраическую систему, выразить состояние знания участников о протоколе и затем проанализировать достижимость определенных состояний. Этот подход пока не привлек столько внимания, как формальная логика, но состояние дел меняется. Он впервые был использован Майклом Мерриттом [1076], который показал, что для анализа криптографических протоколов можно использовать алгебраическую модель. Другие подходы рассмотрены в [473, 1508, 1530, 1531, 1532, 1510, 1612].

Анализатор протоколов Исследовательской лаборатория ВМС (Navy Research Laboratory, NRL), возможно, является наиболее успешным применением этих методов [1512, 823, 1046, 1513]. Он был использован для поиска как новых, так и известных "дыр" во множестве протоколов [1044, 1045, 1047]. Анализатор протоколов определяет следующие действия:

— Принять (Боб, Алиса, M, N). (Боб принимает сообщение M как пришедшее от Алисы в течение локального раунда Боба N.)

— Узнать (Ева, M). (Ева узнает M.)

— Послать (Алиса, Боб, Q, M). (Алиса посылает M Бобу в ответ на запрос, Q.)

— Запросить (Боб, Алиса, Q, N). (Боб посылает Q Алисе в течение локального раунда Боба N.)

Используя эти действия, можно задать требования. Например:

— Если Боб принял сообщение M от Алисы в какой-то прошедший момент времени, то Ева не знает M в какой-то прошедший момент времени.

— Если Боб принял сообщение M от Алисы в течение локального раунда Боба N, то Алиса послала M Бобу в ответ на запрос Боба в локальном раунде Боба N.

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

Хотя формальные методы в основном применяются к уже существующим протоколам, сегодня есть тенденция использовать их и при проектировании протоколов. Ряд предварительных шагов в этом направлении сделан в [711]. Это же пытается сделать и анализатор протоколов NRL [1512, 222, 1513].

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

3.5 Криптография с несколькими открытыми ключами

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

Эта концепция была обобщены Конном Бойдом (Conn Boyd) [217]. Представьте себе вариант криптографии с открытыми ключами, использующий три ключа: K_A, K_Bи K_C, распределение которых показано в Табл. -2.

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

Табл. -2.
Распределение ключей в трехключевой системе.

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

Широковещательная передача сообщения

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

Криптография с несколькими ключами позволяет решить эту задачу намного проще. Мы будем использовать трех агентов: Алису, Боба и Кэрол. Вы выдадите Алисе ключ K_A и K_B, Бобу - K_B и K_С, Кэрол - K_С и K_A. Теперь вы сможете говорить с любым нужным подмножеством агентов. Если вы хотите, чтобы сообщение могла прочитать только Алиса, зашифруйте его ключом K_С. Когда Алиса получит сообщение, она расшифрует его, последовательно используя ключи K_A и K_B.Если вы хотите послать сообщение только Бобу, зашифруйте его ключом K_A, а сообщение для Кэрол - ключом K_B. Если вы хотите, чтобы посланное сообщение могли прочитатьАлиса и Боб, зашифруйте его ключами K_A и K_С.

Для трех агентов это не слишком впечатляет, но для 100 преимущество достаточно ощутимо. Индивидуальные сообщения означают использование отдельного ключа для каждого агента (всего 100 ключей) и каждого сообщения. Передача сообщений всем возможным подмножествам означает использование 2¹⁰⁰-2 различных ключей (исключены случаи сообщения всем агентам и никому из них). Для схемы, использующий криптографию с несколькими открытыми ключами, нужно только одно шифрованное сообщение и сто различных ключей. Недостатком этой схемы является то, что вам также придется широковещательно передавать, какое подмножество агентов может читать сообщение, иначе каждому их них придется перебирать все возможные комбинации ключей в поисках подходящей. Даже только перечисление имен получателей может быть весьма внушительным. Кроме того, каждому агенту придется хранить немаленький объем информации о ключах, по крайней мере при прямолинейной реализации этой схемы.

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

Табл. -3.
Шифрование сообщения в трехключевой системе.

3.6 Разделение секрета

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

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

По простейшей схеме сообщение делится между двумя людьми. Вот протокол, используя который Трент делит сообщение между Алисой и Бобом:

(1) Трент генерирует строку случайных битов, R, такой же длины, что и сообщение, M.

(2) Трент выполняет "исключающее или" (XOR) над M и R, создавая S.

R Å M = S

(1) Трент передает Алисе R, а Бобу - S.

Чтобы получить сообщение, Алисе и Бобу нужно выполнить единственное действие:

(4) Алиса и Боб выполняют операцию над имеющимися у них частями, восстанавливая сообщение.

R Å S = M

Этот метод при правильном выполнении абсолютно безопасен. Каждая часть в отдельности абсолютно бессмысленна. Что существенно, Трент шифрует сообщение одноразовым блокнотом и дает шифротекст одному человеку, а блокнот - другому. Одноразовые блокноты, обладающие абсолютной безопасностью, обсуждаются в разделе 1.5. Никакие вычислительные средства не смогут восстановить сообщение только по одной его части.

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

(1) Трент генерирует три строки случайных битов, R, S и T, такой же длины, что и сообщение, M.

(2) Трент выполняет "исключающее или" (XOR) над M и созданными тремя строками, создавая U.

M Å R Å S Å T = U

(1) Трент передает Алисе R, Бобу - S, Кэрол - T, а Дэйву - U.

Вместе Алиса, Боб, Кэрол и Дэйв могут восстановить сообщение:

(4) Алиса, Боб, Кэрол и Дэйв собираются вместе и вычисляют:

R Å S Å T Å U = M

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

Однако одна проблема у этого протокола существует. Если любая из частей будет потеряна, а Трента не будет поблизости, пропадет и все сообщение. Если Кэрол, обладая частью рецепта соуса, перейдет работать к конкуренту, оставив свою часть секрета у себя, значит, остальным не повезло. Она не сможет восстановить рецепт, но не смогут, собравшись, и Алиса, Боб и Дэйв. Ее часть также критична для восстановления сообщения, как и любая другая. Все, что известно Алисе, Бобу и Дэйву - это длина сообщения, и ничего больше. Это истинно, так как у R, S, T, U и M одинаковая длина, следовательно, каждому из участников известна длина M. Помните, сообщение M делится не в обычном смысле этого слова, а подвергается операции XOR со случайными величинами.

3.7 Совместное использование секрета

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

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

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

Более сложная схема совместного использования, называемая пороговой схемой, может решить и эти задачи, и более сложные - математически. На ее простейшем уровне вы можете взять любое сообщение (секретный рецепт, коды запуска, ваш список для прачечной и т.п.) и разделить его на n частей, называемых тенями или долями, так, что по любым m из них можно восстановить сообщение. Более точно, это называется (m,n)‑пороговой схемой.

Используя (3,4)-пороговую схему, Трент может разделить свой секретный рецепт между Алисой, Бобом, Кэрол и Дэйвом так, что любые трое из них могут сложить свои тени вместе и восстановить сообщение. Если Кэрол в отпуске, то Алиса, Боб и Дэйв смогут восстановить сообщение. Если Боб попал под автобус, то сообщение смогут восстановить Алиса, Кэрол и Дэйв. Но если Боб попал под автобус, а Кэрол в отпуске, то Алиса и Дэйв самостоятельно не смогут восстановить сообщение.

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

Эта идея была независимо выдвинута Ади Шамиром [1414] и Джорджем Блэкли (George Blakley) [182] и интенсивно была изучена Гусом Симмонсом (Gus Simmons) [1466]. Множество различных алгоритмов обсуждается в разделе 23.2.

Совместное использование с мошенниками

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

Сценарий 2: Полковники Алиса и Боб сидят в бункере вместе с Мэллори. Мэллори ложно выдает себя за полковника. От президента приходит то же самое сообщение и все открывают свои тени. "Ха-ха-ха!" кричит Мэллори. "Я подделал это сообщение президента. Теперь я знаю обе ваших доли." Он убегает вверх по лестнице и исчезает прежде, чем его успеют поймать.

Сценарий 3: Полковники Алиса, Боб и Кэрол сидят в бункере вместе с Мэллори, который снова замаскировался. (Помните, у Мэллори нет правильной тени.) От президента приходит то же самое сообщение и все открывают свои тени. Мэллори открывает свою тень, только услышав все остальные. Так как для восстановления секрета требуется только три тени, он может быстро создать правильную тень и открыть ее. Итак, он не только заполучил секрет, но и никто не догадался, что он не является частью этой системы. Некоторые протоколы, которые позволяют бороться с подобными мошенниками, рассматриваются в разделе 23.2.

Совместное использование секрета без Трента

Банк хочет, чтобы его подвал могли открыть трое из пяти офицеров, введя свои ключи. Это выглядит как типичная (3,5)-пороговая схема, но с одной тонкостью. Никто не знает секрета целиком. Трента, которые делит секрет на пять частей, нет. Существуют протоколы, используя которые пять офицеров могут создать секрет и поделить его на части так, что никто из офицеров не узнает секрета, пока он не будет восстановлен. В этой книге я не рассматриваю эти протоколы, подробности см. в [756].

Совместное использование секрета без раскрытия долей

У этих схем есть одна проблема. Когда участники протокола собираются, чтобы восстановить секрет, они открывают свои части. Но раскрытие секрета не всегда желательно. Если разделяемый секрет является закрытым ключом (например, к цифровой подписи), то каждый из n участников может выполнить частичную подпись документа. После n-ой частичной подписи документ оказывается подписан совместно используемым закрытым ключом, а ни один из участников не может узнать содержания части, используемой другим участником. Смысл в том, что вы можете повторно использовать секрет, и для работы с ним вам не понадобится надежный посредник. Дальнейшее развитие эта идея получила в работах Иво Десмедта (Yvo Desmedt) и Йера Френкеля (Yair Frankel) [483, 484].

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

Трент передает Алисе, Бобу, Кэрол и Дэйву часть секрета (или, по крайней мере, заявляет, что он это делает). Единственный способ убедиться, что их части правильны - это попытаться восстановить секрет. Может быть, Трент послал Бобу поддельную часть, или часть Боба случайно испортилась при передаче по линиям связи. Подтверждаемое совместное использование секрета позволяет каждому из участников лично убедиться, что их часть правильна, без необходимости восстанавливать секрет [558, 1235].

Схемы совместного использования секрета с мерами предохранения

Секрет делится среди 50 человек так, чтобы любые 10 могли собраться вместе и восстановить секрет. Это нетрудно. Но, можем ли мы реализовать ту же схему совместного использования секрета, добавив требование, чтобы 20 человек могли собраться вместе и помешать остальным, независимо от их числа, восстановить секрет? Оказывается, что да [153].

Математика достаточно сложна, но основная идея в том, что каждый получает две части: часть "да" и часть "нет". Когда приходит время восстановить секрет, люди предоставляют одну из своих частей. Какую конкретно зависит от того, хотят ли они, чтобы секрет был раскрыт. Если предоставлено m или больше долей "да" и меньше чем n долей "нет", то секрет может быть восстановлен. В противном случае, это невозможно.

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

Совместное использование секрета с вычеркиванием из списка

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

3.8 Криптографическая защита баз данных

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

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

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

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

В [550] авторы используют эту систему для защиты словаря из 6000 испанских слов. Они сообщают о том, что потеря производительности, вызванная шифрованием, минимальна. В более сложной схеме [549] используется поиск по нескольким индексам, но идея остается той же. Основная проблема, связанная с этой системой, состоит в том, что вы не сможете найти человека, не зная, как пишется его фамилия. Можно попробовать несколько вариантов, пока не будет найден правильный, но неудобно перебирать всех, чьи фамилии начинаются на "Sch" при поиске "Schneier."

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

4 Промежуточные протоколы

4.1 Службы меток времени

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

В цифровом мире все гораздо сложнее. Нет способов обнаружить признаки подделки электронного документа. Его можно бесконечно копировать и изменять, не оставляя никаких следов. Несложно и изменить время создания компьютерного файла. Никто не может взглянуть на документ и с полной уверенностью сказать: "Да, этот документ был создан раньше 4 ноября 1952 года"

Этой проблемой задались Стюарт Хабер (Stuart Haber) и В. Скотт Сторнетта (W. Scott Stornetta) из Bellcore [682, 683, 92]. Им потребовался протокол цифровых меток времени со следующими свойствами:

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

— Должно быть невозможно тайно изменить ни единого бита документа.

— Должно быть невозможно задать для документа метку времени, отличного от текущего.

Решение с посредником

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

(1) Алиса передает копию документа Тренту.

(2) Трент записывает время и дату получения документа, оставляя у себя копию для безопасного хранения.

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

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

Во вторых, самой базе данных придется быть очень большой. Велики будут требования и к пропускной способности линии связи.

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

И в четвертых, может оказаться невозможным найти такого честного Трента для ведения службы меток времени. Может быть, Алиса использует метку времени Боба. Ничто не остановит Алису и Боба от сговора и пометки документа тем временем, которое им нужно.

Улучшенное решение с посредником

Большинство этих проблем легко снимаются при использовании однонаправленной хэш-функции и цифровых подписей:

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

(2) Алиса передает это значение Тренту.

(3) Трент добавляет время и дату получения этого значения и затем подписывает результат цифровой подписью.

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

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

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

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

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

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

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

T_n=S_K(n,A,H_n,T_n,I_n-1,H_n-1,T_n-1,L_n)

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

L_n =H(I_n-1,H_n-1,T_n-1,L_n-1)

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

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

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