Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
10. Пусть E — эллиптическая кривая у2 + у = х3 — х, определенная над Q, и пусть P = (0, 0). Вычисляя 21 P для j = 1,2,..., найти пример такого простого р, что E (mod р) не порождается точкой P (mod р). (Замечание. Можно показать, что P порождает группу рациональных точек на Е.)
11. Использовать построенный по эллиптической кривой аналог системы Эль-Гамаля, чтобы послать сообщение упражнения За, выбирая E и р так же, как в упражнении 3, и полагая В = (0,0). Предположим, что открытый ключ вашего корреспондента — это точка (201, 380) и что ваша последовательность случайных значений к — это 386, 209, 118, 589, 312, 483, 335 (каждое из них используется для посылки одного элемента сообщения). Какую последовательность из 7 пар точек вы посылаете?
Заметим, что в этом упражнении мы использовали довольно малое значение р; более реальный пример такого рода, с которым можно встретиться на практике, потребовал бы работы с числами, записанными с помощью нескольких дюжин десятичных цифр.
ЛИТЕРАТУРА к § 2 ГЛАВЫ VI
1. Agnew G., Mullin R., Vanstone S.A. An implementation of elliptic curve cryptosystems over F2i55. — IEEE J. Select. Areas Comm., 1993, v. 11, p. 804-813.
2. Gupta R., Murty M. R. Primitive points on elliptic curves. — Compositio Math., 1986, v. 58, p. 13-44.
3. Roblitz N. Elliptic curve cryptosystems. — Math. Сотр., 1987, v. 48.
4. Roblitz N. Primality of the number of points on an elliptic curve over a finite field. — Pacific J. Math., 1988, v. 131, p. 157-165.
5. Roblitz N. Constructing elliptic curve cryptosystems in characteristic 2. — In: Advances in Cryptology —Crypto'90. Heidelberg etc.: Springer, 1991, v. 156-167.
6. Roblitz N. Elliptic curve implementation of zero-knowledge blobs. — J. Cryptology, 1991, v. 4, p. 207-213.
7. Roblitz N. CM-curves with good cryptographic properties. — In: Advances in Cryptology —Crypto'91. Heidelberg etc.: Springer, 1992, p. 279-287.
8. Lenstra H. W., Jr. Elliptic curves and number-theoretic algorithms. — Report 86-19. Amsterdam: Mathematisch Instituut, Universiteit van Amsterdam, 1986.
9. Menezes A. Elliptic Curve Public Key Cryptosystem. Dordrecht: Kluwer Acad. Publ., 1993.
10. Menezes A., Okamoto Г., Vanstone S.A. Reducing elliptic curve logarithms to logarithms in a finite field. — IEEE Trans. Inform. Theory IT-39, 1993, p. 1639-1646.
11. Menezes A., Vanstone S., Zuccherato R. Counting points on elliptic curves over F2"». — Math. Сотр., 1993, v. 60, p. 407-420.
212
ГЛ. VI. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ
12. Miller V. Use of elliptic curves in cryptography. — In: Abstracts for Crypto 85, 1985.
13. Odlyzko A. M. Discrete logarithms in finite fields and their cryptographic significance. — In: Advances in Cryptology, Proceedings of Eurocrypt 84. Heidelberg etc.: Springer, 1985, p. 224-314.
14. Schoof R. Elliptic curves over finite fields and the computation of square roots mod p. — Math. Сотр., 1985, v. 44, p. 483-494.
§ 3. Критерий простоты, использующий эллиптические кривые
Критерий простоты, использующий эллиптические кривые, который предложили Гольдвассер (S. Goldwasser), Килиан (J.Kilian) и (в другом варианте) Эткин (А. О. L. Atkin), представляет собой аналог следующего связанного с группой (Z/nZ)* критерия простоты По-клингтона (Н. Pocklington).
Предложение VI. 3.1. Пусть п — натуральное число. Предположим, что имеется простой делитель q числа n—1, больший у/п—1. Если существует такое целое число а, что 1) а™ 1 = 1 (mod п) и 2) НОД (а^п 1^9 — l,n) = 1, то п — простое число.
Доказательство. Если п — не простое, то существует простой делитель р числа п, не превосходящий у/п. Так как q > р— 1, имеем НОД (q,p— 1) = 1, и, следовательно, существует такое целое
1 / J 1 \ rp (n—1)/<?\_ uq{n—l)/q и(п— 1)
и, что uq = 1 (mod р - \). Іогда a s_a = а =
1 (mod р) (по условию 1)). Однако это противоречит условию 2).
Замечания. Это — отличный тест при условии, что п — 1 делится на простое число q > у/п — 1 и что мы в самом деле можем найти это q (и доказать его простоту). В противном случае им пользоваться нельзя. (Впрочем, это не совсем так — существует более общий вариант, применимый тогда, когда известны большой делитель п — 1 и известно его разложение на простые множители, см. упражнение 2 ниже.)
Отметим, что этот критерий простоты является вероятностным лишь в том смысле, что случайно выбранное а может либо удовлетворять, либо не удовлетворять условию 2) (но, конечно, а обязано удовлетворять условию 1), иначе п — не простое). Однако, как только такое а найдено (обычно достаточно взять а = 2), критерий доказывает, что п — простое число. В отличие от тестов § V. 1 (тестов Соловея-Штрассена и Миллера-Рабина), заключение теста Поклинг-тона — совершенно определенное: п — простое число (а не «вероятно простое»).
§ 3. КРИТЕРИЙ ПРОСТОТЫ
213
Критерий простоты, использующий эллиптические кривые, основан на аналогичном предложении, в котором предполагается задан-
2 3
ным уравнение у = х + ах + Ь, рассматриваемое по модулю п. Иначе говоря, целые числа а, Ь рассматриваются как вычеты по модулю п и E обозначает множество всех пар (х,у) целых чисел из Z/nZ, удовлетворяющих этому уравнению, вместе с символом О, который мы называем «точкой в бесконечности». Если п — простое число (а это почти всегда так, ибо практически мы рассматриваем лишь числа, прошедшие тесты на вероятную простоту из § V. 1), то E — эллиптическая кривая с нейтральным элементом О.
