Эллиптически кривые над конечными полями

⇐ ПредыдущаяСтр 10 из 10

для современной криптографии актуальна проблема повышения стойкости и уменьшения размера блоков данных путем модификации уже существующих криптосистем.

Самый очевидный путь решения вышеупомянутой проблемы – представление блоков информации в криптографических алгоритмах не только в виде чисел (или элементов конечных полей), но и в виде иных алгебраических объектов большей сложности. Одним из весьма подходящих типов таких объектов являются точки эллиптических кривых. Первоначально эллиптической кривой называлась гладкая кривая на декартовой плоскости, описываемая следующим уравнением:

у² + а₁ху + а₃у = х³ + а₂х² + а₄х + а₆ (1)

Если все коэффициенты и неизвестные – действительные числа, то путем замены переменных уравнение (1) может быть преобразовано к следующему, более простому виду (рис. 3.5):

у² = х³ + ах + b. (2)

Рис. 3.5. Эллиптические кривые

Уравнение (1) может рассматриваться над произвольными полями, и в частности, над конечными полями, представляющими для криптографии особый интерес. В последнем случае решением уравнения (1) является множество отдельных точек, а не линия, но и в этом случае по традиции говорят об эллиптических кривых.

Эллиптические кривые используются в криптографии с середины 80-х г. прошлого века в качестве инструмента решения некоторых теоретико-числовых задач и в качестве основы для построения криптосистем. Любая кривая над полем действительных чисел, задаваемая уравнением общего вида (1), обладает следующими свойствами, в формулировке которых условимся точку касания считать за два пересечения:

1. Любая вертикальная (параллельная оси Оу) прямая, не пересекает кривую ни разу или пересекает ее дважды.

2. Любая другая прямая пересекает кривую один или три раза.

Добавим к множеству точек эллиптической кривой фиктивный элемент «О» (называемый обычно «бесконечной точкой»), который будет играть роль нулевого элемента конструируемой аддитивной группы: для любой точки Р эллиптической кривой положим Р + О = О + Р = Р. Операции отрицания и сложения определяем таким образом, чтобы для каждой прямой, пересекающей эллиптическую кривую дважды или трижды, «сумма» всех точек пересечения с учетом их кратности при касании была «равна нулю»:

P + P' = O – для вертикальных прямых,

P + Q + R = O – для невертикальных прямых (рис. 3.6).

Рис. 3.6. Прямая пересекает эллиптическую кривую

Первое соотношение определяет правило отрицания – аддитивным обратным элементом для любой точки P эллиптической кривой является другая точка пересечения кривой и вертикальной прямой: P' = –P. Второе соотношение определяет правило сложения точек: суммой двух точек кривой является отрицание третьей точки пересечения кривой и прямой, проведенной через первые две: Р + Q = –R = R' (см. рис. 3.6). Для определенных таким образом аддитивных операций выполняются все требования к операциям в абелевых группах:

1. Операция сложения точек очевидным образом коммутативна: для любых точек Р, Q эллиптической кривой справедливо Р + Q = Q + Р.

2. В проективной геометрии доказывается ассоциативность операции сложения точек: для любых трех точек Р, Q, R эллиптической кривой справедливо (Р + Q) + R = P + (Q + R).

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

Определенные выше операции над точками кривых могут быть распространены на случай произвольного поля. Необходимые формулы могут быть получены, если воспользоваться алгебраическими выражениями для геометрических понятий – «прямая», «вертикальная прямая», «касательная».

Эллиптические кривые определяются над двумя типами конечных полей: поля нечётной характеристики ( , где p > 3 – большое простое число) и поля характеристики 2 ( ). Описание эллиптических кривых в полях нечётной характеристики существенно проще, поэтому остановимся на них подробнее. Рассмотрим уравнение двух переменных :

y² = x³ + Ax + B(mod p),

где – константы, удовлетворяющие

Множеством точек эллиптической кривой называется множество пар (x, y), удовлетворяющих вышеуказанному уравнению, объединённое с нулевым элементом :

Теорема Хассе об эллиптических кривых утверждает, что количество точек на эллиптической кривой близко к размеру конечного поля:

Пример. Пусть p = 5, а уравнение эллиптической кривой:
y² = x³ + 3x + 2(mod 5). Тогда (1, 1) и (1, 4) – точки эллиптической кривой, так как

Следует отметить, что в у каждого элемента, кроме нуля, есть либо два квадратных корня, либо нет ни одного, поэтому точки эллиптической кривой всегда получаются парами (x, y₁) и (x, y₂), так что

Следует указать, что не для всякого конечного поля уравнение кривой может быть приведено к виду (2). Так, для конечного поля характеристики 3 невозможно избавиться от члена а₂х², если а₂ отлично от нуля. Для полей характеристики 2 уравнение (1) может быть приведено к одному из следующих видов:

у² + ау = х³ + bх + с (суперсингулярная кривая); (3)

у² + аху = х³ + bх² + с (несуперсингулярная кривая). (4)

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

Для криптографии особую важность представляет нахождение кратного точки эллиптической кривой: Q = kР, где k – большое натуральное число. Эта операция аналогична возведению элемента конечного поля в большую натуральную степень. На сегодняшний день неизвестны эффективные алгоритмы для решения задачи дискретного логарифмирования в полях точек эллиптических кривых.

Вопросы и задания для самостоятельной работы

1. Как определить наибольший общий делитель?

2. Как составить таблицу простых чисел, пользуясь способом «Решето Эратосфена».

3. Выпишите каноническое разложение числа на простые сомножители.

4. Какое число называется Евклидовым числом?

5. Назовите три способа отыскания функции Эйлера.

6. Какова связь непрерывных дробей с алгоритмом Евклида?

7. Как сравнить целые числа по модулю?

8. Какие свойства сравнений подобны свойствам равенств, и какие свойства особенные?

9. Опишите алгоритм решения сравнений первой степени по алгоритму Евклида.

10. Как вычислить обратный элемент по заданному модулю?

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

12. Как найти мультипликативный обратный элемент по модулю m?

⇐ Предыдущая 1 2 3 4 5 6 7 8 910