Опасен ли квантовый компьютер для Биткойна?

Благодаря недавней утечке от Сноудена, мы узнали, что Агентство Национальной Безопасности (АНБ) строит квантовый компьютер. Газета «Вашингтон Пост» опубликовала историю под довольно сенсационным заголовком – «АНБ ищет возможности построить квантовый компьютер, который сможет взломать большинство типов шифрования».

Естественно, это вызвало большой интерес на основных биткойн-форумах, а также в посвященных Биткойну группах на Reddit и Facebook. На самом же деле, мы не узнали ничего особо нового. О соответствующем проекте АНБ было известно давно, различные виды квантовых вычислений интересуют их изначально. Мы знаем, что на этот проект был выделен бюджет в 79.7 миллиона долларов США, но реальные достижения по-прежнему очень малы. И, как правильно заметил один из комментаторов:  «Никогда не поверю, что АНБ уже получила в своё распоряжение нечто подобное, и никто в мире об этом не узнал».

Что это за кубиты такие?

Тем не менее, воспользуемся случаем и обсудим перспективы квантовых вычислений применительно к Биткойну. Позвольте мне привести маленький пример для тех, кто не особенно в курсе квантовых вычислений и недоумевает: о чем, собственно, речь? Современные компьютеры имеют дело с информацией в виде битов — бинарных цифр, только «0» или «1». Эти биты обычно хранятся на жёстких дисках ваших компьютеров. В этом случае они представляют собой полярность намагничивания крошечных частиц магнитного диска.  Если же данные хранятся в оперативной памяти или флеш-памяти, они кодируются двумя различными уровнями заряда мини-конденсатора.

Строка битов может нести информационное наполнение, полезное для человека. Например, 01000001 соответствует букве «A» в расширенной таблице ASCII. При любых расчетах с битами делается одна операция за раз.

Основанные на фотонах квантовые компьютеры используют различные состояния квантовых частиц, чтобы получить так называемые “квантовые биты” (кубиты). Например, фотон, который вращается по вертикальной оси, может обозначать «1», а при вращении по горизонтальной оси фотон будет обозначать «0». В отличие от обычных битов, которые могут представлять лишь значения “0” или “1”, но не то или другое сразу, кубиты обладают одним довольно странным свойством, которое называется  «суперпозиция». Оно означает, что лежащий в основе кубита фотон может вращаться по всем осям — одновременно. То есть кубит может в моменте представлять значение и 0, и 1, и любое их сочетание. Не спрашивайте меня, как именно, это может объяснить разве что профессор квантовой физики, да и то не каждый день.

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

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

Атака перебором: силенок не хватит

Рассмотрим атаку, которая приходит на ум большинству людей при упоминании квантовых компьютеров — атаку путём простого перебора (bruteforce). Это значит, что вы раз за разом пробуете все возможные ключи, пока не получите правильный. Если у вас есть достаточно времени, вы можете подобрать любой пароль. Проблема состоит в том, что при обычных вычислениях потребуются многие миллиарды, нет, триллионы лет вычислений самого новейшего суперкомпьютера, чтобы получить нужный ключ путём перебора. Но, может быть, квантовый компьютер сделает это быстрее?

Обратимся к книге известного эксперта Брюса Шнайера «Прикладная Криптография»:

Одно из следствий из второго закона термодинамики состоит в том, что для представления единицы информации нужно определённое количество энергии.
Запись единичного бита путём изменения состояния системы потребует энергии не менее чем kT, где «T» это абсолютная температура системы и «k» это константа Больцмана.

При постоянной k = 1.38×10^-16 эрга/°Кельвин, и средней температуре во Вселенной в 3.2° Кельвина, наш идеальный компьютер будет работать при 3.2°K. При этом он будет потреблять 4.4×10^-16 эрга каждый раз, когда он изменит состояние одного бита. Запуск компьютера при температурах более низких потребует дополнительного расхода энергии для теплового насоса.

Годовая энергия, излучаемая Солнцем, равняется 1.21×10⁴¹ эрга. Этого достаточно, чтобы обеспечить 2.7×10⁵⁶ переключений бита идеального компьютера; то есть, этого достаточно для перебора 187-битного шифрования за год. Хорошо. Предположим, мы построим сферу Дайсона вокруг Солнца и будем улавливать и копить ВСЮ солнечную энергию 32 года подряд, без каких любо потерь. В этом случае, мы сможем обеспечить энергией компьютер, который позволит нам досчитать до 2¹⁹². Заметим, что это мы просто перебираем биты. У нас не останется энергии ни на что другое, чтобы совершать с этими битами хоть какие-либо полезные вычисления.

Предположим, мы не ограничимся и нашим Солнцем. Обычная сверхновая дает что-то вроде  10⁵¹ эрг (при этом в сотни раз большее количество энергии выделяется в виде нейтрино, её мы не учитываем из-за практических сложностей конвертации этой энергии). Если вся эта энергия пойдёт на одну сверхбольшую вычислительную оргию, мы сможем перебрать 219-битный ключ полностью, от начала и до конца.

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

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

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

Подрываем основы математики

Сегодня большинство алгоритмов шифрования с открытым ключом опираются на алгоритм «целочисленной факторизации» (RSA) или «дискретные логарифмы» (DSA, а также криптография на эллиптических кривых). В 1994 математик Питер Шор продемонстрировал эффективный квантовый алгоритм для решения задач факторизации и вычисления дискретных логарифмов. Этот алгоритм позволит довольно эффективно раскрывать шифрование с открытым ключом при использовании квантового компьютера. Но это не относится ко всем видам криптографии. Скажем, криптография с симметричным ключом, а также криптографические функции хэширования находятся вне зоны действия квантовых алгоритмов поиска.

Биткойн использует сразу несколько криптографических алгоритмов: алгоритм цифровой подписи на эллиптической кривой (ECDSA) для подписи транзакций и две хэширующие функции –  SHA-256 и RIPEMD160. Если АНБ в итоге преуспеет в создании применимого для нужд криптографии квантового компьтера, ECDSA будет скомпрометирован, в то время как  SHA-256 и RIPEMD160 по-прежнему сохранят свои защитные функции.

Хорошие новости состоят в том, что ECDSA, если он будет скомпрометирован, можно сравнительно легко заменить чем-то другим. Гораздо хуже, если удастся подобрать ключ к SHA-256. Напомним, что согласно устройству сети Биткойн, именно SHA-256 используется в процессе Биткойн-майнинга.

На сегодняшний день, миллиарды долларов вложены в чипы, которые не делают ничего, кроме вычислений SHA-256. Если SHA-256 потеряет актуальность, такие востребованные сейчас чипы и основанные на них ASIC-майнеры станут просто никому не нужным железом. Катастрофические последствия возникнут, если это произойдёт внезапно, и ни у кого не будет времени подготовиться. Ведь безопасность сети Биткойн полагается на сложность и дороговизну проведения атаки, позволяющей захватить 51% вычислительной мощности сети. Внезапная замена хэш-функции (скажем, на Scrypt, или что-то другое) приведет к серьезному падению безопасности сети на время переходного периода.

Но хотя (теоретически) какие-то угрозы для SHA-256 и могут существовать, применение квантовых компьютеров, к счастью, к ним совершенно не относится.

Шеф, усё пропало?

Давайте вернёмся к ECDSA, который может быть теоретически взломан достаточно мощными квантовыми компьютерами. Этот алгоритм генерирует пару ключей:  закрытый/открытый ключ.

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

В случае Биткойна, ваш “открытый ключ” изначально не является таким уж открытым. Вместо него используется так называемый “биткойн-адрес”, который представляет собой лишь хэш открытого ключа. Предоставляя свой биткойн-адрес другим людям, чтобы они вам отправили средства, вы даёте им только хэш вашего открытого ключа, но не сам ключ. Хэш — это результат работы криптографической функции хэширования. Данная функция является односторонней и не может быть взломана квантовым компьютером.

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

Привет Мир ==> a830d7beb04eb7549ce990fb7dc962e499a27230

Адрес биткойна рассчитывается путем пропускания вашего открытого ключа сразу через несколько криптографических функций хеширования:

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

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

Если вы не переместите баланс с этого прежнего адреса, АНБ может при помощи квантового компьютера подобрать к нему секретный ключ и украсть всё, что на нём есть. Хотя это и будет не совсем удобно для пользователей, биткойн-разработчики в любом случае получат достаточно времени, чтобы заменить ECDSA на одну из устойчивых к квантовым расчётам схем цифровой подписи, например, подпись Лэмпорта.

Морально Квантово устойчивые подписи

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

Схема одноразовой подписи Лэмпорта (LOTSS)

Для начала мы возьмем хэширующую функцию длиной  в 160-бит, чтобы обеспечить должную безопасность. RIPEMD160 или SHA-1 вполне подойдут. Чтобы получить пары открытый/закрытый ключ, мы создадим 160 пар случайных чисел (320 чисел всего). Этот набор случайных чисел будет служить нашим секретным ключом.

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

А сейчас мы подпишем некий текст подписью Лэмпорта. Для этого мы сначала создадим дайджест этого текста, хэшировав его с помощью RIPEMD160 (в Биткойне используется этот же алгоритм для хэширования транзакции), и транслируем полученный результат в двоичный код. Мы и в этот раз используем «Привет Мир» в качестве примера.

Привет Мир ==> a830d7beb04eb7549ce990fb7dc962e499a27230 ==> 1010100000110000110101111011111010110000010011101011011101010100100111001110100110010000111110110111110111001001011000101110010010011001101000100111001000110000

Далее мы последовательно сопоставим двоичные цифры полученного кода с парами чисел из закрытого ключа (предыдущая таблица). Если бит равен 0, мы добавим первое число к цифровой подписи, а если он равен 1, то второе.

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

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

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

Не меньшей проблемой является то, что размеры ключей и подписи крайне велики. И закрытый, и открытый ключ занимают аж по 6400 байтов. Сравните – 32 и 64 байта для закрытого и открытого ключей ECDSA. И подпись занимает 3200 байтов, а не 71-73 байта. Биткойн уже и так имеет проблемы с масштабируемостью. Повышение размеров ключа и подписи только усугубит эту проблему.

Правда, приватный ключ Лэмпорта можно значительно уменьшить в размере, используя генерацию случайных цифр из одного набора. Для этого мы используем RIPEMD160 (размер набора + n), где n первоначально установлено в 1 и последовательно увеличивается до 320.

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

Схема подписи Мёркле (MSS)

Схема подписи Мёркле объединяет в себе схему одноразовой подписи (неважно, схему Лампорта или Винтерница) с деревом Мёркле (также известным как дерево хэшей). Это позволяет нам подписать одним открытым ключом несколько сообщений, не создавая ущерба их безопасности. Давайте посмотрим, как это работает.

Мы начнём с создания пар ключей Лампорта. Количество ключей, которые нам понадобится, будет равно числу подписей, которые мы хотим получить из одного открытого ключа. Давайте, например, возьмём восемь подписей. Затем мы вычислим дерево Мёркле с помощью каждого из восьми открытых ключей Лампорта. Чтобы сделать это, объединим открытые ключи попарно. Затем полученные хэши перемешиваются и хэшируются снова. Этот процесс чем-то похож на определение победителя футбольного чемпионата.

Хэш находится на самом верху дерева (дерева Мёркле), в то время как корнем дерева является открытый ключ Мёркле. Это заметно сокращает размер открытого ключа — с 6400 байтов, необходимых для подписи Лампорта до длины одного RIPEMD160 хэша — 20 байт.

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

Для схемы, приведённой выше, подписью будет:

sig′||H(Y[i=2])||A[0]||auth[0]||A[1]||auth[1]||A[2]||auth[2]||A[3]

Для проверки подписи Мёркле достаточно просто проверить подпись Лампорта, а затем убедиться, что хэш листьев дерева Мёркле соответствует хэшу публичного ключа. Если это так, подпись действительна.

У данной схемы есть ряд преимуществ по сравнению с LOTSS. И открытый, и закрытый ключи сокращены с 6400 байт до 20 байт. Таким образом, вы можете создать несколько подписей для одного открытого ключа.

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

Святой Грааль криптографии: CMSS/GMSS

Устойчивая к квантовым расчётам криптография MSS известна уже более 30 лет. Она, по сути, осталась невредимой, несмотря на интенсивный криптоанализ. Однако большинство улучшений этой схемы произошли в последние пять лет. Наиболее перспективно выглядят две схемы парной подписи, разработанные группой Дахмена, Клицевич и Бахмана.

Эти схемы – улучшенная схема подписи Мёркле (CMSS) и обобщённая схема подписи Мёркле  (GMSS).

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

Как CMSS, так и GMSS имеют расширенную устойчивость подписи в сочетании с разумным временем проверки и разумной длиной подписи. GMSS предлагает схему с 280 подписями, зато имеет более низкую производительность в сравнении с CMSS. Задача решается разбиванием на отдельные деревья Мёркле с 2ⁿ листьев. Подпись из корня дерева используется для подписи открытого ключа, а ключ используется для создания по тому же принципу следующих деревьев.

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

Будут ли данные схемы практичными в использовании? Давайте сделаем небольшое сравнение. Взглянем на время (t) и требования к памяти (m) для каждого алгоритма. CMSS имеет варианты 2²⁰, 2³⁰, и 2⁴⁰ , а вот GMSS может обеспечить длину подписи в 2⁴⁰ и 2⁸⁰.

Я бы предложил 2⁴⁰ и даже 2³⁰, этого будет вполне достаточно для Биткойн. Просто не могу представить кого -либо, кому понадобится совершать миллиарды и даже триллионы транзакций с одного биткойн-адреса. Также GMSS можно оптимизировать для ускорения времени верификации, правда, это на 25% увеличит размер подписи.

Таким образом, мы видим из таблицы, что CMSS и GMSS обеспечивают лучшую производительность, чем ECDSA по таким параметрам как размер публичного ключа и время подписи. Тем не менее, те критичные для нас переменные, которые влияют на масштабируемость системы и размер подписи, не работают так хорошо, как нам хотелось бы. Время проверки у CMSS заметно лучше, чем у ECDSA. Похожие показатели времени проверки и оптимизированного варианта GMSS. Это реально может улучшить масштабируемость. А вот размер подписи у обеих определённо вызывает вопросы. Рассмотрим некоторые очень грубые оценки: в то время как размер транзакции сейчас – около 500 байт, CMSS или GMSS будет занимать около 4000 байт. Это означает, что для нас все новые транзакции блокчейна увеличатся на 700%. Блокчейн на сегодняшний день и так уже занимает 12.7 гигабайт.

Выдержит ли Биткойн такое большое счастье?

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

Прошу заметить также, насколько велико при использовании GMSS время генерации кошельков. Полностью загрузите компьютер на целых 24 часа и вам удастся генерировать только 3 биткойн адреса. И это в случае использования оптимизированного варианта алгоритма, с увеличенными подписями!

Однако в этом есть и положительная сторона – подобного рода схема будет крайне устойчива к bruteforce-атакам (подбору ключей). Думаю, ускорить эти операции нам сможет помочь специальное ASIC-оборудование. А вот у CMSS показатели генерации кошельков не настолько уж плохи.

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

Источник: bitcoinnotbombs.com Автор: Chris