Новый подход к определению точного числа кривых Эдвардса над простым полем

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

Новый подход к определению точного числа кривых Эдвардса над простым полем

Бессалов А.В., Третьяков Д.Б., Цыганкова О.В.

Аннотация

Рассмотрены новые свойства криптостойких кривых Эдвардса над простыми полями, приемлемых для криптографических приложений. В работе найдены условия сушествования изоморфных кривым Эдвардса кривых в канонической форме y² = x³ + ax + b. Определена зависимость параметра d кривой Эдвардса x² + y² = 1 + d x² y² от параметров а и b эллиптической кривой в канонической форме. Приведено новое доказательство точных формул расчета числа кривых Эдвардса, изоморфных каноническим кривым с ненулевыми параметрами а и b. Оно отличается от доказательства, приведенного в предыдущей работе, лаконичностью.

Ключевые слова: криптосистема, каноническая форма эллиптической кривой, кривая Эдвардса, кривая кручения, параметры кривой, изоморфизм, квадратичный вычет, квадратичный невычет.

Предложенная в работе [1] форма эллиптической кривой, признанная учеными как форма Эдвардса [2], имеет в задачах криптографии ряд несомненных выгод в сравнении с давно известными кривыми в канонической форме. Среди них: быстродействие, универсальность закона сложения и наличие аффинных координат нейтрального элемента (нуля) абелевой группы точек. Некоторые новые свойства кривых Эдвардса над простым полем были нами рассмотрены в работах [3-6]. В работе [6] мы ввели зависимый от традиционных параметров (a, b) канонической формы кривой параметр с как единственный в поле F_p корень кубического уравнения в правой части кривой. Это позволило получить в явном виде условия существования одной точки 2-го порядка и 2-х точек 4-го порядка. Далее в ней получены системы линейных уравнений для неизвестных параметров а и с² с решениями, выраженными через квадратичные вычеты и невычеты. Для нахождения точного числа канонических кривых с ненулевыми параметрами, изоморфных форме Эдвардса, в работе [6] потребовалось сформулировать и доказать 2 леммы о числе решений уравнений, связывающих суммы вычетов и невычетов. Доказательства опираются на схему Гаусса распределения квадратичных вычетов. В итоге впервые найдены формулы расчета точного числа кривых с заданными свойствами и ненулевыми параметрами (a, b) для любых модулей поля р 3mod4 и р 1mod4.

В данной работе, опираясь на свойства кривых в канонической форме, мы нашли функциональную связь между параметром d кривой Эдвардса и параметрами (a, b) изоморфной канонической кривой. Далее приводится новое существенно более лаконичное доказательство утверждения, определяющего формулы расчета точного числа кривых Эдвардса, изоморфных кривым в форме Вейерштрасса с ненулевыми параметрами а и b. В отличие от предыдущей работы [6], это доказательство опирается на кривую, записанную в форме Эдвардса, а не в канонической форме.

1. Определение зависимости между параметрами кривой в форме Эдвардса и канонической форме

Эллиптическая кривая Вейерштрасса в канонической форме над полем характеристики р ? 2, 3 описывается известным уравнением [7]

Е_р : y² = x³ + ax + b, 4a³ + 27b² ? 0, a,b F_p. (1)

Пусть с - единственный в поле F_p корень кубического уравнения x³ + ax + b = 0, тогда вместо (1) можем записать

y² = (x - c)(x² + cx + a + c²) , b = - c³ - ac, c F_p . (2)

Найдем условия, накладываемые на параметры а и с, при которых имеется единственная точка 2-го порядка и 2 точки 4-го порядка. Главной задачей в этом разделе будет нахождение зависимости между параметрами а и с канонической формы эллиптической кривой и параметром d кривой x² + y² = 1 + d x² y² в форме Эдвардса.

Примем u = x - c, тогда уравнение (3) представляется в форме Монтгомери [2,3] эдвардс канонический криптографический изоморфный

y² = u(u² + 3cu + a + 3c²). (3)

Парабола в правой части (4) не имеет корней в поле F_p, если дискриминант квадратного уравнения является квадратичным невычетом, т.е.

9с² - 4(а +3с²) = - (3с² + 4а) ? А². (4)

Это условие гарантирует существование единственной точки 2-го порядка кривой (3), определяемой как D = (0, 0). Условие А² ? 0, входящее в (4), исключает появление кратных корней кубического уравнения и, тем самым, сингулярные кривые [7].

Пусть P = (u₁, y₁) - точка 4-го порядка кривой (3). Ее удвоение 2P = D дает координаты точки 2-го порядка D = (0, 0). При удвоении мы строим касательную к кривой в точке Р, которая проходит через точку (0,0). Таким образом из (3) имеем

Отсюда

2y₁² = 3u₁³ + 6cu₁² + (3c² + a)u₁ . (5)

С другой стороны, в этой же точке согласно (3) имеем

2y₁² = 2u₁³ + 6cu₁² + 2(3c² + a)u₁. (6)

Из системы уравнений (5), (6) получим квадраты для координат точки P 4-го порядка

u₁² = 3c² + a, y₁² = 2u₁³ + 3cu₁² (7)

Из последнего выражения можно теперь получить

(8)

где

(9)

Формулы (7) и (9) позволяют выразить параметр d через параметры a и c канонической формы кривой

, . (10)

Здесь с помощью двоичного выбирается одно из решений квадратного уравнения u₁, которое лежит на кривой (3) и дает ровно 2 точки 4-го порядка. Второе решение не может лежать на кривой: это порождает 4 точки 4-го порядка, что нарушает структуру группы [7].

Из (4) и (7) следует, что необходимыми условиями существования одной точки 2-го и двух точек 4-го порядков являются следующие соотношения, выраженные через символы Лежандра как

(11)

С учетом (7) и (8) и деления на u₁³ уравнение (3) теперь может быть приведено к виду

(12)

Эта форма кривой с помощью сравнительно несложной замены переменных (u.v) > (x,y) [2,3] приводится к кривой в форме Эдвардса

x² + y² = 1 + d x² y², d ? 0, 1. . (13)

Класс изоморфных кривых Эдвардса

(14)

определяется линейной заменой переменных х > е-¹X, у е-¹Y. Такая трансформация расширяет множество всех кривых в (р - 1)/2 раз, но практически бесполезна (более того, добавление нового параметра е усложняет групповые операции).

Как нетрудно видеть из (12), заменой d > d ^-1 получаем кривую кручения с порядком N_E^t = p + 1 + t, симметричным порядку N_E = p + 1 - t исходной кривой относительно середины p + 1. Заметим, что для кривых Эдвардса порядок кривой N_E = 0mod4, поэтому след уравнения Фробениуса t = 0 лишь для значений модуля р = 3 mod4. В этом случае элемент поля (- 1) является квадратичным невычетом, и при значении d = d ^-1 = - 1 пара кривых кручения вырождается в одну суперсингулярную кривую с порядком N_E = p + 1. Это следует также из уравнения (12), которое при d = - 1принимает вид y² = u³ + u [7]. В форме (1) это кривая с коэффициентом b = 0. Она принадлежит классу криптографически слабых суперсингулярных кривых.

В криптографических стандартах не используются уязвимые к MOV-атаке кривые с нулевыми параметрами а или b[7]. Возникает вопрос о числе кривых Эдвардса, изоморфных каноническим кривым с ненулевыми коэффициентами а и b. Эта задача получила точное решение в работе [6] на основе свойств параметров а и с канонических кривых, при этом нам пришлось сформулировать и доказать 2 леммы в теории квадратичных вычетов и утверждение. В следующем разделе мы дадим более лаконичное доказательство полученных в [6] результатов, опираясь на свойства кривой в форме Эдвардса.

2. Новое доказательство формул расчета точного числа кривых Эдвардса, изоморфных кривым в канонической форме с ненулевыми параметрами а и b

Утверждение. Число кривых Эдвардса (14), изоморфных кривым (1) в канонической форме с параметрами a ? 0 и b ? 0 над полем F_p с двумя точками 4-го порядка определяется формулами:

І. При р 3mod4

() М = (р - 1)(р - 7)/4, если ;

() М = (р - 1) )(р - 3)/4 если ;

ІI. При р 1mod4

() М = (р - 1)²/4.

Доказательство.

1. Пусть р 3mod4, тогда (- 1) - квадратичный невычет [7], т.е. и для (11а) невычет заменяем квадратичным вычетом

Аргументы символов Лежандра (11) являются линейными функциями параметров а и с², следовательно, имеем невырожденную систему двух линейных уравнений над полем F_p

3с² +4а = А²,

3с² + а = В² ,

с решениями:

а = 3- ¹(A²- B²), c² = 9- ¹(4B² - A²). (15)

Для кривых с параметрами a ? 0 и b ? 0 квадратичные вычеты A² ? B² и, кроме того, 4B² ? A² (нулевые вычеты c² отбрасываются, так как из с = 0 b = b = - c³ - ac = 0). Из (11) следует, что A² ? 0 и В² ? 0.

Так как параметр d в форме кривой Эдвардса (13) пробегает все квадратичные невычеты поля F_p, их число равно (р - 1)/2. Из этого числа исключим значение d = - 1, которое порождает коэффициенты с = b = 0 (см. формулы (1) и (10)). Остается (р - 3)/2 квадратичных невычетов d.

Пусть Из (15) следует, что при а = 0 А² = В² и с² = 3- ¹А², т.е. существует решение для с и, соответственно, для параметра d, равного согласно (10)

(16)

Нетрудно видеть, что оба решения (16) являются квадратичными невычетами. Например, умножив числитель и знаменатель на знаменатель, получим в знаменателе квадрат, а в числителе разность квадратов 3 - 4 = - 1 , т.е невычет при р 3mod4. Следовательно, из (р - 3)/2 значений невычетов d, исключающих значение b = 0, следует удалить еще 2 значения (16), порождающих коэффициент а = 0. При этом остается (р - 7)/2 допустимых значений невычетов d. Для каждой кривой Эдвардса в форме (13) существует (р - 1)/2 изоморфных кривых (14) с соответствующим числом квадратов е². Общее число кривых Эдвардса с оговоренными свойствами равно М = (р - 1)(р - 7)/4. Утверждение () доказано.

Пусть теперь . В этом случае а ? 0, так как при А² = В² уравнение с² = 3- ¹А² (см.(15)) не имеет решения. Тогда имеем (р - 3)/2 допустимых значений невычетов d, которые вместе с (р - 1)/2 значениями квадратов е² для изоморфных кривых дает М = (р - 1) )(р - 3)/4 кривых. Утверждение () доказано.

2. Пусть р 1mod4, тогда (- 1) - квадратичный вычет, т.е. [7]. Тогда для (11а), принимая А невычетом в системе уравнений:

3с² + 4а = А,

3с² + а = В² ,

находим ее единственное решение

а =3- ¹(A - B²), c² = 9- ¹(4B² - A). (17)

Здесь, мы видим, нулевые решения для а и с² невозможны. Итак, мы имеем (р - 1)/2 допустимых значений невычетов d, которые вместе с (р - 1)/2 значениями квадратов е² для кривых в форме (14) дает М = (р - 1) ²/4 кривых. Утверждение () доказано.

Заметим, что приведенное здесь доказательство формул, определяющих точное число кривых Эдвардса с оговоренными свойствами, существенно проще предыдущего доказательства [6].

Рассчитанные по формулам (), (), () мощности семейств кривых, изоморфных кривым Эдвардса при малых значениях р = 7, 11, 13,…, 47 приведены в таблице 1.

Таблица 1

Пример. Требуется построить кривую Эдвардса на базе изоморфной канонической кривой с двумя точками 4-го порядка над полем F₇. Примем А² = 2, В² = 1, тогда согласно (15) с² = 1 - квадрат в поле, а = 5 и b = c(c² + a) = 1. Получили пару кривых кручения y² = x³ + 5x 1 с порядками N_E = 12 и N_E^t = 4. Первая кривая с параметром с = 1 в форме Монтгомери (3) имеет вид y² = u(u² + 3u +1). Ее точка второго порядка D = (0,0), а координаты точек 4-го порядка первой кривой в соответствии с (7) равны

u₁² = 3c² + a = 1 u₁ = - 1, y₁² = 2u₁³ + 3cu₁² = 1 y₁ = 1 .

Здесь решение u₁ = 1, не лежащее на кривой (3), отбрасывается. Переход к кривой Эдвардса (13) осуществляется вычислением d согласно (10)

.

Кривая x² + y² = (1 + 5x²y²)mod7 имеет порядок 12. Соответствующая кривая кручения с параметром d ^{- 1} = 3 имеет порядок 4. Кривая с параметром d = - 1 отбрасывается. Других кривых в форме (13) при р = 7 не существует. Для каждой из этих двух кривых можно получить по 3 изоморфных кривых (14) с коэффициентами е² = 1, 4, 2. Вообще нал полем F₇ существует, как следует из таблицы 1, 6 кривых Эдвардса, изоморфных каноническим кривым с ненулевыми параметрами а и b и двумя точками 4-го порядка. Здесь каждая пара кривых кручения содержит по 3 изоморфных пар.

Формулы (15), (17) конструктивны, так как позволяют рассчитывать параметры а и с кривой (и, соответственно, b) при заданных значениях пар квадратичных вычетов (A², B²) [6]. После этого легко перейти к изоморфной кривой Эдвардса.

Литература

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. Бессалов А.В. Число изоморфизмов и пар кручения кривых Эдвардса над простым полем. Радиотехника, вып. 167, 2011. С. 203-208.

4. Бессалов А.В., Гурьянов А.И., Дихтенко А.А. Кривые Эдвардса почти простого порядка над расширениями малых простых полей. Прикладная радиоэлектроника, том 11, №2, 2012. С. 225-227.

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

6. Бессалов А.В., Дихтенко А.А., Цыганкова О.В. Мощность семейства эллиптических кривых, изоморфных кривым Эдвардса над простым полем. Захист інформації - Том 16, №1, січень-березень 2014, с.23-28.

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

Размещено на Allbest.ru