Читать «Золотой билет» онлайн - страница 81

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

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

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

Криптография в играх

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

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

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

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