Mã hóa đường elliptic (tiếng Anh: Elliptic Curve Cryptography, viết tắt là ECC) là một phương pháp tiếp cận mật mã học khóa công khai (asymmetric cryptography) dựa trên cấu trúc đại số của các đường cong elliptic xác định trên các trường hữu hạn (finite fields). Trong an toàn thông tin và khoa học máy tính hiện đại, ECC là nền tảng cốt lõi được ứng dụng rộng rãi để thiết lập chữ ký số, trao đổi khóa bảo mật và mã hóa dữ liệu trong các giao thức mạng Internet, thiết bị di động thông minh và hệ thống tiền mã hóa.
Bản chất toán học và cấu trúc nhóm trên đường cong elliptic
Ý tưởng ứng dụng đường cong elliptic vào mật mã học được đề xuất độc lập vào giữa thập niên 1980 bởi hai nhà toán học Neal Koblitz (1987) và Victor S. Miller (1985). Thay vì dựa vào bài toán phân tích thừa số nguyên tố lớn như hệ mật RSA hay bài toán logarit rời rạc trên nhóm nhân trường hữu hạn như hệ mật ElGamal, ECC khai thác tính chất hình học và đại số của tập hợp các điểm trên đường cong elliptic.
Trên trường hữu hạn nguyên tố Fp (với p là số nguyên tố lớn hơn 3), một đường cong elliptic không suy biến được biểu diễn dưới dạng phương trình Weierstrass rút gọn:
y2 = x3 + ax + b (theo modulo p)
Trong đó, các hệ số a và b thuộc trường Fp và phải thỏa mãn điều kiện biệt thức không triệt tiêu: 4a3 + 27b2 ≠ 0 (modulo p) để đảm bảo đường cong không có điểm kỳ dị (không có điểm tự cắt hoặc điểm lùi dạng góc nhọn).
Phép cộng điểm và luật nhóm Abel
Tập hợp các điểm có tọa độ (x, y) thỏa mãn phương trình đường cong kết hợp với một điểm đặc biệt quy ước gọi là điểm vô cực (kí hiệu là O hoặc điểm ở vô tận) tạo thành một nhóm Abel (Abelian group) dưới phép toán cộng điểm hình học (chord-and-tangent rule):
- Phần tử trung hòa (Identity element): Điểm vô cực O đóng vai trò là phần tử đơn vị, thỏa mãn P + O = O + P = P với mọi điểm P trên đường cong.
- Phần tử nghịch đảo (Inverse element): Với mỗi điểm P(x, y), điểm đối xứng qua trục hoành là -P(x, -y mod p) chính là phần tử nghịch đảo, sao cho P + (-P) = O.
- Phép cộng hai điểm phân biệt (Point Addition): Đường thẳng nối hai điểm phân biệt P và Q cắt đường cong tại điểm thứ ba R′; điểm đối xứng của R′ qua trục hoành chính là kết quả của phép cộng P + Q = R.
- Phép nhân đôi điểm (Point Doubling): Khi cộng một điểm với chính nó (P + P = 2P), ta vẽ tiếp tuyến với đường cong tại P; tiếp tuyến này cắt đường cong tại điểm thứ hai R′, và điểm đối xứng của R′ qua trục hoành là 2P.
Bài toán Logarit rời rạc trên đường cong Elliptic (ECDLP)
Trụ cột bảo mật vững chắc của mọi hệ mật mã ECC là độ khó tính toán của Bài toán Logarit rời rạc trên đường cong Elliptic (Elliptic Curve Discrete Logarithm Problem, viết tắt là ECDLP). Bài toán được phát biểu như sau:
Cho trước một đường cong elliptic trên trường hữu hạn, một điểm cơ sở P có bậc nguyên tố lớn n (sao cho nP = O), và một điểm Q nằm trên đường cong sao cho Q = kP (với k là một số nguyên bí mật nằm trong khoảng từ 1 đến n - 1). Nhiệm vụ là tìm lại giá trị của số nguyên vô hướng k khi chỉ biết tọa độ của P và Q.
Trong khi chiều xuôi (phép nhân vô hướng Q = kP) có thể được tính toán cực kỳ nhanh chóng bằng thuật toán "nhân đôi và cộng" (double-and-add) trong thời gian đa thức O(log k), thì chiều ngược lại (tìm k từ P và Q) là bài toán một chiều (one-way function) bất khả quy tính toán trên thực tế.
Khác biệt căn bản giữa ECDLP và bài toán phân tích thừa số nguyên tố của RSA là: đối với ECDLP trên các đường cong được chọn lựa cẩn thận, hoàn toàn không tồn tại các thuật toán tấn công thời gian dưới hàm mũ (sub-exponential algorithms) như thuật toán sàng trường số tổng quát (GNFS) hay thuật toán sàng chỉ số (Index Calculus). Các thuật toán tổng quát tốt nhất hiện nay để giải ECDLP (như thuật toán Pollard rho) đều có độ phức tạp thời gian hàm mũ đầy đủ O(√n).
So sánh hiệu năng và kích thước khóa giữa ECC và RSA
Do khả năng chống lại các đòn tấn công giải mã toán học vượt trội, ECC đạt được mức độ an toàn tương đương với hệ mật RSA nhưng với độ dài khóa ngắn hơn rất nhiều. Điều này mang lại lợi thế khổng lồ về tốc độ xử lý, tiết kiệm năng lượng pin và giảm băng thông truyền nhận:
| Mức độ bảo mật (Security Level) | Độ dài khóa RSA tương đương | Độ dài khóa ECC tương đương | Tỷ lệ nén kích thước khóa |
|---|---|---|---|
| 80-bit (Đã lỗi thời) | 1024-bit | 160-bit | 1 : 6 |
| 112-bit (Tiêu chuẩn tối thiểu cũ) | 2048-bit | 224-bit | 1 : 9 |
| 128-bit (Tiêu chuẩn công nghiệp hiện nay) | 3072-bit | 256-bit | 1 : 12 |
| 192-bit (Bảo mật cấp độ cao) | 7680-bit | 384-bit | 1 : 20 |
| 256-bit (Bảo mật tuyệt mật / Quốc phòng) | 15360-bit | 512-bit / 521-bit | 1 : 30 |
Các giao thức mật mã học chủ đạo ứng dụng ECC
Hệ mật mã đường cong elliptic được tích hợp vào bốn lớp giao thức mật mã học chính phục vụ mọi nhu cầu truyền thông bảo mật:
1. Trao đổi khóa Diffie-Hellman đường cong elliptic (ECDH)
Giao thức ECDH (Elliptic Curve Diffie-Hellman) cho phép hai bên giao tiếp (ví dụ Alice và Bob) thiết lập một khóa bí mật chung qua kênh truyền công khai không an toàn mà không cần gửi trực tiếp khóa bí mật:
- Alice chọn một khóa riêng ngẫu nhiên dA và tính khóa công khai tương ứng QA = dAP.
- Bob chọn một khóa riêng ngẫu nhiên dB và tính khóa công khai tương ứng QB = dBP.
- Hai bên trao đổi khóa công khai QA và QB. Alice tính điểm chung S = dAQB, Bob tính điểm chung S = dBQA. Do tính chất kết hợp của phép nhân vô hướng, cả hai cùng thu được điểm S = dAdBP, từ đó trích xuất ra khóa đối xứng phiên làm việc.
2. Thuật toán chữ ký số đường cong elliptic (ECDSA)
ECDSA (Elliptic Curve Digital Signature Algorithm) là phiên bản đường cong elliptic của chuẩn chữ ký số DSA. Quy trình sinh và kiểm tra chữ ký bao gồm các bước toán học chặt chẽ:
- Sinh chữ ký: Người ký chọn số ngẫu nhiên tạm thời (nonce) k từ 1 đến n - 1, tính điểm R = kP = (x1, y1), đặt r = x1 mod n. Sau đó tính giá trị s = k-1(z + rd) mod n, trong đó z là giá trị băm của thông điệp và d là khóa riêng. Cặp (r, s) chính là chữ ký số.
- Xác minh chữ ký: Người nhận tính các giá trị trung gian u1 = zs-1 mod n và u2 = rs-1 mod n, sau đó tính điểm kiểm tra R′ = u1P + u2Q. Chữ ký hợp lệ khi và chỉ khi hoành độ của R′ modulo n bằng r.
3. Thuật toán chữ ký EdDSA và đường cong Edwards
EdDSA (Edwards-curve Digital Signature Algorithm), tiêu biểu là thuật toán Ed25519 sử dụng đường cong Twisted Edwards (Curve25519), được phát triển nhằm khắc phục các nhược điểm của ECDSA. EdDSA có công thức cộng điểm toàn phần (complete addition formula) không có trường hợp ngoại lệ điểm vô cực, giúp mã nguồn thực thi trong thời gian hằng số (constant-time), tự nhiên miễn nhiễm với các cuộc tấn công kênh kề (side-channel attacks) dựa trên phân tích thời gian và loại bỏ hoàn toàn rủi ro rò rỉ khóa riêng do số ngẫu nhiên trùng lặp.
4. Hệ thống mã hóa tích hợp đường cong elliptic (ECIES)
ECIES (Elliptic Curve Integrated Encryption Scheme) là phương pháp mã hóa khóa lai (hybrid encryption). Nó sử dụng ECDH để sinh khóa phiên đối xứng tạm thời, sau đó dùng thuật toán đối xứng tốc độ cao (như AES-GCM hoặc ChaCha20-Poly1305) để mã hóa khối lượng dữ liệu lớn và kèm theo mã xác thực thông điệp (MAC) để chống giả mạo bản tin.
Các tiêu chuẩn đường cong elliptic phổ biến trong thực tế
Hiệu năng và độ an toàn của ECC phụ thuộc vào việc lựa chọn các tham số đường cong chuẩn (domain parameters). Dưới đây là các đường cong elliptic được triển khai phổ biến nhất trong hạ tầng công nghệ thông tin toàn cầu:
| Tên đường cong | Tổ chức ban hành / Thiết kế | Dạng phương trình đại số | Lĩnh vực ứng dụng tiêu biểu |
|---|---|---|---|
| NIST P-256 (secp256r1) | Viện Tiêu chuẩn và Công nghệ Quốc gia Hoa Kỳ (NIST) | Weierstrass trên trường nguyên tố Fp (p = 2256 - 2224 + 2192 + 296 - 1) | Chứng chỉ số SSL/TLS trên web (HTTPS), bảo mật hệ điều hành Windows, iOS và thẻ căn cước thông minh. |
| secp256k1 | Nhóm Tiêu chuẩn Mật mã học Hiệu năng cao (SECG) | Đường cong Koblitz đặc biệt: y2 = x3 + 7 trên Fp | Mạng lưới chuỗi khối (Blockchain) Bitcoin, Ethereum và phần lớn hệ sinh thái tài chính phi tập trung. |
| Curve25519 / Ed25519 | Daniel J. Bernstein | Đường cong Montgomery (y2 = x3 + 486662x2 + x) / Twisted Edwards | Giao thức SSH, mạng riêng ảo WireGuard, ứng dụng nhắn tin bảo mật Signal, WhatsApp, Tor và TLS 1.3. |
Vấn đề an toàn thực thi và các dạng tấn công trong thực tế
Dù có nền tảng toán học bảo mật cực cao, các triển khai ECC trong phần mềm và phần cứng vẫn có thể bị tổn thương nếu không tuân thủ nghiêm ngặt các nguyên tắc an toàn công nghệ:
- Tấn công kênh kề (Side-Channel Attacks): Kẻ tấn công đo lường thời gian thực thi (timing attacks) hoặc sự biến thiên công suất tiêu thụ điện (power analysis) trong quá trình tính phép nhân vô hướng kP để suy đoán từng bit của khóa riêng. Giải pháp là lập trình thời gian hằng số hoặc sử dụng kỹ thuật che giấu điểm (point blinding).
- Lỗi tái sử dụng số ngẫu nhiên tạm thời (Nonce Reuse): Trong ECDSA, nếu cùng một giá trị k ngẫu nhiên bị sử dụng lại cho hai chữ ký khác nhau, kẻ tấn công có thể giải hệ phương trình tuyến tính đơn giản để khôi phục trực tiếp khóa riêng của người ký (lỗ hổng từng làm lộ khóa máy chơi game PlayStation 3 năm 2010).
- Tấn công đường cong không hợp lệ (Invalid Curve Attacks): Xảy ra khi bên nhận không kiểm tra xem điểm công khai do đối phương gửi đến có thực sự nằm trên đường cong tiêu chuẩn hay không, dẫn đến việc tính toán trên một đường cong yếu hơn có cấp nhóm nhỏ.
Thách thức an ninh và tương lai trước kỷ nguyên máy tính lượng tử
Mặc dù ECC đang là tiêu chuẩn thống trị bảo mật kỹ thuật số, nó đối mặt với thách thức mang tính sống còn trước sự phát triển của điện toán lượng tử (quantum computing). Thuật toán lượng tử Shor do Peter Shor phát minh năm 1994 có khả năng giải quyết cả bài toán phân tích thừa số nguyên tố lẫn bài toán ECDLP trong thời gian đa thức O((log n)3) trên một máy tính lượng tử quy mô lớn.
Nhận thức được nguy cơ này, cộng đồng mật mã học quốc tế và Viện Tiêu chuẩn NIST đang tích cực chuyển dịch sang các chuẩn Mật mã hậu lượng tử (Post-Quantum Cryptography, PQC) dựa trên cấu trúc lưới (lattice-based cryptography như ML-KEM/Kyber và ML-DSA/Dilithium), đảm bảo an toàn lâu dài cho dữ liệu trong tương lai.