Насколько я знаю, нет, но вы могли бы построить один. (Зачем вам это нужно, однако, это другой вопрос...)
Общие положения
Вы можете найти несколько связанный вопрос и отличный ответ здесь, хотя речь идет не конкретно об эллиптических кривых.
TL; DR в основном заключается в том, что проще построить билинейную карту на группах составного порядка. $N=pq$ с $р$ и $q$ простые числа, поскольку они будут иметь две подгруппы большого простого порядка, естественно, из теоремы Лагранжа.
Теперь для эллиптических кривых все немного по-другому. Мы строим «группу эллиптических кривых», которая определена над заданным полем.
«Координаты» точек эллиптической кривой «живут» в этом поле, но сами точки «живут» в группе EC.
Как есть разные заказы. Поле имеет свой порядок, а группа эллиптических кривых имеет свой порядок. $n$ (который может быть составным или простым). Когда мы говорим о кривых простого порядка, мы обычно рассматриваем порядок группы эллиптических кривых, а не порядок базового поля, над которым она определена.
Атака MOV и степень внедрения
Одна вещь, которую важно знать в этой области, это то, что существует так называемая MOV-атака который использует билинейную пару, отображающую две точки на эллиптической кривой $E(\mathbb{F}_q)$ к элементу в поле $\mathbb{F}_{q^k}$, за $к$ степень погружения этой кривой.
Мы определяем $к$ как наименьшее значение такое, что $n | д^к-1$.
Атака MOV опасна, потому что если $к$ является небольшой, то решение DLP в этом поле расширения проще, чем в исходной группе эллиптических кривых, и отображается обратно в решение на эллиптической кривой, эффективно нарушая его безопасность.
Таким образом, типичные эллиптические кривые, которые мы используем для ECDSA, ECDH и других схем на основе эллиптических кривых (которые не основаны на спаривании), требуют, чтобы их степень встраивания была большой. СЕК 1 v2 говорит например:
Наконец, хотя общие субэкспоненциальные алгоритмы для решения ECDLP неизвестны, три класса кривых поддаются алгоритмам специального назначения. Во-первых, эллиптические кривые $Е$ над $F_q$ с $n$ разделяющий $q^B 1$ для маленьких $В$ восприимчивы к атакам, описанным Menezes, Okamoto и Vanstone [MOV93], а также Frey и Rück [FR94]. Атаки эффективно снижают ECDLP
на этих кривых к традиционной задаче дискретного логарифмирования в небольшом расширении степени $F_q$. Связанный $B ¥20$ был обновлен до $B ¥100$ в [X9.62a], чтобы обеспечить большой запас прочности.
Вот их $В$ наша ценность $к$.
Почему важна степень встраивания
Выбор этой степени вложения $к$ для парной криптографии является компромиссом между безопасностью и эффективностью: большая степень встраивания означает, что задачу дискретного логарифмирования труднее решить в результирующей мультипликативной группе, но это также означает, что операции выполняются в расширенном поле более высокой степени , что менее эффективно...
Теперь, когда мы говорим о кривых, удобных для спаривания, обычно имеется в виду, что мы знаем способ построить спаривание, которое будет "легко" вычисляется для этой эллиптической кривой. Это также означает, что обычно мы ожидаем относительно «низкое» значение для $к$, большую часть времени $k \leq 24$.
(Если вы хотите получить общее представление об эллиптической кривой степени вложения 1, я рекомендую вам прочитать этот документ 2016 года.)
Что это значит для безопасности DLP?
Позволять $G$ быть подгруппой порядка $q$ в $E(F_p)$.
Алгоритм Полларда-Ро на подгруппе $G$ нашей эллиптической кривой займет $\sqrt{\frac{Ïq}{2}}$ шаги, и каждый шаг занимает ~$ О (\ журнал ^ 2 (р)) $.
Это означает, что мы хотим убедиться, что порядок нашей подгруппы $q$ настолько велика, насколько это возможно, чтобы алгоритм Полларда-Ро работал как можно дольше.
С вышеупомянутой атакой MOV пусть $e : G\times G' F_{p^k}$ , куда $к$ – степень встраивания, DLP на $G$ затем могут быть переведены в DLP на $F_{p^k}$ и Поллард-Ро на нашем расширенном поле $F_{p^k}$ также нуждается $\sqrt{\frac{Ïq}{2}}$ шаги, но каждый шаг занимает только $О(к\лог(р))$, это огромная разница в сложности.
Вот почему мы хотим иметь большую степень вложения $к$ для эллиптических кривых, используемых для обычного ECC, как я уже упоминал выше, но не обязательно в парной криптографии.
Дело простого порядка
В конце концов, важно вспомнить, чем интересны «простые заказы» для DLP: это из-за Алгоритм Полига-Хеллмана, чей наихудший случай сложности - это алгоритм детского шага-гигантского шага, когда порядок простой.
Pohlig-Hellman в основном похож на CRT для RSA, он позволяет нам работать в меньших и более простых группах, если порядок нашей начальной группы не является простым.
В такой конфигурации имеет смысл иметь большой простой порядок, поскольку все подгруппы нашей исходной группы должны делить его порядок, поэтому мы уверены, что Поллард-Ро настолько сложен, насколько это возможно.
Дело ECDLP
Интересно, что лучшая (общая) известная атака (см. это) в криптографии на эллиптических кривых представляет собой комбинацию алгоритмов Поллига-Хеллмана и Полларда-Ро.
Если вы обозначите $л$ наибольший простой делитель $n$, эта атака способна справиться с ECDLP всего за $O(\sqrt{l})$ время, поэтому мы хотели бы иметь большой простой делитель в нашем порядке $n$...
Обратите внимание, что для аномальной кривой, то есть эллиптических кривых над полем $F_p$ чей заказ ЕС также $р$, у нас есть атаки, которые выполняются за полиномиальное время! Увидеть Сато и Араки здесь, или Семаев, или Умная:
На практике описанный метод означает, что при выборе эллиптических кривых для использования в криптографии необходимо исключить все кривые, групповые порядки которых равны порядку конечного поля
(выделено мной)
Обратите внимание, что в целом, если $nâ1$ является произведением малых простых чисел, то алгоритм Полига-Хеллмана может эффективно решить проблему дискретного логарифмирования в этой группе, что обычно является причиной, по которой мы выбираем безопасное простое число при работе с DLP: он гарантирует, что у нас есть " большое" простое число в разложении $n-1$.
О порядке EC против базовых заказов
Обратите внимание, что порядок кривой в основном представляет собой количество рациональных точек на этой эллиптической кривой. Если мы работаем над $F_p$, то мы знаем, что это количество точек в нашем ЭК равно $p+1-t$ куда $t$ это След Фробениуса кривой. По теореме Хассе мы также знаем, что $t$ между $-2 \sqrt{p}$ и $2 \sqrt{p}$.
Но в ECC мы обычно работаем над подгруппа эллиптической кривой, определяемой базовой точкой. Порядок базовой точки является простым делителем $p+1-t$ по теореме Лагранжа.
Итак, какой из них вы хотели бы быть безопасным премьер-министром? Я бы предположил, что подгруппа сгенерирована заданной базовой точкой.
Это также верно для криптографии на основе пар: пары определяются над подгруппой группы EC. Обычно Пейринг Тейт предполагает $к>1$, $\#E(F_p) = hn$, за $n$ простое число, и оно работает в подгруппе порядка $n$ этой эллиптической кривой.
Как построить один?
К сожалению, как я уже говорил вам в начале, мне неизвестна благоприятная для спаривания кривая, порядок подгруппы которой является безопасным простым числом. Должна быть возможность создать его, но у меня не было времени (пока) написать сценарий поиска, который бы его выдал.
Как у нас дела? Ну, боюсь, самый простой способ там "проб и ошибок"!
Баррето и Нахриг дали метод для кривых простого порядка с $к = 12$, который был «расширен» на кривые с $к= 3, 4, 6$ к Фримен.
К сожалению, я не знаю о реализации с открытым исходным кодом, позволяющей легко
попробуйте создать эту кривую.
