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

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

Определение

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

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

Атаки на DLP

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

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

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

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

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

Следовательно, чтобы выбрать хорошую кривую и хорошее базовое конечное поле, важно знать порядок якобиана. Рассмотрим гиперэллиптическую кривую рода над полем , где — степень простого числа , и определим как , но теперь над полем . Можно показать, что порядок якобиана лежит в интервале , называемом интервалом Хассе-Вейля. ^[6] ${\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}]}$

Но есть еще кое-что: мы можем вычислить порядок, используя дзета-функцию на гиперэллиптических кривых. Пусть — число точек на . Тогда мы определим дзета-функцию как . Для этой дзета-функции можно показать, что где — многочлен степени с коэффициентами в . ^[7] Кроме того, факторы как , где для всех . Здесь обозначает комплексно сопряженное число . Наконец, мы имеем, что порядок равен . Следовательно, порядки якобианов можно найти, вычислив корни . ${\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} }$ ${\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}}}$ ${\displaystyle a}$ ${\textstyle J(C_{k})}$ ${\textstyle \prod _{i=1}^{g}{|1-a_{i}^{k}|^{2}}}$ ${\textstyle P(t)}$

Ссылки

1. Дешен, Изабель (2007). "Группа Пикара, или как построить группу из множества" (PDF) . Учебник по криптографии на эллиптических и гиперэллиптических кривых 2007 .
2. Годри, П.; Любич, Д. (2009). «Арифметика характеристик 2 поверхностей Куммера и эллиптических линий Куммера». Конечные поля и их приложения . 15 (2): 246–260. doi : 10.1016/j.ffa.2008.12.006 .
3. Th'eriault, N. (2003). "Атака с помощью индексного исчисления для гиперэллиптических кривых малого рода". Advances in Cryptology - ASIACRYPT 2003. Нью-Йорк: Springer. ISBN 978-3540406747.
4. Энге, Андреас (2002). «Вычисление дискретных логарифмов в гиперэллиптических якобианах высокого рода за доказуемо субэкспоненциальное время». Математика вычислений . 71 (238): 729–742. Bibcode : 2002MaCom..71..729E. doi : 10.1090/S0025-5718-01-01363-1 .
5. Джаспер Шолтен и Фредерик Веркаутерен, Введение в криптографию на основе эллиптических и гиперэллиптичных кривых и криптосистему NTRU, раздел 4
6. Альфред Дж. Менезес, Йи-Хонг Ву, Роберт Дж. Цуккерато, Элементарное введение в гиперэллиптические кривые, стр. 30
7. Альфред Дж. Менезес, Йи-Хонг Ву, Роберт Дж. Цуккерато, Элементарное введение в гиперэллиптические кривые, стр. 29

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

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