Большие простые числа в ECC и дискретном логарифме

В криптографии на эллиптических кривых с использованием протокола Диффи-Хеллмана нам нужно использовать большие простые числа.

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

Я думаю, поскольку мы используем большие простые числа, у нас будет много точек, которые удовлетворяют нашему уравнению кривой.

Ответ не так прост;

• Прежде всего количество точек, удовлетворяющих уравнению кривой $N$ на кривой ограничен границей Хассе $$|N - (q+1)| \le 2 \sqrt{q}$$ для простого $q$. Это просто говорит о том, что если вам нужна кривая с большим количеством точек, вам нужно большое простое число (рассказ).

• Порядок кривой должен быть простым (простые кривые) или должен иметь по крайней мере один большой простой множитель.Curve25519 не является простой кривой, у которой есть кофактор $ч=N/8$, это обеспечивает представление кривой Монтгомери, что помогает защитить реализации. Если кривая имеет плавный порядок, что означает, что у него не будет большего простого числа, чем Поглиг-Хеламн уничтожит его независимо от порядка. Важно иметь большой заказ или большой основной заказ.

• Изгиб кривой должен иметь большой простой порядок против твист-атаки.

• Порядок кривой и порядок базового поля $(К)$ одинаковы, то дискретный логарифм на этой кривой выполняется за линейное время Смарт 97.

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

Теперь, объединив их, мы можем сказать, имеет ли группа точечных кривых ECC большое простое число и не обладает каким-либо особым свойством (мы можем сказать, что это общая кривая), то лучшая атака - Ро Полларда с $\mathcal{O}(\sqrt{N})$.

При этом мы можем сказать, что Curve25519 имеет около 128-битную безопасность дискретного журнала, а Curve448 имеет 224-битную безопасность дискретного журнала.

И, наконец, для получения дополнительной информации посетите безопасные кривые.

В криптографии на эллиптических кривых с использованием протокола Диффи-Хеллмана нам необходимо использовать большие простые числа.

Точнее

• Обычно мы используем кривую с образующей, порядок которой делится на большое простое число, потому что это дает страховку от Полиг-Хеллман Метод вычисления дискретных логарифмов.
• Мы часто делаем генератор именно такого простого порядка, потому что можем легко это сделать, и это делает кривую+генератор более подходящей для других целей, таких как подпись. Однако это бесполезно для безопасности Диффи-Хеллмана, насколько я знаю.
• Мы часто используем кривую на поле большого простого порядка, хотя у нас ее нет, по обсуждаемым причинам. там.