4. Криптографические методы защиты информации
Например, если f(x) будет четным в 90 процентах всех случаев, когда х является четным, Антон будет брать верх над Борисом почти всегда. - Бросание монеты с помощью криптосистемы с открытым ключом
В этом случае от алгоритмов шифрования (Е) и расшифрования (D) требуется, чтобы они были коммутативны, т. е.:
D (E (E (M))) = E (M),
где К1 и К2 — криптографические ключи, Р — открытый текст сообщения. Для симметричных криптоалгоритмов в общем случае это условие не выполняется, однако существуют алгоритмы шифрования с открытым ключом, для которых оно верно. Последние могут быть использованы в протоколе бросания монеты:
1. - Антон и Борис генерируют каждый для себя по паре ключей, состоящей из открытого и тайного ключа.
2. - Антон генерирует две случайные битовые строки P1 и Р2, одна из которых означает, что при бросании монеты выпал "орел", а другая — что получилась "решка".
3. - При помощи своего открытого ключа Антон шифрует сначала Р1 а потом Р2, и отсылает оба полученных в результате шифрсообщения (ЕА(Р1) и ЕА(Р2)) Борису.
4. - Борис выбирает одно из присланных ему Антоном шифрсообщений (для этой цели Борис может воспользоваться, например, известной считалкой "Эне, бене, раба, квинтер, минтер, жаба" или сходить за советом к астрологу). Борис шифрует выбранное шифрсообщение с помощью своего открытого ключа и отсылает результат (EБ(EA(P)), где Р — это либо Р1 либо Р2) Антону.
5. - Антон расшифровывает пришедшее от Бориса сообщение на своем тайном ключе и посылает то, что у него получилось (DA(EБ(EA(P)))=EБ(P)) обратно Борису.
6. - Борис расшифровывает это сообщение Антона (DБ(EБ(P))=P) и узнает, какой стороной упала монета. Затем Борис шлет Р Антону.
7. - Антон проверяет, действительно ли Р — это одна из тех двух случайных битовых строк, которые он сгенерировал на шаге 2.
8. - Чтобы окончательно убедиться в честности друг друга, Антон и Борис обмениваются парами ключей, которые они сгенерировали на шаге 1.
Читателю предоставляется возможность самому доказать, что каждый из участников этого протокола немедленно обнаружит, если другой участник попытается смошенничать.