TLDR: Nếu chúng tôi chuyên môn hóa một điểm máy phát điện $G$ của một nhóm Đường cong Elliptic theo thứ tự nguyên tố, chúng ta có thể nhất quán định nghĩa GCD của hai điểm cho trình tạo đó. Nhưng chúng ta không thể hiệu quả tìm thấy nó cho các điểm tùy ý và một nhóm lợi ích mật mã, trong đó Bài toán logarit rời rạc là khó.
Trước khi tìm một thứ gì đó, chúng ta phải biết nó là gì. Do đó, câu hỏi phụ của poncho:
'GCD của hai điểm trên một đường cong nguyên tố' nghĩa là gì?
GCD là viết tắt của Ước chung lớn nhất. Như vậy chúng ta cần định nghĩa ba khái niệm
- "Đường cong nguyên tố" là gì. Trong này, đường cong viết tắt của Đường cong elip. Và nguyên tố là một tài sản của một trong hai
- cơ sở trường hữu hạnthứ tự của (thứ tự nguyên tố đó thường được ghi chú $p$, và khi đó trường đơn giản là các số nguyên modulo $p$);
- thứ tự của đường cong, tức là có bao nhiêu phần tử trong nhóm hữu hạn của các điểm của đường cong, bao gồm cả trung tính;
- hoặc thứ tự của một phân nhóm của đường cong (sau đó thường được ghi chú $n$, như chúng ta sẽ làm).
- Khái niệm "ước số" của một điểm trên đường cong elip nguyên tố, mà chúng ta sẽ giả định là một điểm của đường cong elip với một số tính chất được xác định.
- Khái niệm "lớn nhất" giữa các điểm của đường cong elip.
Chúng ta có thể định nghĩa những điều như vậy một cách nhất quán! Chúng tôi cho rằng một "đường cong nguyên tố" là một số nhóm con của thứ tự nguyên tố $n$ của một đường cong elip (có lẽ là toàn bộ đường cong, có thể sử dụng trường nguyên tố; ví dụ: secp256k1, secp256r1), và $G$ một điểm nhất định của đường cong / một yếu tố của nhóm, không phải là trung tính. Bây giờ bộ $n$ số nguyên trong $[0,n)$ đẳng cấu với đường cong, bởi đẳng cấu tầm thường $i\mapsto i\,G$ định nghĩa như bình thường: $0\,G$ là trung lập của nhóm, $i\,G$ Là $((i-1)\,G)+G$ bất cứ gì $i\in[1,n)$ với $+$ luật của nhóm.
Chúng ta có thể định nghĩa "số chia" và "lớn nhất" trên tập hợp $[0,n)$. Và chúng ta có thể xác định GCD của hai phần tử của tập hợp đó (cùng với phần tùy ý $\gcd(0,0)=0$ ). Sau đó, chúng ta có thể sử dụng đẳng cấu này để xác định Ước chung lớn nhất của hai điểm của Nhóm đường cong Elliptic theo thứ tự nguyên tố được cung cấp với một điểm tạo $G$.
Nói cách khác, tôi xác định GCD của các điểm $P$ và $Q$ là điểm phù hợp với khóa riêng (đối với trình tạo $G$) là GCD của các khóa riêng phù hợp $P$ và $Q$, với khóa riêng phù hợp một số nguyên trong $[0,n)$.
Nếu chúng ta có thể giải một cách hiệu quả Bài toán Logarit rời rạc trong nhóm được xem xét, thì chúng ta có thể tính GCD một cách hiệu quả (chúng ta giải hai DLP, tính GCD của các số nguyên và quay lại đường cong).
Cập nhật: điều ngược lại đúng ở một mức độ nào đó. Nếu chúng ta có thể tính toán hiệu quả GCD của không tí nào hai điểm $P$ và $Q$, thì chúng ta có thể sử dụng thuật toán đó để tính Logarit rời rạc một cách hiệu quả $i$ của bất kỳ $P$. Phác thảo: chúng tôi chọn các số nguyên tố đầu tiên $r_j$ cho đến khi $n<\prod r_j$, và cho mỗi $j$ chúng ta tìm thấy $i\bmod r_j$ bằng cách yêu cầu GCD của $(P+k\,G,r_j\,G)$ đó là một trong hai $G$ hoặc $r_j\,G$, trong trường hợp sau tiết lộ rằng $i+k\equiv0\pmod{r_j}$. Sau đó, chúng tôi tìm thấy $i$ bởi Định lý phần dư Trung Quốc. Tối ưu hóa có thể nhóm một số lượng lớn các truy vấn thành một. Ví dụ. đệ trình $(P+k\,G,30\,G)$ và kiểm tra nếu kết quả là $G$, $2\,G$, $3\,G$, $5\,G$, $6\,G$, $10\,G$, $15\,G$ hoặc $30\,G$. Có thể giảm thêm bằng cách tính logarit rời rạc của đầu ra của nhà tiên tri bằng cách sử dụng các biến thể của Baby-Step/Giant-Step.
Tôi không biết bất kỳ ứng dụng nào, trong mật mã hay cách khác.
