Методы и средства криптографической защиты информации. Жданов О.Н - 181 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

181
решения задачи дискретного логарифмирования можно использвать метод
Полига-Силвера-Хеллмана (см. § IV. 3). Заметим, что метод Полига-Силвера-
Хеллмана решает задачу дискретного логарифмирования в любой конечной
абедевой группе (в отличие от также рассмотренного в § IV.3 алгоритма
зычисления индекса, который зависят от особенностей
∗
q
F
). Таким обрезом,
нужно знать, что N не есть произведение малых простых чисел и не похоже, что
это можно узнать, если не найти фактически значение N.
Редукция глобальной пары {Е,В) по модулю р. Упомянем теперь второй
способ нахождения пары, состоящей из эллиптической кривой и точки на ней.
Выберем сначала раз
и навсегда «глобальную» эллиптическую кривую и точку
бесконечного порядка на ней. Итак, пусть Е — эллиптическая кривая,
определенная над полем рациональных чисел (или, для большей общности,
можно было бы использовать эллиптическую кривую, определенную над
некоторым числовым полем), и В — точка беексконечного порядка на Е.
Пример 2. Точка В = (0, 0) является точкой бесконечного порядка
на
эллиптической кривой Е:
xxyy
32
−=+ и фактически порождает всю группу
рациональных точек на Е.
Пример 3. Точка В = (0, 0) является точкой бескспечного порядка на, Е:
232
xxyy −=+ и порождает всю группу рациональных точек.
Далее, мы выбираем большое простое число р (или, если наша
эллиптическая кривая определена над расширением К поля Q, выбираем
некоторый простой идеал в К) и рассматриваем редукцию Е и В по модулю р.
Точнее, для всех р, за исключением нескольких малых простых чисел,
коэффициенты в
уравнении для Е имеют взаимно простые с р знаменатели и,
следовательно, могут рассматриваться пак коэффициенты в уравнении по
модулю р. Если сделать замену переменных, приведя полученное уравнение над
p
F к виду baxxy
32
++= то кубический многочлен в главой части не будет иметь
кратных корней (за исключением нескольких малых простых р) и дает поэтому
эллиптическую кривую над
p
F (которую мы будем обозначать Е(mod p)).
Координаты точки В, будучи также приведенными по модулю р, дают точку на
эллиптической кривой Е (mod p), которую мы будем обозначать В (mod p).
При использовании этого второго способа мы раз и навсегда фиксируем Е
и В и за счет этого получаем много различных возможностей посредством
изменения простого р.
Порядок точки В. С какой вероятностью «случайная» точка В на
«случайной» эллиптической кривой оказывается порождающим элементом?
Или, в случае нашего второго метода выбора (Е, В), какова вероятность того,
что (для случайного р) точка В при редукции по модулю дает образующий

Страницы