А. М. ГИЛЕВ
Московский инженерно-физический институт (государственный университет)
РЕАЛИЗАЦИЯ МЕТОДА ГЕНЕРАЦИИ ПАРАМЕТРОВ ЭЛЛИПТИЧЕСКИХ КРИВЫХ НА ОСНОВЕ АЛГОРИТМА ПОДСЧЁТА КОЛИЧЕСТВА ТОЧЕК
Описание библиотеки, реализующей алгоритм подсчёта количества точек эллиптической кривой над конечным полем. Знание количества точек эллиптической кривой необходимо для проверки её криптографической стойкости.
Многим криптографическим алгоритмам, использующим аппарат эллиптических кривых над конечным полем, требуется знание порядка группы используемой эллиптической кривой. В частности, порядок группы (количество точек) должен быть известен при генерации эллиптической кривой для того, чтобы проверить её криптографическую стойкость. Например, этого требуют новый американский и российский стандарты на цифровую подпись.
Существует два основных метода решения этой проблемы.
1. Использовать способы, позволяющие получать эллиптические кривые, порядок группы которых удовлетворяет некоторым выбранным заранее свойствам, например, алгоритмы “комплексного умножения” [1].
2. Выбрать эллиптическую кривую случайным образом, вычислить порядок группы этой эллиптической кривой, а затем проверить, удовлетворяет ли эллиптическая кривая требуемым свойствам, используя это вычисленное значение.
Первый алгоритм для подсчёта количества точек эллиптической кривой над конечным полем, выполняющийся за полиномиальное время, был предложен Шуфом (Schoof) [2]. В первое время считалось, что алгоритм Шуфа мало пригоден для применения на практике, но Элкис (Elkies) и Аткин (Atkin) внесли в него несколько важных добавлений [3, 4], после чего он стал известен как алгоритм SEA (по первым буквам фамилий авторов). Позже были предложены дальнейшие усовершенствования алгоритма [5, 6].
В ходе работы была написана библиотека “ECcount” на языке программирования C++, реализующая версию алгоритма SEA, описанную в статье [7]. Библиотеку можно собрать как в операционных системах Unix, так и в операционных системах Windows. Используя написанный код можно легко реализовать второй метод генерации параметров эллиптических кривых.
В качестве основы была взята известная математическая библиотека NTL [8]. Выбор базовой библиотеки обусловлен её функциональностью, скоростью (например, на ней были реализованы некоторые криптографические атаки), компактностью (исходный код занимает чуть более 600 килобайт), переносимостью и наличием криптографически стойкого генератора случайных чисел.
Существует несколько других реализаций алгоритма SEA, но они имеют определённые недостатки. В частности, рассматривались реализации, основанные на математических библиотеках Miracle и Lidia. Недостатком первой реализации является то, что в ней алгоритм представлен в виде отдельного приложения, лицензия которого запрещает его модификацию третьими сторонами. Данный факт не позволяет произвести интеграцию данной реализации алгоритма с другими программами, что значительно снижает удобство её использования, а также не позволяет произвести модификации использованного в ней алгоритма в целях ускорения его выполнения. Недостатком второй реализации является невозможность её сборки в операционных системах Windows.
Библиотека “ECcount” может быть расширена за счёт включения в неё новых быстрых алгоритмов подсчёта количества точек эллиптических кривых над полями Галуа порядка 2n [9]. Также возможно использовать библиотеку в качестве основы для более универсальной библиотеки на основе библиотеки NTL, реализующей весь набор операций с эллиптическими кривыми, необходимых для написания криптографических приложений.
Список литературы
1. A. O.L. Atkin, F. Morain, “Elliptic curves and primality proving”. Math Comp. 61, 203, 1993.
2. R. Schoof, “Elliptic curves over finite fields and the computation of square roots mod p”. Mathematics of Computation, 44:483-494, 1985.
3. N. D. Elkies, “Explicit isogenies”, manuscript, Boston, MA, 1992.
4. A. O. L. Atkin, Several public email messages, unpublished, .
5. L. Dewaghe., “Remarks on the Schoof-Elkies-Atkin algorithm”. Mathematics of Computation, 67(223):, 1998.
6. J.-M. Couveignes, F. Morain, “Schoof's algorithm and isogeny cycles”. Lecture Notes in Computer Science, 877, pages 43-58. Springer, Berlin, 1994.
7. J. A. Csirik, “An exposition of the SEA algorithm”, preprint, 2000.
8. V. Shoup, NTL - a library for doing numbery theory, http://www.
9. R. Lercier, D. Lubicz, “Counting points on elliptic curves over finite fields of small characteristic in quasi quadratic time”. Lect. Notes in Comput. Sci., vol. 2656, 360-373, Springer, 2003.
