AI tái hiện phép tính chữ ký RSA 1024 bit trong 3 ngày 22 giờ, con người phê duyệt các bước then chốt

Hai tác nhân AI của Google DeepMind đã tái hiện phép tính chữ ký RSA 1024 bit từ khâu thiết kế đến xác minh kết quả trong 3 ngày 22 giờ, với khoảng 20 tin nhắn trao đổi từ nhà nghiên cứu.

Google DeepMind mô tả công việc này trong bài nghiên cứu dạng working paper là một thử nghiệm tái hiện trường hợp RSA 1024 bit đã được nghiên cứu trước đó. Tác nhân giám sát phụ trách thiết kế, ngân sách tính toán và xác minh từng bước; tác nhân thực thi viết mã, triển khai công việc phân tán và sửa lỗi. Một tác nhân hỗ trợ riêng cũng được dùng cho một bước trong phần đại số tuyến tính.

Nhà nghiên cứu đặt mục tiêu và điều kiện tính toán, đồng thời phê duyệt những bước không thể đảo ngược. Người này không trực tiếp viết mã hay chạy các tác vụ phân tán.

Các tác nhân viết khoảng 33.500 dòng mã mới và thực hiện 336 thử nghiệm phân tán. Công việc sử dụng tối đa khoảng 300.000 lõi CPU cùng 16 GPU.

Thử nghiệm không khôi phục khóa riêng RSA và cũng không phân tích thành thừa số nguyên mô-đun RSA. Nghiên cứu không được tiến hành bằng cách truy cập một hệ thống đang vận hành.

Nhóm nghiên cứu gửi trước khoảng 4 tỷ đầu vào tới oracle, một chương trình trả về kết quả của phép toán ký. Sau đó, họ ngắt kết nối oracle và tiếp tục tính toán.

Sau khi ngắt oracle, các tác nhân tính nghiệm căn modulo cho một giá trị đích mới. Khi giá trị đích đã được xác định, nhóm không thể gửi thêm yêu cầu. Trong những điều kiện nhất định, nghiệm này có thể được dùng để tạo chữ ký hợp lệ cho một thông điệp mới. Thử nghiệm diễn ra trong môi trường cô lập.

Để so sánh, nghiên cứu trước đó dùng 1.380 CPU core-year để tính nghiệm đầu tiên trong cùng trường hợp RSA 1024 bit. Bài nghiên cứu của DeepMind báo cáo mức sử dụng 391 CPU core-year.

CPU core-year là lượng tính toán tương ứng với việc sử dụng một lõi CPU trong một năm. Hai nghiên cứu dùng cùng thuật toán, mô-đun, đa thức và giá trị biên. Theo bài nghiên cứu, chênh lệch 3,5 lần phản ánh cải thiện trong cách triển khai và thực thi, chứ không phải hiệu năng của một thuật toán mới.

Nghiên cứu trước mất khoảng 5 tháng. Thử nghiệm của DeepMind mất 3 ngày 22 giờ từ khâu thiết kế đến xác minh kết quả, và 3,2 ngày tính từ lúc bắt đầu quá trình sàng lọc quy mô lớn.

Bài nghiên cứu cho biết mức độ song song hóa là lý do chính khiến thời gian hoàn thành khác nhau. CPU core-year đo tổng lượng tính toán, còn thời gian thực tế phụ thuộc vào mức độ chia nhỏ và xử lý đồng thời các công việc.

Con số 391 CPU core-year không bao gồm công việc đại số tuyến tính trên GPU và 7,5 CPU core-year dành cho thử nghiệm sơ bộ, diễn tập. Nhóm nghiên cứu ước tính nếu quy đổi công việc GPU sang chi phí CPU của nghiên cứu trước, chênh lệch là 3,4 lần; nếu tính cả phần việc sơ bộ, chênh lệch là 3,3 lần. Hai phép tính được thực hiện trên phần cứng khác nhau.

Trong quá trình xác minh, nhóm phát hiện lỗi chỉ mục 32 bit vượt giới hạn, khiến câu trả lời đã lưu bị đọc sai. Các tác nhân sửa lỗi mà không cần thực hiện lại những yêu cầu đã gửi trước đó tới oracle.

Bài nghiên cứu nêu rõ kết quả này không đe dọa tính bảo mật của các hệ thống hiện dùng RSA-2048 trở lên.

Thử nghiệm không kiểm tra chữ ký Bitcoin (BTC). Dự án phát triển Bitcoin hỗ trợ chữ ký ECDSA và Schnorr dựa trên đường cong secp256k1 thông qua libsecp256k1. TokenPost trước đây cũng đưa tin rằng ước tính phân tích thành thừa số RSA-2048 và phép tính chữ ký Bitcoin là hai vấn đề khác nhau.