Năm 1973, Clifford Cocks giải bài toán mã hóa khóa công khai chỉ sau một đêm. GCHQ giữ kín đến tận năm 1997.

12/10/2026 · VietTechies · Biên tập

Mùa thu năm 1973, Clifford Cocks mang về nhà một bài toán về mã hóa khóa công khai mà ở nơi làm việc mới của ông chưa ai giải được. Khi đó, ông mới vào làm được vài tuần tại Trụ sở Truyền thông Chính phủ (GCHQ), cơ quan tình báo tín hiệu của Anh.

Bài toán đặt ra là tìm một phương pháp dùng được trong thực tế để hai người trao đổi thông điệp mật với nhau mà không cần chia sẻ trước một khóa bí mật. Theo lời Cocks kể, Nick Patterson, người hướng dẫn ông, đã giới thiệu đây là một “bài toán cực hay, nhưng chưa ai thực sự tiến được bước nào”.

Tối hôm đó, Cocks nghiền ngẫm bài toán ở nhà. Đến sáng hôm sau, ông đã đặt được nền móng cho một phương pháp khả thi. Bản ghi chú của ông, đề ngày 20 tháng 11 năm 1973, gồm bốn đoạn ngắn có đánh số. James Ellis, đồng nghiệp ở GCHQ và là người đầu tiên đặt ra bài toán, về sau nhận xét rằng phương án này “về cơ bản chính là thuật toán RSA”. RSA là phương pháp mà ba nhà nghiên cứu ở Viện Công nghệ Massachusetts (MIT) mô tả vào năm 1977, và đến nay vẫn là một trong những thuật toán khóa công khai được dùng rộng rãi nhất.

GCHQ quyết định không hiện thực hóa phương pháp của Cocks và xếp bản ghi chú vào diện tài liệu mật. Phải đến tháng 12 năm 1997, tức 24 năm sau, công chúng mới biết đến công trình này.

Điều tưởng không thể, được chứng minh là có thể

Bài toán này vốn xuất phát từ Ellis. Về sau, ông viết rằng vào thập niên 1960, việc quản lý “lượng khóa mã khổng lồ” là nỗi đau đầu của quân đội. Mọi người, kể cả Ellis, đều mặc nhiên cho rằng muốn liên lạc an toàn thì phải có khóa bí mật, hoặc một lợi thế nào khác trước kẻ nghe lén. Một báo cáo thời chiến của Bell Telephone Laboratories đã khiến ông đổi ý: để bảo mật một cuộc gọi điện thoại, người nhận có thể đưa nhiễu vào đường dây rồi trừ phần nhiễu ấy đi. Người nhận cũng tham gia vào quá trình mã hóa.

Liệu mã hóa thông thường có thể hoạt động như vậy không? Ellis viết rằng câu hỏi ấy “chợt đến với tôi vào một đêm, khi đang nằm trên giường, và việc chứng minh rằng điều này khả thi về mặt lý thuyết chỉ mất vài phút”. Ông trình bày chứng minh đó trong một báo cáo nội bộ vào tháng 1 năm 1970. Nhưng lời chứng minh ấy dựa vào những bảng tra cứu mà thông thường sẽ lớn đến mức bất khả thi, còn các ý tưởng cho một phiên bản dùng được trong thực tế thì hết lần này đến lần khác lộ ra khiếm khuyết. “Vì tôi yếu về lý thuyết số,” Ellis viết, “nên tôi để việc triển khai thực tế lại cho người khác.”

Buổi tối Cocks tìm ra lời giải

Cocks tiếp cận bài toán từ góc độ lý thuyết số. Ông từng học toán ở Cambridge và bắt đầu làm tiến sĩ ở Oxford, trước khi quyết định rằng con đường học thuật không hợp với mình. “Tôi biết thứ mình cần là một hàm toán học tính xuôi thì dễ nhưng đảo ngược thì khó,” ông nói với tạp chí toán học Chalkdust vào năm 2019. “Tôi vốn làm về lý thuyết số, nên phân tích thừa số có vẻ là thứ có thể dùng được.”

Nhân hai số nguyên tố lớn với nhau thì nhanh. Còn từ tích của chúng mà tìm lại hai số nguyên tố ban đầu thì tốn công hơn gấp bội. Bản ghi chú của Cocks biến sự chênh lệch ấy thành một hệ mã:

Người nhận chọn hai số nguyên tố lớn P và Q, rồi gửi công khai tích của chúng, gọi là N.
Người gửi nâng từng khối của thông điệp lên lũy thừa N theo modulo N, rồi gửi kết quả đi.
Người nhận, vốn biết P và Q, dùng thuật toán Euclid tính ra hai số phụ trợ rồi khôi phục thông điệp.

Kẻ nghe lén thấy được N và thông điệp đã mã hóa. Như Ellis tóm tắt: “Độ an toàn nằm ở chỗ khó phân tích N ra thừa số.”

Về sau, Ellis đem hệ mã này so sánh với bản RSA đã công bố. Trong RSA, người gửi nâng thông điệp lên lũy thừa e, một số mũ công khai do người nhận chọn. Còn trong phiên bản của Cocks, số mũ này luôn bằng N. Ellis viết rằng phiên bản ấy “là một trường hợp đặc biệt của RSA, ở chỗ nó đặt e = N”, và “hai thuật toán là những biến thể của cùng một phương pháp”.

Chừng hai tháng sau, Malcolm Williamson, đồng nghiệp ở GCHQ và cũng là bạn thời thơ ấu của Cocks, mang đến cho Ellis một phương án khác. Theo lời Ellis, về sau Williamson cũng nghĩ ra cơ chế trao đổi khóa mà Whitfield Diffie và Martin Hellman công bố năm 1976, chỉ khác ở chỗ Diffie và Hellman buộc modulo phải là một số nguyên tố. Báo cáo của Williamson về cơ chế này đề tháng 8 năm 1976, tức hơn hai tháng sau khi Diffie và Hellman gửi đăng bài báo mô tả cùng cơ chế; Ellis viết rằng Williamson công bố ý tưởng này “muộn hơn nhiều so với lúc ông ấy nghĩ ra”.

Vì sao GCHQ gác lại lời giải

GCHQ chọn không dùng phương pháp của Cocks. “Họ đã suy tính rất nghiêm túc xem nên làm thế nào, nhưng rồi đi đến kết luận rằng việc đó quá tốn kém, và ở thời điểm ấy thì kết luận này hoàn toàn đúng,” Cocks nói. Ông giải thích rằng với máy tính thời đó, muốn triển khai thì phải có phần cứng chuyên dụng, mà kể cả vậy vẫn sẽ rất chậm. Ellis vốn muốn ý tưởng của mình giúp tiết kiệm chi phí chia sẻ khóa, và “khi mục tiêu là tiết kiệm tiền,” Cocks nói, “thì làm vậy sẽ không khả thi.”

Trong khi đó, các nhà nghiên cứu bên ngoài chính phủ đã tự mình đến được đích. Diffie và Hellman công bố bài báo “New Directions in Cryptography” (Những hướng đi mới trong mật mã học) vào tháng 11 năm 1976. Ron Rivest, Adi Shamir và Leonard Adleman ở MIT mô tả RSA, cái tên ghép từ chữ cái đầu trong họ của ba người, trong một bản ghi nhớ đề tháng 4 năm 1977. Tháng 2 năm 1978, họ công bố thuật toán này trên tạp chí Communications of the ACM của Hiệp hội Máy tính (ACM). Theo Chalkdust, ba người đã độc lập tìm ra cùng một lời giải như Cocks. Bộ ba này giành Giải Turing 2002 của ACM; Diffie và Hellman giành Giải Turing 2015.

24 năm sau

Bí mật được công khai là vì một bài thuyết trình. Tháng 12 năm 1997, Cocks có lịch phát biểu tại một hội nghị về mật mã học ở Cirencester, Anh, và đoán trước sẽ có người hỏi liệu mình từng nghiên cứu những phiên bản sơ khai của thuật toán RSA hay chưa. Để chặn trước những đồn đoán ấy, GCHQ giải mật công trình của ông. Ellis không kịp thấy thông báo này. Ông qua đời ngày 25 tháng 11 năm 1997, ở tuổi 73, vài tuần trước khi GCHQ công bố bản tường thuật của ông về câu chuyện.

Điều giai thoại không kể

Giai thoại biến phát hiện này thành một phút lóe sáng của thiên tài. Phần lược sử đi kèm một danh hiệu Cột mốc của Viện Kỹ sư Điện và Điện tử (IEEE) viết rằng “người ta cho rằng” Cocks tìm ra lời giải trong vòng nửa giờ. Còn Cocks thì nói đó là nhờ hoàn cảnh. Ông kể mình đã “ở đúng nơi, đúng lúc, và bài toán được giải thích cho tôi theo đúng cách”, và cho biết việc mới vào nghề cũng giúp ích: “Tôi chưa nhận ra hết đã có bao nhiêu người từng nghiên cứu bài toán này trước đây mà chưa thực sự tiến được bước nào.”

Công lao cũng không thuộc về riêng ai. Tấm biển Cột mốc IEEE được khánh thành ở Cheltenham năm 2010 ghi tên cả ba người và nêu rằng đến năm 1975, Ellis đã chứng minh rằng không nhất thiết phải có một hệ thống khóa bí mật đối xứng, còn Cocks cùng Williamson đã chỉ ra cách hiện thực hóa mật mã khóa công khai.

Không phải ai cũng công nhận trọn vẹn khẳng định của phía Anh. Năm 1998, chuyên gia bảo mật Bruce Schneier lập luận trên tạp chí Dr. Dobb’s Journal rằng những người lo bảo mật cho quân đội không nghĩ tới các vấn đề trong liên lạc kinh doanh và cá nhân, nên người Anh không coi phát minh của mình là lời giải cho bài toán quản lý khóa, và “khái niệm chữ ký số không nảy ra trong đầu họ”. Tuy vậy, bản tường thuật của chính Ellis lại bắt đầu từ bài toán quản lý khóa khiến quân đội đau đầu.

Đúng, nhưng quá sớm

Người ta dễ coi GCHQ là một bộ máy quan liêu ôm khư khư một bước đột phá. Cocks thì không nghĩ vậy: ông cho rằng quyết định của GCHQ là đúng trong bối cảnh lúc bấy giờ. “Hồi đó, thực ra chỉ có các chính phủ mới dùng đến mật mã,” ông nói. Về sau, hai điều đã thay đổi: khả năng của máy tính, và những ai cần trao đổi bí mật với người lạ.

Ellis đã gọi tên cái giá của sự bí mật. Ông viết rằng phần lớn các nhà khoa học đều muốn là người đầu tiên công bố, “bởi chính nhờ được phổ biến mà công trình mới phát huy được giá trị”. Mật mã học thì ngược lại. Sự ghi nhận của công chúng, rồi về sau là các Giải Turing, đã thuộc về những người công bố.

Ý tưởng nào nhóm của bạn đã gác lại vì cho là quá tốn kém, và từ đó đến nay đã có ai kiểm tra lại cái giá ấy chưa?

Bài liên quan

Đọc bằng ngôn ngữ khác: English