Складність деяких методів експоненціювання точки кривої
Найпоширенішою операцією у всіх криптографічних алгоритмах є
- кратне додавання точки
, позначуване як
Цю операцію звичайно називають скалярним множенням, або, звертаючись до термінології мультиплікативної групи, експоненціюванням точки кривої.
З метою підвищення продуктивності під час обчислення точки
багатьма авторами запропоновано різні методи. Дамо стислий опис й оцінку складності найпоширеніших з них.
Підхід до розрахунку точки
може відрізнятися залежно від того, чи є точка
фіксованою (заздалегідь відомою) або довільною точкою. У першому випадку завжди можна користуватися передрозрахунками точок, наприклад,
, які зберігаються в пам'яті. Двійкове подання числа
дозволяє селектрувати ті з них, які в результаті підсумовування утворять точку
. У другому, більш загальному випадку, всі обчислення доводиться проводити в реальному часі.
Нехай порядок
і число
подано у двійковій системі
Розглянемо спочатку основні алгоритми експоненціювання при невідомій заздалегідь точці
експоненціювання алгоритм скалярне множення
Алгоритм подвоєння-додавання
Це найприродніший і найпростіший метод, при якому обчислення здійснюються за формулою
Ці обчислення на основі методу розрахунку ліворуч-праворуч здійснюються за допомогою наступного алгоритму.
Алгоритм 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 оптимальним виявляється вікно шириною
, а при
- вікно шириною
Метод Монтгомері
Розглянемо метод Монтгомері. Нехай
з
Позначимо
Можна перевірити, що
(1)
Отже, знаючи
- координати точок
й
, можна обчислити
координати точок
й
, перейти до пари
, або до пари .
Кожна така ітерація вимагає одного подвоєння й одного додавання з використанням формули (1).
Після останньої ітерації,
- координата точки
може бути відновлена з
- координати точки
й
- координат точок
і
за формулою
Використовуючи проективні координати, можна позбутися від інвертування, і кожна ітерація вимагатиме шість множень. Усього ж трудомісткість алгоритму 5, що реалізує метод експоненціювання Монтгомері, дорівнює
причому алгоритм не вимагає додаткової пам'яті на зберігання попередньо обчислених змінних, а час його роботи не залежить від значення
Алгоритм 5. Метод експоненціювання Монтгомері.
Вхід:
Вихід:
1.
2.
2.1
3.1
3.2
4.
Алгоритм 5 вимагає однієї інверсії, а не двох, тому що можна обчислити
, а
потім отримати множенням на
. Можна домогтися істотного збільшення продуктивності, якщо операцію подвоєння замінити операцією ділення точки на два. Виграш до 40% при цьому досягається у зв'язку з відсутністю операції інверсії елемента в полі. Крім того, групові операції послідовних ділень у НБ зводяться практично до однієї операції множення в полі.
Методи експоненціювання при фіксованій точці
Фіксованою точкою в криптосистемі завжди є генератор або базова точка криптосистеми порядку
. Такі точки - це відкриті ключі користувачів. Якщо в системі є резерв пам'яті, його можна використати для зберігання заздалегідь розрахованих точок. Наприклад, якщо обчислити й записати в пам'яті точки
, то для визначення скалярного добутку
залишиться лише обчислити суми точок відповідно до двійкового подання
. У середньому для цього буде потрібно лише
операцій. Їхнє число можна зменшити до
операцій додавання й віднімання, якщо скористатися трійковим поданням .
Другим досить витонченим підходом є підхід на основі вікон з фіксованою базою. Замість двійкового подання числа використовується
-е із передобчислюванням точок
. Дійсно, нехай
-е подання числа
має вигляд
Тоді
де
Ці обчислення здійснюються за допомогою наступного алгоритму.
Алгоритм 6.
Вхід: ширина вікна
,
,
Вихід:
1. Передрозрахунки:
2.
3.
3.1
3.2
4.
Середня обчислювальна складність алгоритму оцінюється кількістю додавань :
.
Метод вікон у цьому випадку більше продуктивний, ніж при невідомій точці, тому що передрозрахунки не входять в алгоритм експоненціювання. Якщо використати поряд з додаванням подвоєння точки, реалізувати алгоритм можна інакше. Два вікна точки
шириною
кожне можна подати у вигляді:
;
Всі можливі точки
й
обчислюються на етапі передрозрахунків і записуються на згадку. Загальна кількість цих точок
зростає експоненційно зі збільшенням ширини вікна
. Двійкове подання точки
розбивається далі на
фрагментів шириною
. У кожному такому фрагменті відбираються старші розряди й розряди зі зрушенням вправо на
(тобто на половину фрагмента).
Їхні двійкові подання дають першу пару точок
й
, які складаються, після чого їхня сума подвоюється.
Далі реалізується алгоритм послідовних додавань і подвоєнь праворуч із двома вікнами, описаний нижче.
Алгоритм 7
.
Вхід: ширина вікна
,
,
,
Вихід:
1. Передрозрахунки: обчислити всі точки
й
,
2. Подати число
у вигляді конкатенації фрагментів шириною
Нехай
означає
й біт фрагмента
3.
4.
4.1
4.2
5.
Обчислювальна складність цього алгоритму оцінюється числом групових операцій
Обмінюючи час обчислень на пам'ять, можна й далі підвищувати продуктивність експоненціювання точки кривої. Наприклад, для кожного вікна шириною
можна заздалегідь розрахувати
точок, при цьому на згадку рийдеться записати
точок. Операція подвоєння в цьому випадку не використовується, а складність оцінюється числом
додавань. Цей алгоритм назвемо алгоритмом максимальної пам'яті. У табл.13.1 дані для порівняння величини пам'яті
й тимчасової складності
(числа групових операцій) алгоритму 6 й алгоритму максимальної пам'яті при
. В обох випадках зі збільшенням ширини вікна збільшується пам'ять і знижується число групових операцій. Очевидно, що останній алгоритм за наявності більших резервів пам'яті дозволяє істотно прискорити операцію експоненціювання фіксованої точки
Таблиця 1 - Об'єм пам'яті
й тимчасова складність
(число групових операцій) алгоритму 6 й алгоритму максимальної пам'яті при
Метод |
W
= 3 |
W
= 4 |
W
= 5 |
W
= 6 |
M
|
S
|
M
|
S
|
M
|
S
|
M
|
S
|
Алгоритм 6 |
14 |
900 |
30 |
725 |
62 |
632 |
126 |
529 |
Алгоритм
максимальної пам'яті.
|
469 |
58 |
750 |
46 |
1280 |
38 |
2079 |
33 |
|