Компьютерная безопасность. Криптографические методы защиты - Петров А.А.
ISBN 5-89818-064-8
Скачать (прямая ссылка):
5. Участник А посылает участнику В соответствующие маскирующие множители.
Специфические криптографические протоколы
165
6. Участник В открывает (то есть удаляет маскирующий множитель) п-1 документ и убеждается в том, что он корректен.
7. Участник В подписывает оставшийся документ и посылает его участнику А.
8. Теперь участник А удаляет маскирующий множитель и получает подписанный документ.
Этот протокол надежно защищен от мошенничества со стороны участника А. Теперь он должен точно угадать, какой документ участник В не будет проверять.
Существует прием, который уменьшает вероятность противоправного деяния со стороны участника А. На четвертом этапе участник В случайным образом выбирает п/2. документов для проверки. На пятом - участник А присылает ему соответствующие маскирующие множители. На седьмом этапе участник В перемножает все непроверенные документы и подписывает получившийся мстадокумент. На восьмом - участник А удаляет все маскировочные множители. Подпись участника В будет правильной, только если подписано произведение п/2 идентичных документов. Чтобы смошенничать, участнику А нужно точно угадать, какое подмножество документов будет проверять участник В. Вероятность этого гораздо ниже, чем вероятность угадать единственный документ, который участник В не проверял.
Протоколы данного типа имеют большое практическое значение в связи с развитием идеи электронных денег.
2.4.7. Забывающая передача
В этом случае основная идея состоит в том, чтобы участник А после передачи некоторого секрета участнику В не знал, передавал ли он секрет или нет, но при этом участник В точно знал, получил он секрет или не получил. Данная задача может быть решена с помощью частичного раскрытия секретов и доверенного арбитра. Однако в ряде случаев возникает ситуация, в которой воспользоваться услугами доверенной стороны не представляется возможным, поэтому особый интерес вызывают протоколы забывающей передачи, не применяющие доверенную сторону. Приведем в качестве примера протокол, основанный на том факте, что знание двух различных квадратных корней по модулю п из одного числа позволяет разложить п:
1. Участник В выбирает случайное число, вычисляет значение x2mod п и посылает его участнику А.
166
Аспекты создания и применения криптографических протоколов
2. Участник А, зная разложение п, вычисляет четыре квадратных корня из х2 и сообщает один из них участнику В.
3. Участник В проверяет, будет ли полученное значение сравнимо с ±х по модулю п. Если да, то участник В не получает новой информации. В противном случае участник В имеет два различных квадратных корня из одного числа по mod п и, следовательно, может разложить п.
При этом у участника А нет способа узнать, какой из этих случаев имеет место, и вероятность для участника А выбрать правильное значение квадратного корня с точки зрения участника В равна 1 /2.
На практике никто не использует протокол рассеянной передачи, однако он является важным звеном при построении других протоколов.
2.4.8. Подбрасывание монеты по телефону
В некоторых случаях необходимо, чтобы участники, расположенные далеко друг от друга, создали случайную последовательность и при этом не обращались за помощью к третьей стороне. Если участников двое, то действие протокола, решающего поставленную задачу, будет равносильно подбрасыванию монеты по телефону. На практике задача решается посредством однонаправленных функций:
1. Участник А выбирает случайное число х. Он вычисляет у = f(x), где f(x) - однонаправленная функция.
2. Участник А посылает у участнику В.
3. Участник В предполагает, что х четно или нечетно, и отправляет свое предположение участнику А.
4. Если предположение участника В правильно, результатом броска является «орел», если неправильно - «решка». Участник А объявляет результат и посылает х участнику В.
5. Участник В проверяет, что у = f(x).
Безопасность этого протокола обеспечивается однонаправленной функцией. Если участник А сможет найти такие х и х', когда х - четно, а х' -нечетно и у = f(x) = f(x'), он каждый раз смолсет обманывать участника В. Кроме того, наименьший значащий бит f(x) должен быть некоррелирован с х. В противном случае участник В сможет обманывать участника А, по крайней мере изредка. Например, если f(x) в 75% случаев четна, у участника В будет преимущество. (Иногда наименьший значащий бит - не лучший выбор для использования в приложении, потому что его вычисление может оказаться слишком простым.)
Интересно отметить, что в протоколе участники А и В узнают о результате подбрасывания не одновременно. В протоколе есть момент, когда
Специфические криптографические протоколы
167
участник А уже знает, какой стороной упала монета, но не может изменить ситуацию. Он, однако, в состоянии скрыть на какое-то время результат. Этот прием называется броском монет в колодец. Представьте себе высохший колодец. Участник А стоит рядом с колодцем, а участник В немного подальше. Участник В бросает монету, и она падает на дно колодца. Участник А может теперь заглянуть в колодец и увидеть результат, но не имеет возможности спуститься и изменить его. Участник В не сможет увидеть монету, пока участник А не позволит ему подойти и заглянуть в колодец.
