Một Lập trình viên Giải Quyết Một Đố Mã Hóa Đã Bị Lãng Quên Trong 20 Năm

Vào đầu tháng Tư năm 1999, một hòm thời gian được chuyển đến kiến trúc sư nổi tiếng Frank Gehry với hướng dẫn để tích hợp nó vào thiết kế cho tòa nhà sẽ chứa phòng thí nghiệm Máy tính và Trí tuệ Nhân tạo của MIT, hoặc CSAIL. Hòm thời gian này về cơ bản là một bảo tàng về lịch sử máy tính sớm, chứa 50 mục được đóng góp bởi những người như Bill Gates và Tim Berners-Lee.

Hòm thời gian này không dự định mở ra trong 35 năm nữa—trừ khi ai đó có thể giải quyết được câu đố mật mã được bao gồm trong thiết kế của nó. Câu đố được thiết kế bởi Ron Rivest, người tên “R” đóng góp cho RSA, có thể coi là một trong những giao thức mật mã quan trọng nhất từng được tạo ra. Ông nói rằng nó không được thiết kế để phức tạp. Thay vào đó, Rivest tạo ra câu đố để nó sẽ mất gần chính xác 35 năm để tính toán câu trả lời.

Vào ngày 15 tháng 4, gần 20 năm sau khi Rivest công bố câu đố, Bernard Fabrot, một lập trình viên tự học người Bỉ, đã giải quyết nó. Hướng dẫn ban đầu của câu đố đòi hỏi rằng giải pháp phải được gửi đến giám đốc Phòng thí nghiệm Khoa học Máy tính, nhưng Fabrot nói rằng anh ta ngạc nhiên khi biết rằng phòng thí nghiệm không còn tồn tại. (Nó đã được sáp nhập với phòng thí nghiệm AI của MIT vào năm 2003 để tạo ra CSAIL.) Thực tế, Fabrot nói rằng Giám đốc CSAIL Daniela Rus thậm chí không biết về sự tồn tại của câu đố khi anh ta nói với cô ấy rằng anh ta có câu trả lời.

Câu đố của Rivest cơ bản là tìm số kết quả từ việc chạy một phép bình phương gần 80 nghìn tỷ lần. Ví dụ, nếu bạn bắt đầu bằng cách bình phương 2, bạn sẽ có 4, sau đó bình phương 4 để có 16, và sau đó lặp lại quá trình này thêm 80 nghìn tỷ lần nữa. Bạn sau đó lấy số bạn đạt được và thực hiện một phép toán sử dụng số đó và một số được cho trong hướng dẫn của câu đố. Làm như vậy sẽ tạo ra một số mới có thể được dịch thành một câu chúc mừng ngắn. (Rivest và Fabrot từ chối tiết lộ cụ thể câu, sẽ được công bố khi mở hòm thời gian vào ngày 15 tháng 5.)

Chìa khóa của câu đố này là nó yêu cầu các phép toán liên tục, điều này có nghĩa là bạn không thể đạt được câu trả lời nhanh hơn bằng cách sử dụng tính toán song song. Bạn cần đi qua quá trình bình phương từng bước một, xây dựng trên các câu trả lời trước đó, để đạt được câu trả lời, vì vậy việc sử dụng nhiều máy tính hơn hoặc tung một siêu máy tính vào vấn đề sẽ không giúp ích gì. Dựa trên định luật Moore và thời gian chạy phép bình phương vào năm 1999, Rivest ước tính rằng việc tính toán câu trả lời cho câu đố nên mất khoảng 35 năm.

Fabrot, người làm việc như một nhà phát triển độc lập, nói rằng anh tình cờ phát hiện ra câu đố vào năm 2015. Mặc dù Rivest ban đầu phát hành mã câu đố bằng Java, Fabrot nhận ra rằng nó có thể được giải quyết nhanh hơn nếu anh ấy sử dụng Thư viện toán học đa chính xác GNU, phần mềm miễn phí viết bằng C để thực hiện “toán chính xác.” Vì vậy, Fabrot đã dành một trong các lõi CPU trên máy tính để bàn ở nhà để chạy các phép bình phương nhằm giải quyết câu đố. Anh nói rằng máy tính của anh chạy phép toán 24/7, trừ khi anh phải đi nghỉ hoặc có cắt điện.

“Suốt những năm này, tôi không nói với ai rằng tôi đang cố gắng giải quyết câu đố ngoại trừ những người bạn thân thiết,” Fabrot nói. “Tôi biết mình có cơ hội, nhưng nếu tôi nói cho ai đó, họ có thể đã sử dụng một CPU mạnh mẽ hơn để vượt qua tôi.”

Ba năm rưỡi sau đó, Fabrot cuối cùng đã hoàn thành khoảng 80 nghìn tỷ phép bình phương và đã tìm ra giải pháp cho câu đố. Thời điểm không thể tốt hơn. Mặc dù Fabrot không biết, một nhóm các nhà khoa học máy tính và chuyên gia mật mã đang làm việc trên dự án có tên là Cryptophage, sử dụng phần cứng chuyên dụng được thiết kế đặc biệt để giải quyết câu đố của MIT.

Dưới sự chỉ đạo của cựu kỹ sư Intel Simon Peffers, nhóm Cryptophage đang nghiên cứu về hàm trễ có thể xác minh như một cơ chế bảo mật có thể cho các blockchain như Ethereum. Hàm trễ có thể xác minh là một cách hiện đại hóa của công việc đầu tiên của Rivest về mật mã trễ thời gian, và giải pháp của chúng chỉ có thể được tạo ra thông qua các phép toán liên tục. Trong quá trình nghiên cứu của họ, Peffers nói rằng nhóm Cryptophage phát hiện ra câu đố của Rivest, có vẻ như là một cách tốt để kiểm tra nghiên cứu của họ.

Vào giữa tháng Ba, nhóm bắt đầu chạy một thuật toán được thiết kế bởi Erdinc Ozturk, một nghiên cứu viên tại Đại học Sabanci, được tối ưu hóa để giảm lượng trễ giữa các phép toán bình phương. Thuật toán này được triển khai trên một mạch cổng lập trình trường, một vi mạch đa năng được lập trình để chỉ chạy một thuật toán cụ thể, điều này làm cho nó hiệu quả hơn so với CPU chung. Sử dụng thuật toán của Ozturk, FPGA này nhanh khoảng 10 lần so với một CPU thương mại cao cấp chạy phần mềm không được tối ưu hóa.

Dựa trên hiệu suất tính toán của chip, nhóm Cryptophage tính toán rằng họ sẽ có câu trả lời đúng cho câu đố MIT vào tối ngày 10 tháng 5, chỉ hai tháng sau khi họ bắt đầu tính toán. Tuy nhiên, khi họ liên lạc với MIT để thông báo rằng một giải pháp sắp xảy ra, Rivest thông báo cho họ biết rằng Fabrot đã đánh bại họ trong cuộc đua.

“Chúng tôi không có ai đến với chúng tôi cho đến khi hai người này đến gặp chúng tôi vào cùng một ngày nói 'chúng tôi đã giải quyết vấn đề của bạn,'” Rivest nói. “Đó là một sự trùng hợp đáng kinh ngạc.”

Rivest thừa nhận ngay lập tức rằng ông đã đánh giá cao khả năng khó khăn của câu đố của mình. Dự đoán về sự cải thiện trong công nghệ là khó khăn trên quãng thời gian dài như vậy, và Rivest nói rằng ông không dự đoán được những bước đột phá như chip FPGA, chúng không phải là cấp độ phức tạp hoặc phổ biến như họ là ngày nay.

Mặc dù nhóm Cryptophage không phải là nhóm đầu tiên giải quyết câu đố, Peffers nói rằng họ vẫn sẽ tham gia lễ mở hòm thời gian vào ngày 15 tháng 5. Chỉ có những người thiết kế hòm biết đầy đủ nội dung của nó, mặc dù nó bao gồm đóng góp từ Tim Berners-Lee, người phát minh ra World Wide Web; Bob Metcalfe, người phát minh ra ethernet; và Bill Gates, người đóng góp phiên bản gốc của Altair BASIC, sản phẩm đầu tiên của Microsoft. Fabrot nói rằng anh ta rất hào hứng được xem một bản sao gốc của một trong những trò chơi PC sớm nhất, Zork, được bao gồm trong hòm.

Nhiều bài viết tuyệt vời khác trên Mytour

• “If you want to kill someone, we are the right guys”
• The best speed climbers dash up walls with this move
• Everything you need to know about open source software
• Kitty Hawk, flying cars, and the challenges of “going 3D”
• Tristan Harris vows to fight “human downgrading”
• 🏃🏽‍♀️ Want the best tools to get healthy? Check out our Gear team's picks for the best fitness trackers, running gear (including shoes and socks), and best headphones.
• 📩 Get even more of our inside scoops with our weekly Backchannel newsletter