Золотой билет

Любая строка длины 12 может быть ключом. Любая строка длины 12 может быть исходным сообщением. Все варианты равновероятны, так что, имея на руках криптограмму, получить какую-либо информацию об исходном тексте абсолютно невозможно. Этот факт математически доказан, и классы P и NP тут совершенно ни при чем. Но тогда зачем нужны все эти хитроумные и потенциально уязвимые системы шифрования, завязанные на поиск простых сомножителей? Почему бы нам не перейти на одноразовые блокноты?

К сожалению, с блокнотами все обстоит не так просто. Их ведь потому и назвали одноразовыми, что любой ключ разрешается использовать только один раз. Это правило должно соблюдаться неукоснительно; даже если два не связанных между собой человека отсылают сообщения двум другим не связанным между собой людям, лучше, чтобы их ключи не совпадали, иначе конфиденциальность переписки может быть нарушена. Кроме того, одноразовый блокнот обязательно должен быть той же длины, что и сообщение. В отличие от криптосистем с открытым ключом, ключ здесь лишь один – секретный, общий для обеих сторон. И Элис, и Facebook должны знать секретный ключ; если к злоумышленнику попадет хотя бы часть ключа, он сможет получить некоторую информацию об исходном сообщении, поэтому Facebook должен переправить Элис ключ так, чтобы его никто, кроме самой Элис, не увидел (или наоборот – Элис должна переправить ключ в Facebook). Данные, пересылаемые по интернету, легко перехватить. Блокноты нужно передавать на физическом носителе, например – на флешке, причем делать это только лично или через надежного посредника. В совершенном мире Элис, скорей всего, отправилась бы в ближайший супермаркет и купила запечатанную флешку с набором одноразовых блокнотов. Производством таких флешек занималась бы заслуживающая доверия организация (возможно, правительство), способная гарантировать безопасную передачу второго экземпляра блокнота в Facebook и другие подобные компании.

Рис. 8.6. Судоку с нулевым разглашением

Равенство P = NP многое упрощает, однако криптографам оно может принести лишь головную боль.

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

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

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

«У них тут ошибка. Это решить невозможно!» – восклицает он, совершенно выбившись из сил. На крики приходит его коллега Элис; взглянув на судоку, она видит ту самую головоломку, которую утром решила в метро. Боб зря ругается. На рисунке ниже вы видите решение Элис.

Боб вот-вот сдастся, и Элис хочется его поддержать. Она говорит, что решила задачу, но он ей, конечно, не верит. Он ужасно расстроится, когда увидит в завтрашней газете ответ, так что нужно обязательно убедить его подумать еще. Показать свое решение значит испортить Бобу все удовольствие от процесса; но как доказать, что задача решается, не давая при этом никаких подсказок?

Рис. 8.7. Решение судоку с нулевым разглашением

К счастью, в колледже Элис специализировалась на теоретической информатике и поэтому знает о доказательствах с нулевым разглашением. В голове у нее быстро созревает план действий.

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

Рис. 8.8. Новый порядок цифр

С помощью полученной таблицы Элис шифрует свое решение, заменяя 1 на 2, 9 на 3, и т. д., и рисует его на большом листе бумаги. Вот что у нее выходит:

Рис. 8.9. Зашифрованное решение

Дальше Элис аккуратно режет сетку с решением на маленькие квадратики по одной цифре в каждом. Всего квадратиков получается 81. Каждый квадратик она прячет в маленький пакетик и кладет в соответствующую ячейку нарисованной на другом листе пустой сетки.

Рис. 8.10. Решение спрятано

Рис. 8.11. Открытая строка

В левом верхнем пакетике лежит цифра 2, справа от него – цифра 3, и так далее.

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

• открыть все пакетики в одной из строк;

• открыть все пакетики в одном из столбцов;

• открыть все пакетики в одном из девяти блоков 3 × 3;

• открыть все пакетики, расположенные на тех же позициях, что и заданные цифры исходной головоломки.

Допустим, Боб решил открыть третью строку. Что он там увидит?

Если бы в строке оказалось две одинаковых цифры, это означало бы, что Элис наврала. Но поскольку решение у нее действительно есть, и она четко объяснила Бобу, что сделала с пакетиками, Боб видит все различные цифры от 1 до 9 в случайном порядке. Тест пройден!

Если Боб решит открыть столбец или блок 3 × 3, результат будет точно таким же.