Không có cái nào tôi biết, nhưng bạn có thể xây dựng một cái. (Tại sao bạn muốn một cái tuy nhiên là một câu hỏi khác ...)
Tổng quát
Bạn có thể tìm thấy một câu hỏi hơi liên quan và câu trả lời xuất sắc đây, mặc dù nó không nói cụ thể về đường cong elip.
TL; DR về cơ bản là việc xây dựng bản đồ song tuyến tính trên các nhóm có thứ tự tổng hợp sẽ dễ dàng hơn $N=pq$ với $p$ và $q$ số nguyên tố, vì chúng sẽ có hai nhóm con có thứ tự nguyên tố lớn một cách tự nhiên từ định lý Lagrange.
Bây giờ, đối với Đường cong Elliptic, mọi thứ hơi khác một chút. Chúng tôi đang xây dựng một "nhóm đường cong elip" được xác định trên một trường nhất định.
"Tọa độ" của các điểm trên đường cong elip đang "sống" trong trường đó, nhưng bản thân các điểm lại "sống" trong nhóm EC.
Cả hai đều có đơn đặt hàng khác nhau. Trường có thứ tự riêng và nhóm đường cong elip có thứ tự riêng $n$ (có thể là hợp số hoặc nguyên tố). Khi chúng ta nói về các đường cong bậc nguyên tố, chúng ta thường xem xét thứ tự của nhóm đường cong elip, chứ không phải thứ tự của trường cơ sở mà nó được xác định.
Cuộc tấn công MOV và mức độ nhúng
Một điều quan trọng cần biết trong lĩnh vực đó là có cái gọi là tấn công MOV sử dụng ánh xạ ghép cặp song tuyến tính hai điểm trong một đường cong elip $E(\mathbb{F}_q)$ đến một phần tử trong trường $\mathbb{F}_{q^k}$, vì $k$ mức độ nhúng của đường cong đó.
Chúng tôi xác định $k$ là giá trị nhỏ nhất sao cho $n | q^k-1$.
Cuộc tấn công MOV rất nguy hiểm vì nếu $k$ Là bé nhỏ, thì việc giải DLP trong trường mở rộng đó sẽ dễ dàng hơn so với trong nhóm đường cong elip ban đầu và ánh xạ trở lại giải pháp trên đường cong elip, phá vỡ tính bảo mật của nó một cách hiệu quả.
Vì vậy, các đường cong Elliptic điển hình mà chúng tôi sử dụng cho ECDSA, ECDH và các sơ đồ dựa trên đường cong elip khác (không dựa trên ghép nối) có yêu cầu là mức độ nhúng của chúng phải lớn. GIÂY 1 v2 nói ví dụ:
Cuối cùng, mặc dù không có thuật toán hàm mũ con chung nào để giải ECDLP được biết đến, ba loại đường cong dễ bị ảnh hưởng bởi các thuật toán có mục đích đặc biệt. Thứ nhất, đường cong elip $E$ trên $F_q$ với $n$ phân chia $q^B â1$ cho nhỏ $B$ dễ bị tấn công bởi Menezes, Okamoto, và Vanstone [MOV93], và Frey và Rück [FR94]. Các cuộc tấn công làm giảm hiệu quả ECDLP
trên những đường cong này đến bài toán logarit rời rạc truyền thống trong một phần mở rộng nhỏ của $F_q$. một giới hạn $B ¥20$ đã được cập nhật thành $B ¥100$ trong [X9.62a] để cung cấp một biên độ an toàn lớn.
Đây là của họ $B$ là giá trị của chúng tôi $k$.
Tại sao mức độ nhúng lại quan trọng
Sự lựa chọn của mức độ nhúng đó $k$ đối với mật mã dựa trên ghép nối là sự đánh đổi giữa bảo mật và hiệu quả: mức độ nhúng lớn hơn có nghĩa là vấn đề logarit rời rạc khó giải quyết hơn trong nhóm nhân kết quả, nhưng điều đó cũng có nghĩa là các hoạt động được thực hiện trong trường mở rộng mức độ cao hơn , kém hiệu quả hơn ...
Bây giờ, khi chúng ta nói về các đường cong "thân thiện với việc ghép đôi", điều thường có nghĩa là chúng ta biết một cách để xây dựng một cặp đôi sẽ "dễ dàng" tính toán cho đường cong elip đó. Điều đó cũng có nghĩa là chúng tôi thường mong đợi có một giá trị tương đối "thấp" cho $k$, hầu hết thời gian $k \leq 24$.
(Nếu bạn muốn có một cái nhìn tổng quan về đường cong elip của nhúng độ 1, tôi khuyên bạn nên đọc bài báo năm 2016 này.)
Điều đó có ý nghĩa gì về tính bảo mật của DLP?
Để cho $G$ là một nhóm con của trật tự $q$ Trong $E(F_p)$.
Các Thuật toán Pollard-Rho trên nhóm phụ $G$ của đường cong elip của chúng tôi sẽ mất $\sqrt{\frac{Ïq}{2}}$ các bước và mỗi bước mất ~$O(\log^2(p))$.
Điều này có nghĩa là chúng tôi muốn đảm bảo thứ tự nhóm con của chúng tôi $q$ càng lớn càng tốt để làm cho thuật toán Pollard-Rho mất nhiều thời gian nhất có thể.
Với cuộc tấn công MOV đã đề cập ở trên, hãy để $e : G\times G' âF_{p^k}$ , ở đâu $k$ là mức độ nhúng, DLP trên $G$ sau đó có thể được dịch sang DLP trên $F_{p^k}$ và Pollard-Rho trên trường mở rộng của chúng tôi $F_{p^k}$ cũng cần $\sqrt{\frac{Ïq}{2}}$ bước, nhưng mỗi bước chỉ mất $O(k \log(p))$, đây là một sự khác biệt rất lớn về độ phức tạp.
Đây là lý do tại sao chúng tôi muốn có mức độ nhúng lớn $k$ đối với các đường cong elip được sử dụng cho ECC thông thường, như tôi đã đề cập ở trên, nhưng không nhất thiết phải dùng trong mật mã dựa trên ghép nối.
Trường hợp thứ tự chính
Cuối cùng, điều quan trọng là phải nhớ lại lý do tại sao "các lệnh nguyên tố" lại thú vị với DLP: đó là vì Thuật toán Pohlig-Hellman, có trường hợp phức tạp tồi tệ nhất là trường hợp của thuật toán bước nhỏ-bước khổng lồ khi thứ tự là số nguyên tố.
Pohlig-Hellman về cơ bản giống như CRT cho RSA, nó cho phép chúng ta làm việc trong các nhóm nhỏ hơn, dễ dàng hơn nếu thứ tự của nhóm ban đầu không phải là số nguyên tố.
Trong kiểu thiết lập đó, sẽ hợp lý khi có một thứ tự nguyên tố lớn, vì tất cả các nhóm con của nhóm ban đầu của chúng ta phải phân chia thứ tự của nó, do đó chúng ta chắc chắn rằng Pollard-Rho khó hết mức có thể.
Trường hợp ECDLP
Thật thú vị, cuộc tấn công tốt nhất (chung) được biết đến (xem cái này) trên mật mã đường cong elip là sự kết hợp của cả hai thuật toán Pohlig-Hellman và Pollard-Rho.
Nếu bạn biểu thị $l$ ước nguyên tố lớn nhất của $n$, cuộc tấn công này có thể xử lý ECDLP chỉ trong $O(\sqrt{l})$ thời gian, do đó tại sao chúng tôi muốn có ước số nguyên tố lớn theo thứ tự của chúng tôi $n$...
Lưu ý rằng đối với đường cong dị thường, đó là đường cong elip trên một trường $F_p$ có thứ tự EC cũng là $p$, chúng tôi có các cuộc tấn công đang chạy trong thời gian đa thức! Xem Satoh và Araki đây, hoặc Semaev, hoặc Thông minh:
Trong thực tế, phương pháp được mô tả có nghĩa là khi chọn các đường cong elip để sử dụng trong mật mã người ta phải loại bỏ tất cả các đường cong có thứ tự nhóm bằng với thứ tự của trường hữu hạn
(nhấn mạnh của tôi)
Lưu ý rằng nói chung, nếu $nâ1$ là sản phẩm của các số nguyên tố nhỏ, thì thuật toán PohligâHellman có thể giải quyết vấn đề logarit rời rạc trong nhóm này một cách hiệu quả, đây thường là lý do tại sao chúng tôi chọn một số nguyên tố an toàn khi xử lý DLP: nó đảm bảo chúng tôi có một " lớn" số nguyên tố trong sự phân hủy của $n-1$.
Theo thứ tự của EC so với đơn đặt hàng điểm cơ sở
Lưu ý rằng thứ tự của một đường cong về cơ bản là số điểm hữu tỷ trên đường cong elip đó. Nếu chúng ta đang làm việc hơn $F_p$, thì chúng tôi biết rằng số điểm đó trong EC của chúng tôi là $p+1-t$ ở đâu $t$ là Dấu vết Frobenius của đường cong. Theo định lý Hasse, chúng ta cũng biết rằng $t$ ở giữa $-2 \sqrt{p}$ và $2 \sqrt{p}$.
Nhưng trong ECC, chúng tôi thường làm việc trên một phân nhóm của một đường cong elliptic được xác định bởi một điểm cơ sở. Bậc của điểm gốc là ước nguyên tố của $p+1-t$ theo định lý Lagrange.
Vì vậy, cái nào bạn muốn trở thành một số nguyên tố an toàn? Tôi giả sử nhóm con được tạo bởi một điểm cơ sở nhất định.
Điều này cũng đúng đối với mật mã dựa trên ghép nối: các ghép nối được xác định trên một nhóm con của nhóm EC. Tiêu biểu ghép đôi giả định $k>1$, $\#E(F_p) = hn$, vì $n$ một số nguyên tố và nó hoạt động trong nhóm con của thứ tự $n$ của đường cong elip đó.
Làm thế nào để xây dựng một?
Đáng buồn thay, như tôi đã nói với bạn ngay từ đầu, tôi không biết về một đường cong thân thiện với cặp đôi mà thứ tự của nhóm con là một số nguyên tố an toàn. Có thể tạo một cái, nhưng tôi không có thời gian (chưa) để viết một tập lệnh tìm kiếm sẽ tạo ra một cái.
Làm thế nào để chúng tôi làm gì? Chà, tôi e rằng cách dễ nhất là "thử và sai" ở đó!
Barreto và Naehrig đã đưa ra một phương pháp cho các đường cong của bậc nguyên tố với $k = 12$, đã được "mở rộng" thành các đường cong với $k= 3, 4, 6$ qua người tự do.
Đáng buồn thay, tôi không biết về việc triển khai mã nguồn mở cho phép bạn dễ dàng
thử và tạo các đường cong này.
