Информационная система "Конференции"

IV Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям

Красноярск, Академгородок, 3-5 ноября 2003 года

Тезисы докладов

Вычислительная математика и математическое моделирование

Генерация криптографически сильных эллиптических кривых простого порядка

Имамвердиев Я.Н.

Институт Информационных Технологий Национальной Академии Наук Азербайджана (Баку)

Криптография эллиптических кривых является одним из базовых технологий построения инфраструктуры открытых ключей. Чтобы противостоять существующим алгоритмам решения задачи дискретного логарифмирования на эллиптической кривой, эллиптическая кривая должна удовлетворять определенным условияй. Таких кривых обычно называют криптографически сильными. Одним из известных проблем эллиптической криптографии является генерация сильных эллиптических кривых над конечными полями простого порядка. Для генерации эллиптических кривых предложены несколько подходов [3]. В простых случаях для генерации кривой можно использовать теорему Вейля [3]. Более распространенным методом является метод случайной генерации кривой. После генерации методами расчета числа точек [4] находится порядок кривой и проверяется выполнение известных условий. К сожалению, алгоритмы расчета числа точек эллиптической кривой над большими полями слишком медленны [4 ].

Другой подход использует комплексное умножение (КУ) [1]. Этот метод сначала определяет подходящий порядок, а потом генерирует эллиптическую кривую. Входным параметром метода является простое число p (порядок простого поля), из которого вычисляется так называемый дискриминант КУ D. Эллиптическая кривая генерируется построением многочленов Гильберта или Вебера на основе дискриминанта D и нахождением их корней [1,2,5].

Если кольцо эндоморфизмов эллиптической кривой имеет малое число классов, то метод КУ предпочтительнее метода случайной генерации. Но при больших значениях дискриминанта (D>200) существующие методы КУ становятся непрактичными из-за низкой скоростя. Поэтому актуальна разработка быстрых алгоритмов генерации эллиптических кривых методом КУ. Мы представляем модифицированный вариант метода КУ, наш вариант основан на вычислении многочленов Вебера. Многочлены Вебера в сравнении с многочленами Гильберта требуют значительно меньших временных и пространственных ресурсов.

Литература

1. A.O.L.Atkin, F.Morain, Elliptic curves and primality proving, Mathematics of Computation 61(1993), pp.29 -67.

2. H. Baier, J. Buchmann, Efficient Construction of Cryptographically Strong Elliptic Curves, Progress in Cryptology - INDOCRYPT 2000, LNCS 1977, p.191-202, Springer-Verlag, 2000

3. N. Koblitz, A. Menezes, and S. A. Vanstone, "The State of Elliptic Curve Cryptography", Designs, Codes and Cryptography 19, 2000, 173-193.

4. R. Lercier and F. Morain, Counting the number of points of on elliptic curves over finite fields: strategies and performances, Proc. Eurocrypt '95, Lecture Notes in Computer Science 921, Springer, 1995, pp. 79-94.

5. Ростовцев А.Г., О выборе эллиптической кривой над простым полем для построения криптографических алгоритмов //Проблемы информационной безопасности. Компьютерные системы. СПб., 1999, № 3. С. 37-40.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]