Как решить, принадлежит ли точка на эллиптической кривой группе, порожденной генератором g?

Ответ действительно зависит от известных нам криптографических эллиптических кривых!

1. Криптографический EC основного порядка: Поскольку порядок подгруппы, порожденной элементом, должен делить порядок, то есть полная группа и группа элементов. $\mathcal{O}$ порядка $1$ ( Кривые NIST P P-192, P-224, P-256, P-384, P-521) кривые имеют простой порядок, указанный в NIST.FIPS.186-4 и взято из Сек1).

2. Криптографическая ЭК с малым коэффициентом: В криптографии кривые имеют большой порядок, чтобы быть безопасными, и мы должны выбрать базовый элемент из самой большой подгруппы.Это связано с

   1. Защита от Алгоритм Полига-Хеллмана это сокращает время до наибольшего фактора и очень эффективно, когда порядок гладкий, т. е. все факторы малы.

   2. Чтобы иметь бирациональный эквивалент Монтогмери кривой, такой как Curve25519 с кофактором $8$ и Ed448-Златовласка с кофактором $4$. В этом случае у нас есть заказы для таких подгрупп, как; $2,4,8,п,2п,4п,8п$ (для кривой25519)^*

      Чтобы увидеть, что точка $G$ в порядке $2$ или же $р$ легко, проверьте $2[Г]$ или же $[p]G$, если результат тождествен, то они в этой группе. Они, но они также находятся в подгруппе, которая содержит подгруппы. В подгруппе порядка есть элементы $2 пенса$ но не в подгруппе порядка $2$ или же $р$. Проверять $[2]G$ и $[p]G$ если они не тождественны, а $[2p]Г$ то он находится в подгруппе порядка $2 пенса$.

      Кляйн группа — наименьшая группа, имеющая две подгруппы порядка 2, она изоморфна $\mathbb Z_2 \раз \mathbb Z_2$. Это может помочь понять, что две разные подгруппы могут иметь одинаковый порядок.

      Кривые NIST B имеют кофактор 2, а кривые K имеют 4, и они взяты из Сек2.

3. Изюминка криптографической EC: Изгиб известных кривых не имеет большого квадратичного множителя, как и в случае 2.

4. Случайная кривая: Я понятия не имею об ожидаемом размере коэффициентов случайно сгенерированных кривых (видел некоторые работы). У нас может быть кривая с таким порядком, что она имеет большой фактор порядка 2 или более. В этом случае $[p]G$ не раскрывает членство в подгруппе. Для ее решения нам нужно найти генератор для каждой из подгрупп и попытаться решить DLog.

5. Факторизация порядка группы не известна: В этом случае мы имеем проблема решения подгруппы (как указано в другом ответе)

   Данный $(n, G, G1, e)$ и элемент $x \в G$, вывод $1$ если порядок $х$ является $q_1$ и вывод $0$ в противном случае; То есть, не зная факторизации группового порядка $n$, решить, является ли элемент $х$ находится в подгруппе $G$. Мы называем эту проблему проблемой проблема решения подгруппы

   Хотя эта проблема дает интересные результаты в своем контексте, это не связано с эллиптическими кривыми, используемыми в ECDH, EdDSA и т. д. В эллиптических кривых все параметры общедоступны. Даже если вы не предоставляете факторизацию порядка кривой (непонятно, как вы собираетесь продавать свою кривую сообществу), можно учесть 829 бит (512-битная технология существует около 20 лет назад).

   Если вы рассматриваете кривые в очень большом порядке, мы можем сказать, что порядок кривых больше 512 бит (даже 256) не имеет большого значения, поскольку, как только алгоритм Шора установлен в криптографическом квантовом компьютере для 256-битных кривых, это вопрос раз исследователи сломают другой. Это видно из таблицы Работа Прооса и Залкса

Постквантовый ECC, с другой стороны, использует скачки по изогениям вместо DH, и эта статья является хорошим введением для всех, кто хочет учиться.

• Обмен ключами суперсингулярной изогении для начинающих, Крейг Костелло, 2019 г. (С возвращением суперсингулярных кривых!)

В конце концов, единственные проблемные случаи — это не криптографические кривые.

^* Там мы воспользовались Теорема Лагранжа по теории групп;

• Если $Ч$ является подгруппой группы $G$ тогда $ ord (H) \mid ord (G) $

Следует отметить, что мы воспользовались обратной теоремой, если $х|орг(Г)$ то есть подгруппа порядка $х$. Это не всегда верно, и чередующаяся группа 4 степени $A_4$ это самый маленький пример.