Квантовый PC vs обычный ПК
Сможет ли квантовый компьютер сломать шифрование и защиту Биткоина?
Для начала необходимо понимать, чем отличается квантовый компьютер от обычного и почему он настолько мощнее, чем обычный.
Объясним очень простыми словами, чтобы каждый смог понять отличие.
Стандартные компьютеры выполняют операции, используя обычные биты, которые могут равняться либо нулю, либо единице.
Квантовые компьютеры, используют квантовые биты или же кубИты. Кубиты могут одновременно быть и единицей, и нулем, что называется суперпозицией.
Именно это дает квантовому компьютеру такую вычислительную мощность.
Говоря еще проще, обычный компьютер, чтобы сделать 100 условных вычислений, должен проделать 100 операций одну за другой.
Квантовый же компьютер сможет за один раз, одновременно проделать все 100 вычислений.
Благодаря суперпозиции кубит может принимать значения, полученные путем их комбинирования, и находиться во всех этих состояниях одновременно. В этом заключается параллельность квантовых вычислений, то есть отсутствие необходимости перебирать все возможные варианты состояний системы.
Чем больше кубит в квантовом компьютере, тем больше параллельных вычислений он может проделывать.
Более подробно углубляться в квантовую механику мы не станем, так как цель этой статьи немного другая, но общий принцип работы квантового компьютера вы поняли.
Bitcoin и квантовые компьютеры
Теперь, давайте перейдем к тому, как Квантовый компьютер может взломать систему Биткоина.
Теоретически, квантовый компьютер сможет подбирать приватный ключ по известному публичному ключу. Так как публичный ключ получен из приватного через алгоритм эллиптической кривой ECDSA, на подбор приватного ключа из публичного, обычному компьютеру потребовалось бы несколько триллионов лет.
Квантовый сможет сделать это относительно быстро.
Но публичный ключ это не Биткоин адрес, который используется для получения Биткоинов.
Биткоин адрес генерируется через ХЭШ функцию RIPEMD-160 и SHA-256 из публичного ключа и этот процесс необратим даже для квантового компьютера. Из Биткоин адреса невозможно получить публичный ключ, так как HASH функция необратима.
Соответственно, не зная публичного ключа, даже квантовый компьютер не сможет рассчитать приватный ключ из Биткоин Адреса.
Но при подписании исходящих транзакций, публиный ключ все-же записывается в блокчейн и доступен для просмотра каждому, поэтому уязвим для квантовых вычислений.
Если же вы перевели Биткоины на адрес, ранее вами не используемый, то его публичный ключ не будет виден в блокчейне, так как с этого адреса не производились транзакции.
А если неизвестен публичный ключ, то приватный ключ квантовый компьютер высчитать не сможет.
Появляется и другая проблема – с временем создания нового блока. В сети Биткоин новый блок создается каждые 10 минут. И пока новые транзакции не имеют ни одного подтверждения, квантовый компьютер может высчитать приватный ключ из публичного и переотправить транзакцию на адрес злоумышленника с большей комиссией.
Таким образом, использование новых адресов не решит проблему полностью. Сейчас, по статистике 41% адресов Биткоина используются повторно.
А промежуток в 10 минут между созданием нового блока ставит под угрозу безопасность платежей.
Проблема с получением приватного ключа из публичного довольно легко решается переходом на другой алгоритм защиты.
Биткоин имеет обновляемый код, в который с момента создания было внесено достаточно много полезных обновлений, например, Lightning Network и SegWit.
Чтобы защититься от квантового компьютера, необходимо лишь обновить систему защиты Биткоина и начать использоваться постквантовую криптографию, например, основанную на ХЭШ функциях.
Один из таких методов защиты, это заменить алгоритм ECDSA на подпись ЛЭмпорта. Это криптосистема подписи с открытым ключом, которая может быть построена на использовании любой односторонней ХЭШ функции.
Биткоин сейчас использует несколько криптографических алгоритмов: Алгоритм ECDSA, ХЭШ функцию SHA-256 и ХЭШ функцию RIPEMD160. Квантовый компьютер сможет взломать лишь алгоритм ECDSA, который можно спокойно заменить на подпись Лэмпорта или на дерево Меркла, и на еще несколько других вариантов подписи.
Но подпись Лэмпорта очень длинная и весит достаточно много.
Это может привести к быстрому заполнению блока и уменьшению пропускной способности сети Биткоина.
Давайте рассмотрим еще несколько вариантов подписей, устойчивых против квантовых вычислений.
Подпись Винтерница. (VIternicz)
В подписи Винтерница, в отличие от подписи Лэмпорта, исходное сообщение подписывается не побитово, а блочно.
Одноразовая подпись Винтерница, как и Лэмпорта, может быть построена на основе любой стойкой криптографической функции.
Размеры открытого ключа и подписи, при тех же параметрах, что и для подписи Лэмпорта, равны 1 КБ. В сумме это меньше, чем в подписи Лэмпорта (24 КБ).
Однако, количество операций вычисления хеша при этом составляет 8160.
Что, несомненно, очень много.
Дерево Меркла(MSS)
Одноразовые подписи способны обеспечить удовлетворительную криптографическую безопасность, однако, именно их одноразовость может стать серьезной проблемой.
Допустим, необходимо передать сбережения с одного адреса на другой. При этом получается, что при использовании одноразовых подписей необходимо будет каждый раз переводить весь объем средств, и для проведения каждой транзакции нужен будет новый адрес.
С каждой транзакцией нужно будет публиковать новый открытый ключ.
Кроме того, сохранение в блокчейне новых транзакций постепенно будет требовать все больше времени на их поиск.
Для решения проблемы расширяют схему подписи за счет проведения нескольких подписываний на основе нескольких пар ключей для каждого адреса.
Использование нескольких подписей выполняют на базе двоичного хеш-дерева — дерева Меркла.
При использовании одноразовых подписей Меркла или Винтерница нет необходимости передавать отдельно выбранный одноразовый открытый ключ, поскольку его можно получить из подписи сообщения.
Достаточно передать его номер, отражающий его положение в дереве.
Основным недостатком базовой схемы Меркла является то, что количество доступных подписей ограничено, и все пары ключей одноразовых подписей должны быть сгенерированы до вычисления дерева Меркла.
Но эту проблему решает использование гипердрева.
Расширенная структура дерева меркла (XMSS)
Схема XMSS как и дерево Меркла позволяет расширять одноразовые подписи.
Применяется схема на основе алгоритма расширенной подписи Винтерница на базе связных структур Меркла (связные XMSS).
Данная схема обеспечивает 196-битную защиту, что обеспечивает высочайшую защиту от перебора квантовыми компьютерами.
Как видите, методов защиты от квантовых компьютеров достаточно много и написаны целые книги про постквантовую криптографию.
Все, что необходимо сделать Биткоину для защиты от квантовых компьютеров – это провести софтфорк и ввести обновление для подписи транзакций. Даже стандартная подпись Лэмпорта уже подойдет для защиты от квантового перебора, а проблему с масштабируемостью биткоина определенно решат в блищайжем будущем.
Теперь назревает вопрос:
Почему Квантовый компьютер сможет взломать ECDSA алгоритм, а SHA-256 и RIMEPD-160 не сможет?
Алгоритм ECDSA опирается на следующее утверждение: Сложность разложения числа на простые множители растет экспоненциально от размера ключа.
Данное утверждение справедливо лишь для классических компьютеров, но несправедливо для квантовых.
Используя Алгоритм Шора на квантовом компьютере можно разложить число на простые множители за достаточно приемлемое время.
Именно это позволяет найти приватный ключ из публичного ключа. Но алгоритм SHA-256 спокойно противостоит квантовым вычислениям.
Используя Алгоритм Гровера, для взлома SHA-256, квантовому компьютеру потребуется 2^166 логических циклов кубита, или же 10^32 лет.
Это намного больше, чем те 14 миллиардов лет, которые существует вселенная.
Теперь перейдем к самому интересному.
BTC безопасен перед квантовыми компьютерами?
Допустим, что будет создан квантовый компьютер, который сможет взломать ECDSA алгоритм.
Первым под удар попадет не Биткоин, а банковские системы, почтовые сервисы, спецслужбы, крупные корпорации в общем все, что использует алгоритм шифрования, неустойчивый к квантовым вычислениям.
Появление достаточно мощного квантового компьютера отразится на всей информационной системе, использующей асимметричное шифрование.
Квантовые компьютеры уже сейчас существуют и максимальное количество кубит – 51. Этого абсолютно недостаточно для вычисления приватного ключа из публичного.
Тем более, текущие квантовые компьютеры предназначены для выполнения определенных минимальных функций на основе готовых данных. Ни о каком переборе ключей и речи быть не может.
Многие сейчас могут упомянуть квантовый компьютер от компании Dwave, который содержит якобы 2000 кубит.
Но квантовый компьютер от компании DWave не совсем квантовый. Система D-Wave — это не компьютер общего назначения.
Он способен решать лишь определенные задачи на базе алгоритмов модели Изинга.
Этот компьютер используется как «система для оптимизированных решений» таких проблем, как расчет наиболее эффективного использования ресурсов (времени и топлива, например) при наличии различных сценариев проблемы.
Как говорит Грег ТАллант: «В этом ключе можно говорить лишь о квантовом отжиге. Мы вносим в машину задачи, ответы на которые нам известны. После этого загружаем в нее задачи, ответы на которые нужно будет найти. После чего мы попробуем совместить информацию обеих задач. В конечном итоге на основе решений-кандидатов мы сможем получить ответ на нашу задачу».
D-wave это установка квантового отжига, а не полноценный квантовый компьютер. Система способна справляться лишь с ограниченным числом задач. Нынешние квантовые компьютеры абсолютно не угрожают текущей асимметричной криптографии и не смогут угрожать еще несколько десятков лет.
Давайте подведем небольшой итог:
• Теоретически, квантовый компьютер сможет взломать ассиметричные системы шифрования
• В случае возникновения минимальной угрозы квантового перебора, что произойдет минимум лет через 20 — Биткоин может обновить алгоритм цифровой подписи на постквантовый и квантовый компьютер никак не сможет взломать биткоин.
• Появление квантового компьютера никак не повлияет на майнинг Биткоина вообще, так как это устройство другого класса, не предназначенное для майнинга.
Для подсчета ХЭШЕЙ квантовый компьютер не подойдет, так как его придется согласовывать с классической электроникой, а это сильно уменьшит производительность.
• Появление рабочего квантового компьютера, способного использовать алгоритм шора для взлома асимметричного шифрования спровоцирует переход всей системы на постквантовую криптографию.
• Полноценный универсальный квантовый компьютер пока является гипотетическим устройством.
На данный момент существуют лишь устройства квантового отжига, на которых реализованы лишь единичные экспериментальные системы, исполняющие фиксированный алгоритм небольшой сложности.Готового, рабочего квантового компьютера пока что нет, и не будет еще несколько десятков лет.
Так что квантовый компьютер, который взломает алгоритм ECDSA – это из раздела фантастики на ближайшие 20 лет.