Могут ли квантовые компьютеры навредить Биткойну?

Могут ли квантовые компьютеры навредить Биткойну? Конечно же, криптография на эллиптических кривых тщательно исследуется с того времени, как как тема квантовых компьютеров стала мэйнстримом. Стоит напомнить, что Биткойн построен так, чтобы исключить необходимость в доверии посредством криптографического доказательства. Но, это относится не только к биткойнам. Двумя наиболее распространёнными криптографическими алгоритмами являются Rivest-Shamir-Adleman (RSA) и криптография на эллиптических кривых (ECC). И, как правило, информация, которой вы обмениваетесь по сети зашифрована с помощью RSA или ECC. Но, эти системы уязвимы перед атаками квантовых компьютеров. Достаточно мощный квантовый компьютер может стать проблемой безопасности для любого онлайн-взаимодействия.

От переводчика:

Квантовый компьютер – вычислительное устройство, которое использует явления квантовой механики для передачи и обработки данных. Квантовый компьютер, в отличие от обычного, оперирует не битами – способными принимать значение либо 0, либо 1, а кубитами, имеющими значения одновременно и 0, и 1. Теоретически, это позволяет обрабатывать все возможные состояния одновременно, достигая существенного превосходства над обычными компьютерами в ряде алгоритмов.

Шифрование сегодня и влияние Шора

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

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

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

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

Прим. переводчика. В 1994 американский математик Питер Шор открыл квантовый алгоритм, который превзошёл классические аналоги.   

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

Подробнее о закрытых и открытых ключах

Читать больше: Биткойн: введение для разработчиков

Нельзя кому-либо передавать закрытый ключ, т.к. он может использоваться для нежелательной транзакции [у вас могут украсть деньги]. В общем, поскольку квантовые компьютеры постоянно совершенствуются – безопасность RSA ставится под вопрос.

RSA существует с 1977 года и используется по сей день. Позднее, было рекомендовано использовать ECC, т.к. там более короткие ключи и выше скорость. Однако, ECC также уязвима для квантового алгоритма Шора.

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

В 2015 году из-за опасений подобных атак – АНБ заявило, что планирует заменить рекомендованные шифры из списка Suite B на «квантово-стойкие» алгоритмы. В январе 2019 года NIST [Национальный Институт стандартов и технологий США] опубликовал список из 26 алгоритмов, которые могут противостоять атакам квантовых компьютеров. И хотя несколько из них действительно являются достойными кандидатами, и просто стоит выбрать лучший – криптовалюты имеют довольно специфическую архитектуру и различные стандарты, что значительно усложняет переход.

Какая мощность потребуется квантовому компьютеру, чтобы разрушить Биткойн?

Насколько мощным должен быть этот «квантовый убийца Биткойна»? В Microsoft Research заявили [август, 2018], что для взлома дискретных логарифмов на эллиптических кривых потребуется меньшее количество кубитов нежели для 2048-битного ключа RSA, для которого требуется не менее 4000 кубитов.

Прим. переводчика. 4096 кубитов, если точнее. В 2015 году количество кубитов для взлома 2048-битного ключа RSA оценивалось в 1 млрд…

Однако, это идеальные «логические» кубиты. Для исправления ошибок и других необходимых процессов потребуется ещё много физических кубитов.

Через какой период Биткойн будет взломан. John Smith; https://twitter.com/JSmith_Crypto/status/1156539778667601921

Хотя, для стандартного 256-битного ключа нужно около 2500 кубитов. И всё же, Джон Прескилл [John Preskill] в своей лекции по квантовой информации, отметил, что [для полноценного результата] квантовым компьютерам потребуется около 10 млн физических и 10 тыс логических кубитов.

В общем, современные квантовые технологии ещё далеки от этого. Не так давно, в конце 2017 года, в IBM объявили, что смогли создать систему с 50 кубитами, а в начале 2018 года – в Google анонсировали систему с 72 кубитами. В свою очередь, компания IonQ, используя ионные ловушки, представила квантовый компьютер со 160 кубитами и выполнила операции на 79 кубитах.

Дополнительно, компания DWave выпустила свою систему с 2048 кубитами, но, она основана на базе квантового отжига, и не может использовать алгоритм Шора. Однако, здесь, в конечном счёте, цель заключена в создании достаточно мощных квантовых компьютеров для целей науки: химии, оптимизации, машинного обучения.

И хотя до этого ещё далеко – это всё равно затронет те криптовалюты, которые на сегодня находятся в обращении.

Угроза квантового компьютера для криптовалют

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

Основная проблема заключена в том, что квантовый компьютер может высчитать закрытый ключ, которым подписывают транзакцию, на основе открытого ключа, который виден во время транзакции. Следовательно, есть возможно произвести несанкционированный расход [совершить кражу].

Как уменьшить подобную угрозу? Есть всего несколько слабых мест, которые потенциально позволяют квантовым компьютерам получить доступ к монетам.

Открытый ключ

Во-первых, злоумышленник должен получить открытый ключ. И хотя адрес кошелька основан на открытом ключе – он хэшируется алгоритмами, которые в настоящее время не подвержены атакам квантовых компьютеров. Однако, во время транзакции – открытый ключ виден.

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

Самый простой способ увидеть, что происходит в процессе транзакции – это посмотреть код в действии. Для этого можно использовать сервис pybitcointools:

Пошаговый алгоритм (кратко):

Создание приватного ключа

Генерация открытого ключа из закрытого ключа

Подпись транзакции закрытым ключом

Открытый ключ виден в коде транзакции

Отправка транзакции

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

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

Повторное использование адресов кошелька

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

Достаточно быстрые атаки

Но, даже если не использовать адреса повторно – всё ещё остаётся время для атаки во время проведения транзакции. Таким образом, пока транзакция не подтверждена – она остаётся уязвимой. И тем не менее, для квантового компьютера этого короткого времени достаточно чтобы перенаправить транзакцию.

Крейг Гидни и Мартин Экера опубликовали в мае 2019 года статью о том, как вычислить 2048-битные целые числа RSA за 8 часов, используя 20 млн кубитов.

Среднее время подтверждения биткойн-транзакции в июне 2019 года составляло 9,47 минут. Однако были периоды, когда среднее время подтверждения достигало 11453 минут – более 7 дней!

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

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

Потерянные монеты

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

При этом, некоторые биткойны давно потеряны – их владелец не имеет закрытого ключа, который необходим для совершения транзакций.

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

И если человек, который получит эти монеты – начнёт их продавать, то курс биткойнов может рухнуть, что подорвёт доверие к системе. Также, возникают дополнительные вопросы. Поскольку количество биткойнов ограничено, то стоит ли переиздать эти монеты? Или всё же общая капитализация снизится?

Переход к пост-квантовым алгоритмам

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

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

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

Например, в Fawkescoin пытаются решить эту проблему, демонстрируя, что распределённую сеть возможно реализовать с помощью симметричной криптографии. В свою очередь, другие монеты, такие как Quantum Resistant Ledger используют криптографию на основе хэша. Ведь алгоритмы на основе хэша до сих пор способны противостоять атакам квантовых компьютеров.

Взгляд на пост-квантовое будущее

Вообще-то, предсказать будущее технологий довольно трудно. И, вероятно, квантовые вычисления будут не единственной технологией, которая подвергнет риску безопасность криптовалют. Иногда требуется всего один технологический скачок, чтобы мы оказались там, где не предполагали оказаться. И, вполне возможно, что обновлять стандарты криптографии придётся несколько раз.

Одно из постоянных свойств технологий – это то, что всегда есть прогресс и новые прорывы, даже если мы не знаем, какими они будут. Не так давно, Zapata Computing опубликовала статью о вариационном квантовом факторинге, где могут использоваться гибридные (работающие с классическими компьютерами) устройства Noisy Intermediate Scale Quantum (NISQ) с сотнями кубитов для вычисления факторных чисел. Конечно, эта технология ещё толком не проверена и обладает ограничениями. Тем не менее, это подтверждает факт наличия множества возможностей для создания новых алгоритмов и проведения исследований, что может значительно ускорить прогресс.

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

Например, Google использует квантовое моделирование для изучения проблем эффективности производства удобрений, которые потребляют 1-2% энергии в мире.

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

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

Уже сейчас стоит задаться следующими вопросами: являются ли квантовые компьютеры угрозой для вашего криптовалютного портфеля? Возможно ли создание достаточно мощного квантового компьютера для эффективной атаки на Биткойн? Стоит ли начать беспокоиться об этом уже сейчас?

Автор: Anastasia Marchenkova

Источник: twitter.com

Комментарии: