ВУЗ:
Составители:
180
В, при помощи которой можно снять «маску» k
B
a В, если знать секретное число
B
a . Злоумышленник, который умеет решать загачу дискретного
логарифмирования на Е, может, конечно, найти
B
a
зная
B
a
В и В.
Выбор кривой и точки. Существуют различные способы выбора
эллиптической кривой и (в системах Диффи-Хеллмана и Эль-Гамаля) точки В на
ней.
Случайный выбор (Е,В). Взяв какое-либо большое конечное поле
q
F ,
можно следующим образом осуществить одновременный выбор Е и В = (x, у)
∈
Е. (Будем предполагать, что характеристика р поля
q
F
больше 3, так что
эллиптическая кривая задана уравнением (1) из § 1; при q =
r
2 или
r
3
нетрудно
сделать очевидные изменения в дальнейшем изложении.) Выбираем сначала
случайным образом три элемента из
∗
q
F в качестве х, у, а. Далее полагаем
)axx(yb
32
+−= . Убеждаемся в том, что кубический многочлен baxx
3
++ не
имеет ' кратных корней, что равносильно проверке условия
0b27a4
23
≠+ . (Если
это условие не выполняется, берем другую случайную тройку х, у, а.) Полагаем
В = (х, у). Тогда В — точка на эллиптической кривой
baxxy
32
++= .
Число N точек кривой можно найти несколькими способами. Первый
полиномиальный алгоритм для вычисления #Е, построенный Рене Шуфом (Rene
Schoof), является даже детерминистическим. Он основывается на нахождении
значения #Е по модулю l для всех простых чисел l, меньших некоторой
границы. Для этого анализируется действие автоморфизма Фробениуса
(отображения в р-ю степень) на
точках порядка l.
В статье Шуфа оценка времени работы была фактически O(
qlog
8
), т. е.
хотя и полиномиальной, однако быстро растущей. Вначале казалось, что
алгоритм не имеет практического значения. Однако с тех пор многие пытались
повысить скорость алгоритма Шуфа (Миллер (V. Miller), Элкис (N. Elkis).
Бухман (J. Buchman), Мюллер (V. Miiller), Менезес (A. Menezes), Чарлап (L.
Charlap), Коули (R. Coley) и Роббинс (D.Robbins)). Кроме того. Эткин (А. О. L.
Atkin) разработал другой метод, который, хотя и не гарантирует
полиномиального
времени работы, на практике дает весьма удовлетворительные
результаты. В результате всех этих усилий стало возможным вычислять порядок
произвольной эллиптической кривой над
q
F , если q — степень простого числа,
записываемая 50 или даже 100 знаками.
Следует также отметить, что хотя для реализации систем Диффи-
Хеллмана или Эль-Гамаля знать N не нужно, на практике желательно быть
уверенным в их надежности, которая зависит от того, имеет ли N большой
простои делитель. Если N есть произведение малых простых
чисел, то для
Страницы
- « первая
- ‹ предыдущая
- …
- 178
- 179
- 180
- 181
- 182
- …
- следующая ›
- последняя »
