Иллюстрированный самоучитель по защите информации

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

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

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

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

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

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

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

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

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

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

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

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