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

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

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

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

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

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

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

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

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