Гиперэллиптік қисықтар криптографиясы: қағидалар мен ерекшеліктері
Hyperelliptic curve cryptography
Гиперэллиптиктік криптография: ECC-ге ұқсас, бірақ жоғары родтағы қисықтарды қолданады. Математикалық негіздері, Jacobian тобы және криптографиялық қолданыстары туралы ақпарат.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Гиперэллиптік қисық криптографиясы, Эллиптік қисық криптографиясымен (ECC) салыстырғанда, гиперэллиптік қисықтың Якобианы арифметикалық амалдар орындалатын абельдік топ болып табылады, дәл ЭКК-де эллиптік қисықтағы нүктелер тобы қолданылатындай.
Hyperelliptic curve cryptography is similar to elliptic curve cryptography (ECC) insofar as the Jacobian of a hyperelliptic curve is an abelian group in which to do arithmetic, just as we use the group of points on an elliptic curve in ECC.
Анықтама
(Кейдегі) гендердегі гипереллиптикалық қисық, өріс үстінде, теңдеуімен беріледі, мұнда - дәрежесінен аспайтын көпмүше, ал - дәрежелі мономдық көпмүше. Осы анықтамадан эллиптік қисықтар – 1 гендердегі гипереллиптикалық қисықтар екені шығады. Гипереллиптикалық қисық криптографиясында көбінесе шекті өріс болып табылады. -ның Якобианы, белгіленген, бөлшектік топ болып табылады, сондықтан Якобиан элементтері нүктелер емес, олар сызықтық эквиваленттілік қатынасы бойынша 0 дәрежелі бөлгіштердің эквиваленттілік кластары. Бұл эллиптік қисық жағдайымен сәйкес келеді, өйткені эллиптік қисықтың Якобианы эллиптік қисықтағы нүктелер тобымен изоморфты екенін көрсетуге болады. Криптографияда гипереллиптикалық қисықтарды қолдану 1989 жылы Нил Коблицтен бастау алды. ECC-ден кейін 3 жыл өткенімен, көптеген криптожүйелер гипереллиптикалық қисықтарды іске асырмайды, себебі арифметиканы іске асыру эллиптік қисықтарға немесе факторизацияға (RSA) негізделген криптожүйелерге қарағанда тиімді емес. Арифметиканы іске асырудың тиімділігі негізгі шекті өріске байланысты, практикада 2 сипаттамалы шекті өрістер аппараттық іске асыру үшін жақсы таңдау болып табылады, ал бағдарламалық қамтамасыздану әдетте тақ сипаттамалы өрістерде жылдамдатылады. Гипереллиптикалық қисықтағы Якобиан – Абель тобы және осылайша дискретті логарифм мәселесі (DLP) үшін топ ретінде қызмет ете алады. Қысқасы, егер бізде Абель тобы және элементі болса, онда үстіндегі DLP екі элементі берілген жағдайда бүтін санын табуды білдіреді, атап айтқанда және . Топтың алғашқы түрі шекті өрістің көбейту тобы болды, кейін (гипер)эллиптикалық қисықтардың Якобиандары да қолданылды. Егер гипереллиптикалық қисық сақтап таңдалса, онда Поллардтың rho әдісі DLP-ні шешудің ең тиімді жолы болып табылады. Бұл Якобианда элемент болса, орындалу уақыты експоненциалды болады дегенді білдіреді. Бұл салыстырмалы түрде кішкентай ретті Якобиандарды пайдалануға мүмкіндік береді, осылайша жүйені тиімдірек етеді. Бірақ егер гипереллиптикалық қисық дұрыс таңдалмаса, 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-ге қарсы шабуылдар
Дискретті логарифм мәселесіне шекті абельдік топтарда жасалған барлық жалпы шабуылдар, мысалы, Полиг–Хеллман алгоритмі және Поллардтың rho әдісі гиперэллиптік қисықтардың Якобианында DLP-ге шабуыл жасау үшін қолданылуы мүмкін. Полиг–Хеллман шабуылы біз жұмыс істейтін топтың ретін қарастыра отырып, DLP-нің қиындығын азайтады. Егер қолданылатын топта *n* элемент болса, мұнда *n* – жай санның жіктелуі, Полиг–Хеллман DLP-ні реттік топтардағы DLP-лерге дейін азайтады. Демек, егер *p* – *n*-нің ең үлкен жай бөлгіші болса, онда *n* реттік топтағы DLP-ні шешу, *p* реттік топтың DLP-сін шешумен бірдей қиын. Сондықтан біз *n*-нің ең үлкен жай бөлгіші өзіне жақын болуын қалаймыз. *n* жеткілікті үлкен болуы көбінесе жеткілікті. Индекстік есептеу алгоритмі – бұл кейбір жағдайларда DLP-ні шешу үшін қолданылатын тағы бір алгоритм. (Гипер)эллиптік қисықтардың Якобиандары үшін DLP-ге индекстік есептеу шабуылы қолданылады. Егер қисықтың туысы тым жоғары болса, шабуыл Поллардтың rho әдісінен тиімді болады. Бүгінде тіпті 10-ға тең туыс та қауіпсіздікті қамтамасыз ете алмайды. Сондықтан біз 2-ші туыстың эллиптік және гиперэллиптік қисықтарымен қалдық. Гиперэллиптік қисықтарды қолдануға тағы бір шектеу – Менезес–Окамото–Ванстон шабуылы / Фрей–Рюк шабуылы. Біріншісі, көбінесе MOV деп аталады, 1993 жылы жасалды, екіншісі 1994 жылы пайда болды. Шекті өріс үстіндегі (гипер)эллиптік қисықты қарастырайық, мұнда *q* – жай санның дәрежесі. Егер қисықтың Якобианында *n* элемент болса және *p* – *n*-нің ең үлкен жай бөлгіші болса, онда *p*-ге қатысты ең кіші оң бүтін сан *k* үшін, *k*-ретінің Якобианның кіші тобынан *q*-ретінің тобына есептеуге болатын инъективті гомоморфизм бар. Егер *k* кішкентай болса, онда біз DLP-ні *q*-да индекстік есептеу шабуылын қолдану арқылы шеше аламыз. Кездейсоқ қисықтар үшін *k* өте үлкен (шамамен *q*-ға тең); сондықтан индекстік есептеу шабуылы шекті өрістердің көбейтуші топтары үшін өте жылдам болғанымен, бұл шабуыл көптеген қисықтар үшін қауіп төндірмейді. Бұл шабуылда қолданылатын инъективті функция – жұптау, және оларды пайдаланатын криптографиядағы кейбір қолданбалар бар. Мұндай қолданбаларда DLP-нің *q*-да және *p*-да қиындығын теңестіру маңызды; қауіпсіздік деңгейіне байланысты 6 мен 12 аралығындағы *k* мәндері пайдалы. Якобианның кіші тобы – тор. Торға негізделген криптографияда кейбір тәуелсіз қолданыс бар. Бізде сондай-ақ проблема бар, егер *p*, Якобиан ретінің ең үлкен жай бөлгіші, *q*-ның сипаттамасына тең болса. Басқа инъективті карта арқылы біз Якобиандағы DLP орнына *q*-ның қосымша тобындағы 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.
Якобтар ордені
Сондықтан, жақсы қисық пен жақсы жатқан шекті өрісті таңдау үшін Якобианның ретін білу маңызды. дәрежесі болған және өрiсiндегi гиперэллиптік қисықты қарастырайық, мұнда жайтсан санның дәрежесі, және -ты өрiсiнде деп анықтаймыз. Якобианның реті Хассе-Вейль аралығында жататынын көрсетуге болады, яғни . Бірақ мұнан да көп, гиперэллиптік қисықтардағы дзета-функцияны қолданып, ретті есептеуге болады. қисығындағы нүктелер саны болсын. Онда қисығының дзета-функциясы былай анықталады: . Бұл дзета-функция үшін екенi көрсетiледi, мұнда - дәрежелi көпмүше, ал коэффициенттерi -те. сондай-ақ түрiнде көшiрiледi, мұнда барлық үшiн . Мұнда - кешендi жұптас. Соңында, реті тең. Демек, Якобиандардың ретiн -ның түбiрлерiн есептеу арқылы табуға болады.
Hence, in order to choose a good curve and a good underlying finite field, it is important to know the order of the Jacobian. Consider a hyperelliptic curve of genus over the field where is the power of a prime number and define as but now over the field It can be shown that the order of the Jacobian of lies in the interval , called the Hasse Weil interval. But there is more, we can compute the order using the zeta function on hyperelliptic curves. Let be the number of points on Then we define the zeta function of as For this zeta function it can be shown that where is a polynomial of degree with coefficients in Furthermore factors as where for all Here denotes the complex conjugate of Finally we have that the order of equals Hence orders of Jacobians can be found by computing the roots of .