Крипто перетворення в гіпереліптичних кривих

Першими пропозиціями щодо застосування гіпереліптичних кривих вочевидь необхідно вважати пропозиції Neal Koblitz – професора математики Вашингтонського університету [144]. Він є визнаним математиком, у тому числі з алгебраїчної геометрії, що включає й розділи теорії еліптичних і гіпереліптичних кривих. Деякий час вважалося, що застосування перетворень на гіпереліптичних кривих в криптографії суттєво обмежено через складності необхідних обчислень і, як наслідок, незадовільний рівень швидкодії.

Значні результати у вирішенні цього протиріччя вніс професор Christof Paar (Германія). Ним вирішені задачі оптимізації обчислень на гіпереліптичних кривих 1–4 родів [146]. Так, він виконав оптимізацію формул складання та подвоєння дивізорів з використанням узагальненого метода Карацуби. Це дозволило підвищити швидкодії перетворень на гіпереліптичних кривих, досягти результатів, порівнюваних зі складністю перетворень на еліптичних кривих, а в деяких випадках і перевершити їх. Він також вів модифіковану метрику, більш точну. Останні дослідження значною мірою присвячені оптимізації складання та подвоєння за критерієм складності. В останні роки значні зусилля були спрямовані й на розробку теорії та практики криптографічної стійкості відносно криптографічних перетворень на гіпереліптичних кривих [145 - 150].

 

 

Таблиця 9.1 - Асиметричні криптографічні перетворення для реалізації направленого шифрування

Параметри НШ/ Математичний апарат	Особистий ключ НРШ	Відкритий ключ НЗШ (сертифікат)	Асиметрична пара (ключ)	Загальні параметри крипто перетворення	Сертифікати	Складність крипто аналізу
НШ в кільці (RSA)	Di	Ei	(Di, Ei)	N = P Q	Еi	Субекспоненційна
НШ в полі Галуа F(P)	Хi	Yi=g^Xi( mod P)	(Xi, Yi)	P, q, g	Yi	Субекспоненційна
НШ в групі точок еліптичних кривих Е(F(q))	di	Qi=di G( mod q)	(di, Qi)	a, b, G, n, f(x)(P), h	Qi	Експоненційна
НШ в гіпереліптичних кривих	Сi	D2= ci D1	(ci, D2)	f(x), g(x), q, D1, g, J	D2	Експоненційна
НШ зі спарюванням точок еліптичних кривих	diD =s QiD	QiD=H1 (ID)	(diD, QiD)	G1, G2, e, H1, P, H2, H3, F2^m, Pp	QiD	Експоненційна – субекспоненційна
НШ в кільці зрізаних поліномів (NTRU)	f = 1 +pF (modq)	h= f ^1*g*p(modq)	(f, h)	N, q, p, f, g,df, dg, c		Експоненційна – субекспоненційна

 

 

Визначено, що основним параметром, від значення якого залежить криптографічна стійкість перетворень на еліптичних кривих, є порядок групи дивізорів гіпереліптичної кривої. На сьогодні для визначення порядку еліптичної кривої можуть бути застосовані два класи методів – l - адичні та p - адичні. В обох випадках теоретичною основою є поняття Дзета-функції та гіпотези Вейля. Чисельником Дзета-функції є характеристичний поліном ендоморфізма Фробеніуса. Далі, якщо гіпереліптична крива визначена над кінцевим полем , то для визначення її порядку достатньо знати число точок, які задовольняють рівнянню кривої над усіма розширеннями поля до включно, де g - рід кривої. Нині найбільше розповсюдження отримали Р- адичні методи визначення порядку гіпереліптичних кривих.

Наведемо деякі поняття й визначення, що стосуються гіпереліптичних кривих, орієнтуючись на [145 150].

Визначення 1.1 Нехай F - кінцеве поле та нехай - алгебраїчне замикання F. Тоді рівняння вигляду

, (1.57)

де - поліном степені не більше , - нормований поліном степені і немає розв’язків , які одночасно задовольняли б рівнянню , і рівняння приватних похідних задовольняють умовам та , визначає гіпереліптичну криву C роду () над F.

Коли g = 1, то ми маємо звичайну еліптичну криву. У цьому випадку нормований поліном у рівнянні (12.1) є поліномом третього ступеню.

За цієї умови еліптична крива Е в канонічній формі Веєрштрасса в афінних координатах може бути подана в такому вигляді:

, (1.58)

причому коефіцієнти a, b, c Î F. Також відомо, що гіпереліптична крива не має особливих точок.

Нехай – кінцева точка на гіпереліптичній кривій . Протилежною точці є точка . Також точка на нескінченності є протилежною сама собі, тобто . Якщо кінцева точка задовольняє умові , то така точка називається точкою спеціального вигляду, усі інші називаються звичайними.

На рис. 1.2 наведено приклад гіпереліптичної кривої над полем дійсних чисел.

Для такої кривої точка на нескінченності лежить у проективній площині . Це єдина точка, що лежить на прямій у нескінченності, що задовольняє рівнянню, однорідному рівнянню гіпереліптичної кривої. Якщо , то є єдиною особливою точкою.