Е. Б. МАХОВЕНКО
Санкт-Петербургский государственный политехнический университет
АЛГОРИТМЫ ГЕНЕРАЦИИ ПАРАМЕТРОВ
КРИПТОСИСТЕМ НА БИЛИНЕЙНЫХ ОТОБРАЖЕНИЯХ
Рассматривается возможность генерации эллиптических кривых для криптосистем на билинейных отображениях, параметры которых удовлетворяют требованиям российского стандарта электронной цифровой подписи ГОСТ Р 34.10-2001.
Протоколы цифровой подписи на билинейных отображениях эллиптических кривых (личностные протоколы цифровой подписи [1, 2], протоколы короткой цифровой подписи [3] и т. п.) находят все большее применение. Одним из факторов, затрудняющих использование таких протоколов, является проблема генерации эллиптических кривых, «удобных» для реализации спариваний и таких, чтобы стойкость соответствующих протоколов подписи была не ниже стойкости, предусмотренной российским стандартом цифровой подписи ГОСТ Р 34.10-2001.
Параметрами, определяющими возможность использования эллиптической кривой для построения протоколов на билинейных отображениях, являются отношение g=(log p)/(log r), где p – характеристика поля, r – порядок циклической подгруппы группы точек, и так называемый параметр безопасности k – степень расширения поля характеристики p. Если g принимает значение 1, то кривая имеет простой порядок группы точек и может быть использована для реализации протоколов короткой подписи. Групповые операции на такой кривой могут быть реализованы наиболее эффективно. При g=2 этот протокол не имеет преимущества по длине подписи перед классическими протоколами на эллиптических кривых (такими как ГОСТ 34.10-2001). Отношение g кривых с малым параметром безопасности k (31<k<100), полученных неспециальными методами, имеет тенденцию принимать значение около 2.
Анализ существующих методов генерации эллиптических кривых показал, что метод Комута-Кавазоэ-Такахаши [4] дает порядка 2^10 различных эллиптических кривых, удовлетворяющих требованиям ГОСТ Р 34.10-2001 и имеющим значение параметра g, близкое к 1,9. Такие кривые могут применяться в протоколах обмена ключами, для создания электронных монет и т. п. Однако эффективность реализации таких протоколов достаточно низкая. Помимо основного множества кривых, метод Комута-Кавазоэ-Такахаши дает класс кривых со значением g=1,18, допускающий формирование короткой цифровой подписи, длина которой составит не менее 301 бита.
Наибольшее множество кривых, а также свободу выбора параметра k и дискриминанта D дает метод Кокса-Пинча [5]. Этот метод позволяет выбирать значение k специального вида, например 2i3j (в том числе наименьшее допустимое ГОСТ 34.10-2001 значение, равное 32) и использовать известные методы оптимизации вычисления спариваний на основе «башни» расширений небольших степеней. Выбор больших значений дискриминанта позволяет вырабатывать классы кривых с фиксированными p и r и различными инвариантами. В отличие от метода Комута-Кавазоэ-Такахаши, данный метод дает возможность выбирать небольшие дискриминанты D (длиной меньше 21 бит), что позволяет более эффективно вычислять инварианты и генерировать эллиптические кривые. Кроме того, метод Кокса-Пинча позволяет генерировать кривые, имеющие порядок группы с малым весом, что позволяет значительно сократить число сложений точек при вычислении билинейного отображения. Кроме того, если значение r задано полиномом r(x), то выбор аргумента x с малым весом Хэмминга часто дает значение r(x) также с малым весом [6].
На основе этих методов с учетом требований ГОСТ 34.10-2001 разработаны алгоритмы генерации кривых.
При ослаблении требований к минимальному значению k (при уменьшении значения k до 21, как в стандарте ECDSS) рассмотренные методы позволяют генерировать большое число кривых с отношением g<1,3. Такие кривые могут быть использованы, в частности, для реализации протоколов укороченной цифровой подписи. Кроме того, при увеличении размера задачи до 512 бит появляется возможность генерировать большое число кривых с «удобными» значениями k>31.
Список литературы
1. Cha J. C., Cheon J. H. An identity-based signature from gap Diffie-Hellman groups // Practice and Theory in Public Key Cryptography. PKC 2003. LNCS. Springer-Verlag, 2003. Vol. 2567. P. 1830.
2. Paterson K. G. ID-based signatures from pairings on elliptic curves // Cryptology ePrint archive. Report 2002/0http://eprint. iacr. org.
3. Boneh D., Lynn B., Shacham H. Short signatures from the Weil pairing // Proceedings of Asiacrypt 2001. LNCS. Springer-Verlag, 2001. Vol. 2248. P. 514–532.
uta A., Kawazoe M., Takahashi T. How to construct pairing-friendly curves for the embedding degree k = 2n, n is odd prime. // http://citeseer. ist. psu. edu/761770.html.
5. Cocks C. and Pinch R. G. E. Identity-based cryptosystems based on the Weil pairing. // unpublished manuscript, 2001.
6. Freeman D., Scott M., Teske E. A taxonomy of pairing-friendly elliptic curves // Cryptology ePrint Archive: Report 2006/372.
