BC/NW 2009; №2 (15):11

BC/NW 2009; №2 (15):11.6

ФУНКЦИИ СПАРИВАНИЯ В БИБЛИОТЕКЕ КЛАССОВ ДЛЯ ЭЛЛИПТИЧЕСКОЙ КРИПТОГРАФИИ

Болдырев А.Г., Фролов А.Б.

(ГОУВПО «Московский энергетический институт (технический университет)», Россия)

Работа выполнена при поддержке РФФИ, проект 08-01-00632а

Отображение спаривания использовалось ранее для сведения задачи дискретного логарифмирования в группе точек эллиптической кривой к аналогичной задаче в мультипликативной группе конечного поля [1]. В 2000 г. вышла работа [2], открывшая новый класс криптографических протоколов - протоколов, основанных на спаривании, не имеющих аналогов в классе протоколов, основанных на свойствах мультипликативной группы конечного поля. В настоящей работе рассматриваются отображения спаривания в соответствии с их систематизацией в монографиях [3,4] и ряд алгоритмов спаривания, реализованных в разработанной с участием авторов библиотеки классов эллиптической криптографии.

Эллиптические кривые. Спаривание Вейля [3,4]. Уравнение в форме Вейерштрасса эллиптической кривой E над конечным полем F_q, где q - степень простого числа, имеет вид:

E: Y²+a₁XY+ a₃Y=X³ + a₂X³+ a₄X+ a₆,

где коэффициенты являются элементами поля F_q . На множестве точек этой кривой, дополненном точкой O, называемой точкой в бесконечности, определяется операция сложения, обладающая свойствами операции абелевой группы. Порядок |E(F_q)| этой группы выражается формулой |E(F_q)|=q+1-t, где t - так называемый след Фробениуса. По теореме Хассе |t| £ 2Öq. Кривая E называется суперсингулярной, если след Фробениуса t кратен характеристике p поля F_q. Для вычисления порядка таких кривых известны замкнутые формулы. В теории спаривания E[n] обозначают множество точек n-кручения кривой E(), где - замыкание поля F. Наименьшее число k такое, что E[n]ÍE(F^k) называется множителем вложения, или множителем безопасности. Известно, что E[n] есть подгруппа группы E(F^k) и что ее структура изоморфна структуре прямой суммы Z_n Å Z_n . Обозначают E[n](E(F)) подгруппу группы E[n], являющуюся подгруппой группы E(F_q). Обозначим m_n подгруппу корней n‑ой степени из единицы группы (F_q^k)^*. Спариванием Вейля называется отображение e:E[n]´ E[n]® m_n, обладающее свойствами

билинейности:

e(S,T₁+T₂)=e(S,T₁)e(S,T₂); e(S₁+S₂,T)=e(S₁,T)e(S₂,T);

невырожденности :

"S $Q e(S,Q)¹1

и альтернированности:

"P e(P,P)=1.

Дивизором D на E называется формальная сумма D=Sn_P(P), n_PÎZ. Множество ненулевых коэффициентов n_P дивизора называется его носителем. Главным называется дивизор вида (f)= Sord f(P), где f есть рациональная функция на E, ord f (P) есть кратность функции f в точке P, n_P>0. если P является нулем и n_P <0, если P есть полюс. Дивизоры D и D’ эквивалентны, если D-D’ есть главный дивизор. Известно, что дивизор D=Sn_P(P) является главным тогда и только тогда, когда Sn_P=0 и Sn_PP =O. Главными являются дивизоры n(D_P^T)=(f_P^T)=n(P)-n(O) и n(D_P)=n(f_P)=n(P+R) - n(R). Для всякой рациональной функции f и дивизора D=Sn_P(P) с носителем, не пересекающимся с носителем дивизора (f) определена функция f(D)=Pf(P)ⁿ_P, где перемножаемые элементы поля определяются носителем дивизора D.

По алгоритму Миллера значение функции f_P(S) в точке S в зависимости от вида дивизора (f_P) и принадлежности точки P группе E[n](E(F)) определяется следующим образом.

Используются следующие рациональные функции на E:

g_P_,_Q(X) = l - Y+lX - функция такая, что l-Y+lX=0 - уравнение линии, проходящей через точки P и Q;

g_P_,_P(X) = l - Y+lX - функция такая, что l-Y+lX=0 - уравнение касательной в точке P;

g_Q(X)=X - a - функция такая, что X - a=0 - уравнение вертикальной линии, проходящей через точку Q=(a,b).

Алгоритм 1 (для точки).

Число n представляется в двоичном коде

n=(1,b_t_-₁, …, b_j, …, b₀), b_t=1, b_jÎ{0,1}.

Принимаем f₁=g_P₊_R/g_P_,_R в случае (f_P)=D_P ,

и f₁=1 в случае (f_P)=D_P^T; Z=P.

Для j=t-1,…, 0

полагаем f=f² g_Z_,_Z(S)/g₂_Z(S), Z=2Z

(шаг удвоения в E[n](E(F)), если PÎE[n](E(F)), иначе в E[n]);

если b_j=1, то полагаем

f=f₁ f g_Z_,_P(S)/g_Z₊_P(S), Z=Z+P

(сложение в E[n](E(F)), если PÎE[n](E(F)), иначе в E[n]).

Возвращаемое значение есть f=f_P(S)ÎF^k^* или 0.

С целью сокращения медленных операций деления используют алгоритм вычисления точки с отложенными операциями деления, возвращающий числитель N и знаменатель D такие, что f_P(S)=N/D.

Алгоритм 2 (для точки). Число n представляется в двоичном коде

n=(1,b_t_-₁, …, b_j, …, b₀), b_t=1, b_jÎ{0,1}.

Принимаем N₁=g_P₊_R, D₁=g_P_,_R в случае (f_P)=D_P ,

и f₁=1 в случае (f_P)=D_P^T; N=1; D=1; Z=P.

Для j=t-1,…, 0

полагаем N=N² g_Z_,_Z(S); D=g₂_Z(S), Z=2Z

(шаг удвоения в E[n](E(F)), если PÎE[n](E(F)), иначе в E[n]);

если b_j=1, то полагаем

N=N₁ N g_Z_,_P(S); D=g_Z₊_P(S); Z=Z+P.

(сложение в E[n](E(F)), если PÎE[n](E(F)), иначе в E[n]).

Возвращаемые значения суть N, DÎF^k^* или 0.

Примечание. Если в процессе вычислений по алгоритму 1 или 2 некоторая функции g принимает значение 0, то вычисления прерываются и возвращается значение 0.

Спаривание Вейля определяется формулой

e(P,Q)=[f_P(D_Q)/f_Q(D_P)]^⁽^q^{^}^k^-^1)/ⁿ,

где D_P=(P+R₁) -(R₁); D_Q=(P+R₂) -(R₂).

Его можно вычислить, четырежды применяя алгоритм 1 или 2 для точки к соответствующим точкам дивизоров (D_P) и (D_Q):

Алгоритм 1 (основной вариант алгоритма спаривания Вейля):

e(P,Q)= f_P(Q+R₂) f_Q(R₁)/f_Q(P+R₁) f_P(R₂). (1)

Алгоритм 2 (совмещенный вариант алгоритма спаривания Вейля) отличается от предыдущего тем, что циклы четырех исполнений алгоритма 1 для точки совмещаются, чем экономятся операции возведения в квадрат и умножения.

Алгоритм 3 (вариант с отложенными делениями) отличается от предыдущего тем, что в каждом цикле с использованием алгоритма 2 для точки также совмещенным образом вычисляются отдельно числители и знаменатели, а деление их заключительных версий осуществляется непосредственно перед завершением алгоритма, чем существенно сокращается (до одного) количество делений в конечном поле.

Последующие варианты (алгоритм 4 и алгоритм 5) вычисления спаривания Вейля предполагают разложение числа n в системе счисления по основанию 4 или 3 (т.н. тернарный алгоритм).

Примечание. Алгоритмы 1 - 5 спаривания Вейля возвращают значение 0, если это значение возникает при вычислении значение некоторой функции g. Поэтому они используются в качестве тела цикла

Пока e=0, выбрать случайно точки R₁ и R₂ и вычислить e=e(P,Q). Перед циклом инициализируется значение e=0. По окончании цикла вернуть e⁽^q^{^}^k^-^1)/ⁿ.

Спаривание Тейта. Спаривание Тейта это билинейное невырожденное альтернированное отображение

e_T : E[n](E(F))´ E[n](E(F^k))®m_n.

Оно вычисляется по формуле f_P(D(Q)), где (f_P)=D_P^T=(P)-(O), D(Q)=(Q+R)-(R):

e_T (P,Q)= [f_P(D_Q)]^{(q^k}^-^1)/n

Алгоритмы вычисления спаривания Тейта аналогичны рассмотренным выше алгоритмам 1 - 5 вычисления спаривания Вейля и отличаются от них тем, что исключены операции, связанные с «обработкой» знаменателя формулы (1), функция f₁=1, операции удвоения точки и сложения точек в каждой итерации цикла осуществляются в группе Е[n](E(F)). Обозначим эти алгоритмы алгоритм 1_T , …, алгоритм 5_T .

Искажающие отображения. Неальтернированные спаривания. Рассмотренные выше отображения спаривания являются альтернированными, что не позволяет применить их в криптографических протоколах, основанных на спаривании. Отображение спаривания, используемое в них, билинейное, невырожденное и неальтернированное. Использование так называемых искажающих отображений [5] y:E[n](E(F^k))®E[n](E(F^k)) и y:E[n](E(F))®E[n](E(F^k)) позволяет построить на основе спаривания Вейля и спаривания Тейта соответственно неальтернированные спаривания Вейля : E[n](E(F))´E[n](E(F))®m_n;
=e(P,y(Q)) и Тейта _T: E[n] (E(F))´E[n] (E(F))®m_n; _T = e_T(P, y(Q)). Ниже такие спаривания называются модифицированными. При вычислении модифицированного спаривания как Вейля, так и Тейта используются дивизоры D_P^T и D_Q^T, что упрощает алгоритмы. Во всех случаях f₁=1. Основной алгоритм вычисления модифицированного спаривания Вейля (алгоритм 1м) соответствует формуле

(P,Q)==[f_P(D_y_(Q)^T)/f_y_(Q)[D_P^T)]^{(q^k}^-^1)/n)=

=[f_P(y(Q))f_y_(Q)(O) / f_y_(Q)(P)f_P(y(O))]^{(q^k}^-^1)/n) ,

а для суперсингулярных кривых

E_1,0: Y²=X³+X, где pº3(mod 4),

E_2,_b: Y²+Y=X³+X+b, bÎ{0,1}, над полем GF(2^m), при нечетном m,

E_3,_b: Y²=X³ - X+b, bÎ{-1,1}, над полем GF(3^m), при mº±1(mod 12) или mº±6(mod 12)

он соответствует формуле

(P,Q)=[f_P(y(Q))f_{y (}_Q)(O) / f_y(_Q)(P)]⁽^q^{^}^k^-^1)/ⁿ⁾.

Здесь учтено, что f_P(y(O))⁽^q^{^}^k^-^1)/ⁿ=1.

При этом значения функций f_P(S) и f_y(_Q)(S) в соответствующей точке вычисляются по алгоритму 1,

Алгоритмы 2м - 5м вычисления модифицированного спаривания Вейля отличаются от алгоритма 1м так же, как алгоритмы 2 - 5 вычисления спаривания Вейля отличаются от алгоритма 1.

Алгоритмы вычисления модифицированного спаривания Тейта соответствуют формуле

e_T(P,y(Q))=f_P(D_Q^T)⁽^q^{^}^k^-^1)/ⁿ=(f_P(y(Q))/f_P (y(O)))⁽^q^{^}^k^-^1)/ⁿ, а для суперсингулярных кривых

E_i_,_b, i=1,2,3, bÎ{0,1} при i=1,2, bÎ{-1,1} при 1=3 они соответствуют формуле _T(P,Q)=f_P(y(Q))⁽^q^{^}^k^-^1)/ⁿ. Она получается из предыдущей формулы, поскольку f_P(y(O))⁽^q^{^}^k^-^1)/ⁿ=1. Таким образом, вычисление модифицированного спаривания Тейта на указанных суперсингулярных кривых сводится к вычислению значения функции f_P, такой, что (f_P)=nD_P^T, в точке y(Q) и осуществляется по алгоритму 1 для точки, вычисление с отложенными делениями осуществляется по алгоритму 2 для точки.

Алгоритмы Дуурсма - Ли - Квона. Существенное упрощение модифицированных алгоритмов спаривания Тейта на суперсингулярных эллиптических кривых с распространением на гиперэллиптические кривые достигнуто в работах [6 -8]. Применительно к эллиптическим кривым E_3,_b известны три алгоритма Дуурсма-Ли-Квона: базовый, ускоренный и алгоритм без извлечения кубических корней [7,8]. В работе [8] укоренный алгоритм и алгоритм без извлечения квадратных корней обоснованы для кривых E_2,_b. Описания этих алгоритмов можно найти в книге [4].

Функции спаривания библиотеки MPEIAAL. В библиотеку MPEIAAL [9] включены следующие функции.

а) millerf_function_for_point_1_GF(p)(T) - вычисление значения f_n(S) по алгоритму 1 для точки (T=0: (f_n)=(P+R)-(R); T=1: (f_n)=(P)-(O)). Вычисления на E[n](F), если PÎE[n] и на E[n](F^k), если PÎ E[n](F^k). Вход: E, n, k, P, Q. Выход: e(P,Q) Î F^k, F=GF(p);

millerf_function_for_point_1_GF(2^m)(T) и

millerf_function_for_point_1_GF(3^m)(T) - аналогичные функции применительно к эллиптическим кривым над полями GF(2^m) и GF(3^m).

б) millerf_function_for_point_2_GF(p) (T) - вычисление значения f_n(S) по алгоритму 1 для точки (T=0: (f_n)=(P+R) - (R); T=1: (f_n)=(P)-(O)). Вычисления на E[n](F), если PÎE[n] и на E[n](F^k), если PÎ E[n](F^k). Вход: E, n, k, P, Q. Выход: N, D такие, что e(P,Q) Î F^k, F=GF(p).

millerf_function_for_point_2_GF(2^m) (T) и

millerf_function_for_point_2_GF(3^m) (T) - аналогичные функции применительно к эллиптическим кривым над полями GF(2^m) и GF(3^m).

в) weil_pairing_general (i)_GF(p), weil_pairing_general (i)_GF(2^m), weil_pairing_general (i)_GF(3^m) - вычисление спаривания Вейля по алгоритму i (i=1-5) на эллиптических кривых над полями GF(p²), GF(2⁴^m), GF(3⁶^m).

г) tate_pairing_general (i)_GF(p), tate_pairing_general (i)_GF(2^m), tate_pairing_general (i)_GF(3^m), - вычисление спаривания Тейта по алгоритму i_T(i=1-5) - на эллиптических кривых над полями GF(p²), GF(2⁴^m), GF(3⁶^m).

д) weil_pairing_morif_general (i)_GF(p), weil_pairing_morif _general (i)_GF(2^m), weil_pairing_morif _general (i)_GF(3^m) - вычисление модифицированного спаривания Вейля по алгоритму i_м (i=1-5) на эллиптических кривых над полями GF(p²), GF(2⁴^m), GF(3⁶^m).

e) weil_pairing_morif (i)_GF(p), weil_pairing_morif (i)_GF(2^m), weil_pairing_morif (i)_GF(3^m) - вычисление модифицированного спаривания Тейта на эллиптических суперсингулярных кривых над полями GF(p²), GF(2⁴^m), GF(3⁶^m).

ж) tate_pairing_morif_general (i)_GF(p), tate_pairing_morif _general (i)_GF(2^m), tate_pairing_morif _general (i)_GF(3^m) - вычисление модифицированного спаривания Тейта по алгоритму i_м (i=1-5) на эллиптических кривых над полями GF(p²), GF(2⁴^m), GF(3⁶^m).

з) tate_pairing_morif (i)_GF(p), tate_pairing_morif (i)_GF(2^m), tate_pairing_morif (i)_GF(3^m) - вычисление модифицированного спаривания Тейта на эллиптических суперсингулярных кривых над полями GF(p²), GF(2⁴^m), GF(3⁶^m).

ж) tate_pairing_duursma-lee_general (i)_GF(3^m), - вычисление модифицированного спаривания Тейта по базовому алгоритму Дурсма - Ли на эллиптических кривых над полем GF(3^m).

з) tate_pairing_duursma-lee_accellerated (i)_GF(3^m), - вычисление модифицированного спаривания Тейта по ускоренному алгоритму Дурсма - Ли на эллиптических кривых над полем GF(3^m).

и) tate_pairing_duursma-lee_kwon (i)_GF(3^m), - вычисление модифицированного спаривания Тейта по алгоритму Дурсма - Ли - Квона без извлечения кубических корней на эллиптических кривых над полем GF(3^m).

к) tate_pairing_duursma-lee_accellerated (i)_GF(2^m), - вычисление модифицированного спаривания Тейта по ускоренному алгоритму Дурсма - Ли - Квона на эллиптических кривых над полем GF(2^m).

л) tate_pairing_duursma-lee_kwon (i)_GF(2^m), - вычисление модифицированного спаривания Тейта по алгоритму Дурсма - Ли - Квона без извлечения квадратных корней на эллиптических кривых над полем GF(2^m).

Заключение. С включением в библиотеку MPEIAAL описанных в настоящей статье функций, она может использоваться для реализации разнообразных протоколов, основанных на спаривании. Такими протоколами являются, в частности, протоколы согласования ключей для симметричных систем шифрования [2], шифрования с личностным ключом [10], короткой цифровой подписи [11], слепой цифровой подписи [12], цифровой подписи с личностным ключом [13] и др. При этом возможен сравнительный анализ эффективности их реализации в зависимости от выбора способов реализации спаривания, конечных полей и эллиптических кривых.

Авторы выражают благодарность д.ф.-м.н. профессору Гашкову С.Б. за помощь при подготовке настоящей работы.

Литература

1. Okamoto T., Pointsheval P. The Gap Problems: a new class of problems for the security of cryptographic primitives, PKC 2001, LNCS 1992(2001), 104-118.

2. Joux A. One round protocol for tripartite Diffie-Hellman. Lecture Notes in Computer Science 1838 (2000) 385-393.

3. Болотов А.А., Гашков С.Б., Фролов А.Б., Часовских А.А. Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы. - М.: КомКнига, 2006.

4. Болотов А.А., Гашков С.Б., Фролов А.Б. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. - М.: КомКнига, 2006.

5. Verheul E. Evidence that XTR is more secure than supersingular ellipticcurve cryptosystems J.Cryptology, 17(2004), 277-296.

6. Barreto P.S.M.L., Galbraith S., O hEigeartaigh C., and Scott M. Efficient pairing computation on supersingular abelian varieties Cryptology ePrint Archive, Report 2004/375, 2004.

7. Duursma I. and Lee H.-S. Tate pairing implementation for hyperelliptic curves y^2=x^p-x+d. Asiacrypt-2003, LNCS2894(2003), 111-123.

8. Kwon S. Efficient Tate pairing computation for supersingular elliptic curves over binary fields Cryptology ePrint Archive, Report 2004/303, 2004.

9. Белова А.Ю., Мамонтов А.И., Морозов С.В. Библиотека классов для эллиптической криптографии, 17-я Международная Научно-техническая конференция "Информационные средства и технологии". Москва, 2009. В наст. томе.

10. Boneh D., Franklin M. Identity Based encription from the Weil Pairing //SIAM J. on Computing. 2003. 32, 586-615.

11. Boheh D. Short signatures from Weil pairing/Boneh D., Lynn B., and Shacham H.// J. of Cryptology, vol 7, (2004) 297-319.

12. Boldyreva A. Efficient Thrishold Signatere, Multisignature and Blind Signature Schemes Based on the Gap-Gaffie-Hellman-Group Signature Scheme/ A.Boldyreva // PKC 2003, LNCS2139, Springer-Verlag, (2003) 31-46,

13. Hess F. Exponent group signature schemes and efficient identity based signature schemes based on pairings/F. Hess//Cryptology ePrint Archive, Report 2002/012.