Реализация метода генерации параметров эллиптических кривых на основе алгоритма подсчёта количества точек



Скачать 28.33 Kb.
Дата24.11.2012
Размер28.33 Kb.
ТипДокументы

УДК 004.056:378(06) Проблемы информационной безопасности в системе высшей школы


А.М. ГИЛЕВ

Московский инженерно-физический институт (государственный университет)
РЕАЛИЗАЦИЯ МЕТОДА ГЕНЕРАЦИИ ПАРАМЕТРОВ ЭЛЛИПТИЧЕСКИХ КРИВЫХ НА ОСНОВЕ АЛГОРИТМА ПОДСЧЁТА КОЛИЧЕСТВА ТОЧЕК
Описание библиотеки, реализующей алгоритм подсчёта количества точек эллиптической кривой над конечным полем. Знание количества точек эллиптической кривой необходимо для проверки её криптографической стойкости.
Многим криптографическим алгоритмам, использующим аппарат эллиптических кривых над конечным полем, требуется знание порядка группы используемой эллиптической кривой. В частности, порядок группы (количество точек) должен быть известен при генерации эллиптической кривой для того, чтобы проверить её криптографическую стойкость. Например, этого требуют новый американский и российский стандарты на цифровую подпись.

Существует два основных метода решения этой проблемы.

  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, 1991-1992.

  5. L. Dewaghe., “Remarks on the Schoof-Elkies-Atkin algorithm”. Mathematics of Computation, 67(223):1247-1252, 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.shoup.net

  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.




ISBN 5-7262-0557-Х. XII Всероссийская научно-практическая конференция

Похожие:

Реализация метода генерации параметров эллиптических кривых на основе алгоритма подсчёта количества точек iconН. В. Медведев, С. С. Титов Почти-пороговые схемы разделения секрета на эллиптических кривых
Работа посвящена исследованию схем разделения секрета при помощи многочленов на эллиптических кривых. Изучены структуры доступа и...
Реализация метода генерации параметров эллиптических кривых на основе алгоритма подсчёта количества точек iconПодход к построению нечеткого параллельного генетического алгоритма
Предложен нечеткий адаптивный подход подстройки параметров параллельного генетического алгоритма для повышения вероятности нахождения...
Реализация метода генерации параметров эллиптических кривых на основе алгоритма подсчёта количества точек iconУдк 519. 688 Параллельная реализация генетического алгоритма оптимизации в гидрологических моделях трансформации стока
В работе для восстановления параметров классической модели трансформации речного стока по данным наблюдений применен генетический...
Реализация метода генерации параметров эллиптических кривых на основе алгоритма подсчёта количества точек iconРазработка и применение численного метода решения линейных эллиптических уравнений в неограниченной области
В трехмерном случае метод требует действий. Приведены результаты тестовых расчетов, подтверждающие эффективность метода
Реализация метода генерации параметров эллиптических кривых на основе алгоритма подсчёта количества точек iconПрограмма «Enrollment for Education Solutions»
Ным заведениям покрыть лицензиями весь парк пк в рамках единого соглашения на подписку. Она обеспечивает такие возможности, как лицензирование...
Реализация метода генерации параметров эллиптических кривых на основе алгоритма подсчёта количества точек iconКонтроллер промышленный комбинированный (кпк) гамма-11
Понятие данных, параметров настройки, исполняемого алгоритма, данных и параметров настройки алгоритма кпк
Реализация метода генерации параметров эллиптических кривых на основе алгоритма подсчёта количества точек iconЭцп на основе эллиптических кривых над полем
Сша и Западной Европе – ecdsa, в России – гост р 34. 10-2001. Однако, стоит отметить тот факт, что в стандартах ecdsa и гост р 34....
Реализация метода генерации параметров эллиптических кривых на основе алгоритма подсчёта количества точек iconСопрягаемые со вторичными приведенными формами пуанкаре
Система уравнений диофанта-ферма, пифагора и эллиптических кривых имеет вычисляемые решения
Реализация метода генерации параметров эллиптических кривых на основе алгоритма подсчёта количества точек icon§ 26. Уравнения некоторых кривых, встречающихся в математике и её приложениях 701
Составить уравнение геометрического места точек, произ­ведение расстояний которых до двух данных точек F1 (— с; 0) и
Реализация метода генерации параметров эллиптических кривых на основе алгоритма подсчёта количества точек iconАнализ стойкости метода коха-жао стеганографического встраивания информации в статические изображения
Рассмотрен метод стеганографического встраивания информации Коха-Жао. В статье проведен анализ стойкости данного метода к jpeg-компрессии...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org