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

y = x + x над простым конечным полем F.

Имеется 23 точки, удовлетворяющие этому уравнению над данным полем:

Е(F_23) = {O, (0,0),(1,5),(1,18),(9,5),(9,18),(11,10),(11,13),(13,5),(13,18),(15,3),(15,20),

(16,8),(16,15),(17,10) (17,13),(18,10),(18,13),(19,1),(19,22),(20,4),(20,19),(21,6),(21,17)}

Графически точки кривой можно изобразить следующим образом:

На рисунке видна симметрия точек.

Во многих приложениях, на основе аппарата эллиптических кривых, используются кривые над F2m поскольку в этом случае точки на кривой и её коэффициенты представимы в виде двоичных векторов. Однако, в отечественном стандарте на цифровую подпись на основе эллиптических кривых [ГОСТ 34.10-2001], кривые над такими полями вообще не используются, а используются только кривые над конечным простым полем Fпри p > 2.

При перечислении точек кривой в форме Вейерштрасса y = x+a x +b над конечным полем F мы перебирали все возможные значения x, а затем находили y как квадратные корни из (x+ax +b), если они существуют. Рассмотрим вопрос существования и нахождения решений сравнения y = a (mod p) подробнее.

Далее потребуется

Определение [Г05].

Целое число a, взаимно простое с простым числом p, называется квадратичным вычетом по модулю p, если сравнение y = a (mod p) имеет решение, и квадратичным невычетом по модулю p в противном случае.

Известно, что среди чисел 1, … ,(p – 1) содержится (p-1)/2 квадратичных вычетов и (p-1)/2 квадратичных невычетов по модулю p. Кроме того, справедлива

Теорема (критерий Эйлера).

Целое число a, взаимно простое с p, является квадратичным вычетом или невычетом по простому модулю p>2 в том и только том случае, когда соответственно выполняется условие

a) a = 1 (mod p) или b) a = - 1 (mod p).

При этом в случае а) сравнение y = a (mod p) имеет точно 2 решения.

Нахождение самих решений сравнения y = a (mod p) , в случае его разрешимости, достаточно просто при р=3 (mod 4) и р=5 (mod 8). Есть и вероятностные методы нахождения решений [К87, Г05, 257с.].

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

Символ Лежандра (обозначается как (a/p), а – числитель, p – знаменатель символа) для нечетных простых чисел p определяется как 1, если a – квадратичный вычет по модулю p, и как – 1, если a квадратичный невычет. С использованием этого понятия критерий Эйлера можно переформулировать так. Целое число a является квадратичным вычетом по нечетному простому модулю p тогда и только тогда, когда (a/p)=a(mod p).

В работе [R87] вводится понятие квадратичного характера , обобщающего символ Лежандра. Это отображение, переводящее элемент конечного поля F в 1 или – 1, в зависимости от того, является или нет этот элемент квадратом некоторого элемента из этого поля. В случае когда q=p, где p простое число, (а) = (a/p) – символу Лежандра. В любом случае число решений уравнения y = a над F равно 1+(а). Тогда число точек N эллиптической кривой E(F) равно величине

N = 1+ (1+ (x+ax+b)) = q + 1 +( (x+ax+b)),

где суммирование берется по всем x из F.

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

Теорема (Hasse).

Число точек N эллиптической кривой над полем F (q=p), удовлетворяет неравенству

N - (q+1) < 2 .

Если обозначить через N(a, b,p) - число точек эллиптической кривой в форме Вейерштрасса над полем F , равное (p+1–t) при некотором t, то для числа N(a, b, p) – числа точек кривой с теми же коэффициентами a, b, но над полем F, то его можно найти [В03, 109 с.] из соотношения

N(a, b, p) = p+ 1 – t, где t удовлетворяет рекуррентному соотношению 2-го порядка

t_(j+1) = (t)(t) – p (t), j>=1, t = t, t = 2.

Поэтому важно уметь находить число точек кривой над конечным простым полем. Это имеет важное значение как в криптографии [ГОСТ 34.10-2001], так и в алгоритмах проверки простоты чисел [B03, 123 c.].

На практике часто необходимо знать не оценку, а точное число точек эллиптической кривой. Для подсчета этого числа к настоящему времени разработано несколько алгоритмов, а их реализацию можно найти в Интерненте (например, на странице http://www. informatik. tu-darmstadt. de/TI/LiDIA/Welcome. html ).

Сначала Шуф (Schoof) в 1985 году предложил полиномиальный алгоритм для подсчета числа точек эллиптической кривой для нечетных q. Вскоре Коблиц (Koblitz) распространил его на случай поля F [В03]. Алгоритм Шуфа эффективен для небольших значений q<100. Далее методы подсчета числа точек кривых были усовершенствованы Аткиным, Элкисом, Мюллером и другими для больших значений q.

В отечественном стандарте [ГОСТ 34.10 - 2001] требуется, чтобы порядок группы точек эллиптической кривой делился на большое простое число q из интервала 2< q <2. В стандарте [FIPS 186-2] используются кривые, порядок которых имеет вид q f, где f равен 1,2 или 4, а q также большое простое число.

Порядки точек эллиптических кривых

Пусть Р – точка из группы E(F) точек эллиптической кривой. Порядком точки Р называется наименьшее положительное целое число k, такое что kP = (P+ … +P) = O (суммирем k точек Р).