А они… чижика съели

[nlothik]

Раз уж зашла речь про алгоритм шифрования RSA. Его секретность зиждется, повторюсь, на том, что число, полученное перемножением достаточно длинных простых чисел, умучаешься раскладывать на множители. Неверящие могут попробовать разложить в уме (да можно даже с обычным калькулятором) число 7081. Если не знать, что это 73×97, то придётся перебирать простые числа до полного посинения.

Ну, не совсем прямо «до полного посинения», конечно — нет смысла перебирать множители >√(7081)≈84. Но всё равно — простых чисел меньше 83 (а 83 — наибольшее простое число, меньшее 84) довольно много.

Ну, а реальная криптография, конечно, работает не на четырёхзначных числах, а на числах с сотнями знаков — что позволяет нам безопасно передавать номер кредитки при покупках наклеечек с котиками в ентом вашем Ёнтернете.

Несколько лет назад всех вдруг накрыла квантовая паника. Мол, да вот придут квантовые компьютеры, да на них работает алгоритм Шора, и все эти ваши RSA, DH, ECDH, ECDSA, и прочие умные слова — полетят на свалку истории. Ну да, ну да, полетят, как же. Вот только шнурки погладят — и сразу полетят.

Мир криптографии в лице NIST (и при активной поддержке Микрософта, надо отдать им должное) в шухерном режиме стандартизировал квантово-устойчивые алгоритмы криптографии, и сейчас у нас есть то, что не ломается даже на ентих ваших кубитах со всей их квантовой запутанностью и прочей непонятной простым смертным теорией.

А на деле мы имеем что? А на деле в 2001 году, с огромной помпой, квантовый компьютер сумел-таки наконец разложить на множители… число 15. Ага, пятнадцать. 3×5.

С тех пор были и другие демонстрации — 21, 35, ещё несколько аккуратно подобранных чисел. Иногда с классической «помощью», иногда с заранее известной структурой. Это важные научные шаги — никто не спорит. Но это не «взлом традиционной криптографии к соответствующей матери». Это подтверждение теории в лабораторных условиях.

Дело в том, что алгоритм Шора для взлома RSA-2048 требует порядка нескольких тысяч логических кубитов, а каждый логический кубит — это тысячи физических кубитов, потому что квантовая теория — это вам не транзистор, это крайне обидчивая киса, и нормально работает она только при температуре, близкой к абсолютному нулю. Современные квантовые компьютеры — это несколько сотен физических кубитов без полновесной коррекции ошибок. А логических, устойчивых к шуму, — в практическом смысле пока нет.

Квантовая угроза реальна. Но она инженерная, а не магическая.
Между красивой теоремой Шора и машиной, способной ломать банковскую криптографию, лежат десятилетия прорывов в физике и инженерии. Так что отставить панику! До квантового апокалипсиса ещё очень далеко. Можете пока спокойно продолжать покупать свои наклеечки. С котиками.

PS: Для тех, кто хочет копнуть глубже в современные оценки и архитектурные ограничения квантовых устройств, см. работу 2025 года на arXiv: https://arxiv.org/pdf/2410.14397v1

Permalink to this post

Comments

[ymarkov]

Спасибо за успокоение!