Làm cách nào để quyết định xem một điểm trên đường cong elip có thuộc nhóm được tạo bởi trình tạo g không?

Câu trả lời thực sự phụ thuộc vào Đường cong elip mật mã mà chúng ta biết!

1. Thứ tự chính Mật mã EC: Vì thứ tự của nhóm con do một phần tử sinh ra phải chia thứ tự nên mới có nhóm đầy đủ và nhóm các $\mathcal{O}$ trật tự $1$ ( Các đường cong NIST P Các đường cong P-192, P-224, P-256, P-384, P-521) có thứ tự nguyên tố được liệt kê trong NIST.FIPS.186-4 và lấy từ giây1).

2. Mật mã EC với một yếu tố nhỏ: Trong Mật mã các đường cong có bậc lớn để an toàn ta phải chọn phần tử cơ sở từ nhóm con lớn nhất.Điều này là do

   1. Bảo vệ khỏi Thuật toán Pohlig-Hellman giúp giảm thời gian xuống yếu tố lớn nhất và rất hiệu quả khi đơn hàng suôn sẻ, tức là tất cả các yếu tố đều nhỏ.

   2. Để có một Montogmery tương đương lưỡng tính của đường cong như Curve25519 với đồng sáng lập $8$ và Ed448-Goldilocks với đồng sáng lập $4$. Trong trường hợp này, chúng tôi có các đơn đặt hàng cho các nhóm con như; $2,4,8,p,2p,4p,8p$ (đối với Curve25519)^*

      Để thấy rằng một điểm $G$ là thứ tự $2$ hoặc $p$ thật dễ dàng, hãy kiểm tra $2[G]$ hoặc $[p]G$, nếu kết quả là danh tính, thì họ thuộc nhóm này. Họ nhưng họ cũng nằm trong nhóm con chứa các nhóm con. Có các phần tử trong nhóm con của thứ tự $2p$ nhưng không thuộc nhóm con của thứ tự $2$ hoặc $p$. Kiểm tra $[2]G$ và $[p]G$ nếu họ không phải là bản sắc nhưng $[2p]G$ thì nó nằm trong nhóm con của thứ tự $2p$.

      Các nhóm Klein là nhóm nhỏ nhất có hai nhóm con bậc 2, nó đẳng cấu với $\mathbb Z_2 \times \mathbb Z_2$. Điều này có thể giúp hiểu rằng hai nhóm con khác nhau có thể có cùng thứ tự.

      Các Đường cong NIST B có đồng yếu tố 2 và đường cong K có 4, và chúng được lấy từ giây2.

3. Sự thay đổi của mật mã EC: Sự xoắn của những đường cong nổi tiếng không có thừa số bậc hai lớn, áp dụng tương tự như trường hợp 2.

4. đường cong ngẫu nhiên: Tôi không biết về kích thước dự kiến ​​của các yếu tố của các đường cong được tạo ngẫu nhiên (đã xem một số tác phẩm). Chúng ta có thể có một đường cong với bậc sao cho nó có hệ số lớn bậc 2 trở lên. Trong trường hợp này, các $[p]G$ sẽ không tiết lộ thành viên nhóm con. Để giải quyết nó, chúng ta cần tìm một trình tạo cho từng nhóm con và cố gắng giải DLog.

5. Yếu tố thứ tự của nhóm không được biết đến: Trong trường hợp này, chúng ta có một vấn đề quyết định phân nhóm (như đã nêu trong câu trả lời khác)

   Được cho $(n, G, G1, e)$ và một phần tử $x \in G$, đầu ra $1$ nếu thứ tự của $x$ Là $q_1$ và đầu ra $0$ nếu không thì; Đó là, không cần biết phân tích thành thừa số của thứ tự nhóm $n$, quyết định xem một phần tử $x$ nằm trong một nhóm con của $G$. Chúng tôi gọi vấn đề này là vấn đề quyết định phân nhóm

   Mặc dù vấn đề này đưa ra các kết quả thú vị trong ngữ cảnh của nó, nhưng vấn đề này không liên quan đến Đường cong Elliptic được sử dụng trong ECDH, EdDSA, v.v. Trong các đường cong elliptic, tất cả các tham số đều được công khai. Ngay cả khi bạn không cung cấp thứ tự của đường cong (không rõ bạn sẽ bán đường cong của mình cho cộng đồng như thế nào), người ta vẫn có thể tính đến 829 bit (512-bit đã đạt được bản ngã khoảng 20 năm).

   Nếu bạn xem xét các đường cong theo thứ tự rất lớn, chúng ta có thể nói rằng thứ tự đường cong lớn hơn 512 bit (thậm chí 256) không có nhiều ý nghĩa, vì một khi thuật toán của Shor được đặt trong Máy tính lượng tử mật mã cho các đường cong 256 bit, thì vấn đề là các nhà nghiên cứu thời gian sẽ phá vỡ cái kia. Điều này có thể được nhìn thấy từ bảng của Công việc của Proos và Zalks

Mặt khác, ECC hậu lượng tử sử dụng nhảy trên các đồng vị thay vì DH và bài báo này cung cấp một giới thiệu tốt cho bất kỳ ai muốn tìm hiểu.

• Trao đổi khóa isogeny supersingular dành cho người mới bắt đầu, Craig Costello, 2019. ( Chào mừng trở lại với các đường cong siêu dị!)

Cuối cùng, các trường hợp có vấn đề duy nhất không phải là các đường cong mật mã.

^* Ở đó chúng tôi đã sử dụng Định lý Lagrange trên Lý thuyết nhóm;

• Nếu $H$ là một nhóm con của một nhóm $G$ sau đó $ord(H) \mid ord(G)$

Cần lưu ý rằng chúng ta đã sử dụng điều ngược lại của định lý, nếu $x|org(G)$ sau đó có một nhóm con của thứ tự $x$. Điều này không phải lúc nào cũng đúng và xen kẽ nhóm độ 4 $A_4$ là ví dụ nhỏ nhất.