lời mở đầu
Một mặt của sự an toàn của ECDSA phụ thuộc vào bảo mật logarit rời rạc của Đường cong Elliptic đã sử dụng (gọi nó là $E$). Các đường cong elip tạo thành một nhóm đại số cộng có thứ tự $n$. Nếu nhóm được hình thành bởi đường cong được sử dụng là một nhóm chung thì cuộc tấn công cổ điển tốt nhất là $\mathcal{O}(\sqrt{2^n})$ - Pollard's Rho.
ECDSA
khóa riêng $k$ được tính như một số nguyên ngẫu nhiên trong khoảng $[1,n-1]$ và giữ bí mật mọi lúc. Lưu ý rằng khóa riêng $k$ là một số nguyên, không phải là một điểm trên đường cong $E$.
khóa công khai $P$, mặt khác, được tính như một điểm $p = [k]G$ ở đâu $G$ là điểm cơ sở của đường cong được xác định trong các tiêu chuẩn và hoạt động $[k]G$ được gọi là phép nhân vô hướng được định nghĩa là;
$$[k]G : = \underbrace{G + G + \cdots + G}_{k-times}$$
Điều này không nên nhầm lẫn với phép nhân, không, đây là những gì chúng tôi viết để đơn giản hóa $k$-lần bổ sung.
Các $[k]P$ có thể được tính toán ít nhất bằng thuật toán nhân đôi và cộng để nhanh chóng tính toán trong $\mathcal{O}(\log k)$-thời gian.
Các điểm
Bây giờ như chúng ta có thể thấy, ngay cả $k=0$ không phải là vấn đề trong ECDSA vì nó không phải là giá trị hợp lệ cho $k$.
Nếu nhật ký rời rạc dễ dàng
Nếu nhật ký rời rạc dễ dàng trên đường cong này, thì đó là việc tìm kiếm $k$ được cho $[k]G$, thì mọi giá trị đều dễ dàng suy ra.
Nếu đường cong được mở cửa sau với một điểm cơ sở khác $H$, tức là ai đó có thể giải logarit rời rạc về cơ số $H$ trên nhóm đường cong. Sau đó, họ có thể sử dụng điều này để giải quyết Dlog trên cơ sở $G$ rất dễ dàng;
- Họ tính toán $G = [t]H$ vì $t \in [1,n-1]$ chỉ một lần
- Họ giải quyết $P =[k\cdot a]G$ đến cơ sở $H$ vì $a \in [0,n-1]$. Một lần $ka$ được tìm thấy $k$ có thể được tính như $k = a \cdot k \cdot a^{-1}$ kể từ khi chúng ta biết $a$ và $a^{-1} \cdot a = 1 \bmod n$.
Nếu nhật ký rời rạc không dễ dàng
Trong trường hợp này, người ta có thể tính toán một số trong số chúng với sức mạnh tối đa của chúng. Giả sử bạn có thể sử dụng siêu máy tính Summit và bạn có khả năng tính toán $2^{70}$ nhân đôi và cộng cho một số nhất định $t$. Các em tính toán và lập bảng băm để truy vấn nhanh sự tồn tại của log rời rạc trong dãy $[1,2^{70}]$. Quá trình chạy trong một năm và dung lượng lưu trữ cần thiết là $2^{70}*256*3$-bit (~147574 Petabyte). Chà, lưu trữ là một trong những vấn đề và vấn đề khác là bảng băm có thể không $\mathcal{O}(1)$ nữa không. Giả sử rằng bạn đã giải quyết được vấn đề này, thì xác suất mà bạn có thể tìm thấy một khóa riêng đã cho từ khóa chung là bao nhiêu. Giá trị chính xác phụ thuộc vào nhóm đường cong, giả sử người ta sử dụng nhóm đường cong có kích thước $2^{256}$ để được an toàn chống lại các cuộc tấn công Dlog tiêu chuẩn. Xác suất trúng là $$\frac{2^{70}}{2^{256}} = \frac{1}{2^{186}}.$$ Điều này thậm chí có ít xác suất hơn nhiều so với $\dfrac{1}{100}$, vì vậy chúng tôi nói điều đó sẽ không xảy ra!
Thay vì các lựa chọn ngẫu nhiên tuần tự của $t$s thay đổi kết quả, KHÔNG!
Lưu ý đặc biệt 1:0x0000...0000 là mã hóa thông thường của $\mathcal{O}(n)$ từ $(0,0)$ không nằm trên đường cong. Điều này không được chấp nhận như một khóa công khai hợp lệ trong GIÂY 1 Phiên bản. 2.0 mục 3.2.2.1.
Lưu ý đặc biệt 2: Một số đường cong elip là đường cong nguyên tố, điều này có nghĩa là nhóm mà chúng tạo thành có thứ tự nguyên tố. Trong trường hợp này, mọi phần tử đều là trình tạo, ngoại trừ phần tử nhận dạng. Nếu thứ tự không phải là số nguyên tố, như trong Curve25519, thì chúng ta có đồng sáng lập $h = \#E(K)/n$ ở đâu $n$ là số nguyên tố lớn nhất chia bậc của đường cong. Nếu sử dụng nhóm đầy đủ, có thể dễ dàng nhận thấy các phần tử có thứ tự nhỏ, chỉ cần kiểm tra $[o]P = \mathcal{O}$ hay không, ở đâu $o$ là thứ tự nhỏ. Đối với Curve25519, $o$ giá trị là $2,4,$ và $8$. Đây không phải là vấn đề bảo mật vì người dùng hợp pháp luôn chọn $k \equiv 0 \pmod 8$.
