Đề tài Giải thuật RSA

TỔNG CÔNG TY BƯU CHÍNH VIỄN THÔNG VIỆT NAM HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------- Báo cáo bài tập lớn GIẢI THUẬT RSA Nhóm biên soạn: Bùi Minh Tuấn Lê Việt Dương Nguyễn Thị Thu Huyền Phan Văn Quân Hà nội tháng 5 năm 2007 LỜI NÓI ĐẦU Thuật toán mã hóa công khai đã ra đời từ lâu. Nhưng trước những nhu cầu về giao dịch an toàn trên mạng Internet ngày nay, những ứng dụng của nó ngày càng tỏ rõ tầm quan trọng. Một trong những thuật toán mã hóa công khai phổ biến đó là RSA. Thuật toán được ứng dụng rộng rãi cho công nghệ VPN. Cuốn tài liệu này được viết ra với mong muốn giúp các bạn hiểu được một cách tổng quát cách hoạt động của RSA. Tài liệu được chia làm 2 phần bao gồm 2 chương, trong đó phần I (chương I) trình bày về tổng quan về thuật toán RSA; phần II tập truy trình bày về những thực tế khi triển khai RSA. MỤC LỤC LỜI NÓI ĐẦU ii MỤC LỤC iii DANH MỤC HÌNH VẼ iv CHƯƠNG 1: RSA HOẠT ĐỘNG NHƯ THẾ NÀO 5 1.1 Giới thiệu về RSA 5 1.2 Thuật toán RSA 5 1.3 Tạo chữ ký số 10 1.4 Chuyển đổi văn bản rõ 13 CHƯƠNG 2: TRIỂN KHAI THỰC TẾ 15 2.1 Quá trình tạo khóa 15 2.2 Tốc độ 16 2.3 Phân phối khóa 16 2.4 Bảo mật 17 2.5 Tấn công 22 KẾT LUẬN 23 TÀI LIỆU THAM KHẢO 24 DANH MỤC HÌNH VẼ Hình 1.1 Mã hóa và giải mã 5 Hình 1.2 Trao đổi khóa bất đối xứng 7 Hình 2.1 Cố gắng phá hoại cặp khóa bất đối xứng 14 RSA HOẠT ĐỘNG NHƯ THẾ NÀO Giới thiệu về RSA Trong mật mã học, RSA là một thuật toán mật mã hóa khóa công khai. Đây là thuật toán đầu tiên phù hợp với việc tạo ra chữ ký điện tử đồng thời với việc mã hóa. Nó đánh dấu một sự tiến bộ vượt bậc của lĩnh vực mật mã học trong việc sử dụng khóa công cộng. RSA đang được sử dụng phổ biến trong thương mại điện tử và được cho là đảm bảo an toàn với điều kiện độ dài khóa đủ lớn. Thuật toán được Ron Rivest, Adi Shamir và Len Adleman mô tả lần đầu tiên vào năm 1977 tại Học viện Công nghệ Massachusetts (MIT). Tên của thuật toán lấy từ 3 chữ cái đầu của tên 3 tác giả. Trước đó, vào năm 1973, Clifford Cocks, một nhà toán học người Anh làm việc tại GCHQ, đã mô tả một thuật toán tương tự. Với khả năng tính toán tại thời điểm đó thì thuật toán này không khả thi và chưa bao giờ được thực nghiệm. Tuy nhiên, phát minh này chỉ được công bố vào năm 1997 vì được xếp vào loại tuyệt mật. Thuật toán RSA được MIT đăng ký bằng sáng chế tại Hoa Kỳ vào năm 1983 (Số đăng ký 4,405,829). Bằng sáng chế này hết hạn vào ngày 21 tháng 9 năm 2000. Tuy nhiên, do thuật toán đã được công bố trước khi có đăng ký bảo hộ nên sự bảo hộ hầu như không có giá trị bên ngoài Hoa Kỳ. Ngoài ra, nếu như công trình của Clifford Cocks đã được công bố trước đó thì bằng sáng chế RSA đã không thể được đăng ký. Thuật toán RSA Thuật toán Giả sử A và B cần trao đổi thông tin bí mật thông qua một kênh không an toàn (ví dụ như Internet). Với thuật toán RSA, đầu tiên A cần tạo ra cho mình cặp khóa gồm khóa công khai và khóa bí mật theo các bước sau: Bước 1: Chọn 2 số nguyên tố lớn
và
với
, được lựa chọn ngẫu nhiên và độc lập. Bước 2: Tính:
. Bước 3: Tính: giá trị hàm số Ơle
. Bước 4: Chọn một số tự nhiên e sao cho
và là số nguyên tố cùng nhau với
. Bước 5: Tính: d sao cho
. Một số lưu ý Các số nguyên tố thường được chọn bằng phương pháp thử xác suất. Các bước 4 và 5 có thể được thực hiện bằng giải thuật Euclid mở rộng. Bước 5 có thể viết cách khác: Tìm số tự nhiên
sao cho
cũng là số tự nhiên. Khi đó sử dụng giá trị
. Ở bước 3 ta có thể sử dụng
thay cho
. Khóa công khai bao gồm: n, môđun, và e, số mũ công khai (cũng gọi là số mũ mã hóa). Khóa bí mật bao gồm: n, môđun, xuất hiện cả trong khóa công khai và khóa bí mật, và d, số mũ bí mật (cũng gọi là số mũ giải mã). Một dạng khác của khóa bí mật bao gồm: p and q, hai số nguyên tố chọn ban đầu, d mod (p-1) và d mod (q-1) (thường được gọi là dmp1 và dmq1), (1/q) mod p (thường được gọi là iqmp) Dạng này cho phép thực hiện giải mã và ký nhanh hơn với việc sử dụng định lý số dư Trung Quốc. Ở dạng này, tất cả thành phần của khóa bí mật phải được giữ bí mật. A gửi khóa công khai cho B và giữ bí mật khóa cá nhân của mình. Ở đây, p và q giữ vai trò rất quan trọng. Chúng là các phân tố của n và cho phép tính d khi biết e. Nếu không sử dụng dạng sau của khóa bí mật (dạng CRT) thì p và q sẽ được xóa ngay sau khi thực hiện xong quá trình tạo khóa. Me
Hình 1.1 Mã hóa và giải mã Mã hóa Giả sử B muốn gửi đoạn thông tin M cho A. Đầu tiên B chuyển M thành một số m < n theo một hàm có thể đảo ngược (từ m có thể xác định lại M) được thỏa thuận trước. Lúc này B có m và biết n cũng như e do A gửi, B sẽ tính c là bản mã hóa của m theo công thức:
Hàm trên có thể tính dễ dàng sử dụng phương pháp tính hàm mũ (theo môđun) bằng thuật toán bình phương và nhân. Cuối cùng B gửi c cho A. Giải mã A nhận c từ B và biết khóa bí mật d. A có thể tìm được m từ c theo công thức sau:
Biết m, A tìm lại M theo phương pháp đã thỏa thuận trước. Quá trình giải mã hoạt động vì ta có
. Do ed ≡ 1 (mod p-1) và ed ≡ 1 (mod q-1), (theo định lý Fermat nhỏ) nên:
và
Do p và q là hai số nguyên tố cùng nhau, áp dụng định lý Số dư Trung Quốc, ta có:
. hay:
. Các định lý cơ sở Thuật toán RSA dựa trên các định lý sau: Đinh lý 1 (Định lý nhỏ của Fermat): Với p là một số nguyên tố khác 2 thì chia một số a lũy thừa p cho p sẽ có số dư chính bằng a:
Mở rộng ta có
với
là số nguyên tố cùng nhau với m và nhỏ hơn m Đinh lý 2(Định lý Số dư Trung Quốc): Cho hệ phương trình đồng dư bậc nhất
trong đó m1,m2,...,mk đôi một nguyên tố cùng nhau. Định lý Hệ phương trình đồng dư nói trên có nghiệm duy nhất theo mođun M = m1.m2...mk là
trong đó M1 = M / m1,M2 = M / m2,...,Mk = M / mky1 = (M1) − 1(mod m1), y2 = (M2) − 1(mod m2),..., yk = (Mk) − 1(mod mk) Áp dụng trường hợp đặc biệt: Cho p và q là 2 số nguyên tố cùng nhau. Nếu a= b (mod p) và a = b (mod q) thì a= b (mod pq) Ví dụ Sau đây là một ví dụ với những số cụ thể. Ở đây chúng ta sử dụng những số nhỏ để tiện tính toán còn trong thực tế phải dùng các số có giá trị đủ lớn. Lấy 2 số nguyên tố khác nhau p, q: p = 11 q = 13 Ta tính được số module N là: N= pq = 11 * 13 = 143 Giá trị hàm số Ơ le là:
= (p-1) * (q-1) = 10 * 12 = 120 e là số nguyên tố cùng nhau với
e = 17 Tìm d sao cho ed = 1 (mod
) 17 * d = 1 (mod 120) => d = 113 vì 7 * 113 = 1921 = 16 * 120 + 1 = 1 (mod 120) Khóa công khai là cặp (e, n). Khóa bí mật là d. Hàm mã hóa là: c = encrypt(m) = me mod n = m17 mod 143 với m là văn bản rõ. Hàm giải mã là: m = decrypt(c) = cd mod n = c113 mod 143 với c là văn bản mã. Để mã hóa văn bản có giá trị m = 50 và có cặp khóa công khai (e,n) là (17,143) ta thực hiện phép tính: encrypt(50) = 5017 mod 143 = 85 Để giải mã văn bản có giá trị c=545 và cặp khóa bí mật (d,n) là (113,1435) ta thực hiện phép tính: decrypt(85) = 85113 mod 143 = 50 Cả hai phép tính trên đều có thể được thực hiện hiệu quả nhờ giải thuật bình phương và nhân.
Hình 1.2. Trao đổi khóa bất đối xứng Tạo chữ ký số Giới thiệu chung Ngày nay, có ba hệ mã hóa thông dụng được sử dụng để xây dựng các lược đồ ký điện tử, đó là hệ mã hóa RSA, hệ mã hóa dựa trên bài toán logarit rời rạc và hệ mã hóa dựa trên đường cong elliptic. Các hàm một chiều sử dụng trong các hệ mã này hiện đang được xem là an toàn theo thừa nhận (tức là không có thuật toán nào hữu hiệu để tính hàm ngược của chúng). Tuy nhiên, một vấn đề cơ bản của tính an toàn đối với một lược đồ ký điện tử lại là tính không thể giả mạo được chữ ký và điều này không suy ra được trực tiếp từ tính an toàn của hệ mã mà nó dựa vào. Trong khoảng mười năm gần đây, vấn đề này đang thu hút rất nhiều sự quan tâm của cộng đồng mật mã trên thế giới. Người ta đang cố gắng đưa ra những lược đồ ký sao cho tính không thể giả mạo được của nó có thể được đánh giá thông qua độ an toàn của các hàm một chiều mà nó sử dụng. Trong bài này chúng tôi xem xét một số lược đồ ký sử dụng hàm một chiều của hệ mã RSA (đang được xem là phổ biến nhất hiện nay). Giả sử A muốn gửi cho B một văn bản có chữ ký của mình. Để làm việc này, A tạo ra một giá trị băm (hash value) của văn bản cần ký và tính giá trị mũ d mod n của nó (giống như khi A thực hiện giải mã). Giá trị cuối cùng chính là chữ ký điện tử của văn bản đang xét. Khi B nhận được văn bản cùng với chữ ký điện tử, anh ta tính giá trị mũ e mod n của chữ ký đồng thời với việc tính giá trị băm của văn bản. Nếu 2 giá trị này như nhau thì B biết rằng người tạo ra chữ ký biết khóa bí mật của A và văn bản đã không bị thay đổi sau khi ký. Ký điện tử và những mô hình nguyên thủy Hàm băm mật mã Người ta thường sử dụng sự hỗ trợ của các hàm băm mật mã trong quá trình Encoding của các lược đồ ký. Một hàm băm với đầu vào là văn bản (có độ dài bất kỳ), sinh ra cho ta xâu H có độ dài xác định, được gọi là mã băm của . Hàm băm mật mã h phải thỏa mãn các điều kiện sau: • Là hàm một chiều: Tức là nếu cho ta sẽ dễ dàng tính ra H=h(M) . Nhưng nếu chỉ có mã băm H thì rất khó có thể tìm được văn bản M sao cho H=h(M) (rất khó có nghĩa là hiện nay không có thuật toán hữu hiệu nào làm được). • Không tìm được xung đột: Tức là rất khó để tìm ra hai văn bản M và M’ có cùng mã băm. • Không tìm được xung đột của văn bản cho trước: Tức là cho trước văn bản M thì rất khó để tìm được văn bản M’có cùng mã băm với văn bản Mđó. Trong thực tế rất khó có thể tìm ra được một hàm băm thỏa mãn nghiêm ngặt các tính chất trên. Hiện nay, ngày càng có những kết quả thám mã mạnh tấn công vào tính chất thứ hai. Cho nên, các lược đồ ký gần đây thường cố gắng tránh việc dựa trực tiếp vào tính chất này. Lược đồ ký RSA nguyên thủy Lược đồ ký RSA sử dụng thao tác sinh khóa của chính hệ mã RSA. Một hàm băm mật mã (công khai) sẽ được sử dụng trong quá trình Encoding của thao tác ký. Ở đây ta mô tả lược đồ RSA có văn bản kèm theo. Thao tác ký nhận đầu vào là văn bản và khóa bí mật sẽ sinh ra chữ ký là x. Thao tác xác minh, nhận đầu vào là M1x và Ph , sẽ cho ra kết quả là 1 nếu như x đúng là chữ ký trên văn bản M của người có bộ khóa (sh,ph), ngược lại sẽ cho kết quả 0. Thao tác ký RSA-Sign(M) bao gồm các bước như sau: (1) Tính H=h(M): (2) Tính y=0x0001FFFF…FF00\\H; 3) Tính x=f-1(y)=ydmodN, x chính là chữ ký trên văn bản M Ở bước (2) của thao tác ký ta thấy có một số các xâu 0xFF được nối vào mã băm H của M. Mục đích của việc này để tạo ra xâu y có độ dài k bit (là độ dài của N trong chìa khóa). Xâu 0x0001 đầu tiên có ý nghĩa là để cho y luôn nhỏ hơn N . Xâu 00 ngăn cách giữa phần mã băm và phần nối thêm có mục đích giúp ta có thể dễ dàng lấy ra được mã băm H từ xâu y. Ở bước (3) ta giả sử xâu y đã chuyển sang thành số y tương ứng. Thao tác xác min RSA-Verify(M,) Bao gồm các công đoạn sau: (1) Tính H1=h(M); (2) Tính y=f(x)=xe mod N v à lấy ra xâu H từ y là kh bit cuối cùng, với kh là độ dài của mã băm ứng với hàm băm công khai h. (3) Nếu H1=H thì cho ra 1, ngược lại cho ra 0. Theo lược đồ trên, ta thấy mã băm H chỉ là một phần nhỏ của y. Và việc tìm ra xung đột của hàm h sẽ gây ảnh hưởng trực tiếp đến độ an toàn của lược đồ. Cụ thể là, nếu như tìm được hai văn bản M và M’ có cùng mã băm thì chữ ký trên văn bản M cũng chính là chữ ký trên văn bản M'. Hiện nay, đã có những thuật toán tìm ra được một số điểm xung đột của những hàm băm khá phổ biến trước đây (như MD5, SHA-1,...), khiến cho các lược đồ ký nguyên thủy bị “lung lay”. Tuy nhiên, cũng cần ghi nhận rằng các thuật toán tìm xung đột nêu trên chưa cho phép tìm được một văn bản khác với văn bản M cho trước mà có cùng mã băm với M . Như vậy, cho đến nay, việc “mạo chữ ký” của một văn bản cho trước là vẫn chưa thể thực hiện được. Lược đồ ký theo chuẩn PKCS#1 (V2.1) Mô tả lược đồ Thao tác sinh khóa của PSS2000 cũng giống như của PSS96, có một chút sự khác biệt được ở quá trình Encoding. Ta mô tả quá trình Encoding như sau: PSS2000 – Encode (H) bao gồm các bước sau:
Như vậy thao tác Encoding ở PSS2000 có sự khác biệt so với phiên bản 96 là ở trong bước (2) hàm băm có nối thêm xâu gồm u chữ số 0 vào trước văn bản được băm. Ở thao tác (4), xâu E được nối vào cuối của xâu kết quả. Xâu E cố định có thể là 0xbc =10111100 hoặc HID\\cc, v ới HID là chỉ số của hàm băm h. Còn bước (3) chẳng qua cách diễn đạt khác của hàm g1, g2 trong phiên bản 96.

Lược đồ ký PSS2000-SIGN, cho văn bản M, tính giá trị H=h(M) và tính y=PSS2000-Encode(H), kết quả trả lại là x=f-1(y). Ta có thể nhận thấy có thêm một khác biệt giữa PSS2000 và PSS96, đó là ở PSS2000 có thêm thao tác băm văn bản trước khi đưa vào thao tác encoding. b. Lược đồ ký thu gọn Nhận xét. Lược đồ ký RSA-GenPSS-Reduced như trên chẳng qua là lược đồ ký thông thường như PSS96, chỉ có một vài điểm khác nhau nhỏ như sau: • Thứ nhất: lược đồ trên, độ dài các văn bản đầu vào chỉ cho phép là ; hk • Thứ hai: Một chuỗi gồm u chữ số 0 được nối vào H||r trước khi cho vào băm (bước (2) quá trình GenPSS-Encode) ; • Thứ ba, đó là sự khác nhau giữa hai quá trình Encoding đã nhận xét ở trên, ở sự tham gia của E trong ảnh của quá trình Encoding. Yêu cầu thứ nhất là hiển nhiên do lược đồ thu gọn làm việc trên giá trị băm của hàm băm . Yêu cầu thứ hai được đưa vào nhằm mục đích tạo ra sự tương thích cho lược đồ ký có khôi phục văn bản và cũng góp phần làm giảm xung đột. Bởi lẽ sẽ khó hơn nếu khi tìm kiếm hai văn bản xung đột với nhau khi ta yêu cầu cả hai văn bản đó đều phải có u bit đầu tiên là 0. Sự thay đổi thứ ba có thể góp phần làm tăng thêm độ an toàn cho lược đồ ký. Thật vậy, bài toán tìm đầu vào cho hàm RSA, ta thường gọi là hàm , sao cho đầu ra thỏa mãn điều kiện ràng buộc có bit đầu tiên là 0 và bít sau cùng là cố định, là một bài toán khó hơn so với khi không có ràng buộc này. Như vậy ta có thể thấy RSA-GenPSS-Reduced là lược đồ ký có độ an toàn tương đương (nếu không muốn nói là tốt hơn) PSS96 với độ dài văn bản đầu vào cố định. Chuyển đổi văn bản rõ Trước khi thực hiện mã hóa, ta phải thực hiện việc chuyển đổi văn bản rõ (chuyển đổi từ M sang m) sao cho không có giá trị nào của M tạo ra văn bản mã không an toàn. Nếu không có quá trình này, RSA sẽ gặp phải một số vấn đề sau: Nếu m = 0 hoặc m = 1 sẽ tạo ra các bản mã có giá trị là 0 và 1 tương ứng Khi mã hóa với số mũ nhỏ (chẳng hạn e = 3) và m cũng có giá trị nhỏ, giá trị me cũng nhận giá trị nhỏ (so với n). Như vậy phép môđun không có tác dụng và có thể dễ dàng tìm được m bằng cách khai căn bậc e của c (bỏ qua môđun). RSA là phương pháp mã hoá xác định (không có thành phần ngẫu nhiên) nên kẻ tấn công có thể thực hiện tấn công lữa chọn bản rõ bằng cách tạo ra một bảng tra giữa bản rõ và bản mã. Khi gặp một bản mã, kẻ tấn công sử dụng bảng tra để tìm ra bản rõ tương ứng. Trên thực tế, ta thường gặp 2 vấn đề đầu khi gửi các bản tin ASCII ngắn với m là nhóm vài ký tự ASCII. Một đoạn tin chỉ có 1 ký tự NUL sẽ được gán giá trị m = 0 và cho ra bản mã là 0 bất kể giá trị của e và N. Tương tự, một ký tự ASCII khác, SOH, có giá trị 1 sẽ luôn cho ra bản mã là 1. Với các hệ thống dùng giá trị e nhỏ thì tất cả ký tự ASCII đều cho kết quả mã hóa không an toàn vì giá trị lớn nhất của m chỉ là 255 và 2553 nhỏ hơn giá trị n chấp nhận được. Những bản mã này sẽ dễ dàng bị phá mã. Để tránh gặp phải những vấn đề trên, RSA trên thực tế thường bao gồm một hình thức chuyển đổi ngẫu nhiên hóa m trước khi mã hóa. Quá trình chuyển đổi này phải đảm bảo rằng m không rơi vào các giá trị không an toàn. Sau khi chuyển đổi, mỗi bản rõ khi mã hóa sẽ cho ra một trong số khả năng trong tập hợp bản mã. Điều này làm giảm tính khả thi của phương pháp tấn công lựa chọn bản rõ (một bản rõ sẽ có thể tương ứng với nhiều bản mã tuỳ thuộc vào cách chuyển đổi). Một số tiêu chuẩn, chẳng hạn như PKCS, đã được thiết kế để chuyển đổi bản rõ trước khi mã hóa bằng RSA. Các phương pháp chuyển đổi này bổ sung thêm bít vào M. Các phương pháp chuyển đổi cần được thiết kế cẩn thận để tránh những dạng tấn công phức tạp tận dụng khả năng biết trước được cấu trúc của bản rõ. Phiên bản ban đầu của PKCS dùng một phương pháp đặc ứng (ad-hoc) mà về sau được biết là không an toàn trước tấn công lựa chọn bản rõ thích ứng (adaptive chosen ciphertext attack). Các phương pháp chuyển đổi hiện đại sử dụng các kỹ thuật như chuyển đổi mã hóa bất đối xứng tối ưu (Optimal Asymmetric Encryption Padding - OAEP) để chống lại tấn công dạng này. Tiêu chuẩn PKCS còn được bổ sung các tính năng khác để đảm bảo an toàn cho chữ ký RSA (Probabilistic Signature Scheme for RSA – RSA - PSS). TRIỂN KHAI THỰC TẾ Quá trình tạo khóa Việc tìm ra 2 số nguyên tố đủ lớn p và q thường được thực hiện bằng cách thử xác suất các số ngẫu nhiên có độ lớn phù hợp (dùng phép kiểm tra số nguyên tố cho phép loại bỏ hầu hết các hợp số). Phép kiểm tra số nguyên tố được thực hiện như sau: Các phương pháp thô sơ: Phương pháp đơn giản nhất để kiểm tra một số n có là số nguyên tố không là kiểm tra xem nó có chia hết cho các số m từ 2 đến n − 1 hay không. Nếu n chia hết cho một số m nào đó thì n là hợp số (composite), ngược lại n là số nguyên tố. Kiểm tra theo xác suất: Các phép kiểm tra tính nguyên tố hay dùng nhất là các thuật toán ngẫu nhiên. Giả sử có một mệnh đề Q(p,a) nào đó đúng với mọi số nguyên tố p và một số tự nhiên a <= p. Nếu n là một số tự nhiên lẻ và mệnh đề Q(n,a) đúng với một a<= n được lấy ngẫu nhiên, khi đó a có khả năng là một số nguyên tố. Ta đưa ra một thuật toán, kết luận rằng n là số nguyên tố. Nó là một thuật toán ngẫu nhiên hay thuật toán xác suất. Trong các thuật toán loại này, dùng một kiểm tra ngẫu nhiên không bao giờ kết luận một số nguyên tố là hợp số nhưng có thể kết luận một hợp số là số nguyên tố. Xác suất sai của phép kiểm tra có thể giảm xuống nhờ việc chọn một dãy độc lập các số a; nếu với mỗi số a xác suất để thuật toán kết luận một hợp số là số nguyên tố là nhỏ hơn một nửa thì sau k lần thử độc lập, xác suất sai là nhỏ hơn 2−k, độ tin cậy của thuật toán sẽ tăng lên theo k. Cấu trúc cơ bản của một phép kiểm tra ngẫu nhiên là: Chọn một số ngẫu nhiên a. Kiểm tra một hệ thức nào đó giữa số a và số n đã cho. Nếu hệ thức sai thì chắc chắn n là một hợp số (số a là "bằng chứng" chứng tỏ n là hợp số) và dừng thuật toán. Lặp lại bước 1 cho đến khi đạt được số lần đã định hoặc gặp bước 2. Sau một loạt lần kiểm tra, nếu không tìm được bằng chứng chứng tỏ n là hợp số thì ta kết luận n là số nguyên tố. Các phép kiểm tra tất định Vào năm 2002, Manindra Agrawal, Nitin Saxena và Neeraj Kayal đề xuất một giải thuật tất định kiểm tra tính nguyên tố, là kiểm tra AKS, có khả năng chạy trong O((log n)12). Trên thực tế thuật toán này chạy chậm hơn các phương pháp xác suất. Các phương pháp lý thuyết số Có một vài phương pháp khác trong lý thuyết số để kiểm tra tính nguyên tố như kiểm tra Lucas-Lehmer và kiểm tra Proth. Chúng thường dựa vào việc phân tích n + 1, n − 1, hoặc những số khác. Tuy nhiên các phương pháp này không dừng cho các số tự nhiên n bất kỳ mã chỉ cho các số có một dạng đặc biệt nào đó Kiểm tra Lucas-Lehmer dựa trên tính chất: bậc (multiplicative order) cúa một số a modulo n là n − 1 với n là số nguyên tố và a là căn nguyên thuỷ (primitive root) modulo n. Nếu ta có thể biểu diễn a chỉ theo n, ta có thể thấy n là nguyên tố. p và q còn cần được chọn không quá gần nhau để phòng trường hợp phân tích n bằng phương pháp phân tích Fermat. Ngoài ra, nếu p-1 hoặc q-1 có thừa số nguyên tố nhỏ thì n cũng có thể dễ dàng bị phân tích và vì thế p và q cũng cần được thử để tránh khả năng này. Bên cạnh đó, cần tránh sử dụng các phương pháp tìm số ngẫu nhiên mà kẻ tấn công có thể lợi dụng để biết thêm thông tin về việc lựa chọn (cần dùng các bộ tạo số ngẫu nhiên tốt). Yêu cầu ở đây là các số được lựa chọn cần đồng thời ngẫu nhiên và không dự đoán được. Đây là các yêu cầu khác nhau: một số có thể được lựa chọn ngẫu nhiên (không có kiểu mẫu trong kết quả) nhưng nếu c