Складність деяких методів експоненціювання точки кривої
Найпоширенішою
операцією у
всіх криптографічних
алгоритмах
є
- кратне додавання
точки
,
позначуване
як
![]()
Цю операцію звичайно називають скалярним множенням, або, звертаючись до термінології мультиплікативної групи, експоненціюванням точки кривої.
З метою
підвищення
продуктивності
під час обчислення
точки
багатьма авторами
запропоновано
різні методи.
Дамо стислий
опис й оцінку
складності
найпоширеніших
з них.
Підхід
до розрахунку
точки
може відрізнятися
залежно від
того, чи є точка
фіксованою
(заздалегідь
відомою) або
довільною
точкою. У першому
випадку завжди
можна користуватися
передрозрахунками
точок, наприклад,
,
які зберігаються
в пам'яті. Двійкове
подання числа
дозволяє селектрувати
ті з них, які в
результаті
підсумовування
утворять точку
.
У другому, більш
загальному
випадку, всі
обчислення
доводиться
проводити в
реальному часі.
Нехай
порядок
і число
подано у двійковій
системі

Розглянемо
спочатку основні
алгоритми
експоненціювання
при невідомій
заздалегідь
точці
![]()
експоненціювання алгоритм скалярне множення
Алгоритм подвоєння-додавання
Це найприродніший і найпростіший метод, при якому обчислення здійснюються за формулою

Ці обчислення на основі методу розрахунку ліворуч-праворуч здійснюються за допомогою наступного алгоритму.
Алгоритм 1.
Вхід:
![]()
Вихід:
![]()
1.
![]()
2.
![]()
2.1
![]()
2.2
![]()
3.
.
Реалізація
методу вимагає
операцій
подвоєння точки
й
додавань
,
де
- вага Хеммінга
двійкового
вектора
(число одиниць
цього вектора).
Оскільки в
середньому
число одиниць
випадкового
вектора дорівнює
,
загальне число
групових операцій
оцінюється
величиною
![]()
Алгоритм подвоєння-додавання-віднімання
Попередній
алгоритм можна
вдосконалити,
якщо вести
додаткову
операцію-віднімання
точки. Цей метод
запропонований
в 1990 році Ф. Морейном
і Дж. Олівосом.
Наприклад,
число
у двійковій
системі має
вага у
,
але його можна
подати як
з вагою
Ця ідея знижує
вагу Хеммінга
і, відповідно,
число групових
операцій. Реалізувати
алгоритм подвоєння
- додавання
віднімання
можна переходом
від двійкового
подання числа
до трійкового
з коефіцієнтами
Одне із властивостей
подання
- відсутність
у ньому суміжних
пар ненульових
елементів,
завдяки чому
зростає питома
вага нульових
елементів
.
Для розрахунку
використовується
наступний
алгоритм.
Алгоритм 2.
Вхід:
позитивне ціле
число
![]()
Вихід:
![]()
1.
![]()
2.
![]()
2.1
![]()
2.2
![]()
2.3
![]()
3.
![]()
Після
розрахунку
обчислюється
точка
методом ліворуч-праворуч
за допомогою
алгоритму 3.
Алгоритм 3.
Вхід:
![]()
Вихід:
![]()
1.
![]()
2.
![]()
2.1
![]()
2.2
![]()
2.3
![]()
3.
.
-подання
числа
може виявитися
на один біт
більше двійкового.
Водночас, для
випадкового
ймовірність
ненульових
елементів
і
знижується
від
до
,
тобто, у середньому,
для
- розрядного
числа їхня
кількість
оцінюється
величиною
.
Тоді загальне
середнє число
групових операцій
додавання
й подвоєння
в алгоритмі
3 можна оцінити
як суму
![]()
Метод вікон з алгоритмом подвоєння - додавання - віднімання
Якщо в
криптосистемі
є резерви пам'яті,
їх можна задіяти
для подальшого
збільшення
швидкості
обчислень. Ідея
в тому, що замість
точки
можна експоненціювати
і надалі складати
суміжні блоки
або вікна шириною
в
- поданні точки
![]()
Для цього
розраховується
за допомогою
алгоритму 2
трійкове число
,
що потім може
розбиватися
на блоки довжиною,
не менше
![]()
Назвемо
- вікном числа
непарний
коефіцієнт
утримуючий
хоча б один
ненульовий
елемент. Зазначимо,
що
![]()
.
Наприклад, при
маємо вісім
різних значень
![]()

Цих вікон
достатньо для
формування
числа
довільної
довжини
.
Зазначимо, що
парні коефіцієнти
в
- поданні числа
надлишкові,
тому що вони
утворяться
подвоєнням
непарних. На
першому етапі
передрозрахунків
розраховуються
й записуються
на згадку вісім
точок:
і
![]()
У загальному
випадку в пам'яті
зберігається
точок. Число
може бути визначене
за допомогою
модифікованого
алгоритму 2.
Модифікація
полягає в тому,
що:
на кроці 2.1 замість
необхідно
записати
,
де
означає ціле
число
,
певне в інтервалі
.
Далі обчислюється
точка
згідно з алгоритмом
4.
Алгоритм 4.
Вхід:
![]()

Вихід:
![]()
1.
![]()
2.
![]()
3.
![]()
3.1
![]()
3.2
![]()
![]()
![]()
4.
.
Нехай,
наприклад,
при цьому
й
Використання
трійкового
вимагає, мабуть,
двох додавань
точок, тоді як
у другому випадку
за рахунок
попереднього
розрахунку
точки
достатньо
одного додавання.
Число подвоєнь
однаково в обох
випадках. Зрозуміло
також, що виграш
за рахунок
вікна з'являється
лише при порівняно
більших довжинах
числа
![]()
Перший
крок алгоритму
4 у загальному
випадку вимагає
групових операцій
із точками
кривої. На третьому
кроці складність
обчислень
оцінюється
середнім числом
групових операцій
додавання й
подвоєння.
Збільшення
ширини
вікна веде до
збільшення
складності
обчислень на
першому кроці
(і об'єму пам'яті)
і зниження
тимчасової
складності
на третьому
кроці. Для значень
розширення
поля порядку
180-260 оптимальним
виявляється
вікно шириною
,
а при
- вікно шириною
![]()
Метод Монтгомері
Розглянемо
метод Монтгомері.
Нехай
![]()
з
Позначимо
Можна перевірити,
що