4.4 Подписи уполномоченного свидетеля

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

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

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

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

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

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

4.5 Подписи по доверенности

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

Решением этого являются подписи по доверенности [1001]. Алиса передает Бобу полномочия так, чтобы имели место следующие свойства:

- Различимость. Кто угодно может отличить подписи по доверенности от обычных подписей.

- Неподдельность. Только сам подписывающий и назначенный им подписывающий по доверенности м о-жет создать правильную подпись по доверенности.

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

- Подтверждаемость. По подписи по доверенности контролер должен убедиться в согласии первон а-чального подписывающего с подписанным сообщением.

- Идентифицируемость. Первоначальный подписывающий может определить личность подписывающ его по доверенности по подписи по доверенности.

- Неотрицаемость. Подписывающий по доверенности не может снять им подпись по доверенности, п о-лученную пользователем

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

4.6 Групповые подписи

Эта проблема была введена Дэвидом Чаумом ( David Chaum) в [330]:

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

Решение этой проблемы называется групповой подписью. Групповые подписи обладают следующими сво й-ствами:

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

- Получатель подписи может убедиться, что это - правильная подпись группы.

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

Групповые подписи с надежным посредником

Следующий протокол использует заслуживающего посредника:

(1) Трент создает большую кучу пар открытый ключ/закрытый ключ и выдает каждому члену группы инд и-видуальный список уникальных закрытых ключей. Одинаковых ключей в списках нет. (Если в группе n членов, и каждый из них получает m пар ключей, то общее число пар ключей составит n*m.)

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

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

(4) Когда кто-то хочет убедиться, что подпись принадлежит члену данной группы, он перебирает главный список в поисках подходящего открытого ключа и проверяет подпись.

(5) В случае споров обращаются к Тренту, который знает, какие ключи использует каждый член группы.

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

Чаум [330] перечислил ряд других протоколов, в некоторых из них Трент не может подделать подписи, а в других от и не нужен вовсе. Еще один протокол [348] не только прячет личность подписывающего, но и позв о-ляет добавлять новых членов в группу. И еще один протокол можно найти в [1230].

4.7 Подписи с обнаружением подделки

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

Подписи с обнаружением подделки, введенные Биржитом Пфицманом (Birgit Pfitzmann) и Майклом уэйднером (Michael Waidner) [1240] предотвращают подобное мошенничество. Если после грубого взлома Ева подделывает подписи Алисы, Алиса сможет доказать подлог . Если Алиса подпишет документ, а потом объявит свою подпись подложной, правда может быть доказана судом .

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

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

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

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

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

Дополнительную теорию и применения подписей с обнаружением подделки можно найти в [1239, 1241, 730, 731].

4.8 Вычисления с зашифрованными данными

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

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

4.9 Вручение битов

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

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

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

Боб: "Подберите-ка для меня пяток акций. Если на них удастся заработать, я передам свой бизнес вам."

Алиса: "Если я подберу пять акций для вас, вы сможете вложить в них деньги, не заплатив мне. Почему бы мне не показать вам пять акций, которые я подобрал в прошлом мес яце?"

Боб: "Откуда я знаю, что вы не подменили результаты вашего выбора, узнав настоящие. Если вы сообщите мне о своем выборе сейчас, я буду уверен, что вы не подмените результат. Я не буду вкладывать деньги в эти акции, пока я не оплачу ваши услуги. Поверьте мне."

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

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

Вручение битов с помощью симметричной криптографии

Этот протокол вручения битов использует симметричную криптографию :

(1) Боб генерирует строку случайных битов, R, и пос1лает ее Алисе.

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

EK(,R,b)

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

Когда для Алисы придет время раскрыть свой бит, протокол продолжается :

(3) Алиса передает Бобу ключ.