Bài viết này giới thiệu một số thông tin về các số RSA, các thành tựu phân tích số, việc phân tích thành công đối với RSA - 768 và dự báo về việc phân tích RSA - 1024. Do phần lớn độ dài khoá phổ biến hiện nay đang sử dụng là 1024 bit nên việc phân tích thành công của RSA - 1024 sẽ có ý nghĩa quan trọng đối với việc ứng dụng thuật toán xác thực khoá công khai RSA.
Các số RSA “thách đố”
Trong toán học, các số RSA là một tập của các số tựa nguyên tố - semiprime (đó là những số chỉ có đúng 2 thừa số nguyên tố). Năm 1991, RSA Laboratories đã lập ra một danh sách “thách đố” gồm 53 số RSA [3]. Nội dung thách đố ở đây là việc phân tích các số này ra các thừa số nguyên tố. Việc này nhằm khuyến khích quá trình nghiên cứu  về khả năng tính toán và độ khó thực hành của việc phân tích các số lớn trong lý thuyết số.
Danh sách do RSA Laboratories  công bố gồm một loạt các số tựa nguyên tố với độ lớn từ 100 đến 617 chữ số thập phân. Các khoản tiền thưởng với các mức tương ứng đã được đề xuất cho việc phân tích một trong các số đó. Số RSA nhỏ nhất đã được phân tích trong một số ít ngày. Phần lớn các số đó vẫn chưa được phân tích và nhiều số trong chúng có khả năng là không phân tích được trong một thời gian nữa.
RSA - 129 không nằm trong Thách thức Phân tích RSA năm 1991, nhưng nó được đề cập tới trong số phát hành tháng 8/1997 của Tạp chí Scientific American [9] (mục thông tin của Martin Gardner).
Cho đến tháng 12/2009, có 14 trong số 54 số được đưa ra đã bị phân tích: Đó là 11 số RSA nhỏ nhất từ RSA - 100 cho đến RSA-576, cùng với RSA-640, RSA- 768 và RSA-  200.
Thách thức RSA đã kết thúc một cách công khai vào năm 2007, nhưng nhiều nhà nghiên cứu vẫn đang nỗ lực tìm cách phân tích chúng. RSA Laboratories cho rằng “Hiện nay xã hội đã có những tiến bộ đáng kể về sức mạnh của các thuật toán khoá đối xứng và khoá công

giải pháp công nghệ hai phổ biến, những thách thức này không còn nhiều ý nghĩa tích cực nữa” [4].
Các số RSA đầu tiên, từ RSA-100 đến RSA- 500 đã được đánh số theo số các chữ số thập phân của chúng. Sau đó, bắt đầu từ RSA -  576, các chữ số nhị phân đã được tính thay vào. Ngoại trừ RSA- 617 (có 2048 bit), nó đã được tạo ra từ trước.
Phân tích RSA -  768
Ngày 12/12/2009, RSA modulus 768- bit đã được một số nhà nghiên cứu cùng Paul Zimmermann phân tích bằng phương pháp sàng trường số [28]. Số RSA- 768 này được lấy từ danh sách Thách thức RSA đã cũ [1], đó là số có 768 bit. Đây là kỷ lục về phân tích số nguyên dạng tổng quát. Việc phân tích một RSA modulus 1024 - bit sẽ khó hơn khoảng một nghìn lần, cũng như việc phân tích một RSA modulus 768 - bit hàng nghìn lần khó hơn so với việc phân tích một RSA modulus 512 - bit. Việc phân tích thành công đầu tiên của một RSA modulus 512- bit đã tiến hành hàng chục năm trước [29], nên không phải là không có lý khi cho rằng các RSA modulus 1024 - bit có thể sẽ được phân tích trong khoảng 10 năm sau với những nỗ lực nghiên cứu. Vì vậy, cần thận trọng khi sử dụng các RSA modulus 1024 - bit trong 3 hay 4 năm nữa.
Kỷ lục trước đây về việc phân tích số bằng phương pháp sàng bình phương đã được thiết lập với số 663 - bit, đó là RSA -  200 với 200 chữ số thập phân được công bố ngày 9/5/2005. Các kỷ lục của việc phân tích số bằng sàng bình phương 663 - bit này và kỷ lục 768 - bit hiện nay không nên đánh đồng với việc phân tích sàng bình phương đặc biệt. Kỷ lục về phân tích sàng bình phương đặc biệt gần đây đã đạt được với số (21039 – 1) có 1039 bit, được thiết lập vào năm 2007 [30]. Mặc dù (21039 – 1) là lớn hơn nhiều so với RSA- 768, nhưng dạng đặc biệt của nó khiến cho dễ phân tích hơn so với RSA - 768.
Để phân tích được RSA - 768, nhóm nghiên cứu của Thorsten Kleinjung đã tốn nửa năm, chạy trên 80 bộ xử lý để thực hiện lựa chọn đa thức. Nhưng so với công việc chính là sàng (sieving) thì việc này chỉ chiếm 3%, việc sàng đã được làm trên vài trăm chiếc máy tính và mất gần 2 năm. Nếu việc này được làm trên một bộ xử lý 2,2 GHz AMD Opteron có 1 lõi với 2 GB RAM thì sẽ mất 1.500 năm. Việc sàng bao gồm khối lượng lớn của bước sàng qua (oversieving) -  đó là công việc phức tạp nhất và bước xử lý ma trận (matrix step), bước này dễ điều khiển hơn. Việc chuẩn bị dữ liệu cho bước xử lý ma trận chiếm hai tuần trên một số bộ xử lý. Bước cuối cùng sau bước xử lý ma trận chiếm gần nửa ngày, nhưng mất hơn 4 ngày làm việc tiếp theo bởi vì cần phải chỉnh sửa một số lỗi.
Thorsten Kleinjung và các cộng sự đã phải làm 2 lần việc sàng cần thiết để nhận được một ma trận sử dụng được và dữ liệu phụ thêm cho phép sinh ra một ma trận dễ xử lý hơn so với dự liệu khi bắt đầu dự án. Mặc dù nhóm các nhà mật mã trên đã tốn thời gian máy tính cho việc sàng nhiều hơn so với yêu cầu, nhưng việc sàng là một quá trình đã được sắp đặt ngược, nên khi đã khởi động thì không đòi hỏi phải quan tâm nhiều, ngoại trừ việc khởi động lại máy bất ngờ. Ngược lại, bước xử lý ma trận là một công việc tinh tế hơn, ở đó một biến động nhỏ dễ gây ra rủi ro lớn, đặc biệt nếu như vấn đề là do việc kéo căng kích thước tuyệt đối của tài nguyên có thể sử dụng. Cho nên, giải pháp đã được sử dụng là xử lý phụ trội đối với phần dễ tính toán nhằm thiết lập một ma trận có thể được xử lý tương đối mịn, tránh được những rắc rối đáng kể. Một lý do quan trọng khác đằng sau việc sàng là dữ liệu sàng thêm cho phép chúng ta tiến hành các thí nghiệm khác nhau với mục đích biết được nhiều hơn về quan hệ giữa việc sàng, cách xử lý ma trận và hiệu ứng đối với hiệu suất của sàng trường số cũng như hiệu suất tổng thể. Đây là một nghiên cứu đang tiến hành và các kết quả của nó sẽ được thông báo.
Với số (21039–1), các bước xử lý ma trận lần đầu tiên đã được thực hiện trên một số các cụm tính toán khác nhau [30]. Phần chính của việc tính toán đã được thực hiện song song tại hai địa điểm trên 4 cụm máy tính. Trước đó, do đã sử dụng thuật toán khối Weidemann cho bước xử lý ma trận [31] nên tiếp theo sẽ thực hiện 2 dãy liên tiếp nhau của các phép nhân ma trận với vecto. Như đã bàn luận [32], mức độ thực hiện song song và độc lập dẫn tới sự đa dạng của các  mức thách đố cần phải vượt qua trước khi các vấn đề lớn hơn có thể giải quyết, chẳng hạn như các modulo 1024- bit. Ở đây, các tác giả [2] đã thực hiện những bước đầu tiên để chỉ ra rằng tính mềm dẻo hơn có thể đạt được nhờ số lượng và khả năng thực hiện của các cụm độc lập khác nhau. Kết quả là bước xử lý ma trận khó hơn 9 lần (so với 21039 - 1) đã được giải trong thời gian ít hơn 4

háng chạy trên 8 tiến trình độc lập tại các cụm  máy tính được đặt ở Pháp, Nhật và Thuỵ sỹ. Khi chạy một bước nhỏ trong các tiến trình này cũng cần đến khoảng một terabyte bộ nhớ. Những con số này hàm ý rằng các ma trận lớn đã có thể thực hiện được, nhưng khả năng xử lý ma trận cần thiết cho việc phân tích số 1024 bit bằng sàng trường số vào năm 2020 vẫn còn chưa chắc chắn. Như một phần của các thí nghiệm đã được nhắc tới ở trên, nhóm nghiên cứu cũng dự định phân tích xem một cụm lớn duy nhất có thể xử lý được các ma trận như thế hay không nhờ thuật toán khối Lanczos [33]. So với khối Weidemann thì thuật toán này có các ưu thế là một dãy duy nhất ngắn hơn của các phép lặp và không có bước trung tâm Berlekamp - Massey phức tạp và tốn nhiều bộ nhớ [34] nhưng cũng có những nhược điểm như không thể chạy trên các cụm tách rời nhau và mỗi lần lặp sẽ bao gồm phép nhân ma trận cho cả ma trận và chuyển vị của nó.Như vậy, cùng với việc phân tích thành công RSA -  768 và sự phát triển của công nghệ tính toán thì triển vọng phân tích được RSA - 1024 cũng nằm trong tương lai không xa. Việc sử dụng thuật toán xác thực khóa công khai RSA với khóa 1024 bit cần quan tâm tới các quá trình phân tích này