Гиперэллиптическая криптография: основы и особенности реализации

Введение

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

Определение

(Воображаемая) гипереллиптическая кривая рода *g* над полем *K* задается уравнением *y*2 = *f*(x), где *f* – многочлен степени не более 2*g* + 2, а *x* – мономический многочлен степени 2*g* + 2. Из этого определения следует, что эллиптические кривые являются гипереллиптическими кривыми рода 1. В криптографии на гипереллиптических кривых *K* часто является конечным полем. Якобиан кривой, обозначаемый *J*, является факторгруппой, таким образом, элементы Якобиана – это не точки, а классы эквивалентности делителей степени 0 относительно отношения линейной эквивалентности. Это согласуется со случаем эллиптической кривой, поскольку можно показать, что Якобиан эллиптической кривой изоморфен группе точек на эллиптической кривой. Использование гипереллиптических кривых в криптографии началось в 1989 году благодаря Нилу Коблицу. Хотя они были введены всего на 3 года позже ECC, немногие криптосистемы реализуют гипереллиптические кривые, поскольку реализация арифметики не так эффективна, как в криптосистемах, основанных на эллиптических кривых или факторизации (RSA). Эффективность реализации арифметики зависит от лежащего в основе конечного поля *K*; на практике конечные поля характеристики 2 оказываются хорошим выбором для аппаратных реализаций, в то время как программное обеспечение обычно быстрее для полей нечетной характеристики. Якобиан гипереллиптической кривой является абелевой группой и, как таковой, может служить группой для задачи дискретного логарифмирования (DLP). Вкратце, предположим, что у нас есть абелева группа *G* и элемент *a* из *G*. Задача DLP в *G* заключается в нахождении целого числа *x*, зная два элемента *G*, а именно *a* и *a*x. Первым типом группы, использованным для DLP, была мультипликативная группа конечного поля, позже также использовались Якобианы (гипер)эллиптических кривых. Если гипереллиптическая кривая выбрана с осторожностью, то метод Ро Поларда является наиболее эффективным способом решения DLP. Это означает, что если Якобиан имеет *n* элементов, то время работы алгоритма экспоненциально зависит от log *n*. Это позволяет использовать Якобианы относительно небольшого порядка, что повышает эффективность системы. Однако, если гипереллиптическая кривая выбрана неудачно, задача DLP станет довольно простой для решения. В этом случае существуют известные атаки, которые более эффективны, чем общие решатели дискретных логарифмов или даже субекспоненциальные алгоритмы. Следовательно, следует избегать таких гипереллиптических кривых. Учитывая различные атаки на DLP, можно перечислить характеристики гипереллиптических кривых, которых следует избегать.

An (imaginary) hyperelliptic curve of genus over a field is given by the equation where is a polynomial of degree not larger than and is a monic polynomial of degree From this definition it follows that elliptic curves are hyperelliptic curves of genus 1. In hyperelliptic curve cryptography is often a finite field. The Jacobian of , denoted , is a quotient group, thus the elements of the Jacobian are not points, they are equivalence classes of divisors of degree 0 under the relation of linear equivalence. This agrees with the elliptic curve case, because it can be shown that the Jacobian of an elliptic curve is isomorphic with the group of points on the elliptic curve. The use of hyperelliptic curves in cryptography came about in 1989 from Neal Koblitz. Although introduced only 3 years after ECC, not many cryptosystems implement hyperelliptic curves because the implementation of the arithmetic isn't as efficient as with cryptosystems based on elliptic curves or factoring (RSA). The efficiency of implementing the arithmetic depends on the underlying finite field , in practice it turns out that finite fields of characteristic 2 are a good choice for hardware implementations while software is usually faster in odd characteristic. The Jacobian on a hyperelliptic curve is an Abelian group and as such it can serve as group for the discrete logarithm problem (DLP). In short, suppose we have an Abelian group and an element of , the DLP on entails finding the integer given two elements of , namely and The first type of group used was the multiplicative group of a finite field, later also Jacobians of (hyper)elliptic curves were used. If the hyperelliptic curve is chosen with care, then Pollard's rho method is the most efficient way to solve DLP. This means that, if the Jacobian has elements, that the running time is exponential in This makes it possible to use Jacobians of a fairly small order, thus making the system more efficient. But if the hyperelliptic curve is chosen poorly, the DLP will become quite easy to solve. In this case there are known attacks which are more efficient than generic discrete logarithm solvers or even subexponential. Hence these hyperelliptic curves must be avoided. Considering various attacks on DLP, it is possible to list the features of hyperelliptic curves that should be avoided.

Атаки на DLP

Все общие атаки на задачу дискретного логарифмирования в конечных абелевых группах, такие как алгоритм Поллига — Хеллмана и метод Полларда ро, могут быть использованы для атаки на задачу дискретного логарифмирования (DLP) в якобиане гиперэллиптических кривых. Атака Поллига — Хеллмана снижает сложность DLP, рассматривая порядок группы, с которой мы работаем. Предположим, что используемая группа имеет *n* элементов, где *n* — произведение простых множителей. Алгоритм Поллига — Хеллмана сводит задачу DLP в группе порядка *n* к задачам DLP в подгруппах порядка *pi*, где *pi* — простые множители *n*. Таким образом, для *p* — наибольшего простого делителя *n*, задача DLP в группе порядка *n* столь же сложна, как и задача DLP в подгруппе порядка *p*. Следовательно, мы хотели бы выбрать *n* таким образом, чтобы наибольший простой делитель *p* числа *n* был почти равен самому *n*. Обычно достаточно требовать *n* быть степенью простого числа. Алгоритм вычисления индексов — это еще один алгоритм, который может быть использован для решения DLP при определенных обстоятельствах. Для якобианов (гипер)эллиптических кривых существует атака вычисления индексов на DLP. Если род кривой становится слишком большим, атака будет эффективнее метода Полларда ро. Сегодня известно, что даже род 8 не может обеспечить безопасность. Следовательно, у нас остаются эллиптические и гипереллиптические кривые рода 2. Еще одно ограничение на гипереллиптические кривые, которые мы можем использовать, связано с атакой Менезеса — Окамото — Ванстоуна / атакой Фрея — Рюка. Первая, часто называемая MOV, была разработана в 1993 году, вторая — в 1994 году. Рассмотрим (гипер)эллиптическую кривую *E* над конечным полем *Fq*, где *q* — степень простого числа *p*. Предположим, что якобиан кривой имеет *N* элементов и *p* — наибольший простой делитель *N*. Для *t* — наименьшего положительного целого числа, такого что существует вычислимый инъективный групповой гомоморфизм из подгруппы порядка *pt* группы *E(Fq)* в якобиан *J(E)*. Если *t* мало, мы можем решить DLP в *J(E)*, используя атаку вычисления индексов в *E(Fq)*. Для произвольных кривых *t* очень велико (порядка размера *N*); поэтому, хотя атака вычисления индексов достаточно быстра для мультипликативных групп конечных полей, эта атака не представляет угрозы для большинства кривых. Инъективная функция, используемая в этой атаке, является спариванием, и существуют некоторые приложения в криптографии, которые используют их. В таких приложениях важно сбалансировать сложность DLP в *E(Fq)* и *J(E)*; в зависимости от уровня безопасности полезными являются значения *t* между 6 и 12. Подгруппа порядка *pt* является тором. Существует некоторое независимое использование в криптографии на основе торов. У нас также есть проблема, если *p*, наибольший простой делитель порядка якобиана, равен характеристике поля *Fq*. С помощью другого инъективного отображения мы могли бы тогда рассматривать DLP в аддитивной группе *E(Fq)* вместо DLP на якобиане. Однако DLP в этой аддитивной группе тривиально решается, что легко увидеть. Следовательно, эти кривые, называемые аномальными кривыми, также не должны использоваться в DLP.

All generic attacks on the discrete logarithm problem in finite abelian groups such as the Pohlig–Hellman algorithm and Pollard's rho method can be used to attack the DLP in the Jacobian of hyperelliptic curves. The Pohlig Hellman attack reduces the difficulty of the DLP by looking at the order of the group we are working with. Suppose the group that is used has elements, where is the prime factorization of Pohlig Hellman reduces the DLP in to DLPs in subgroups of order for So for the largest prime divisor of , the DLP in is just as hard to solve as the DLP in the subgroup of order Therefore, we would like to choose such that the largest prime divisor of is almost equal to itself. Requiring usually suffices. The index calculus algorithm is another algorithm that can be used to solve DLP under some circumstances. For Jacobians of (hyper)elliptic curves there exists an index calculus attack on DLP. If the genus of the curve becomes too high, the attack will be more efficient than Pollard's rho. Today it is known that even a genus of cannot assure security. Hence we are left with elliptic curves and hyperelliptic curves of genus 2. Another restriction on the hyperelliptic curves we can use comes from the Menezes Okamoto Vanstone attack / Frey Rück attack. The first, often called MOV for short, was developed in 1993, the second came about in 1994. Consider a (hyper)elliptic curve over a finite field where is the power of a prime number. Suppose the Jacobian of the curve has elements and is the largest prime divisor of For the smallest positive integer such that there exists a computable injective group homomorphism from the subgroup of of order to If is small, we can solve DLP in by using the index calculus attack in For arbitrary curves is very large (around the size of ); so even though the index calculus attack is quite fast for multiplicative groups of finite fields this attack is not a threat for most curves. The injective function used in this attack is a pairing and there are some applications in cryptography that make use of them. In such applications it is important to balance the hardness of the DLP in and ; depending on the security level values of between 6 and 12 are useful. The subgroup of is a torus. There exists some independent usage in torus based cryptography. We also have a problem, if , the largest prime divisor of the order of the Jacobian, is equal to the characteristic of By a different injective map we could then consider the DLP in the additive group instead of DLP on the Jacobian. However, DLP in this additive group is trivial to solve, as can easily be seen. So also these curves, called anomalous curves, are not to be used in DLP.

Орден Якобинов

Поэтому, чтобы выбрать хорошую кривую и хорошее конечное поле, важно знать порядок Якобиана. Рассмотрим гиперэллиптическую кривую рода *g* над полем 𝔽*q*, где *q* – степень простого числа, и определим *C* как кривую, но теперь над полем 𝔽*q*2. Можно показать, что порядок Якобиана *C* лежит в интервале [2, *q**g* + 1], называемом интервалом Хассе — Вейля. Но есть и другое: мы можем вычислить порядок, используя дзета-функцию на гиперэллиптических кривых. Пусть *N* – число точек на *C*. Тогда мы определим дзета-функцию *C* как *Z(t) = exp(∑i=1∞ Niti/i)*. Для этой дзета-функции можно показать, что *Z(t) = P(t)/(1-t)*, где *P(t)* – многочлен степени *2g* с коэффициентами в 𝔽*q*. Кроме того, *P(t)* раскладывается как *P(t) = ∏i=12g (t - αi)*, где αi – корни многочлена, и |αi| = √*q* для всех *i*. Здесь αi обозначает комплексный сопряженный. Наконец, порядок Якобиана равен *q**g* - ∑i=12g αi + 1. Следовательно, порядки Якобианов можно найти, вычислив корни многочлена *P(t)*.