Обнаружена уязвимость Биткойна: угроза квантовых вычислений может опустошить кошельки менее чем за 10 минут

В первой части этой серии объясняется, что на самом деле представляют собой квантовые компьютеры. Не просто более быстрые версии обычных компьютеров, а принципиально иной тип машины, использующей странные правила физики, применимые только в масштабе атомов и частиц.

Но знание того, как работает квантовый компьютер, не говорит вам, как злоумышленник может использовать его для кражи биткойнов. Для этого необходимо понять, что на самом деле он атакует, как построена безопасность Биткойна и в чем именно заключается его слабость.

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

Карта с односторонним движением

Биткойн использует систему, называемую криптографией эллиптических кривых, чтобы доказать, кто чем владеет. У каждого кошелька есть два ключа. Закрытый ключ, представляющий собой секретное число длиной 256 цифр в двоичном формате, примерно такой же длины, как это предложение. Открытый ключ получается из закрытого ключа путем выполнения математической операции над определенной кривой, называемой «secp256k1».

Думайте об этом как о карте с односторонним движением. Начните с известного места на кривой, с которым все согласны, и которое называется образующей точкой G (как показано на диаграмме ниже). Сделайте определенное количество шагов по шаблону, определенному математическими расчетами кривой. Количество шагов — это ваш приватный ключ. Там, где вы окажетесь на кривой, находится ваш открытый ключ (точка K на диаграмме). Любой может подтвердить, что вы оказались именно в этом конкретном месте. Никто не может сосчитать, сколько шагов вы сделали, чтобы туда добраться.

Технически это записывается как K = k × G, где k — ваш закрытый ключ, а K — ваш открытый ключ. «Умножение» — это не обычное умножение, а геометрическая операция, при которой вы неоднократно добавляете точку к самой себе вдоль кривой. Результат попадает в, казалось бы, случайное место, которое может дать только ваше конкретное число k.

Важнейшее свойство состоит в том, что движение вперед легко, а движение назад для классических компьютеров фактически невозможно. Если вы знаете k и G, вычисление K займет миллисекунды. Если вы знаете K и G и хотите вычислить k, вы решаете то, что математики называют проблемой дискретного логарифмирования эллиптической кривой.

Подсчитано, что самые известные классические алгоритмы для 256-битной кривой займут больше времени, чем возраст Вселенной.

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

Алгоритм Шора открывает дверь в обе стороны

В 1994 году математик Питер Шор открыл квантовый алгоритм, который взламывает люк.

Алгоритм Шора эффективно решает задачу дискретного логарифмирования. Та же самая математика, которая заняла бы у классического компьютера больше времени, чем существует Вселенная, алгоритм Шора обрабатывает то, что математики называют полиномиальным временем, что означает, что сложность растет медленно по мере увеличения чисел, а не взрывным образом.

Интуитивное представление о том, как это работает, возвращается к трем квантовым свойствам из первой части этой серии.

Алгоритму необходимо найти ваш закрытый ключ k по вашему открытому ключу K и точке генератора G. Он превращает это в задачу нахождения периода функции. Представьте себе функцию, которая принимает на вход число и возвращает точку на эллиптической кривой.

Когда вы передаете ему последовательные числа 1, 2, 3, 4, выходные данные в конечном итоге повторяются в цикле. Длина этого цикла называется периодом, и как только вы узнаете, как часто функция повторяется, математические решения задачи дискретного логарифма решаются за один шаг. Приватный ключ выпадает практически сразу.

Нахождение этого периода функции — это именно то, для чего созданы квантовые компьютеры. Алгоритм помещает свой входной регистр в суперпозицию (или, в квантовой механике, частица существует в нескольких местах одновременно), представляя все возможные значения одновременно. Он применяет функцию ко всем из них одновременно.

Затем он применяет квантовую операцию, называемую преобразованием Фурье, которая приводит к сокращению количества неправильных ответов и усилению правильных ответов.

Когда вы измеряете результат, появляется период. За этот период обычная математика восстанавливает k. Это ваш закрытый ключ и, следовательно, ваши монеты.

В атаке используются все три квантовых трюка из первой части. Суперпозиция оценивает функцию сразу на всех возможных входных данных. Запутывание связывает входные и выходные данные, поэтому результаты остаются коррелированными. «Интерференция» фильтрует шум до тех пор, пока не останется только ответ.

Почему биткойн все еще работает сегодня

Алгоритм Шора известен более 30 лет. Причина, по которой Биткойн все еще существует, заключается в том, что для его работы требуется квантовый компьютер с достаточно большим количеством стабильных кубитов, чтобы поддерживать согласованность на протяжении всего расчета.

Создать такую ​​машину было невозможно, но вопрос всегда заключался в том, насколько она «достаточно велика».

Предыдущие оценки