Библиографическое описание:

Бабенко М. Г. Анализ методов скалярного умножения на эллиптической кривой // Молодой ученый. — 2010. — №4. — С. 24-29.

В настоящие время эллиптические кривые широко применяются в криптографии. Основным в арифметике на эллиптической кривой [1, c.31] является алгоритм умножения точки  эллиптической кривой на числовую константу  или алгоритм вычисления  или алгоритм скалярного умножения точки. Поэтому актуальной становиться задача эффективной реализации скалярного умножения на эллиптической кривой. Проанализируем существующие методы скалярного умножения на эллиптической кривой.

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

Базовыми алгоритмами для реализации скалярного умножения являются алгоритм сложения, удвоения точек, так как, если  то .

Алгоритм 1 [2, c. 102]. Сложения точек на эллиптической кривой заданных в проективной системе координат.

Вход  – простое число и точки , где .

Выход:

1      

2      

3      

4      

5      

6       

7        Return

Алгоритм 2 [2, c. 102]. Удвоения точки на эллиптической кривой, заданной в проективной системе координат.

Вход  – простое число и точка .

Выход:

1      

2      

3      

4      

5      

6      

7       

8        Return  

Приведем основные алгоритмы скалярного умножения  на эллиптической кривой, при их изложении будут использоваться следующие обозначения:  – сложность операции удвоения в группе точек эллиптической кривой;  – сложность операции сложения-вычитания в группе; порядок точки  на эллиптической кривой  равен ;   и  число   представлено  в  двоичной системе исчисления .

Алгоритм удвоения-сложения

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

Вычисления осуществляются с помощью следующего алгоритма:

Алгоритм 3. Удвоения-сложения

Вход: ,

Выход: .

1.                

2.                 For  to  do

2.1                   If  then

2.2                  

3.                 Return

Реализация  метода  требует    операций  удвоения точки  и  сложений,  где  – вес  Хэмминга  двоичного  вектора  . Так как в  среднем число  единиц  случайного вектора   равно , то общее число групповых операций оценивается величиной .

Алгоритм удвоения-сложения-вычитания

Модификация алгоритма удвоения-сложения, основанная на введении дополнительной операции вычитания точки. Например, число  в двоичной системе  имеет  вес ,  но  его  можно  представить  как    с  весом  . Понижение количества операций происходит за счет понижения веса  Хэмминга, так как число представляется в  с коэффициентами   (NAF – non-adjacent form).  Одно  из  свойств представления   –  отсутствие  в  нем  смежных  пар  ненулевых  элементов, благодаря чему возрастает удельный вес нулевых элементов . Для расчета  используется следующий алгоритм.

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

Вход: положительное целое число k.

Выход: .

1                  

2                   While  do

2.1                   If  is odd then ,  

2.2                   Else

2.3                   ,

3                   Return

После  расчета  вычисляется  точка    методом  слева направо с

помощью следующего алгоритма.

Алгоритм 5.  Удвоения-сложения-вычитания.

Вход: ,

Выход: .

1                  

2                   For  to  do

2.1                   If  then

2.2                   If  then

2.3                  

3                   Return

 – представление  числа    может  оказаться  на  один  бит  длиннее

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

Метод окон с алгоритмом удвоения-сложения-вычитания

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

Назовем -окном числа ,  – нечетный коэффициент, , содержащий хотя бы один ненулевой элемент. Заметим, что .

Пример. Пусть , тогда имеем  различных значений :

Этих  окон  достаточно  для  формирования  числа  произвольной  длины  . Четные  коэффициенты  в -представлении  числа    избыточны,  так  как  они образуются  удвоением  нечетных.  На  первом  этапе  произведем вспомогательные вычисления и занесем в память  точек: , ,  и .

В  общем  случае  в памяти  хранится    точек. Число  может  быть определено  с  помощью  модифицированного  алгоритма  4. Модификация состоит в следующем: на шаге 2.1  заменяется на  ,  где .

Алгоритм 6. Удвоения-сложения-вычитания.

Вход: , , .

Выход: .

1                   , .

2                  

3                   For  to  do

3.1             If  then If  then  else

3.2            

4                   Return

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

Реализуем предложенные методы скалярного умножения на языке программирования Free Pascal и кривыми из работы [3 c.6-8]:

Кривая P-192

 

Кривая P-224

Кривая P-256

,

где для всех трех случаев  и точка . Для тестирования алгоритмов скалярного умножения выбираем множество случайных целых чисел , содержащее 10000 элементов. После запросили системное время  – время начала вычислений ,  – время окончания выполнения алгоритма а среднее время вычисления скалярного умножения  вычисляем по формуле . Результаты, полученные при тестировании, представлены в таблице.

Таблица. Среднее время вычисления скалярного умножения в миллисекундах.

 

Кривая  P-192

Кривая  P-224

Кривая P-256

Алгоритм 3

5,897

6,724

7,550

Алгоритм 5

5,014

5,703

6,391

Алгоритм 6

4,978

5,539

6,217

 

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

 

Литература

1.      Болотов А.А, Гашков С.Б., Фролов А.Б. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. – М.:КомКнига, 2006. – 280 с. 

2.      Бессалов А.В.,  Телиженко А.Б. Криптосистемы на эллиптических кривых : Учеб. пособие. – К: Политехника, 2004. – 224 c.

3.      Recommended Elliptic Curves for Federal Government Use. .: http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf

 

Обсуждение

Социальные комментарии Cackle