Эта странная математика. На краю бесконечности и за ним - [34]

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

Большинство ученых, занимающихся вычислительными системами, полагают, что P ≠ NP. Это мнение подкреплено десятилетиями исследований, в результате которых ни для одной из более чем 3000 известных NP-полных задач не было найдено ни единого алгоритма, позволяющего решить ее за полиномиальное время. И все же аргумент, основанный на отрицательном опыте, не слишком убедителен, особенно в свете неожиданного доказательства Великой теоремы Ферма – очень просто сформулированной задачи, для решения которой потребовались огромные усилия и самые передовые методы. Чисто философские аргументы в пользу того, что P ≠ NP, также не очень убедительны. Скотт Ааронсон, математик, специалист в области теории вычислительных систем, преподающий в Массачусетском технологическом институте, заявил: “Если окажется, что P = NP, то мир станет совершенно не таким, каким мы его обычно считаем. Не будет больше никакой особой ценности в «творческих скачках», исчезнет принципиальная разница между решением задачи и признанием правильности найденного решения”. Тем не менее и в математике, и в других науках с завидной частотой происходят события, полностью переворачивающие наши представления об окружающем мире. Если действительно окажется, что P = NP, то, прежде всего, вряд ли это открытие будет иметь большое практическое значение – ведь доказательство, скорее всего, будет неконструктивным. Другими словами, даже если будет доказано, что для решения NP-полных задач существуют полиномиальные алгоритмы, ни одного конкретного алгоритма в доказательстве приведено не будет. Так что по крайней мере в ближайшем будущем нашим защищенным данным ничто не угрожает – хотя не совсем ясно, как долго это продлится, ведь математики уже всерьез занялись поиском такого алгоритма.

В любом случае, прежде чем существенные сдвиги в решении проблемы равенства P и NP или в разработке более эффективных алгоритмов поставят под угрозу безопасность наших данных, на помощь нам, вероятно, подоспеет квантовая механика. Разработки в области квантовой криптографии могут привести к созданию абсолютно стойкого шифра, не поддающегося дешифровке никакими методами. Один из действительно нераскрываемых шифров был изобретен еще в 1886 году и получил название “одноразовый блокнот”. Ключ представляет собой случайную последовательность букв той же длины, что и сообщение. Сообщение объединяется с ключом путем присвоения каждой букве числового значения (A = 1, B = 2 и так далее), сложения числовых значений букв сообщения и соответствующих им букв ключа, вычитания из получившихся сумм 26, в случае если сумма превышает 26, и последующего обратного превращения чисел в буквы[24]. Доказано, что этот метод является абсолютно криптостойким. Даже если у кого-то найдется достаточно времени, чтобы перебрать все возможные комбинации, будет совершенно невозможно отличить правильную расшифровку от множества неправильных вариантов. Важное условие: чтобы шифр невозможно было взломать, ключ должен после использования уничтожаться. Если его использовать повторно, то любой человек, имеющий в своем распоряжении оба зашифрованных сообщения и знающий, что ключ один и тот же, сможет их расшифровать. Кроме того, ключи должны передаваться секретно, поскольку доступ к ключу грозит мгновенной расшифровкой. Одноразовые шифры в свое время использовались советскими шпионами. Они сшивались в крошечные блокноты и пропитывались специальным горючим составом, чтобы при уничтожении от них не оставалось и следа. Такие шифры и сейчас используются для защиты данных, передаваемых по линии прямой связи между президентами США и России. Но необходимость секретно обмениваться ключами – серьезный недостаток метода, делающий его непригодным для большинства практических целей, например для передачи данных онлайн.