Анин Б.Ю. Защита компьютерной информации

Подождите немного. Документ загружается.

все документы вместо себя, не предоставляя ему доступ к своему тайному

ключу?

Для этого Антону следует воспользоваться цифровой подписью по

доверенности. Тогда в случае необходимости Антон сможет передать Борису

доверенность на право ставить свою цифровую подпись. Для этого

поставленная по доверенности цифровая подпись должна обеспечивать:

 Распознаваемость. Подпись по доверенности всегда можно отличить

от оригинальной подписи ее настоящего владельца.

 Невозможность фальсификации. Только истинный владелец подписи

и его доверенное лицо в состоянии поставить эту подпись под

документом.

 Проверяемость. Изучение цифровой подписи, поставленной по

доверенности, позволяет убедиться, что ее владелец действительно

предоставил эту доверенность лицу, поставившему данную подпись.

 Опознаваемость. Цифровая подпись по доверенности дает

возможность ее владельцу однозначно идентифицировать человека,

который поставил эту подпись.

 Неоспоримость. Цифровая подпись по доверенности, поставленная

под

документом, не может быть впоследствии оспорена лицом, на

законных основаниях поставившим ее под этим документом.

В некоторых случаях требуется, чтобы возможность однозначно

идентифицировать лицо, поставившее цифровую подпись по доверенности,

была предоставлена не только законному владельцу подписи, но и любому, кто

пожелает это сделать.

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

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

обладают следующими свойствами:

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

 владелец документа может убедиться, действительно ли поставленная

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

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

поставил;

 в случае возникновения разногласий имеется возможность однозначно

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

подпись.

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

помощи следующего протокола с арбитражем:

181

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

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

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

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

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

общедоступную базу данных, сохраняя в секрете от посторонних

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

этих ключей.

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

предоставленного ему Дмитрием.

4. Чтобы проверить подлинность групповой подписи, достаточно

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

ним в базу данных.

5. В случае возникновения спора Дмитрий знает, кому из членов группы

принадлежит ключ, с помощью которого была поставлена подпись,

вызвавшая разногласия.

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

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

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

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

принадлежит.

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

Предположим, что в распоряжении злоумышленника Зиновия имеется

множество высокопроизводительных компьютеров. И все они работают днем и

ночью, чтобы вскрыть тайный ключ Антона, которым тот пользуется,

подписывая своей цифровой подписью важные финансовые документы. Цель

оправдывает средства: ведь в случае успеха Зиновий сможет свободно

распоряжаться весьма значительными денежным и средствами Антона,

подделывая его подпись.

Чтобы противостоять злодейским планам Зиновия, Антону следует

воспользоваться цифровой подписью с дополнительной защитой. Тогда, если

Зиновий вскроет тайный ключ Антона с помощью тотального перебора и

подделает его подпись, Антон сможет разоблачить подделку. Идея, которая

лежит в основе цифровой подписи с дополнительной защитой, достаточно

проста. Каждому открытому ключу ставится в соответствие не один тайный

ключ, а некоторое множество тайных ключей. Любой из них позволяет

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

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

тайный ключ, остальные ему неизвестны.

Теперь, если Зиновий накопит достаточно документов, подписанных

182

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

нахождения тайного клю ча Антона, то самое большее, чего сможет добиться

Зиновий, — это отыскание отдельного ключа. А если количество возможных

тайных ключей, соответствующих данному открытому ключу, чрезвычайно

велико, то Зиновий вряд ли найдет именно тот ключ, который использует

Антон для подписи своих документов.

Если Зиновий попытается подделать подпись Антона, воспользовавшись

тайным ключом, вскрытым тотальным перебором, то эта подделка будет

заметно отличаться от настоящей подписи Антона. И когда дело дойдет до

суда, Антон сможет продемонстрировать, что с помощью его собственного

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

воспроизвел Зиновий. Однако в случае, если Антон окажется не в состоянии

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

подпись под спорным документом является подлинной.

Таким образом, цифровая подпись с дополнительной защитой позволяет

отразить атаку, предпринятую Зиновием, имеющим в своем распоряжении

самые современные суперкомпьютеры. Но с бандитом, который проникнет в

квартиру Антона и украдет его тайный ключ, или с самим Антоном,

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

сможет поделать даже самая изощренная схем а цифровой подписи с

дополнительной защитой. В первом случае остается только посоветовать

установить более совершенную сигнализацию или обзавестись сторожевой

собакой. А во втором — тщательнее выбирать себе деловых партнеров.

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

Непревзойденный маг и волшебник Антон решает публично

продемонстрировать свои необычайные интеллектуальные способности. Он

точно знает, какую карту выберет из колоды Борис еще до того, как это сделает

сам Борис! Поэтому Антон записывает название этой карты на листке бум аги,

кладет листок в конверт и запечатывает его. Затем Антон передает

запечатанный конверт на хранение кому-то из публики. “Возьми из колоды

любую карту”, — предлагает Антон Борису. Борис выбирает наугад карту и

показывает зрителям: “Т уз пик”. Антон вскрывает конверт и извлекает из него

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

написано: “Туз пик”. Шквал аплодисментов.

Но как узнать наверняка, что Антон не подменил конверт, прежде чем его

вскрыть? Специальный криптографический протокол позволяет Антону

сохранить предсказанное им значение, состоящее из одного или нескольких

битов, в тайне до тех пор, пока он не пожелает ознакомить с ним остальных. С

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

Антон не смошенничал и не изм енил свой выбор уже после того, как этот

выбор был им сделан.

Информация о сделанном Антоном выборе фиксируется в виде

183

обязательства, которое передается на хранение Борису. Обязательство

представляет собой значение, которое, после того как Антон познакомит

Бориса со своим выбором, Борис может предъявить Антону и потребовать,

чтобы Антон преобразовал это значение и получил величину, известную

Борису. Если Антон сумеет это сделать, значит мошенничества с его стороны

проявлено не было.

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

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

использует симметричную криптосистему:

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

2. Антон присоединяет бит b, значение которого он собирается

предсказать, к S, шифрует полученную в результате битовую строку

(S,b) при, помощи симметричной криптосистемы E

и некоторого

секретного ключа К, а затем отсылает результат обратно Борису.

На этом завершается процесс предсказания. Поскольку Борис не может

дешифровать полученное от Антона сообщение E

(S, b), то предсказание,

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

Теперь, если Антон пожелает ознакомить Бориса со своим

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

шагов протокола:

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

2. С помощью К Борис расшифровывает E

(S,b) и узнает значение b.

Чтобы убедиться в честности Антона, Борис проверяет, содержит ли

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

случайную битовую строку S.

Если бы посланное Борису сообщение изначально не содержало

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

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

предсказанного значения b противоположное. Поскольку b принимает всего 2

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

сообщении случайной битовой строки, сгенерированной Борисом, Антону

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

―

только инвертированный бит b, но и S. Если Антон пользуется хорошей

симметричной криптосистемой, то его шансы найти такой ключ будут

пренебрежимо малы. Следовательно, Антон не сможет изменить предсказанное

им значение после того, как сделает свой выбор, выполнив первые 2 шага

протокола.

184

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

однонаправленной функции

Антон может предсказать битовое значение, воспользовавшись

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

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

и S

;

 Антон присоединяет к сгенерированным S

и S

бит b, значение

которого собирается предсказать;

 Антон вычисляет значение однонаправленной функции Н, используя в

качестве аргумента битовую строку (S

, S

,b), и вместе с S

отсылает

Борису полученный результат.

Теперь у Бориса имеется вся необходимая информация, которая не

позволит Антону впоследствии изменить предсказанное значение b. Однако

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

поскольку в этом случае ему придется вычислять Н

-1

, S

, b).

Когда потребуется, чтобы Антон ознакомил со своим предсказанием

Бориса, им обоим необходимо будет продолжить выполнение следующих

шагов протокола:

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

, S

, b).

2. Борис вычисляет H(S

, S

, b), а затем сравнивает вычисленное значение

и S

со значением и случайной битовой строкой, присланными ему

Антоном на шаге 3. В случае совпадения b действительно представляет

собой значение, предсказанное Антоном на шаге 2.

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

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

не требуется, чтобы Борис посылал какие-либо сообщения Антону. А Антону

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

одно, чтобы Борис смог с этим предсказанием ознакомиться.

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

Борису уже не обязательно генерировать какие-либо случайные битовые

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

функцию и не сможет смошенничать, составив фальшивое сообщение

,S’

,b’) такое, что H(S

,S’

,b’) = H(S

,b). Антон посылает

Борису случайную битовую строку S

, чтобы у Антона не было возможности

путем подбора S

и S

добиться, чтобы изменилось b и чтобы при этом было

сохранено значение H(S

,b), которое Антон ранее отослал Борису.

Храня S

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

H(S

,b) и H(S

,b’), а затем определить b, сравнив эти значения с

тем, что прислал ему Антон.

185

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

битовых последовательностей

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

генератор псевдослучайных битовых последовательностей:

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

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

2. Антон вычисляет случайное начальное значение для генератора

псевдослучайных битовых последовательностей. Затем для каждого

бита присланной Борисом битовой строки S

Антон отправляет Борису

либо (а) выходное значение генератора псевдослучайных битовых

последовательностей, если этот бит равен 1, либо (б) результат

сложения выходного значения генератора псевдослучайных битовых

последовательностей со значением, предсказанным Антоном, если

соответствующий бит S

равен 0.

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

будут перейти к выполнению последних двух шагов протокола:

1. Антон высылает Борису случайное начальное значение, вычисленное

им для генератора псевдослучайных битовых последовательностей на

шаге 2.

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

убедиться в том, что Антон не смошенничал.

Если сгенерированная Борисом случайная битовая строка является

достаточно длинной, а генератор псевдослучайных битовых

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

непредсказуем, то у Антона практически нет шансов обмануть Бориса.

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

Для разрешения неожиданно возникшего спорного вопроса Антон и

Борис решают бросить монету. Однако и у того, и у другого при себе не

оказалось ни одной. Тогда они решают “бросить” м онету в уме: сначала Антон

загадает, что выпадет — “орел” или “решка ”, а потом Борис подумает и

объявит, какой стороной упала “брошенная” им монета. Спрашивается: м огут

ли Антон и Борис сделать это так, чтобы полностью быть уверенными в том,

что никто из них не смошенничал?

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

заставит их действовать таким образом, что:

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

предсказать, какой стороной она упадет;

186

 Антон не сможет изменить результат бросания монеты после того, как

услышит, на какую сторону монеты сделал свою ставку Борис;

 Борис не узнает, что выпало — “орел” или “решка”, до тех пор, пока не

примет окончательное решение и не сообщит о нем Антону.

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

предсказания бита

В этом случае криптографический протокол, которого должны

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

образом:

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)

187

требуется, чтобы они были коммутативны, т. е.:

где К

и К

— криптографические ключи, Р — открытый текст сообщения. Для

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

однако существуют алгоритмы шифрования с открытым ключом, для которых

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

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

состоящей из открытого и тайного ключа.

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

и Р

, одна из

которых означает, что при бросании монеты выпал “орел”, а другая —

что получилась “решка”.

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

, а

потом Р

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

(Р

) и Е

(Р

)) Борису.

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

(для этой цели Борис может воспользоваться, например, известной

считалкой “Эне, бене, раба, квинтер, минтер, жаба” или сходить за

советом к астрологу). Борис шифрует выбранное шифрсообщение с

помощью своего открытого ключа и отсылает результат (Е

(Е

(Р)), где

Р — это либо Р

либо Р

) Антону.

5. Антон расшифровывает пришедшее от Бориса сообщение на своем

тайном ключе и посылает то, что у него получилось D

(Е

(Р))) = =Е

(Р)) обратно Борису.

6. Борис расшифровывает это сообщение Антона (D

(Е

)(P)) = P)) и

узнает, какой стороной упала монета. Затем Борис шлет Р Антону.

7. Антон проверяет, действительно ли Р — это одна из тех двух

случайных битовых строк, которые он сгенерировал на шаге 2.

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

обмениваются парами ключей, которые они сгенерировали на шаге 1.

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

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

попытается смошенничать.

Интересно отметить, что участники протокола узнают результат

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

момент времени один из участников знает, как “легла” подброшенная монета, а

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

кто уже знает результат, может повести себя неспортивно, отказавшись от

дальнейшего выполнения шагов протокола.

На практике протоколы бросания монеты часто используются для

генерации сеансовых ключей. В этом случае Антон и Борис могут

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

посторонние окажутся не в состоянии повлиять на ее выбор. Тем не менее при

188

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

Борису все равно придется шиф ровать все свои сообщения, чтобы защититься

от возможного подслушивания.

Игра в покер

Подобно тому, как Антон и Борис бросали монету, не имея при себе

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

криптографический протокол аналогичен протоколу, который помог Антону и

Борису организовать бросание монеты — в обоих необходимо обеспечить,

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

коммутативны.

Отличие между этими протоколами состоит в том, что теперь Антону

требуется сгенерировать, зашифровать и отослать Борису не 2 битовых

последовательности, а 52 — по числу карт в воображаемой колоде. Среди них

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

их при помощи своего открытого ключа и посылает Антону. Антон

расшифровывает полученные последовательности и шлет обратно Борису,

который тоже расшифровывает их. Затем Борис выбирает еще 5 битовых

последовательностей и посылает Антону, который опять их расшифровывает. В

результате и у Антона, и у Бориса на руках окажется по 5 карт, которыми они и

будут играть друг против друга. Если потребуется, дополнительные карты

могут быть розданы обоим игрокам по той же схеме.

По окончании игры Антон и Борис открывают свои карты и

обмениваются ключами, чтобы иметь возможность проверить, насколько

честно они следовали правилам карточной игры. К сожалению,

криптографические протоколы, предназначенные для игры в покер, устроены

таким образом, что в ходе нее игроки могут слегка мошенничать. Характер

этого мошенничества зависит от используемого криптоалгоритма. Например,

при шифровании при помощи квадратичных вычетов играющие имеют

возможность пометить несколько карт. Не бог весть что, но ведь покер — это

такая игра, в которой даже небольшая порция дополнительной информации о

сопернике может в конечном счете решить исход игры.

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

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

конфиденциальной информации

Антон: “Я знаю пароль для входа в компьютерную сеть Центробанка,

рецепт приготовления “Байкала”, а также почему Ельцин всегда выглядел так,

189

будто только что проглотил живого лягушонка!”

Борис: “Нет, не знаешь!” Антон: “Нет, знаю!” Борис: “Чем докажешь?”

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

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

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

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

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

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

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

первому встречному. Есть ли у Антона возможность помешать Борису это

сделать?

Конечно есть. В первую очередь, Антону не следует доверять свою тайну

Борису. Но тогда как Антон сможет убедить Бориса, что действительно входит

в число посвященных в эту тайну?

Антону надо воспользоваться протоколом доказательства с нулевым

разглашением конфиденциальной информации. С помощью этого протокола

Антон окажется в состоянии доказать Борису, что он обладает некой секретной

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

необязательно.

Доказательство носит интерактивный характер. Борис задает Антону

серию вопросов. Если Антон знает секрет, то ответит правильно на все

заданные ему вопросы. Если не знает, вероятность правильного ответа на

каждый из вопросов будет невелика. После примерно 10-ти вопросов Борис

сможет твердо узнать, обманывает ли его Антон. При этом шансы Бориса

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

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

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

конфиденциальной информации

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

конфиденциальной информации можно пояснить на конкретном примере.

Предположим, что имеется пещера. Вход в пещеру находится в точке А, а в

точке В пещера разветвляется на две половины — С и D. У пещеры есть секрет:

только тот, кто знает волшебные слова, может открыть дверь, расположенную

между С и D.

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

Борису, что знает волшебные слова, но так, чтобы Борис по-прежнему

оставался в неведении относительно этих слов. Тогда Антон может

воспользоваться следующим протоколом:

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

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

либо со стороны точки D.

190