Рейтинг:1

Crypto

Как рассчитать порядок secp256k1?

Andy

21.12.2022, 21:16

Эллиптическая кривая secp256k1 определяется как $у^2 = х^3 + 7$. Прайм для поля установлен на:

р = 115792089237316195423570985008687907853269984665640564039457584007908834671663

Итак, теперь можно вычислить порядок с помощью алгоритма Шуфа. Здесь представлена реализация Python: https://github.com/pdinges/python-schoof

Однако кажется, что вычисление порядка больших простых чисел занимает слишком много времени. Кроме того, реализация, похоже, не способна вычислить его для такого большого простого числа.

root@78774381cc80:/home/python-schoof# python3 reduce_computation_schoof.py 17 0 7
Точки подсчета y^2 = x^3 + 0x + 7 по GF<17>: 18
root@78774381cc80:/home/python-schoof# python3 Reduced_computation_schoof.py 115792089237316195423570985008687907853269984665640564039457584007908834671663 0 7
Точки подсчета y^2 = x^3 + 0x + 7 по GF<115792089237316195423570985008687907853269984665640564039457584007908834671663>: трассировка (последний последний вызов):
  Файл "reduced_computation_schoof.py", строка 268, в <module>
    бегун.run()
  Файл "/home/python-schoof/support/running.py", строка 498, выполняется
    результат = self.__algorithm( *item, output=self.__output)
  Файл "reduced_computation_schoof.py", строка 258, в файле reduce_computation_schoof_algorithm.
    порядок = p + 1 - frobenius_trace (EllipticCurve (конечное поле (p), A, B))
  Файл "reduced_computation_schoof.py", строка 55, в frobenius_trace
    len(диапазон_поиска),
OverflowError: Python int слишком велик для преобразования в C ssize_t

Кто-нибудь знает, что он был рассчитан и как его воспроизвести? Есть ли лучшая реализация алгоритма Шуфа для таких больших чисел?

407

1 + 3

эллиптические кривые

конечное поле

secp256k1

fgrieu

22.12.2022, 10:31

Примечание: порядок $n$ в `secp256k1` хорошо известен, и его легко _проверить_: выберите любую точку $T$ (кроме нейтральной $\mathcal O$) и проверьте $n\,T=\mathcal O$, что доказывает, что порядок $T$ делит $n$. Теперь проверьте, что $n$ простое и близко к $p$ (в пределах 30%; или [граница Хассеса](https://en.wikipedia.org/wiki/Hasse%27s_theorem_on_elliptic_curves)). Самостоятельно: имеем близкую причину на тему "Запросы литературы, софта или подобные рекомендации не по теме", так что вопрос в горячих водах; посмотрим, перевесит ли интерес вопроса этот общий запрет.

Ответить

Andy

22.12.2022, 14:43

@fgrieu, что такое нейтральный $\mathcal{O}$ `secp256k1`?

Ответить

fgrieu

23.12.2022, 06:33

Нейтральный $\mathcal O$ — это нейтральный элемент группы точек кривой. Эквивалентно, для всех точек $T$ кривой $T+\mathcal O=T=\mathcal O+T$. Ее также называют бесконечно удаленной точкой и обозначают $\infty$. У него нет координат $x$, $y$, удовлетворяющих уравнению кривой $y^2\equiv x^3+7\pmod p$.

Ответить

Рейтинг:2

Crypto

djao

22.12.2022, 05:02

ПАРИ включает (среди прочего) реализацию алгоритма Шуфа (точнее, алгоритма Шуфа-Элкиса-Аткина).

? р = 115792089237316195423570985008687907853269984665640564039457584007908834671663
%1 = 115792089237316195423570985008687907853269984665640564039457584007908834671663
? карточка (эллинит ([0,7], p))
%2 = 115792089237316195423570985008687907852837564279074904382605163141518161494337

Это с открытым исходным кодом, так что вы можете легко заглянуть внутрь.

Если вы не хотите устанавливать PARI, CoCalc позволяет запускать PARI (или Sage) в браузере. Просто запустите новый проект и внутри этого нового терминала Linux введите «gp», и вы готовы к работе в PARI.

В качестве альтернативы вы можете выполнить расчет непосредственно в Мудрец (которую вы также можете запустить с помощью CoCalc: New – Sage worksheet), но это не дает вам никакой новой реализации, поскольку Sage просто вызывает PARI для этой функции:

мудрец: p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
мудрец: EllipticCurve(GF(p), [0,7]).order()
115792089237316195423570985008687907852837564279074904382605163141518161494337

Для документации в PARI:

? ?эллкарта
ellcard(E,{p}): дана эллиптическая кривая E, определенная над конечным полем Fq, 
вернуть порядок группы E(Fq); для других полей определения K p должен 
определяют конечное поле вычетов (p простое число для K = Qp или Q; p максимальный идеал для 
K числовое поле), вернуть порядок (несингулярного) сокращения E.

Для документации в Sage:

мудрец: E = EllipticCurve(GF(p), [0,7])
мудрец: Э. порядок?
мудрец: E.порядок??

0 + 0

Admin