Điểm:2

Crypto

Bổ sung điểm ECC trên tọa độ Jacob - Không giao hoán?

LeonMSH

04:58, 13/12/2022

Tôi có một tập lệnh python thực hiện bổ sung điểm ECC (dán mã bên dưới), nó chỉ đơn giản thực hiện P = Q1 + Q2 khi phối hợp Jacob. Tuy nhiên, khi thực hiện một số phép thử hồi quy, tôi nhận thấy nếu hoán đổi vị trí P1 và P2 sẽ nhận được các kết quả khác nhau, trong đó có một kết quả đúng. Dưới đây là một ví dụ chỉ cần sử dụng điểm secp256k1 G làm một điểm và 2*G làm điểm thứ 2 để chạy thử nghiệm.

Câu hỏi của tôi (Cập nhật nhận xét sau khi nhận được trả lời từ @fgrieu) 1). Phép cộng điểm ECC trên một đường cong--đó có phải là Giao hoán (nên là) không?

2). Tôi nhận thấy rằng đối với các kết quả, tọa độ x giống nhau trong khi y/z khác nhau-- (chúng biểu thị giống nhau trên tọa độ affine).

3). Dựa trên các đề xuất, tôi cập nhật tập lệnh để hoàn thành.

def Point_Add(bản thân, Q1, Q2):
    nếu (Q1.x==self.p): 
        trở lại quý 2
    nếu (Q2.x==self.p):
        trở lại Q1
    Q1z2 = (Q1.z*Q1.z) % self.p
    Q2z2 = (Q2.z*Q2.z) % self.p

    U1 = (Q1.x*Q2z2) % self.p
    U2 = (Q2.x*Q1z2) % self.p

    S1 = (Q1.y*Q2z2*Q2.z) % self.p
    S2 = (Q2.y*Q1z2*Q1.z) % self.p
    nếu (U1 == U2): 
        if (S1!=S2): # cặp đối diện, tức là Q1 = -Q2
            tự trả về.Unit
        khác: # Q1 = Q2
            tự trả về.Point_Double(Q1)

    H = (U2-U1) % self.p   
    R = (S2-S1) % self.p
    H2 = (H*H) % self.p
    H3 = (H2*H) % self.p

    x3 = (R*R-H3-2*U1*H2 ) % self.p
    y3 = (R*(U1*H2-x3)-S1*H3 ) % self.p
    z3 = (H*Q1.z*Q2.z) % self.p

trả lại JBPoint(self, x3, y3, z3)

Kết quả kiểm tra
Gỡ lỗi 1: kiểm tra P=Q1+Q2:
Điểm.X(Jacob): 0xca90ef9b06d7eb51d650e9145e3083cbd8df8759168862036f97a358f089848
Điểm.Y(Jacob): 0x435afe76017b8d55d04ff8a98dd60b2ba7eb6f87f6b28182ca4493d7165dd127
Điểm.Z(Jacob): 0x9242fa9c0b9f23a3bfea6a0eb6dbcfcbc4853fe9a25ee948105dc66a2a9b5baa
Điểm.X(affine): 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9
Điểm.Y(affine): 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672
Point.X(affine): 112711660439710606056748659173929673102114977341539408544630613555209775888121
Điểm.Y(affine): 25583027980570883691656905877401976406448868254816295069919888960541586679410
Gỡ lỗi 2: kiểm tra P=Q2+Q1:
Điểm.X(Jacob): 0xca90ef9b06d7eb51d650e9145e3083cbd8df8759168862036f97a358f089848
Điểm.Y(Jacob): 0xbca50189fe8472aa2fb007567229f4d458149078094d7e7d35bb6c27e9a22b08
Điểm.Z(Jacob): 0x6dbd0563f460dc5c401595f1492430343b7ac0165da116b7efa23994d564a085
Điểm.X(affine): 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9
Điểm.Y(affine): 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672
Point.X(affine): 112711660439710606056748659173929673102114977341539408544630613555209775888121
Điểm.Y(affine): 25583027980570883691656905877401976406448868254816295069919888960541586679410

127

1 + 0

đường cong elip

secp256k1

Điểm:4

Crypto

fgrieu

06:29, 13/12/2022

Cộng điểm ECC có tính chất giao hoán.
Vấn đề gặp phải là trong hệ tọa độ Jacobian, một điểm không phải là trung tính có một số bộ ba tọa độ hợp lệ như nhau $(x,y,z)$, tất cả tương ứng với cùng $(z^{-2}\,x,z^{-3}\,y)$ trong hệ tọa độ Descartes. Bình đẳng có thể được kiểm tra như ${z_2}^2\,x_1-{z_1}^2\,x_2\bmod p=0$ và ${z_2}^3\,y_1-{z_1}^3\,y_2\bmod p=0$ (Nếu có một phím tắt ngoài việc sử dụng lại $z^2$ để tính toán $z^3$ giả sử các điểm nằm trên đường cong, tôi muốn tìm hiểu nó).
Các mã ban đầu được hiển thị không xử lý trường hợp Q1 và quý 2 đại diện cho cùng một điểm (nghĩa là nhân đôi điểm). Hơn nữa, không có gì xác định cách trung tính được thể hiện trên đầu vào và đầu ra. Điều đó đã được sửa ngay bây giờ.

Cập nhật, mở rộng lần 3: có một số trường hợp đặc biệt phải cộng điểm $Q_1+Q_2$, cần được xử lý đặc biệt:

khi nào $Q_1$ là trung lập, kết quả là $Q_2$;
khi nào $Q_2$ là trung lập, kết quả là $Q_1$;
khi nào $Q_1=Q_2$ (trong định nghĩa trong 2), đó là nhân đôi điểm;
khi nào $Q_1=-Q_2$, kết quả là trung lập.

Có nhiều cách để xử lý việc này. Nếu được yêu cầu sửa đổi Mã Python ban đầu được hiển thị, Trước tiên, tôi sẽ thêm các tuyên bố từ chối trách nhiệm nổi bật rằng mã thậm chí không cố gắng giảm thiểu các cuộc tấn công theo thời gian (dù sao thì điều này gần như không thể thực hiện hoàn hảo trong Python), do đó không được sử dụng khi đó là sự cố (thường bao gồm tính toán chữ ký); sau đó tôi có thể sẽ:

xác định rằng bất cứ điều gì với $z=0$ là trung lập và sử dụng trường hợp này để xử lý hai trường hợp đầu tiên theo cách rõ ràng và trường hợp thứ tư không cần thêm mã.
phát hiện ra rằng $H=0$ và $R=0$, cho biết chúng ta đang nhân đôi điểm và do đó cần các công thức khác.

Mã hiện được hiển thị sử dụng một phương thức khác (tôi nghĩ là hợp lệ) trong đó $(tr,0,1)$ là trung lập. Điều đó cũng hoạt động, với nhược điểm về hiệu suất và kích thước mã (có thể hầu như không đo lường được):

mã rõ ràng là cần thiết cho $Q_1=-Q_2$ trường hợp không trung lập, khi nó không dành cho trung tính được định nghĩa là $(tr,0,1)$. Trong sử dụng thực tế hợp pháp trong mật mã, trường hợp đặc biệt đó rất hiếm nên việc loại bỏ nó sẽ cải thiện hiệu suất.
hai thử nghiệm ban đầu cho trung tính lớn hơn và chậm hơn một chút.

Một lần nữa, nên thêm các nhận xét rằng mã này không cố gắng tránh các phụ thuộc về thời gian phụ thuộc vào dữ liệu, điều này có thể tạo thành một kênh phụ.

0 + 8

LeonMSH

08:10, 13/12/2022

Cảm ơn rất nhiều vì đã phản hồi nhanh chóng... Q2). Điều đó có nghĩa là cả hai kết quả tôi nhận được đều hợp lệ (đại diện cho cùng một điểm trên tọa độ Descartes)? Tôi có thể đặt thêm một số hạn chế nào nữa không, để tôi có thể có cùng tọa độ Jacob duy nhất, tôi có thể chuyển đổi ngược lại để kiểm tra tọa độ Descartes cho điều đó nhưng vì tôi có một số bài kiểm tra điểm chuẩn cần thực hiện sau để đảm bảo tọa độ Jacob hoạt động hoàn hảo, không có giá trị duy nhất thì rất bất tiện). 3)Có bạn tìm thấy nó, tôi chưa kiểm tra trường hợp đặc biệt, điều đó nên được thêm vào;

Hồi đáp

LeonMSH

08:23, 13/12/2022

Có, tôi thực hiện kiểm tra tọa độ affine, các điểm kết quả thực sự giống nhau trên affine. Câu hỏi còn lại của tôi sẽ là: có cách nào (hoặc khó) để tôi luôn có được tọa độ Jacob giống nhau không (tôi không quan tâm đến phạm vi bảo hiểm, chỉ quan tâm đến tính chính xác.

Hồi đáp

fgrieu

08:48, 13/12/2022

@LeonMSH: cách duy nhất tôi thấy để "luôn có cùng tọa độ Jacob[ian]" là chuẩn hóa thành cùng một $z$, ví dụ: $z=1$, nghĩa là thay đổi $(x,y,z)$ của kết quả thành $(z^{-2}\,x,z^{-3}\,y,1)$. Nhưng điều đó phủ nhận cơ sở lý luận của việc sử dụng tọa độ Jacobian ngay từ đầu, đó là để tránh nghịch đảo mô đun.

Hồi đáp

111

11:09, 13/12/2022

Có thể, nếu bạn chỉ sử dụng tọa độ affine. Có tọa độ affine, giả sử $(a,b)$ để có tọa độ xạ ảnh của điểm này, chỉ cần gửi nó tới $[a:b:1].$ Cần đặc biệt cẩn thận đối với điểm ở vô cực. Nếu bạn cộng các điểm $(a_1,b_1)$ và $(a_2,b_2)$, bạn phải kiểm tra xem $b_1=b_2.$ Việc cộng các điểm này có phải là điểm ở vô cực không $[0:1:0]$ (sử dụng mô hình Weierstrass). Hy vọng rằng sẽ giúp.

Hồi đáp

LeonMSH

02:36, 16/12/2022

@111, đối với điểm affine P1(a1,b1) và P2(a2,b2), nếu b1=b2, P1+P2 có phải là điểm gấp đôi không? Tôi nghĩ bạn có nghĩa là trường hợp b1 =-b2?

Hồi đáp

LeonMSH

02:48, 16/12/2022

@fgrieu về tọa độ điểm vô cực O Jacobian - Tôi thấy các cách biểu diễn khác nhau, như O= (p, 0, 1), (0, 1, 0), (1 , 1 , 0) , thì đâu là đúng?

Hồi đáp

111

14:43, 16/12/2022

@LeonMSH đúng. b1=-b2.

Hồi đáp

LeonMSH

04:44, 17/12/2022

@fgrieu Tôi cập nhật tập lệnh, nhân tiện, điểm Đơn vị tôi đang sử dụng cho mã này là O(p,0,1) chứ không phải điểm với z=0.. Nó vẫn hoạt động. đó là lý do tại sao tôi đặt câu hỏi liên quan đến điểm O, đối với điểm jacob..

Hồi đáp

Phan Văn Trường

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

EN: ECC Point Addition on Jacob coordinate -- Not Commutative?

TH: การเพิ่มจุด ECC บนพิกัด Jacob -- ไม่สับเปลี่ยน?

RO: Adăugarea punctului ECC pe coordonatele Jacob -- Nu este comutativă?

RU: Добавление точки ECC к координате Джейкоба — не коммутативно?

VI: Bổ sung điểm ECC trên tọa độ Jacob - Không giao hoán?

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.