За последний год сразу несколько групп, включая такие большие компании как IBM и Google, объявили о создании квантовых компьютеров, содержащих более 50 кубит и потенциально способных выполнять универсальные вычисления. В то же время, вы, возможно, слышали, что одна из вещей, которые квантовые компьютеры делают лучше, чем классические, — это взлом ключей, шифрующих информацию в современных системах связи. Означает ли это, что пора беспокоиться о сохранности денег на наших счетах?
Что такое квантовый компьютер?
Напомню, что квантовые компьютеры так же, как и классические, представляют информацию в виде последовательности битов. Каждый бит может принимать значение 0 или 1. Главная особенность квантовых компьютеров заключается в использовании явления квантовой суперпозиции, которое позволяет каждому биту — в этом случае их называют квантовыми битами или кубитами — находится в произвольной суперпозиции состояний 0 и 1. В некотором смысле кубиты как бы находятся одновременно и в состоянии 0, и в состоянии 1, позволяя проводить операции сразу с обеими значениями.
Такой квантовый параллелизм для некоторых задач, которые решаются только перебором, позволяет значительно ускорить время поиска ответа. Например, для стандарта шифрования AES взлом на классическом компьютере требует перебора 2²⁵⁶ вариантов ключей — это число с 78 знаками! Для квантового компьютера существует алгоритм поиска, который эквивалентен перебору всего лишь 2¹²⁸ ключей — это число с 39 знаками. Разница колоссальна, однако видно, что вариантов всего равно много, и вряд ли в обозримом будущем удастся создать систему, которая выполнит такой перебор за разумное время.
Что сейчас?
Уже этот пример демонстрирует, что, как минимум, не всякий шифр окажется по зубам квантовым вычислениям. Однако наиболее распространёнными всё же являются не AES или подобные стандарты, а шифрование с открытым ключом.
Как следует из названия, в этом случае собеседники шифруют свои сообщения ключом, который вообще говоря открыт и доступен любому желающему. Это значительно облегчает нашу с вами жизнь, позволяя, например, оплачивать покупки не в магазине, а по интернету, не боясь при этом, что кто-то посторонний сможет расшифровать номер нашей карты и её CVC-код.
Уверенность, что даже зная открытый код никто не сможет расшифровать послание, основана на математической уловке, называемой односторонние преобразования. Оказывается, существуют математические операции, которые легко и быстро выполняются в одну сторону, но очень сложны с вычислительной точки зрения для выполнения в обратную.
Например, есть быстрый алгоритм поиска очень больших простых чисел. Однако если два таких числа перемножить, то чтобы найти что это были за числа, когда известно только их произведение, требуется перебрать все простые числа подряд. И это занимает совершенно нереальное для современных компьютеров время. На этом основан самый популярный метод шифрования с открытым ключом RSA.
Задача разложения больших чисел на простые множители, однако, относится к классу задач, называемых задачами со скрытой подгруппой. Группа — это термин, который обозначает определённую математическую структуру, а скрытая подгруппа — это другая структура, которая входит в состав группы, но не может быть извлечена простым способом. В примере с разложением числа на множители группу образует операция умножения, а простые множители образуют скрытую подгруппу.
Квантовые компьютеры называют угрозой для классического шифрования, поскольку доказано, что они могут решать задачу поиска скрытой подгруппы экспоненциально быстрее, чем классические компьютеры. Например, чтобы разложить на множители число из 2¹⁵³⁶⁰ цифр классическому компьютеру требуется перебрать порядка 2²⁵⁶ простых чисел. Квантовый же компьютер справится с этой же задачей за время, эквивалентное перебору всего лишь 20 000 ключей! И это, очевидно, огромная разница.
Как решить проблему?
Так, означает ли это, что классической криптографии пора на свалку? Не совсем. Хотя некоторые, действительно, призывают переходить на квантовое шифрование, которое в принципе не может быть взломано так, чтобы об этом не стало известно участникам общения, классические шифры тоже можно сделать квантово-устойчивыми.
Дело в том, что не все односторонние преобразования приводят к задачам со скрытой подгруппой. Примером может служить криптография на решётках. Она основана на задаче поиска кратчайшего расстояния между двумя узлами скошенной решётки, построенной в n измерениях.
Например, если Алиса хочет отправить Бобу сообщение, она ставит ему в соответствие некий узел на n-размерной скошенной решётке и добавляет к полученным координатам небольшой «шум», немного сдвигая точку из узла решётки. Если n достаточно велико, а углы решётки далеки от прямых, то Еве, перехватившей шифрованное сообщение, практически невозможно определить, какой же узел Алиса имела ввиду. При этом предполагается, что у Боба имеется секретная решётка с прямыми углами, узлы которой совпадают с узлами скошенной решётки, и это позволяет ему легко расшифровать сообщение даже при наличии «шума».
Что дальше?
Почему же до сих пор используются методы шифрования из семейства RSA? В первую очередь из-за их простоты. Ну и надо понимать, что квантовые компьютеры всё же пока далеки от того, чтобы эффективно их взламывать. Лучшее, что они на данный момент смогли, — это разложить 15 на 5 и 3. Для этого потребовалось пять кубит. На большем количестве кубит задачу разложения числа на множители пока делать не пытались.
Тем не менее, Национальный институт стандартизации и технологий США NIST в 2016 году запустил программу проверки квантово стойких шифров. Программа должна продлиться от 4 до 6 лет.
Это вполне разумный срок. С одной стороны, специалистам требуется время, чтобы проверить возможные пути взлома предложенных алгоритмов. Например, в 2014 году британские шифровальщики предложили основанный на решётке метод шифрования, который казался квантово устойчивым, однако через несколько лет удалось показать, что его расшифровка сводится к классу задач со скрытой подгруппой, и поэтому уязвима для квантовых компьютеров.
С другой стороны, вряд ли можно ожидать, что в ближайшие 5—10 лет появятся квантовые компьютеры, способные взламывать современные шифры на основе RSA. Так что опасности для ваших кредитных карт достижения в квантовых вычислениях пока что не представляют.
Угостить автора кофе
Читайте также
Телепортация энергии? Квантовый вакуум всё стерпит
Квантовый симулятор невозможной физики
Учёные измерили квантовые флуктуации напрямую
Подписывайтесь также на мой Telegram-канал!
