BC/NW 2006, №1, (8) : 16.6

Ускорение преобразований в группах точек эллиптической кривой, путем развития метода использования смешанных систем координат

М.М. Кошлак, Ю.Н. Мельников

(Москва, Московский энергетический институт (технический университет), Россия)

Криптосистемы цифровой подписи на основе эллиптических кривых (ЭК) с длиной ключа 160 бит имеют одинаковую стойкость с криптосистемами DSA и Эль-Гамаля с длиной ключа 1024 бита. Очевидно, что в ближайшем будущем данные системы займут доминирующее положение в криптографии с открытым ключом. По этой причине криптосистемы на ЭК обсуждались в ISO/IEC CD 14883-3, ISO/IEC DIS 11770-3, ANSI ASC X.9.63, X.9.62, IEEE p1363, ГОСТ-34.2001 РФ и NESSIE и в настоящее время получили развитие.

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

· Использование специфических кривых, в которых доступно комплексное умножение;

· Использование различных базисов представления элементов поля для . Полиномиальное представление эффективней при программной реализации преобразований на ЭК, а нормальный базис Гауса предпочтительней при аппаратной реализации;

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

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

Первый фактор – это характеристика поля, над которым определена кривая. Здесь мы можем выбирать оптимальные поля с точки зрения, например, операции обращения в данном поле.

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

Третий метод – использование, при умножении точки на число, смешанных координат. То есть использование представлений точки кривой в различных системах координат, что позволяет производить такие действия как удвоение или сложение точек, избегая операции, инвертирования в полях больших простых чисел, для достижения наилучшего быстродействия.

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

Литература

1. Болотов А.А., Гашков С.Б., Фролов А.В., Часовских А.А. Алгоритмические основы эллиптической криптографии - Москва: МЭИ. 2000. 100с.

2. Математические и компьютерные основы криптологии: Учеб. пособие / Ю. С. Харин, В. И. Берник, Г. В. Матвеев, С. В. Агиевич. – Мн.: Новое знание, 2003. – 382 с.

3. Молдовян Н. А., Молдовян А. А., Еремеев М. А. Криптография: от примитивов к синтезу алгоритмов. – СПб.: БХВ-Петербург, 2004. – 448 с.: ил.