Tại sao các đường cong elip trên các trường nhị phân được sử dụng ít hơn so với các đường cong trên các trường nguyên tốï¼

Trong các ứng dụng thực tế, đường cong elip trên $F_p$ dường như được phổ biến hơn những người trên $F_{2^n}$. Có phải vì các phép toán trên các trường nguyên tố nhanh hơn các phép toán trên $F_{2^n}$ cho cùng một mức độ bảo mật?

Có lẽ đó là trí tưởng tượng của tôi. Tôi chỉ thấy nhiều dự án mở hơn sử dụng các đường cong elip trên $F_p$ nhưng không nhiều hơn $F_{2^n}$.

Bảo mật: Các trường nhị phân có nhiều vectơ tấn công hơn các trường nguyên tố

Nhật ký rời rạc trên ECC với trường nhị phân không bị hỏng. Đó không phải là lý do. Bernstein nói;

câu chuyện bảo mật cho các trường không phải là số nguyên tố (ví dụ: các trường mở rộng nhị phân) là phức tạp hơn và kém ổn định hơn hơn là câu chuyện bảo mật cho các trường nguyên tố, như được minh họa bởi Frey năm 1998, GaudryâHessâSmart năm 2002, Gaudry năm 2009 và PetitâQuisquater năm 2012.

Kết quả là, việc chọn các trường nguyên tố làm giảm vectơ tấn công, do đó ít lo ngại hơn về bảo mật.

• 2002 Các khía cạnh xây dựng và phá hủy của Weil Descent trên các đường cong Elliptic

  Trong bài báo này, chúng tôi xem xét chi tiết các đường cong phát sinh trong phương pháp của Galbraith và Smart để tạo ra các đường cong trong giới hạn Weil của một đường cong elip trên một trường hữu hạn của đặc trưng hai của mức độ tổng hợp. Chúng tôi giải thích cách phương pháp này có thể được sử dụng để xây dựng các hệ thống mật mã siêu elip có thể an toàn như các hệ thống mật mã dựa trên đường cong elliptic ban đầu. Mặt khác, chúng tôi chỉ ra rằng điều này có thể cung cấp một cách tấn công hệ thống mật mã đường cong elip ban đầu bằng cách sử dụng những tiến bộ gần đây trong nghiên cứu về bài toán logarit rời rạc trên đường cong siêu elip

• 2004 Phép tính chỉ số cho các giống abelian và bài toán logarit rời rạc trên đường cong elip bởi Pierrick Gaudry

  Chúng tôi đã chỉ ra rằng một cách tiệm cận, các đường cong elip được xác định trên các trường mở rộng mức độ nhỏ là yếu hơn hơn những trường được xác định trên các trường nguyên tố hoặc các trường mở rộng cấp nguyên tố lớn.

• 2012 Về các hệ thống đa thức phát sinh từ một dòng dõi Weil bởi Christophe Petit và Jean-Jacques Quisquater

  Họ đã xem xét ECDLP trên trường mở rộng nhị phân và chỉ ra rằng thuật toán của họ hoạt động tốt hơn các thuật toán logarit rời rạc chung cho $N >2000$. Các kích thước được đề xuất vẫn chưa bị ảnh hưởng!

Bằng sáng chế của Certicom (và những người khác)

Một vấn đề quan trọng khác là bằng sáng chế mà chủ yếu là Certicom đã/có.

Đầu tiên Câu nói của Bruce Schneier

"Certicom chắc chắn có thể yêu cầu quyền sở hữu ECC," Schneier nói với chúng tôi. "Thuật toán được phát triển và cấp bằng sáng chế bởi những người sáng lập công ty, và các bằng sáng chế được viết tốt và mạnh mẽ. Tôi không thích điều đó, nhưng họ có thể yêu cầu quyền sở hữu."

• Một trong những bằng sáng chế của Certicom là về hiệu quả $\operatorname{GF}(2^n)$ phép nhân trong biểu diễn cơ sở thông thường; Bằng sáng chế Hoa Kỳ 5.787.028. Bằng sáng chế này được cấp vào năm 1998 và cuối cùng đã hết hạn vào năm 2016.
• NSA đã có một số bằng sáng chế về $\operatorname{GF}(2^n)$, quá; [1] [2] [3] [4], tuy nhiên, chúng đã hết hạn sớm hơn nhiều vì NSA không trả phí (tôi nghĩ đó là cố ý)

Giai đoạn hiện tại của các cuộc tấn công để so sánh

Nếu chúng ta nhìn vào Thách thức ECC của Certicom

• Một đường cong Koblitz trên $2^{108}$ bị phá vỡ vào năm 2000.
• Một $109$ đường cong bit prime bị phá vỡ vào năm 2002.
• Một đường cong trên $2^{109}$ bị phá vỡ vào năm 2004.
• Các thử thách 131-bit Binary hoặc Prime vẫn chưa bị phá vỡ.

Ngoài những thách thức này;

• Bài toán logarit rời rạc đường cong elip 117,35 bit trên đường cong nhị phân bị phá vỡ vào năm 2016 bởi Bernstein et. tất cả

Một thực tế thực tế làm thay đổi cán cân theo hướng $\mathbb F_p$ là các CPU tiêu chuẩn của những năm 1990 và đầu những năm 2000 thường có nhiều lệnh nhưng không hỗ trợ phần cứng cho sản phẩm ít mang theo, đảo ngược lợi thế $\mathbb F_{2^k}$ có trong phần cứng. Và số học trong $\mathbb F_p$ đã được nghiên cứu rộng rãi cho RSA và DSA. Vì vậy, có thể hiểu được mọi người bắt đầu sử dụng $\mathbb F_p$, và sau đó không có lý do thuyết phục để thay đổi. Có lẽ (mỗi trong bình luận này) Bằng sáng chế của Certicom về ECC trong $\mathbb F_{2^k}$ lái xe khách hàng tiềm năng đi. Ngoài ra, nhiều người hiểu số học trong $\mathbb F_p$, và không ai từng bị sa thải vì đã chọn nó.

Từ quan điểm bảo mật, tôi nghĩ rằng có một cảm giác hợp lý rằng với $\log_2p\khoảng m$, ECC trong lĩnh vực chính $\mathbb F_p$ an toàn hơn trong trường nhị phân $\mathbb F_{2^m}$. Những lý do tôi hiểu là:

• Để cho $m$, có khoảng $\approx0,69\cdot2^m/m$ lựa chọn cho $p$. Tất cả các trường hữu hạn của một thứ tự nhất định là đẳng cấu. Cho nên $\mathbb F_{2^m}$ là trường hợp đặc biệt và trong tiền điện tử, trường hợp đặc biệt hiếm khi an toàn hơn.
• Ít nhất là về phần cứng, việc bổ sung điểm ECC tốn kém hơn đáng kể trong lĩnh vực này $\mathbb F_p$ hơn trong lĩnh vực này $\mathbb F_{2^m}$. Có lẽ khó hơn ngụ ý an toàn hơn và khó hơn ngụ ý kém an toàn hơn sẽ khá ngạc nhiên.
• Giải DLP trong nhóm con nhân của trường $\mathbb F_p$ khó hơn nhiều so với $\mathbb F_{2^m}$, như có thể thấy từ các bản ghi ($795\text{-bit }p$ Trong $\mathbb F_p$, $m=30750$ Trong $\mathbb F_{2^m}$ ). Một lần nữa, có lẽ DLP khó hơn trong nhóm con nhân lên ngụ ý DLP khó hơn trong nhóm ECC, và thật ngạc nhiên khi nó ngụ ý DLP dễ dàng hơn trong nhóm ECC.

Có những lý do bảo mật khác. Tôi đề cập đến ba gạch đầu dòng đầu tiên của câu trả lời khác. Tôi hiểu họ vừa đủ để nói rằng họ không dẫn đến một cuộc tổng tấn công vào ECC trong $\mathbb F_{2^m}$, ví dụ. trên các đường cong trong phần 3 của sec2v2. Tuy nhiên, thật hợp lý khi họ thấm nhuần sự khó chịu.

Cuối cùng, giống như hầu hết, tôi chấp nhận Sự khôn ngoan của Safecurve :

2006 Bernstein tuyên bố rằng các trường nguyên tố "có ưu điểm là giảm thiểu số lượng mối lo ngại về bảo mật đối với mật mã đường cong elip". Tương tự, tiêu chuẩn Brainpool và tiêu chuẩn Suite B của NSA yêu cầu các trường nguyên tố. Có một thỏa thuận chung rằng các trường nguyên tố là sự lựa chọn an toàn, thận trọng cho ECC.