Mã hóa khóa công khai: một chìa để khóa, một chìa để mở, không cần gặp mặt trước | Viết bởi sonradio

Khi gửi tin nhắn hay mở một trang web có ổ khóa nhỏ trên thanh địa chỉ, máy tính không gửi mật khẩu thô qua đường dây. Nó dùng một hệ thống có hai khóa liên kết: khóa công khai ai cũng lấy được để mã hóa, và khóa bí mật chỉ người nhận giữ để giải mã. Cách làm này gọi là mã hóa khóa công khai, hay mật mã bất đối xứng, và là nền tảng của hầu hết giao tiếp số an toàn hiện nay.

Vấn đề của một khóa dùng chung

Theo Wikipedia, trước giữa thập niên 1970, mọi hệ mật mã thực dụng đều dùng khóa đối xứng: người gửi và người nhận dùng cùng một khóa bí mật. Khóa đó phải được đưa cho nhau trước bằng một kênh an toàn, ví dụ gặp mặt hoặc đường dây riêng. Khi số người tăng lên, số khóa cần quản lý tăng rất nhanh vì mỗi cặp người nói chuyện riêng lại cần một khóa riêng.

Mã hóa khóa công khai tách hai vai trò đó. Mỗi người có một cặp khóa: khóa công khai được công bố rộng rãi, khóa bí mật giữ kín. Ai muốn gửi tin riêng cho bạn chỉ cần lấy khóa công khai của bạn để mã hóa; chỉ khóa bí mật của bạn mới giải được. Số khóa cần quản lý vì thế chỉ khoảng gấp đôi số người dùng, chứ không tăng theo số cặp người.

Sơ đồ tự vẽ: bên trái là cách cũ dùng chung một khóa bí mật; bên phải là cặp khóa công khai và khóa bí mật. Phía dưới là Diffie–Hellman và RSA

Diffie, Hellman và bài báo năm 1976

Năm 1976, Whitfield Diffie và Martin Hellman công bố bài "New Directions in Cryptography", lần đầu công khai mô tả hệ mật mã khóa công khai và chữ ký số. Họ cũng đưa ra giao thức trao đổi khóa Diffie–Hellman: hai bên chọn số bí mật riêng, gửi lên kênh mở một giá trị tính từ số đó, rồi cả hai tự tính ra cùng một khóa bí mật chung mà người nghe lén khó khôi phục được.

Whitfield Diffie phát biểu tại hội nghị RSA năm 2010. Cùng Martin Hellman, ông công bố ý tưởng mã hóa khóa công khai năm 1976

Theo Wikipedia, ý tưởng phân phối khóa công khai của Ralph Merkle cũng ảnh hưởng tới Diffie và Hellman. Merkle nghĩ ra kỹ thuật "Merkle's Puzzles" năm 1974 và công bố năm 1978. Diffie–Hellman trở thành phương pháp thực dụng đầu tiên được công bố để hai bên thống nhất khóa bí mật trên kênh đã xác thực nhưng không bí mật, mà không cần chia sẻ bí mật trước đó.

Năm 1977, Ron Rivest, Adi Shamir và Leonard Adleman tại MIT tìm ra một cách thực hiện mã hóa và chữ ký bằng khóa công khai dựa trên việc nhân hai số nguyên tố lớn. Thuật toán mang tên RSA từ chữ cái đầu của ba người. Theo Wikipedia, mô tả thuật toán xuất hiện trên cột Mathematical Games của tạp chí Scientific American tháng 8/1977, và bài báo đầy đủ được đăng năm 1978.

Khóa công khai RSA gồm tích n của hai số nguyên tố lớn cùng một số mũ e. Khóa bí mật dựa trên chính hai số nguyên tố đó. Mã hóa dùng (n, e); giải mã cần khóa bí mật. An toàn của RSA gắn với việc phân tích thừa số của n: khi p và q đủ lớn, chưa có phương pháp tổng quát hiệu quả đã công bố để phá hệ thống.

Điều GCHQ biết trước nhưng giữ kín

Tài liệu giải mật sau này cho thấy ý tưởng tương tự đã xuất hiện sớm hơn trong cộng đồng mật mã quân sự Anh. Năm 1970, James H. Ellis tại GCHQ nghĩ tới "mã hóa không bí mật". Năm 1973, Clifford Cocks đề xuất một sơ đồ tương đương RSA. Năm 1974, Malcolm J. Williamson đề xuất thứ ngày nay gọi là Diffie–Hellman. Những công trình này chỉ được công bố công khai nhiều năm sau.

Một số nhà mật mã tại hội thảo năm 2008, trong đó có Martin Hellman (giữa). Công trình Diffie–Hellman mở đường cho HTTPS, SSH và chữ ký số ngày nay

Trong thực tế, mã hóa khóa công khai thường chậm hơn mã hóa đối xứng, nên các giao thức như TLS, SSH, S/MIME và PGP dùng kiểu lai: khóa công khai chỉ để trao đổi hoặc bọc một khóa phiên ngắn hạn, còn nội dung dài được mã bằng khóa đối xứng. Ổ khóa trên trình duyệt vì thế là kết quả của cả hai lớp đó, chứ không phải chỉ một thuật toán.

Nguồn: Wikipedia: Public-key cryptography , Wikipedia: Diffie–Hellman key exchange , Wikipedia: RSA (cryptosystem) , Britannica Kids: public-key cryptography , Communications of the ACM: Finding New Directions in Cryptograph