Mật mã đường cong Elliptic

Mật mã đường cong elliptic (ECC) hiện thực hóa các lược đồ khóa công khai trên nhóm các điểm trên một đường cong elliptic, đạt được bảo mật tương đương với RSA hoặc Diffie-Hellman trường hữu hạn với các khóa nhỏ hơn nhiều.

Definition

Mật mã đường cong elliptic là mật mã khóa công khai mà nhóm cơ bản của nó là tập hợp các điểm trên một đường cong elliptic trên một trường hữu hạn, với bảo mật dựa trên độ khó của bài toán logarit rời rạc đường cong elliptic.

Scope

Chủ đề này bao gồm luật nhóm đường cong elliptic trên các trường hữu hạn, bài toán logarit rời rạc đường cong elliptic và các lược đồ được xây dựng trên chúng: Diffie-Hellman đường cong elliptic (ECDH), các lược đồ chữ ký ECDSA và EdDSA, và các đường cong hiện đại như Curve25519. Nó giải thích lý do tại sao logarit rời rạc đường cong elliptic khó hơn logarit trường hữu hạn (không có phép tính chỉ số dưới mũ) và các vấn đề triển khai như tái sử dụng nonce trong ECDSA. Nó không bao gồm RSA và các lược đồ logarit rời rạc trường hữu hạn được đề cập trong các chủ đề liên quan.

Core questions

• Làm thế nào phép cộng hình học các điểm trên một đường cong elliptic tạo thành một nhóm mật mã?
• Tại sao logarit rời rạc đường cong elliptic khó hơn logarit trường hữu hạn tương tự, cho phép sử dụng các khóa nhỏ hơn?
• Diffie-Hellman và chữ ký số được khởi tạo trên đường cong elliptic như thế nào?
• Điều gì làm cho các đường cong hiện đại như Curve25519 an toàn hơn khi triển khai so với các đường cong NIST cũ hơn?
• Tại sao tính duy nhất của nonce trên mỗi chữ ký lại quan trọng trong ECDSA?

Key concepts

• luật nhóm đường cong elliptic
• phép nhân vô hướng
• bài toán logarit rời rạc đường cong elliptic
• ECDH
• ECDSA
• EdDSA và Ed25519
• Curve25519
• lỗ hổng tái sử dụng nonce
• kích thước khóa so với RSA

Key theories

Bài toán logarit rời rạc đường cong elliptic

Cho các điểm P và Q = kP trên một đường cong, việc khôi phục vô hướng k được cho là đòi hỏi nỗ lực hoàn toàn theo cấp số mũ đối với các đường cong được chọn tốt, bởi vì các cuộc tấn công tính toán chỉ số làm suy yếu logarit rời rạc trường hữu hạn không áp dụng được.

Khóa nhỏ hơn cho bảo mật tương đương

Bởi vì các cuộc tấn công tốt nhất vào logarit rời rạc đường cong elliptic là các thuật toán căn bậc hai chung, một đường cong elliptic 256-bit mang lại bảo mật khoảng 128-bit — tương đương với RSA 3072-bit — mang lại các hoạt động nhanh hơn và các khóa và chữ ký nhỏ hơn.

Mechanisms

Các điểm trên một đường cong elliptic trên một trường hữu hạn tạo thành một nhóm Abel dưới một luật cộng hình học; việc cộng lặp lại một điểm cơ sở P với chính nó k lần (phép nhân vô hướng, kP) là hiệu quả, nhưng việc khôi phục k từ kP là bài toán khó. ECDH thực hiện Diffie-Hellman bằng cách trao đổi các bội vô hướng của một điểm cơ sở; ECDSA và EdDSA tạo ra chữ ký từ một vô hướng trên mỗi tin nhắn (một nonce) — nếu được lặp lại hoặc có thể dự đoán được, sẽ làm lộ khóa riêng, như một số vụ vi phạm thực tế đã cho thấy.

Clinical relevance

ECC là lựa chọn khóa công khai mặc định cho các hệ thống mới: ECDHE cung cấp trao đổi khóa bí mật chuyển tiếp trong TLS 1.3, Ed25519 ký các khóa SSH, cập nhật phần mềm và chứng chỉ, và Curve25519 bảo mật Signal, WireGuard và các ứng dụng nhắn tin hiện đại. Các khóa nhỏ và hoạt động nhanh của nó làm cho nó rất phù hợp với thiết bị di động, thẻ thông minh và phần cứng IoT hạn chế.

Evidence & guidelines

ECDSA được chuẩn hóa trong FIPS 186, ECDH trong NIST SP 800-56A, và EdDSA/Ed25519 trong RFC 8032; Curve25519/X25519 trong RFC 7748. Thực hành hiện đại ưu tiên các đường cong Edwards và X25519 vì khả năng chống lại các cạm bẫy triển khai. Sự cố của ECDSA khi các nonce được tái sử dụng (đặc biệt là việc trích xuất khóa Sony PlayStation 3 năm 2010) là một ví dụ cảnh báo tiêu chuẩn.

History

Neal Koblitz và Victor Miller độc lập đề xuất sử dụng đường cong elliptic cho mật mã vào năm 1985-1987. Việc áp dụng ban đầu chậm do các vấn đề về bằng sáng chế và lòng tin cũng như sự phức tạp của các đường cong NIST, nhưng ECC trở nên chiếm ưu thế vào những năm 2010 khi hiệu quả kích thước khóa trở nên quan trọng hơn và Curve25519 (2006) của Bernstein và Ed25519 đã cung cấp các thiết kế nhanh, chống lạm dụng hiện đang được triển khai rộng rãi.

Key figures

• Neal Koblitz
• Victor Miller
• Daniel J. Bernstein
• Alfred Menezes
• Scott Vanstone

Seminal works

• koblitz1987
• hankerson2004
• katz2020

Frequently asked questions

Tại sao khóa đường cong elliptic 256-bit lại tương đương với khóa RSA 3072-bit?

Các cuộc tấn công tốt nhất được biết đến đối với logarit rời rạc đường cong elliptic là chung và mất thời gian khoảng căn bậc hai của kích thước nhóm, trong khi phân tích thừa số và logarit rời rạc trường hữu hạn có các thuật toán dưới mũ nhanh hơn. Vì vậy, đường cong elliptic cần ít bit hơn nhiều cho cùng một mức độ bảo mật.

Các đường cong elliptic NIST có đáng tin cậy không?

Các đường cong P tiêu chuẩn của NIST được sử dụng rộng rãi và không được biết là đã bị phá vỡ, nhưng các lựa chọn hằng số không giải thích được và khó khăn trong việc triển khai của chúng đã khiến nhiều người ưu tiên Curve25519 và Ed25519, vốn có lý do thiết kế minh bạch và dễ triển khai an toàn hơn trong thời gian không đổi.