Современная прикладная криптография (стр. 33 )

примет вид

Y Z = X + a X Z + b Z.

При ненулевой Z, мы видим, что y = x + a x +b выполняется тогда и только тогда, когда

(Y/Z) = (X/Z) + a (X/Z) + b.

Бесконечные точки нашей кривой - это классы точек (X : Y : 0), для которых выполнено соотношение

Y 0 = X + a X (0) + b 0 ,

то есть X=0. Существует только один такой класс эквивалентности (0 : 1 : 0). Это и есть искомая бесконечно удаленная точка О.

Требования, которые мы предъявили к точке О, корректно определяют ее как нулевую точку относительно операции сложения точек на эллиптической кривой. Действительно, в силу нашего соглашения, вертикальная прямая, проходящая через точку Р, проходит через Р и О. Поэтому точка Р` пересечения этой прямой с эллиптической кривой удовлетворяет соотношению Р + Р` = О, то есть является обратной по сложению к точке Р. В то же время, Р` - это точка, симметричная к Р относительно оси Ох. Значит, любая точка Р имеет обратную точку – Р = Р`.

Для вычисления точки 2Р = Р+Р нужно провести не секущую, а касательную в этой точке. Точки вида n P теперь находятся по индукции: 3Р= 2Р+Р, … .

Для того, чтобы окончательно убедиться, что точки эллиптической кривой относительно описанной операции сложения образуют абелеву группу, осталось проверить ассоциативность для этой операции, то есть выполнение равенства (P+Q)+S=P+(Q+S) для всех точек кривой Е(К), включая бесконечно удаленную точку О.

Геометрически доказать это трудно [ПС97], но можно показать с помощью приводимых ниже формул вычисления координат точки, являющейся суммой двух произвольных точек. При этом надо будет рассмотреть несколько случаев, в зависимости от того, P=Q или нет, и от того, S=(P+Q) или нет, что делает доказательство достаточно трудоемким (http://math. rice. edu/~friedl/papers/AAELLIPTIC. PDF ).

Формулы для вычисления координат суммы точек эллиптической кривой.

Пусть Р = (х, у), Q= (х, у), P+Q = (x, y). Уравнение прямой на аффинной плоскости, соединяющей точки Р и Q, имеет вид у=к х+d, где

k=(у – у)/(х – х), d = y – k x = (x y – x y)/(x – x).

Подставив у=к х+d в уравнение эллиптической кривой y = x + a x +b, получим уравнение третьей степени (к х+d ) = x+ a x +b, то есть

x- k x + (a – 2 kd) x + b – d= 0.

Мы знаем два его корня х1 и х2, так как точки (х, k x+ d) и (x, k x+d) лежат на кривой.

Отсюда по теореме Виета

x= k - x - x,

y= - k x – d (знак минус взят в силу определения операции сложения точек).

Подставляя в эти формулы значения k и d, получим

x = ((y-y) / (x-x)) – x – x,

y = - y1 + ((y – y)/(x – x)) (x – x).

При х = х эти формулы не имеют смысла. Это соответствует случаю, когда P и Q лежат на вертикальной прямой и их сумма равна точке в бесконечности.

Случай, когда Р = Q разбирается аналогично. В этом случае уравнение секущей

у = к х+d нужно заменить уравнением касательной и действовать по прежней схеме, здесь k есть значение производной в точке Р и равно k = ((3 x + a)/2 y) , и поэтому мы получаем координаты удвоенной точки Р вида

x = ((3x + a)/2 y) – 2x,

y = - y + ((3x + a)/2y)(x – x).

Ясно, что эти формулы верны для любого поля, характеристика которого отлична от 2 и 3. Для указанных случаев будут справедливы приводимые ниже формулы (см., например [БССШ03]).

Если а=а=0 в длинной форме Вейерштрасса, а а не обязательно нуль (случай, включающий char K = 3), то

x = ((y-y)/(x-x)) – a – x – x,