Điểm:1

Crypto

Làm thế nào để tính thứ tự của secp256k1?

Andy

21:16, 21/12/2022

đường cong elip secp256k1 được định nghĩa là $y^2 = x^3 + 7$. Số nguyên tố cho trường được đặt thành:

p = 115792089237316195423570985008687907853269984665640564039457584007908834671663

Vì vậy, bây giờ, người ta có thể tính toán thứ tự bằng cách sử dụng Thuật toán của Schoof. Có một triển khai Python được cung cấp tại đây: https://github.com/pdinges/python-schoof

Tuy nhiên, dường như quá tốn thời gian để tính toán thứ tự cho các số nguyên tố lớn. Hơn nữa, việc triển khai dường như không có khả năng tính toán nó cho một số nguyên tố lớn như vậy.

root@78774381cc80:/home/python-schoof# python3 reduce_computation_schoof.py 17 0 7
Đếm số điểm của y^2 = x^3 + 0x + 7 trên GF<17>: 18
root@78774381cc80:/home/python-schoof# python3 reduce_computation_schoof.py 115792089237316195423570985008687907853269984665640564039457584007908834671663 0 7
Đếm số điểm của y^2 = x^3 + 0x + 7 trên GF<115792089237316195423570985008687907853269984665640564039457584007908834671663>: Traceback (lần gọi gần đây nhất):
  Tệp "reduced_computation_schoof.py", dòng 268, trong <module>
    người chạy.run()
  Tệp "/home/python-schoof/support/running.py", dòng 498, đang chạy
    kết quả = self.__algorithm( *item, output=self.__output)
  Tệp "reduced_computation_schoof.py", dòng 258, trong reduce_computation_schoof_algorithm
    thứ tự = p + 1 - frobenius_trace( EllipticCurve( FiniteField(p), A, B ) )
  Tệp "reduced_computation_schoof.py", dòng 55, trong frobenius_trace
    len(search_range),
OverflowError: Python int quá lớn để chuyển đổi thành C ssize_t

Có ai đó biết nó đã được tính toán và làm thế nào để tái tạo nó? Có triển khai tốt hơn Thuật toán của Schoof cho số lượng lớn như vậy không?

407

1 + 3

đường cong elip

trường hữu hạn

secp256k1

fgrieu

10:31, 22/12/2022

Lưu ý: Thứ tự $n$ của `secp256k1` đã được nhiều người biết đến và thật dễ dàng để _xác minh_ nó: chọn bất kỳ điểm nào $T$ (ngoài $\mathcal O$ trung tính) và kiểm tra $n\,T=\mathcal O$, điều này chứng tỏ thứ tự của $T$ chia cho $n$. Bây giờ hãy kiểm tra xem $n$ có phải là số nguyên tố và gần với $p$ (trong phạm vi 30% sẽ đúng; hoặc [Hasses' bound](https://en.wikipedia.org/wiki/Hasse%27s_theorem_on_elliptic_curves)). Một cách độc lập: chúng tôi có lý do chặt chẽ về giai điệu "Yêu cầu về tài liệu, phần mềm hoặc các đề xuất tương tự là lạc đề", vì vậy câu hỏi là ở vùng nước nóng; chúng ta sẽ xem liệu mối quan tâm của câu hỏi có lớn hơn sự cấm đoán chung đó hay không.

Hồi đáp

Andy

14:43, 22/12/2022

@fgrieu $\mathcal{O}$ trung tính của `secp256k1` là gì?

Hồi đáp

fgrieu

06:33, 23/12/2022

Trung lập $\mathcal O$ là phần tử trung lập của nhóm các điểm của đường cong. Tương tự, đối với tất cả các điểm $T$ của đường cong, $T+\mathcal O=T=\mathcal O+T$. Nó còn được gọi là điểm ở vô cực và được ghi là $\infty$. Nó không có tọa độ $x$, $y$ thỏa mãn phương trình của đường cong $y^2\equiv x^3+7\pmod p$.

Hồi đáp

Điểm:2

Crypto

djao

05:02, 22/12/2022

PARI bao gồm (trong số nhiều thứ khác) việc triển khai thuật toán Schoof (cụ thể hơn là thuật toán Schoof-Elkies-Atkin).

? p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
%1 = 115792089237316195423570985008687907853269984665640564039457584007908834671663
? ellcard(ellinit([0,7], p))
%2 = 115792089237316195423570985008687907852837564279074904382605163141518161494337

Đó là mã nguồn mở, vì vậy bạn có thể dễ dàng nhìn vào bên trong.

Nếu bạn không muốn cài đặt PARI, CoCalc cho phép bạn chạy PARI (hoặc Sage) trong trình duyệt. Chỉ cần bắt đầu một dự án mới và bên trong thiết bị đầu cuối Linux mới đó, hãy nhập "gp" và bạn đã tắt và chạy trong PARI.

Ngoài ra, bạn có thể thực hiện tính toán trực tiếp trong Hiền nhân (mà bạn cũng có thể chạy qua CoCalc: Bảng tính â Sage mới), nhưng điều này không cung cấp cho bạn bất kỳ triển khai mới nào vì Sage chỉ gọi PARI cho chức năng này:

hiền triết: p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
hiền triết: EllipticCurve(GF(p), [0,7]).order()
115792089237316195423570985008687907852837564279074904382605163141518161494337

Đối với tài liệu trong PARI:

? ?ellcard
ellcard(E,{p}): cho một đường cong elip E xác định trên trường hữu hạn Fq, 
trả về thứ tự của nhóm E(Fq); đối với các trường khác của định nghĩa K, p phải 
xác định một trường thặng dư hữu hạn, (p nguyên tố cho K = Qp hoặc Q; p một lý tưởng cực đại cho 
K một trường số), trả về thứ tự rút gọn (không phải số ít) của E.

Đối với tài liệu trong Sage:

hiền triết: E = EllipticCurve(GF(p), [0,7])
hiền triết: E.order?
hiền triết: E.order??

0 + 0

Phan Văn Trường

Câu hỏi này là trong các ngôn ngữ khác: