Анонимные совместные вычисления

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

Атака методом сведения к середине

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

1. Антон посылает Борису свой открытый ключ. Зиновий перехватывает этот ключ, а вместо него отсылает Борису свой собственный открытый ключ.

2. Борис посылает Антону свой открытый ключ. Зиновий перехватывает лог ключ, а вместо него отсылает Антону свой собственный открытый ключ.

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

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

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

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

Аутентификация

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

Аутентификация при помощи криптосистем с открытым ключом

Ни "изюминки", ни периодически сменяемый пароль не гарантируют защиту от злонамеренных действий Петра, перехватывающего все сообщения Антона, которые тот пересылает по линии связи, соединяющей его с сервером. Решить эту проблему помогает применение криптографии с открытым ключом.

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

1. Сервер генерирует случайную битовую строку и посылает ее Антону.

2. Антон шифрует эту строку при помощи своего тайного ключа и отсылает обратно на сервер.

3. На сервере производится расшифрование сообщения, пришедшего от Антона, с помощью его открытого ключа.

4. Если полученный в результате открытый текст идентичен случайной битовой строке, ранее посланной Антону, последний получает доступ к серверу.

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

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

1. Антон производит некоторые специальные вычисления на основе предварительно сгенерированной им случайной битовой последовательности и своего тайного ключа. Затем он отсылает вычисленные им значения на сервер.

2. Сервер посылает Антону случайную битовую последовательность, отличную от той, которая была задействована Антоном на шаге 1.

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

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

5. Если проверка дает положительный результат, Антону разрешается доступ к серверу.

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

Аутентификация при помощи однонаправленных функций

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

1. Антон посылает на сервер свой пароль.

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

3. Сервер сравнивает вычисленное хэш-значение с эталоном, который хранится в его памяти, и делает вывод о правильности пароля Антона.

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

Блокировочный протокол

Блокировочный протокол, изобретенный американскими криптологами Р. Райвестом и А. Шамиром, позволяет существенно осложнить жизнь Зиновию и ему подобным личностям:

1. Антон посылает Борису свой открытый ключ.

2. Борис посылает Антону свой открытый ключ.

3. Антон зашифровывает свое сообщение и отсылает половину этого сообщения Борису.

4. Борис зашифровывает свое сообщение и отсылает половину этого сообщения Антону.

5. Антон отсылает вторую половину своего сообщения Борису.

6. Борис расшифровывает сообщение Антона с помощью своего тайного ключа. Борис отсылает вторую половину своего сообщения Антону.

7. Антон расшифровывает сообщение Бориса с помощью своего тайного ключа.

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

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

На шаге 1 блокировочного протокола Зиновий по-прежнему может подставить свой собственный открытый ключ вместо открытого ключа Антона. Однако теперь на шаге 3 Зиновий будет не в состоянии дешифровать перехваченное сообщение Антона и зашифровать его заново при помощи открытого ключа Бориса. Зиновию непременно придется придумать свое собственное сообщение (случайный битовый вектор или хэш-значение) и послан, его половину Борису. То же самое касается и сообщения Бориса Антону. которое Зиновий перехватит на шаге 4 блокировочного протокола. А после того как Зиновий получит в свое распоряжение вторые половины подлинных сообщений Антона и Бориса, будет уже слишком поздно изменить придуманные им ранее фальшивые сообщения, которые он уже отослал от их имени. Следовательно, Зиновию придется дать волю своей фантазии и продолжить вести всю переписку от имени Антона и Бориса.

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

Бросание монеты

Для разрешения неожиданно возникшего спорного вопроса Антон и Борис решают бросить монету. Однако и у того, и у другого при себе не оказалось ни одной. Тогда они решают "бросить" монету в уме: сначала Антон загадает, что выпадет — "орел" или "решка", а потом Борис подумает и объявит. какой стороной упала "брошенная" им монета. Спрашивается: могут ли Антон и Борис сделать это так, чтобы полностью быть уверенными в том. что никто из них не смошенничал?

Могут, если воспользуются криптографическим протоколом, который заставит их действовать таким образом, что:

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

Антон не сможет изменить результат бросания монеты после того, как услышит, на какую сторону монеты сделал свою ставку Борис;

Борис не узнает, что выпало — "орел" или "решка", до тех пор. пока не примет окончательное решение и не сообщит о нем Антону.

Бросание монеты с помощью криптосистемы с открытым ключом

В этом случае от алгоритмов шифрования (Е) и расшифрования (D) требуется, чтобы они были коммутативны, т. е.:

D K1 (E K2 (E K1 (M) ) ) ) = Е К2 (М),

где К 1 и К 2 — криптографические ключи, Р — открытый текст сообщения. Для симметричных криптоалгоритмов в общем случае это условие не выполняется, однако существуют алгоритмы шифрования с открытым ключом, для которых оно верно. Последние могут быть использованы в протоколе бросания монеты:

1. Антон и Борис генерируют каждый для себя по паре ключей, состоящей из открытого и тайного ключа.

2. Антон генерирует две случайные битовые строки Р 1 и Р 2, одна из которых означает, что при бросании монеты выпал "орел", а другая — что получилась "решка".

3. При помощи своего открытого ключа Антон шифрует сначала Р 1 , а потом Р 2 , и отсылает оба полученных в результате шифрсообщения (E A (P 1 ) и E A (P 2 )) Борису.

4. Борис выбирает одно из присланных ему Антоном шифрсообшений (для этой цели Борис может воспользоваться, например, известной считалкой "Эне, бене, раба, квинтер, минтер, жаба" или сходить за советом к астрологу). Борис шифрует выбранное шифрсообщение с помощью своего открытого ключа и отсылает результат (E Б (E A (P)) , где Р — это либо Р 1 , либо Р 2 ) Антону.

5. Антон расшифровывает пришедшее от Бориса сообщение на своем тайном ключе и посылает то, что у него получилось ( D Б (E Б (P)) = E Б (P) обратно Борису.

6. Борис расшифровывает это сообщение Антона ( D Б (E Б (P)) = P) и узнает, какой стороной упала монета. Затем Борис шлет Р Антону.

7. Антон проверяет, действительно ли Р — это одна из тех двух случайных битовых строк, которые он сгенерирована на шаге 2.

8. Чтобы окончательно убедиться в честности друг друга, Антон и Борис обмениваются парами ключей, которые они сгенерировали на шаге 1.

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

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

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

Бросание монеты с помощью однонаправленной функции

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

1. Антон выбирает случайное число х и вычисляет значение y = f(x).

2. Антон посылает у Борису.

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

4. Антон информирует Бориса о том, какое число х он выбрал.

5. Борис проверяет, действительно ли f(x) = y, а также узнает, была ли верна его догадка.

Здесь все зависит от свойств однонаправленной функции f. Если Антон вдруг сможет найти два числа х и х' такие, что х является четным, а х' — нечетным, и при этом y = f(x) = f(x'), то Борис всегда будет в проигрыше. Необходимо также, чтобы наименее значимый бит f(x) не зависел от х. Например, если f(x) будет четным в 90 процентах всех случаев, когда х является четным, Антон будет брать верх над Борисом почти всегда.

Бросание монеты с помощью предсказания бита

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

1. Антон делает предсказание битового значения в соответствии с одной из схем, описанных в разделе "Предсказание бита",

2. Борис пытается догадаться, какое значение предсказал Антон, и информирует о своей догадке Антона.

3. Антон сообщает Борису предсказанное значение. Борис выигрывает, если его догадка была правильной.

Что такое криптографический протокол

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

Протоколы имеют и другие отличительные черты:

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

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

Цифровая подпись

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

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

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

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

Цифровая подпись и шифрование

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

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

1. Антон подписывает сообщение Р при помощи своего тайного ключа К А:

S K A (P)

2. Антон шифрует подписанное сообщение, используя открытый ключ Бориса К Б , и посылает его Борису

Е K Б ( S K A (P) )

3. Борис расшифровывает сообщение Антона с помощью своего тайного ключа К Б :

D K Б ( Е K Б ( S K A (P) ) ) = S K A (P)

4. С помощью открытого ключа Антона К А, Борис проверяет подпись Антона и получает открытый текст его сообщения:

V K A (S K A (P) ) = Р

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

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

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

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

Е K Б ( S K A (P) )

2. Борис расшифровывает сообщение Антона на своем тайном ключе, удостоверяется в подлинности подписи Антона с помощью его открытого ключа и восстанавливает открытый текст сообщения:

S K A (D K Б (Е K Б ( S K A (P) ) ) ) = P

3. Борис подписывает сообщение Антона с использованием своего тайного ключа, шифрует это сообщение вместе со своей подписью на открытом ключе Антона и отсылает обратно:

Е K A ( S K Б (P) )

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

К сожалению, если для шифрования и проверки цифровой подписи применяется одинаковый криптографический алгоритм (т. е., V K = E К и S К = D К ), Зиновий, являясь законным пользователем сети связи, при определенных условиях сможет читать шифрованную переписку Антона. Для этого, перехватив сообщение Антона Е K Б ( S K A (P) ) , Зиновий шлет его от своего имени Борису. Борис после расшифрования и проверки цифровой подписи Зиновия получит:

E K З (D K Б (Е K Б ( D K A (P) ) ) ) = E K З (D K А (P) )

В соответствии с протоколом Борис должен отправить Зиновию подтверждение правильности приема пришедшего ему сообщения:

В результате Зиновию останется только преобразовать сообщение, присланное ему Борисом, при помощи своего тайного ключа и известных открытых ключей Антона и Бориса — и вот он, заветный открытый текст Р сообщения, отправленного Антоном!

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

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

Цифровая подпись по доверенности

Кроме проверки своей цифровой подписи, Антон может поручить другому лицу ставить эту подпись вместо себя. В жизни случается всякое, и Антон не застрахован от несчастного случая. Или, например, попытка продать текстовый редактор "УниЛекс'97" якутским оленеводам может потребовать от Антона посещения районов, в которых компьютерные сети — все еще большая редкость. Каким же образом Антон может передать Борису право подписывать все документы вместо себя, не предоставляя ему доступ к своему тайному ключу?

Для этого Антону следует воспользоваться цифровой подписью по доверенности. Тогда в случае необходимости Антон сможет передать Борису доверенность на право ставить свою цифровую подпись. Для этого поставленная по доверенности цифровая подпись должна обеспечивать:

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

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

Цифровая подпись с дополнительной защитой

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

Чтобы противостоять злодейским планам Зиновия, Антону следует воспользоваться цифровой подписью с дополнительной защитой. Тогда, если Зиновии вскроет тайный ключ Антона с помощью тотального перебора и подделает его подпись, Антон сможет разоблачить подделку. Идея, которая лежит в основе цифровой подписи с дополнительной зашитой, достаточно проста. Каждому открытому ключу ставится в соответствие не один тайный ключ, а некоторое множество тайных ключей. Любой из них позволяет поставить под документом цифровую подпись, но она будет отлична от подписей, изготовленных при помощи других ключей. Антон знает только один ключ, остальные ему неизвестны.

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

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

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

Цифровая подпись с назначенным конфирмантом

Если дела у компании "ПрограммКомп" резко пойдут в гору и "УниЛекс'97" станут покупать нарасхват, то Антону вскоре придется заниматься одной только проверкой подлинности цифровых подписей на проданных копиях вместо того, чтобы готовить к выпуску новую, более универсальную, версию своего текстового редактора. Поэтому Антон вряд ли откажется, если ему Борис предложит стать его конфирмантом, т. е. взять на себя верификацию подписей Антона. Для этого Антон просто будет ставить под копиями "УниЛекса'97" не обыкновенную цифровую подпись, а цифровую подпись с назначенным конфирмантом.

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

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

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

Депонирование ключей

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

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

В самом общем случае Стандарт шифрования данных с депонированием ключа реализуется с помощью следующего криптографического протокола:

1. Антон генерирует пару ключей, состоящую из открытого и тайного ключа, и делит их на n частей.

2. Антон посылает каждую часть тайного ключа и соответствующую ей часть открытого ключа отдельному доверенному лицу.

3. Каждое доверенное лицо проверяет полученные от Антона части открытого и тайного ключа и помещает их на хранение в надежное место.

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

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

Депонирование ключей и политика

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

Правительственные агентства США, особенно АНБ, убеждали законодателей в том, что если использование стойких криптосистем станет повсеместным, это даст возможность преступникам и враждебно настроенным странам мешать расследованию их противоправной деятельности. Сторонники депонирования ключей резонно напоминали о том, что успехи криптоаналитических спецслужб англо-американских союзников в значительной мере способствовали достижению победы во второй мировой войне. Важная роль. которую криптоанализ играл в обеспечении безопасности страны, была впоследствии подтверждена и американским послевоенным законодательством. установившим контроль над экспортом шифраторов по тем же правилам, которые действовали в отношении поставок военного снаряжения. Примеру США последовали все государства, производящие коммерческие программы шифрования, причем некоторые из них (Израиль, Россия и Франция) также стали осуществлять контроль над импортом шифровальных средств и их использованием внутри страны.

Кроме того, в ходе "холодной" войны АНБ неуклонно повышало свой шпионский потенциал. Соответственно росло его влияние на политическую жизнь страны. К началу 90-х годов АНБ превратилось в монстра, внушавшего американским политикам и законодателям благоговейный страх. Для них мнение руководства АНБ было намного весомее возражений его оппонентов. А директор АНБ и его помощники неустанно твердили о том. что недоверие к Стандарту шифрования данных с депонированием ключей вызвано, главным образом, его незнанием. И в этом была доля правды, поскольку значительная часть проекта с самого начала хранилась в строгой тайне, включая сам алгоритм под условным названием Skipjack (Попрыгунчик), используемый для шифрования сообщений.

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

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

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

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

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

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

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

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

Дополнительная терминология

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

По этой причине в ходе дальнейшего изложения о процессах подписания документа и проверки подлинности подписи будет говориться без упоминания конкретных алгоритмов, которые используются для этих целей. Подписание документа Р при помощи тайного ключа К будет обозначаться S К (P), а проверка подлинности подписи с использованием соответствующего открытого ключа — V К (P).

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

Допустим, что требуется рассылать групповые шифрованные сообщения

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

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

Формальный анализ криптографических протоколов

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

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

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

Авторами третьего подхода являются американские криптологи М. Бэрроуз. М. Абади, Р. Нидхэм (М. Burrows, M. Abadi, R. Needham). Они разработали формальную логическую модель, названную по первым буквам их фамилий БАН-логикой (BAN-logic). Составить с ее помощью общее представление о надежности криптографического протокола нельзя. Однако основное преимущество БАН-логики перед другими подходами заключается в том, что она состоит из набора простых логических правил, которые легко применяются на практике и весьма полезны при обнаружении отдельных изъянов в анализируемых протоколах.

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

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

Гибридные криптосистемы

На практике криптосистемы с открытым ключом используются для шифрования не сообщений, а ключей. На это есть две основные причины:

Алгоритмы шифрования с открытым ключом в среднем работают в тысячи раз медленнее, чем алгоритмы с симметричным ключом. И хотя темпы роста компьютерной производительности очень высоки, требования к скорости шифрования растут не менее стремительно. Поэтому криптосистемы с открытым ключом вряд ли когда-нибудь смогут удовлетворить современные потребности в скорости шифрования. Алгоритмы шифрования с открытым ключом уязвимы по отношению к криптоаналитическим атакам со знанием открытого текста. Пусть С=Е(Р), где С обозначает шифртекст, Р — открытый текст, Е — функцию шифрования. Тогда, если Р принимает значения из некоторого конечного множества, состоящего из n открытых текстов, криптоаналитику достаточно зашифровать все эти тексты, используя известный ему открытый ключ, и сравнить результаты с С. Ключ таким способом ему вскрыть не удастся, однако открытый текст будет успешно определен.

Чем меньше количество ( n ) возможных открытых текстов, тем эффективнее будет атака на криптосистему с открытым ключом. Например, если криптоаналитику известно, что шифрованию подверглась сумма сделки, не превышающая 1 млн долл., он может перебрать все числа от 1 до 1 000 000.

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

1. Антон генерирует сеансовый ключ К и шифрует его с использованием открытого ключа В, принадлежащего Борису:

Е В (К)

2. Борис расшифровывает сообщение Антона при помощи своего тайного ключа и получает в результате сеансовый ключ К. сгенерированный Антоном:

K=D B (E B (K))

3. Антон и Борис обмениваются сообщениями, зашифрованными одним и тем же сеансовым ключом К.

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

Криптографические протоколы

Глава 7. Криптографические протоколы

Что такое криптографический протокол Цифровая подпись Цифровая подпись и шифрование Основные криптографические протоколы Аутентификация Формальный анализ криптографических протоколов Многоключевая криптография с открытым ключом Распределение ответственности Вспомогательные криптографические протоколы Неоспоримая цифровая подпись Цифровая подпись с назначенным конфирмантом Цифровая подпись по доверенности Групповые подписи Цифровая подпись с дополнительной защитой Предсказание бита Бросание монеты Специальные криптографические протоколы Неосознанная передача информации Анонимные совместные вычисления Депонирование ключей

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

Групповыми подписями называются цифровые подписи, которые обладают следующими свойствами:

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

Поставить групповую подпись под документом можно, например. мощи следующего протокола с арбитражем:

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

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

3. Чтобы подписать документ, член группы выбирает ключ из списка, предоставленного ему Дмитрием.

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

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

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

Игра в покер

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

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

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

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

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

1. Антон подвергает документ хэшированию при помощи однонаправленной хэш-функции.

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

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

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

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

Как найти себе подобного

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

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

Протокол выглядит так:

1. Используя однонаправленную функцию, Антон преобразует 7-значный идентификатор своего чудачества в другое 7-значное число.

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

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

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

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

Многоключевая криптография с открытым ключом

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

Имеется три ключа К А , К Б и К С , которые распределены между участниками процесса обмена сообщениями следующим образом:

Антон К А

Борис К Б

Владимир К В

Георгий К А и К Б

Денис К Б и К В

Евгений К В и К А

Если Антон зашифрует свое сообщение с помощью ключа К А, расшифровать его смогут либо Денис, либо Борис совместно с Владимиром, которые имеют в своем распоряжении К Б и К В . Сообщение, зашифрованное Борисом, сможет прочесть Евгений. Владимир может зашифровать сообщение, которое в состоянии прочесть Георгий. Сообщение, зашифрованное Георгием при помощи ключа К А , смогут прочесть Денис. Если Георгий воспользуется ключом кб, то его сообщение прочитает Евгений, а если применит кб и кб, то с этим сообщением сможет ознакомиться Владимир. Аналогичным образом может .зашифровать свое сообщение Денис, и тогда его прочтут либо Антон, либо Георгий, либо Евгений. Всевозможные сочетания ключей шифрования и расшифрования перечислены в табл. 7.2.

Множественная рассылка ключей и сообщений

Почему бы Антону не послать шифрованное сообщение сразу нескольким адресатам? Он может сделать это, например так:

1. Антон генерирует случайный сеансовый ключ Кис его помощью зашифровывает сообщение М, получая в результате Е К (М).

2. Антон извлекает открытые ключи Бориса, Владимира и Георгия из базы данных.

3. Антон шифрует К при помощи открытых ключей Бориса, Владимира и Георгия, получая в результате Е Б (К), Е в (К)и Е г (К).

4. Антон, посылает шифрованное сообщение Е к (М), а также многократно зашифрованный сеансовый ключ (E Б (K), Е в (К)и Е Г (К)) всем, кто пожелает их получить.

5. Только Борис, Владимир и Георгий смогут расшифровать сеансовый ключ К при помощи своих тайных ключей.

6. Только Борис, Владимир и Георгий смогут прочесть шифрованное сообщение Антона с помощью сеансового ключа К.

Неинтерактивные протоколы доказательства с нулевым разглашением конфиденциальной информации

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

1. Антон использует имеющуюся у него информацию и n сгенерированных случайных чисел, чтобы свести трудно решаемую задачу к n другим трудно решаемым задачам, изоморфным исходной задаче. Затем Антон решает эти n новых задач.

2. Антон задействует протокол предсказания бита для найденных на шаге 1 n решений.

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

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

5. Антон передает в общедоступную базу данных все обязательства, которые были получены им на шаге 2.

6. Борис, Владимир или любое другое заинтересованное лицо могут проверить правильность выполнения Антоном шагов 1—5.

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

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

В отличие от интерактивного протокола, здесь требуется большее количество итераций. Поскольку генерация случайных чисел возложена на Ангина. подбором этих чисел он может попытаться добиться, чтобы на выходе одно направленной функции получилась битовая последовательность нужно: и ему вида. Ведь даже если Антон не знает решения исходной трудно решаемой задачи, он всегда в состоянии выполнить требования пли пункта (а). или пункта (б) шага 4 протокола. Тогда Антон может попытается догадаться. на какой из этих пунктов падет выбор, и выполнить шаги 1—3 протокола. А если его догадка неверна, он повторит все сначала. Именно поэтому в неинтерактивных протоколах необходим больший запас прочности, чем в интерактивных. Рекомендуется выбирать n = 64 или даже n = 128.

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

Неосознанная передача информации

Предположим, что Борис безуспешно пытается разложить на простые множители 700-битовое число. При этом ему известно, что данное число является произведением семи 100-битовых множителей. На помощь Борису приходит Антон, который случайно знает один из множителей. Антон Предлагает Борису продать этот множитель за 1000 руб. — по 10 руб. за бит. Однако у Бориса имеются в наличии лишь 500 руб. Тогда Антон выражает желание отдать Борису 50 бит за половину цены. Борис сомневается, поскольку даже купив эти 50 бит, он все равно не сможет убедиться, что они действительно являются частью искомого множителя, пока не узнает все его биты целиком.

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

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

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

1. Антон генерирует две пары ключей, состоящих из открытого и тайного ключа, и отсылает оба открытых ключа Борису.

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

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

4. Антон шифрует два сообщения по DES-алгоритму, используя в качестве ключей обе битовые последовательности, которые были получены им на шаге 3, и отсылает результаты шифрования Борису.

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

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

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

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

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

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

Неоспоримая цифровая подпись

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

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

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

Математический аппарат, используемый для конструирования неоспоримой цифровой подписи, довольно сложен и громоздок, однако основная идея соответствующего протокола достаточно прозрачна:

1. Антон знакомит Бориса со своей цифровой подписью.

2. Борис генерирует случайное число и передает его в распоряжение Антона.

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

4. Борис подтверждает получение вычисленного Антоном значения.

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

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

В результате Борис может на законных основаниях приобрести копию "УниЛекса'97", сделать с нее пиратскую копию и перепродать Владимиру. Как только Владимир захочет проверить подлинность цифровой подписи под пиратской копией "УниЛекса'97", Борис обратится к Антону с просьбой произвести проверку подписи под купленной легально копией этого текстового редактора. Сгенерированное Владимиром случайное число Борис переадресует Антону, а поступивший от Антона ответ он перешлет Владимиру.

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

Неоспоримость

Вполне возможна ситуация, при которой Антон, подписав некоторый документ, впоследствии попытается ее оспорить — заявит о том, что подпись под документом поставил не он. Причиной может послужить, например. потеря Антоном своего тайного ключа в людном месте или намеренная его публикация Антоном в разделе частных объявлений популярной газеты. Эта ситуация называется отказ от обязательств.

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

1. Антон подписывает документ.

2. Антон генерирует заголовок, в который помещает свои личные данные. присоединяет этот заголовок к подписанному им документу, еще раз подписывает итоговый документ и посылает его Дмитрию.

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

4. Борис проверяет подпись Дмитрия, персональные данные Антона и его подпись.

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

Несколько подписей под одним документом

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

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

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

1. Антон подписывает хэш-значение документа.

2. Борис подписывает хэш-значение того же самого документа.

3. Борис отсылает свою подпись Антону.

4. Антон шлет документ вместе со своей подписью и подписью Бориса Владимиру.

5. Владимир проверяет подлинность подписей Антона и Бориса.

Обмен ключами для криптосистем с открытым ключом

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

1. Антон находит открытый ключ Бориса в справочнике, в базе данных или получает его от Дмитрия.

2. Антон генерирует случайный сеансовый ключ, шифрует его при помощи открытого ключа Бориса и отправляет ему в зашифрованном виде.

3. Борис расшифровывает сообщение Антона с использованием своего тайного ключа.

4. Антон и Борис обмениваются сообщениями, зашифрованными на одном и том же сеансовом ключе.

Обмен ключами для симметричных криптосистем

Предположим, что Антон и Борис, являющиеся пользователями компьютерной сети, получили секретные ключи от Дмитрия (доверенного липа, наделенного правами арбитра). Секретные ключи попали к Антону и Борису еще до начала сеанса связи, а злоумышленник Зиновий ровным счетом ничего не знает о том, какие это ключи. Тогда для обмена шифрованными сообщениями по компьютерной сети Антон и Борис могут воспользоваться следующим криптографическим протоколом:

1. Антон связывается с Дмитрием и запрашивает у него сеансовый ключ для связи с Борисом.

2. Дмитрий генерирует случайный сеансовый ключ и создает две шифрованных копии этого ключа — один раз Дмитрий шифрует сеансовый ключ с помощью секретного ключа Антона, второй — с помощью секретного ключа Бориса. Затем Дмитрий отсылает обе копии Антону.

3. Антон расшифровывает свою копию сеансового ключа.

4. Антон отправляет Борису его копию сеансового ключа.

5. Борис расшифровывает свою копию сеансового ключа.

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

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

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

Одновременная передача ключа и сообщения

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

1. Антон генерирует случайный сеансовый ключ Кис помощью него зашифровывает сообщение М, получая в результате Е К (М).

2. Антон извлекает открытый ключ Бориса В из базы данных.

3. Антон шифрует сеансовый ключ К при помощи В, получая в результате Е В (К) .

4. Антон посылает Борису Е к (М) и Е в (К).

5. Борис расшифровывает сеансовый ключ К с помощью своего тайного ключа.

6. Борис расшифровывает сообщение Антона на сеансовом ключе К.

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

Основные криптографические протоколы Обмен ключами

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

Отметка о времени подписания документа

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

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

Отметка о времени создания файла и арбитраж

Файл можно снабдить отметкой о времени его создания при помощи протокола, в котором принимает участие доверенное лицо (Дмитрий):

1. Антон передает копию своего документа Дмитрию.

2. Дмитрий фиксирует время получения копии документа, которую с этого момента хранит у себя, чтобы предъявить по первому требованию Антона.

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

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

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

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

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

1. Антон вычисляет хэш-значение для своего документа.

2. Антон передает вычисленное хэш-значение Дмитрию.

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

4. Дмитрий отсылает подписанное им хэш-значение с проставленной отметкой времени обратно Антону.

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

Отражение словарной атаки при помощи "изюминок"

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

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

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

"Изюма" понадобится много. Во многих версиях операционной системы UNIX используются "изюминки" длиной 12 бит. Этого явно недостаточно: существуют программы, которые при помогли словарной атаки позволяют за неделю вскрыть от 30 до 40% всех паролей, применяемых пользователями UNIX.

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

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

Параллельные доказательства с нулевым разглашением конфиденциальной информации

Обычный протокол доказательства с нулевым разглашением конфиденциальной информации требует, чтобы Антон и Борис последовательно повторили его шаги n раз. Можно попробовать выполнять действия, предусмотренные этим протоколом, одновременно:

2. Антон задействует протокол предсказания бита для найденных на шаге 1 n решений, чтобы впоследствии, если у Бориса возникнет необходимость ознакомиться с этими решениями, Борис мог бы достоверно убедиться, что предъявленные Антоном решения действительно были получены им на шаге 1.

3. Антон показывает n новых трудно решаемых задач Борису.

4. Для каждой из n новых трудно решаемых задач Борис просит Антона или доказать, что она изоморфна исходной трудно решаемой задаче или предоставить решение этой задачи, которое Антон должен был найти на шаге 1, и доказать, что оно действительно является ее решением.

5. Антон выполняет все просьбы Бориса.

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

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

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

Антон генерирует случайное число R и пересылает его серверу, который вычисляет, исходя из этого числа и однонаправленной функции f значения x 1 = f (R), x 2 =f (f (R)), x 3 = f (f (f(R))) и т.д. 101 раз. Первые 100 вычисленных значений x 1 , х 2 , . . , x 100 передаются Антону в качестве списка паролей, который он должен хранить в тайне. A x 101 запоминается на сервере.

Теперь, когда Антон захочет зарегистрироваться для работы на сервере, ему достаточно ввести свое имя и число х 100 . Сервер вычислит f(x 100 ) и сравнит его с х 101 . В случае совпадения Антону будет разрешен доступ к серверу, который затем заменит х 101 на х 100 . А Антон вычеркнет х 101 из своего списка паролей.

В следующий раз, когда Антон снова захочет получить доступ к серверу, он найдет в списке паролей следующее по порядку не зачеркнутое значение х j . Сервер вычислит f(x j ) и сравнит с запомненным X j+ 1 .

Злоумышленник Зиновий, взломавший сервер, все равно не сможет узнать очередной пароль Антона x j по хранимому на сервере значению x j+l, поскольку функция f является однонаправленной. По той же самой причине. даже если Зиновий перехватит x j , это позволит ему зарегистрироваться под именем Антона всего лишь один раз. А значения x 1 , x 2 , ... , х j -1 так и останутся для Зиновия тайной за семью печатями при условии, что Антон достаточно ответственно относится к хранению списка паролей, полученного им с сервера.

Подписание документов при помощи криптосистем с открытым ключом

Протокол подписания документа при помощи криптосистемы с открытым ключом достаточно незатейлив:

1. Антон шифрует документ с использованием тайного ключа, тем самым проставляя под этим документом свою подпись, и отправляет ею Борису.

2. Борис расшифровывает документ с использованием открытого ключа Антона, тем самым проверяя подлинность подписи.

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

Подписание документов при помощи симметричных криптосистем и арбитра

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

1. Антон шифрует свое сообщение Борису на ключе К А и посылает это сообщение Дмитрию.

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

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

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

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

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

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

2. Дмитрий расшифровывает полученное от Бориса сообщение, заглядывает в свой архив и убеждается, что Борис не внес никаких изменений в исходный открытый текст сообщения Антона.

3. Дмитрий зашифровывает сообщение Бориса с помощью ключа К Б , используемого для связи с Владимиром, и шлет это сообщение Владимиру.

4. Владимир расшифровывает сообщение Дмитрия и получает как открытый текст сообщения Антона, так и подтверждение того факта, что лея текст на самом деле принадлежит Антону.

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

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

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

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

Простым подсознательным каналом может служить число слов в предложениях невинного на первый взгляд текста. Нечетное количество слов соответствует 0, а четное — 1. Таким образом, если мой сообщник подсчитает количество слов в предложениях предыдущего абзаца, то получит секретное сообщение "11010". К сожалению, в этом алгоритме отсутствует ключ, а сам алгоритм является ограниченным — здесь стойкость всецело зависит от сохранения в тайне самого алгоритма.

Американский криптолог Г. Симмонс (G. Simmons) первым сумел встроить подсознательный канал в обыкновенную цифровую подпись. В этом случае алгоритм цифровой подписи со встроенным подсознательным каналом б\-дет неотличим для Олега от стандартного алгоритма цифровой подписи. Олег не только не сможет читать сообщения, передаваемые Антоном и Борисом по подсознательному каналу. В его мозгу не мелькнет даже намека па мысль о возможном существовании такового.

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

1. Антон генерирует произвольное сообщение, выглядящее вполне невинно.

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

3. Антон отдает подписанное сообщение Олегу.

4. Олег знакомится с сообщением Антона, проверяет цифровую подпись. Не обнаружив ничего подозрительного, Олег передает это сообщение Борису.

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

6. Используя секретный ключ, которым он владеет совместно с Антоном, Борис извлекает секретную информацию, содержащуюся в подсознательном канале.

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

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

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

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

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

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

Предсказание бита

Непревзойденный маг и волшебник Антон решает публично продемонстрировать свои необычайные интеллектуальные способности. Он точно знает. какую карту выберет из колоды Борис еще до того, как это сделает сам Борис! Поэтому Антон записывает название этой карты на листке бумаги, кладет листок в конверт и запечатывает его. Затем Антон передает запечатанный конверт на хранение кому-то из публики. "Возьми из колоды любую карту", — предлагает Антон Борису. Борис выбирает наугад карту и показывает зрителям: "Туз пик". Антон вскрывает конверт и извлекает из него листок бумаги, на котором, как все могут убедиться, черным по белому написано: "Туз пик". Шквал аплодисментов.

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

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

Предсказание бита с помощью однонаправленной функции

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

Антон генерирует две случайные битовые строки S 1 и S 2;

Антон присоединяет к сгенерированным S 1 и S 2 бит b , значение которою собирается предсказать;

Антон вычисляет значение однонаправленной функции Н, используя в качестве аргумента битовую строку (S 1 , S 2 ,b), и вместе с S 1 отсылает Борису полученный результат.

Теперь у Бориса имеется вся необходимая информация, которая не позволит Антону впоследствии изменить предсказанное значение b . Однако проверить правильность предсказания без участия Антона Борис не сможет. поскольку в этом случае ему придется вычислять H -1 (S 1 ,S 2 ,b).

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

1. Антон посылает Борису исходную битовую строку (S 1 ,S 2 ,b).

2. Борис вычисляет H(S 1 ,S 2 ,b), а затем сравнивает вычисленное значение и S 1 со значением и случайной битовой строкой, присланными ему Антоном на шаге 3. В случае совпадения b действительно представляет собой значение, предсказанное Антоном на шаге 2.

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

Теперь, при предсказании бита с помощью однонаправленной функции. Борису уже не обязательно генерировать какие-либо случайные битовые строки, поскольку Антон использует для предсказания однонаправленную функцию и не сможет смошенничать, составив фальшивое сообщение (S 1 S ' 2 , b') такое, что H(S 1 S 2 , b') = H(S 1 ,S 2 ,b). Антон посылает Борису случайную битовую строку S 1 чтобы у Антона не было возможности путем подбора S 1 и S 2 добиться, чтобы изменилось b и чтобы при этом было сохранено значение H(S 1 ,S 2 ,b), которое Антон ранее отослал Борису. Храня S 1 в секрете от Бориса, Антон не дает Борису вычислить значения H(S 1 ,S 2 ,b) и H(S 1 ,S 2 ,b ' ), а затем определить b, сравнив эти значения с тем, что прислал ему Антон.

Предсказание бита с помощью симметричной криптосистемы

Антон может сделать предсказание, выполнив шаги протокола, который использует симметричную криптосистему:

1. Борис, генерирует случайную битовую строку S и посылает ее Антону.

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

На этом завершается процесс предсказания.

Поскольку Борис не может дешифровать

Поскольку Борис не может дешифровать полученное от Антона сообщение Е K ( S , b ), то предсказание, сделанное Антоном, остается для Бориса тайной за семью печатями.

Теперь, если Антон пожелает ознакомить Бориса со своим предсказанием, они могут продолжить совместное выполнение следующих шагов протокола:

1. Антон посылает Борису ключ К.

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

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

Предсказание с помощью генератора псевдослучайных битовых последовательностей

Для предсказания битового значения Антон может использовать генератор псевдослучайных битовых последовательностей:

1. Борис генерирует случайную битовую строку S Б и посылает ее Антону.

2. Антон вычисляет случайное начальное значение для генератора псевдослучайных битовых последовательностей. Затем для каждого бита присланном Борисом битовой строки S Б Антон отправляет Борису либо (а) выходное значение генератора псевдослучайных битовых последовательностей, если этот бит равен 1, либо (б) результат сложения выходного значения генератора псевдослучайных битовых последовательностей со значением, предсказанным Антоном, если соответствующий бит S Б равен 0.

Когда Антон захочет раскрыть Борису свое предсказание, они должны буду: перейти к выполнению последних двух шагов протокола:

1. Антон высылает Борису случайное начальное значение, вычисленное им для генератора псевдослучайных битовых последовательностей на шаге 2.

2. Борис повторяет действия Антона, предпринятые им на шаге 2. чтобы убедиться в том, что Антон не смошенничал.

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

Протокол доказательства с нулевым разглашением конфиденциальной информации

Использование доказательства с нулевым разглашением конфиденциальной информации можно пояснить на конкретном примере. Предположим, что имеется пещера. Вход в пещеру находится в точке А, а в точке В пещера разветвляется на две половины — С и D. У пещеры есть секрет: только то;, км знает волшебные слова, может открыть дверь, расположенную между С и I).

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

1. Борис стоит в точке А.

2. По своему выбору Антон подходит к двери либо со стороны точки С, либо со стороны точки D.

3. Борис перемещается в точку В.

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

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

6. Шаги 1—5 повторяются n раз, где n — параметр протокола.

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

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

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

Протокол доказательства с нулевым разглашением срабатывает в силу того. что не зная волшебных слов, Антон может выходить только с той стороны, с которой зашел. Следовательно лишь в 50% всех случаев Антон сумеет обмануть Бориса, догадавшись, с какой именно стороны тот попросит его выйти. Если количество экспериментов равно n , то Антон успешно пройдет все испытания только в одном случае из 2". На практике можно ограничиться n =16. Если Антон правильно исполнит приказ Бориса во всех 16-ти случаях. значит он и правда знает секрет волшебных слов.

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

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

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

2. Антон задействует протокол предсказания бита для найденного на шаге 1 решения, чтобы впоследствии, если у Бориса возникнет необходимость ознакомиться с этим решением, Борис мог бы достоверно убедиться, что предъявленное Антоном решение действительно было получено им па шаге 1.

3. Антон показывает новую трудно решаемую задачу Борису.

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

5. Антон выполняет просьбу Бориса.

6. Антон и Борис повторяют шаги 1—6 n раз, где n — параметр протокола.

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

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

Протокол обмена ключами с цифровой подписью

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

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

Зиновию остается только перехватывать шифрованные сообщения, которыми обмениваются Антон и Борис, и пытаться их читать с помощью криптоаналитических методов.

Однако следует отметить, что в протоколе обмена сеансовыми ключами с цифровой подписью появился новый участник — Дмитрий. Если Зиновий сумеет перевоплотиться в Дмитрия, он сможет подписывать и навязывать участникам протокола известные ему фальшивые сеансовые ключи. Таким образом, несмотря ни на что, у Зиновия все же остается возможность атаковать этот протокол, воспользовавшись методом сведения к середине.

Протокол обмена сообщениями с использованием шифрования с открытым ключом

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

В 1976 г. американские криптологи У. Диффи и М. Хеллман изобрели криптографию с открытым ключом. Они предложили использовать два вида ключей — открытые и тайные. Вычислить тайный ключ, зная только открытый, очень сложно. Человек, владеющий открытым ключом, может с его помощью зашифровать сообщение. Расшифровать это сообщение в состоянии только тот, кто имеет соответствующий тайный ключ. В отличие от симметричной криптосистемы, для алгоритма шифрования с открытым ключом больше подходит сравнение с почтовым ящиком. Опустить почту и этот ящик очень просто, равно как и зашифровать сообщение с применением открытого ключа. А извлечение из почтового ящика находящейся в нем корреспонденции сродни расшифрованию сообщения. Желающего сделать это без ключа вряд ли ожидает легкая работа. Обладатель же ключа откроет почтовый ящик, т. е. расшифрует сообщение, без особого труда.

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

Протокол обмена сообщениями с использованием шифрования с открытым ключом выглядит следующим образом:

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

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

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

1. Антон находит открытый ключ Бориса в базе данных.

2. Антон шифрует открытый текст своего сообщения при помощи открытого ключа Бориса.

3. Борис расшифровывает сообщение Антона, используя свой тайный ключ.

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

Протокол обмена сообщениями с использованием симметричного шифрования

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

1. Антон и Борис уславливаются о том, какой криптосистемой они будут пользоваться.

2. Антон и Борис генерируют ключи для шифрования и расшифрования своих сообщений и затем обмениваются ими.

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

4. Антон отправляет зашифрованное сообщение Борису.

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

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

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

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

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

Протокол с судейством

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

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

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

"Шарады" Меркля

Оригинальный протокол обмена ключами был предложен американским криптологом Р. Мерклем (R.-Merkle) в 1974 г. Данный протокол основывается на так называемых "шарадах", которые требуется решить для получения ключа. Это гораздо легче сделать отправителю и получателю шифрованных сообщений, чем криптоаналитику, перехватывающему их. В результате Антон может послать шифрованное сообщение Борису, предварительно не передавая ему секретного ключа:

1. Борис генерирует 2 20 (около 1 млн) сообщений вида: "Это шарада под номером х. Это секретный ключ под номером у", где х — случайное число, у— случайный секретный ключ. Пара х, у является уникальной для каждого сообщения. Затем Борис шифрует все эти сообщения при помощи какого-либо симметричного алгоритма на различных 20-битных ключах и отсылает Антону.

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

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

4. Борис, зная соответствие между х и у, расшифровывает сообщение, пришедшее ему от Антона.

Конечно же, Петр может вскрыть ключ, который был использован Антоном для зашифрования секретного сообщения, однако для этого Петру придется выполнить значительно больший объем вычислений, чем Антону и Борису Петр должен будет прочесть все 2 20 шифрованных сообщений, отправленных Борисом, чтобы найти у, соответствующее значению х, выбранному Антоном. На решение этих "шарад" Петр потратит примерно квадрат времени. которое потребуется Антону и Борису, чтобы их составить. И хотя такое отличие в трудоемкости по криптографическим меркам довольно невелико, в некоторых случаях этого может оказаться достаточно. Например, если Антон и Борис смогут опробовать по 10 тыс. ключей в секунду, им понадобится немногим более 1 минуты, чтобы ключ шифрования у оказался в руках Антона. В то же время у Петра, обладающего примерно такой же вычислительной мощью для опробования ключей, как Антон и Борис, на вскрытие правильного ключа уйдет больше года.

Распределение ответственности

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

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

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

1. Дмитрий генерирует случайную битовую строку R, которая имеет ту же длину, что и исходное сообщение М.

2. Дмитрий складывает М с R по модулю 2 и получает S.

3. Дмитрий вручает R Антону, a S — Борису.

Чтобы восстановить сообщение М в исходном виде, Антон и Борис должны совместно выполнить последний шаг протокола:

1. Антон и Борис складывают R и S по модулю 2 и получают М.

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

Этот протокол можно легко применять для любого числа участников. Если участников 4, он будет выглядеть следующим образом:

1. Дмитрий генерирует три случайных битовых строки R, S и Т, которые имеют ту же длину, что и исходное сообщение М.

2. Дмитрий складывает М, R, S и Т по модулю 2 и получает U.

3. Дмитрий вручает R Антону, S — Борису, Т — Владимиру, U — Георгию.

Чтобы восстановить сообщение М в исходном виде, Антон, Борис, Владимир и Георгий должны совместно выполнить последний шаг протокола:

1. Антон, Борис, Владимир и Георгий складывают R, S, Т и U по модулю 2 и получают М.

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

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

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

Ситуацию можно еще усложнить. Допустим, что для нажатия "ядерной кнопки" в нашей стране нужны 1 генерал и 3 полковника. А если генерал по причине своего старческого склероза, забыл приехать к "ядерной кнопке" в назначенное время, достаточно и пятерых полковников. При этом, если собрались всего 4 полковника, Америке ничего не грозит до тех пор, пока 5 полковников не окажутся в полном сборе. Или пока генерал не приедет.

Криптологи придумали так называемый пороговый протокол, который позволяет распределять ответственность даже еще более сложным образом. В общем случае берется любое секретное сообщение (пароль, код запуска баллистических ракет, рецепт приготовления "Кока-колы") и делится па n частей (называемых долями) так, что для реконструкции исходного сообщения обязательно нужны m из них. Такой протокол более точно именуется ( т, п ) - пороговым протоколом.

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

Распределение ответственности и мошенничество

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

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

2. К Антону, Борису, Владимиру и Георгию, получившим от шефа распоряжение включить персональный компьютер Дмитрия, присоединяется Зиновий, который утверждает, что он явился по приказу шефа для воссоздания пароля, поскольку якобы является законным обладателем соответствующей пятой доли. После того как ничего не подозревающие Антон, Борис, Владимир и Георгий огласили свои доли, Зиновий с торжествующем воплем убегает из комнаты: теперь он может в одиночку реконструировать пароль Дмитрия, т. к. знает все необходимые для этого доли.

3. Вместо того чтобы убежать, Зиновий дожидается, пока все участники протокола по очереди огласят свои доли, а затем называет случайную битовую строку требуемой длины. В этом случае Зиновий не только сумеет узнать все доли, но и никто из участников протокола так и не осознает. что Зиновий является посторонним лицом и не имеет никакого права присутствовать при восстановлении секретного пароля Дмитрия.

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

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

Распределение ролей

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

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

Люди не вечны. Поэтому вполне может случиться так, что когда Антон обратится за содействием к I n -1 , тот уже успеет отправиться в мир иной, где отметки о времени создания документов вовсе не так важны для его обитателей. В этом случае можно посоветовать Антону воспользоваться распределенным протоколом и встроить в отметку о времени создания своего документа временные отметки, по крайней мере, 10-и других человек. Таким образом, у Антона будет больше шансов найти людей, которые при необходимости смогут помочь удостоверить время создания его документа. Распределенный протокол также позволяет избавиться от услуг Дмитрия:

1. С помощью генератора криптографически надежной псевдослучайной последовательности Антон получает k чисел R 1 , R 2 , . . . , R k , в качестве начального значения используя хэш-значение Н n , вычисленное для своего документа,.

2. Антон интерпретирует сгенерированные числа R 1 , R 2 , . . . , R k , как идентификаторы абонентов компьютерной сети, и отсылает Нп каждому из них.

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

4. Антон собирает и хранит все k подписей вместе с отметкой о времени создания своего документа.

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

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

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

Разновидности атак на протоколы

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

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

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

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

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

Роль в протоколе

Роль в протоколе

Антон Первый участник протоколов Борис Второй участник протоколов Владимир Участник трех- и четырехсторонних протоколов Георгий Участник четырехсторонних протоколов Дмитрий Доверенное лицо, наделенное правами арбитра Зиновий Злоумышленник Кирилл Контролер Олег Охранник Петр Подслушивает за участниками протоколов Сергей Свидетель

Протокол с арбитражем

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

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

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

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

Самоутверждающийся протокол

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

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

Сообщение, предназначенное Борису

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

В случае трех абонентов эта схема множественной рассылки сообщений группам абонентов выглядит не слишком впечатляюще, но при 100 абонентах ее преимущества становятся очевидны. Вместо порядка 2 100 ключей абонентам сети надо раздать всего 100 ключей, и посылать требуется всего одно шифрованное сообщение, а не n , где n — количество абонентов в группе ( n >1).

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

Специальные криптографические...

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

Борис: "Нет, не знаешь!"

Антон: "Нет, знаю!"

Борис: "Чем докажешь? "

Антон: "Хорошо, я тебе все расскажу".

Антон дол со шепчет что-то на ухо Борису.

Борис: "Действительно интересно! Надо сообщить об этом газетчикам!"

Антон: "Е-мое, как же я так лопухнулся..."

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

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

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

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

Связующий протокол

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

Пусть А— это идентификатор Антона, присвоенный ему в компьютерной сети, Н n — хэш-значение документа, для которого Антон хочет получить отметку о времени создания, a T n -1 — отметка о времени создания предыдущего документа. Тогда, чтобы затруднить сговор между Антоном и Дмитрием, можно воспользоваться так называемым связующим протоколом:

1. Антон посылает Дмитрию Н 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 К свидетельствует о том, что сообщение подписано цифровой подписью Дмитрия. Присутствие А необходимо, чтобы идентифицировать Антона в качестве получателя этого сообщения. Параметр n задает порядковый номер отметки о времени создания документа, хэш-значение которого Дмитрий получил от Антона. Т n — это сама отметка о времени. Остальные параметры перечисляют идентификатор хэш-значение, отметку времени и связующую информацию, которые были вычислены для предыдущего документа, присланного Дмитрию для постановки отметки о времени создания.

3. После того как Дмитрий получит следующий документ, на который потребуется поставить отметку о времени создания, он перешлет Антону идентификатор I n+ 1 своего очередного клиента, приславшего этот документ.

Теперь, если кто-то поставит под сомнение время создания документа Антоном, он может связаться с I n -1 и I n +1 , т. е. с авторами предыдущего и следующего документов, присланных Дмитрию. Если и у них возникнут сомнения относительно времени создания документов, то они. в свою очередь, могут обратиться к I n - 2 и I n + 2 . Каждый из них может доказать, что на его документ была поставлена отметка времени, предшествующая отметке следующего клиента и идущая за отметкой предыдущего.

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

Удостоверение личности с нулевым разглашением конфиденциальной информации

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

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

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

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

В-третьих, Антон может попросить Зиновия одолжить на время его цифровое удостоверение личности. Мол, Антону надо съездить в Соединенные Штаты, а поскольку он — бывший сотрудник советской разведки, работавший против США, американское правительство наотрез отказывает ему во въездной визе. Зиновий с радостью соглашается: после отъезда Антона он сможет пойти практически на любое преступление, поскольку обзавелся "железным" алиби. С другой стороны, ничто не мешает совершить преступление Антону. Кто поверит .лепету Зиновия о том, что он одолжил свое цифровое удостоверение личности какому-то другому человеку?

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

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

Вспомогательные криптографические протоколы Отметка о времени создания файла

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

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

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

Вычисление средней зарплаты

Допустим, что начальник отдела приказал своим подчиненным подсчитан, среднюю зарплату в отделе. Начальник осведомлен о зарплате любого сотрудника, но слишком занят более важными делами, чтобы отвлекаться па подобные пустяки. Каждый сотрудник прекрасно знает собственную зарплату, но категорически не желает сообщать о ней сослуживцам. Чтобы сотрудники отдела (Антон, Борис, Владимир и Георгий) смогли просуммировать свои оклады, сохранив их в тайне от других, им следует воспользоваться следующим протоколом:

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

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

3. На своем тайном ключе Владимир расшифровывает результат, вычисленный Борисом, прибавляет к нему свою зарплату, шифрует полученную сумму при помощи открытого ключа Георгия и затем передает то. что у него получилось, Георгию.

4. На своем тайном ключе Георгий расшифровывает результат, вычисленный Владимиром, прибавляет к нему свою зарплату, шифрует подученную сумму при помощи открытого ключа Антона и затем передает то. что у него получилось, Антону.

5. На своем тайном ключе Антон расшифровывает результат, вычисленный Георгием, вычитает из него случайное число, сгенерированное на шаге 1, делит на количество сотрудников отдела и получает искомую среднюю зарплату в отделе.

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

Зачем нужны криптографические протоколы

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

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

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

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