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

магистр Кошлак М. М., д. т. н. Мельников Ю. Н.

В 80-е годы были разработаны, а в 90-е нашли широкое распространение системы цифровой подписи, построенные на использовании методов несимметричной криптографии. Основными из них являлись алгоритмы цифровой подписи RSA, DSA, Эль-Гамаля. Эти системы были отнесены к классу вероятно-стойких или доказуемо-стойких, что объясняется тем, что доказательство их стойкости сводилось к доказательству сложности решения определенных математических задач при соответствующих значениях (размерах) общесистемных параметров. Так доказательство стойкости RSA систем сводилось в основном к доказательству сложности решения задач факторизации модуля преобразования N. Доказательство стойкости алгоритмов Эль-Гамаля и DSA сводилось к доказательству сложности решения задачи нахождения дискретного логарифма в конечном поле. При этом по мере расширения применения указанных стандартов активизировались усилия по их взлому. Появились совершенно новые разделы математики, позволяющие существенно уменьшить вычислительную сложность решения указанных задач. Например, создание средств решения таких задач на основе общего решета числового поля в сочетании с применением мощных компьютеров сделало возможным взлом систем с параметрами, используемыми на практике. Иначе говоря, средства криптоанализа, в смысле математики и производительности криптоаналитических систем, развивались быстрее, чем изменялись версии средств цифровой подписи, направленного шифрования и распределение ключей.

Основным методом защиты стали изменения параметров, в смысле их увеличения, например, модулей преобразования. Так, в Эль-Гамаля и DSA системах длина модуля преобразования составляет порядка 1024 и более битов. Но при этом до такой же длины были увеличены длины ключей, как следствие увеличилась вычислительная сложность криптографических преобразований и уменьшилась скорость. В тоже время все преобразования необходимо осуществлять все с возрастающими скоростями, как правило, в реальном масштабе времени. Разрешение указанного противоречия было найдено за счет реализации различных несимметричных преобразований в группах точек эллиптических кривых. К настоящему времени, уже разработаны, прошли сертификацию и утверждены несколько стандартов цифровой подписи на эллиптических кривых. Прежде всего, это международный стандарт цифровой подписи Х 9.62-1998. В 2001 году в России так же был введен новый стандарт на цифровые подписи основанный на эллиптических кривых - ГОСТ Р 34.10-2001.

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

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

Эллиптической кривой E над полем F называется гладкая кривая, задаваемая уравнением Вейерштрасса:

где

Для обозначения эллиптической кривой используют запись E или E/F, чтобы подчеркнуть, что кривая определена над полем F.

Точка P = (x₀, y₀) Î E называется невырожденной (гладкой), если для многочлена верно по крайней мере одно из условий:

или

Эллиптическая кривая E/F является невырожденной (гладкой), если каждая точка (x, y) Î E является невырожденной.

На множестве точек кривой вводится операция сложения точек по следующему закону: сумма любых 3-х точек эллиптической кривой, лежащих на 1-й прямой, равна O. Геометрически точка O лежит в бесконечности на прямой пересекающей противоположные точки, в положительном направлении оси ординат.

Множество точек (x,y) Î E , содержащее, кроме того, бесконечно удаленную от кривой точку O, с введенной на нем операцией сложения точек образуют конечную абелеву (коммутативную) группу, которая называется группой точек эллиптической кривой. Точка O является аддитивной единицей в данной группе.

В группе точек эллиптической кривой E вводится операция скалярного умножения (умножения точки на число), определяемая следующей формулой:

,

где P Î E, Q Î E, a Î N.

Для практического применения в криптографии используются эллиптические кривые, заданные над полями Галуа (простыми полями).

Пусть задано простое число p > 3. Тогда эллиптической кривой E, определенной над простым конечным полем F_p, называется множество пар чисел (x, y), x, y Î F_p, которые удовлетворяют тождеству:

где a, b Î F_p и (4a³ + 27b²) ¹ 0 (mod p).

Стойкость протоколов криптографии на эллиптических кривых в конечных полях основана на сложности решения проблемы дискретного логарифма. Эта проблема имеет место в каждом случае, когда задана некоторая циклическая группа G с образующим элементом a. Тогда любой элемент y Î G может быть вычислен как: y = a^x, где x Î Z (Z – кольцо целых чисел). При известном x вычислить y довольно легко, а сделать обратное преобразование, то есть вычислить x по известному y очень трудно. Под словами очень трудно здесь понимается отсутствие алгоритма решения данной задачи за субполиномиальное время (практически задача может быть решена полным перебором).

Под порядком эллиптической кривой понимают порядок группы точек эллиптической кривой (число различных точек на E, включая точку O).

Для эллиптической кривой E заданной над простым полем F_p, порядок m группы точек данной кривой зависит от размера поля, определяемого простым числом p, и удовлетворяет неравенству:

Каждая точка P эллиптической кривой над простым полем E(F_p) образует циклическую подгруппу G группы точек эллиптической кривой.

Порядок циклической подгруппы группы точек эллиптической кривой (число точек в подгруппе) называется порядком точки эллиптической кривой.

Точка P Î E(F_p) называется точкой порядка q, если:

,

где q – наименьшее натуральное число, при котором выполняется данное условие.

Причем: m = nq, n Î Z, n>=1.

Образующую точку P Î E(F_p) необходимо выбрать так, чтобы порядок q циклической подгруппы был достаточно большим. Далее в данной подгруппе производится вычисление открытого ключа по данному закрытому. Выбирается случайное число 0 < d < q, которое будет являться закрытым ключом и вычисляется точка Q = dP, которая будет являться открытым ключом.

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

Криптосистемы цифровой подписи на основе эллиптических кривых с длиной ключа 160 бит имеют одинаковую стойкость с криптосистемами DSA и Эль-Гамаля с длиной ключа 1024 бита. Очевидно, что в ближайшем будущем данные системы займут доминирующее положение в криптографии с открытым ключом. Однако, при их широком распространении и применении, большие силы криптоаналитиков будут направлены на поиск новых, более быстрых, алгоритмов решения проблемы дискретного логарифма в группе точек эллиптических кривых. Скорее всего такие алгоритмы будут найдены, как это уже произошло с проблемами разложения больших чисел на множители (RSA) или дискретного логарифма в простом поле (DSA, Эль-Гамаль).