документа. После 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)Трент отправляет подписанное значение хэш-функции вместе с меткой времени Алисе.

Это решает все проблемы, кроме последней. Алисе больше не нужно беспокоиться о раскрытии содержания