Применение эллиптических кривых в криптографии. Жданов О.Н - 14 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

6 16
7 6
8 15
9 3
10 22
11 9
12 16
13 3
14 22
15 10
16 19
17 9
18 9
19 2
20 17
21 14
22 22
Теперь сравниваем числа в правых столбцах таблиц 1 и 2. Число, попавшее в оба
столбца, определяет две точки кривой. Так, число 1 содержится и в правом столбце табли-
цы 1, и в правом столбце таблицы 2. Число 1 определяет точки (0,1) и (0,22); число 8 дает
тоже две точки, находим по левым столбцам их координаты: это (3,10) и (3,13), и т.д
. По-
лучаем таблицу 3.. Пара чисел (x, y), для которой )(mod
32
pbaxxy ++≡ , включается в
нашу таблицу соответствий: эта пара чисел, т.е. точка кривой, кодирует некоторый символ
языка открытых текстов.
Таблица 3. Точки группы )1,1(
23
E
(0, 1) (6, 4) (12, 19)
(0, 22) (6, 19) (13, 7)
(
1, 7
)
(
7, 11
)
(
13, 16
)
(1, 16) (7, 12) (17, 3)
(
3, 10
)
(
9, 7
)
(
17,20
)
(
3, 13
)
(
9, 16
)
(
18,3
)
(4, 0) (11, 3) ' (18,20)
(
5, 4
)
(
11, 20
)
(
19,5
)
(5, 19) (12, 4) (19,18)
Далее устанавливаем соответствие символов языка и точек кривой, например,
)1,0(→a ; )22,0(→б и т.д.
Кратные точки.
Для эллиптических кривых аналогом умножения двух элементов группы
∗
q
F
слу-
жит сложение двух точек эллиптической кривой Е, определенной над
q
F
. Таким образом,
аналог возведения в степень к элемента из
∗
q
F
– это умножение точки Р ∈ Е на целое чис-
ло k. Возведение в k-ю степень в
∗
q
F методом повторного возведения в квадрат можно
осуществить за O( klog qlog
3
) двоичных операций. Аналогично мы покажем, что кратное
kP ∈ Е можно найти за O( klog qlog
3
) двоичных операций методом повторного удвоения.
Пример 1.
Чтобы найти 100Р, записываем 100Р = 2(2(Р + 2(2(2(Р + 2Р))))) и прихо-
дим к цели, производя 6 удвоений и 2 сложения точек на кривой.
Предложение 1.
Пусть эллиптическая кривая Е определена уравнением Вейершт-
расса (уравнением (1), (2) или (3) из предыдущего параграфа) над конечным полем
q
F .
Если задана точка Р на Е, то координаты kP можно вычислить за О( klog qlog
3
) двоич-
ных операций.
Замечания.

Страницы