Читаем 1c2b9509b53cb0837976a7dc6c8bcd37 полностью

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

достоянием. Поэтому подпись на базе одного ключа целесообразно

использовать лишь единожды, что также создает значительные неудобства

для проектирования систем на базе этого алгоритма.

Следующий алгоритм, который также считается постквантовым, — это так

называемая «криптография на решетках». Решеткой в математике называют

периодическую сеть точек в n-мерной системе координат, где задано число n

«базисных векторов», порождающих саму решетку. Вот простой пример

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

векторами.

Сложная для вычисления задача в данном алгоритме — это нахождение так

называемого SVP (Shortest Vector Problem) или «наиболее короткого вектора»

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

размерности пространства n. Если рассматривать обыкновенную плоскую

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

узлу решетки, для человека не составляет никакого труда. Однако если это

будет делать компьютер, то в ход пойдут непростые математические

вычисления. А если начать увеличивать количество пространственных

измерений, то процесс превратится в весьма серьезную вычислительную

задачу. Считается, что на данный момент сложность такой задачи превышает

возможности квантового компьютера. Впрочем, из алгоритмов, базирующихся

на криптографии на решетках, неуязвимым пока признается только

непосредственно само шифрование. Цифровая электронная подпись уже

подверглась взлому в 1999 году, а ее модифицированная версия — в 2006

году. В настоящее время математики работают над дальнейшим развитием

алгоритма ЭЦП, чтобы разрешить эту проблему и предложить индустрии

новый, более совершенный стандарт криптографической безопасности.

Наконец, рассмотрим, возможно, самый перспективный на текущий момент

алгоритм — использование криптографии на базе изогений эллиптических

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

подобного же типа. Алгоритм преобразования точек представляет собой

соотношение двух полиномов (многочленов) для каждой из координат точки по

осям x и y. В случае если получить такое отображение считается

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

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

называемый «j-инвариант», являющийся чем-то вроде «классификатора»

эллиптической кривой и представленный в виде обычного числа. Для расчета j-

инварианта используются коэффициенты из уравнения эллиптической кривой.

Применяя различные значения коэффициентов, рассчитывают множество

инвариантов, которые затем отображаются в виде графа. В полученном графе

инварианты становятся его вершинами, а ребрами графа служат соединения