Введение
1 Операции в группе точек эллиптической кривой 14
1.1 Эллиптические кривые 14
1.2 Преобразования на основе эллиптических кривых 17
1.3 Операции на основе эллиптических кривых
1.3.1 Операции в простом поле 17
1.3.2 Арифметические операции с точкой 18
1.3.3 Скалярные арифметические операции 24
1.4 Композиция операций 27
1.4.1 Операции вида dP ЕВ Q 27
1.4.2 Операции вида dP 35
1.5 Метод замены умножений 42
1.5.1 Быстрые формулы для традиционных операций 44
1.5.2 Быстрые формулы для композитных операций 46
1.6 Многоосновные скалярные умножения 47
1.6.1 Метод многоосновного несовместного представления 47
1.6.2 Метод многоосновного несовместного представления с окном 48
1.6.3 Метод расширенного многоосновного несовместного представления с ок
2 Эффективные алгоритмы вычисления преобразований на основе эллип тических кривых 52
2.1 Архитектура системы алгоритмов 52
2.1.1 Уровень С\ 52
2.1.2 Уровень С-2 53
2.1.3 Уровень з 54
2.1.4 Уровень С 54
2.1.5 Уровень 5 55
2.2 Критерий эффективности алгоритмов вычисления преобразований на основе эллиптических кривых з
2.3 Эффективные эллиптические кривые 56
2.4 Эффективная операция DA 56
2.5 Эффективные алгоритмы скалярного умножения точки эллиптической кривой
2.5.1 Алгоритм на основе метода бинарного представления скаляра 57
2.5.2 Алгоритм на основе метода бинарной несовместной формы представления скаляра 64
2.5.3 Алгоритм на основе метода несовместной формы представления скаляра c окном 68
2.5.4 Алгоритм на основе метода несовместной формы представления скаляра со скользящим окном 2.6 Эффективные композитные операции 78
2.7 Эффективный алгоритм мультискалярного умножения
2.7.1 Быстрые предвычисления 85
2.7.2 Основная часть алгоритма 89
2.8 Выводы 89
3 Композиции алгоритмов вычисления преобразований на основе эллиптических кривых 91
3.1 Вычислительная сложность алгоритмов вычисления операций с большими це лыми числами 91
3.1.1 Операция сложения 91
3.1.2 Операция умножения 91
3.2 Вычислительная сложность операций в простом поле 93
3.2.1 Приведение по модулю 93
3.2.2 Мультипликативный обратный элемент 93
3.3 Алгоритмы скалярного умножения точки эллиптической кривой, полученные композициями 94
3.3.1 Алгоритмы без предварительных вычислений точек 94
3.3.2 Алгоритмы с предварительными вычислениями точек 105
3.4 Выводы 117
Заключение 118
Список литературы
