Software & Systems

В 1985 году Нил Коблиц и Виктор Миллер независимо предложили использовать эллиптические кривые для криптосистем с открытым ключом. Со второй половины 90-х годов криптосистемы на эллиптических кривых стали приобретать важное практическое значение.

Эффективность криптосистем на эллиптических кривых зависит от эффективности алгоритмов умножения скаляра на точку.

Задача умножения скаляра на точку состоит в вычислении следующей суммы:

Метод Коблица-Солинаса, используемый для поля характеристики два, на сегодняшний день является самым быстрым методом для умножения скаляра на точку (см., например: J.A. Solinas. Efficient Arithmetic on Koblitz curves. 2000).

Последние несколько лет наблюдается интерес к методам быстрого умножения скаляра на точку в полях характеристики три (Nigel P. Smart, E.J. Westwood. Point Multiplication on Ordinary Elliptic Curves over Fields of Characteristic Three. 2003). Это связано с появлением нового направления эллиптической криптографии – криптосистем, основанных на билинейных отображениях.

Данная работа посвящена модификации метода Коблица-Солинаса для поля характеристики три. На основе известных алгоритмов предложен новый алгоритм умножения скаляра на точку.

Арифметика эллиптических кривых, заданных над полем характеристики три

Рассмотрим неособую кривую над полем :

(1)

где .

Арифметические операции на кривой (1) могут быть определены следующим образом.

Сложение точек: :

Удвоение точек: :

В таблице 1 приведены оценки сложности операций, выраженные через сложность полевых операций, где M – сложность умножения; I – сложность нахождения обратного.

Таблица 1

Прямая модификация метода Коблица-Солинаса

Пусть E – это эллиптическая кривая вида (1), определенная над конечным полем , причем ее коэффициенты принадлежат . Поскольку кривая определена над , то для нее справедливо, если – точка на кривой E, то точка будет так же лежать на кривой E.

Можно проверить, что кривая, заданная в поле характеристики три будет удовлетворять следующему свойству:

(2)

для каждой точки на E, где , где – колличество -рациональных точек на кривой E (см.: D. Hanker­son, Alfred Menezes, Scott Vanstone/. Guide to Eliptic Curve Cryptography. 2004).

Определим отображение :

Тогда (2) можно переписать как

. (3)

Решение уравнения (3): где

Скаляр k может быть представлен как ряд , и затем , применяя правило Горнера,

Найдем правило для нахождения ряда по основанию .

Теорема: делится на тогда и только тогда, когда .

Доказательство. Поскольку из (3) мы можем найти, что тогда . Последнее выражение делится на 3 тогда и только тогда, когда .

Отметим, что тогда

Для того чтобы снизить длину последовательности в работе Майера и Штэфельбаха, было отмечено, что (см.: W. Meier, O. Staffelbach. Efficient Multiplication on Certain Nonsupersingular Elliptic Curves. 1992).

Если k выбран около , то длина знакового тернарного представления по основанию будет уменьшена вполовину. Для нахождения вычислим, чему равно в виде и предложим алгоритм, который определит . Первая задача может быть решена с применением следующей рекурсивной процедуры. Пусть , и для . Легко видеть, что .

Для иллюстрации алгоритма деления возьмем кривую c . Характеристическое уравнение будет иметь следующий вид: .

Его корень .

Для нахождения алгоритма деления найдем сопряженное к . Сопряженное будет . Умножим числитель и знаменатель на .

Алгоритм 1. Вычисление .

Вход:

Выход:

return

Рассмотрим алгоритм 2, на входе котрого будет комплексное число , а на выходе – последовательность коэффициентов , таких что

Алгоритм 2. Тернарное знаковое представление по основанию .

Вход: ,t

Выход: Тернарное знаковое представление по основанию

,

repeat

,

ifthen

end if

untill and

return

Если , тогда длина ряда по основанию будет равна m. Плотность ненулевых позиций составит около .

Алгоритм 3. Вычисление .

Вход:

Выход:

Использовать алгоритм 1 для нахождения

Использовать алгоритм 2 для нахождения

for, do

If then

end if

if then

end if

end for

return

Средняя сложность алгоритма составит где A – сложность сложения; – сложность вычисления отображения .

Использование метода разбиения для прямой модификации метода Коблица-Солинаса

Разобьем ряд по основанию на две половины (см.: Robert P. Gallant, Robert J. Lambert, Scott A. Vanstone. Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms. 2001):

Обозначим тогда

(4)

Главное свойство полученной последовательности (4) состоит в том, что длина последовательности уменьшается наполовину. Алгоритм 3 использует разбиение при вычислении .

Алгоритм 4. Метод разбиения.

Вход:

Выход:

Использовать алгоритм 1 для нахождения

Использовать алгоритм 2 для нахождения

If then

end if

Предвычислим: ,,,

for , do

return

Средняя сложность алгоритма составит .

Таблица 2 содержит оценки сложности изложенных ранее методов с предложенным (A – стоимость сложения двух точек; – сложность отображения ).

Таблица 2

Очевидно, что при выборе использование метода разбиения по сравнению с прямой модификацией метода Коблица-Солинаса будет давать выигрыш.