RSA-129 là bức mật thư mà ba nhà khoa học MIT đăng năm 1977 kèm lời hứa rằng phải mất chừng bốn mươi triệu tỷ năm mới có người đọc được. Đến tháng 4/1994, câu bên trong đã được giải mã, nhờ khoảng sáu trăm tình nguyện viên dùng máy tính rảnh rỗi của mình qua thư điện tử. Chuyện đáng nhớ vì nó cho thấy một lời hứa "không thể phá" thực ra luôn dựa vào hình dung về kẻ đối địch.

Tóm tắt nhanh

Năm 1977, Ron Rivest, Adi Shamir và Leonard Adleman công bố mật mã RSA, kèm một bức mật thư khoá bằng số 129 chữ số và 100 đô la cho người đọc được. Năm 1993–1994, nhóm của Arjen Lenstra, Derek Atkins, Michael Graff và Paul Leyland huy động tình nguyện viên khắp thế giới để tách con số ấy bằng phương pháp "sàng bậc hai". Con số vỡ thành hai thừa số 64 và 65 chữ số, bản rõ hiện ra: "The magic words are squeamish ossifrage". Thứ sụp đổ là lời dự báo thời gian, còn RSA với khoá dài vẫn đứng vững.

Diễn biến chính

1977: RSA ra đời và bức mật thư của Gardner

Mùa xuân 1977, tại MIT, Rivest, Shamir và Adleman theo đuổi ý tưởng "khoá công khai": ai cũng khoá được, chỉ một người mở được. Theo lời kể thường gặp (qua cuốn The Code Book của Simon Singh), bước ngoặt của Rivest đến vào một đêm lễ Vượt Qua; đây là giai thoại, không phải tài liệu gốc. Cốt lõi: nhân hai số nguyên tố lớn rất dễ, tách tích ngược lại thì cực khó.

Tháng 8/1977, Martin Gardner dành kỳ chuyên mục "Mathematical Games" trên Scientific American cho phát minh này. Cuối bài là bức mật thư khoá bằng số 129 chữ số, thưởng 100 đô la cho ai đọc được. Rivest ước tính phải mất khoảng bốn mươi triệu tỷ năm với máy và thuật toán thời đó.

1988: phân tích số bằng thư điện tử

Arjen Lenstra, làm việc tại Bellcore (New Jersey), cùng cộng sự nhận ra hàng nghìn máy trạm bị bỏ chạy không mỗi đêm. Họ viết chương trình chạy khi máy rảnh, gửi kết quả qua thư điện tử. Năm 1988, hàng trăm máy cùng tách được một số 100 chữ số, lần đầu một bài toán lớn tìm tình nguyện viên qua mạng.

Tháng 8/1993: lời kêu gọi trên danh sách cypherpunks

Derek Atkins (MIT), Michael Graff (Đại học bang Iowa) và Paul Leyland (Oxford) tìm đến Lenstra xin một bài toán đủ nổi tiếng; ông chỉ họ đến RSA-129. Lenstra viết phần mềm, Atkins giữ máy chủ ở MIT, Graff tuyển người, Leyland chỉnh chương trình. Ngày 23/8/1993, Graff đăng lời kêu gọi, mục tiêu khoảng mười nghìn máy trạm khi mới có chừng năm trăm. Chương trình không chiếm máy khi có người dùng, ai tham gia cũng nhận mã nguồn, và 100 đô la tiền thưởng sẽ tặng Quỹ Phần mềm Tự do.

1993–1994: tám tháng sàng số

Nhóm dùng "sàng bậc hai": tạo hàng tỷ con số, giữ lại những số bẻ vụn hoàn toàn được thành các số nguyên tố nhỏ trong một danh sách cố định (khoảng nửa triệu số). Mỗi số đạt chuẩn là một "quan hệ"; gom đủ nhiều thì ghép lại để tách con số gốc. Mỗi máy sàng một vùng riêng nên rất hợp với Internet.

Theo thông báo năm 1994, công việc kéo dài khoảng tám tháng, với khoảng sáu trăm người ở hơn hai mươi nước, trên mọi châu lục trừ Nam Cực, tương đương khoảng 5.000 MIPS-năm. Kết quả là 569.466 quan hệ, gửi về MIT kiểm tra rồi chuyển cho Lenstra.

Tháng 4/1994: con số vỡ đôi

Lenstra thu gọn bảng số khổng lồ rồi đưa phần lõi lên máy song song MasPar với mười sáu nghìn bộ xử lý, chạy 45 giờ. Ba tổ hợp đầu chỉ cho thừa số tầm thường; tổ hợp thứ tư thành công, tách số thành hai thừa số 64 và 65 chữ số. Bản rõ hiện ra: "The magic words are squeamish ossifrage". Bellcore thông báo ngày 26/4/1994. Lenstra nói năm 1977 điều này là không thể tưởng tượng; Rivest gọi đó là một mốc đo hữu ích.

Sau 1994: RSA không chết, lời dự báo thì sụp

Khoá bị phá chỉ dài 426 bit, trong khi bài báo năm 1978 đã khuyên dùng khoảng 200 chữ số. Sàng trường số về sau trở thành công cụ chính, còn khoá thực tế được kéo dài lên 512, 1024, 2048 bit. Cách làm này lan sang distributed.net (1997) và SETI@home (1999). Năm 2015, theo lời kể, một lập trình viên là Nat McHugh làm lại bài toán trong khoảng một ngày với chừng ba mươi đô la.

Điều còn tranh cãi hoặc cần thận trọng

  • Con số "bốn mươi triệu tỷ năm": kịch bản lưu ý Rivest tính cho một số ngắn hơn chút, với máy và thuật toán năm 1977; có người còn cho con số này bị thổi phồng.
  • Các con số tròn: số người (600 hay 1.600 máy), thời gian (6 hay 8 tháng) và kết quả năm 2015 (một ngày hay ít phút) khác nhau tuỳ nguồn.
  • Hai chiếc máy fax: chi tiết này chỉ xuất hiện trong một bài báo năm 1996, tài liệu của chính nhóm không nhắc tới.
  • "Ossifrage": là kền kền râu, không phải chim ưng biển như nhiều bản dịch viết.

Vì sao câu chuyện này đáng nhớ?

Mỗi lời hứa "không thể phá" đều ngầm nói thêm: không thể với đối thủ mà người hứa hình dung. Năm 1977, đối thủ ấy là một người với một chiếc máy; năm 1994, đó là một đám đông chưa từng tồn tại, được thư điện tử nối lại. Không thuật toán nào sai, chỉ có bức chân dung kẻ địch đã cũ.

Từ đó giới mật mã thôi hỏi một chiếc máy cần bao lâu, mà hỏi đối thủ có bao nhiêu tiền, người và thời gian. Khi nghe những lời hứa tương tự về hệ thống an toàn hay máy thông minh, câu hỏi hữu ích vẫn là: không thể, với bao nhiêu người cùng làm?

Câu hỏi thường gặp

RSA-129 là gì?

Là bức mật thư khoá bằng một số 129 chữ số, công bố trên Scientific American tháng 8/1977 kèm giải thưởng 100 đô la. Số này là tích của hai số nguyên tố dài 64 và 65 chữ số.

Ai đã giải được RSA-129?

Nhóm do Arjen Lenstra, Derek Atkins, Michael Graff và Paul Leyland điều phối, với khoảng sáu trăm tình nguyện viên góp máy tính. Kết quả công bố ngày 26/4/1994.

Câu bí mật trong bức thư là gì?

"The magic words are squeamish ossifrage", nghĩa là những chữ thần chú là con kền kền bẻ xương khó tính. Ossifrage là tên cổ của kền kền râu.

Việc giải RSA-129 có nghĩa là RSA đã bị phá?

Không. Khoá bị phá dài 426 bit, còn bài báo năm 1978 đã khuyên dùng khoảng 200 chữ số. Về sau người ta chỉ việc dùng khoá dài hơn.

Nguồn tham khảo

  • M. Gardner, "Mathematical Games", Scientific American 237(2), tháng 8/1977
  • R. Rivest, A. Shamir, L. Adleman, bài báo trên Communications of the ACM, 1978
  • Atkins, Graff, Lenstra, Leyland, thông báo phân tích RSA-129 (4/1994, bản lưu danh sách thư MIT)
  • Bellcore, thông cáo báo chí ngày 26/4/1994 (đăng lại trên danh sách cypherpunks)
  • M. Graff, "Large factoring attempt on RSA-129", cypherpunks, 23/8/1993
  • M. Janeba, "Factoring Challenge Conquered" (Đại học Willamette)
  • Wikipedia, "The Magic Words are Squeamish Ossifrage"
  • J. D. Cook, bài về bài báo RSA của Martin Gardner (2025)

Bài viết tóm tắt từ video của kênh; nội dung mang tính giới thiệu.