Алгебра еліптичних кривих

Вступ

Література.

Час – 4 год.

Навчальні питання

Лекція 8. Криптографічні системи, що спираються на еліптичні криві

1.... Алгебра еліптичних кривих. 1

2.... Геометрія еліптичних кривих. 3

3.... Додавання точок на еліптичній кривій. 8

4.... Криптосистеми, що визначаються над еліптичними кривими. 11

5.... Безпека систем дискретних логарифмів, що спираються на еліптичні криві 13

1. Тилборг ван Х.К. Основы криптологии. Профессиональное руководство и интерактивный учебник. — М.: Мир, 2006, с. 208 – 230.

2. Henk C.A. van Tilborg, FUNDAMENTALS OF CRYPTOLOGY. A Professional Reference and Interactive Tutorial. Eindhoven University of Technology. The Netherlands. KLUWER ACADEMIC PUBLISHERS, Boston/Dordrecht/London.

3. Silverman J.H. The Arithmetic of Elliptic Curves, Springer Verlag, Berlin, etc., 1986.

4. Schoof R. Counting points on elliptic curves over finite fields, Journal de Theorie des Nombres de Bordeaux, 7, pp. 219-254, 1995.

5. Menezes A.J. Elliptic Curve Public Key Cryptosysterns, Kluwer Academic Publishers, Boston, etc., MA, 1993.

6. Demytko N. A new elliptic curve based analogue of RSA, Advances in Cryptology: Proc. of Eurocrypt'93, T. Helleseth, Ed., Lecture Notes in Computer Science 765, Springer Verlag, Berlin, etc., pp. 40-49, 1994.

7. Silverman J.H. The XEDNI calculus and the elliptic curve discrete logarithm problem, preprint.

Криптосистемы, основанные на проблеме дискретных логарифмов, могут также определяться на эллиптических кривых (ЕС). Теоретически система RSA тоже может быть реализована на эллиптических кривых, но большого смысла или существенного выигрыша в быстродействии такая реализация иметь не будет.

Криптосистемы, основанные на проблеме дискретных логарифмов и реализованные на эллиптических кривых, допускают меньшие значения ключевых параметров, обеспечивающие тот же уровень безопасности, какой дают обычные системы над конечными полями.

Однако многие вопросы, касающиеся ЕС-систем, на данный момент остаются еще открытыми.

Пусть) ‑ конечное поле из элементов, где. Число — простое и называется характеристикой поля Галуа. Если, то, это множество целых чисел, в котором операции сложения и умножения заданы по модулю.

Так называемое (аффинное[1]) уравнение Вейерштрасса имеет вид

(10.1)

Оно может определяться над любым полем (например, или), но для криптографических целей мы всегда будем предполагать, что коэффициенты уравнения лежат в.

Если, то уравнение Вейерштрасса можно упростить посредством преобразования. Получится (с новыми значениями, и) уравнение

(10.2)

Если, кроме того,, то можно применить также преобразование, чтобы привести уравнение к виду

(10.3)

При для соотношения (10.1) возможны два стандартных упрощения:

(10.4)

(10.5)

Дата добавления: 2013-12-12