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

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

Означення

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

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

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

де крива має дискримінант $\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}+{\delta ^{2} \over 3}T+a_{3}\delta ^{2}=0.$

Тоді

$\mu ={\delta -a_{1}\delta ^{2/3} \over 3}.$

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

Тепер, визначивши наступне значення $D={\dfrac {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}\neq 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}+\varepsilon x,3\varepsilon (y-1)),$

де

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

та

$\varepsilon ={\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})$.

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

Подвоєння

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

$[2]P=\left(Y_{1}\left(X_{1}^{3}-Z_{1}^{3}\right):X_{1}\left(Z_{1}^{3}-Y_{1}^{3}\right):Z_{1}\left(Y_{1}^{3}-X_{1}^{3}\right)\right)$.

Додавання

Таким же чином для двох різних точок $P=(X_{1}:Y_{1}:Z_{1})$ та точки $Q=(X_{2}:Y_{2}:Z_{2})$ можна визначити формулу додавання. Нехай $R$ позначає суму цих точок, $R=P+Q$, тоді її координати наступні:

$R=\left(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}\right)$.

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

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

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

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

Більш того, $(Z:X:Y)\neq (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}).\quad \quad (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}=BY_{1}-Y_{2}A,$

$Y_{3}=X_{1}A-BX_{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
• Marc Joye, Jean-Jacques Quisquater (2001). Hessian Elliptic Curves and Side-Channel Attacks. Springer-Verlag Berlin Heidelberg 2001. ISBN 978-3-540-42521-2.
• N. P. Smart (2001). The Hessian form of an Elliptic Curve. Springer-Verlag Berlin Heidelberg 2001. ISBN 978-3-540-42521-2.