Методы и средства криптографической защиты информации. Жданов О.Н - 175 стр.

UptoLike

ВУЗ: 

СибГАУ | Красноярск

Составители: 

Рубрика: 

175
элементов группы
∗
q
F служит сложение двух точек эллиптической кривой Е,
определенной над
q
F
. Таким образом, аналог возведения в степень к элемента из
∗
q
F — это умножение точки Р
∈
Е на целое число k. Возведение в k-ю степень в
∗
q
F методом повторного возведения в квадрат можно осуществить за O
(
klog qlog
3
) двоичных операций (см. предложение II. 1.9). Аналогично, мы
покажем, что кратное kР
∈ Е можно найти за O( klog qlog
3
) двоичных операций
методом повторного удвоения.
Пример 1. Чтобы найти 100Р, записываем 100Р = 2(2(Р + 2(2(2(Р + 2Р)))))
и приходим к цели, производя 6 удвоений и 2 сложения точек на кривой.
Предложение 2.1. Пусть эллиптическая кривая Е определена уравнением
Вейерштрасса (уравнением (1),(2) или (3) из предыдущего параграфа) над
конечным полем
q
F
. Если задана точка Р на Е, то координаты kР можно
вычислить за О (
klog qlog
3
) двоичных операций.
Замечание 1. Оценки времени работы в предложении 2.1 не являются
наилучшими, особенно для конечных полей характеристики р = 2. Нам, однако,
достаточно этих оценок, которые следуют из наиболее очевидных алгоритмов
арифметики в конечных полях.
Замечание 2. Если известно число N точек на нашей эллиптической
кривой Е и если k > N, то в силу
равенства NP = О мы можем заменить к его
наименьшим неотрицательным вычетом по модулю N; в этом случае временная
оценка заменяется на O(
qlog
4
)
(напомним, что
)q(Oq21qN =++≤
). Рене Шуф (R. Schoof) предложил
алгоритм, вычисляющий N за O(
qlog
8
) двоичных операций.
Представление открытого текста. Мы намереваемся кодировать наши
открытые тексты точками некоторой заданной эллиптической кривой Е,
определенной над конечным полем
q
F
Мы хотим ото осуществить простым и
систематическим способом так чтобы открытый текст m (который можно
рассматривать как целое число из некоторого интервала) можно было легко
прочитать, зная координаты соответствующей точки
m
P . Заметим, что это
«кодирование» - не то же самое, что засекречивание. Позднее мы будем
рассматривать способы шифрования точек
m
P открытого текста. Однако
законный пользователь системы должен быть в состоянии восстановить т после
дешифрования точки шифртекста.
Следует сделать два замечания. Во-первых, не известно
детерминистического полиномиального (по log q) алгоритма для выписывания

Страницы