Một câu đố mã hóa bị lãng quên có ‘tuổi thọ’ 20 năm đã được giải mã

Vào đầu tháng 4/1999, khi đó kiến trúc sư nổi tiếng Frank Gehry đang thiết kế một tòa nhà mà sau này trở thành nơi "đóng đô" của Phòng thí nghiệm Khoa học máy tính và trí tuệ nhân tạo của MIT (viết tắt là CSAIL) thì nhận được một "viên nang thời gian" với chỉ dẫn nhằm tích hợp nó vào các bản thiết kế của ông.

Về cơ bản, "Viên nang thời gian" này là một viện bảo tàng về lịch sử sơ khai của máy tính, có chứa 50 món kỷ vật đóng góp bởi những người có đóng góp lớn cho sự phát triển của công nghệ máy tính như Bill Gates và Tim Berners-Lee.

"Viên nang thời gian" này được khóa bằng câu đố mã hóa bằng ngôn ngữ Java do Ron Rivest thiết kế. Nếu bạn chưa biết thì Ron Rivest chính là người được lấy tên đặt cho chữ "R" trong RSA - một trong những giao thức mã hóa quan trọng bậc nhất từng được tạo ra. Theo ước lượng của Ron Rivest, để tính toán ra câu trả lời cho câu đố mã hóa này, người ta sẽ phải cần tới khoảng 35 năm.

Vào ngày 15/4 vừa qua, sau gần 20 năm Rivest công bố câu đố, Bernard Fabrot một lập trình viên tự học người Bỉ đã tìm ra câu trả lời. Chỉ dẫn ban đầu của câu đố nói rằng, lời giải phải được gửi đến giám đốc Phòng thí nghiệm Khoa học máy tính. Nhưng năm 2003, phòng thí nghiệm đó đã được nhập vào phòng thí nghiệm AI của MIT để tạo ra CSAIL. Chính vì vậy, Fabrot đã liên hệ với Daniela Rus, giám đốc CSAIL, nhưng bà thậm chí còn không biết đến sự tồn tại của câu đố.

Về cơ bản, câu đố của Rivest xoay quanh việc tìm ra con số thu được từ việc thực hiện phép tính bình phương gần 80 nghìn tỷ lần, rồi dùng nó để chạy một phương trình toán học. Kết quả của phương trình được phiên dịch ra thành một cụm từ mang ý nghĩa chúc mừng. Cụm từ chính xác sẽ được Rivest và Fabrot công bố vào ngày 15/5 tới, khi "viên nang thời gian" được mở.

Để giải được câu đố này, bạn cần phải thực hiện một chuỗi các phép tính liên tục một cách tuần tự. Tức là có kết quả của phép tính trước, rồi dùng nó để thực hiện phép tính tiếp theo nên không thể sử dụng điện toán song song để tìm ra câu trả lời nhanh hơn được. Ngay cả siêu máy tính cũng không thể giải quyết được vấn đề.

Dựa vào quãng thời gian cần để chạy phép tính bình phương vào năm 1999 và định luật Moore, Rivest ước tính rằng phải mất khoảng 35 năm mới có thể tính toán ra được câu trả lời cho câu đố của mình.

Ron Rivest, người tạo ra câu đố mã hóa.

Vào năm 2015, Fabrot, hiện là một nhà phát triển độc lập, đã vô tình gặp câu đố này. Dù câu đố được mã hóa bằng ngôn ngữ Java, nhưng Fabrot nhận ra rằng nếu dùng GNU Multiple Precision Arithmetic Library, một phần mềm miễn phí chuyên dùng vào việc thực hiện các phép tính số học chính xác viết bằng ngôn ngữ C, thì có thể giải nhanh hơn.

Để giải câu đố, Fabrot đã dành riêng một nhân CPU trên máy tính để bàn của mình để chạy phép tính bình phương. Máy tính của Fabrot chạy phép tính 24/7, và chỉ nghỉ khi anh đi du lịch hoặc bị mất điện.

Fabrot cho biết, ngoài những người bạn rất thân anh không hề tiết lộ với ai về việc đang cố giải câu đố bởi anh sợ những người khác có thể dùng một CPU mạnh mẽ hơn để vượt mặt mình.

Cuối cùng Fabrot cũng hoàn tất hơn 80 nghìn tỷ phép tính bình phương và tìm ra câu trả lời cho câu đố của Rivest sau 3,5 năm.

Bernard Fabrot.

Tuy nhiên, có một nhóm các nhà khoa học máy tính và chuyên gia mã hóa, dẫn đầu bởi cựu kỹ sư Intel Simon Peffers, cũng đang thực hiện một dự án có tên là Cryptophage. Họ cũng sử dụng phần cứng chuyên dụng được thiết kế dành riêng cho việc giải mã câu đố MIT đó.

Fabrot hoàn toàn không biết về điều này.

Nhóm Cryptophage đang nghiên cứu các chức năng trì hoãn có thể kiểm chứng, một dạng hiện đại hơn của phương thức mã hóa trì hoãn thời gian sơ khai của Rivest, để làm cơ chế bảo mật cho các blockchain như Ethereum. Trong quá trình nghiên cứu, họ đã gặp câu đố của Rivest và sử dụng nó để thử nghiệm nghiên cứu của họ.

Vào giữa tháng 3, nhóm này bắt đầu chạy một thuật toán được thiết kế nhằm giảm khoảng trì hoãn giữa các phép tính bình phương, trên một con chip đa chức năng FPGA. Con chip này được lập trình để chạy một thuật toán cụ thể duy nhất nên có hiệu quả gấp 10 lần so với một CPU thương mại cao cấp chạy phần mềm chưa được tối ưu hóa.

Nhờ vậy, nhóm Cryptophage tính được rằng chỉ cần 2 tháng họ sẽ có lời giải chính xác cho câu đố của MIT, tối ngày 10/5. Thế nhưng khi họ liên hệ với MIT để thông báo rằng sắp có kết quả, thì biết rằng Fabrot đã đi trước một bước!

Rivest cho biết, ông đã rất kinh ngạc khi cả hai người cùng xuất hiện vào cùng một ngày để thông báo về việc đã giải được câu đố của mình. Rivest cũng thừa nhận rằng mình đã đánh giá quá cao độ khó của câu đố, ông không ngờ đến sự xuất hiện của những đột phá công nghệ như chip FPGA.

Buổi lễ mở "viên nang thời gian" sẽ được tổ chức vào ngày 15/5 tới, nhóm Cryptophage cũng sẽ có mặt dù họ không phải là người đầu tiên giải được câu đố.

Trong “viên nang” chứa những đóng góp từ Tim Berners-Lee, nhà phát minh ra World Wide Web; Bill Gates, người đã đóng góp phiên bản nguyên thủy của Altair BASIC, sản phẩm đầu tiên của Microsoft, Bob Metcalfe, người phát minh ra ethernet. Nhưng chỉ những người thiết kế ra nó mới biết được toàn bộ nội dung bên trong gồm những gì.

Fabrot cho biết anh rất hào hứng chờ đến ngày “viên nang” được mở để được thấy một bản sao nguyên bản của Zork, một trong những trò chơi PC đầu tiên, vốn được lưu trữ trong đó.