Алгоритм Шора и RSA
Урок 12 из 23 курса «Квантум: курс с нуля». Бесплатно, с анимациями и тестом.
Замок из простых чисел
Когда ты заходишь на сайт по HTTPS, подписываешь документ или платишь картой, часто работает схема RSA, её придумали в 1977 году. Идея простая: перемножить два больших простых числа легко, а разложить результат обратно на множители очень трудно. 61 × 53 ты посчитаешь за минуту, а вот найти множители 3233 уже дольше. В RSA-2048 число длиной 617 цифр, и обычным компьютерам на разложение не хватит возраста Вселенной.
Трюк Шора: превратить разложение в ритм
В 1994 году математик Питер Шор из Bell Labs заметил: разложение числа можно свести к поиску ритма. Возьмём N = 15 и число 7. Будем возводить 7 в степень и брать остаток от деления на 15: выходит 1, 7, 4, 13, и снова 1, 7, 4, 13. Ритм повторяется каждые 4 шага. Зная ритм, школьной арифметикой находим множители: 3 и 5. Для маленьких чисел ритм видно глазами, для чисел из сотен цифр он астрономически длинный, и тут нужен квантовый компьютер.
Как квантовый компьютер слышит ритм
Шаг первый: суперпозиция всех степеней сразу, и в амплитудах прячется повторяющийся узор. Шаг второй: квантовое преобразование Фурье, или QFT. Оно делает то же, что эквалайзер в плеере: раскладывает сигнал на частоты. Благодаря интерференции правильная частота усиливается, а все остальные гасятся. Измеряем и получаем число, из которого вычисляется период. Это и есть экспоненциальное ускорение: задача на миллиарды лет превращается в задачу на часы или дни.
Сколько нужно кубитов и почему цифра падает
Шор на бумаге ломает RSA давно, но для этого нужен большой компьютер с коррекцией ошибок. Оценки быстро падают. В 2019 году Крейг Гидни и Мартин Экеро насчитали около 20 миллионов физических кубитов и 8 часов. В мае 2025 года Гидни показал: меньше миллиона кубитов и меньше недели. В феврале 2026 года стартап Iceberg Quantum заявил о схеме меньше чем на 100 тысяч кубитов, а в конце марта команда Caltech оценила, что на нейтральных атомах может хватить 10–20 тысяч. Правда, обе оценки — для особых архитектур, которых ещё нет. У лучших чипов сегодня тысячи кубитов, и качества пока не хватает. Но разрыв сокращается с двух сторон.
Под ударом не только RSA
Тот же алгоритм Шора ломает и эллиптические кривые. На них держатся подписи Bitcoin и Ethereum и обмен ключами в HTTPS. В марте 2026 года команда Google с соавторами, среди которых криптограф Дэн Боне, оценила: для кривой Bitcoin хватит меньше 500 тысяч физических кубитов, а после того как публичный ключ засветился, взлом займёт около 9 минут. А вот симметричные шифры вроде AES и хэши вроде SHA-256 от Шора не страдают: им грозит только «корень» от Гровера. Подробно про крипту — в последнем уровне.
Почему защищаться надо уже сейчас
Если большой квантовый компьютер появится только через годы, зачем спешить? Из-за тактики «собери сейчас, расшифруй потом». Злоумышленник уже сегодня может записывать зашифрованный трафик и хранить его до дня, когда сможет взломать. Медицинские данные, гостайны и переписка должны оставаться секретными десятилетиями. Поэтому в 2024 году NIST утвердил первые постквантовые стандарты, а Signal, iMessage и Chrome уже включили такую защиту для обычных пользователей.
Проверь себя
- Какой факт делает RSA уязвимым для квантового компьютера?
Правильный ответ: Разложение сводится к поиску периода, а период хорошо ищет QFT. Шор превращает разложение в поиск ритма, а QFT с помощью интерференции выделяет ритм. Это и даёт экспоненциальное ускорение. - Зачем защищать данные сейчас, если Q-Day через годы?
Правильный ответ: Трафик можно записать сейчас и расшифровать потом. Тактика «собери сейчас, расшифруй потом» делает угрозу актуальной уже сегодня для данных с долгим сроком жизни. - Что из этого Шор не ломает?
Правильный ответ: AES-256. AES — симметричный шифр, у него нет «ритма» для Шора. Против него работает только Гровер, и 256-битный ключ держит удар.