Складність деяких методів експоненціювання точки кривої
Складність деяких методів експоненціювання точки кривої
Найпоширенішою операцією у всіх криптографічних
алгоритмах є - кратне додавання
точки , позначуване як
Цю операцію звичайно називають скалярним множенням,
або, звертаючись до термінології мультиплікативної групи, експоненціюванням точки
кривої.
З метою підвищення продуктивності під час обчислення
точки багатьма авторами запропоновано
різні методи. Дамо стислий опис й оцінку складності найпоширеніших з них.
Підхід до розрахунку точки може відрізнятися залежно від того, чи є точка
фіксованою (заздалегідь відомою)
або довільною точкою. У першому випадку завжди можна користуватися передрозрахунками
точок, наприклад, , які зберігаються
в пам'яті. Двійкове подання числа дозволяє селектрувати ті з них, які в результаті підсумовування
утворять точку . У другому, більш
загальному випадку, всі обчислення доводиться проводити в реальному часі.
Нехай порядок і число подано у двійковій системі
Розглянемо спочатку основні алгоритми експоненціювання
при невідомій заздалегідь точці
експоненціювання алгоритм скалярне множення
Алгоритм подвоєння-додавання
Це найприродніший і найпростіший метод, при якому
обчислення здійснюються за формулою
Ці обчислення на основі методу розрахунку ліворуч-праворуч
здійснюються за допомогою наступного алгоритму.
Алгоритм 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
|
A