Форма Гессе еліптичної кривої

У геометрії крива Гессе — це плоска крива, схожа на декартів лист. Вона названа на честь німецького математика Отто Гессе. Ця крива була запропонована для застосування в еліптичній криптографії, оскільки арифметика в цьому представлені кривої швидша і потребує менше пам'яті, ніж арифметика в стандартній формі Вейерштрасса.

Означення

Крива Гессе рівняння $x^3+y^3+1=0.3xy$

Нехай задано поле $K$. Розглянемо еліптичну криву $E$ у наступному спеціальному випадку форми Вейерштрасса над полем $K$:

$Y^2+a_{1}XY+a_{3}Y=X^3,$

де крива має дискримінант $\mathrm{\Delta }=(a_3^3(a_1^3-27a_3))=a_3^3\delta$. Тоді точка $P=(0,0)$ має порядок 3.

Щоб довести, що $P=(0,0)$ має порядок 3, зауважимо, що дотична до $E$ у точці $P$ — пряма $Y=0$, яка перетинає $E$ в точці $P$ з кратністю 3.

І навпаки, задавши точку $P$ порядку 3 на еліптичній кривій $E$, що визначена над полем $K$, можна представити криву у формі Вейерштрасса з $P=(0,0)$, так, що дотичною в точці $P$ є пряма $Y=0$. Тоді рівняння кривої має вигляд $Y^2+a_{1}XY+a_{3}Y=X^3$ та $a_1,a_3\in K$.

Тепер, щоб отримати криву Гессе, необхідно виконати таке Шаблон:Не перекладено:

Спочатку позначимо через $\mu$ корінь многочлена

$T^3-\delta T^2+\frac{{\delta }^2}{3}T+a_3{\delta }^2=0.$

Тоді

$\mu =\frac{\delta -a_1{\delta }^{2/3}}{3}.$

Зауважимо, що над полем $K$ скінченого порядку $q\equiv 2$ $\mathrm{m}\mathrm{o}\mathrm{d}3$ кожен елемент поля $K$ має єдиний кубічний корінь у загальному випадку, $\mu$ належить розширенню поля $K$.

Тепер, визначивши наступне значення $D=\frac{3(\mu -\delta )}{\mu }$, отримуємо іншу криву $C$, яка біраціонально еквівалентна $E$:

$C$ : $x^3+y^3+z^3=Dxyz,$

в афінній площині його називають кубічною формою Гессе (у проективних координатах $x=\frac{X}{Z}$ та $y=\frac{Y}{Z}$)

$C$: $x^3+y^3+1=Dxy.$

Більш того, $D^3\ne 1$ (інакше, крива буде Шаблон:Не перекладено).

Починаючи з кривої Гессе, біраціонально еквівалентне рівняння Вейерштрасса задається співвідношенням

$v^2=u^3-27D(D^3+8)u+54(D^6-20D^3-8),$

за допомогою перетворень

$(x,y)=(\eta (u+9D^2),-1+\eta (3D^3-Dx-12))$

та

$(u,v)=(-9D^2+\epsilon x,3\epsilon (y-1)),$

де

$\eta =\frac{6(D^3-1)(v+9D^3-3Du-36)}{(u+9D^2{)}^3+(3Dd-Du-12{)}^3}$

та

$\epsilon =\frac{12(D^3-1)}{Dx+y+1}$.

Закон групування

Цікаво проаналізувати закон групування еліптичної кривої, визначивши формули додавання та подвоєння. Крім того, у цьому випадку потрібно використовувати лише ту саму процедуру для обчислення додавання, подвоєння чи віднімання точок для отримання ефективних результатів, як було сказано вище. У загальному випадку закон групування визначається наступним чином: якщо три точки лежать на одній прямій, то їх сума дорівнює нулю. Отже, за цією властивістю закони групування різні для кожної кривої.

У цьому випадку коректним шляхом є використання формул Коші-Десбовеса для отримання точки на нескінченності $\theta =(1:-1:0)$, тобто нейтрального елемента (обернений до $\theta$ є знову $\theta$). Нехай $P=(x_1,y_1)$ — точка на кривій. Прямій $y=-x+(x_1+y_1)$ належить точка $P$ і точка на нескінченності $\theta$. Тому $-P$ є третьою точкою перетину цієї прямої з кривою. Перетин еліптичної кривої з прямою дає приводить до умова $x_2-(x_1+y_1)x+x_1{y}_1=\theta$. Оскільки $x_1+y_1+D$ не дорівнює нулю ($D^3$ не дорівнює $1$), $x$-координатою точки $-P$ є $y_1$, а $y$-координатою точки $-P$ є $x_1$, тобто $-P=(y_1,x_1)$, або в проективних координатах $-P=(Y_1:X_1:Z_1)$.

У деяких застосуваннях еліптичної криптографії та факторизації за допомогою еліптичних кривих (Шаблон:Не перекладено) необхідно обчислювати множення на скаляр для точки $P$, наприклад, $[n]P$ з деяким цілим числом $n$, і вони базуються на методі швидкого піднесення до степеня; ці операції потребують формул додавання та подвоєння.

Подвоєння

Для точки $P=(X_1:Y_1:Z_1)$ на еліптичній кривій можна визначити операцію «подвоєння» за допомогою формул Коші-Десбовеса:

$[2]P=(Y_1(X_1^3-Z_1^3):X_1(Z_1^3-Y_1^3):Z_1(Y_1^3-X_1^3))$.

Додавання

Таким же чином для двох різних точок $P=(X_1:Y_1:Z_1)$ та точки $Q=(X_2:Y_2:Z_2)$ можна визначити формулу додавання. Нехай $R$ позначає суму цих точок, $R=P+Q$, тоді її координати наступні:

$R=(Y_1^2{X}_2{Z}_2-Y_2^2{X}_1{Z}_1:X_1^2{Y}_2{Z}_2-X_2^2{Y}_1{Z}_1:Z_1^2{X}_2{Y}_2-Z_2^2{X}_1{Y}_1)$.

Алгоритми та приклади

Існує алгоритм, за допомогою якого можна додати або подвоїти дві різні точки, запропонований Джойєм (Joye) і Кіскватером (Шаблон:Не перекладено). Наступне трердження дає можливість отримати операцію подвоєння шляхом додавання:

Теорема. Нехай $P=(X,Y,Z)$ — точка на еліптичній кривій Гессе $E(K)$, тоді

$2(X:Y:Z)=(Z:X:Y)+(Y:Z:X).(1)$

Більш того, $(Z:X:Y)\ne (Y:Z:X)$.

На відміну від інших параметризацій, тут відсутнє віднімання для обчислення віддзеркалення точки. Отже, цей алгоритм додавання також може бути використаний для віднімання двох точок $P=(X_1:Y_1:Z_1)$ і $Q=(X_2:Y_2:Z_2)$ на еліптичній кривій Гессе:

$(X_1:Y_1:Z_1)-(X_2:Y_2:Z_2)=(X_1:Y_1:Z_1)+(Y_2:X_2:Z_2).(2)$

Підсумовуючи, шляхом адаптування порядку вводів відповідно до рівнянь (1) або (2), алгоритм додавання, наведений вище, можна використовувати для додавання двох (різних) точок, подвоєння точки і віднімання двох точок лише за допомогою 12 добутків і 7 допоміжних змінних, включаючи 3 початкові змінні. До появи Шаблон:Не перекладено ці результати були найшвидшим відомим способом реалізації скалярного множення на еліптичній кривій для противаги атакам сторонніми каналами.

Для деяких алгоритмів захист від атак сторонніми каналами не є необхідним. Отже, такі подвоєння можуть бути швидшими. Оскільки існує багато алгоритмів, тут наведено лише найкращі алгоритми для формул додавання та подвоєння з прикладом для кожного з них:

Додавання

Нехай $P_1=(X_1:Y_1:Z_1)$ і $P_2=(X_2:Y_2:Z_2)$ дві точки відмінні від $\theta$, і $Z_1=Z_2=1$, тоді алгоритм такий:

$A=X_1{Y}_2,$

$B=Y_1{X}_2,$

$X_3=B{Y}_1-Y_{2}A,$

$Y_3=X_{1}A-B{X}_2,$

$Z_3=Y_2{X}_2-X_1{Y}_1.$

Для алгоритму необхідно: 8 множень та 3 додавання, а для відновлення: 7 множень та 3 додавання, в залежності від першої точки.

Приклад

Нехай задано точки кривої для $d=-1$: $P_1=(1:0:-1)$ та $P_2=(0:-1:1)$. Якщо $P_3=P_1+P_2$, то

$X_3=0-1=-1,$

$Y_3=-1-0=-1,$

$Z_3=0-0=0.$

Таким чином, $P_3=(-1:-1:0)$.

Подвоєння

Нехай $P=(X_1:Y_1:Z_1)$ — точка, тоді формула подвоєння має наступний вигляд:

$A=X_1^2,$

$B=Y_1^2,$

$D=A+B,$

$G=(X_1+Y_1{)}^2-D,$

$X_3=(2Y_1-G)\times (X_1+A+1),$

$Y_3=(G-2X_1)\times (Y_1+B+1),$

$Z_3=(X_1-Y_1)\times (G+2D).$

Необхідні операції для алгоритму: 3 множення $+$ 3 піднесення до квадрату $+$ $11$ додавань $+$ $3\times 2$.

Приклад

Якщо $P=(-1:-1:1)$ точка кривої Гессе з параметром $d=-1$, то координати подвоєної точки $2P=(X:Y:Z)$ наступні:

$X=(2\cdot (-1)-2)(-1+1+1)=-4,$

$Y=(-4-2\cdot (-1))((-1)+1+1)=-2,$

$Z=(-1-(-1))((-4)+2\cdot 2)=0.$

Отже, $2P=(-4:-2:0)$.

Розширені координати

Існує ще одна система координат, за допомогою якої може бути зображена крива Гессе; ці нові координати називаються розширеними координатами. Вони можуть прискорити процес додавання та подвоєння. Щоб отримати більше інформації про операції з розширеними координатами, див.

http://hyperelliptic.org/EFD/g1p/auto-hessian-extended.html#addition-add-20080225-hwcd

Координати $x$ і $y$ представляються через $X$, $Y$, $Z$, $XX$, $YY$, $ZZ$, $XY$, $YZ$, $XZ$, що задовольняють наступним рівнянням:

$x=X/Z,$

$y=Y/Z,$

$XX=X\cdot X,$

$YY=Y\cdot Y,$

$ZZ=Z\cdot Z,$

$XY=2\cdot X\cdot Y,$

$YZ=2\cdot Y\cdot Z,$

$XZ=2\cdot X\cdot Z,$

Див. також

Для отримання додаткової інформації про час роботи, необхідний у конкретному випадку, див. Шаблон:Не перекладено.

Шаблон:Не перекладено.

Посилання

• http://hyperelliptic.org/EFD/g1p/index.html

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

• Otto Hesse (1844), «Über die Elimination der Variabeln aus drei algebraischen Gleichungen vom zweiten Grade mit zwei Variabeln», Journal für die reine und angewandte Mathematik, 10, pp. 68–96
• Шаблон:Cite book
• Шаблон:Cite book

Шаблон:Ізольована стаття