З урахуванням вказаного метод комплексного множення використовувати не рекомендується.

Побудова загальних параметрів з використанням випадково генерованої кривої зводиться до перевірки параметрів кривої та обчисленню порядку кривої. Ці методи не мають вказаних недоліків, але вимагають значно більших обчислювальних ресурсів. Серед цих методів необхідно виділити метод Скуфа, що має поліноміальну складність. В подальшому цей метод був удосконалений Алкіном та Елкистом, що дозволило суттєво знизити складність його реалізації. Так, складність алгоритму Скуфа складає

, (1.44)

а складність удосконаленого SEA

(1.45).

Проведені дослідження дозволяють зробити наступні висновки:

при виборі випадково вибраної еліптичної кривої забезпечується формування криптографічно стійких загальних параметрів;

алгоритм Скуфа забезпечує обчислення порядку будь-якої кривої як над простим так і над розширеним полем, але обчислювальна складність при цьому зростає зі збільшенням поліноміально;

алгоритм SEA має суттєво меншу складність обчислення порядку випадково генерованих еліптичних кривих.

Таким чином, на теперішній час розроблено та реалізовано метод побудови параметрів еліптичних кривих SEA, що задовольняє вимогам в частині криптографічної стійкості та має допустиму складність для кривих з порядком до .

12.2.3 Загальні параметри еліптичної кривої над полем

До загальних параметрів еліптичної кривої над полем відносяться наступні параметри:

Розмір поля , який визначає базове скінченне поле і є покажчиком базису, що використовується для подання елементів поля.

Бітовий рядок , якщо еліптична крива генерована випадково. В [62] наведено приклад того, як згенерувати випадкову еліптичну криву та контролювати її параметри, використовуючи для ініціалізації строку (необов’язково).

Параметри та еліптичної кривої, які визначають рівняння еліптичної кривої , що використовується: .

Базова точка порядку з координатами та .

Порядок базової точки при умові, що та - просте число.

Кофактор взаємозв’язку порядку кривої та порядку базової точки причому (не обов¢язково, якщо це потрібно в базовій схемі).

Крива, тобто її параметри 1-6, ні в якому випадку не повинні вибиратись із переліку значень, що виключені із списку (не рекомендуються або заборонені).

Аналіз показує [32,44, 52], що на нинішній час розроблено та рекомендовано до використання ряд еліптичних кривих над полем . Так рекомендується використовувати поля зі значенням . Особливістю цих значень є те, що для можуть використовуватись тільки поліноми , що мають вигляд

f (x) = ;

;

; (1.46)

;

.

 

Необхідно вказати, що при використанні пентаномів, тобто поліномів з п’ятьма членами у порівнянні з трьома, збільшується складність крипто перетворень.

Для вказаних довжин порядок поля вибраний таким чином, щоб його довжина була у два рази більшою довжин ключів для симетричних шифрів. В цьому випадку забезпечується однаковий рівень стійкості симетричного шифру та крипто перетворень в групі точок еліптичних кривих.

В [62, 63] приведено 10 кривих над розширеним полем , перші 5 з них наведено в таблиці додатку А. Там же наведені значення порядку базової точки.

 

В [52] наведені параметри еліптичних кривих , та для еліптичних кривих в поліноміальному базисі () та оптимальному нормальному базисі ().

Таким чином, на теперішній час розроблено методи та засоби обчислення загальних параметрів. Існує можливість використання як уже сформованих та представлених у стандартах [32, 44, 52] параметрів, так і формування параметрів з використанням методів Скуфа та Сатоха[135].

Враховуючи складність формування загальних параметрів, на перших порах застосування стандарту ДСТУ ISO/IEC 15946 можна рекомендувати використовувати загальні параметри, що наведені в [32, 44, 52]. В подальшому повинні бути розроблені спеціальні програмно-апаратні комплекси, що призначені для формування загальних параметрів еліптичних кривих.

 

12.2.4 Методи побудови загальних параметрів еліптичних кривих над полем .

На нинішній час найбільш найбільше придатним методом формування загальних параметрів в групі точок еліптичних кривих над полем є метод Сатоха[134, 135, 168 - 171].

Метод Сатоха, як і метод Скуфа, для визначення порядку кривої використовує властивості ендоморфізма Фробеніуса, але ідея алгоритму серйозно відрізняється від алгоритму Скуфа.

Обчислення виконуються в два етапи:

- підняття циклу ізогенії та коефіцієнтів кривої;

- обчислення сліду ендоморфізма Фробеніуса, на базі якого визначається порядок кривої.

Підняття виконується послідовним підняттям - інваріантів, коефіцієнтів кривої разом з підняттям підгруп - крутіння з попереднім обчисленням циклу кривих та - інваріантів .

Для зниження обчислювальних затрат підняття виконується з використанням багатомірної ітерації Ньютона, що дозволяє виконати одночасний підйом. Це дозволяє обчислити спряженні інваріанти не обчислюючи значення ендоморфізму Фробеніуса.

Більш детально метод Сатоха генерації загальних параметрів еліптичної кривої наведений в [170, 171 ].

 

12.3. Аналіз основних проблемних питань відносно побудування загально системних параметрів для еліптичних кривих

Проблемні питання та їх вирішення

Побудова загальносистемних параметрів є початковим етапом криптографічних перетворень в групі точок еліптичних кривих. Від рівня їх криптографічної стійкості залежить стійкість додатків, які використовують вказані параметри. Постійне вдосконалення методів та засобів криптоаналізу вимагає розв’язку задач, яка полягає в побудові наборів загальносистемних параметрів для криптографічних перетворень з різними рівнями стійкості.

Загальносистемні параметри розподіляють між користувачами повноважні органи або їх можна отримати в стандартизованому вигляді. В теперішній час в світі триває процес створення та введення в дію нових стандартів.

Метою цього параграфу є вивчення алгоритмів та методів, побудови еліптичних кривих придатних до застосування в криптографічних перетворення, що застосовуються в міжнародному стандарті ISO/IEC 15946-5: 2009(Е).

Область застосування стандарту обмежена криптографічними методами, що застосовують еліптичні криві, що задані над скінченими полями простого степеневого порядку (простого порядку та характеристики два, три). Стандарт ISO/IEC 15946-5 не повністю описує реалізацію методів, які він визначає, тому продукти, що сумісні з цим міжнародним стандартом, можуть бути несумісними між собою.

Стандартом передбачено:

· побудова псевдо - випадкових еліптичних кривих прийнятного порядку, застосовуючи методи обчислення порядку еліптичної кривої,

· побудова еліптичних кривих прийнятного порядку за допомогою методу комплексного множення,

· побудова еліптичних кривих, за допомогою підняття еліптичної кривої, яку задано над полем малої характеристики до кривої, яка задана над розширенням даного поля, ступеня який забезпечує достатній рівень захисту.

Побудова псевдо - випадкових еліптичних кривих в даному стандарті передбачає генерацію кривих як над простим полем так і над розширенням поля характеристики два .