Изоморфизм несуперсингулярных кривых над полями характеристики 2 и кривых Эдвардса с одним параметром

[Введите текст]

Размещено на http://www.allbest.ru/

96

ІSSN 0485-8972 Радиотехника. 2014. Вып. 176

ИЗОМОРФИЗМ НЕСУПЕРСИНГУЛЯРНЫХ КРИВЫХ НАД ПОЛЯМИ ХАРАКТЕРИСТИКИ 2 И КРИВЫХ ЭДВАРДСА С ОДНИМ ПАРАМЕТРОМ

А.В. БЕССАЛОВ, А.А. ДИХТЕНКО

Введение

Форма Эдвардса эллиптической кривой над полем характеристики задает симметричную относительно координат кривую с порядком, кратным 4 [1, 2, 5, 6]. Для всех кривых этого класса групповая операция выполняется рекордно малым числом арифметических операций в поле [2, 5]. Наряду с простыми полями большой характеристики в криптографии широко применяются расширенные поля F₂^m характеристики 2. Несмотря на различия в форме записи, кривым Эдвардса над полями F₂^m и (при ) присущи сходные свойства [3, 4, 7]. Для двух типов кривых Эдвардса нуль абелевой группы представляется парой аффинных координат, а соответствующий групповой закон справедлив для произвольной пары точек кривой (включая совпадающие, обратные точки, и нуль группы) [2, 3]. Минимальный кофактор в порядке кривой Эдвардса над полем F₂^m равен 2. Задачей работы является поиск кривых Эдвардса, приемлемых для криптографии. эллиптический эдвардс криптография проективный

В настоящей работе рассматриваются кривые в форме Эдвардса над расширенными полями F₂^m. Анализ оценок сложности операций сложения и удвоения точек кривой Эдвардса над полем F₂^m приводит к выводу, что наибольшая производительность присуща кривым с одним параметром d = d₁ = d₂. Между несуперсингулярными кривыми и кривыми Эдвардса в общем виде над полями F₂^m существует изоморфизм [3]. В разд. 3 находим условия, при которых для данной эллиптической кривой найдется изоморфная кривая Эдвардса с одним параметром d. Для известных канонических кривых из национальных стандартов (ДСТУ 4145 - 2002 [8, 9] и FIPS 186-2 - 2000 [8]), удовлетворяющих полученным условиям, были найдены изоморфные кривые Эдвардса с одним параметром d . В случае ДСТУ 4145 - 2002 таких кривых две, в американском стандарте FIPS 186-2 - 2000 данные условия выполняются для четырех кривых Коблица.

Кривые Эдвардса над расширенными полями характеристики 2

Кривая Эдвардса над полем F₂^m описывается уравнением в аффинных координатах [3]

(1)

где - пара элементов поля, удовлетворяющих условиям и . Закон сложения точек кривой (1) универсален и имеет вид

,

.(2)

Полнота закона (2) - наиболее весомый аргумент для включения кривых Эдвардса над полями F₂^m в проекты будущих стандартов шифрования. Нуль группы , как видно из (2), не изменяет координат другой точки в сумме. Прочие свойства кривых Эдвардса над полями четных и нечетных характеристик подробно рассмотрены в работах [3, 4, 7] и [1, 2, 5, 6] соответственно. Очевидно, что производительность криптосистемы в значительной мере зависит от ее параметров, и в случае кривых над полями F₂^m, актуален вопрос нахождения таких коэффициентов кривой Эдвардса, при которых будет достигаться максимальная скорость выполнения операций.

Проблема инверсии в формулах сложения (2) для кривой, заданной в аффинных координатах, решается переходом к проективным координатам. Подставив в уравнение (1) и умножив обе его части на (при ), получим однородное уравнение кривой Эдвардса над полем F₂^m с теми же параметрами :

, (3)

где .

Помимо точек вида при и а F₂^m*, которые соответствуют точкам аффинного представления, уравнению (3) удовлетворяют еще две точки с проективными координатами и . Обе являются сингулярными.

Сложность выполнения групповых операций на кривой Эдвардса, заданной в проективных координатах

Согласно [3] сложение в проективных координатах для кривых Эдвардса реализуется за операций в поле. Аналогичная величина для удвоения составляет и операций. Здесь , , - сложность умножения, возведения в квадрат и умножения на параметры в поле F₂^m. Главным преимуществом кривых

Эдвардса над полями F₂^m, как отмечалось, является полнота и универсальность закона сложения (2) [3, 4]. Производительность же данных кривых в общем случае не является максимальной [3]. Однако приведенные оценки сложности можно улучшить, если принять значения параметров кривой Эдвардса над полем F₂^m равными между собой. Другими словами, при имеем аффинную кривую вида

(4)

с соответствующим представлением в проективных координатах:

,

, и , . (5)

Для этого случая формулы сложения и удвоения будут иметь меньшую сложность: и операций в поле F₂^m [3].

Логично поставить вопрос, при каких условиях для данной канонической кривой можно найти изоморфную кривую Эдвардса вида (4) над полем и как связаны параметры таких кривых.

Условия изоморфизма канонической эллиптической кривой над полем F₂^m и кривой Эдвардса с одним параметром

Каноническая эллиптическая кривая (или несуперсингулярная кривая) задана над полем F₂^m аффинным уравнением

, (6)

где .

При построении кривых Эдвардса вида (1), изоморфных кривым вида (6) в работе [7] выбирали значение параметра так, чтобы выполнялись два условия: и . Далее вычисляли значение другого параметра по формуле [3, 7]. Пусть для кривой (6) существует изоморфная кривая Эдвардса вида (4). Тогда, принимая , получим систему

.(7)

Возьмем функцию следа от обеих частей первого уравнения системы, тогда с учетом получим . Теперь из 2-го и 3-го уравнений следует, что

(8)

Первая формула в системе (7) позволяет вычислить для изоморфной кривой Эдвардса единственное значение параметра d

, . (9)

Условие в (4) и существование квадратного корня у каждого элемента поля F₂^m обеспечивает разрешимость данного равенства.

Равенства (8), (9) задают изоморфизм между кривыми вида (6) и (4). Из всех несуперсингулярных кривых ровно половина кривых со следом отвечает этим условиям. Так как 8 не делит порядок мультипликативной группы поля , для каждого ненулевого параметра кривой (6) существует единственное значение параметра изоморфной кривой Эдвардса и обратно: - единственное значение для каждого d.

Из (8) следует, что все несуперсингулярные кривые и изоморфные им кривые Эдвардса вида (4) имеют порядок, кратный 4. В качестве примера можем взять две кривые действующего украинского стандарта ДСТУ 4145-2002 над полями со степенью расширения , соответственно, которые удовлетворяют условиям (8), (9).

В табл. 1 приведены параметры кривых в форме Эдвардса вида , изоморфных данным кривым в канонической форме над соответствующим полем, а также координаты генераторов криптосистемы.

Взяв за основу американский стандарт FIPS 186-2-2000 и принимая во внимание условия (8), (9), можно заметить, что каждой из четырех кривой Коблица с параметром изоморфна кривая Эдвардса с параметрами , над различными полями простых степеней расширения. В табл. 2 приведены координаты генераторов криптосистемы на кривых Эдвардса вида изоморфных данным кривым Коблица над соответствующим полем.

Таблица 1 Кривые Эдвардса, изоморфные каноническим кривым над полями F₂^m при , для случая украинского стандарта ДСТУ 4145-2002

Таблица 2 Кривые Эдвардса, изоморфные кривым Коблица над полями F₂^m при , , , для случая американского стандарта FIPS 186-2-2000

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

Заключение

Среди множества форм представления эллиптических кривых кривые в форме Эдвардса особенно интересны с практической точки зрения. В настоящей работе рассмотрены кривые Эдвардса над расширенными полями . Закон сложения для данных кривых обладает свойством универсальности и полноты, а его сложность варьируется в зависимости от выбранных параметров кривой.

Исходя из имеющихся оценок сложности групповой операции [3], а также формул изоморфного преобразования [3, 7] между кривыми Эдвардса и каноническими эллиптическими кривыми над полями были получены условия существования кривой Эдвардса с одним параметром, изоморфной кривой в канонической форме. Далее были вычислены искомые значения параметров, соответствующие двум кривым из стандарта ДСТУ 4145-2002 (при и ).

Можно констатировать, что сравнительно немного кривых над полями из рассматриваемых стандартов удовлетворяют условию (8). Поэтому, для нахождения большего числа быстрых кривых Эдвардса необходимо искать новые кривые форме Эдвардса с почти простым значением порядка.

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

1. Edwards, H.M. A normal form for elliptic curves. Bulletin of the American Mathematical Society, Volume 44, Number 3, July 2007, Pages 393-422.

2. Bernstein Daniel J., Lange Tanja. Faster addition and doubling on elliptic curves. IST Programme under Contract IST-2002-507932 ECRYPT, 2007, PP. 1-20.

3. Bernstein Daniel J., Lange Tanja. Farashahi Reza Rezaeian. Binary Edwards curves. Cryptographic hardware and embedded systems-CHES 2008, 10th international workshop, Washington, D.C., USA, August 10--13, 2008, PP. 224-256.

4. Bernstein Daniel J. Batch binary Edwards. Advances in cryptology-Crypto 2009, 29th annual international cryptology conference, Santa Barbara, CA, USA, August 16--20, 2009, PP. 317-336.

5. Бессалов, А.В., Дихтенко, А.A., Третьяков, Д.Б. Сравнительная оценка быстродействия канонических эллиптических кривых и кривых в форме Эдвардса над конечным полем. Сучасний захист інформації, №4, 2011. С.33-36.

6. Бессалов, А.В., Дихтенко, А.А. Криптостойкие кривые Эдвардса над простыми полями // Прикладная радиоэлектроника. - 2013. - Т. 12, №2, - С.107-113.

7. Бессалов, А.В., Дихтенко, А.А. Изоморфные канонической форме эллмптические кривые Эдвардса над расширенными полями характеристики 2 // Радиотехника. - 2013. - Вып. 175. - С. 200 -205.

8. Бессалов, А.В., Телиженко, А.Б. Криптосистемы на эллиптических кривых : учеб. пособие. - К. : ІВЦ «Політехніка», 2004. - 224с.

9. Державний стандарт України. Інформаційні технології. Криптографічний захист інформації. Цифровий підпис, що ґрунтується на еліптичних кривих. Формування та перевірка ДСТУ 4145 - 2002. Видання офіційне. - К. : Держстандарт України, 2003 - 39с. Размещено на Allbest.ru