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

Доказательство.

Сначала предположим, что a не равно 0. Это равносильно тому, что j=j не равен 0, поэтому и a не равно 0. Выберем d так, a = a (d), что возможно в силу замкнутости.

Тогда в силу равенства j=j получаем

4 a/(4a + 27 b) = 4 a/(4a+27b) = 4 d a/(4 d a+ 27 b) = 4 a/(4a+27d b),

что означает, что b = (b d).

Поэтому b = (b d). Если b = + b d, то все доказано. Если b = - bd, то заменим d на i d ( где i = - 1). Это дает a= a (d) и b = b d.

Если а равно 0, то и а = 0. Так как дискриминант не равен 0, то b и b не равны 0. Выбираем d таким, что b= b (d). Ч. т.д.

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

Наконец, заметим, что число j является j - инвариантом для кривой вида

Y = x + (3j/(1728 –j)) x + (2j/1728 – j),

если j не равен 0 или 1728. (Существуют 2 специальных значения j=0 и j=1728. В стандарте цифровой подписи ГОСТ 34.10-2001 кривые с такими инвариантами исключены) То есть, как коэффициенты эллиптической кривой определяют j-инвариант, так и j-инвариант определяет коэффициенты эллиптической кривой.

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

При построении криптосистем широко используются эллиптические кривые над конечными полями. В основном рассматривается простое поле F и поле F, но исследования ведутся и для произвольного конечного поля F, где q=p (p-простое число) [ГОСТ 34.10 – 2001(F), FIPS 186-ⁿ(Fи F)].

В силу конечности поля F число пар (x, y), удовлетворяющих уравнению

y = x + a x +b над этим полем тоже конечно, и группа точек эллиптической кривой является конечной абелевой группой.

Легко видеть, что порядок этой абелевой группы не может превышать число 2q+1. Если задать кривую в форме Вейерштрасса y = x + a x +b, то для каждого x из F число решений сравнения y = a (mod q) не может превышать двух, и 1 добавляет точка в бесконечности.

Кстати, в криптографических протоколах, когда надо хранить значения точек эллиптической кривой, хранится только одна координата х и знак координаты у.

Напомним основную теорему о строении конечных абелевых групп [ГЕН03].

Теорема.

Любая конечная абелева группа либо является примарной циклической группой, либо раскладывается в прямую сумму примарных циклических подгрупп:

G = (g) + (g) + … +(g),

где порядки элементов ord g= p, где p, …, p – не обязательно различные простые числа.

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

(p>=p) & ((p = p à(k>=k), i = 1, …, (t -1),

называется каноническим разложением конечной абелевой группы, а вектор (p, …, p) – типом этого разложения.

Существование приведенного разложения равносильно тому, что существует изоморфизм:

G = Z p + … + Z p,

который также называется каноническим разложением группы G.

В [K87, 197с.] показано, что тип абелевой группы точек эллиптической кривой в форме y= x – x над полем F_71 равен (4,2,9).