Квантовые вычисления представляют определенную угрозу для современной криптографии, ведь, как мы писали ранее, теоретически они способны взломать протокол RSA. Но как именно они могут это сделать, и чего не хватает квантовым машинам сегодня, чтобы раз и навсегда изменить шифрование в сети?
Протокол RSA был впервые описан в 1977 году Роном Ривестом, Ади Шамиром и Леонардом Адлеманом из Массачусетского технологического института (MIT). Этот протокол стал наиболее широко используемым асимметричным алгоритмом, безопасность которого строится на сложности разложения чисел на множители. Как известно, умножение двух чисел провести легко, но сделать обратную операцию крайне трудно: с этой задачей не справляются мощнейшие суперкомпьютеры мира.
“RSA используется везде. Каждый раз, когда вы выходите в интернет, вы, вероятно, используете RSA. Всякий раз, когда вы отправляете сообщение на iPhone, вы также используете RSA.”
— Мэтью Грин, криптограф из Института информационной безопасности Джона Хопкинса.
Согласитесь, было бы интересно придумать машину, которая имеет достаточно вычислительной мощности, чтобы сломать самую популярную систему шифрования. Питер Шор, профессор математики из MIT, придумал алгоритм для факторизации (разложения на множители) больших чисел с помощью квантового компьютера в 1994 году. Он не имел возможности проверить его, ведь в то время люди не имели больших квантовых машин.
Однако, уже в 2001 году Исаак Чанг и его группа из того же MIT, сумели использовать этот алгоритм для факторизации числа 15. Это была одна из первых реализаций квантового компьютера, основанного на ядерно магнитном резонансе. В ней кубиты представляют собой цепочку ионов, удерживаемых электрическим полем и управляемых с помощью импульсов. Им потребовалось четыре кубита для выполнения алгоритма Шора и пятый для вывода. Чанг и его коллеги обнаружили, что пятикубитный квантовый компьютер успешно нашел множители числа 15. Конечно, любой классический компьютер разложит число 15 намного быстрее чем квантовый, но важно было показать, что алгоритм рабочий и главное реализуемый. Компьютер из тысячи кубитов позволит находить множители чисел, недоступных классическому.
Так в чем же фокус алгоритма Шора? В квантовой механике есть два принципа, которые несколько противоречат нашей интуиции — это суперпозиция и запутанность. Суперпозиция позволяет кубиту быть не только в состоянии 0 или 1, а нулем и единицей одновременно. Запутанность же позволяет кубитам связываться друг с другом с помощью внутренних квантовых корреляций.
Алгоритм Шора состоит из 2 частей: классической и квантовой. Классическая часть лишь подготавливает нас к главному представлению и, по сути, сводит задачу разложения на множители к другой задаче: нахождению периода некоторой функции. А вот для эффективного решения последней необходим квантовый процессор с множеством кубитов.
- Для начала нужно создать квантовое состояние, которое будет общим для всех кубитов, то есть запутать их. На практике это самое сложное, ведь вам надо “размазать” запутанность по всему квантовому процессору. В сверхпроводящих кубитах это происходит с помощью последовательности микроволновых импульсов.
- Затем посылает последовательность импульсов, задающая ту самую функцию, которая определяется изначальным числом, которое нужно разложить на множители.
- Последний шаг перед измерением — это Квантовое преобразование Фурье. Оно то как раз и дает квантовое ускорение и находит период функции. Вам остается только измерить кубиты, которые дадут период, а, используя классический алгоритм, вы сможете найти и множители.
Первый шаг создает максимально запутанное состояние, которое является главные ресурсом алгоритма на ряду с суперпозицией, которая проявляется в процессе квантового вычисления. Алгоритм Шора оказался настолько быстрым, что время его работы сопоставимо с умножением чисел. Для криптографии это ночной кошмар — делить числа так же быстро, как и умножать.
Современное состояние квантовых компьютеров не позволяет реализовать этот алгоритм с большими числами в силу недостаточной универсальности квантовых процессоров. Сделать миллион кубитов — не проблема, проблема — запутать их, управлять ими, считывать их, поддерживать квантовое состояние достаточно долго. Это все непростые задачи, которые требуют новых физических идей и концепций. Есть и инженерные сложности: к примеру, алгоритм подразумевает, что вы можете связать каждый кубит с каждым, но на практике так не получается, и приходится усложнять алгоритм, что, конечно же, влияет на его эффективность.
Однако, решение этих вопросов — дело времени, рано или поздно квантовый компьютер научится взламывать RSA и даже Биткоин. Тогда начнется совсем другая эра, и, как сказал Андрей Себрант из Яндекса,
“... уже знакомые нам прошедшие “цифровые революции” могут оказаться просто утренниками в детском саду на фоне успешной квантовой.”