Обзор эффективных алгоритмов подсчета числа точек якобиана гиперэллиптической кривой над конечным полем

УДК 511.48:519.61

И. Д. Ильяшенко

ОБЗОР ЭФФЕКТИВНЫХ АЛГОРИТМОВ ПОДСЧЕТА ЧИСЛА ТОЧЕК ЯКОБИАНА ГИПЕРЭЛЛИПТИЧЕСКОЙ КРИВОЙ НАД КОНЕЧНЫМ ПОЛЕМ

Рассмотрены различные алгоритмы нахождения порядка якобиана, их область применения и эффективность.

Various algorithms for finding of the order of Jacobian, their range of use and efficiency are considered.

Ключевые слова: гиперэллиптическая кривая, якобиан, подсчет точек, дискретный логарифм.

Key words: hyperelliptic curve, Jacobian, point counting, discrete logarithm.

Пусть p — простое число, Fq — конечное поле, где q = pl . C — гиперэллиптическая кривая рода

g, определенная над полем Fq вида у2 = f(x), гдеf(x) — многочлен степени 2g + 1 в Fq (x).

Пусть JC — якобиан кривой C, а Jc (Fq) — группа рациональных точек якобиана, а %(t) —

характеристический многочлен эндоморфизма Фробениуса кривой C, тогда # Jc (Fq) = х(1),

поэтому задачу отыскания порядка якобиана можно свести к нахождению %(t).

В случае кривой рода 2

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

Колм О'Хегертэй сравнил [1] методы подсчета точек якобиана гиперэллиптических кривых над простыми полями и полями характеристики 2. Он сравнил время работы этих алгоритмов и определил их практическое применение для различных характеристик полей. Для полей характеристики 2 О'Хегертэй рассмотрел два алгоритма.

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

Алгоритм Сакая — Сакурая позволяет вычислять порядок якобиана для кривых произвольного рода над полями малых характеристик. Этот алгоритм является рекурсивным и сводится к нахождению порядка якобиана над полями меньшего размера.

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

Для кривых над простыми полями О'Хегертэй привел алгоритмы Хассе — Витта, Фурукавы — Кавазо — Такахаши и Коблица.

Алгоритм Хассе — Витта. Данный алгоритм возводит многочлен Дх) из уравнения кривой в степень (р - 1)/2, где р — характеристика поля (причем 64 < р < 100 000, то есть применение данного поля в криптографии небезопасно). Коэффициенты полученного многочлена являются начальными значениями для рекурсивной функции, которая в итоге находит числа в1 и э2 для формулы (2).

Алгоритм Фурукавы, Кавазо и Такахаши также рекурсивен, но требует вместо возведения в степень нахождения а є Бр, не являющегося квадратичным вычетом, и числа с = 1(шод р) из

р = с2 + 2й2, где й — целое.

Xq(t) = t4 — sa t3 + s212 — stqt + q2, где Sj eZ, |Sl| sS 4Jq , |s2| ^ 6q. Тогда

# jc (Fq) = q2 + 1 — s1(q + 1) + s2.

Вестник Российского государственного университета им. И. Канта. 20l0. Вып. l0. С. l08—lll.

" 'п ^

Алгоритм Коблица применим для кривых вида у + у = хп, п = 2£ + 1, р = 1(шод п), где g — род кривой. Для подсчета точек здесь используют суммы Якоби вида ]Т (х, х) = ^ х(і)х(1 - і), причем

ієБ г

р

вся сложность алгоритма сводится именно к нахождению этих сумм. Алгоритм Коблица по скорости сравним с алгоритмом Фукуравы, Кавазо, Такахаши.

А если поле произвольно и наша криптосистема работает с определенным типом кривых?

Кавазо, Такахаши и Фурукава рассмотрели в [3] семейство гиперэллиптических кривых у2 = х5 + ах над большим конечным полем . Основная идея алгоритма такова. Для данных кривых характеристический многочлен Фробениуса имеет вид (1). Значения в1, в2 ограничены: |"2^ |в1|-2Ц ] ^ в2 ^ ^q+l+(NC|(g)-(q+l))/g + 2q^. Пусть ц = р — простое, причем р > 64. Тогда,

чтобы найти в1, в2, необходимо рассмотреть максимум три возможных значения в2, найти для них число точек и проверить умножением на произвольную точку якобиана.

Позднее Ханеда, Кавазо, Такахаши расширили рассматриваемое семейство до

гиперэллиптических кривых у2 = х2к+1 + ах, предложив эффективный алгоритм вычисления порядка якобиана при помощи сумм якобстала фк г (а) = ^ Х2(хк+1 + ах), где а є Бр, г = 1, ..., g, х2

хєБ г

— элемент порядка 2 поля БрГ. Число рациональных точек кривой над полем БрГ при этом равно |С(БрГ)| = рг +1 + Фкг(а). Тогда находим характеристический многочлен Фробениуса из условия

2 £ 2£

Хі(і) = П(і - аі), тогда |С(Б г)| = рг +1 + ^аг . С помощью данного алгоритма авторы выделяют і=1 р і=1

наиболее приемлемые для безопасности конечные поля и соответствующие порядки якобианов.

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

С. Халоуи показала в [4] верхние и нижние возможные границы для числа рациональных точек абелевых многообразий и якобианов. Если задано конечное поле ^ размерности £, то для

абелевого многообразия А: (с/ + 1 - 2^):‘- < #А(Р ) < (с/ + 1 + 2^)8. Для якобианов всевозможнъгх кривых над полем ^ это так же применимо, причем ІЧІ£) 5 < (с] + '^+(Nq(g)-(q + Ї))/g)g, где Ыч($) — максимальное число точек, которое может содержать кривая в Б?. Также для якобианов приведена асимптотическая оценка при росте размерности £: ц

На смену криптографии с использованием спаривания Вейля на эллиптических кривых приходит спаривание на якобианах гиперэллиптических кривых. Для того чтобы осуществить это спаривание, Кристиан Равншой в [5 — 7] предложил вероятностный алгоритм нахождения образующих группы кручения якобиана гиперэллиптической кривой рода 2 над конечным полем Б?. Для этого автор использует спаривание Тейта и «диагонализацию» множества случайно

выбранных точек (Рі, ., Р4, Q1, ., Q4} якобиана с использованием эндоморфизма Фробениуса. Тем самым автор касается нахождения подходящих для криптографии гиперэллиптических кривых, то есть кривых, якобианы которых содержат большие циклические подгруппы.

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

Рассмотрим понятие «обобщенного» якобиана, упоминаемое Изабель Дешен [8; 9]. Это некоторая алгебраическая группа гиперэллиптической кривой. Она является обобщением таких структур, как якобиан и тор. «Обобщенный» якобиан аналогичен обычному, но вместо линейного отношения эквивалентности между дивизорами вводят специальное О ~т V, если 3/ є К(С) ,

, Ш

такой, что (f = D - D' и f = 1(mod m), где C — некоторая кривая над конечным алгебраически

замкнутым полем K, а m — положительный дивизор.

Элементы данной группы можно представить в виде пары (k, P), где k е Gm, P е C . Для такого представления описан групповой закон.

«Обобщенные» якобианы обладают полезными свойствами как обычных якобианов (маленький размер ключа), так и торов (компактное представление элементов). Однако решение проблемы дискретного логарифма здесь остается не менее сложной задачей, чем на самой кривой или в конечном поле. Гэлбрэйт и Смит показали, что данная проблема является и не более сложной [10]. Эффективный алгоритм решения проблемы дискретного алгоритма в якобиане гиперэллиптической кривой рассмотрен К. Нагао [11]. Он основан на работах Харли и Терьялу и использует множества гладких и почти гладких дивизоров относительно множества B сР, где

Р = (P | -P е Р). Генерируем множества гладких дивизоров, затем находим числа sv по модулю | Jq | такие, что ^svv = = 0(mod| Jq |, где v — почти гладкий дивизор. Подставляя значения в

V

-^svav /^sVPV(mod | Jq |), находим дискретный логарифм.

V V

Список литературы

1. Colm O hEigeartaigh. A comparison of point counting methods for hyperelliptic curves over prime fields and fields of characteristic 2 // Cryptology ePrint Archive. 2004.

2. Haneda M., Kawazoe M., Takahashi T. Suitable curves for genus-4 HCC over prime fields: point counting

formulae for hyperelliptic curves of type y2 = x2k+1 + ax // Ibid.

3. Furukawa E., Kawazoe M, Takahashi T. Counting points for hyperelliptic curves of type y2 = x5 + ax // Ibid. 2002.

4. Haloui S. The minimum and maximum number of rational points on jacobian surfaces over finite fields. URL: http://arxiv. org/abs/1002.3683.2010.

5. RaVnshoj C. R. Generators of Jacobians of genus two curves / / Cryptology ePrint Archive. 2008.

6. RaVnshoj C. R. Non-cyclic subgroups of Jacobians of genus two curves // Ibid.

7. RaVnshoj C. R. Non-cyclic subgroups of Jacobians of genus two curves with complex multiplication // Ibid.

8. Dechene I. Arithmetic of generalized Jacobians // Ibid. 2006.

9. Dechene I. On the security of generalized Jacobian cryptosystems // Ibid.

10. Galbraith S. D., Smith B. A. Discrete logarithms in generalized Jacobians / / Ibid.

11. Nagao K. Improvement of theriault algorithm of index calculus for Jacobian of hyperelliptic curves of small genus // Ibid. 2004.

Об авторе

Илья Дмитриевич Ильяшенко — студ., РГУ им. И. Канта, e-mail: tommplay@ googlemail. com.

Author

Ilya Ilyashenko — student, IKSUR, e-mail: tommplay@googlemail. com.