Применение эллиптических кривых в криптографии. Жданов О.Н - 20 стр.

UptoLike

ВУЗ: 

СибГАУ | Красноярск

Составители: 

Рубрика: 

Пример 4. Точка В = (0, 0) является точкой бесконечного порядка на эллиптической
кривой
Е: xxyy −=+
32
и фактически порождает всю группу рациональных точек на Е.
Пример 5.
Точка В = (0, 0) является точкой бесконечного порядка на Е:
232
xxyy −=+ и порождает всю группу рациональных точек.
Далее, мы выбираем большое простое число
р (или, если наша эллиптическая кри-
вая определена над расширением
К поля Q, выбираем некоторый простой идеал в К) и
рассматриваем редукцию
Е и В по модулю р. Точнее, для всех р, за исключением несколь-
ких малых простых чисел, коэффициенты в уравнении для
Е имеют взаимно простые с р
знаменатели и, следовательно, могут рассматриваться как коэффициенты в уравнении по
модулю
р. Если сделать замену переменных, приведя полученное уравнение над
p
F к ви-
ду
baxxy ++=
32
то кубический многочлен в главой части не будет иметь кратных кор-
ней (за исключением нескольких малых простых
р) и дает поэтому эллиптическую кри-
вую над
p
F
(которую мы будем обозначать Е(mod p)). Координаты точки В, будучи также
приведенными по модулю
р, дают точку на эллиптической кривой Е(mod p), которую мы
будем обозначать
В(mod p).
При использовании этого второго способа мы раз и навсегда фиксируем
Е и В и за
счет этого получаем много различных возможностей посредством изменения простого
р.
Порядок точки В.
С какой вероятностью «случайная» точка В на «случайной» эллиптической кривой
оказывается порождающим элементом? Или, в случае нашего второго метода выбора (
Е,
В), какова вероятность того, что (для случайного р) точка В при редукции по модулю дает
образующий элемент кривой
Е(mod p)? Этот вопрос близок к следующему вопросу о
мультипликативных группах конечных полей: пусть целое
b фиксировано, а простое р
случайно; какова вероятность того, что
b – образующий элемент в
∗
p
F
? Вопрос изучался
как для конечных полей, так и для эллиптических кривых.
Как упоминалось выше, описанные криптосистемы могут быть надежными даже
если точка
В не является порождающим элементом Фактически нужно, чтобы в цикличе-
ской группе, порождаемой
В, задача дискретного логарифмирования не была эффективно
разрешима. Это будет так (т.е. все известные методы решения задачи дискретного лога-
рифмирования в произвольной абелевой группе оказываются слишком медленными), если
порядок
B делится на очень большое простое число, скажем, имеющее порядок величины,
близкий к
N.
Один из способов гарантировать, что наш выбор
B является надлежащим (а факти-
чески, что
B порождает эллиптическую кривую) – это взять такую эллиптическую кривую
и такое конечное поле, чтобы число точек
N было простым чистом. Тогда всякая точка В
≠ O будет порождающим элементом. Если использовать первый из описанных выше ме-
тодов, то при фиксированном
p
F
можно продолжать выбор пар (Е, В), пока не найдется
такая, для которой число точек на
Е есть простое число (что можно определить одним из
известных тестов на простоту). Если применять второй метод, то для фиксированной гло-
бальной эллиптической кривой
Е над Q можно продолжать выбирать простые р, пока не
найдем кривую
Е(mod p), число точек на которой простое. Как долго нам придется ждать?
Этот вопрос аналогичен следующему вопросу о группах
∗
p
F
: является ли (р – 1)/2 про-
стым числом, т.е. верно ли, что любой элемент, отличный от ±1, – либо порождающий,
либо квадрат порождающего элемента? Ни для эллиптических кривых, ни для конечных
полей вопрос пока не получил явного ответа, однако в обоих случаях предполагается, что
вероятность выбора
р с требующимся свойством есть O(1/ plog )
3амечание.
Для того чтобы Е(mod p) имела простой порядок N при большом р, надо
выбирать
Е так, чтобы она имела тривиальное кручение, т.е. чтобы на ней не было точек

Страницы