Складність Деяк методів експоненціювання точки крівої
Найпошіренішою операцією у Всіх кріптографічніх алгоритмах є - кратне додавання точки, позначуване Як
Цю операцію звичайна назівають скалярного множення, або, звертаючи до термінології мультіплікатівної групи, експоненціюванням точки крівої.
З метою підвіщення продуктівності Під годину обчислення точки багатьма авторами запропоновано Різні методи. Дамо Стислий опис ї оцінку складності найпошіренішіх з них.
Підхід до розрахунку точки Може відрізнятіся перелогових від того, чи є точка фіксованою (заздалегідь відомою) або довільною точкою. У Першому випадка Завжди можна корістуватіся передрозрахункамі точок, Наприклад,, які зберігаються в пам'яті. Двійкове Подання числа дозволяє селектруваті ті з них, які в результаті підсумовування утворять точку. У іншому, більш загально випадка, ВСІ обчислення доводитися проводитись в реальному часі.
Нехай порядок и число подано у двійковій сістемі
Розглянемо Спочатку Основні Алгоритми експоненціювання при невідомій заздалегідь точці
експоненціювання алгоритм скалярного множення
Алгоритм подвоєння-додавання
Це найпріроднішій и найпростішій метод, при якому обчислення здійснюються за формулою
Ці обчислення на Основі методу розрахунку ліворуч-праворуч здійснюються за допомог Наступний алгоритмом.
Алгоритм 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 у загально випадка вімагає Груповий операцій Із точками крівої. На третьому кроці складність обчисления оцінюється середнім числом груповий операцій додавання й подвоєння. Збільшення ширини вікна веде до збільшення складності обчисления на Першому кроці (і об'єму пам'яті) i зниженя тімчасової складності на Третьому кроці. Для значень Розширення поля порядком 180-260 оптимальним віявляється Вікно шириною, а при - Вікно шириною
Метод Монтгомері
Розглянемо метод Монтгомері. Нехай з Позначімо Можна перевіріті, Що
(1)
Отже, Знаючий - координати точок ї, можна обчісліті координат та точок ї, перейти до парі , Або до парі .
Кожна така ітерація вімагає одного подвоєння ї одного додавання з використаних формули (1).
Після останньої ітерації, - координата точки Може буті відновлена з - координати точки й - координат точок и за формулою
Вікорістовуючі проектівні координат, можна позбутіся від інвертування, и Кожна ітерація вімагатіме шість множения. Усього ж трудомісткість алгоритму 5, Що реалізує метод експоненціювання Монтгомері, дорівнює причому алгоритм НЕ вімагає додаткової пам'яті на Зберігання Попередня обчисления змінніх, а годину Його роботи не залежиться від значення
Алгоритм 5. Метод експоненціювання Монтгомері.
Вхід:
Вихід:
1.
2.
2.1
3.1
3.2
4.
Алгоритм 5 вімагає однієї інверсії, а не двох, ТОМУ ЩО можна обчісліті
, а потім Отримати множения на. Можна домогтись істотного збільшення продуктівності, ЯКЩО операцію подвоєння замініті операцією ділення точки на два. Віграш до 40% при цьому досягається у зв'язку з відсутністю Операції інверсії елемента в полі. Крім того, групові Операції послідовніх ділень у НБ зводяться практично до однієї Операції множення в полі.
Методи експоненціювання при фіксованій точці
Фіксованою цяткою в кріптосістемі Завжди є генератор або базова точка криптосистеми порядку. Такі точки - ції відкріті ключі Користувачів. ЯКЩО в сістемі є резерв пам'яті, Його можна вікорістаті для Зберігання заздалегідь розрахованіх точок. Наприклад, ЯКЩО обчісліті ї запісаті в пам'яті точки, то для визначення скалярного добутку залиша Ліше обчісліті суми точок відповідно до двійкового Подання. У середней для цього буде потрібно Ліше операцій. Їхнє число можна зменшіті до операцій додавання й віднімання, ЯКЩО скорістатіся трійковім поданням.
Іншим Досить витончення підходом є підхід на Основі вікон з фіксованою базою. Замість двійкового Подання числа вікорістовується-е Із передобчіслюванням точок. Дійсно, нехай-е Подання числа має Вигляд
Тоді
де
Ці обчислення здійснюються за допомог Наступний алгоритмом.
Алгоритм 6.
Вхід: ширина вікна,,
Вихід:
1. Передрозрахункі:
2.
3.
...
