- •О. Н. Жданов в. А. Чалкин эллиптические кривые: основы теории и криптографические приложения
- •Оглавление
- •П редисловие
- •Эллиптические кривые
- •§ 1. Алгебраические кривые и эллиптические кривые
- •Список уравнений кривых с целыми коэффициентами,
- •Список уравнений кривых с целыми коэффициентами,
- •§ 2. Группа точек эллиптической кривой
- •Ранги эллиптических кривых 𝛦, задаваемых уравнениями
- •Ранги эллиптических кривых 𝛦, задаваемых уравнениями
- •Значения для 𝑥 от 0 до 22
- •Точки кривой
- •§ 3. Применение эллиптических кривых в задаче факторизации чисел
- •Контрольные задания
- •Глава 2 Криптосистемы на эллиптических кривых
- •§ 1. Кодирование и дискретное логарифмирование
- •§ 2. Ключевой обмен и шифрование с использованием группы точек эллиптической кривой
- •Вычислительные усилия, необходимые для криптоанализа при использовании эллиптических кривых и rsa
- •§ 3. Алгоритм цифровой подписи, основанный на группе точек эллиптической кривой
- •Контрольные задания
- •Глава3 . Аспекты практической реализации криптографических алгоритмов на эллиптических кривых
- •§ 1. Эффективная реализация элементарных операций
- •§ 2. Определение количества точек на кривой
- •§ 3. Использование стандартных кривых
- •§ 4. Применение эллиптических кривых в криптографии
- •Алфавит точек эллиптической кривой для выполнения индивидуальных заданий
- •Пример выполнения контрольного задания 4.Умножение точки на число.
- •Пример3.Генерация подписи
- •Пример 4.Проверка подписи
- •Контрольные задания
- •1. Шифрование
- •2. Расшифрование
- •3. Сложение точек
- •5. Генерация подписи
- •6. Проверка подписи
- •Практические задания
- •Послесловие
- •Библиографический список
- •3. Определения и обозначения
- •Эллиптические кривые: основы теории и криптографические приложения
Контрольные задания
Докажите, что множество допустимых преобразований коорди-нат образует группу относительно операции композиции преобразований.
Докажите, что множество всех эллиптических кривых над дан-ным полем разбивается на классы эквивалентности относительно отно-шения изоморфизма.
Докажите, что любая эллиптическая кривая над полем 𝕂 харак-теристики, отличной от 2, изоморфна кривой вида
= + + 𝑥 + , ∈ 𝕂.
Докажите, что любая эллиптическая кривая над полем 𝕂 харак-теристики ≠2,3 изоморфна кривой вида
=
+
,
∈
𝕂.
Докажите, что любая эллиптическая кривая над полем 𝕂 харак-теристики 2 изоморфна кривой вида
+ 𝑥𝑦 = + + , ∈ 𝕂 (несуперсингулярные кривые)
или кривой вида
+
𝑦
=
+
+
,
∈
𝕂
(суперсингулярные
кривые).
6. Пусть 𝐸– эллиптическая кривая, определенная над ℂ, уравнение (1) которой имеет коэффициенты 𝑎, 𝑏 ∈ ℝ; тогда точки 𝐸 с вещественными координатами образуют подгруппу. Опишите все возможные виды структуры такой подгруппы комплексной кривой 𝐸 (которая как группа изоморфна произведению окружности на себя). Приведите пример для каждой из них.
7. Сколько точек 𝑃 порядка 𝑛 (т. е. таких, что 𝑛P = 𝒪) имеется на эллиптической кривой над ℂ? Сколько таких точек на эллиптической кривой над ℝ?
8. Приведите пример эллиптической кривой над ℝ, имеющей в точности 2 точки порядка 2, и пример кривой, имеющей в точности 4 точки порядка 2.
9. Пусть Р – точка на эллиптической кривой над ℝ. Предположим, что Р не есть точка в бесконечности. Найдите геометрическое условие, эквивалентное тому, что Р – точка порядка: а) 2; б) 3; в) 4.
10. Каждая из следующих точек имеет конечный порядок на данной эллиптической кривой над ℚ. Найдите в каждом случае порядок P:
a)
P
= (0, 16) на
б)
P
=
на
в)
P
= (3, 8) на
.
г)
P
= (0,0) на
.
11. Выведите формулы сложения, аналогичные (16)–(17), для эллиптических кривых над полем характеристики 2, 3 (см. уравнения (18),(19).
12. Докажите, что число -точек на каждой из следующих эллиптических кривых равно q + 1:
а) , когда q 3 (mod 4);
б)
,
когда q
2 (mod
3) (q
нечетное);
в)
,
когда q
2 (mod
3) (здесь q
может быть четным).
13. Для всех степеней нечетных простых чисел до 27 включительно найдите порядок и тип группы -точек на эллиптических кривых и (в последнем случае – при р 3). В некоторых случаях нужно будет проверить, сколько точек имеют порядок 3 или 4.
14. Пусть и пусть эллиптическая кривая E над имеет уравнение :
а) выразите координаты –Р и 2Р в терминах координат Р;
б) покажите, что при q = 16 каждая Р Е есть точка порядка 3;
в)
покажите, что любая точка Е
с координатами в
фактически есть точка с координатами
в
.
Далее с помощью теоремы Хассе при q
= 4 и 16
определите число точек на кривой.
15.
Вычислите дзета-функцию кривой
над
для р
= 2, 3, 5, 7, 11, 13. (Сначала покажите, что
=
1.) Пусть N(x)
=
обозначает норму комплексного числа.
В терминах нормы найдите простую формулу
для
.
