ВУЗ:
Составители:
пользователю Б сообщение, которое кодируется эллиптической точкой
m
P = (562,201), и
что пользователь А выбирает случайное число k = 386. Открытым ключом Б является
B
P
= (201,5). Мы имеем 386(0,376) = (676,558) и (562,201) + 386(201, 5) = (385, 328). Таким
образом, пользователь А должен послать шифрованный текст {(676, 558), (385, 328)}.
Выбор кривой и точки.
Существуют различные способы выбора эллиптической кривой и (в системах
Диффи-Хеллмана и Эль-Гамаля) точки
В на ней.
1) Случайный выбор (
Е, В). Взяв какое-либо большое конечное поле
q
F , можно
следующим образом осуществить одновременный выбор
Е и В = (x, у) ∈ Е. Будем предпо-
лагать, что характеристика
р поля
q
F больше 3, так что эллиптическая кривая задана
уравнением (1) из § 1; при
q =
r
2 или
r
3
нетрудно сделать очевидные изменения в даль-
нейшем изложении. Выбираем сначала случайным образом три элемента из
∗
q
F
в качестве
х, у, а. Далее полагаем )(
32
axxyb +−= . Убеждаемся в том, что кубический многочлен
baxx ++
3
не имеет кратных корней, что равносильно проверке условия
0274
23
≠+ ba
.
Если это условие не выполняется, берем другую случайную тройку
х, у, а. Полагаем В =
(
х, у). Тогда В – точка на эллиптической кривой baxxy ++=
32
.
Число
N точек кривой можно найти несколькими способами. Первый полиноми-
альный алгоритм для вычисления #
Е, построенный Рене Шуфом (Rene Schoof), является
даже детерминированным. Он основывается на нахождении значения #
Е по модулю l для
всех простых чисел
l, меньших некоторой границы. Для этого анализируется действие ав-
томорфизма Фробениуса (отображения в
р-ю степень) на точках порядка l.
В статье Шуфа оценка времени работы была фактически
O( q
8
log ), т. е. хотя и по-
линомиальной, однако быстро растущей. Вначале казалось, что алгоритм не имеет прак-
тического значения. Однако с тех пор многие пытались повысить скорость алгоритма
Шуфа: Миллер (V. Miller), Элкис (N. Elkis). Бухман (J. Buchman), Мюллер (V. Muller),
Менезес (A. Menezes), Чарлап (L. Charlap), Коули (R. Coley) и Роббинс (D.Robbins). Кроме
того. Эткин (А.О.L. Atkin) разработал другой метод, который, хотя и не гарантирует
поли-
номиального времени работы, на практике дает весьма удовлетворительные результаты. В
результате всех этих усилий стало возможным вычислять порядок произвольной эллипти-
ческой кривой над
q
F , если q – степень простого числа, записываемая 50 или даже 100
знаками. Некоторые методы нахождения числа точек на эллиптической кривой рассмат-
риваются в работах из приведенного в конце пособия списка литературы.
Следует также отметить, что хотя для реализации систем Диффи-Хеллмана или
Эль-Гамаля знать
N не нужно, на практике желательно быть уверенным в их надежности,
которая зависит от того, имеет ли
N большой простой делитель. Если N есть произведение
малых простых чисел, то для решения задачи дискретного логарифмирования можно ис-
пользовать метод Полига-Силвера-Хеллмана. Заметим, что метод Полига-Силвера-
Хеллмана решает задачу дискретного логарифмирования в любой конечной абелевой
группе (в отличие от алгоритма вычисления индекса, который зависит от особенностей
∗
q
F ). Таким образом, нужно знать, что N не есть произведение малых простых чисел и не
похоже, что это можно узнать, если не найти фактически значение
N.
2) Редукция глобальной пары (
Е, В) по модулю р. Упомянем теперь второй способ
нахождения пары, состоящей из эллиптической кривой и точки на ней. Выберем сначала
раз и навсегда «глобальную» эллиптическую кривую и точку бесконечного порядка на
ней. Итак, пусть
Е – эллиптическая кривая, определенная над полем рациональных чисел
(или, для большей общности, можно было бы использовать эллиптическую кривую, опре-
деленную над некоторым числовым полем), и
В – точка бесконечного порядка на Е.
Страницы
- « первая
- ‹ предыдущая
- …
- 17
- 18
- 19
- 20
- 21
- …
- следующая ›
- последняя »
