Контрольная работа Складність деяких методів експоненціювання точки кривої
Работа добавлена на сайт bukvasha.net: 2015-10-25Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего
от 25%

Подписываем
договор
Складність деяких методів експоненціювання точки кривої
Найпоширенішою операцією у всіх криптографічних алгоритмах є
Цю операцію звичайно називають скалярним множенням, або, звертаючись до термінології мультиплікативної групи, експоненціюванням точки кривої.
З метою підвищення продуктивності під час обчислення точки
Підхід до розрахунку точки
Нехай порядок
Розглянемо спочатку основні алгоритми експоненціювання при невідомій заздалегідь точці
експоненціювання алгоритм скалярне множення
Алгоритм подвоєння-додавання
Це найприродніший і найпростіший метод, при якому обчислення здійснюються за формулою
Ці обчислення на основі методу розрахунку ліворуч-праворуч здійснюються за допомогою наступного алгоритму.
Алгоритм 1.
Вхід:
Вихід:
1.
2.
2.1
2.2
3.
Реалізація методу вимагає
Алгоритм подвоєння-додавання-віднімання
Попередній алгоритм можна вдосконалити, якщо вести додаткову операцію-віднімання точки. Цей метод запропонований в 1990 році Ф. Морейном і Дж. Олівосом. Наприклад, число
Алгоритм 2.
Вхід: позитивне ціле число
Вихід:
1.
2.
2.1
2.2
2.3
3.
Після розрахунку
Алгоритм 3.
Вхід:
Вихід:
1.
2.
2.1
2.2
2.3
3.
Метод вікон з алгоритмом подвоєння - додавання - віднімання
Якщо в криптосистемі є резерви пам'яті, їх можна задіяти для подальшого збільшення швидкості обчислень. Ідея в тому, що замість точки
Для цього розраховується за допомогою алгоритму 2 трійкове число
Назвемо
Цих вікон достатньо для формування числа
У загальному випадку в пам'яті зберігається
Алгоритм 4.
Вхід:
Вихід:
1.
2.
3.
3.1
3.2
4.
Нехай, наприклад,
Перший крок алгоритму 4 у загальному випадку вимагає
Метод Монтгомері
Розглянемо метод Монтгомері. Нехай
Отже, знаючи
Кожна така ітерація вимагає одного подвоєння й одного додавання з використанням формули (1).
Після останньої ітерації,
Використовуючи проективні координати, можна позбутися від інвертування, і кожна ітерація вимагатиме шість множень. Усього ж трудомісткість алгоритму 5, що реалізує метод експоненціювання Монтгомері, дорівнює
Алгоритм 5. Метод експоненціювання Монтгомері.
Вхід:
Вихід:
1.
2.
2.1
3.1
3.2
4.
Алгоритм 5 вимагає однієї інверсії, а не двох, тому що можна обчислити
Методи експоненціювання при фіксованій точці
Фіксованою точкою в криптосистемі завжди є генератор або базова точка криптосистеми порядку
Другим досить витонченим підходом є підхід на основі вікон з фіксованою базою. Замість двійкового подання числа використовується
Тоді
де
Ці обчислення здійснюються за допомогою наступного алгоритму.
Алгоритм 6.
Вхід: ширина вікна
Вихід:
1. Передрозрахунки:
2.
3.
3.1
3.2
4.
Середня обчислювальна складність алгоритму оцінюється кількістю додавань :
Метод вікон у цьому випадку більше продуктивний, ніж при невідомій точці, тому що передрозрахунки не входять в алгоритм експоненціювання. Якщо використати поряд з додаванням подвоєння точки, реалізувати алгоритм можна інакше. Два вікна точки
Всі можливі точки
Їхні двійкові подання дають першу пару точок
Далі реалізується алгоритм послідовних додавань і подвоєнь праворуч із двома вікнами, описаний нижче.
Алгоритм 7.
Вхід: ширина вікна
Вихід:
1. Передрозрахунки: обчислити всі точки
2. Подати число
3.
4.
4.1
4.2
5.
Обчислювальна складність цього алгоритму оцінюється числом групових операцій
Обмінюючи час обчислень на пам'ять, можна й далі підвищувати продуктивність експоненціювання точки кривої. Наприклад, для кожного вікна шириною
Таблиця 1 - Об'єм пам'яті
Метод | 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 |
Размещено на Allbest.ru