1 year ago
17
Ученый IBM Quantum доктор Майка Такита в лаборатории. Фото: IBM В журнале Nature опубликована статья о возможной атаке квантовых компьютеров на информационную безопасность. Безопасность компьютерной информации зависит от решения такой, казалось бы, абстрактной математической задачи, как разложение (большого) числа на простые множители. В настоящее время обычные компьютеры не в состоянии решать эту задачу достаточно быстро, чтобы взламывать шифрование.
В свое время физики придумали квантовые компьютеры, логической единицей которых является не классический объект (бит) с состояниями «0» и «1», но квантовый — так называемый кубит. В настоящее время квантовые компьютеры реализованы экспериментально; самый большой из них содержит 433 кубита. „
По идее, квантовые компьютеры обладают рядом преимуществ перед классическими, которые позволяют им более быстро решать задачу разложения числа на простые множители.
Это привело бы к революции в цифровом мире — стандартные способы шифрования перестали бы быть надежными, и человечеству пришлось бы заново решать проблему безопасности переписки и банковских трансакций.
Традиционный подход к задаче разложения числа на простые множители с помощью квантового компьютера основан на так называемом алгоритме Шора. Для его полноценной реализации с целью взлома стандартных алгоритмов шифрования нужен квантовый компьютер примерно с миллионом кубитов. Это существенно больше, чем достижимо на настоящий день технологически.
Алгоритм Шора. Фото: Wikimedia Commons, CC BY-SA 4.0
В конце прошлого года появилась статья китайских ученых (Бао Ян и другие), в которой предъявлен результат, который претендует на революционность: они продемонстрировали, что совсем маленький квантовый компьютер из 10 кубитов справляется с реализацией алгоритма разложения на простые множители. Речь идет не о стандартном алгоритме Шора, а о так называемом алгоритме Шнорра. Его до сих пор не реализовывали на квантовом компьютере.
По оценке китайских товарищей, если бы им дали квантовый компьютер с 372 кубитами, они смогли бы сломать алгоритмы RSA-шифрования, для чего им потребовалось бы разлагать на простые множители 600-значные числа в десятичной записи. Но пока что на опыте это смелое заявление не было проверено.
Переворачивает ли это ситуацию с компьютерной безопасностью? Как кажется, пока нет — автор статьи в Nature Давиде Кастельвекки приводит скептические соображения экспертов по поводу эффективности предлагаемого метода. В работе китайских ученых использовался пример чисел гораздо меньших, чем те, которые нужно разлагать для реального взлома шифра. И китайские товарищи также не показали, что их метод дает результаты быстрее, чем обычный лэптоп. Как будет расти время решения задачи при увеличении рассматриваемых чисел — мы тоже пока что не знаем. Таким образом, эффект от «квантовости» вычислений пока что неясен. Поэтому сама принципиальная реализация разложения на простые числа на квантовом компьютере еще не говорит ничего о достижимости взлома квантового шифрования.
