Александр Цихилов - Блокчейн. Принципы и основы

находиться в состоянии так называемой «квантовой запутанности», когда

изменение состояния одного кубита автоматически влечет за собой изменение

состояния другого, связанного с ним, на противоположное. Однако

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

технологически очень сложно, поскольку их необходимо тщательно

изолировать от любых видов помех в окружающей среде. На текущий момент

ведущим производителям квантовых компьютеров, таким, например, как

Google, удалось удержать в связанном состоянии целых 72 кубита, что пока

является мировым рекордом среди подобных разработок. Много или мало 72

кубита для решения задач взлома хотя бы, например, алгоритма факторизации

RSA? Если рассматривать n обычных бит, то из 2n возможных состояний в

один момент времени можно выбрать лишь одно, в то время как n кубитов в

состоянии суперпозиции будут находиться в 2n состояниях одновременно. Как

результат при линейном возрастании количества кубитов количество

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

обладать исключительной вычислительной мощностью. Учитывая новейшие

разработки в области квантовых вычислений, специалисты оценивают

различия по мощности между квантовым и обычным компьютером не менее

чем в миллиарды раз. При этом главное преимущество квантовый компьютер

будет иметь именно при решении математических задач, связанных с

переборами вариантов.

Тем не менее даже такая существенная вычислительная мощность может

оказаться недостаточной, чтобы легко взламывать криптоалгоритмы с

открытым ключом. Необходимое для этого число кубитов исчисляется гораздо

большими величинами: например, для алгоритма факторизации RSA с ключом

в 2048 бит потребуется ровно вдвое больше кубитов. Эти данные рассчитаны

на базе вычислительных требований гибридного (содержащего как

классическую, так и квантовую части) алгоритма, представленного в 1994 году

американским ученым, специалистом в области квантовой информатики

Питером Шором. Для взлома же эллиптической криптографии необходимое

количество кубитов, как ни странно, меньше: для ключей в 256 бит потребуется

1536 кубитов, а для 512 бит — 3072. Учитывая скорость роста

производительности квантовых компьютеров (а она на данный момент

превышает закон Мура), до момента, когда самые популярные

криптоалгоритмы сдадут свои позиции, остались, возможно, считаные годы. И

о решении этой потенциальной угрозы специалистам-криптографам

необходимо позаботиться уже сейчас.

Все не так страшно, как может показаться на первый взгляд. Уже разработан

ряд алгоритмов асимметричной криптографии, которые остаются устойчивыми

к квантовому перебору даже с использованием достаточно большого

количества кубитов. Такие алгоритмы называют «постквантовыми», и о

некоторых из них мы поговорим. В частности, о подписях Лэмпорта, криптографии на решетках и об изогениях эллиптических кривых.

Формирование цифровой электронной подписи на базе алгоритма Лэмпорта

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

генератора случайных чисел. Создается 256 пар случайных чисел длиной по

256 бит каждое. Этот набор данных суммарным объемом 16 килобайт и будет

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

хешей представляют собой открытый ключ. Затем на базе секретного ключа

формируется электронная подпись для отправляемого сообщения. Как

известно, чтобы подписать сообщение электронной подписью, его сначала

надо хешировать. А затем составляется электронная подпись, в которой для

каждого значения бита хеша сообщения (нуля или единицы) выбирается либо

первое, либо второе число из пары секретного ключа, соответствующей

порядковому номеру бита в хеше.

Криптостойкость данного алгоритма зависит от типа используемой хеш-

функции. С учетом того, что процедура хеширования имеет сугубо

односторонний характер, а также того факта, что хешируется значительное

количество данных (256 пар), задачу обратного восстановления секретного

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

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

(до 16 килобайт). Во-вторых, при формировании электронной подписи данным