Если классическая технология создания компьютеров упирается в свой предел развития, значит, следует искать решения по дальнейшему увеличению производительности в принципиально новых научно-технологических направлениях. Наиболее перспективной областью в части поиска возможностей для существенного роста производительности вычислений в настоящий момент считаются так называемые квантовые компьютеры.
Квантовые компьютеры – это вычислительные устройства, существенно отличающиеся от привычной для нас архитектуры двоичной логики. В классическом представлении мельчайшая ячейка памяти, называемая битом, может принимать устойчивые значения либо нуля, либо единицы. В квантовом же компьютере биты имеют квантовую природу и называются «кубитами». В роли таких кубитов могут выступать, например, направления спинов субатомных частиц, а также различные состояния внешних электронов или фотонов. Чтобы не углубляться в основы квантовой механики, мы не станем подробно рассматривать физическое устройство квантового компьютера, а отметим лишь некоторые свойства, отличающие его от компьютера классического.
В 1931 году австрийский физик Эрвин Шредингер предложил мысленный эксперимент, в котором он помещал условного кота в стальную камеру, где находилось устройство с радиоактивным атомным ядром, а также колба с ядовитым газом. По условиям эксперимента атомное ядро в течение часа может ожидать распад с вероятностью 50 %. Если это происходит, то срабатывает механизм, разбивающий колбу, после чего кот погибает. Но если распад ядра все же не случился, тогда кот остается цел и невредим. Смысл этого эксперимента в том, что внешний наблюдатель никогда точно не знает, распалось ли ядро и жив ли кот, до тех пор, пока не откроет сам ящик, а до этого момента считается, что кот и жив, и мертв одновременно.
Понятно, что ни одна сущность в нашем мире не может находиться в двух разных состояниях в один и тот же момент времени. Поэтому правильнее было бы сказать, что кот находится в так называемом состоянии «суперпозиции», в котором все возможные варианты состояния принимаются с различной степенью вероятности. При этом сумма вероятностей всех возможных состояний обязательно должна быть равна 100 %. То же самое можно отнести и к принципу работы кубита квантового компьютера – он таким же образом может находиться в состоянии суперпозиции, принимая одновременно значения логического нуля и единицы. До момента непосредственного измерения состояния кубита его точное значение наблюдателю неизвестно, а после измерения и получения результата кубит сразу же фиксируется в однозначном состоянии нуля или единицы. Это на первый взгляд странное свойство кубитов оказалось очень полезным в организации параллельных расчетов сложных вычислительных задач, включая криптографические алгоритмы.
Еще одна интересная особенность кубитов состоит в том, что вместе они могут находиться в состоянии так называемой «квантовой запутанности», когда изменение состояния одного кубита автоматически влечет за собой изменение состояния другого, связанного с ним, на противоположное. Однако организовать квантовую запутанность большого числа кубитов между собой технологически очень сложно, поскольку их необходимо тщательно изолировать от любых видов помех в окружающей среде. На текущий момент ведущим производителям квантовых компьютеров, таким, например, как Google, удалось удержать в связанном состоянии целых 72 кубита, что пока является мировым рекордом среди подобных разработок. Много или мало 72 кубита для решения задач взлома хотя бы, например, алгоритма факторизации RSA? Если рассматривать n обычных бит, то из 2n возможных состояний в один момент времени можно выбрать лишь одно, в то время как n кубитов в состоянии суперпозиции будут находиться в 2n состояниях одновременно. Как результат при линейном возрастании количества кубитов количество возможных состояний будет расти экспоненциально. А это, в свою очередь, означает, что квантовый компьютер с большим количеством кубитов будет обладать исключительной вычислительной мощностью. Учитывая новейшие разработки в области квантовых вычислений, специалисты оценивают различия по мощности между квантовым и обычным компьютером не менее чем в миллиарды раз. При этом главное преимущество квантовый компьютер будет иметь именно при решении математических задач, связанных с переборами вариантов.
Тем не менее даже такая существенная вычислительная мощность может оказаться недостаточной, чтобы легко взламывать криптоалгоритмы с открытым ключом. Необходимое для этого число кубитов исчисляется гораздо большими величинами: например, для алгоритма факторизации RSA с ключом в 2048 бит потребуется ровно вдвое больше кубитов. Эти данные рассчитаны на базе вычислительных требований гибридного (содержащего как классическую, так и квантовую части) алгоритма, представленного в 1994 году американским ученым, специалистом в области квантовой информатики Питером Шором. Для взлома же эллиптической криптографии необходимое количество кубитов, как ни странно, меньше: для ключей в 256 бит потребуется 1536 кубитов, а для 512 бит – 3072. Учитывая скорость роста производительности квантовых компьютеров (а она на данный момент превышает закон Мура), до момента, когда самые популярные криптоалгоритмы сдадут свои позиции, остались, возможно, считаные годы. И о решении этой потенциальной угрозы специалистам-криптографам необходимо позаботиться уже сейчас.
Все не так страшно, как может показаться на первый взгляд. Уже разработан ряд алгоритмов асимметричной криптографии, которые остаются устойчивыми к квантовому перебору даже с использованием достаточно большого количества кубитов. Такие алгоритмы называют «постквантовыми», и о некоторых из них мы поговорим. В частности, о подписях Лэмпорта, криптографии на решетках и об изогениях эллиптических кривых.
Формирование цифровой электронной подписи на базе алгоритма Лэмпорта представляет собой использование криптографической хеш-функции и генератора случайных чисел. Создается 256 пар случайных чисел длиной по 256 бит каждое. Этот набор данных суммарным объемом 16 килобайт и будет являться секретным ключом. Каждая из 256-битных пар хешируется, и эти 512 хешей представляют собой открытый ключ. Затем на базе секретного ключа формируется электронная подпись для отправляемого сообщения. Как известно, чтобы подписать сообщение электронной подписью, его сначала надо хешировать. А затем составляется электронная подпись, в которой для каждого значения бита хеша сообщения (нуля или единицы) выбирается либо первое, либо второе число из пары секретного ключа, соответствующей порядковому номеру бита в хеше.
Криптостойкость данного алгоритма зависит от типа используемой хеш-функции. С учетом того, что процедура хеширования имеет сугубо односторонний характер, а также того факта, что хешируется значительное количество данных (256 пар), задачу обратного восстановления секретного ключа из открытого не способен решить даже квантовый компьютер. Но этот алгоритм тоже не совершенен. Во-первых, ключи имеют существенный размер (до 16 килобайт). Во-вторых, при формировании электронной подписи данным алгоритмом половина секретного ключа становится фактически публичным достоянием. Поэтому подпись на базе одного ключа целесообразно использовать лишь единожды, что также создает значительные неудобства для проектирования систем на базе этого алгоритма.
