Складність деяких методів експоненціювання точки кривої

Складність деяких методів експоненціювання точки кривої

Найпоширенішою операцією у всіх криптографічних алгоритмах є - кратне додавання точки, позначуване як

Цю операцію звичайно називають скалярним множенням, або, звертаючись до термінології мультиплікативної групи, експоненціюванням точки кривої.

З метою підвищення продуктивності під час обчислення точки багатьма авторами запропоновано різні методи. Дамо стислий опис й оцінку складності найпоширеніших з них.

Підхід до розрахунку точки може відрізнятися залежно від того, чи є точка фіксованою (заздалегідь відомою) або довільною точкою. У першому випадку завжди можна користуватися передрозрахунками точок, наприклад,, які зберігаються в пам’яті. Двійкове подання числа дозволяє селектрувати ті з них, які в результаті підсумовування утворять точку. У другому, більш загальному випадку, всі обчислення доводиться проводити в реальному часі.

Нехай порядок і число подано у двійковій системі

Розглянемо спочатку основні алгоритми експоненціювання при невідомій заздалегідь точці

експоненціювання алгоритм скалярне множення

Алгоритм подвоєння-додавання

Це найприродніший і найпростіший метод, при якому обчислення здійснюються за формулою

Ці обчислення на основі методу розрахунку ліворуч-праворуч здійснюються за допомогою наступного алгоритму.

Алгоритм 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 й алгоритму максимальної пам’яті при