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

UptoLike

ВУЗ: 

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

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

Рубрика: 

где от эллиптической кривой Е зависит лишь целое число а. Значение а связано с числом
N =
1
N соотношением N = q + 1 - а. Кроме того, дискриминант квадратного трехчлена в
числителе отрицателен (т.е.
qa 4
2
≤ – теорема Хассе), таким образом, этот трехчлен имеет
два комплексно сопряженных корня
α
и
β
, оба по модулю равные q (точнее, корнями
являются 1/
α
и 1/
β
, а
α
,
β
— корни «возвратного» уравнения).
3амечание.
Если записать числитель (8) в виде )1)(1( TT
β
α
−
−
и затем взять произ-
водную от логарифмов обеих частей (заменяя левую часть по формуле (7), определяющей
дзета-функцию), то нетрудно убедиться, что формула (8) эквивалентна последовательно-
сти соотношений
rrr
r
qN
βα
−−+= 1, r = 1,2,...
Так как
α
и
β
, наряду с а, определяются значением N =
i
N , то число точек над по-
лем
q
F
однозначно определяет число точек над любым его расширением. Таким образом,
теорему Вейля для эллиптических кривых можно использовать, в частности, для нахож-
дения числа точек над расширениями высокой степени.
Пример 5.
Легко вычисляется дзета-функция эллиптической кривой
32
xyy =+ над
2
F , так как имеется всего три
2
F -точки. Она равна ))21)(1/(()21(
2
TTT −−+ . Таким обра-
зом, обратные корни числителя – это
2i± . Отсюда следует формула
⎪
⎩
⎪
⎨
⎧
−−+
+
=
четно.если,)2(212
нечетно,если,12
2/
r
r
N
rr
r
r
(9)
В заключение этого параграфа заметим, что существует много аналогий между
группой
q
F -точек на эллиптической кривой и мультипликативной группой
∗
q
F
. Например,
по теореме Хассе они имеют примерно одинаковое число элементов.
Однако абелевы группы, которые строятся по эллиптическим кривым, имеют
одно значительное преимущество, которое объясняет их ценность для криптогра-
фии: для одного и того же большого q существует богатый выбор различных эллип-
тических кривых с разными значениями N. Эллиптические кривые составляют бо-
гатый источник «естественно возникающих» конечных абелевых групп, и это от-
крывает большие возможности для применения в криптографии.
УПРАЖНЕНИЯ
1. Пусть Е – эллиптическая кривая, определенная над С, уравнение (1) которой
имеет коэффициенты
а, b ∈ R; тогда точки Е с вещественными координатами образуют
подгруппу. Описать все возможные виды структуры такой подгруппы комплексной кри-
вой
Е (которая как группа изоморфна произведению окружности на себя). Приведите
пример для каждой из них.
2. Сколько точек
Р порядка n (т.е. таких, что nP = О) имеется на эллиптической
кривой над
С? Сколько таких точек на эллиптической кривой над R?
3. Привести пример эллиптической кривой над
R, имеющей в точности 2 точки по-
рядка 2, и пример кривой, имеющей в точности 4 точки порядка 2.
4. Пусть
Р – точка на эллиптической кривой над R. Предположим, что Р не есть
точка в бесконечности. Найти геометрическое условие, эквивалентное тому, что
Р – точка
порядка а) 2; б) 3; в) 4.
5. Каждая из следующих точек имеет конечный прядок на данной эллиптической
кривой над
Q. Найти в каждом случае порядок P.
a) P = (0, 16) на 256
32
+= xy .
б)
P =
⎟
⎠
⎞
⎜
⎝
⎛
2
1
,
2
1
на
xxy
4
1
32
+= .

Страницы