Tôi đã xem xét nội dung cơ bản của ecc và tìm thấy các ví dụ từ Internet sử dụng đường cong miền liên tục hoặc sử dụng số nguyên tố rất nhỏ P
như 17 trong một miền riêng biệt để hiển thị các điểm.
Tôi thực sự tò mò rằng nếu tôi có thể tìm thấy một điểm thực sự lớn P
trong thực tế. Ví dụ, secp256k1 đang sử dụng một P
=2^256â2^32â977 trong miền (p,a,b,G,n,h).
Dưới đây là mã python tôi sử dụng để trừ số nguyên có thể có của y khỏi việc giải phương trình với phạm vi số nguyên x
. Tôi ngạc nhiên rằng không có tìm thấy ngay cả trong phạm vi 1 triệu!
Vì vậy, câu hỏi của tôi là, mã bên dưới phải không? Và thứ hai, nếu nó đúng hoặc được sửa bởi một số chuyên gia thực sự, tôi nên thử phạm vi giá trị nào?
Tái bút
Tôi tự hỏi làm thế nào điểm máy phát điện g
cũng được chọn. Nhưng điều đó có thể cần hiểu sâu hơn về chủ đề này.
nhập toán
# secp256k1
# y**2 = x**3 + 7 (mod p)
P = 2**256 - 2**32 - 977
một = 0
B = 7
#nist P256
P = 115792089210356248762697446949407573530086143415290314195533631308867097853951
A = -3
B = 41058363725152142129326129780047268409114441015993725554835256314039467401291
xác định in_curve(x):
đường cong = x**3 + A*x + B
y_float = math.sqrt(đường cong)
nếu abs(math.modf(y_float)[0]) < 0,0001 hoặc \
(1 - abs(math.modf(y_float)[0]) < 0,0001):
# in(y_float)
# lỗi: y_int = int(math.modf(y_float)[1])
y_int = int(vòng(y_float))
nếu y_int * y_int == (đường cong):
in(y_int)
trả lại y_int
trở lại Không có
cho x trong phạm vi (1, 1000000):
y = in_curve(x)
nếu y không phải là Không có:
in(x, y)
cập nhật 1
Mã trước đó là sai, vì dấu phẩy động sqrt() sẽ gây ra lỗi không thể chấp nhận được khi chuyển đổi nó trở lại số nguyên.
Nhưng, sau khi thay thế toán.sqrt()
đến toán.isqrt()
, nó vẫn không làm cho mọi thứ trở nên hợp lý.
cập nhật 2
Nhờ những lời khuyên từ tất cả trả lời trong chủ đề. Sử dụng điểm tạo để xác minh thuật toán của tôi, giờ đây tôi biết rõ ràng tại sao mình thất bại.
Vấn đề là ngoài việc sử dụng %
cho tất cả phép nhân và phép cộng, tôi Nên cũng sử dụng căn bậc hai mô-đun để tìm giải pháp, thay vì căn bậc hai số nguyên cùng với %
. Đó hoàn toàn là một sự lạm dụng %
chắc chắn.
Mã sửa đổi vượt qua bài kiểm tra với một số vectơ kiểm tra.
nhập mô-đun_sqrt
# ví dụ. Tôi đã sử dụng mã từ https://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python
# vui lòng xin phép nếu việc sử dụng vượt quá phạm vi sở thích giáo dục và luôn liệt kê tín dụng là một con người tử tế ;-)
# nist P256, lấy từ https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186-draft.pdf
P = 115792089210356248762697446949407573530086143415290314195533631308867097853951
A = -3
B = 41058363725152142129326129780047268409114441015993725554835256314039467401291
Gx = 48439561293906451759052585252797914202762949526041747995844080717082404635286
Gy = 36134250956749795798585127919587881956611106672985015071877198253568414405109
chắc chắn get_y_in_curve(x):
y2 = x**3 + A*x + B
y_int = modul_sqrt(y2, P)
nếu y_int và ((y_int * y_int) % P) == (y2 % P):
trả lại y_int
trở lại Không có
khẳng định get_y_in_curve(Gx) == Gy