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

UptoLike

ВУЗ: 

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

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

Рубрика: 

ное сложение – аналогом возведения в степень. Чтобы построить криптографическую
систему, используя эллиптические кривые, нужно найти «трудную проблему», соответст-
вующую разложению на множители произведения двух простых чисел или дискретному
логарифмированию.
Цель этого параграфа – описание построения криптографических систем с откры-
тым ключом, основанных на конечной абелевой группе точек эллиптической кривой, оп-
ределенной над
q
F . Прежде чем описывать криптосистемы, нужно обсудить некоторые
вспомогательные понятия.
Пример эллиптической кривой над конечным полем.
Особый интерес для криптографии представляет объект, называемый эллиптиче-
ский группой по модулю р, где р является простым числом. Такая группа определяется
следующим образом. Выберем два неотрицательных целых числа, а и b, которые меньше
р и удовлетворяют условию
0)(mod274
22
≠+ pba
Тогда
),( baE
p
обозначает эллиптическую группу по модулю р, элементами которой
(х, у) являются пары неотрицательных целых чисел, которые меньше р и удовлетворяют
условию
)(mod
32
pbaxxy ++=
вместе с «точкой в бесконечности» О.
Например, пусть р = 23. Рассмотрим эллиптическую кривую 1
32
++= xxy . В этом
случае a = b = 1 и мы имеем 08)23(mod12714
22
≠=×+× , что удовлетворяет условиям
эллиптической группы по модулю 23.
Рассматриваются только целые значения от (0, 0) до (р, р) в квадранте неотрица-
тельных чисел, удовлетворяющих уравнению по модулю р. В таблице 1 представлены
точки (отличные от О), являющиеся элементами )1,1(
23
E . В нашем случае такой список
можно создать по следующим правилам.
1. Вычисляем значения )23(mod
2
y (см. таблицу 1).
Таблица 1. Значения )23(mod
2
y для y от 0 до 22
y
2
y (mod 23)
0 0
1 1
2 4
3 9
4 16
5 2
6 13
7 3
8 18
9 12
10 8
11 6
12 6
13 8
14 12
15 18
16 3
17 13
18 2
19 16
20 9
21 4
22 1
2.Вычисляем значения )23(mod1
32
++= xxy (см. таблицу 2).
Таблица 2. Значения )23(mod1
3
++ xx для x от 0 до 22
x
)23(mod1
3
++ xx
0 1
1 3
2 11
3 8
4 0
5 16

Страницы