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