Điểm:2

Tại sao r được sử dụng trong chữ ký ECDSA trong khi R trong chữ ký Schnorr?

lá cờ br

Trong chữ ký Schnorr (R, s), R được sử dụng. Nhưng trong chữ ký ECDSA (r, s), r được sử dụng, là tọa độ x của R. Tại sao lại có sự khác biệt?

kelalaka avatar
lá cờ in
Bằng sáng chế của Schnorr!
lá cờ br
ECDSA không thể sử dụng R do bằng sáng chế?
Điểm:4
lá cờ ng

Trong chữ ký Schnorr $(R,s)$, $R$ Được sử dụng. Nhưng trong chữ ký ECDSA $(r,s)$, $r$ được sử dụng, đó là tọa độ x của $R$.

Khẳng định đó là không chính xác về mặt kỹ thuật:

  • Trong chữ ký Schnorr (thay thế.) như được xác định ban đầu, thành phần đầu tiên của chữ ký là một hàm băm, không phải là một phần tử nhóm, ít hơn nhiều là một điểmâ trên một nhóm Đường cong Elliptic, vốn không được sử dụng phổ biến trong mật mã.
  • Trong định nghĩa của Chữ ký ECDSA, thành phần đầu tiên $r$ của chữ ký là tọa độ x $x_R$ của một điểm trên Đường cong Elliptic, biến thành một số nguyên, sau đó giảm modulo thứ tự nhóm $n$ (sau đó được chuyển thành một chuỗi phụ, nhưng chúng tôi sẽ bỏ nó sang một bên); nó không chỉ $x_R$.

Tuy nhiên, phần cốt lõi của khẳng định đó có một vài điều chỉnh:

  • Chữ ký Schnorr trong sách giáo khoa hiện đại được xác định cho một nhóm tùy ý trong đó Bài toán logarit rời rạc khó, với hai biến thể chính tùy theo thành phần đầu tiên của chữ ký có phải là
    • Hàm băm của (ít nhất) tin nhắn và phần tử nhóm $R$, như trong chữ ký gốc của Schnorr.
    • Phần tử nhóm A (biểu diễn bit duy nhất của a) $R$, như trong ví dụ EdDSA. Đó là biến thể mà khẳng định áp dụng cho.
  • Nhóm đã nói thường là một nhóm con Đường cong Elliptic theo thứ tự nguyên tố $n$ của một đường cong Elliptic trên một lĩnh vực $\mathbb F_{p^m}$, và thông thường $m=1$, do đó tọa độ x $x_R$ của $R$ là một số nguyên trong $[0,p)$.
  • Đối với các đường cong phổ biến như vậy $n\xấp xỉ p$, do đó với $r:=x_R\bmod n$ nó giữ $r=x_R$ với xác suất cao ngay cả khi $n<p$ (ví dụ. secp256k1, secp256r1) hoặc chúng ta có thể chọn Đường cong Elliptic với $n>p$.

Bây giờ chúng ta có một khẳng định đúng, chúng ta có thể hỏi:

Tại sao sự khác biệt?

Bởi vì ECDSA là một sự thích ứng với nhóm Elliptic Curve của DSA, trong đó thành phần đầu tiên của chữ ký là phần tử nhóm được rút gọn theo modulo thứ tự nguyên tố của nhóm. Trong DSA, việc giảm đó là để rút ngắn thành phần đầu tiên của chữ ký. Lý do tại sao DSA sử dụng kỹ thuật đó thay vì hàm băm, như trong chữ ký Schnorr ban đầu, có thể là

  • Chữ ký gốc của Schnorr được bao phủ bởi một bằng sáng chế, bao gồm ở Mỹ, và do đó có sự quan tâm đến một phương pháp khác¹.
  • DSA đã gần hơn với nghiên cứu tốt chữ ký ElGamal.
  • Các nguyên Chữ ký Schnorr, do hẹp $k$-bit băm (và trái ngược với chữ ký Schnorr hiện đại với hàm băm rộng hơn, trong cả hai biến thể ở trên):
    • Không thể sử dụng một cách an toàn như một cam kết của thông báo đã được ký: người nắm giữ khóa riêng tư ký một thông báo và có thể chọn nó một phần (ví dụ: thay đổi một vài byte ở cuối) có thể cố tình làm như vậy theo cách sao cho một thông báo khác có ý nghĩa khác của sự lựa chọn của họ có cùng chữ ký. Cuộc tấn công là một cuộc tấn công va chạm tiền tố được chọn trên $k$-bit băm, với chi phí dự kiến ​​ít hơn $2^{k/2+1,4}$ băm. Điều này làm tăng nguy cơ từ chối chữ ký và về mặt pháp lý có thể gây ra Sợ hãi, Không chắc chắn và Nghi ngờ.
    • Sẽ dễ bị tấn công giả định (thứ nhất hoặc thứ hai) vào đầu vào thông báo của hàm băm, bao gồm cả các hàm băm trong một tập hợp con mỏng của $\{0,1\}^k$, chi phí dự kiến $2^k$ băm; khi DSA (nhờ hàm băm rộng hơn nhiều) có rất nhiều lợi nhuận trên đó.

DSA sử dụng một nhóm Schnorr, đó là một nhóm con tuần hoàn của nhóm nhân modulo một số nguyên tố $p$. Về cơ bản, ECDSA thay đổi điều đó thành một Nhóm đường cong elip trên một trường Galois, cho phép khóa công khai nhỏ hơn và tính toán nhanh hơn. Nguyên tắc giảm thành phần đầu tiên của modulo chữ ký của DSA giữ nguyên thứ tự nhóm. Việc chuyển đổi trước cần thiết từ phần tử trường thành số nguyên được thực hiện theo tọa độ x $x_R$, phớt lờ $y_R$. Ngẫu nhiên, điều đó dẫn đến mất tài sản bảo đảm: ECDSA không sEUF-CMA, khi DSA là, bởi vì $R$ và ngược lại với $R$ trong nhóm Đường cong Elliptic có chung $x_R$, cho phép biến chữ ký ECDSA hợp lệ thành chữ ký hợp lệ khác cho cùng một thông báo bằng cách thay đổi $s$ đến $-s$ modulo thứ tự nhóm.


¹ Claus-Peter Schnorr khẳng định phương pháp của DSA thuộc bằng sáng chế của ông. Điều đó không bao giờ đi đến thử thách của tòa án. Mặc dù phần lớn DSA có thể được đọc trong mô tả của bằng sáng chế, nhưng việc khiếu nại vi phạm sẽ là không thể với các khiếu nại như hiện tại và một cuộc chiến khó khăn với các khiếu nại được viết lại. Cụ thể, nó mô tả một hàm băm có đầu vào bên cạnh thông báo, khi chỉ có thông báo được băm trong DSA.

lá cờ br
Vì vậy, về mặt kỹ thuật, ECDSA cũng có thể sử dụng (R, s) làm chữ ký?
fgrieu avatar
lá cờ ng
@sinoTrinity: vâng, chúng tôi có thể sửa đổi một chút ECDSA để có biểu diễn nhị phân của $R$ làm thành phần đầu tiên của chữ ký và yêu cầu trình xác minh biến nó thành một số nguyên sau đó sử dụng modulo $n$. Có vẻ như điều đó có thể khôi phục sEUF-CMA [ nhưng sẽ làm như vậy bằng cách tăng kích thước chữ ký lên ít nhất 1 bit, thay vì giảm 1 bit như thay thế $s$ bằng $\min(s,n-s)$ ]. Và đó vẫn không phải là bất kỳ dạng nào trong hai dạng chữ ký EC-Schnorr, vì chỉ có thông báo đi vào hàm băm của ECDSA, chứ không phải thông báo và điểm trong chữ ký EC-Schnorr (tất cả các biến thể).

Đă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.