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