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

1 / 14

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ
ИНФОРМАТИКИ
УДК 512.742.72
БЫСТРЫЕ АЛГОРИТМЫ ВЫЧИСЛЕНИЯ ПРЕОБРАЗОВАНИЙ
НА ОСНОВЕ ЭЛЛИПТИЧЕСКИХ КРИВЫХ С ПРЕДВАРИТЕЛЬНЫМИ
ВЫЧИСЛЕНИЯМИ
Д.С. Хлебородов
МГТУ им. Н.Э. Баумана, Москва, Российская Федерация
e-mail:
Эффективные алгоритмы вычисления преобразований на основе эллиптических
кривых — сравнительно новая область исследований, представляющая огром-
ный интерес. Рассмотрено эффективное скалярное умножение точки элли-
птической кривой, определенной над простым полем, с использованием пред-
варительных вычислений. В основе предлагаемых алгоритмов лежат методы
несовместного представления скаляра (Non-Adjacent Form, NAF) с окном фик-
сированной и переменной ширины (скользящим окном). Для оценки эффектив-
ности полученных и ранее предложенных алгоритмов введен критерий эффек-
тивности, основанный на средней вычислительной сложности. Для получения
новых более эффективных алгоритмов использованы эффективные операции в
простом поле, операции с точкой: сложение (ADD); удвоение (DBL и DBLJ
A
);
операция “удвоить и сложить” (DA); масштабирование (SCALE); свойства
аффинной координатной системы; свойства координатной системы Якоби;
свойства координатной системы Якоби – Чудновского. Для алгоритмов сфор-
мулированы и доказаны утверждения относительно их вычислительной слож-
ности.
Ключевые слова: быстрые алгоритмы, эллиптические кривые, сложность, пред-
варительные вычисления, скалярное умножение точки.
FAST COMPUTATION ALGORITHMS OF TRANSFORMATIONS BASED
ON ELLIPTIC CURVES WITH PRECOMPUTATIONS
D.S. Khleborodov
Bauman Moscow State Technical University, Moscow, Russian Federation
e-mail:
The paper considers efficient algorithms for calculating transformations based on
elliptic curves. This new research area is of great interest nowadays. The paper
presents an effective scalar multiplication of an elliptic curve point defined over the
prime field using of preliminary calculations. The proposed algorithms are based
on the method of incompatible representations of the scalar (Non-Adjacent Form,
NAF) with a window of both fixed and variable width (a sliding window). In order
to evaluate the effectiveness of the previously obtained algorithms we proposed the
architecture of the algorithms and the criterion of efficiency based on the average
computational complexity. For elaborating newer and more efficient algorithms some
effective operations both in the prime field and with a point, such as addition (ADD),
doubling (DBL, DBLJ
A
), a complex operation “double and add” (DA), a scaling
duplication (SCALE), properties of the affine coordinate system, and Jacobi and
Jacobi – Chudnovsky coordinate systems are used. Statements about the algorithms
computational complexity are formulated and proved.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 3 65