hai khóa ECDSA có khoảng cách gần nhau

Giả sử rằng một người sử dụng hai khóa riêng $x_1$ và $x_2$ để tạo hai khóa ECDSA công khai $y_1$ và $y_2$ (ví dụ: được sử dụng làm khóa công khai cho địa chỉ Bitcoin). Khoảng cách giữa $x_1$ và $x_2$ nhỏ (ví dụ: nhỏ hơn ${2^{20}}$). cái gì xấu về nó?

Tôi biết rằng nếu một người phá vỡ $x_1$, nó chắc chắn dẫn đến sự phá vỡ của $x_2$ với một nỗ lực tìm kiếm nhỏ. Nhưng hãy giả sử rằng ngoại trừ $|x_1 - x_2|$ là một số nhỏ, tất cả các phương pháp khác đều an toàn, ví dụ: không bao giờ sử dụng lại randon nonce khi ký, có bất kỳ kết quả xấu nào khác của nó không (ngoại trừ việc phá vỡ một đồng xu cũng giống như phá vỡ hai)?

Để cho $d=x_2-x_1$và để các khóa công khai ở điểm cơ sở nổi tiếng $G$. Do đó, các cặp khóa sẽ được $(x_1, X_1=x_1G)$ và $(x_2, X_2=x_2G)$.

Giá trị $d$ có thể bị cưỡng bức bằng cách sử dụng Bước Lớn-Bước Nhỏ phương pháp, sẽ mất ít hơn một giây trên CPU hiện đại khi $n=20$.

Nếu bạn sử dụng chữ ký Schnorr để ký một tin nhắn $m$ sử dụng $X_1$, bạn sẽ tạo cặp chữ ký $(c, r_1)$ bằng cách chọn một nonce ngẫu nhiên thống nhất $k$, rồi tính $c=H(kG\mathbin\| m)$ và $r_1=k-cx_1$.

Chữ ký được xác minh bằng cách kiểm tra $c\overset{?}{=}H(r_1G+cX_1 \mathbin\| m)$.

Kẻ tấn công, người đã cưỡng bức vũ phu $d$, sau đó có thể tạo chữ ký trên cùng một thư nhưng dường như được ký bằng khóa riêng tư khác của bạn $x_2$, như sau:

Các giá trị của $k$ và $c$ sẽ vẫn như cũ. Sau đó tính toán $r_2=r_1-cd$. Chữ ký giả mạo là cặp $(c, r_2)$.

Chữ ký sẽ được xác minh bằng cách kiểm tra xem $c\overset{?}{=}H(r_2G+cX_2 \mathbin\| m)$.

Điều này sẽ xác minh thành công nếu $kG==r_2G+cX_2$, điều này sẽ đúng nếu $k==r_2+cx_2$.

Bằng cách thay thế $r_2==r_1-cd$ và $x_2==d+x_1$, chúng ta có thể thấy rằng điều này sẽ đúng nhờ vào sự lựa chọn của chúng ta $r_2$.

Cuộc tấn công này chỉ hoạt động nếu hàm băm hoặc thông báo không liên kết chữ ký với một khóa công khai cụ thể. Nếu giao thức yêu cầu rằng $c$ thay vào đó được tính như $c=H(kG\mathbin\| X_1\mathbin\| m)$, cuộc tấn công sẽ không hoạt động vì giá trị của $c$ không thể sử dụng lại giữa các chữ ký (vì người xác minh sẽ xác minh chữ ký bằng cách nối $X_2$ bên trong hàm băm thay vì $X_1$).