Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Как упоминалось выше, описанные криптосистемы могут быть надежными, даже если точка В не является порождающим элементом. Фактически нужно, чтобы в циклической группе, порождаемой В, задача дискретного логарифмирования не была эффективно разрешима. Это будет так (т. е. все известные методы решения задачи дискретного логарифмирования в произвольной абелевой группе оказываются слишком медленными), если порядок В делится на очень большое простое число, скажем, имеющее порядок величины, близкий к N.
Один из способов гарантировать, что наш выбор В является надлежащим (а фактически, что В порождает эллиптическую кривую) — это взять такую эллиптическую кривую и такое конечное поле, чтобы число точек N было простым числом. Тогда всякая точка В ф О будет порождающим элементом. Если использовать первый из описанных выше методов, то при фиксированном Fp можно продолжать выбор пар (Е,В), пока не найдется такая, для которой число точек на E есть простое число (что можно определить одним из тестов на простоту, обсуждавшихся в § V. 1). Если применять второй метод, то для фиксированной глобальной эллиптической кривой E над Q можно продолжать выбирать простые р, пока не найдем кривую E (mod р), число точек на которой — простое. Как долго нам придется ждать? Этот вопрос аналогичен следующему вопросу о группах F*: является ли (р - 1)/2 простым числом, т.е. верно ли, что любой элемент, отличный от ±1, — либо порождающий, либо квадрат порождающего элемента (см. упражнение 13 к §11.1)? Ни для эллиптических кривых, ни для конечных полей вопрос пока не получил явного ответа, однако в обоих случаях предполагается, что вероятность выбора р с требующимся свойством есть 0(1/ logр).
Замечание. Для того чтобы E (mod р) имела простой порядок JV при большом р, надо выбирать E так, чтобы она имела тривиальное кручение, т. е. чтобы на ней не было точек конечного порядка, кроме О. В противном случае JV будет делиться на порядок периодической подгруппы.
210
ГЛ. VI. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ
УПРАЖНЕНИЯ
1. Построить вероятностный алгоритм для нахождения элемента, не являющегося квадратом в F5.
2. Описать полиномиальный детерминистический алгоритм для представления открытых текстов в виде точек на эллиптических кривых в следующих случаях:
(а) E имеет уравнение = і3 - і и } E 3 (mod 4);
(б) E имеет уравнение у2+у = х3ид = 2 (mod 3).
3. Пусть E — эллиптическая кривая у2 + у = х3 — х, определенная над полем из р = 751 элементов (заменой переменных вида у' = у + 376 это уравнение приводится к виду (1) из § 1). Эта кривая содержит N = 727 точек. Предположим, что передаваемые элементы открытого текста — это десятичные цифры 0-9 и буквы A-Z с числовыми эквивалентами 10-35 соответственно. Берем х = 20.
а) Применяя изложенный метод, написать сообщение «STOP007» в виде последовательности семи точек на кривой.
б) Перевести последовательность точек (361, 383), (241, 605), (201, 380), (461, 467), (581, 395) в ответное сообщение.
4. Пусть E — эллиптическая кривая, определенная над Q, и р — большое простое число, в частности, настолько большое, что, приводя уравнение у2 = х3 + ах + 6 по модулю р, мы получаем эллиптическую кривую над Fp. Показать, что
а) если многочлен х3 + ах + b разлагается по модулю р на три линейных множителя, то E (mod р) — не циклическая;
б) если этот многочлен имеет корень по модулю р, то число N элементов на E (mod р) четно.
5. Пусть E — эллиптическая кривая из примера 5 в § 1. Полагаем q = 2r, и пусть Nr — число F2---T04eK на Е. \
а) Показать, что при г > 1 число NT не может быть простым.
б) В случае 4|г найти условия, эквивалентные тому, что NT делится на (г/4)-разрядное или (г/4 + 1)-разрядное простое число в двоичной записи.
6. Пусть E — эллиптическая кривая, определенная над Fp, и N1- обозначает число Fpг-точек на Е.
а) Доказать, что при г > 1 и р > 3 число NT не может быть простым.
б) Привести контрпримеры к части а) в случаях р = 2 и р = 3.
7. а) Найти эллиптическую кривую Е, определенную над F4, которая имеет лишь одну F4-T04Ky (точку в бесконечности О).
б) Показать, что число F4г-точек на кривой из части а) есть квадрат числа Мерсенна 2Г — 1.
в) Найти простую формулу удвоения F4>--to4kh на этой кривой.
г) Доказать, что если 2Г — 1 — простое число Мерсенна, то всякая F4i--T04Ka (за исключением О) имеет порядок в точности 2Г — 1.
8. Пусть г нечетно и пусть К обозначает поле Fjr. Для z ? К пусть g(z) обозначает Y^f=q ' > а *г z (называемый «следом») обозначает JZj = O 2^' ¦
а) Доказать, что tr z Є F2; tr (zi +Z2) = ti z\ + tr z2\ tri = 1; g(z) + g(z)2 = z + tr z.
б) Показать, что tr z = 0 для одной половины элементов из К и tr г = 1 для другой половины.
§ 2. КРИПТОСИСТЕМЫ НА ЭЛЛИПТИЧЕСКИХ КРИВЫХ
211
в) Описать вероятностный алгоритм порождения Ггг-точек на эллиптической кривой у2 + у = х3 + ах + Ь.
9. Пусть E — эллиптическая кривая у2 = х3 + ах + b с а, Ь Є Z. Пусть P Є Е. Пусть р > 3 обозначает такое простое число, что ни 4а3 +2762, ни знаменатели х-и 2/-координат точки P не делятся на р. Показать, что порядок точки P (mod р) на эллиптической кривой E (mod р) — это такое наименьшее натуральное число к, что либо 1) kP = О на Е, либо 2) р делит знаменатель координат кР.
