Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
§ 2. КРИПТОСИСТЕМЫ НА ЭЛЛИПТИЧЕСКИХ КРИВЫХ
203
ни г над Fp, дает элемент F9.
Итак, при данном т при каждом j = 1, 2,..., х мы получаем элемент X из F9, соответствующий тн-\- j. Для такого х вычисляем правую часть уравнения
у2 = f(x) = X3 + ах + b
и пытаемся найти квадратный корень из f(x), используя метод, изложенный в конце §11.2. (Хотя этот алгоритм был приведен для простого поля Fp, он дословно переносится на любое конечное поле F9. Чтобы воспользоваться им, нужно иметь элемент д в этом поле, не являющийся квадратом; его можно легко найти с помощью вероятностного алгоритма.) Если мы находим такой у, что у2 = f(x), то берем P7n = (х,у). Если f(x) не оказывается квадратом, то увеличиваем j на 1 и повторяем попытку с соответствующим значением х. Если мы находим х, для которого f(x) — квадрат, прежде, чем j превысит х, то мы можем восстановить т по известной точке (х,у) с помощью формулы т = [(х — j)/x], где х — целое число, соответствующее X при установленном взаимно однозначном соответствии между целыми числами и элементами F9. Так как f(x) — квадрат приблизительно в 50% случаев, то вероятность того, что метод не приведет к результату и мы не найдем точки P7n с х-координатой, соответствующей целому числу X между тх + 1 и mx + х, равна примерно 2 *. (Точнее, вероятность того, что f(x) есть квадрат, фактически равна N/(2q), однако N/(2q) очень близко к 1/2.)
Дискретный логарифм на Е. В § IV. 3 мы рассматривали криптосистемы с открытым ключом, основанные на задаче дискретного логарифмирования в мультипликативной группе конечного поля. Теперь мы сделаем то же самое в группе (относительно сложения точек) эллиптической кривой, определенной над конечным полем F9.
Определение. Пусть E — эллиптическая кривая над F9 и В — точка на Е. Задачей дискретного логарифмирования на E (с основанием В) называется задача нахождения для данной точки P^E такого целого числа х ? Z (если оно существует), что хВ = Р.
Вполне возможно, что задача дискретного логарифмирования на эллиптической кривой окажется более трудной для решения, чем задача дискретного логарифмирования в конечных полях. Наиболее сильные методы, разработанные для конечных полей, по-видимому, не работают в случае эллиптических кривых. Это обстоятельство по-особенному отчетливо проявляется в случае полей характеристики 2. Как объясняется в обзорной статье Одлыжко, упомянутой в списке литературы, специальные методы решения задачи дискретного лога-
204
ГЛ. VI. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ
рифмирования в F2r позволяют сравнительно легко вычислять дискретные логарифмы и, следовательно, вскрывать криптосистемы, рассмотренные в § IV. 3, если г не выбрано очень большим. Аналогичные системы, использующие эллиптические кривые над F2r (см. ниже), судя по всему, являются надежными при значительно меньших значениях г. Так как имеются практические причины (связанные с устройством ЭВМ и программированием) предпочтительности арифметических операций над полями F2r, криптосистемы с открытым ключом, рассматриваемые ниже, могут оказаться более удобными для практического применения, чем системы, основанные на задаче дискретного логарифмирования в F*.
До 1990 г. единственными известными алгоритмами дискретного логарифмирования на эллиптических кривых были те, которые работают в любой группе и не используют особенности ее строения. Эти алгоритмы с экспоненциальным временем работы применимы к случаям, когда порядок группы делится на большое простое число. Однако впоследствии Менезес (Menezes), Окамото (Okamoto) и Вэн-стон (Vanstone) предложили новый подход к задаче дискретного логарифмирования на эллиптической кривой Е, определенной над F9. А именно, они использовали спаривание Вейля (см. § III. 8 учебника Силвермена (Silverman) из списка литературы к § 1) для вложения группы E в мультипликативную группу некоторого расширения F9* поля F9. Это вложение сводит задачу дискретного логарифмирования на E к соответствующей задаче для F*k. \
Однако такое сведение полезно, лишь еслії'степень к расширения мала. Фактически единственный вид эллиптических кривых, для которых к мало, — это так называемые «суперсингулярные» эллиптические кривые, наиболее известными примерами которых являются кривые вида у2 = х3-\-ах надполем F9 характеристики р = -l(mod4)
2 3
и кривые вида у = х 4- b над полем F9, когда р = — 1 (mod 3). Как правило, эллиптические кривые не являются суперсингулярными. Для них такое сведение почти никогда не приводит к субэкспоненциальным алгоритмам (см. мою работу в J. of Cryptology, приведенную в списке литературы).
Таким образом, основные преимущества криптосистем на эллиптических кривых заключаются в том, что не известны субэкспоненциальные алгоритмы вскрытия этих систем, если в них не используются суперсингулярные кривые, а также кривые, порядки которых делятся на большое простое число.
Теперь мы опишем аналоги систем с открытым ключом из § IV. 3, основанные на задаче дискретного логарифмирования на эллиптической кривой, определенной над конечным полем F9.
