Что такое алгоритм Шора?
Квантовый алгоритм, способный за секунды раскладывать большие числа на простые множители и решать задачу дискретного логарифма. На сложности этих двух задач основана значительная часть современной асимметричной криптографии (с открытым ключом): RSA, протокол Диффи — Хеллмана, ECDSA и подписи Шнорра.
Для классического компьютера эти задачи практически нерешаемы при достаточной длине ключа. Лучший традиционный метод — метод решета числового поля — требует субэкспоненциального времени. Например, взлом ключа RSA-2048 занял бы миллиарды лет, а алгоритм Шора решает эту же задачу за полиномиальное время. Алгоритм стал одним из ключевых результатов ранней истории квантовых вычислений. Он показал, что достаточно мощная квантовая машина сможет эффективно решать задачи, на сложности которых основаны широко используемые криптографические системы.
Кто и когда его придумал?
Математик Питер Шор из Bell Labs в 1994 году. До этого квантовые вычисления уже существовали как теоретическое направление, но у них не было столь убедительного применения для решения практически значимой задачи. Работа Шора показала, что достаточно мощный квантовый компьютер сможет взламывать целый ряд криптографических систем с открытым ключом, включая RSA и криптографию на эллиптических кривых. Это стало одним из главных стимулов для развития квантовых вычислений и впоследствии — для создания постквантовой криптографии, устойчивой к таким атакам.
Как работает алгоритм Шора?
Задача факторизации (разложения числа на множители) сводится к поиску периода специальной функции. Классический компьютер тратит на этот поиск слишком много времени. Квантовый компьютер создает суперпозицию множества возможных состояний, а затем с помощью интерференции и квантового преобразования Фурье выделяет периодическую структуру функции. После измерения и классической обработки из нее можно получить множители числа или решить задачу дискретного логарифма.
- Подготовка (обычный ПК): формулирует задачу и подбирает случайное число для старта.
- Квантовое ядро (квантовый ПК): за один проход находит скрытый период функции.
- Финал (обычный ПК): использует период, чтобы мгновенно рассчитать множители.
Квантовый компьютер выдает результат с определенной вероятностью. Если попытка оказалась неудачной, алгоритм запускают снова. Для эллиптических кривых, которые защищают сеть первой криптовалюты, используется модификация алгоритма Шора: она решает задачу дискретного логарифма и позволяет вычислить приватный ключ на основе публичного.
Почему квантовые компьютеры угрожают именно биткоину?
Для контроля большинства биткоин-выходов используются приватные и публичные ключи на эллиптической кривой secp256k1. Первый нужен для создания подписи, второй — для ее проверки. Найти приватный ключ по публичному на классическом компьютере невозможно: лучшие алгоритмы требуют порядка 2¹²⁸ вычислительных шагов.
Алгоритм Шора эффективно решает задачу дискретного логарифма на кривой за полиномиальное время, сокращая процесс взлома.Квантовая атака становится возможной после раскрытия публичного ключа. Для одних типов выходов он публикуется уже при создании выхода, для других — только при первой трате средств. Под угрозой алгоритма Шора находятся как подписи ECDSA, так и современные подписи Шнорра.
При этом майнинг и хеш-функция SHA-256 защищены гораздо лучше. Квантовый алгоритм Гровера дает против них лишь квадратичное ускорение. Сложность перебора падает до 2¹²⁸ операций, что остается безопасным и легко нивелируется переходом на более длинные хеши в будущем.
Квантовая угроза для биткоина: сколько нужно кубитов?
Здесь важно различать физические и логические кубиты. Физические кубиты нестабильны и подвержены шуму. Чтобы получить один надежный логический кубит, требуются десятки или сотни физических, объединенных алгоритмами коррекции ошибок. Когда исследователи говорят о реальной атаке, они оценивают именно физические кубиты отказоустойчивой машины.
Оценки ресурсов для квантовой атаки на криптографию блокчейна стремительно падают. Ранние теоретические работы для ионных систем требовали миллионы физических кубитов, однако в 2026 году ситуация изменилась:
- Google Quantum AI совместно с Ethereum Foundation и Стэнфордским университетом опубликовала исследование, согласно которому для взлома 256-битного ключа на сверхпроводящей архитектуре хватит менее 500 000 физических кубитов. Это в 20 раз меньше прежних оценок. Практическая реализация пока недостижима, но теоретический порог сильно снизился.
- Компания IonQ представила первую полную инженерную схему атаки на кривую secp256k1. По расчетам инженеров, на новейшей архитектуре Walking Cat ионному компьютеру потребуется всего 19 397 физических (1457 логических) кубитов. При этом один подбор ключа займет около 25,7 дней.
Разброс в цифрах объясняется типом оборудования. Ионные ловушки IonQ выполняют операции гораздо точнее сверхпроводящих чипов Google, поэтому требуют кратно меньше кубитов для коррекции ошибок. Расплачиваться за это приходится временем: ионные машины работают значительно медленнее — отсюда почти месяц на генерацию одного ключа вместо минут у сверхпроводников.
Что означает оценка IonQ на практике?
Сразу оговоримся: это математический расчет, а не реальный эксперимент. Компания отдельно подчеркнула, что машины, способной выполнить такую атаку, сегодня не существует — ни один криптокошелек или приватный ключ не скомпрометирован.
Ценность исследования в другом. Впервые алгоритм Шора расписан до мельчайших деталей — вплоть до конкретных вентилей коррекции ошибок с доказанной, а не предполагаемой вероятностью успеха. По сути, это подробный чертеж для будущих устройств.
Для понимания масштаба: крупнейшие действующие квантовые процессоры (как, например, у IBM) сегодня содержат всего около 1100-1200 физических кубитов, работающих без полноценной коррекции ошибок. Разрыв между тысячей шумных кубитов и необходимыми 20 000 кубитов в отказоустойчивой машине по-прежнему огромен.
Кто-нибудь уже взламывал ключи алгоритмом Шора?
Пока успехи ограничиваются «игрушечными» масштабами. Еще в 2001 году 7-кубитная система жидкостного ЯМР от IBM впервые успешно реализовала алгоритм Шора, разложив число 15 на простые множители. В 2012 году исследователи подняли планку до числа 21, однако этот и последующие рекорды были достигнуты за счет «скомпилированных» квантовых схем, которые упрощались математиками заранее, еще до запуска вычислений.
В сегменте эллиптических кривых прогресс выглядит динамичнее, но не без важных оговорок. 24 апреля 2026 года независимый исследователь Джанкарло Лелли доказал взлом 15-битного ключа на общедоступном квантовом решении от IBM (получив за это награду в 1 BTC от Project Eleven). Пространство поиска по сравнению с прошлым 6-битным рекордом выросло в 512 раз.
Однако блокчейн-разработчики встретили новость со скепсисом: 15 бит генерируют всего 32 768 комбинаций, которые обычный ПК перебирает за долю секунды, а результаты квантовой генерации из-за шума железа на таких масштабах с трудом отличимы от случайной подстановки.
До реального ключа сети биткоина (256 бит) по-прежнему далеко. Разрыв между 15-битным экспериментом и secp256k1 огромен, но не потому, что ресурсы алгоритма Шора растут экспоненциально с каждым битом. Основная проблема — необходимость выполнить очень длинную квантовую схему на сотнях или тысячах логических кубитов с коррекцией ошибок. Для этого нужны на порядки более масштабные и надежные устройства, чем существующие сегодня.
Какие монеты под угрозой в первую очередь?
Алгоритму Шора нужен публичный ключ. В биткоине он раскрывается не всегда:
- Адреса формата P2PK (ранние монеты, включая предположительно принадлежащие Сатоши Накамото) содержат публичный ключ прямо в блокчейне.
- Кошельки с повторным использованием: если с такого счета (например, P2PKH) уже отправляли транзакции, публичный ключ раскрылся при подписи. Повторное использование такого адреса делает баланс уязвимым.
- Сеть формата Taproot (P2TR): публичный ключ непосредственно присутствует в блокчейне уже с момента создания UTXO. Поэтому при появлении достаточно мощной квантовой машины такие средства будут уязвимы даже до начала траты.
Адреса, с которых никогда не тратили средства (например, «чистые» P2PKH, P2WPKH), скрывают ключ за криптографическим хешем. Атаковать их можно лишь в короткое окно, когда транзакция находится в мемпуле: у злоумышленника есть минуты, чтобы вычислить ключ и «перебить» транзакцию своей. Текущая оценка IonQ в 26 дней на один ключ такую атаку полностью исключает. По разным подсчетам, в адресах с уже раскрытым ключом сейчас находится порядка четверти всех существующих биткоинов.
Как индустрия готовится?
В августе 2024 года NIST утвердил первые три постквантовых стандарта: ML-KEM для обмена ключами, а также ML-DSA и SLH-DSA для цифровых подписей. В марте 2025 года к ним добавился резервный алгоритм HQC, финальный стандарт которого ожидается к 2027 году.
Согласно проекту руководства NIST IR 8547, классические RSA и эллиптические кривые планируется признать устаревшими после 2030 года, а к 2035-му — полностью запретить их использование в госсекторе США.
В биткоин-сообществе активно обсуждают черновик предложения BIP-361. Инициатива, представленная разработчиком Джеймсоном Лоппом и группой экспертов, предполагает заморозку монет, уязвимых для квантовых компьютеров.
В Ethereum одним из ключевых инструментов рассматривают абстракцию учетной записи, которая после соответствующего обновления протокола позволит аккаунтам использовать разные схемы проверки подписей, в том числе постквантовые.
Когда наступит «Q-Day»?
Единого мнения нет. После мартовских публикаций 2026 года Google, Microsoft и Cloudflare назвали 2029 год ориентиром — но не для создания суперкомпьютера, а для полного перехода на постквантовые алгоритмы шифрования. Эксперты ожидают появление криптографически опасного квантового компьютера ближе к 2030-м годам. При этом скептики напоминают, что за 30 лет с момента публикации алгоритма Шора на реальном железе удалось разложить лишь число 21.
Тем не менее исследования 2026 года показывают: требования к оборудованию снижаются быстрее, чем казалось. За полгода теоретическая оценка для систем на нейтральных атомах упала с миллионов кубитов до 10 000-20 000.
Что делать держателю криптовалют?
- Не использовать адреса повторно. Каждая новая транзакция — новый адрес.
- Переводить средства со старых P2PK-адресов и адресов с раскрытым ключом на новые.
- Следить за обновлениями кошельков: миграция на постквантовые подписи потребует действий от пользователя.
- Не доверять проектам, которые обещают «квантовую защиту» без открытого аудита кода.
Опаснее всего для сети не внезапный взлом, а хаос при поспешной миграции. Чем раньше сообщество договорится о стандарте, тем спокойнее пройдет переход.