Понятие и использованиепреобразований в эллиптических кривых

     Сед отображения Фробениуса и эндоморфизм  Фробениуса связаны

уравнением:

т. е. для произвольной точки кривой выполнено соотношение

,

В котором  сложение и вычитание — суть групповые  операции на ЭК. Есть два частных случая криптографически непригодных эллиптических кривых:

  Кривая называется аномальной, если ее след Фробениуса

равен 1, т.е. . Эта кривая особенно неудобна, когда q — простое число.

 Кривая  называется суперсингулярной, если характеристика

р поля делит след отображения Фробениуса . Таких кривых также стараются избегать в криптографии. При q = р ССК насчитывает р + 1 точку, поскольку t = 0 в этом случае. Если же то у суперсингулярных кривых может принимать значения

при нечетном

при четном  если и если

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

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

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

      Как было отмечено ранее, случаи требуют дополнительных

усилий. Реализация криптографических систем, основанных на ЭК, базируется на поле , чья характеристика равна 2, или на поле с большим простым числом р. Поэтому в конце текущей главы мы сконцентрируем внимание на полях характеристики 2 и , опустив случай . Большинство общих рассуждений с некоторой модификацией переносится на случай характеристики три, что хорошо освещено в специальной литературе. 

     1.3.1 Кривые над полем характеристики  р > 3 

Пусть основное поле с , где р > 3 — простое число И Как уже отмечалось, уравнение кривой над таким полем можно представить в виде короткой формы Вейерштрасса

     

      

Ее дискриминант равен  а ί-инвариант Формулы из леммы 2.2, описывающие ГК, также упрощаются: и если то координаты вычисляются так:

  

где при 

а при 

 

 

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

Здесь мы ограничимся  конечными полями с при . В этом случае ί-инвариант кривой Е вычисляется по формуле   Условие т.е. в характеристике 2 равносильно суперсингулярности кривой Е. Мы уже отмечали, что суперсингулярные кривые — очень специфический случай, который не используется в криптографии. Поэтому будем предполагать, что

В этих предположениях представитель любого класса изоморфизма эллиптических кривых над записывается уравнением

     

    

где и Здесь — фиксированный элемент поля , удовлетворяющий соотношению: , где — абсолютный след, вычисляющийся по формуле

Когда характеристика поля равна 2, формула для противоположного элемента ЭК из леммы 2.2 преобразуется  к виду и, если , то

где при 

а если то

 

     1.4 Большая характеристика 

Формулы сложения точек ЭК, заданной уравнением

над полем  большой характеристики выглядят теперь как

где тройка координат    вычисляется последовательно по правилу:

Обратите  внимание, что здесь нет ни одной  операции деления, кроме деления на 2, которая легко заменяется умножением на заранее вычисленное число

      Удвоение  точек упрощается с помощью формул

      

 

     1.4.1  Четная характеристика 

Уравнение ЭК над полем четной характеристики

записывается  в виде

Сложение точек 

В этом случае осуществляется по рецепту:

И, наконец, координаты удвоенной точки определяются по правилу:

Итак, в обоих интересных случаях — при большой и четной характеристиках поля — мы исключили дорогостоящую операцию деления. 

     1.5 Сжатие точек 

Во многих криптографических протоколах возникает  необходимость хранить в памяти или передавать по сети отдельные точки ЭК.

В аффинных координатах это можно сделать с помощью двух элементов поля: координат х и у. Однако экономнее применять так называемую технику сжатия точек.

     Метод сжатия точек работает благодаря  тому, что уравнение кривой в аффинных координатах при фиксированном значении х превращается в квадратное уравнение относительно координаты у. Поэтому каждому возможному значению координаты х точки кривой соответствует не более двух значений координаты у. Значит, вместо двух координат для идентификации точки кривой можно хранить в памяти компьютера только координату х и еще некий двоичный параметре 6, сообщающий о том, какое именно значение координаты у нужно брать. Остается только решить, как вычислять параметр b и как по нему и данному х восстановить у-координату нужной точки. 

1.5.1. Случай  большой характеристики поля 

Заметим, что если р > 2, то квадратные корни из элемента представляются натуральными числами разной четности из промежутка

1, . . . , р — 1, поскольку

Таким образом, в качестве параметра  b можно выбрать четность у-координаты соответствующей точки. Покажем теперь, как восстановить полную информацию о координатах точки по паре (x, b). Сначала вычисляется

а затем  переменной у присваивают значение , если четность совпадает

с четностью  b, и р — , когда четности разные. Если же оказалось, что = 0, то, не обращая внимания на параметр b, можно положить у = 0.

      В качестве примера рассмотрим кривую

над полем . Для представления каждой из ее точек (4,1) и (4,6) в

двоичной  системе счисления нам потребуется шесть разрядов:

(0b 100, 0b 001)   и  (0b100, 0b 110),

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

(0b 100, 0b1)  и  (0b 100, 0b0).

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

На ней  есть точка с координатами

для записи которой нам потребовалось 102 разряда. При сжатии информации эту точку можно представить в виде

(1125 899 906 842 675,1),

где использовано только 52 разряда. 

     1.5.2. Четная характеристика 

В случае четной характеристики необходимо проявить больше изобретательности. Предположим, что нам дана точка Р(x, у) на эллиптической

кривой

     

     

Если  у = 0, то можно положить b = 0. в противном случае вычисляют z = у/х и присваивают переменной b самый младший двоичный разряд числа z.

Для восстановления у по данной паре (x, b) в случае вычисляют

и обозначают через  одно из решений уравнения

Если  наименьший двоичный разряд числа  совпадает с 6, то у = x/ .

В противоположной ситуации у = х( +1). Для объяснения того, почему этот метод правильно восстанавливает y-координату точки, напомним, что координаты (x, у) точки Р — решение уравнения (2.5). Поэтому пары (х, у/х) и (х, 1+у/х) удовлетворяют соотношению