Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
ЛИТЕРАТУРА к § 1 ГЛАВЫ VI
1. Eulton W. Algebraic Curves. Menlo Park: Benjamin, 1969.
2. Husemoller D. Elliptic Curves. Heidelberg etc.: Springer, 1987.
3. Koblitz N. Introduction to Elliptic Curves and Modular Forms. 2nd ed. Heidelberg etc.: Springer, 1993.
4. Koblitz N. Why study equations over finite fields? — Math. Mag., 1982, v. 55, p. 144-149.
5. Lang S. Elliptic Curves: Diophantine Analysis. Heidelberg etc.: Springer, 1978.
6. Silverman J. The Arithmetic of Elliptic Curves. Heidelberg etc.: Springer, 1986.
§ 2. Криптосистемы на эллиптических кривых
В § IV. 3 мы показали, как можно конечную абелеву группу — мультипликативную группу конечного поля — использовать для создания криптосистемы с открытым ключом. Точнее, именно слож-
§ 2. КРИПТОСИСТЕМЫ НА ЭЛЛИПТИЧЕСКИХ КРИВЫХ
201
ность решения задачи дискретного логарифмирования приводит к криптосистемам, обсуждавшимся в § IV. 3. Цель этого параграфа — построение аналогичных систем с открытым ключом, основанных на конечной абелевой группе эллиптической кривой, определенной над F9.
Прежде чем описывать криптосистемы, нужно обсудить некоторые вспомогательные понятия.
Кратные точки. Для эллиптических кривых аналогом умножения двух элементов группы F* служит сложение двух точек эллиптической кривой Е, определенной над F9. Таким образом, аналог возведения в степень к элемента из F* — это умножение точки P є E на целое число к. Возведение в к-ю степень в F9 методом повторно-го возведения в квадрат можно осуществить за О (log Hog q) двоичных операций (см. предложение II. 1. 9). Аналогично, мы покажем, что кратное кP є E можно найти за 0(log&log q) двоичных операций методом повторного удвоения.
Пример 1. Чтобы найти 100Р, записываем 100Р = 2(2(P + 2(2(2(P + 2P))))) и приходим к цели, производя 6 удвоений и 2 сложения точек на кривой.
Предложение VI. 2.1. Пусть эллиптическая кривая E определена уравнением Вейерштрасса (уравнением (1),(2) или (3) из предыдущего параграфа) над конечным полем F9. Если задана точка P на
Е, то координаты kP можно вычислить за 0(\ogk\og q) двоичных операций.
Доказательство. Заметим, что вычисление координат суммы двух точек по уравнениям (4)-(5) (или по аналогичным уравнениям из упражнения 6 к § 1) требует не более 20 действий в F9 (умножений, делений, сложений или вычитаний). Поэтому, согласно предложению II. 1.9, сложение двух точек (или удвоение точки) занимает время О (log3 q). Так как при методе повторного удвоения выполняется 0(logA;) одинаковых шагов (см. доказательство предложения 1.3.6), мы получаем, что координаты точки kP вычисляются за 0(log&log q) двоичных операций.
Замечание 1. Оценки времени работы в предложении VI. 2.1 не являются наилучшими, особенно для конечных полей характеристики р = 2. Нам, однако, достаточно этих оценок, которые следуют из наиболее очевидных алгоритмов арифметики в конечных полях.
Замечание 2. Если известно число N точек на нашей эллиптической кривой E и если к > JV, то в силу равенства NP = O мы можем заменить к его наименьшим неотрицательным вычетом по модулю N; в этом случае временная оценка заменяется на 0(log4 q)
202
ГЛ. VI. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ
(напомним, что N^q + l+ 2^/q = 0(q)). Рене Шуф (R. Schoof) предложил алгоритм, вычисляющий N за 0(log8 q) двоичных операций.
Представление открытого текста. Мы намереваемся кодировать наши открытые тексты точками некоторой заданной эллиптической кривой Е, определенной над конечным полем F9. Мы хотим это осуществить простым и систематическим способом так, чтобы открытый текст тп (который можно рассматривать как целое число из некоторого интервала) можно было легко прочитать, зная координаты соответствующей точки Рт. Заметим, что это «кодирование» — не то же самое, что засекречивание. Позднее мы будем рассматривать способы шифрования точек Рт открытого текста. Однако законный пользователь системы должен быть в состоянии восстановить т после дешифрования точки шифртекста.
Следует сделать два замечания. Во-первых, не известно детерминистического полиномиального (по logg) алгоритма для выписывания большого числа точек произвольной эллиптической кривой E над F9. Однако, как мы увидим далее, существуют вероятностные алгоритмы с малой вероятностью неудачи. Во-вторых, порождать случайные точки на E недостаточно: чтобы закодировать большое число возможных сообщений т, необходим какой-то систематический способ порождения точек, которые были бы связаны с т определенным образом, например, чтобы х-координата имела с т простую связь.
Приведем один возможный вероятностный метод представления открытых текстов как точек на эллиптической кривой Е, определенной над F9, где q = рг предполагается большим (и нечетным (см. ниже упражнение 8 при q = 2Г)). Пусть х — достаточно большое целое число, настолько, что можно считать допустимым, если попытка представить в нужном нам виде элемент («слово») открытого текста т оказывается неудачной в одном случае из 2х; практически достаточно X = 30 или, на худой конец, х = 50. Пусть элементы нашего сообщения т — целые числа, 0 ^ т ^ М. Предположим также, что выбранное нами конечное поле имеет q элементов, q > Mx. Записываем целые числа от 1 до Mx в виде mx + j, где 1 ^ х, и устанавливаем взаимно однозначное соответствие между такими числами и некоторым множеством элементов из F9. Например, можно записать такое число как г-значное число в р-ичной системе счисления и, отождествляя цифры в этой записи с элементами Fp = Z/pZ, рассматривать их как коэффициенты многочлена степени не выше г - 1 над Fp, соответствующего элементу поля F9. Таким образом, числу (ат._1ат._2 ... аі«о)р ставится в соответствие многочлен ?[=0 ctiX1, который, будучи рассмотрен по модулю некоторого фиксированного неприводимого многочлена степе-
