ОБЗОР СУЩЕСТВУЮЩИХ СПОСОБОВ ГЕНЕРАЦИИ ЭЛЛИПТИЧЕСКИХ КРИВЫХ

В настоящее время информационные технологии очень быстро развиваются одновременно с ростом ценности всякого рода цифровой информации. С ростом ценности одновременно возрастает стоимость защиты информации [2]. Именно по этой причине на данный момент актуально создание и использование защищенных систем шифрования данных.

Одной из разновидностей таких систем являются системы шифрования на основе эллиптических кривых. Согласно исследованиям НИСТ системы шифрования на основе эллиптических кривых при меньшей длине ключей позволяют обеспечить более высокий уровень безопасности данных.

При использовании таких систем шифрования возникает вопрос выбора основного параметра системы, а именно криптобезопасной эллиптической кривой [1].

Анализ способов генерации эллиптических кривых.

Можно выделить следующие способы генерации ЭК:

• Способ на основе алгоритма Шуфа
• Способ на основе алгоритма SEA
• Способ детерминированной генерации ЭК

Данные способы являются основными для генерации эллиптических кривых, у каждого из способов есть свои плюсы и минусы.

Способ на основе алгоритма Шуфа является частным случаем использования метода случайной генерации эллиптических кривых (ЭК), в котором для расчета числа точек ЭК над полем Fq используют алгоритм Шуфа.

Данный способ состоит из 4 основных этапов:

1 этап – получение случайной ЭК.

2 этап – вычисление количества точек ЭК над полем Fq используя алгоритм Шуфа.

3 этап – вычисления порядка циклической группы ЭК.

4 этап – проверка ЭК на криптостойкость.

Данный способ позволяет генерировать ЭК с заданным уровнем криптостокойсти, но процесс будет очень трудоемким и займет довольно большое количество времени. На основе данного способа был разработан следующий, более быстрый способ.

Способ на основе алгоритма SEA. Алгоритм SEA является усовершенствованным алгоритмом Шуфа и носит те же основные идеи расчета точек и использования самого алгоритма в генерации ЭК. По сути, в данном способе представлены те же этапы что и в способе на основе алгоритма Шуфа, с тем отличием, что на 2 этапе для расчета количества точек кривой будет использоваться алгоритм SEA. Работа алгоритма SEA изображена на рисунке 1.

Рисунок 1. Аалгоритм SEA для расчета числа точек кривой

Данный алгоритм состоит из следующих этапов:

1 этап – получение случайной ЭК.

2 этап – вычисление количества точек ЭК над полем Fq используя алгоритм SEA.

3 этап – вычисления порядка циклической группы ЭК.

4 этап – проверка ЭК на криптостойкость.

Данный способ, так же как и предыдущий позволяет генерировать криптостойкие ЭК, при этом он является более быстрым благодаря использованию усовершенствованного алгоритма SEA, который является более быстрым по сравнению с алгоритмом Шуфа.

Способ детерминированной генерации ЭК основывается на использовании алгоритма комплексного умножения для построения ЭК с известным порядком циклической группы точек. В данном алгоритме используется теорема Аткина и Морейна[3]: пусть p – нечетное простое число, такое, что справедливо равенство 4p=, где W и V целые. Тогда существует ЭК, определенная над Fp, такая что E(Fp)=p+1-W.

Число D, удовлетворяющее теореме, является дискриминантом ЭК. А сама ЭК обладаем комплексным умножением над. Таким образом, зная р и D, можно вычислить j-инвариант ЭК. С данным инвариантом можно построить ЭК порядка p+1-W. Кроме того, данный способ позволяет постро­ить ещё и ЭК порядка р+l+W. Эта техника генерации ЭК является методом комплексного умножения.

 Ниже приведены основные этапы представленного способа.

1 этап – вычисление дискриминанта ЭК. На данном этапе

2 этап – вычисление порядка циклической группы ЭК.

3 этап – построение ЭК.

4 этап – проверка криптостойкости ЭК

Данный способ позволяет довольно быстро генерировать криптостойкие ЭК, но при этом разнообразие кривых очень низкое за счет особенностей алгоритма генерации.

Таким образом, можно сделать вывод, что на текущий момент не существует способа генерации ЭК, который бы позволил быстро генерировать кривые в широком диапазоне их свойств.

Список литературы:

1. Колесников, П.В. Оценка стойкости преобразований в группе точек эллиптических кривых при использовании открытых параметров и ключей в качестве личных / П.В. Колесников// Правове, нормативне та метролопчне забезпечення системи захисту шформацн в УкраУнь - 2001. - вип. 2. - С. 95-98. 124
2. Пылин, В.В. Проблемы использования специальных эллиптических кривых в системах электронно-цифровой подписи / В.В.Пылин // Информационные технологии в профессиональной деятельности и научной работе: сборник материалов Всероссийской научно-практической конференции с международным участием: в 2 ч. - 4.2 - Йошкар-Ола: Марийский государственный технический университет, 2008. - С.148-150.
3. Atkin, A.O. Elliptic curves and primality proving / A.O. Atkin, F. Morain // Mathematics of Computation. - 1993. - Vol. 61. - P. 29-68.