Эта странная математика

Как и любая другая молодая и перспективная технология, квантовые компьютеры – это и множество надежд, и немало проблем. Среди последних – вероятность взлома шифров, которые до сих пор считались высокозащищенными, в основном потому, что, несмотря на все предпринятые усилия, за последние несколько десятилетий никому не удалось разработать полиномиальный метод их дешифровки. Современные методы криптографической защиты основаны на алгоритме RSA, названном так по первым буквам фамилий его изобретателей Рона Ривеста, Ади Шамира и Леонарда Адлемана[22]. Алгоритм позволяет очень быстро зашифровать данные и используется ежедневно, ежесекундно при обмене данными в интернете. А вот расшифровка тем же алгоритмом без специальной информации – ключа – происходит гораздо медленнее и требует экспоненциального времени. Именно этой асимметрией скорости и необходимостью обладать дополнительной информацией объясняется эффективность RSA. Работает алгоритм следующим образом: у каждого пользователя есть два ключа – открытый и секретный. С помощью открытого, общедоступного ключа информация шифруется, а секретный ключ, предназначенный для расшифровки, известен только его владельцу. Отправить защищенное сообщение просто – достаточно с помощью открытого ключа применить алгоритм. Но прочитать сообщение сможет только его адресат, имеющий секретный ключ. Теоретически секретный ключ возможно разгадать, зная открытый, но для этого придется разлагать на множители огромные числа, состоящие из сотен знаков. Если ключи достаточно большие, то для расшифровки сообщений, которые мы постоянно отправляем при совершении банковских и других конфиденциальных операций, понадобится задействовать все компьютеры мира, причем работать им нужно будет гораздо больше времени, чем текущий возраст Вселенной. Есть, однако, опасения, что с приходом квантовых компьютеров ситуация может круто измениться.

В 2001 году с помощью алгоритма Шора, который позволяет осуществлять разложение чисел на множители за полиномиальное время, и 7-кубитного квантового компьютера число 15 было разложено на множители 3 и 5. Десятилетие спустя тем же методом было разложено число 21. Оба достижения кажутся смехотворно скромными, учитывая, что то же без труда сделает любой школьник, знающий таблицу умножения. Но вот в 2014 году с помощью другого алгоритма и квантовой вычислительной системы были разложены на простые множители уже гораздо более внушительные числа, 56 153 – самое большое[23]. Даже этот результат может показаться не очень впечатляющим на фоне проблемы разложения на множители гигантских чисел, состоящих из сотен знаков. Однако с ростом числа кубитов в квантовых компьютерах успешная дешифровка всех шифров RSA рано или поздно станет возможной. Когда это произойдет, сегодняшние способы обмена данными в интернете перестанут быть безопасными – и банковская индустрия, а вместе с ней и все другие системы, требующие защиты передаваемых данных, будут повергнуты в хаос. Вероятно, удастся разработать новую систему криптографической защиты на основе NP

-трудных задач – таких, которые не менее трудны для решения, чем NP-полные, но не обязательно относятся к классу

NP. Наиболее сложные из NP

-полных задач решить очень непросто, но для более типичных случаев обычно можно подобрать подходящий алгоритм. Криптографическую защиту на основе таких задач будет довольно легко взломать, хотя небольшая вероятность того, что шифр окажется крайне сложным, все же есть. Для надежной защиты нужен алгоритм, почти всегда дающий крайне сложный шифр, требующий экспоненциального времени для взлома. Пока такой метод не разработан, хотя в принципе это возможно. Если квантовые компьютеры окажутся неспособными решать NP-полные (а значит, и NP-трудные) задачи, то разработка такого криптографического метода даст нам возможность снова почувствовать себя в безопасности, хотя бы на какое-то время.