Национальный институт стандартов и технологий США (NIST) с 2016 года продвигает разработку криптографических алгоритмов, устойчивых к квантовым компьютерам. Тем не менее, Питер Гутманн, профессор компьютерных наук в Университете Окленда (Новая Зеландия), считает это бессмыслицей для читателей — и прямо заявил об этом в своей презентации под названием «Почему квантовый криптоанализ — бред» .
Ожидается, что мощный квантовый компьютер сможет сломать основу лснов современного мира-криптографию. Этот день уже называют катастрофой Q-Day . Многие общедоступные криптосистемы, используемые сегодня, пострадают, говорится в обзоре NIST по постквантовой криптографии (PQC).
Аргумент Гутманна против такой паники прост: до сих пор квантовые компьютеры, которые он считает скорее «физическими экспериментами», чем перспективными продуктами, не смогли без мошенничества разложить на множители ни одного числа, большего 21.
Квантовые вычисления и PQC чрезвычайно сложны. Но сам процесс взлома RSA-шифрования-довольно прямолинейный. Имея модуль n из открытого ключа, нужно найти два простых числа p и q, такие что n = p ? q.
Если n = 21, то p = 3, q = 7 — простая 5-битная реализация RSA. Но если n имеет 1024 или 2048 бит, поиск p и q требует колоссальных вычислительных ресурсов. Именно эта потребность в колоссальных вычислительных ресурсах делает взлом криптографии фактически невозможным на кремниевых процессорах-они не предоставляют нужной вычислительной мощности.
Беспокойство NIST — и не только — заключается в том, что когда-нибудь квантовый компьютер сможет запускать алгоритм Шора , который значительно ускоряет разложение больших чисел на простые множители. В таком случае данные, защищенные слишком простыми ключами, окажутся под угрозой. Чтобы избежать этого гипотетического риска, NIST координирует разработку» квантифицированных » алгоритмов: HQC, CRYSTALS-Kyber, CRYSTALS-Dilithium, Sphincs+, FALCON — вместо RSA.
NIST отмечает, что некоторые инженеры предполагают появление таких методов взлома в течение 20 лет. Поскольку именно столько времени ушло на внедрение инфраструктуры открытых ключей, NIST считает, что пора готовиться.
Однако, если смотреть на текущее состояние квантовых вычислений, потребность в новых алгоритмах выглядит не такой уж и насущной. В статье Гутманн и соавтор Стефан Нойхаус, преподаватель информатики из Германии, утверждают, что возможности современных квантовых компьютеров можно воспроизвести с помощью домашнего 8-битного компьютера VIC-20 (1981 года), абакуса и собаки.
«PQC-это не математика и не инженерия, это гадание: “придет большая машина, и она уничтожит всю существующую криптографию. Будет Голод, Чума, Война и долгий неурожай”»
В статье упоминается, что IBM еще в 2001 году реализовала алгоритм Шора на 7-кубитном квантовом компьютере, разложив число 15. спустя 10 лет удалось разложить 21. в 2019 году IBM пыталась разложить 35, но результат был удачным лишь в 14% случаев из-за многочисленных ошибок кубитов.
Исследователи из Шанхайского университета заявили, что использовали квантовый компьютер D-Wave для разложения 2048-битного числа RSA.
Но, по словам гутманна и Нойгауса, выбранные простые числа были слишком близки друг к другу, что значительно упрощает задачу.
Как и фокусник, подготовивший колоду заранее, авторы объясняют: «факторизация в» квантовом стиле»-это фокусы с числами, подобранными так, чтобы их легко было разложить экспериментом по физике или VIC-20, абакусом и собакой».
«Поскольку n = p ? q, квадратный корень из n дает значения p и q с точностью до одного или двух битов, если p и q близки. Именно поэтому стандарты RSA, такие как FIPS 186, требуют, чтобы p и q различались как минимум на 100 бит (т. е. на 2^100 или 1,3 ? 10^30, что называется “нониллион”) — чтобы нельзя было приблизительно угадать их через корень», — объясняет Гутманн.
Аналогия с миром ИИ: хвастаться высокими результатами в бенчмарках, используя ИИ, который тренировался именно на этих тестах.
Тревор Лантинг, технический директор D-Wave, прокомментировал: «это исследование не является прорывом. Это исследование предыдущих попыток использования квантового отжига (annealing) для разложения малых чисел. Чтобы взломать современное шифрование, нужны квантовые процессоры на много порядков масштабнее. Угрозы для криптографии не будет еще много лет. К тому же уже существуют квантостойкие алгоритмы. D-Wave не специализируется на криптографии, но наша технология используется для обнаружения угроз и атак».
Несмотря на громкие заявления о» квантовом превосходстве » от Google, сомнительный прорыв Microsoft с фермионами Майораны, аргументы профессора Даниэля Бернштейна из Университета Иллинойса, что квантовые компьютеры не следует списывать со счетов, и мнение Скотта Ааронсона из Техасского университета, что квантовые вычисления «почти готовы к прорыву», Гутманн остается скептиком: никто в ближайшее время не будет взламывать коды с помощью»экспериментов по физике».
Гутманн уточняет, когда именно он понял, что квантовый криптоанализ-это миф.
«Какого — то конкретного мгновения не было, — ответил он, — но со временем стало все очевиднее: никакого реального (не мошеннического) прорыва не появилось. Это так же реально, как термоядерное электричество , которое будет настолько дешевым, что его не придется считать».
«Я эмпирический гностик. С обычной криптографией все четко: есть математика, инженерия, вычислительные ресурсы — и можно провести линию на графике: вот когда будет опасно. А PQC — это не наука. Это гадание».
«В презентации мы провели линию через две существующие точки PQC-и получили, что уровень криптоанализа, как у современных компьютеров, квантовые достигнут где-то через 2000 лет. И даже эти точки-это фокусы, а не реальные результаты алгоритма Шора для нахождения неизвестных p и q. Поэтому мы в статье предлагаем критерии оценки таких заявлений, которые должны защищать от мошенничества».
«На самом деле у нас ноль достоверных точек данных. Это довольно веское доказательство, что криптоанализ на базе физических экспериментов никуда не ведет».
Гутманн добавляет: У нас столько же данных и о путешествиях быстрее света, и о телепортации, как в Star Trek , и о других мечтах техноутопистов.
Когда его спросили, распространяется ли его скептицизм по поводу PQC на квантовые компьютеры в целом, Гутманн ответил, что лучше всего это сформулировал Австралийский институт стратегической политики (ASPI).
Когда его спросили, что следует делать специалистам по кибербезопасности в связи с переходом в PQC, он ответил:
«Ничего. На самом деле, мы теряем больше. Сегодня существует многомиллиардная индустрия киберпреступности, которая построена на том факте, что шифрование не выполняет свою защитную функцию. И вместо того, чтобы исправить это, мы тратим колоссальные ресурсы на внедрение новых алгоритмов, которые не лучше, а только неудобнее. Неудивительно, что их игнорировали десятилетиями — они не практичны. Переход на PQC-это просто отвлечение от реальной, сложной задачи».
По материалам: The Register
