Đây là một câu trả lời mở rộng một chút;
Tôi đã tự hỏi liệu có cách nào khác để tính nghịch đảo nhân mô-đun của một điểm trên đường cong elip (như secp256k1) không? Hoặc có lẽ một lý do tại sao nó là không thể chứng minh?
Cộng đồng bitcoin thường gọi phép nhân vô hướng thông thường là phép nhân1. Những gì chúng ta định nghĩa là phép nhân vô hướng như
$$[k]G : = \underbrace{G + G + \cdots + G}_{k-times}$$ nói cách khác, thêm một điểm $k$ lần.
Đã có một vấn đề được xác định cho vấn đề này ( sử dụng phiên bản EC $r$ là thứ tự của phần tử cơ sở $G$, đường cong là bậc nguyên tố, và $E(K)$ là tập hợp các điểm của đường cong);
Các định nghĩa;
- CDH : tặng gấp ba lần $(G,[a]G,[b])$ tìm thấy $[ab]G$.
- Nghịch đảo-DH : được tặng một cặp $(G, [a]G) \in E(K) - \{\mathcal{O}\}$ của các phần tử của thứ tự nguyên tố $r$ Trong $E(K)$ để tính toán $[a^{-1}]G$.
- Vuông-DH: Bài toán tính Square-DH
được đưa ra $(G, [a]G )$ ở đâu $G \in E(K)$ có thứ tự chính $r$ để tính toán $[a^2]G$.
Giảm giá;
$\text{Nghịch đảo-DH} \leq_R \text{CDH}$.
Giả sử chúng ta có một lời tiên tri $O$ mà giải quyết $\text{CDH}$. Chúng ta được cho $(G,[a]G)$ như $\text{Nghịch đảo-DH}$ ví dụ và chúng tôi muốn tìm $P = [a]G$. Sau đó chúng tôi có $$G = [a^{-1}]P = [a^{-1}a]G = G$$
Bây giờ, hãy gọi nhà tiên tri $O$ với $O(P,G,G) = O(P,[a^{-1}]P,[a^{-1}]P) $ và kết quả đầu ra của Oracle $[a^{-2}]P$. Thay thế $P$ để có được $$[a^{-2}]P = [a^{-2}a]G = [a^{-1}]G$$ Điều này cho thấy sự giảm bớt.
$\text{Square-DH} \leq_R \text{Nghịch đảo-DH}$.
Hãy giả sử $O$ là một nhà tiên tri giải quyết $\text{Nghịch đảo-DH}$ và để cho $(G, P = [a]G )$ được cho. Nếu $P = \mathcal{O}$ Sau đó trở lại $\mathcal{O}$ khác $$O(P, G) = O(P , [a^{-1}]P) = [a]P = [a\cdot a]P = [a^2]P.$$ Điều này cho thấy sự giảm bớt.
Vì vậy chúng tôi có $\text{Square-DH} \leq_R \text{Nghịch đảo-DH} \leq_R \text{CDH}$. Nếu chúng ta có thể chỉ ra rằng $\text{CDH} \leq_R \text{Square-DH}$ sau đó chúng ta sẽ có sự tương đương.
$\text{CDH} \leq_R \text{Square-DH}$
để cho $O$ là một nhà tiên tri để giải quyết $\text{Square-DH}$ và chúng tôi được cho $(G,[a]G, [b]G)$ như một $\text{CDH}$ ví dụ.
Cuộc gọi $O$ hai lần với $O(G,[a]G)$ và $O(G,[b]G)$ để có được $P= [a^2]G$ và $Q= [b^2]G$, tương ứng.
Bây giờ một cuộc gọi nữa $O(G, P+Q) = O(G, [a+b]G)$ và lấy $$R = [(a+b)^2]G = [a^2+2ab+b^2]G.$$
Bây giờ cuối cùng tính toán $$[2^{-1}](R - (P+Q)) = [2^{-1} (a^2+2ab+b^2 -a^2 -b^2)]G = [ ab]G$$ Điều này cho thấy sự giảm bớt.
Do đó, chúng tôi có sự tương đương. Vì vậy, nếu $\text{CDH}$ thì khó rồi $\text{Nghịch đảo-DH}$ cũng khó. Chà, chúng tôi hy vọng điều này là dành cho những đối thủ phi lượng tử.
Có cách nào (ngoài lực lượng vũ phu) để tìm một số nguyên có kết quả là 1 khi khóa chung được nhân với số nguyên đó không?
Tôi có thể đọc điều này theo hai cách;
$1$ là danh tính của đường cong chúng ta viết $\mathcal{O}$, thì ta có đẳng thức $[r]P = \mathcal{O}$ cho mọi phần tử của một đường cong nguyên tố có thứ tự $r$. Đây là định nghĩa của thứ tự của một phần tử trong lý thuyết nhóm.
$1$ như $[a\cdot a^{-1}]G = [\color{red}{1}]G = G$ thì đây là $\text{Nghịch đảo-DH}$ như chúng ta đã bàn.
1Chà, người ta có thể (định nghĩa | gọi) phép cộng điểm là phép nhân điểm, tuy nhiên, phép cộng là lịch sử và tất cả các sách về đường cong Elliptic chính đều sử dụng phép cộng điểm; Trên các số phức, bất kỳ đường cong elip nào cũng có thể được nhận ra là $\mathbb C/\Gamma$
cho một số mạng $\Gamma$. Trong trường hợp này, phép cộng đơn giản xuất phát từ phép cộng tiêu chuẩn của các số phức.
