Оригинал материала: www.computerra.ru/179897/matematika-protiv-loma-ili-bitkojn-kak-kvantovaya-kanarejka
7.04.2018
Математика против лома, или Биткойн как квантовая канарейка
Мы живём в удивительное время: впервые в истории ценность массово «переезжает» из физических хранилищ в виртуальные — криптовалюту, блокчейн. И это заставляет задуматься, насколько надёжно новое хранилище защищено. Пока речь шла о слитках, монетах, банкнотах, ценных бумагах, сохранность можно было обеспечить чисто физически — возведя стальные стены и поставив возле них вооружённую охрану. Но в криптовалютной реальности всё основано на математике.
В результате, говоря попросту, вор может опустошить чужой криптокошелёк не вставая с дивана — если только удастся отыскать в математике слабину. Хуже того, такие ограбления уже происходят, а прогноз на ближайшее будущее иногда звучит и вовсе катастрофический: вот появятся квантовые компьютеры, тогда вообще всем криптовалютам каюк. Давайте разберёмся, в чём состоит опасность и насколько она в действительности велика.
Прежде всего вспомним, как устроена самая популярная из криптовалют — Bitcoin (а по аналогии с ней и сотни других, отличающихся зачастую лишь значением переменных). Основа основ здесь: число длиной в 256 бит, сгенерировать которое для себя должен каждый пользователь. Это число можно представить как ключ к сейфу, где хранятся личные сбережения: им «подписывают» поручения, заносимые в блокчейн. Вот почему знать его должен только владелец. Его так и называют: приватный ключ.
Чтобы доказать окружающим, что приватный ключ у вас есть, но не раскрывать его, по приватному ключу вычисляют второе число — ключ публичный. Используемая при этом криптографическая функция (ECDSA, «эллиптическое крипто») такова, что «прокрутить» её в обратную сторону, то есть вычислить по публичному ключу приватный, намного труднее.
Наконец, есть ещё и третье число: так называемый «адрес кошелька». Оно нужно, чтобы принимать переводы от других пользователей. В принципе публичный ключ сам может служить адресом и в первые пару лет существования Bitcoin его так и использовали. Но сегодня адрес вычисляют: так удобней (он короче, всего 160 бит) и, как увидите, безопасней. Адрес получают из публичного ключа путём последовательного двукратного вычисления хэша (сперва SHA-256, потом RIPEMD-160).
Отсюда важный вывод. Чтобы увести деньги с произвольного кошелька Bitcoin, достаточно восстановить его приватный ключ. Не требуется вламываться в банк с оружием, рисковать жизнью, «ломать» чужие компьютеры. Всё, что нужно, это написать простую программу, которая путём перебора отыщет заветное число. Есть, правда, нюанс: число это имеет длину 256 бит, что означает, что при существующих мощностях вычислительной техники на его подбор уйдёт время, сопоставимое с временем жизни Вселенной. Спросите на любом форуме, если не верите, и вам замечательно, с математическими выкладками, это докажут.
Чего, вероятно, не знают авторы таких доказательств, так это того, что приватные ключи всё-таки подбирают. Уже!
Вот, взгляните на проект Large Bitcoin Collider (LBC). Суть, несколько упрощая: объединёнными усилиями коллектив единомышленников подбирает ключи к биткойн-кошелькам. Теория гласит, что на решение такой задачи нужны миллиарды лет. На практике же можно учесть две существенных поправки. Во-первых, из-за потери информации при генерации адреса (помните: 160 бит против 256?), каждому уникальному адресу Bitcoin соответствует не один, а 2^96 приватных ключей. Что означает, что перебрать требуется не 2^256, а только 2^160 вариантов. И во-вторых, число биткойн-адресов, использованных хотя бы однажды, каждые сутки прирастает на полмиллиона, а тенденция экспоненциальная.
В результате примерно каждые два месяца LBC находит очередной приватный ключ. И деньги, если только они в данном кошельке имеются и владелец не затребует их обратно, поступают в распоряжение участников этого «невозможного» проекта. А даже если владелец и затребует их обратно, LBC отстаивает право забрать себе 10% возвращаемой суммы — вроде как в качестве вознаграждения за пойманную чужую корову (скажите спасибо, что мы её привели, другие на шашлык пустили бы!).
Но как же так: с одной стороны миллиарды лет, с другой — два месяца?! Тонкость, конечно, в том, что речь идёт не о взломе конкретного кошелька, а о поиске случайных совпадений. Никто в LBC не знает, какой приватный ключ удастся подобрать следующим. Так что за свой персональный биткойн-кошелёк вы можете не переживать, его по-прежнему надёжно охраняет теория вероятностей: если кто-то на него нацелится, на подбор ключа уйдут (вероятно!) миллиарды лет. Однако всё может измениться с появлением квантового компьютера — подбирать с помощью которого приватные ключи станет очень легко, а потому чрезвычайно выгодно.
С квантовыми компьютерами (КК) связана отдельная интересная и свежая история. Дело в том, что официальные успехи строителей КК невелики. Грубо говоря, сегодня построены два типа таких компьютеров. Одни — неполноценные (см. продукцию D-Wave Systems): в них действительно используются некоторые квантовые эффекты, но применять их можно лишь для решения ограниченного круга задач. Для исполнения наиболее полезных квантовых алгоритмов — так называемых алгоритма Шора (разложение на множители) и Гровера (задача перебора) — неполноценные КК не годятся.
А полноценные КК — в которых работают настоящие кубиты и каждый кубит «запутан» со всеми другими — пока не перешагнули 20-кубитового порога. Хуже того, то, например, что удалось построить коммерческий 17-кубитовый квантовый процессор (IBM, 2017) не означает, что с той же технологией удастся построить 18-кубитовый или более. Поэтому настоящие, «классические» квантовые компьютеры пока годны лишь для экспериментов, не имеющих практической ценности — и когда это удастся исправить, никто не знает.
Но чем дольше всё это длится, тем больше сторонников у теории «квантового» заговора. Мол, пока нас тут кормят сказками о невозможности практически полезного КК, за стенами секретных лабораторий мощные настоящие КК уже построены — и с их помощью решены некоторые фундаментальные задачи. Например, взломана современная криптография, так что спецслужбы теперь читают все шифрованные сообщения в интернете.
Верить ли этому — решайте сами. Конспирологам, как всегда, достаточно веры. Но буквально за эту зиму был сформулирован замечательный контраргумент, получивший название «квантовой канарейки»: если полноценный квантовый компьютер, годный для решения практических задач, удастся построить, Bitcoin — словно та канарейка, которую рудокопы исстари брали в шахту — первым сообщит нам об этом своим изменившимся поведением.
Рассуждения тут простые. Bitcoin основан на классических криптоалгоритмах, которые уязвимы для квантовых вычислений: решая задачу разложения длинного числа на множители, обычный компьютер вынужден перебирать варианты один за другим, тогда как КК способен «пережить» все возможные состояния одномоментно. Что сильно сокращает число требуемых квантовых операций.
Как сильно — зависит от конкретного алгоритма. В случае с ECDSA разница радикальная: если простому компьютеру для подбора приватного ключа по известному публичному требуется 2^128 операций, КК сделает то же самое за 128^3. На хэшах (упоминавшиеся выше SHA, RIPEMD) разница меньше: так обращение хэша SHA-256 потребует вместо 2^256 операций на обычном компьютере 2^128 на квантовом.
Несколько теоретических подходов к этой проблеме, выполненных учёными из разных стран (см., в частности, здесь и здесь), позволяют нарисовать следующий сценарий квантовой атаки. Ломать свежие кошельки (то есть подбирать приватные ключи к ним) обладатели КК не станут. В том числе и потому, что это сравнительно сложно. Сегодня не принято раскрывать публичный ключ (правильные Bitcoin-программы, тратя средства с одного адреса, не переводят сдачу обратно, а отправляют её на новый адрес, публичный ключ к которому не опубликован), но в первые два года существования Bitcoin публичный ключ использовался в качестве адреса. Иначе говоря, для адресов, которые тогда засветились, публичные ключи известны — и это сильно снижает требуемый для взлома объём вычислений (см. предыдущий параграф: нужно лишь обратить ECDSA). А хранящиеся там суммы порой гигантские!
Так что владельцы КК смогут и наверняка захотят завладеть содержимым некоторых из тех кошельков. Скажете, кража, скажете, преступление? Но правовой статус самой криптовалюты определён далеко не везде. И не факт, что приватные ключи к тем кошелькам не утеряны. А даже если владельцы и отыщутся, и станут возражать, всегда можно прибегнуть к той же аргументации, что участники LBC. По прикидкам, квантового компьютера с парой тысяч кубит (полноценных, не забывайте), менять состояние которых можно с частотой в сотни мегагерц, будет достаточно для подбора приватных ключей Bitcoin в реальном времени.
К каким последствиям это приведёт, легко представить. Ведь до сих пор (по крайней мере в его новейшей истории) в биткойне не было обнаружено ни одной фундаментальной уязвимости. Поэтому первые же применения квантового компьютера спровоцируют панику. Её поднимут владельцы опустошённых кошельков, либо энтузиасты, которые заметят операции с древними кошельками. И обменный курс нырнёт к нулю: кто же захочет платить за числа, которые так легко подобрать?
Факт, что этого всё ещё не произошло, свидетельствует, что опасный для массовой криптографии квантовый компьютер пока не построен — даже в секретных лабораториях. «Квантовая канарейка» всё ещё жива.
К счастью, есть возможность продлить её жизнь и дальше. Нужно лишь перейти на криптоалгоритмы, устойчивые к квантовым вычислениям. Сильно упрощая, для этого достаточно, например, перевести Bitcoin на использование исключительно хэшей. Так называемая подпись Лэмпорта, которую с недавних пор продвигают в Bitcoin, Ethereum и прочих криптовалютах, как раз основана на такой идее. К сожалению, у подписи Лэмпорта (как и, предположительно, у прочих КК-стойких алгоритмов) есть свой недостаток: она очень длинная (килобайты!), что неизбежно раздует размер блоков в блокчейне. Поэтому когда такой переход случится, Bitcoin имеет больше шансов выжить — благодаря уже реализованным средствам компрессии блокчейна и реализуемому (но фактически стартовавшему, см. Lightning Network) второму уровню сети.
Но есть и более оптимистичный сценарий. Дело в том, что квантовый компьютер даст значительный прирост производительности в майнинге (где всё сводится к SHA). И, опираясь на постулат, что майнинг совокупно всегда выгодней грубого взлома, можно предположить, что владельцы первых же КК займутся не сомнительным с точки зрения закона и нравственности подбором приватных ключей, а майнингом. И это тоже будет легко заметить — по рывку на графиках, иллюстрирующих текущую сложность майнинг-операций. Иначе говоря, они обратят квантовый компьютер на благо обществу.
Что в сухом остатке? Опасностей если и ждать, то с другой стороны. Математика криптовалют по-прежнему надёжней вооружённой охраны и стальных стен.
Bitcoin,криптовалюта,криптография,квантовый_компьютер,ECDSA,Large_Bitcoin_Collider