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