Метод адаптивного "-окна"-операций в эллиптических кривых

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Вестн. Сам. гос. техн. ун-та. Сер. Физ. -мат. науки. — 2008. — № 2(17). — С. 279−281
УДК 512. 742. 72
МЕТОД АДАПТИВНОГО «ОКНА» ОПЕРАЦИЙ В ЭЛЛИПТИЧЕСКИХ КРИВЫХ
А. Б. Спельников
Северо-Кавказский государственный технический университет, 355 029, г. Ставрополь, просп. Кулакова, 2.
E-mail: fiss_runamail. ru
Разработан алгоритм адаптивного «оконного» умножения точки на число на эллиптической кривой, позволяющий увеличить скорость расчетов в криптографических приложениях.
Ключевые слова: эллиптические кривые, умножение точки на число.
В общем случае умножение точки P на эллиптической кривой на число определяется как комбинация последовательных сложений и удвоений точки. Выделяют различные методики умножения [1]. Рассмотрим некоторые из них.
Метод прямой последовательности. Показатель представляется в виде
n — 1
l =53 1i2
?=0
где li? {0,1}, i — порядковый номер бита данных. Затем последовательно вычисляются точки 2i+1P удвоением точки 2iP (i = 0,1,…, n — 1) и складываются те из них, для которых коэффициент l равен единице.
Метод обратной последовательности. В данном случае вычисляются точки Pi-1 = 2P + li- 1P (i = n — 1, n — 2,. ., 1).
Метод обратной последовательности ускоряется при помощи методики «окон». «Окном» называется представление основания системы счисления, равного степени числа два. Для этого показатель l разбивается на группы, по величине степени:
l = lo + 2dl1 + 2dmlm.
Вычисляются значения 2P, 3P… 2dP. Далее вычисляется Pi-1 = 2dP + li- 1P, где i = m — 1, m — 2, …, 1.
Данным методом число сложений сокращается примерно в 4 раза по сравнению с числом удвоений [1].
Разработана методика изменяемого, адаптивного «окна». Вычислим значения 2P, 3P … 2dP. Здесь d — минимальный размер окна. Рассмотрим двоичное представление показателя l. В общем случае оно представляет собой набор из нулей и единиц со случайным распределением.
Вычислим первое значение P1 = lmP. Здесь lm -значение старших d бит, представленное в десятичной системе. Это значение найдено на этапе предварительных вычислений.
Затем передвинем указатель на d бит. Рассмотрим значение нового старшего бита. Пусть это 1. Вычислим P2 = 2dP[ + lm-1P. Здесь lm- 1 -значение новых старших d бит, представленное в десятичной системе.
Передвинем указатель на d бит. Рассмотрим значение нового старшего бита. Пусть это 0. Передвинем указатель на следующий бит. Повторяем операцию до тех
Спельников Алан Борисович — аспирант кафедры информационных систем и технологий Северо-Кавказского государственного технического университета.
Спельников А. Б.
пор, пока бит не будет равен единице. Пусть получилось смещение в? бит. Вычислим Рз = + 2Р. Здесь 1т-2 -значение новых старших ! бит, представленное
в десятичной системе (см. рисунок). Тогда представим выражение для вычислений методом адаптивного «окна»:
Р& lt-_1 = 2*+4Р + Р.
Здесь г — переменное число, которое определяется в процессе вычислений.
V
М/ V V
_
10 011 100 001 011
-I-I-I--I-I-I--I-I-I-I-I-
Метод адаптивного «окна»
Численный пример. Пусть дана эллиптическая кривая вида у2 = х3 + 21х + 17, определённая в поле порядка р = 31. Пусть исходная точка Р = (1- 15), показатель I = 142. Выберем размер «окна» ! =2.
Вычислим 2Р = (16- 4), 3Р = (2- 25).
Двоичное представление показателя I = 100 110 102 = 154ю.
Первый показатель I = 102 = 2ю.
Вычисляем Р1 = 2Р = (16- 4).
Передвигаем указатель на 2 бита. Проверяем старший бит, передвигаем на следующий и присваиваем? =1. Проверяем бит: I =112 = 3ю.
Вычисляем Р2 = 22+1Р1 + 3Р = (20- 6).
Передвигаем указатель на 2 бита. Проверяем старший бит, передвигаем на следующий и присваиваем? =1. Проверяем бит: I = 102 = 2ю.
Вычисляем окончательно: Рз = 22+1Р2 +2Р =(6- 24).
В результате применения метода адаптивного «окна» в данном примере экономия по отношению к стандартному методу «окон» составила одну операцию сложения точек эллиптической кривой.
Рассчитаем изменение количества операций и прирост производительности умножителя, полученный вследствие применения методики адаптивного «окна».
Рассмотрим модель, представленную на рисунке. С точки зрения теории вероятностей, значение бита под указателем — случайное событие, вероятность исхода которого равна 0,5. Тогда в первом приближении количество сдвигающих нулей после блоков можно выразить по формуле
ко =
0,5Н
где Н — значимая разрядность числа.
Так как значение под указателем, равное нулю, сдвигает следующий блок, то количество блоков будет уменьшаться. Значит, более точно количество блоков, после которых стоит ноль, можно вычислить по формуле
Аи
0,5Н

Н
Бю2
0,5Н
ад — 1
По аналогии можно вычислить количество блоков, после которых есть г нулей:
А = 0,5кг1
ад — 1
= 0,5®Н
(ю — 1Г
С учётом того, что блоки, А являются подмножеством блоков, получим выражение для нахождения количества блоков, после которых встречается заданное
ад
2
ад
ю
ад
Метод адаптивного «окна» операций в эллиптических кривых
число нулей:
n-1
bi = ki ^ ^ kj.
j=i+1
Тогда наиболее вероятное количество операций сложения точек можно найти по формуле
h-1
K=W (& quot- - e j-
j=1
Таким образом, разработан алгоритм адаптивного «оконного» умножения точки на число на эллиптической кривой, позволяющий увеличить скорость расчётов в криптографических приложениях.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Ростовцев, А. Г. Теоретическая криптография [Текст] / А. Г. Ростовцев, Е. Б. Маховен-ко. -СПб.: Профессионал, 2005. -478 с. -ISBN 5−98 371−012−5.
Поступила в редакцию 30/VI/2008- в окончательном варианте — 16/X/2008.
MSC: 14H52
THE ADAPTIVE & quot-WINDOW"- METHOD FOR ELLIPTIC CURVE OPERATIONS
A. B. Spel'-nikov
North Caucasus State Technical University, 355 029, Stavropol'-, prosp. Kulakova, 2.
E-mail: fiss_runSmail. ru
The algorithm of adaptive & quot-window"- multiplication of a point by a number on the elliptic curve is introduced, allowing to increase the calculation speed in cryptographic applications.
Key words: elliptic curves, point at number multiplication.
Original article submitted 30/VI/2008- revision submitted 16/X/2008.
Spel'-nikov Alan Borisovich, Postgraduate Student, Dept. of Information Systems and Technologies of North Caucasus State Technical University.

ПоказатьСвернуть
Заполнить форму текущей работой