Криптография гиперэллиптических кривых

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

Определение

( Воображаемая ) гиперэллиптическая рода кривая $g$ над полем $K$ задается уравнением $C:y^{2}+h(x)y=f(x)\in K[x,y]$ где $h(x)\in K[x]$ является многочленом степени не большей, чем $g$ и $f(x)\in K[x]$ является моническим полиномом степени $2g+1$ . Из этого определения следует, что эллиптические кривые — это гиперэллиптические кривые рода 1. В криптографии гиперэллиптических кривых $K$ часто является конечным полем . Якобиан $C$ , обозначенный $J(C)$ , является факторгруппой , поэтому элементы якобиана не являются точками, они являются классами эквивалентности дивизоров степени 0 при отношении линейной эквивалентности . Это согласуется со случаем эллиптической кривой, поскольку можно показать, что якобиан эллиптической кривой изоморфен группе точек на эллиптической кривой. ^[1] Использование гиперэллиптических кривых в криптографии пришло в 1989 году от Нила Коблица . Несмотря на то, что они были представлены всего через 3 года после ECC, не многие криптосистемы реализуют гиперэллиптические кривые, поскольку реализация арифметики не так эффективна, как в криптосистемах, основанных на эллиптических кривых или факторинге ( RSA ). Эффективность реализации арифметики зависит от лежащего в основе конечного поля. $K$ На практике оказывается, что конечные поля характеристики 2 являются хорошим выбором для аппаратных реализаций, в то время как программное обеспечение обычно быстрее в нечетной характеристике. ^[2]

Якобиан на гиперэллиптической кривой является абелевой группой и как таковой может служить группой для задачи дискретного логарифмирования (ДЛП). Короче говоря, предположим, что у нас есть абелева группа $G$ и $g$ элемент $G$ , DLP на $G$ влечет за собой нахождение целого числа $a$ учитывая два элемента $G$ , а именно $g$ и $g^{a}$ . Первым типом используемой группы была мультипликативная группа конечного поля, позже стали использоваться также якобианы (гипер)эллиптических кривых. Если гиперэллиптическая кривая выбрана тщательно, то метод Ро Полларда является наиболее эффективным способом решения DLP. Это означает, что если якобиан имеет $n$ элементов, что время работы экспоненциально $\log(n)$ . Это позволяет использовать якобианы достаточно малого порядка , что делает систему более эффективной. Но если гиперэллиптическая кривая выбрана неудачно, решить DLP станет довольно легко. В этом случае существуют известные атаки, которые более эффективны, чем обычные решатели дискретного логарифма. ^[3] или даже субэкспоненциальный. ^[4] Следовательно, следует избегать этих гиперэллиптических кривых. Рассматривая различные атаки на DLP, можно перечислить особенности гиперэллиптических кривых, которых следует избегать.

Атаки на DLP

Все общие атаки на проблему дискретного логарифмирования в конечных абелевых группах, такие как алгоритм Полига – Хеллмана и метод Ро Полларда, могут быть использованы для атаки ДЛП в якобиане гиперэллиптических кривых. Атака Полига-Хеллмана снижает сложность DLP, учитывая порядок группы, с которой мы работаем. Предположим, группа $G$ который используется, имеет $n=p_{1}^{r_{1}}\cdots p_{k}^{r_{k}}$ элементы, где $p_{1}^{r_{1}}\cdots p_{k}^{r_{k}}$ является основной факторизацией $n$ . Полиг-Хеллман снижает DLP в $G$ DLP в подгруппах заказа $p_{i}$ для $i=1,...,k$ . Итак, для $p$ наибольший простой делитель $n$ , DLP в $G$ так же сложно решить, как и DLP в подгруппе порядка $p$ . Поэтому мы хотели бы выбрать $G$ такой, что наибольший простой делитель $p$ из $\#G=n$ почти равен $n$ сам. Требующий ${\textstyle {\frac {n}{p}}\leq 4}$ обычно хватает.

Алгоритм расчета индекса — это еще один алгоритм, который при некоторых обстоятельствах можно использовать для решения DLP. Для якобианов (гипер)эллиптических кривых существует атака DLP с помощью индексного исчисления. Если род кривой станет слишком большим, атака будет более эффективной, чем ро Полларда. Сегодня известно, что даже род $g=3$ не может гарантировать безопасность. ^[5] Следовательно, у нас остались эллиптические кривые и гиперэллиптические кривые рода 2.

Другое ограничение на гиперэллиптические кривые, которые мы можем использовать, связано с атакой Менезеса-Окамото-Вэнстона/атакой Фрея-Рюка. Первая, часто называемая для краткости MOV, была разработана в 1993 году, вторая — в 1994 году. Рассмотрим (гипер)эллиптическую кривую. $C$ над конечным полем $\mathbb {F} _{q}$ где $q$ это степень простого числа. Предположим, что якобиан кривой имеет $n$ элементы и $p$ является наибольшим простым делителем $n$ . Для $k$ наименьшее целое положительное число такое, что $p|q^{k}-1$ существует вычислимый гомоморфизм инъективной группы из подгруппы $J(C)$ порядка $p$ к $\mathbb {F} _{q^{k}}^{*}$ . Если $k$ небольшой, мы можем решить DLP в $J(C)$ используя атаку индексного исчисления в ${\textstyle \mathbb {F} _{q^{k}}^{*}}$ . Для произвольных кривых $k$ очень большой (размером примерно с $q^{g}$ ); поэтому, хотя атака с использованием индексного исчисления довольно быстра для мультипликативных групп конечных полей, эта атака не представляет угрозы для большинства кривых. Инъективная функция, используемая в этой атаке, представляет собой пару , и в некоторых приложениях в криптографии они используются. В таких приложениях важно сбалансировать жесткость DLP в $J(C)$ и ${\textstyle \mathbb {F} _{q^{k}}^{*}}$ ; в зависимости от уровня безопасности значений $k$ от 6 до 12 полезны.Подгруппа ${\textstyle \mathbb {F} _{q^{k}}^{*}}$ является тором . Существует некоторое независимое использование в криптографии на основе тора .

У нас также есть проблема, если $p$ , наибольший простой делитель порядка якобиана, равен характеристике $\mathbb {F} _{q}.$ Используя другое инъективное отображение, мы могли бы тогда рассмотреть ДЛП в аддитивной группе. $\mathbb {F} _{q}$ вместо DLP на якобиане. Однако, как легко видеть, проблему DLP в этой аддитивной группе решить тривиально. Поэтому эти кривые, называемые аномальными кривыми, не следует использовать в DLP.

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

Следовательно, чтобы выбрать хорошую кривую и хорошее конечное поле, лежащее в ее основе, важно знать порядок якобиана. Рассмотрим гиперэллиптическую кривую ${\textstyle C}$ рода ${\textstyle g}$ над полем ${\textstyle \mathbb {F} _{q}}$ где ${\textstyle q}$ является степенью простого числа и определяет ${\textstyle C_{k}}$ как ${\textstyle C}$ но теперь над полем ${\textstyle \mathbb {F} _{q^{k}}}$ . Можно показать, что порядок якобиана ${\textstyle C_{k}}$ лежит в интервале ${\textstyle [({\sqrt {q}}^{k}-1)^{2g},({\sqrt {q}}^{k}+1)^{2g}]}$ , называемый интервалом Хассе-Вейля. ^[6]

Но это еще не все: мы можем вычислить порядок, используя дзета-функцию на гиперэллиптических кривых. Позволять ${\textstyle A_{k}}$ быть количеством очков на ${\textstyle C_{k}}$ . Затем мы определяем дзета-функцию ${\textstyle C=C_{1}}$ как ${\textstyle Z_{C}(t)=\exp(\sum _{i=1}^{\infty }{A_{i}{\frac {t^{i}}{i}}})}$ . Для этой дзета-функции можно показать, что ${\textstyle Z_{C}(t)={\frac {P(t)}{(1-t)(1-qt)}}}$ где ${\textstyle P(t)}$ является полиномом степени ${\textstyle 2g}$ с коэффициентами в ${\textstyle \mathbb {Z} }$ . ^[7] Более того ${\textstyle P(t)}$ факторы как ${\textstyle P(t)=\prod _{i=1}^{g}{(1-a_{i}t)(1-{\bar {a_{i}}}t)}}$ где ${\textstyle a_{i}\in \mathbb {C} }$ для всех ${\textstyle i=1,...,g}$ . Здесь ${\textstyle {\bar {a}}}$ обозначает комплексно-сопряженное число $a$ . Наконец мы имеем, что порядок ${\textstyle J(C_{k})}$ равно ${\textstyle \prod _{i=1}^{g}{|1-a_{i}^{k}|^{2}}}$ . Следовательно, порядки якобианов можно найти, вычислив корни ${\textstyle P(t)}$ .

Ссылки

^ Дешен, Изабель (2007). «Группа Пикарда, или как собрать группу из набора» (PDF) . Учебное пособие по криптографии с эллиптическими и гиперэллиптическими кривыми, 2007 г.
^ Годри, П.; Любич, Д. (2009). «Арифметика двух характеристических поверхностей Куммера и эллиптических линий Куммера» . Конечные поля и их приложения . 15 (2): 246–260. дои : 10.1016/j.ffa.2008.12.006 .
^ Терио, Н. (2003). «Атака индексного исчисления для гиперэллиптических кривых малого рода». Достижения в криптологии — ASIACRYPT 2003 . Нью-Йорк: Спрингер. ISBN 978-3540406747 .
^ Энге, Андреас (2002). «Вычисление дискретных логарифмов в гиперэллиптических якобианах высокого рода за доказуемо субэкспоненциальное время» . Математика вычислений . 71 (238): 729–742. Бибкод : 2002MaCom..71..729E . дои : 10.1090/S0025-5718-01-01363-1 .
^ Джаспер Шолтен и Фредерик Веркаутерен, Введение в криптографию эллиптических и гиперэллиптических кривых и криптосистему NTRU , раздел 4
^ Альфред Дж. Менезес, Йи-Хонг Ву, Роберт Дж. Зуккерато, Элементарное введение в гиперэллиптические кривые , стр. 30
^ Альфред Дж. Менезес, Йи-Хонг Ву, Роберт Дж. Зуккерато, Элементарное введение в гиперэллиптические кривые , стр. 29

Внешние ссылки

Колм О hÉigeartaigh Реализация некоторых алгоритмов гиперэллиптических кривых с использованием MIRACL
DJ Bernstein Surface1271: высокоскоростная криптография с гиперэллиптической кривой рода 2 - незавершенная работа 2006 года с намерением создать вариант Диффи-Хеллмана, но застопорилась из-за трудностей с выбором поверхностей (в свою очередь, из-за того, что подсчет точек для больших поверхностей недоступен) . Содержит программное обеспечение для скалярного умножения Pentium M на поверхности Куммера.

[1] Дешен, Изабель (2007). «Группа Пикарда, или как собрать группу из набора» (PDF) . Учебное пособие по криптографии с эллиптическими и гиперэллиптическими кривыми, 2007 г.

[2] Годри, П.; Любич, Д. (2009). «Арифметика двух характеристических поверхностей Куммера и эллиптических линий Куммера» . Конечные поля и их приложения . 15 (2): 246–260. дои : 10.1016/j.ffa.2008.12.006 .

[3] Терио, Н. (2003). «Атака индексного исчисления для гиперэллиптических кривых малого рода». Достижения в криптологии — ASIACRYPT 2003 . Нью-Йорк: Спрингер. ISBN 978-3540406747 .

[4] Энге, Андреас (2002). «Вычисление дискретных логарифмов в гиперэллиптических якобианах высокого рода за доказуемо субэкспоненциальное время» . Математика вычислений . 71 (238): 729–742. Бибкод : 2002MaCom..71..729E . дои : 10.1090/S0025-5718-01-01363-1 .

[5] Джаспер Шолтен и Фредерик Веркаутерен, Введение в криптографию эллиптических и гиперэллиптических кривых и криптосистему NTRU , раздел 4

[6] Альфред Дж. Менезес, Йи-Хонг Ву, Роберт Дж. Зуккерато, Элементарное введение в гиперэллиптические кривые , стр. 30

[7] Альфред Дж. Менезес, Йи-Хонг Ву, Роберт Дж. Зуккерато, Элементарное введение в гиперэллиптические кривые , стр. 29

[1]

[2]

[3]

[4]

[5]

[6]

[7]