Background Image
Previous Page  4 / 14 Next Page
Information
Show Menu
Previous Page 4 / 14 Next Page
Page Background

L

a

(

n

) =

L

i

min

(

n

)

,

при этом

L

i

min

= min

c

∈L

i

E

{

L

c

(

n

)

}

,

(1)

где

E

:

E

(

F

p

) :

y

2

=

x

3

+

ax

2

+

b

(mod

p

)

— множество эллиптических

кривых, утвержденных Национальным институтом стандартов и тех-

нологий (National Institute of Standards and Technology, NIST). Далее

рассмотрим подмножества кривых

E

:

P

192

,

P

224

,

P

256

,

P

384

и

P

521

.

В настоящей статье будут приведены алгоритмы, когда при выпол-

нении условия (1) выполняется соотношение

S

(

a

)

6

= 0

.

Описание основных операций в поле

F

p

и обозначение их вычи-

слительной сложности представлены в табл. 1 [4].

Таблица 1

Обозначение вычислительной сложности операций в простом поле

Операция

Описание

A

Сложение/вычитание (

a

ddition/subtraction) в поле

F

p

R

Приведение по модулю (

r

eduction)

p

S

Возведение в квадрат (

s

quaring) в поле

F

p

M

Умножение в поле (

m

ultiplication) в поле

F

p

I

Нахождение мультипликативного обратного элемента (

i

nversion)

в поле

F

p

Эффективные алгоритмы вычисления скалярного умножения

точки.

Перечислим полученные в процессе настоящего исследования

алгоритмы.

Алгоритм на основе метода несовместной формы представле-

ния скаляра c окном.

Предварительные вычисления повышают эффек-

тивность вычисления кратной точки. При

w

2

несовместное пред-

ставление (

w

NAF

) целого

d

по основанию 2 имеет вид

d

=

m

1

X

i

=0

k

i

2

i

,

где

w

2

,

k

i

это простое,

|

d

i

|

<

2

w

1

[3].

Преимуществом указанного метода является то, что число ненуле-

вых чисел и, следовательно, необходимых сложений в ходе вычисле-

ний невелико. Предлагаемый алгоритм

a

w

NAF

(алгоритм 1) скалярного

умножения точки для данного

w

NAF

-представления скаляра основан

на этом свойстве.

Алгоритм 1

. Эффективное вычисление скалярного умножения точ-

ки

dP

,

d

Z

,

P

E

(

F

p

)

,

w

NAF (

d

) = (

d

n

1

, . . . , d

0

)

на основе метода

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

d

с окном

w

.

Вход:

— эллиптическая кривая

E

(

F

p

)

;

— точка

P

E

(

F

p

)

,

P

= (

x, y

)

,

x, y

F

p

;

68 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 3