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

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

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

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

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

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

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

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

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

делит на количество сотрудников отдела и получает искомую среднюю зарплату в отделе.

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



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



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

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

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

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





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

3.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

изюминок.

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

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

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

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

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



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





Даже при наличии "изюминок" схема аутентификации пользователей путем проверки их паролей имеет один очень серьезный недостаток. Ведь не исключено, что линия связи, соединяющая персональный компьютер Антона с сервером информационно-коммерческой службы, проходит по территориям 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.

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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



В этом случае от алгоритмов шифрования (Е) и расшифрования (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.

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

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

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



Игра в покер



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

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


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

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

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

Протокол —

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

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

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

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

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

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

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

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



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



В повседневной жизни нам приходится сталкиваться с протоколами буквально на каждом шагу — играя

в

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

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

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

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


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



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



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



Таблица 7.1. Роли, которые играют участники протоколов

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

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



Арбитр —

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

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

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


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

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

Введение арбитра в любой протокол увеличивает время, затрачиваемое на реализацию этого протокола.

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

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

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



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



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

судья.

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

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


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



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



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

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

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



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



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

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

пассивная атака

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

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


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

активная атака

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

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

мошенником.

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

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



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



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



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

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

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

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

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

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

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

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


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

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

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



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



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

В 1976 г. американские криптологи У. Диффи и М. Хеллман изобрели криптографию с открытым ключом. Они предложили использовать два вида ключей —

открытые

и

тайные.

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


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

При зашифровании и расшифровании сообщений в криптосистеме с

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

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

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

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

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

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

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

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

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

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



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

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



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



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

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

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

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

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

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

Е

В

(К)

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


сгенерированный Антоном:

K=D

B

(E

B

(K))

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

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

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



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



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

1. Борис генерирует 2

20

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

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

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

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



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

20

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

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

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

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

Подпись нельзя подделать. Наличие подлинной подписи является доказательством того, что именно тот человек, которому она принадлежит, поставил эту подпись под документом.

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

Подписанный документ не подлежит никаким изменениям.

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

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

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

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

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

А,

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

Б

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

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

А

и посылает это сообщение Дмитрию.

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

Б

, а затем отправляет их Борису.

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

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

А

и, следовательно. только он мог зашифровать это сообщение с помощью К

А

.

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

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

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

Б

и отсылает их Дмитрию.

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



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

Б

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

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

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



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



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

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

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

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



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



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


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

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



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

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

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

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

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

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



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



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



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

шифрованием на тайном ключе, а

процесс проверки подлинности подписи —

расшифрованием на открытом ключе.

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

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

К

(P), а проверка подлинности подписи с использованием соответствующего открытого ключа — V

К

(P).

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

аутентифнкационным протоколом.



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



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



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

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

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

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

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

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

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

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



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



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

отказ от обязательств.

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

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

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



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

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

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

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

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

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

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 (Попрыгунчик), используемый для шифрования сообщений.

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

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


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

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

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

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

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


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

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

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

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

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

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

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

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

БАН-логикой (BAN-logic).

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

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

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

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

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

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

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

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

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

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

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

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

Вспомогательные криптографические протоколы

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

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

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

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

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

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

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

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

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

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

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

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

Групповыми подписями

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

только члены группы могут подписывать документы;

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

по подписи невозможно определить, кто именно из членов группы ее поставил;

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

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

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

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

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

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

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

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

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

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

Имеется три ключа К

А

, К

Б

и К

С

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

Антон

К

А

Борис           

К

Б

Владимир     К

В

Георгий       

К

А

и К

Б

Денис          

К

Б

и

К

В

Евгений        К

В и

К

А

Если Антон зашифрует свое сообщение с помощью ключа К

А,

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

К

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

Предположим, что Борис безуспешно пытается разложить на простые множители 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. Борис расшифровывает свою копию сеансового ключа.

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

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

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



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



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

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

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

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

4.

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



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



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

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

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

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


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

4.

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

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

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



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



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

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

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

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

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

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

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


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

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

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

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

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

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

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

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


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



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



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

В результате Зиновию придется весьма несладко. Он не сможет выдать себя

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

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

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



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



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

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

К

(М).

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

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

В

(К)

.

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

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

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

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

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

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

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

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 шага протокола.



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



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

Антон генерирует две случайные битовые строки 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. Антон вычисляет случайное начальное значение для генератора псевдослучайных битовых последовательностей. Затем для каждого бита присланном Борисом битовой строки S

Б

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

Б

равен 0.

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

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

2.

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

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

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

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

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

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

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

участников были против, сообщение будет восстановлено в первозданном виде, а иначе — не будет.



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

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

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

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

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

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

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

"

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

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

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

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

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

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

Антону надо воспользоваться

протоколом

доказательства с

нулевым paзглашением

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

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

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

Использование доказательства с нулевым разглашением конфиденциальной информации можно пояснить на конкретном примере.
Предположим, что имеется пещера. Вход в пещеру находится в точке А, а в точке В пещера разветвляется на две половины — С и 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 — параметр протокола.

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

Не



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



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



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

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

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

новых задач.

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

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

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



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

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

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



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



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

неинтерактивный

протокол, в котором вместо Бориса используется однонаправленная функция:

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.

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


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



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



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

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

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

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


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

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

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

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

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

Вспомогательные криптографические протоколы

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

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

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

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

в файл нельзя внести какие-либо изменения так, чтобы эти изменения остались незамеченными;

имеющуюся отметку о времени создания файла невозможно поменять на другую.

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

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

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

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

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

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



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



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

Пусть А— это идентификатор Антона, присвоенный ему в компьютерной сети, Н

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

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

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



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



Люди не вечны. Поэтому вполне может случиться так, что когда Антон обратится за содействием к 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.

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



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





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

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

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

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

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

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

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

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



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

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

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

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

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

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

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



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



На практике подсознательный канал наиболее подходит для организации связи в шпионских сетях.


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

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

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

Аппаратное и программное шифрование

Аппаратное шифрование

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

аппаратного

шифрования над программным обусловлено несколькими причинами.

Более высокая скорость.

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

Аппаратуру легче физически защитить от проникновения извне.

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

Аппаратура шифрования более проста в установке.

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

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

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

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



Программное шифрование



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


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

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

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

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

Надежность криптосистем

Как выбрать хороший криптографический алгоритм

Симметричный или асимметричный криптографический алгоритм?

Шифрование в каналах связи компьютерной сети

Шифрование файлов

Аппаратное и программное шифрование

Сжатие и шифрование

Как спрятать один шифртекст в другом

Почему криптосистемы ненадежны

Как спрятать один шифртекст в другом

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

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

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

Р Å   К = С

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

С

Å  К = Р

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

К '= С

Å  D

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

С

Å  К ' = D

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

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

Как выбрать хороший криптографический алгоритм

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

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

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

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

из

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

При выборе хорошего криптографического алгоритма можно:

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

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

обратиться к независимому эксперту (непредвзятость во мнении позволит ему объективно оценить достоинства и недостатки различных криптографических алгоритмов);

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

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

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

Поэтому наиболее предпочтительной представляется первая из перечисленных возможностей.


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

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

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

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



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



Криптографические алгоритмы, предназначенные для экспорта из США



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

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

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

ключ имеет длину всего 30 бит вместо официально заявляемых 100 бит, поскольку большинство ключей оказываются эквивалентны;

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

любое шифрованное сообщение содержит некоторый фрагмент открытого текста вместе с соответствующим ему шифртекстом.

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

Почему криптосистемы ненадежны

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

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

Реализация

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

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

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

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

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



Учет реальных потребностей пользователей



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



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



Законодательные ограничения



В Своде законов США имеется пункт 2778, который называется "Контроль за экспортом и импортом вооружений". Именно этот пункт является юридической основой для ряда инструкций, именуемых "Правилами контроля за перемещением оружия в мире" (International Traffic in Arms Regulations, сокращенно— 1TAR). Раздел 120.1 ITAR впрямую причисляет к военному

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

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

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


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

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



Слишком малая длина ключа



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

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

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



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

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

(факторизации)

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

В начале 1998 г. из-за слишком малой длины ключа (56 бит) фактически "приказал долго жить" DES-алгоритм, долгое время являвшийся официальным стандартом шифрования данных в США. Сейчас американским Национальным институтом стандартов объявлен конкурс на новый стандарт шифрования данных Advanced Encryption Standard (AES). Согласно условиям этого конкурса, кандидаты на роль AES должны представлять собой симметричные алгоритмы шифрования с ключом длиной более 128 бит.



Потайные ходы



Причины появления

потайных ходов

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



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

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



Шифрование вокруг нас



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


Далее требуется передать эту систем)

в

ФАПСИ, чтобы получить там лицензию, дающую право на ее легальное распространение и использование на территории России. Однако несмотря на богатый научный потенциал российских криптографов и высокую квалификацию отечественных программистов, единственным лицензированным ФАПСИ шифром в настоящее время является ГОСТ 28147-89, разработанный еще в недрах КГБ. Все остальные криптосистемы, предлагаемые зарубежными и российскими фирмами в виде законченных продуктов или библиотек, включая как устоявшие зарубежные стандарты, так и самостоятельные оригинальные разработки, являются незаконными.

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

ftp.elf.stuba.sk/pub/security).

Их распространению способствует нечеткость президентского Указа № 334, в котором не оговорено, что же конкретно понимается под термином "шифрование" данных. Если предположить, что шифрование — это такая нестандартная кодировка данных, которая серьезно затрудняет возможность их перекодировки в стандартное представление без соответствующего аппаратного или программного обеспечения, то в категорию шифрсистем тут же попадут архиваторы (pkzip, arj и r а r ), известные текстовые редакторы (Word и Lexicon), a также средства редактирования графических изображений (Paint и CorelDraw), поскольку все они используют свою собственную нестандартную кодировку, не позволяющую без соответствующих программ просматривать закодированные с их помощью данные.

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


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

Учитывая неразбериху, царящую в российском законодательстве, неудивительно, что российские пользователи для защиты своей конфиденциально!! информации активно применяют архиваторы с парольной защитой, Norton Diskreet, Word, Excel, многочисленные условно-бесплатные программы (PGP, CodeDvag, SecurPC, Secur-all 32, BestCrypt NP, Kremlin и др.). криптографические системы отечественных фирм ("Лан Крипто". "Анкорт" и др.), собственные кустарные разработки, а также программы неизвестного происхождения. Большинство из них крайне слабы, и программы их взлома за вполне умеренную плату можно получить, например, в Internet по адресу

www.accessdata.com.

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

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

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


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

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

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

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

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

Шифрование файлов

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

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

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

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

нередко после шифрования файла его незашифрованная копия остается на другом магнитном диске, на другом компьютере или в виде распечатки, сделанной на принтере;

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

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

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

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

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

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

мастер-ключа.

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

Шифрование в каналах связи компьютерной сети

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

уровни,

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

OSI

(Open . Systems Interconnection — Модель открытых сетевых соединений).

Согласно модели OSI коммуникационные функции разнесены по уровням. Функции каждого уровня независимы от функций ниже- и вышележащих уровней. Каждый уровень может непосредственно общаться только с двумя соседними. Модель OSI определяет 7 уровней: верхние 3 служат для связи с конечным пользователем, а нижние 4 ориентированы на выполнение коммуникационных функций в реальном масштабе времени.

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

канальным,

а если на верхних, то такое шифрование называется

сквозным.

Оба этих подхода к шифрованию данных имеют свои преимущества и недостатки.

Канальное шифрование

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

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

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

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

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

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



Сквозное шифрование



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



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

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

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



Комбинированное шифрование



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

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

Симметричный или асимметричный криптографический алгоритм?

Какой алгоритм лучше — симметричный или асимметричный? Вопрос не вполне корректен, поскольку предусматривает использование одинаковых критериев при сравнении криптосистем с секретным и открытым ключами. А таких критериев просто не существует.

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

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

Сжатие и шифрование

Алгоритмы сжатия данных очень хорошо подходят для совместного использования с криптографическими алгоритмами. Тому есть две причины:

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

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

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

---

---