Поиск кривых Эдвардса, приемлемых для криптографии. Сложность выполнения групповых операций на кривой Эдвардса, заданной в проективных координатах. Параметр, соответствующий стандарту ДСТУ 4145–2002. Изоморфизм канонической эллиптической кривой над полем.
Аннотация к работе
Форма Эдвардса эллиптической кривой над полем характеристики задает симметричную относительно координат кривую с порядком, кратным 4 [1, 2, 5, 6]. Для двух типов кривых Эдвардса нуль абелевой группы представляется парой аффинных координат, а соответствующий групповой закон справедлив для произвольной пары точек кривой (включая совпадающие, обратные точки, и нуль группы) [2, 3]. Анализ оценок сложности операций сложения и удвоения точек кривой Эдвардса над полем F2m приводит к выводу, что наибольшая производительность присуща кривым с одним параметром d = d1 = d2. Между несуперсингулярными кривыми и кривыми Эдвардса в общем виде над полями F2m существует изоморфизм [3]. Кривая Эдвардса над полем F2m описывается уравнением в аффинных координатах [3]Закон сложения для данных кривых обладает свойством универсальности и полноты, а его сложность варьируется в зависимости от выбранных параметров кривой. Исходя из имеющихся оценок сложности групповой операции [3], а также формул изоморфного преобразования [3, 7] между кривыми Эдвардса и каноническими эллиптическими кривыми над полями были получены условия существования кривой Эдвардса с одним параметром, изоморфной кривой в канонической форме.
Введение
Форма Эдвардса эллиптической кривой над полем характеристики задает симметричную относительно координат кривую с порядком, кратным 4 [1, 2, 5, 6]. Для всех кривых этого класса групповая операция выполняется рекордно малым числом арифметических операций в поле [2, 5]. Наряду с простыми полями большой характеристики в криптографии широко применяются расширенные поля F2m характеристики 2. Несмотря на различия в форме записи, кривым Эдвардса над полями F2m и (при ) присущи сходные свойства [3, 4, 7]. Для двух типов кривых Эдвардса нуль абелевой группы представляется парой аффинных координат, а соответствующий групповой закон справедлив для произвольной пары точек кривой (включая совпадающие, обратные точки, и нуль группы) [2, 3]. Минимальный кофактор в порядке кривой Эдвардса над полем F2m равен 2. Задачей работы является поиск кривых Эдвардса, приемлемых для криптографии. эллиптический эдвардс криптография проективный
В настоящей работе рассматриваются кривые в форме Эдвардса над расширенными полями F2m. Анализ оценок сложности операций сложения и удвоения точек кривой Эдвардса над полем F2m приводит к выводу, что наибольшая производительность присуща кривым с одним параметром d = d1 = d2. Между несуперсингулярными кривыми и кривыми Эдвардса в общем виде над полями F2m существует изоморфизм [3]. В разд. 3 находим условия, при которых для данной эллиптической кривой найдется изоморфная кривая Эдвардса с одним параметром d. Для известных канонических кривых из национальных стандартов (ДСТУ 4145 - 2002 [8, 9] и FIPS 186-2 - 2000 [8]), удовлетворяющих полученным условиям, были найдены изоморфные кривые Эдвардса с одним параметром d . В случае ДСТУ 4145 - 2002 таких кривых две, в американском стандарте FIPS 186-2 - 2000 данные условия выполняются для четырех кривых Коблица.
Кривые Эдвардса над расширенными полями характеристики 2
Кривая Эдвардса над полем F2m описывается уравнением в аффинных координатах [3]
(1) где - пара элементов поля, удовлетворяющих условиям и . Закон сложения точек кривой (1) универсален и имеет вид
, .(2)
Полнота закона (2) - наиболее весомый аргумент для включения кривых Эдвардса над полями F2m в проекты будущих стандартов шифрования. Нуль группы , как видно из (2), не изменяет координат другой точки в сумме. Прочие свойства кривых Эдвардса над полями четных и нечетных характеристик подробно рассмотрены в работах [3, 4, 7] и [1, 2, 5, 6] соответственно. Очевидно, что производительность криптосистемы в значительной мере зависит от ее параметров, и в случае кривых над полями F2m, актуален вопрос нахождения таких коэффициентов кривой Эдвардса, при которых будет достигаться максимальная скорость выполнения операций.
Проблема инверсии в формулах сложения (2) для кривой, заданной в аффинных координатах, решается переходом к проективным координатам. Подставив в уравнение (1) и умножив обе его части на (при ), получим однородное уравнение кривой Эдвардса над полем F2m с теми же параметрами : , (3) где .
Помимо точек вида при и AI F2m*, которые соответствуют точкам аффинного представления, уравнению (3) удовлетворяют еще две точки с проективными координатами и . Обе являются сингулярными.
Сложность выполнения групповых операций на кривой Эдвардса, заданной в проективных координатах
Согласно [3] сложение в проективных координатах для кривых Эдвардса реализуется за операций в поле. Аналогичная величина для удвоения составляет и операций. Здесь , , - сложность умножения, возведения в квадрат и умножения на параметры в поле F2m. Главным преимуществом кривых
Эдвардса над полями F2m, как отмечалось, является полнота и универсальность закона сложения (2) [3, 4]. Производительность же данных кривых в общем случае не является максимальной [3]. Однако приведенные оценки сложности можно улучшить, если принять значения параметров кривой Эдвардса над полем F2m равными между собой. Другими словами, при имеем аффинную кривую вида
(4)
с соответствующим представлением в проективных координатах: , , и , . (5)
Для этого случая формулы сложения и удвоения будут иметь меньшую сложность: и операций в поле F2m [3].
Логично поставить вопрос, при каких условиях для данной канонической кривой можно найти изоморфную кривую Эдвардса вида (4) над полем и как связаны параметры таких кривых.
Условия изоморфизма канонической эллиптической кривой над полем F2m и кривой Эдвардса с одним параметром
Каноническая эллиптическая кривая (или несуперсингулярная кривая) задана над полем F2m аффинным уравнением
, (6) где .
При построении кривых Эдвардса вида (1), изоморфных кривым вида (6) в работе [7] выбирали значение параметра так, чтобы выполнялись два условия: и . Далее вычисляли значение другого параметра по формуле [3, 7]. Пусть для кривой (6) существует изоморфная кривая Эдвардса вида (4). Тогда, принимая , получим систему
.(7)
Возьмем функцию следа от обеих частей первого уравнения системы, тогда с учетом получим . Теперь из 2-го и 3-го уравнений следует, что (8)
Первая формула в системе (7) позволяет вычислить для изоморфной кривой Эдвардса единственное значение параметра d
, ? . (9)
Условие в (4) и существование квадратного корня у каждого элемента поля F2m обеспечивает разрешимость данного равенства.
Равенства (8), (9) задают изоморфизм между кривыми вида (6) и (4). Из всех несуперсингулярных кривых ровно половина кривых со следом отвечает этим условиям. Так как 8 не делит порядок мультипликативной группы поля , для каждого ненулевого параметра кривой (6) существует единственное значение параметра изоморфной кривой Эдвардса и обратно: - единственное значение для каждого d.
Из (8) следует, что все несуперсингулярные кривые и изоморфные им кривые Эдвардса вида (4) имеют порядок, кратный 4. В качестве примера можем взять две кривые действующего украинского стандарта ДСТУ 4145-2002 над полями со степенью расширения , соответственно, которые удовлетворяют условиям (8), (9).
В табл. 1 приведены параметры кривых в форме Эдвардса вида , изоморфных данным кривым в канонической форме над соответствующим полем, а также координаты генераторов криптосистемы.
Взяв за основу американский стандарт FIPS 186-2-2000 и принимая во внимание условия (8), (9), можно заметить, что каждой из четырех кривой Коблица с параметром изоморфна кривая Эдвардса с параметрами , над различными полями простых степеней расширения. В табл. 2 приведены координаты генераторов криптосистемы на кривых Эдвардса вида изоморфных данным кривым Коблица над соответствующим полем.
Таблица 1 Кривые Эдвардса, изоморфные каноническим кривым над полями F2m при , для случая украинского стандарта ДСТУ 4145-2002 m = 173 P(x) = x173 x10 x2 x 1, n=800000000000000000000189B4E67606E3825BB2831
Закон сложения для кривых Коблица не обладает свойством полноты и универсальности (в отличие от случая кривых Эдвардса), и это можно трактовать как их недостаток. Однако сложность групповой операции в случае кривых Коблица все же будет меньшей, чем в случае изоморфных кривых Эдвардса, поэтому нельзя сделать однозначный вывод о превосходстве одной формы рассматриваемых кривых над другой.
Вывод
Среди множества форм представления эллиптических кривых кривые в форме Эдвардса особенно интересны с практической точки зрения. В настоящей работе рассмотрены кривые Эдвардса над расширенными полями . Закон сложения для данных кривых обладает свойством универсальности и полноты, а его сложность варьируется в зависимости от выбранных параметров кривой.
Исходя из имеющихся оценок сложности групповой операции [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. Бессалов, А.В., Дихтенко, А.А., Третьяков, Д.Б. Сравнительная оценка быстродействия канонических эллиптических кривых и кривых в форме Эдвардса над конечным полем. Сучасний захист інформації, №4, 2011. С.33-36.
7. Бессалов, А.В., Дихтенко, А.А. Изоморфные канонической форме эллмптические кривые Эдвардса над расширенными полями характеристики 2 // Радиотехника. - 2013. - Вып. 175. - С. 200 -205.
8. Бессалов, А.В., Телиженко, А.Б. Криптосистемы на эллиптических кривых : учеб. пособие. - К. : ІВЦ «Політехніка», 2004. - 224с.
9. Державний стандарт України. Інформаційні технології. Криптографічний захист інформації. Цифровий підпис, що ґрунтується на еліптичних кривих. Формування та перевірка ДСТУ 4145 - 2002. Видання офіційне. - К. : Держстандарт України, 2003 - 39с. Размещено на .ru