Основою даного алгоритму побудування псевдо випадкових кривих є метод, який було застосовані в стандарті іеее р 1363-2000.

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

Недоліком метода P. Скуфа є велика степінь поліномів ділення, на основі яких виконано обчислення значення сліду відображення ендоморфізма Фробеніуса. Один зі шляхів подолання даного недоліку полягає в використанні поліномів меншого ступеня або розкладення поліномів ділення на множники, що дозволяє визначити координати точок крутіння використовуючи менший об’єм пам’яті в порівнянні з методом Р. Скуфа.

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

На основі метода, запропонованого Р. Скуфом, було розроблено вдосконалений метод обчислення порядку кривої під назвою SEA [4,5], який може бути застосовано, як над полем характеристики , так і над розширенням поля характеристики два. Метод SEA базується на пошуку значення сліду ендоморфізму Фробеніуса з рівняння

Можна зробити висновок, що вдосконалення Аткіна та Ілкіса, на основі яких побудований метод під назвою SEA, дозволяють зменшити обчислювальну складність методу Р. Скуфа шляхом використання поліномів степеня або поліномів степеня .

Обчислювальна складність алгоритму, який базується на методі SEA, та має таку ж назву дорівнює . Недоліком цього метода є зростання коефіцієнтів поліномів при зростанні значення . Наприклад, вільний член полінома дорівнює 157 000 000 000, а вільний член полінома дорівнює 1855425871872000000000 [3]. Обчислення порядку кривої, для полів вимірності від до за допомогою даного методу неможливо здійснити за прийнятний час завдяки наведеного недоліку.

Застосування алгоритму Скуфа для обчислення порядку еліптичної кривої в стандарті ISO/IEC 15946-5 замість інших швидкодійних, в порівнянні з ним, алгоритмів пояснено тим, що цей алгоритм застосовано при розробці алгоритму перевірки числа на простоту Голдвассером і Килиана [8,9]. Алгоритм перевірки числа на простоту за допомогою еліптичних кривих Голдвассера і Килиана також включено до стандарту ISO/IEC 15946-5. Вказаний ймовірнісний алгоритм випадковим чином обирає еліптичну криву і перевіряє виконання деяких умов. На виході видається відповідь є число простим або складним, або знову здійснюється випадковий вибір. Вказаний алгоритм працює доти доки перевірка на простоту буде виконана чи закінчиться час відведений для прогону цього алгоритму. Якщо за допомогою алгоритму Голдвассера—Килиана доведено простоту числа, тоді він також видає «сертифікат» простоти.

2) Метод комплексного множення, який запропоновано в роботі [13] взятий за основу методу, що запропонований в даному стандарті. Він передбачає:

1. По заданому порядку еліптичної кривої, яка визначена над полем , з кофактором та великим простим порядком (160 біт та більше) визначити параметр , де та квадратичний лишок по модулю порядку поля;

2. Знайти коефіцієнти мінімального полінома -ого інваріанта (полінома Гільберта);

3. Обчислити корені полінома Гільберта по модулю порядку поля ;

4. Визначити коефіцієнти еліптичної кривої над полем (усі операції здійснюють по модулю );

5. Обирати випадкову точку на еліптичній кривій та перевірити умову , де - нескінчено віддалена точка. Якщо умова виконана, тоді криву знайдено. Якщо ні, тоді будують криву крутіння та виконують алгоритм знову;

6. При умові невиконання рівності для кривої крутіння, де - випадкова точка кривої крутіння повторюють процедуру побудови еліптичної кривої для іншого кореня полінома Гільберта.

 

3) Стандартом ISO/IEC 15946-5 також передбачено застосування еліптичних кривих, які побудовано за допомогою білінійного спарювання, а саме Miyaji-Nakabayashi-Takano curve, Barreto-Naehrig curve, Freeman curve, Cocks-Pinch curve. Вказані методи побудування еліптичних кривих, що наведено в даному стандарті, базуються на розв’язанні порівняння , де є поліномом Гільберта для дискримінанту , яке було застосованого для обчислення порядку еліптичної кривої методом комплексного множення.

4) В стандарті ISO/IEC 15946-5 наведено алгоритм обчислення порядку еліптичної кривої за допомогою підняття. Вказаний алгоритм дозволяє, застосовуючи рівняння еліптичної кривої над полем та його порядок, отримати значення порядку еліптичної кривої, яка визначена над полем , базову точку цієї кривої. Даний алгоритм обчислення порядку еліптичної кривої відрізняється від ймовірнісних алгоритмів Сатоха та алгебраїчно-геометричних значень тим, що в вказаному алгоритмі обирають еліптичну криву, яка визначена над простим полем малого порядку. Завдяки тому, що порядок поля малий є можливість обчислити порядок еліптичної кривої дуже швидко, використовуючи, наприклад, алгоритм Скуфа. Далі за допомогою даного порядку обчислюють порядок еліптичної кривої, яка визначена над полем . На відміну цього методу, методи Сатоха та алгебраїчно-геометричних значень [12], використовують криву, яка визначена над полем та знаходять її порядок застосовуючи підняття до розширення кільця р -адичних цілих степені .

 

Таким чином, стандарт ISO/IEC 15946-5 забезпечує:

1. Базові методи побудови еліптичних кривих та перевірки їх на придатність до застосування в криптографічних перетвореннях були застосовані з стандартів IEEE P1363-2000, Standard Specifications for Public-Key Cryptography, ISO/IEC 9796 Information technology — Security techniques — Digital signature schemes, ISO/IEC 18032:2005, Information technology — Security techniques — Prime number generation;

2. Застосовані способи побудування еліптичних кривих за допомогою спарювання Вейля;

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

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

 

Основна література до 12.3

1. Schoof R. Counting points on an elliptic curve over finite fields / Schoof R. // Proc. Journees Arithmetiques. – 1995. – № 93. – P. 219–252.

2. Бухштаб А.А. Теория чисел / А.А. Бухштаб М. Просвещение, 1996. ‑ 386с.

3. Бессалов А. Криптосистемы на эллиптических кривых / А. Бессалов, А. Телиженко. – К.: Політехніка, 2004. – 224 с.

4. Henri Cohen Handbook of Elliptic and Hyperelliptic Curve Cryptography / Henri Cohen Gerhard Frey.‑ Taylor & Francis Group, LLC, 2006 ‑ 843 P

5. Fouquet M. Isogeny volcanoes and the SEA algorithm In Algorithmic number theory / Fouquet M., Morain F. // Notes in Comput. Sci. – 2000, – Vol. 2369 – P. 276– 291.

6. Skjernaa B. Satoh’s algorithm in characteristic 2 / Skjernaa B. // Mathematics of computation. – 2003. – № 72. – P. 477–487.

 

7. Blake. Ian F. Elliptic Curves in Cryptography / Blake. Ian F., Seroussi G, Nigel P. // Cambridge University Press – 1999. – P.121–130.

8. Morain F. Primality proving using elliptic curves: an update // Proceedings of ANTS III. 1998. (Lect. Notes in Comput. Sci.; V. 1423). P. 111—127.

9. Adleman L., Huang M.-D.A. Primality testing and abelian varietes over finite fields. 1992. (Lect. Notes in Math.; V. 1512).

10. Atkin A. O.L., Morain F. Elliptic curves and primality proving // Math. Comp. 1993. V. 61 (203). P. 29—67.

11. Satoh T. Canonical lifting of elliptic curves and p – adic point counting. (theoretical background) / Satoh T. // Department of Mathematics, Faculty of Science, Saitame University. – 2001. – P. 1–21. 12. Н. Соhen, C Frey Handbook of elliptic end hyperelliptic curve cryptografy // Carman end hall / CRC – 2006, – 843 p.

13. L.C. Washington, “Elliptic Curves-Number Theory and Cryptography”, Chapman &Hall/CRC, edition, 2008