Как квантовый компьютер сломал бы мои пароли

Как хранятся пароли и почему их нельзя просто прочитать

Чтобы понять масштаб квантовой угрозы, нужно вспомнить устройство авторизации в вебе. Сервисы не держат пароли пользователей в открытом текстовом виде. Когда ты вводишь символы в форму авторизации, сервер берет эту строку, добавляет к ней случайную соль и прогоняет через хэш-функцию вроде bcrypt, scrypt или семейство SHA. Получается фиксированная строка знаков — цифровой слепок. Обратно превратить хэш в пароль математически невозможно. Классический компьютер для взлома вынужден наугад перебирать комбинации, хэшировать их и сверять с базой данных сервиса.

Второй барьер защиты работает во время передачи данных от браузера к серверу. Твой пароль летит по сети внутри защищенного туннеля TLS, который обеспечивает протокол HTTPS. Для создания этого туннеля два компьютера договариваются об общем секретном ключе шифрования. Они делают это на глазах у всех с помощью асимметричной криптографии — алгоритма RSA или протокола Диффи — Хеллмана на эллиптических кривых. Вся современная интернет-безопасность держится на предположении, что решить математическую задачу разложения гигантского числа на простые множители за разумное время невозможно.

В чем принципиальная разница между битом и кубитом

Классический процессор в смартфоне или ноутбуке манипулирует битами. Бит жестко зафиксирован в одном из двух состояний — ноль или единица. Это транзистор, который либо пропускает ток, либо заперт. Чтобы перебрать миллион возможных паролей, обычный процессор проверяет их строго последовательно или распределяет между ядрами, выполняя миллиарды тактов работы.

Квантовый процессор использует кубиты. Благодаря законам квантовой механики кубит находится в состоянии суперпозиции. Он представляет собой линейную комбинацию нуля и единицы одновременно с определенными амплитудами вероятностей. Физически это может быть спин электрона, направление поляризации фотона или искусственный сверхпроводящий контур, охлажденный до температуры, близкой к абсолютному нулю.

Сила квантовой системы раскрывается в явлении запутанности. Когда разработчики связывают кубиты между собой, система из N кубитов может одновременно описывать 2 в степени N состояний. Обычный регистр из трех бит держит одно число от нуля до семи. Регистр из трех кубитов хранит все восемь чисел параллельно. Система из 300 кубитов способна одновременно удерживать больше квантовых состояний, чем атомов во всей обозримой Вселенной. Это дает возможность запускать параллельные математические преобразования над гигантскими массивами чисел за один такт работы логических вентилей.

Два алгоритма, которые рушат цифровую защиту

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

Алгоритм Шора против сетевых ключей

В 1994 году американский математик Питер Шор представил квантовый алгоритм, способный находить простые делители больших чисел за полиномиальное время. На этом алгоритме ломается основа протокола RSA. Защита RSA опирается на то, что перемножить два простых числа длиной в 1024 или 2048 бит легко, а восстановить эти множители обратно по их произведению обычным кремниевым чипам потребуются миллионы лет.

Шор доказал, что факторизацию чисел можно свести к поиску периода математической функции в модульной арифметике. Квантовое преобразование Фурье вычисляет период такой функции почти мгновенно за счет конструктивной квантовой интерференции. Алгоритм отсекает ошибочные результаты и резко увеличивает вероятность появления правильного ответа при измерении состояния системы.

• Классический суперкомпьютер взламывает ключ RSA-2048 через обобщенный метод решета числового поля за тысячи лет непрерывных вычислений
• Квантовый компьютер с достаточным числом стабильных кубитов справится с ключом RSA-2048 за считанные часы или даже минуты
• Криптосистема на эллиптических кривых ECC-256 требует еще меньше логических кубитов для полного вычисления закрытого ключа через решение задачи дискретного логарифмирования

Алгоритм Гровера против сохраненных хэшей

В 1996 году Лов Гровер придумал квантовый алгоритм для поиска данных в неупорядоченной базе. Обычному серверу для поиска нужного элемента среди N вариантов требуется в среднем N пополам операций. Алгоритм Гровера находит решение за корень квадратный из N шагов. Это фундаментальное квадратичное ускорение.

Если злоумышленник украл базу данных сайта с хэшированными паролями, алгоритм Гровера превращает перебор длинного пароля в гораздо более простую задачу. Он фактически уменьшает эффективную криптостойкость шифра вдвое. Симметричный ключ длиной 128 бит обеспечивает сложность взлома 2 в степени 64 операций, что вполне достижимо для мощных вычислительных систем. При этом ключ длиной 256 бит под алгоритмом Гровера опускается до надежности 128 бит, оставаясь безопасным на долгие десятилетия вперед.

Сценарий взлома личного аккаунта шаг за шагом

Если бы злоумышленник получил доступ к масштабируемому квантовому устройству, сценарий кражи учетной записи выглядел бы следующим образом.

1. Перехват транзитного интернет-трафика между твоим устройством и веб-сервисом в момент начала TLS-сессии
2. Применение квантового алгоритма Шора к открытому ключу сервера для мгновенного вычисления закрытого ключа
3. Расшифровка сессионного симметричного ключа прямо в момент установки соединения
4. Чтение данных авторизации в открытом виде, включая логин, пароль и одноразовые токены сессии
5. Вход в учетную запись от твоего имени без необходимости взламывать локальные базы данных или сами устройства

Главные трудности на пути квантового превосходства

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

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

Как мир готовится защищать пароли уже сейчас

Индустрия информационной безопасности готовится к переходу на постквантовую криптографию. Это математические алгоритмы, которые работают на обычных кремниевых процессорах, но опираются на задачи, не поддающиеся быстрому решению ни алгоритмом Шора, ни алгоритмом Гровера.

Национальный институт стандартов и технологий США (NIST) вел отбор постквантовых алгоритмов с 2016 по 2024 год. В число новых стандартов вошли системы на основе многомерных криптографических решеток, например ML-KEM для обмена ключами и ML-DSA для создания цифровых подписей. Квантовые компьютеры не дают преимущества при взломе решеточных структур, поэтому обновленные протоколы TLS сохранят безопасность данных в глобальной сети.