Sinh số nguyên tố lớn dùng trong mật mã

Kỷ yếu công trình khoa học 2015 – Phần I 
SINH SỐ NGUYÊN TỐ LỚN DÙNG TRONG MẬT MÃ 
Nguyễn Đức Thắng, Trần Vĩnh Đức 
Khoa Toán-Tin, Trường Đại học Thăng Long 
Email: thangdn.tlu@outlook.com 
Email: tranvinhduc@gmail.com 
Tóm tắt:Bài báo này mô tả phương pháp sinh ngẫu nhiên các số nguyên tố mạnhđể sử 
dụng trong cáchệ mật mã công khai và chữ ký số dựa trên RSA. Cụ thể, thuật toán Rabin-
Miller và thuật toán Gordon sẽ được trình bày một cách chi tiết. 
Từ khóa:RSA, chữ ký số, mật mã. 
1. Giới thiệu chung 
Bài báo này mô tả phương pháp sinh số nguyên tố lớn dùng trong hệ thống chữ ký số 
của Trường Đại Học Thăng Long. Do yêu cầu của hệ thống, việc sinh số phải đảm bảo: 
1. Số được sinh phải có độ dài 3072 bit, 
2. Số được sinh phải ngẫu nhiên (khó dự đoán), và 
3. Thời gian sinh mỗi số phải đủ nhanh, thời gian trung bình chỉ vài giây trên máy tính 
cấu hình không mạnh. 
Định nghĩa 1. Số nguyên dương p > 1 là nguyên tố nếu p không chia hết cho số 
nguyên dương nào ngoài 1 và p. Ngược lại p là hợp số. 
Ta định nghĩa hàm phân phối của các số nguyên tố là số lượng số nguyên tố nhỏ 
hơn hoặc bằng n. 
Ví dụ: = 4 vì có đúng bốn số nguyên tố nhỏ hơn 10 là 2, 3, 5, 7. 
Định lý sau đây cho ta ước lượng xấp xỉ hàm . 
Định lý 1. 
Nói cách khác, giá trị xấp xỉ bằng với khi n lớn. 
Ví dụ:Với ta có 
 và 
Sai số ở đây là 6%. 
Vậy nếu ta lấy ngẫu nhiên một số nguyên dươngk bit, xác suất để số này là số nguyên 
tố bằng . Về trung bình, ta cần lần thử để lấy được một số nguyên tố k bit. 
Ví dụ:Nếu thì,về trung bình, lấy ngẫu nhiên số, ta sẽ có 
được một số nguyên tố k bit. 
Trường Đại học Thăng Long 106 
Kỷ yếu công trình khoa học 2015 – Phần I 
Từ phân tích ở trên, về trung bình, thuật toán ngẫu nhiên dưới đây sẽ dừng sau 2130 
bước lặp. 
Thuật toán sinh số nguyên tố: 
1. Chọn ngẫu nhiên một số nhị phân độ dài bit. 
2. Đặt cả hai bit cao nhất và bit thấp nhất của lên . 
3. Kiểm tra xem có là số nguyên tố. 
4. Nếu có thì trả ra số nguyên tố . Còn nếu không thì quay lại Bước 1. 
Trong Bước 2 của thuật toán, 
• Ta đặt bit thấp nhất của lên đảm bảo rằng là số lẻ; 
• Và ta đặt bit cao nhất của lên để đảm bảo rằng số sinh ra thỏa mãn 
điều này là cần thiếtvì để đảm bảo an toàn cho thuật toán RSA thì các số nguyên tố 
sinhra phải đủ lớn. 
Các bước 1 và bước 3 sẽ được phân tích ở mục 2 và mục 3. 
2. Sinh số ngẫu nhiên 
Hệ thống chữ ký điện tử dự kiến sẽ được cài đặt trên GNU/Linux. Chúng tôi dự định 
dùng hàm sinh dãy bit ngẫu nhiên của hệ điều hành này. 
Hệ điều hành GNU/Linux sinh các dãy bit ngẫu nhiên từ các nguồn ngẫu nhiên của hệ 
thống (các thao tác chuột, các thao tác bàn phím, các chương trình chạy). Các dãy bit này 
được lưu trữ trong tệp tin/dev/urandom. Trong trường hợp các dãy bit sinh ra chưa đủ ngẫu 
nhiên do entropy nhỏ, hệ thống sẽ sử dụng một hàm giả ngẫu nhiên an toàn. Phương pháp lấy 
dữ liệu ngẫu nhiên này được nhiều người sử dụng và theo chúng tôi biết, cho đến nay vẫn 
chưa có báo cáo nào về tính không an toàn của nó. 
3. Thuật toán kiểm tra số nguyên tố 
Thuật toán đơn định AKS cho phép kiểm tra xem liệu một số nguyên dương có là 
nguyên tố trong thời gian . Tuy nhiên, nó không được sử dụng nhiều trong mật 
mã vì thời gian chạy chậm. 
Chúng tôi cài đặt thuật toán ngẫu nhiên Rabin-Miller kết hợp với một số bước tiền xử 
lý để tăng tốc thuật toán. 
Thuật toán của Rabin-Miller là thuật toán kiểu Monte Carlo. Nó cho phép kiểm tra 
một số nguyên có là nguyên tố hay không với một xác suất sai có thể làm nhỏ tuỳ ý. Chúng 
tôi chọn xác suất sai số bằng . Cụ thể, nếu thuật toán thông báo là hợp số, vậy chắc 
chắn là hợp số. Còn nếu thuật toán thông báo là nguyên tố thì xác suất là hợp số chỉ 
là . 
Trường Đại học Thăng Long 107 
Kỷ yếu công trình khoa học 2015 – Phần I 
Phần còn lại trong mục này mô tả từng bước xây dựng và cải tiến thuật toán. 
Trước hết định lý sau đây cho một thuật toán đơn giản để kiểm tra một số là nguyên 
tố. 
Định lý 2 (Fermat). Nếu là số nguyên tố thì, với mọi , 
Thuật toán như sau: 
Tất nhiên, thuật toán trên có thể cho kết quả sai, nhưng chỉ có một kiểu sai: Nếu nó trả 
lại thì vẫn có khả năng là hợp số, nhưng nếu nó trả lại thì chắc chắn là hợp số. 
Ví dụ:Với cả bốn số và , thuật toán cho kết 
quả là , dù các số này đều là hợp số. 
Câu hỏi tự nhiên là: Số trường hợp mà thuật toán này cho kết quả sai có nhiều không? 
Thật ngạc nhiên là số trường hợp sai rất hiếm. Trong số nguyên dương đầu tiên, thuật 
toán chỉ nhầm số. 
Thuật toán sau đây là một cải tiến của thuật toán trước dựa trên hai ý tưởng. 
• Thay cơ sở trong thuật toán bằng một số bất kỳ; 
• Kết hợp với Định lý 3 sau đây để hạn chế số trường hợp sai. 
Định lý 3. Nếu là số nguyên tố lẻ và thì phương trình 
chỉ có hai nghiệm và . 
Trường Đại học Thăng Long 108 
Kỷ yếu công trình khoa học 2015 – Phần I 
Thuật toán trên thực hiện tính bằng cách lặp lại việc tính 
bắt đầu từ . Nếu thì là số nguyên tố.Vòng lặp có thể kết thúc sớm nếu 
vì khi đó ta kết luận là hợp số theo theo Định lý 3. 
Thuật toán dưới đây lặp lại lần tính để giảm xác suất 
sai. 
Xác suất sai của thuật toán được chỉ ra bởi định lý sau. 
Định lý 4.Với mỗi số nguyên lẻ và số nguyên dương , sai số của thuật toán 
 nhiều nhất là . 
Thuật toán sau đây thêm một vài bước tiền xử lý để giảm thời gian chạy của thuật 
toán . 
Bước 1 và 2 nhằm loại rất nhanh các số chia hết cho 400 số nguyên tố đầu tiên. Bước 
3loại nhanh một số lượng lớn các hợp số nhờ Định lý Fermat. Chúng tôi chọn cơ sở để việc 
tính toán nhanh trên bit. Cuối cùng ta kiểm tra những số còn lại bằng thuật 
toán . Bước 4 cần nhiều tính toán. 
Trường Đại học Thăng Long 109 
Kỷ yếu công trình khoa học 2015 – Phần I 
Nếu thuật toán này thông báo “ là hợp số”, vậy chắc chắn là hợp số. Còn nếu nó 
thông báo “ là số nguyên tố”, vậy xác suất là hợp số chỉ là . 
4. Thuật toán sinh số nguyên tố mạnh 
Thuật toán p−1 của Pollard là một trong những thuật toán hiệu quả để phân tích thừa 
số nguyên tố n = pq, khi p và q thỏa mãn một số tính chất đặc biệt.Để tránh phương pháp tấn 
công này, các số p và q nên là các số nguyên tố mạnh. Đây là lý do mà chuẩn ANSI X9.31yêu 
cầu sử dụng số nguyên tố mạnh để sinh khóa cho các hệ chữ ký điện tử dựa trên RSA. 
Định nghĩa 2. Số nguyên tố p được gọi là số nguyên tố mạnh nếu nó thỏa mãn ba điều 
kiện sau: 
1. p−1 có thừa số nguyên tố u đủ lớn; 
2. p+1 có thừa số nguyên tố s đủ lớn; và 
3. u−1 có thừa số nguyên tố t đủ lớn. 
Năm 1984 John Gordon đã đề xuất một thuật toán hiệu quả để sinh số nguyên tố 
mạnh. Thuật toán Gordon chỉ mất thêm 19% thời gian tính toán so với thời gian tìm một số 
nguyên tố cùng kích thước bằng thuật toán Rabin-Miller. 
Trong bước 1, 2, 4, ta sử dụng thuật toán Rabin-Miller để kiểm tra số nguyên tố. 
5. Thử nghiệm 
Chúng tôi đã cài đặt và chạy thử nghiệm các thuật toán mô tả trong các mục trước để 
sinh 100 số nguyên tố ngẫu nhiên độ dài 3072 bit. Chương trình chạy trên máy laptop với bộ 
xử lý Intel Core i7 Haswell (4500U, 1.80 GHz), Ram 4 GB, 1600 MHz, và chạy hệ điều hành 
GNU/Ubuntu 15.04. Thời gian trung bình để sinh ra mỗi số nguyên tố khoảng 2.09 giây và 
khoảng 2.75 giây đối với mỗi số nguyên tố mạnh. 
Trường Đại học Thăng Long 110 
Kỷ yếu công trình khoa học 2015 – Phần I 
Hình 1: Mô tả các histogram thời gian chạy cho việc sinh ngẫu nhiên 100 số nguyên 
tố cỡ 3072 bit. Cột của bảng mô tả số lượng số nguyên tố chạy trong thời gian (tính 
theo giây) chỉ ra bởi hàng. 
6. Tài liệu tham khảo 
[1]. Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, Charles E. Leiserson, 
Introduction to Algorithms, McGraw-Hill Higher Education, 2001. 
[2]. H. H. Khoái, P. H. Điển, Số học thuật toán: Cơ sở lý thuyết và tính toán thực 
 hành, NXB Đại học Quốc Gia Hà Nội, 2003. 
[3]. Jonathan Katz và Yehuda Lindell, Introduction to Modern Cryptography, 
 Chapman & Hall/CRC, 2007. 
[4]. Ronald L. Rivest, Robert D. Silverman y, Are ‘Strong’ Primes Needed for RSA?, 
November 22, 1999. 
[5]. Victor Shoup, A computational introduction to number theory and algebra, 
Cambridge University Press, 2006. 
Abstract: This paper describes the classical method to generate random strong 
primes used in cryptography. Specifically, the Rabin-Miller and Gordon algorithmsare 
presented in detail. 
Trường Đại học Thăng Long 111