Эллиптические кривые в криптографии

Поля

 

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

 

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

 

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

 

Определение. Характеристикой поля называется наименьшее число m , т.ч. сумма m единиц поля равна 0. Если сумма единиц поля не равна 0 ни при каком m , то характеристика поля равна 0.

 

Поля и – поля характеристики 0. Поле Z_p имеет характеристику p.

 

Определение. Пусть задано поле ( E, +, ´ ) . Подмножество F Í E c операциями поля E называется подполем поля E , оно является полем относительно этих операций. Поле E в этом случае называется расширением поля F .

 

Пример.Поле действительных чисел R является расширением поля рациональных чисел Q.

 

Конечные поля – поля Галуа[2]

 

Поле, содержащее конечное число элементов, называется конечным, или полем Галуа. Порядок конечного поля – это число его элементов.

 

Утверждение (о существовании и единственности конечных полей). Если F – конечное поле, то оно содержит q = pⁿ элементов, где p – простое число, n ³ 1.

 

Поля вычетов Z_p являются простейшими примерами конечных полей.

 

Обозначение конечных полей – GF ( q ).

 

Поле GF( p ), где p – простое число, называется простым, поле GF( pⁿ ) называется расширенным.

 

Утверждение. Поле GF ( pⁿ ) имеет характеристику p .

 

Утверждение. Если GF ( pⁿ ) – поле, то GF ( p^d ) – подполе поля GF ( pⁿ ) для любого d – делителя n.

 

Ненулевые элементы поля Галуа GF(q) образуют мультипликативную группу, которая обозначается через GF^*( q ).

 

Утверждение. Мультипликативная группа GF^*( q ) является циклической группой порядка q – 1.

 

Образующий элемент мультипликативной группы поля Галуа называют примитивным элементом поля.

В поле примитивным элементом является класс вычетов . Его степени

, , , , ,

исчерпывают все ненулевые элементы поля.

 

Контрольные вопросы

 

1. Дайте определение кольца.

2. Какое кольцо называется коммутативным?

3. Дайте определение поля.

4. Что такое мультипликативная группа поля?

5. Сформулируйте основное свойство мультипликативной группы поля.

6. Что такое поле Галуа?

7. Что такое примитивный элемент поля?

 

Эллиптическая кривая – это математический объект, который может быть определен над любым полем, в частности над полем вещественных чисел или над конечным полем Галуа.

 

В общем случае эллиптическая кривая над полем К имеет вид

E: y² + axy + by = x³ +cx² + dx + e ,

где a, b, c, d, e Î K .

 

На рисунке 1 представлен пример эллиптической кривой, определенной уравнением

y² = x³ + x + 1 ,

над полем вещественных чисел R.

 

 

Рисунок 1. Пример эллиптической кривой y² = x³ + x + 1 над R.

 

В криптографии применяются эллиптические кривые, определенные над конечными полями Галуа GF ( q ). В этом случае они представляют собой множество точек E(GF(q)), координаты которых удовлетворяют уравнению кривой. Такая форма называется редуцированной.

 

Пример. Дана эллиптическая кривая y² = x³ + x + 1 mod 5 над полем GF(5). Этому уравнению удовлетворяют 8 конечных точек с координатами из GF(5). На рисунке 2 представлен пример этой кривой.

 

Рассмотрим эллиптические кривые над простым полем GF (p) следующего вида:

y² = x³ + ax + b mod p, (1)

где р – простое число-модуль преобразований; параметры кривой a, b Î GF (p) - неотрицательны и удовлетворяют условию гладкости кривой , переменные x, y Î GF (p) .

 

Кроме точек ( x, y ), удовлетворяющих уравнению (1), в множество точек эллиптической кривой также включается бесконечно удаленная точка O .

 

Рисунок 2. Пример эллиптической кривой кривая y² = x³ + x + 1 mod 5 над полем GF(5).

 

 

Таким образом, при p = 2 точками эллиптической кривой y² = x³ + x + 1 mod 2 являются четыре точки – (0,1), (1,0), (1,1) и O .

 

Обозначим через E_p(a,b) множество точек эллиптической кривой вида y² = x³ + ax + b mod p .

 

На множестве E_p(a,b) введем операцию сложения + по правилу:

пусть и – точки эллиптической кривой, тогда координаты суммы точек определяются формулами

 

Если P₁ ¹ P₂ ,

 

Если P₁ = P₂ ,

 

Считаем, что P + O = O + P .

 

Утверждение. Множество точек эллиптической кривой E_p(a,b) с операцией сложения + образует аддитивную абелеву группу с нейтральным (нулевым) элементом O, т.е. выполняются следующие условия группы:

 

1) если P и Q Î E_p(a,b) , то P + Q Î E_p(a,b)

2) для любых трех точек кривой P, Q, S Î E_p(a,b) P + (Q + S) = (P + Q) + S

3) для любой точки P = (x, y) Î E_p(a,b) существует обратная точка – P , т.ч. P + (– P) = O ; точка – P имеет координаты (x, – y) .

 

Пример. Найдем точки эллиптической кривой y² = x³ + x + 1 mod 5 . Возможные значения переменной x – 0, 1, 2, 3, 4 . Задавая значения x , найдем y :

x = 0 y² = 1 Þ y = 1, y = – 1 или y = 4

x = 1 y² = 3 Þ решений нет

x = 2 y² = 11 = 1 Þ y = 1, y = 4

x = 3 y² = 31 = 1 Þ y = 1, y = 4

x = 4 y² = 69 = 4 Þ y = 1, y = 4

Таким образом, получим точки (0,1), (0,4), (2,1), (2,4), (3, 1), (3,4), (4,1), (4,4) и добавляем точку O. Эллиптическая кривая E₅(1,1) содержит 9 точек.

 

Определение. Порядком группы точек эллиптической кривой E_p(a,b) называется число элементов этой группы. Обозначение – # E_p(a,b) .

 

Группа точек эллиптической кривой E₅(1,1) имеет порядок, равный 9.