Во многих криптографических протоколах возникает необходимость хранить в памяти или передавать по сети отдельные точки эллиптической кривой. В аффинных координатах это можно сделать при помощи двух элементов поля: координат x и y. Однако экономнее применять так называемую технику сжатия точек.
Метод сжатия точек работает благодаря тому, что уравнение кривой в аффинных координатах при фиксированном значении x превращается в квадратно уравнение относительно координаты y. Значит, вместо двух координат для идентификации точки кривой можно хранить в памяти компьютера только координату x и еще некий двоичный параметр b, сообщающий о том, какое именно значение координаты y нужно брать.
Кривые над полем характеристики p > 3.
Пусть основное поле K = Fq с q = pn, где p > 3 – простое число и .
Уравнение кривой над таким полем можно представить в виде короткой формы Вейерштрасса
E: Y2 = X3 + aX + b.
Ее дискриминант равен Δ = – 16(4a3 + 27b2), а j-инвариант – j(E) = – 1728(4a)3/ Δ.
Формулы группового закона: – P1 = (x1, y1) и, если P3(x3, y3) = P1 + P2 ¹ O, то координаты x3, y3 вычисляются так:
где при x1 ¹ x2
а при x1 = x2, y1 ¹ 0
В проективных координатах формулы сложения точек эллиптической кривой, заданной уравнением
E: Y2 = X3 + aXZ2 + bZ6,
над полем характеристики p > 3 выглядят как
где тройка координат вычисляется последовательно по правилу:
здесь нет ни одной операции деления, кроме деления на 2, которое легко заменяется умножением на заранее вычисленное число 2–1(mod p).
Удвоение точек упрощается с помощью формул
Сжатие точек эллиптической кривой над полем характеристики p > 3.
Если p > 2, то квадратные корни ± β из элемента α Î Fp представляются натуральными числами разной четности из промежутка 1, …, p – 1, поскольку
– β=p – β (mod p).
Таким образом в качестве параметра b можно выбрать четность y координаты соответствующей точки. Полная информация о координатах точки по паре (x, b) осуществляется следующим образом. Сначала вычисляется
а затем переменной y присваивают значение β, если четность β совпадает с четностью b, и p – β, когда четности разные. Если же оказывается, что β = 0, то, не обращая внимания на параметр b, можно положить y = 0.
Не путать параметр четности b с коэффициентом кривой b.