Kỹ sư Cognition dùng AI agent Devin phá kỷ lục giải mã RSA-260

Bởi Eric Lu09.09.26

Trong vài tuần qua, nhóm nghiên cứu Cognition và tôi đã tối ưu hóa bộ lập lịch công việc (job scheduler) của mình để tận dụng tốt hơn các tài nguyên tính toán phân tán (disaggregated compute). Như một bằng chứng về khái niệm (proof of concept), và vì tôi vốn có sở thích phân tích thừa số các con số trong khoảng mười năm nay, tôi đã điều khiển một nhóm các Devin để thực hiện phân tích thừa số RSA-260. Để làm được điều này, các Devin của tôi đã xây dựng bộ sàng lưới (lattice siever) trên GPU có hiệu suất cao nhất thế giới, cho phép phân tích thừa số các con số với chi phí thấp hơn 10 lần so với công nghệ tiên tiến nhất được công bố trước đây. Dưới đây là kết quả phân tích thừa số:

RSA-260 (một con số gồm 260 chữ số) thiết lập một kỷ lục mới cho bài toán RSA Factoring Challenge lớn nhất từng được giải quyết công khai, vốn là thước đo tính khả thi của việc phá vỡ hệ thống mật mã RSA. Kỷ lục trước đó, RSA-250, được thiết lập vào tháng 2 năm 2020. Để tham khảo, các khóa công khai RSA hiện đại chứa các bài toán phân tích thừa số 2048 bit (~617 chữ số), trong khi RSA 1024-bit (~309 chữ số) đã bị loại bỏ từ năm 2013.

Dưới đây tôi sẽ cung cấp một số chi tiết về cách thực hiện điều này, nhưng đây là hai điểm rút ra quan trọng:

Các nhà cung cấp dịch vụ đám mây quy mô lớn (hyperscalers) hoặc các phòng thí nghiệm AI tiên phong có khả năng phân tích thừa số các con số RSA-1024 với chi phí vào khoảng 30 triệu đô la mỗi số — và với một chút tối ưu hóa nữa, con số này có thể thấp hơn đáng kể. Mặt khác, RSA-2048 vẫn khó hơn khoảng một tỷ lần so với RSA-1024 và dường như không bị ảnh hưởng đáng kể bởi công trình này.

Devin là một kỹ sư phần mềm đủ mạnh để giải quyết một vấn đề đầy thách thức nằm ở điểm giao thoa giữa lý thuyết số tính toán và kỹ thuật hiệu năng GPU. Vai trò của tôi chủ yếu là thiết lập các ưu tiên, thiết lập các tiêu chuẩn đánh giá (benchmarks) và nhận biết khi nào công việc đi chệch hướng. Ngoài ra, Devin đã tự chủ xử lý các phép đo, vận hành cụm máy chủ (cluster) và tối ưu hóa từ đầu đến cuối. Điều này thay thế cho công việc mà lẽ ra phải mất nhiều tháng thực hiện bởi một nhóm các chuyên gia chuyên môn cao.

Tóm lại, rào cản gia nhập đối với công việc phân tích mật mã, toán học tính toán nói chung và có lẽ là hầu hết các nghiên cứu tính toán khoa học quy mô lớn, đã thấp hơn nhiều so với trước đây. Những công việc thú vị đang chờ đợi ở bất cứ nơi nào lập trình có thể được sử dụng để giải quyết một vấn đề nghiên cứu; tôi khuyến khích tất cả mọi người hãy đầy tham vọng và khám phá những gì các tác nhân kỹ thuật phần mềm tự chủ có thể làm khi được áp dụng vào các lĩnh vực này!

Điều này đã xảy ra như thế nào?

Trái ngược với một số tuyên bố đang lan truyền, tôi không phân tích thừa số RSA-260 bằng cách đoán và kiểm tra thủ công các số nguyên tố 130 chữ số. Cognition cũng chưa chế tạo máy tính lượng tử hàng nghìn qubit. RSA-260 đã được phân tích thừa số bằng một bản triển khai mới của thuật toán sàng trường số tổng quát (GNFS) cho GPU, được chuẩn bị và chạy bằng Devin. GNFS là thuật toán hiệu quả nhất được biết đến cho (hầu hết) các con số có kích thước trên khoảng 100 chữ số và đã được sử dụng trong các lần phân tích thừa số RSA phá kỷ lục trước đây.

Bản triển khai này là một phiên bản CADO-NFS đã được sửa đổi đáng kể. Tôi báo cáo rằng về cơ bản không có tiến bộ thuật toán nào — việc triển khai sàng lưới và giải hệ phương trình tuyến tính thưa trên GPU chỉ đòi hỏi "kỹ thuật hiệu năng kiểu cũ" để tận dụng các hệ thống bộ nhớ phi lý của GPU.

Ước tính chi phí

Tổng cộng, tôi ước tính rằng quá trình phân tích thừa số này tiêu tốn khoảng 4.900 GPU-ngày, hay 13,5 GPU-năm, tương đương khoảng 400 nghìn đô la theo giá thị trường hiện tại. Chi tiết hơn, các bản triển khai GNFS hiện đại bao gồm một vài giai đoạn chạy tuần tự: chọn đa thức, sàng lưới và giải hệ phương trình tuyến tính. Thời gian phân bổ như sau:

643 GPU-ngày cho việc chọn đa thức (con số này cao bất thường về cơ bản là do sự thiếu năng lực của người vận hành)

3.813 GPU-ngày cho việc sàng lọc

467 GPU-ngày cho việc giải hệ phương trình tuyến tính (trong đó khoảng 7% thất bại trong việc đạt tiến triển do sự cố hoặc bị chiếm quyền ưu tiên bởi các công việc quan trọng hơn)

Tôi đã thực hiện việc này như một dự án phụ bằng cách sử dụng một tỷ lệ phần trăm nhỏ (một chữ số) trong cụm máy chủ của chúng tôi, trong quá trình tối ưu hóa bộ lập lịch công việc để cải thiện việc phân bổ nhằm sử dụng tài nguyên tính toán phân tán. Điều này có ý nghĩa gì đối với các trường hợp RSA lớn hơn?

RSA-1024 tương đương với 309 chữ số; theo quy mô GNFS tiêu chuẩn, con số này chỉ tốn nhiều hơn 78 lần tính toán so với RSA-260. Tôi ước tính chi phí phân tích thừa số RSA-1024 theo giá GPU thị trường vào khoảng 30 triệu đô la, con số này có thể đánh đổi với thời gian thực tế (wall clock time). Tôi biết chắc chắn rằng bản triển khai hiện tại vẫn còn dưới mức tối ưu đáng kể; tôi sẽ không ngạc nhiên nếu công việc tiếp theo ở mức độ vừa phải có thể giảm chi phí phân tích thừa số RSA-1024 thêm một hệ số 2 nữa.

Tất nhiên, việc RSA-1024 không an toàn không phải là tin mới. Đã có suy đoán rằng NSA có thể có khả năng thực hiện RSA-1024 về mặt kinh tế từ đầu những năm 2000 (xem ví dụ TWIRL hoặc máy Bernstein). Thay vào đó, như chúng tôi mô tả dưới đây, những phát triển chính là (1) chi phí tiềm năng thấp hơn (tính bằng đô la và thời gian) cho việc phân tích thừa số, (2) khả năng có nhiều bên hơn có thể thực hiện phân tích thừa số (bạn chỉ cần đủ GPU thay vì chế tạo phần cứng chuyên dụng), và (3) sự dễ dàng tương đối mà những người không chuyên về mật mã hiện có thể làm việc để tăng tốc độ phân tích thừa số.

Cuối cùng, tôi nhấn mạnh rằng các cải thiện về hiệu suất có rất ít tác động đến tính khả thi của việc phân tích thừa số các con số có kích thước RSA-2048 bằng GNFS.

Phân tích thừa số trên tài nguyên tính toán dư thừa

Việc phân tích thừa số chạy với chi phí biên bằng không trên các tài nguyên tính toán dư thừa hoặc phân mảnh không thể sử dụng cho các mục đích khác. Tại sao tài nguyên tính toán này lại tồn tại?

Các cụm máy chủ chúng tôi sử dụng để huấn luyện và suy luận LLM chứa các rack NVL72, mỗi rack về danh nghĩa bao gồm 18 máy tính được kết nối với nhau bằng NVLink tốc độ cao. Các khối lượng công việc LLM sử dụng các nhóm máy tính trong cùng một rack để tận dụng kết nối tốc độ cao này. Bộ lập lịch công việc phải giải quyết một bài toán tối ưu hóa có ràng buộc để đóng gói khối lượng công việc vào các rack. Trong việc phân bổ toàn cục này, một số rack có thể kết thúc với một hoặc hai node nhàn rỗi; đôi khi các công việc yêu cầu các node dự phòng để phục vụ chuyển đổi dự phòng (failover), hoặc các công việc có thể cần số lượng máy tính chẵn trên một rack chỉ có 17 máy. Đối với chúng tôi, những sự kém hiệu quả này chiếm một tỷ lệ phần trăm nhỏ trong tổng tài nguyên tính toán.

Để tận dụng tài nguyên tính toán dư thừa này, bước đầu tiên, tôi đã thiết lập bộ lập lịch công việc của chúng tôi để lấp đầy các công việc đơn node xung quanh các khối lượng công việc khác ở mức ưu tiên thấp nhất. Tuy nhiên, chúng tôi cũng thiếu một nguồn công việc đơn node có thể dễ dàng bị chiếm quyền ưu tiên (preemptible). Đương nhiên, tại thời điểm này, tôi nghĩ đến việc sàng lưới, vốn rất phù hợp với tình huống này.

Sàng lưới có khả năng song song hóa cực cao trên hàng tỷ đơn vị công việc nhỏ, có thể đạt tiến triển bằng cách sử dụng từng node một và an toàn để bị chiếm quyền ưu tiên ngay lập tức. Đây cũng là phần tốn kém nhất về mặt tính toán của GNFS, vì vậy việc hoàn thành sàng lọc là một bước tiến lớn hướng tới việc phân tích thừa số. Tuy nhiên, tất cả các kỷ lục phân tích thừa số GNFS công khai trước đây chỉ sử dụng CPU để sàng lưới; thực tế, do những thách thức trong việc triển khai sàng lưới hiệu quả trên GPU, trong một thời gian dài, không rõ liệu sàng lưới trên GPU có thể hiệu quả hơn về chi phí tổng thể hay không.

Tóm lại, tất cả những gì tôi còn thiếu là một bộ sàng lưới trên GPU hiệu suất đủ cao có thể chấp nhận các tham số cần thiết để phân tích thừa số RSA-260. Vậy, tôi đã làm gì? Hỏi Devin.

Sử dụng Devin để tối ưu hóa GNFS

Vào lúc 0:11:58 ngày 13 tháng 8 theo giờ Thái Bình Dương, tôi đã hướng Devin tạo ra một bản thay thế trực tiếp (drop-in replacement) cho las, bộ sàng lưới CPU của CADO-NFS. Đây là câu lệnh (prompt) tôi đã sử dụng:

Hai giờ sau, tôi nói thêm rằng glas (tất nhiên là GPU las) sẽ có thể xử lý các tham số được sử dụng cho RSA-250. Sau đó tôi đi ngủ. Tôi thức dậy và thấy rằng, sau 7 giờ lặp lại nữa, Devin đã thành công.

Trong tuần tiếp theo, tôi đã điều khiển Devin tối ưu hóa việc sàng lưới, sau đó là phần còn lại của quy trình GNFS. Trước tiên, tôi sẽ đưa ra mô tả cấp cao về các tối ưu hóa GNFS của chúng tôi, và sau đó tôi sẽ mô tả quy trình tối ưu hóa.

Các tối ưu hóa GNFS (cấp cao)

Ở cấp độ cao, GNFS bao gồm một số giai đoạn chạy tuần tự: chọn đa thức, sàng lưới và giải hệ phương trình tuyến tính.

Việc chọn đa thức cố định trường số mà thuật toán chạy trên đó. Việc lựa chọn đa thức kiểm soát tốc độ tăng tốc theo hệ số hằng số ở bước sàng lưới. Do đó, thường đáng để dành một phần cố định (~5%) tổng tài nguyên tính toán sàng lọc để tìm một đa thức "tốt". Có rất ít đổi mới kỹ thuật ở đây; chúng tôi đã điều chỉnh việc chọn đa thức giai đoạn 1 của CADO sang GPU (dẫn đến gps1), đồng thời sử dụng một số thiết bị kernel từ việc chọn đa thức giai đoạn 1 được tối ưu hóa tốt của msieve. Việc chọn đa thức ít nhiều có khả năng song song hóa cực cao.

Phần lớn nỗ lực tính toán của GNFS nằm ở việc sàng lưới. Mục tiêu của sàng lưới là tạo ra rất nhiều (8,3 tỷ trong trường hợp của chúng tôi) các quan hệ tuyến tính thưa trên GF(2), trong đó (lược bỏ một số chi tiết) các mục vector đại diện cho tính chẵn lẻ của các số mũ nguyên tố trong phân tích thừa số nguyên tố của một số trơn (smooth number). Sàng lưới cũng có khả năng song song hóa cực cao trên các mục công việc được gọi là "special q", nhưng mỗi mục công việc đòi hỏi phải thực hiện một số lượng lớn các thao tác đọc/ghi tại (theo mục đích của chúng tôi) các vị trí giả ngẫu nhiên trong một mảng lớn; xử lý điều này là thách thức kỹ thuật chính trong việc tối ưu hóa sàng lọc.

Cuối cùng, chúng tôi đóng gói các quan hệ này vào một ma trận lớn trên GF(2) và sử dụng giải hệ phương trình tuyến tính để tìm sự phụ thuộc tuyến tính. Ở quy mô này, giải hệ phương trình tuyến tính thường được phân tán và đòi hỏi băng thông truyền thông lớn; điều này có sẵn rất nhiều qua Infiniband và NVLink. Thuật toán block Wiedemann cho phép nới lỏng ràng buộc truyền thông phần nào, và bản triển khai cụ thể trong CADO-NFS cũng có thể tối ưu hóa và chạy trên GPU, điều mà chúng tôi đã thực hiện. Các nghiệm có thể được xử lý thành các đồng dư bình phương modulo N, từ đó thu được kết quả phân tích thừa số.

Nhìn chung, Devin đã sửa đổi đáng kể hầu hết mọi phần, bao gồm việc sửa đổi một vài giao diện:

Một phiên bản thích ứng GPU của polyselect giai đoạn 1 của CADO-NFS, với các thành phần từ msieve

Một bộ sàng lưới tối ưu hóa trên GPU dựa trên las

Một CADO head được tối ưu hóa để xử lý khối lượng đơn vị công việc

Các chương trình dup/purge được song song hóa và tối ưu hóa cùng với các chương trình merge/replay được hợp nhất