Золотой билет. P, NP и границы возможного - Лэнс Фортноу Страница 35

Что станет с криптографией в совершенном мире? В мире из второй главы, где P = NP? Определить, что число 16461679220973794359 представляется в виде 5754853343 × 2860486313, а числа 5754853343 и 2860486313 – простые, не составит особого труда; подобные вычисления можно будет проделывать с числами из тысяч и даже миллионов цифр! Задача разложения на множители лежит в классе NP, поскольку потенциальное решение можно проверить очень быстро; если классы P и NP совпадают, то для этой задачи существует эффективный алгоритм, а значит, мы легко отыщем все делители любого, сколь угодно большого числа. Протокол RSA, как и любая другая система шифрования с открытым ключом, станет абсолютно бесполезен, поскольку закрытый ключ будет быстро восстанавливаться по открытому ключу. Равенство P и NP приведет к тому, что мы больше не сможем обмениваться секретной информацией, не условившись предварительно о способе ее передачи.

Так, значит, в совершенном мире о криптографии придется забыть? Вообще-то есть один шифр, надежность которого не зависит от отношений между P и NP: это так называемый одноразовый шифровальный блокнот. Предположим, Элис придумала пароль из 12 символов: FIDDLESTICKS. Шифровальный ключ – он же блокнот – представляет собой случайную последовательность символов той же длины: JXORMQNAMRHC. Возьмем первые символы пароля и ключа, F и J. Это шестая и десятая буквы алфавита, соответственно. В сумме их номера дают число 16, поэтому первым символом шифрованного текста будет шестнадцатая буква алфавита – P. Теперь возьмем вторые символы пароля и ключа, I и X. Это девятая и двадцать шестая буквы алфавита. В сумме их номера дают 33, однако тридцать третьей буквы алфавита в английском языке не существует, поэтому мы вычитаем из числа 33 количество букв в алфавите, т. е. 26. Получается 7, а значит, вторым символом шифровки будет седьмая буква алфавита – G. Действуя аналогичным образом, мы в итоге получим PGSVYVGUVUSV. Эту криптограмму Элис отошлет на Facebook, а он расшифрует ее с помощью точно такого же блокнота, выполняя вычитание вместо сложения.

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

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

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