Số nguyên tố an toàn trong các giao thức DH - KE

Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 Số 1.CS (11) 2020 23 
Số nguyên tố an toàn 
trong các giao thức DH-KE 
Nguyễn Thanh Sơn
Tóm tắt—Việc sinh các số nguyên tố “an toàn” 
𝒑, mà ở đó tất cả các ước nguyên tố khác 𝟐 của 𝒑 −
𝟏 đều là ước nguyên tố lớn, là hết sức cần thiết để 
tránh các tấn công nhóm con nhỏ được chỉ ra bởi 
hai tác giả Chao Hoom Lim và Pil Joong Lee. Một 
thuật toán hiện có để sinh các số nguyên tố như vậy 
cũng đã được trình bày bởi hai tác giả này. Tuy 
nhiên, hạn chế của phương pháp đó là thuật toán 
không phải khi nào cũng trả về được một số 
nguyên tố an toàn. Một phần lý do cho vấn đề này 
là vì thuật toán không (và khó có thể) được phân 
tích và đánh giá kỹ lưỡng về mặt toán học. Do đó, 
mục đích chính của bài báo là đề xuất một thuật 
toán mới để sinh các số nguyên tố an toàn và kèm 
theo các đánh giá chi tiết về mặt toán học. 
Abstract—The generate of “safe” primes 𝒑, 
where all prime divisors of 𝒑 − 𝟏 are large prime 
divisors, is essential to avoid small subgroup 
attacks which are point out by two authors Chao 
Hoom Lim and Pil Joong Lee. An existing 
algorithm for generating such primes has also 
been presented by these two authors. However, the 
drawback of that method is that the algorithm 
does not always return safe prime numbers. Part 
of the reason for this is that the algorithm is not 
(and hardly) be thoroughly analyzed and 
evaluated mathematically. Therefore, the main 
purpose of this paper is to propose a new 
algorithm for generating safe prime numbers, 
including detailed mathematical evaluations. 
Từ khóa—Thuật toán sinh số nguyên tố an toàn; giao 
thức DH-KE. 
Keywords—Safe prime generation algorithm; DH-KE protocol. 
I. ĐẶT VẤN ĐỀ 
Đối với các ứng dụng mật mã như hệ mật khóa 
công khai và lược đồ chữ ký số có độ an toàn dựa 
trên độ khó của bài toán logarit trên 𝐺𝐹(𝑝) thì bộ 
tham số (𝑝, 𝑞, 𝑔) (với 𝑝 là số nguyên tố, 𝑞 là ước 
nguyên tố của 𝑝 – 1 và 𝑜𝑟𝑑(𝑔) = 𝑞) được lựa 
chọn để sử dụng chỉ cần chống được các tấn công 
Bài báo được nhận ngày 12/7/2020. Bài báo được nhận xét bởi 
phản biện thứ nhất ngày 27/7/2020 và được chấp nhận đăng 
ngày 27/7/2020. Bài báo được nhận xét bởi phản biện thứ hai 
ngày 03/8/2020 và được chấp nhận đăng ngày 03/8/2020. 
theo các phương pháp giải bài toán logarit như 
Pollard Lambda, Pollard Rho [3], Pollig 
Hellman [1], Cụ thể, các tham số 𝑝, 𝑞 được 
khuyến cáo để sử dụng trong các chuẩn mật mã 
đều phải là các số nguyên tố lớn. Chẳng hạn, 
trong chuẩn FIPS PUB 186-3 [4] quy định 𝑝 có 
kích thước tối thiểu là 1024-bit và độ dài bit của 
𝑞 tương ứng là 160-bit. 
Khi ứng dụng trong thực tế các lược đồ chữ 
ký số trong các giao thức thỏa thuận khóa kiểu 
Diffie-Hellman (DH-KE) đã nảy sinh một kiểu 
tấn công của chính người tham gia hệ thống 
nhằm tìm khóa mật của người còn lại. Loại tấn 
công này được Chao Hoom Lim và Pil Joong Lee 
(Lim-Lee) công bố năm 1997 [2] và được các tác 
giả của [11] nghiên cứu, xem xét để đề xuất tiêu 
chuẩn cho tham số modulo 𝑝. Cũng để chống lại 
tấn công trên, năm 2006, Tổ chức Tiêu chuẩn hóa 
quốc tế (ISO) đã ban hành chuẩn ISO/IEC 
11770-4:2006 (xem ISO/IEC 11770-4:2006, 
Clause 5) được phát biểu như sau: 
Tiêu chuẩn. (Tiêu chuẩn về sự phân rã 𝑝 – 1) 
Số nguyên tố p dùng trong các giao thức 
thỏa thuận khóa DH-KE với phần tử sinh g ∈ 
GF(p) có cấp bằng 𝑞, phải thỏa mãn các điều 
kiện sau: 
a) 𝑝 = 2𝑞𝑞1𝑞2  𝑞𝑘 + 1 với 𝑞𝑖 là các số nguyên 
tố (không nhất thiết khác nhau). 
b) 𝑞𝑖 > 𝑞 (1 𝑖 𝑘). 
(1) 
Trong Phần II, tác giả chỉ ra rằng: Để chống 
được tấn công của Lim-Lee thì điều kiện (b) chỉ 
cần là: 
𝑞𝑖 ≥ 𝑞 (1 ≤ 𝑖 ≤ 𝑘). (2) 
Trên cơ sở đó đưa ra định nghĩa về bộ tham số 
(𝑝, 𝑞, 𝑔) an toàn cho DH-KE như sau. 
Định nghĩa 1. Bộ tham số (𝑝, 𝑞, 𝑔) ngoài việc 
thỏa mãn việc giải bài toán logarit rời rạc theo 
cơ số g là khó còn thỏa mãn thêm các điều kiện 
Journal of Science and Technology on Information security 
24 No 1.CS (11) 2020 
(1) và (2) được gọi là bộ tham số an toàn cho 
giao thức DH-KE trên 𝐺𝐹(𝑝). 
Cũng trong công trình của mình [2], Lim-Lee 
đã đưa ra một thuật toán mang tính thực nghiệm 
để sinh các số nguyên tố an toàn như vậy. Thuật 
toán này sau đó cũng đã được sử dụng để sinh 
các số nguyên tố an toàn trong các thư viện mật 
mã như Miracl [9], PGP [6], GNU PG [8] và 
Gutmann’s cryptlib [7]. Tuy nhiên như đã đề cập, 
thuật toán được đề xuất bởi Lim-Lee mới chỉ 
mang ý nghĩa về thực nghiệm. Điều này là do 
thuật toán của hai tác giả trên không phải khi nào 
cũng trả về kết quả và cũng không được phân tích 
chi tiết về mặt toán học. Do vậy, mục tiêu của bài 
báo này là đề xuất một thuật toán sinh số nguyên 
tố “an toàn” mới và kèm theo đảm bảo toán học 
cho nó. Cụ thể, thuật toán được đề xuất sẽ được 
trình bày trong Phần III và các phân tích về tính 
đúng đắn, độ phức tạp của thuật toán này sẽ được 
đánh giá trong Phần IV. 
II. SỐ NGUYÊN TỐ AN TOÀN TRONG CÁC GIAO 
THỨC DH-KE 
A. Độ phức tạp của tấn công tìm khóa mật trong 
giao thức DH-KE của Lim-Lee 
Để hiểu rõ hơn về việc cần sử dụng bộ tham 
số an toàn trong các giao thức DH-KE, trong mục 
này sẽ trình bày lại tấn công của hai tác giả trên, 
đưa ra những phân tích để lý giải cho chuẩn này. 
Trong bài viết của mình, Lim-Lee đã thực 
hiện việc tấn công1 lên họ giao thức trao đổi khóa 
MTI [5] với kết quả thu được là: 
Bổ đề 1. (Độ phức tạp của tấn công tìm 
xB mod u) 
Với u là ước bất kỳ của p – 1 thì chỉ sau 
𝑥𝐵 𝑚𝑜𝑑 𝑢 (hoặc 𝑘𝐵 𝑚𝑜𝑑 𝑢) bước tính toán thì A 
sẽ tìm được 𝑥𝐵 𝑚𝑜𝑑 𝑢 (hoặc 𝑘𝐵 𝑚𝑜𝑑 𝑢) với 𝑥𝐵 
là khóa ký của B (hoặc 𝑘𝐵 là khóa ngắn hạn theo 
phiên do B thực hiện trong giao thức). 
Nói một cách khác, độ phức tạp của tấn công 
Lim-Lee bằng O(u). 
1 Hơn thế nữa, tấn công của Lim-Lee có thể áp dụng lên 
giao thức trao đổi khóa HMQV, giao thức trao đổi khóa 
KEA+ trong trường hợp số nguyên tố 𝑝 ... chlet. 
Cho A và B là hai số tự nhiên thỏa mãn 
𝑔𝑐𝑑(𝐴, 𝐵) = 1. Ký hiệu 𝐴,𝐵(𝑥) là số các số 
nguyên tố 𝑝 = 𝑡. 𝐴 + 𝐵 𝑥 (𝑡 = 0, 1, 2,  ). 
Ta có: 𝐴,𝐵(𝑥)~
1
𝜑(𝐴)
 (𝑥). 
Như vậy, với 𝑥 đủ lớn có thể viết: 
 𝐴,𝐵(𝑥) ≈
1
𝜑(𝐴)
 (𝑥). 
Từ Bổ đề 4, thu được một số hệ quả sau. 
Hệ quả 5. Các tập sử dụng trong bước 5.1 là 
khác rỗng, tức là 
[𝑁, 𝐿 − 𝑀𝑖−1 − (𝑘 − 𝑖) ∗ 𝑁 − 1] ≠ ∅. 
Chứng minh 
Theo (5) thì 𝐿 − 𝑀𝑖−1 − 1 ≥ (𝑘 − 𝑖 + 1)𝑁 
 𝐿 − 𝑀𝑖−1 − (𝑘 − 𝑖)𝑁 ≥ 𝑁 
Suy ra, có tập 
[𝑁, 𝐿 − 𝑀𝑖−1 − (𝑘 − 𝑖) ∗ 𝑁 − 1] ≠ ∅.■ 
Hệ quả 6. Mọi số nguyên tố 𝑞𝑘 đều thỏa mãn 
𝑞𝑘 𝑞. 
Chứng minh 
Do 𝑞𝑘 ∈ 𝑃𝑟𝑖𝑚𝑒[𝐴, 𝐵] nên chỉ cần chứng 
minh được 𝐴 𝑞 thì hệ quả là hiển nhiên. 
Do 𝑓𝑘−1 = 𝑓𝑘−2. 𝑞𝑘−1 nên 
𝑀𝑘−1 ≤ 𝑙𝑒𝑛(𝑓𝑘−2) + 𝑙𝑒𝑛(𝑞𝑘−1) = 𝑀𝑘−2 +
𝑁𝑘−1. (11) 
Theo cách xác định 𝑁𝑘−1 thì 
𝑁𝑘−1 ≤ 𝐿 − 𝑀(𝑘−1)−1 − (𝑘 − (𝑘 − 1))𝑁 − 1 
 = 𝐿 − 𝑀𝑘−2 − 𝑁 − 1. 
Hay 𝑀𝑘−2 + 𝑁𝑘−1 ≤ 𝐿 − 𝑁 − 1. (12) 
Từ (11) và (12) thu được 
 𝐴 = ⌈
2𝐿−1
𝑓𝑘−1
⌉ ≥
2𝐿−1
𝑓𝑘−1
≥ 2𝐿−1−𝑀𝑘−1 ≥
2𝐿−1−(𝐿−𝑁−1) = 2𝑁 > 𝑞. 
Đây là điều cần chứng minh.■ 
Hệ quả 7. Với A và B xác định tại bước 7 của 
Thuật toán 3 thì: 
a) B < 2𝐿−𝑁 (13) 
b) 𝐵 − 𝐴 + 1 ≥ 2𝑁 (14) 
Chứng minh 
Từ 𝐵 = ⌊
2𝐿−1
𝑓𝑘−1
⌋ nên 𝐵 này lớn nhất khi 𝑘 = 1, 
khi đó 𝑓𝑘−1 = 𝑓0 = 2𝑞 là số (N+1)-bit nên 
𝑓𝑘−1 ≥ 2
𝑁. Cho nên: 
Journal of Science and Technology on Information security 
28 No 1.CS (11) 2020 
𝐵 = ⌊
2𝐿−1
𝑓𝑘−1
⌋ ≤
2𝐿−1
𝑓𝑘−1
<
2𝐿
2𝑁
= 2𝐿−𝑁. 
Vậy (13) đã được chứng minh. 
Theo (12) thì 𝑙𝑒𝑛(𝑓𝑘−1) = 𝑀𝑘−1 ≤ 𝑀𝑘−2 +
𝑁𝑘−1 ≤ 𝐿 − 𝑁 − 1, hay 𝑓𝑘−1 < 2
𝐿−𝑁−1. Nên 
𝐵 − 𝐴 + 1 = ⌊
2𝐿−1
𝑓𝑘−1
⌋ − ⌈
2𝐿−1
𝑓𝑘−1
⌉ + 1 
 ≥ (
2𝐿−1
𝑓𝑘−1
− 1) − (
2𝐿−1
𝑓𝑘−1
+ 1) + 1 
 = 
2𝐿−1
𝑓𝑘−1
−
1
𝑓𝑘−1
− 1 >
2𝐿−1
2𝐿−𝑁−1
− 2 
 = 2𝑁 − 2. 
Như vậy, Hệ quả 7 đã được chứng minh.■ 
Bổ đề 8. Với mọi số tự nhiên 𝑁 đủ lớn hơn thì: 
a) Khoảng cách trung bình giữa 2 số nguyên tố 
trên tập các số nguyên N-bit, ký hiệu 𝜌(𝑁), 
được đánh giá theo biểu thức sau: 
𝜌(𝑁) < 𝑁. (15) 
b) Khoảng cách trung bình giữa 2 số nguyên tố 
trên tập các số nguyên N-bit cùng dạng 
𝑡. 𝑓 + 1 với f là số tự nhiên lớn hơn 1, ký hiệu 
𝜌𝑓(𝑁), được đánh giá theo biểu thức sau 
𝜌𝑓(𝑁) ≤
𝜑(𝑓)
𝑓
.
𝑁(2𝑁−1+𝑓−1)
2𝑁−1
. 
c) Hơn nữa nếu f là chẵn và nhỏ hơn 2𝑁−1 thì 
𝜌𝑓(𝑁) ≤ 𝑁. (16) 
Chứng minh 
Số các số nguyên tố N-bit, theo định lý 
Gauss là: 
𝜋(2𝑁) − 𝜋(2𝑁−1) ≈
2𝑁
𝑁𝑙𝑛2
−
2𝑁−1
(𝑁 − 1)𝑙𝑛2
=
2𝑁−1(𝑁−2)
𝑁(𝑁−1)𝑙𝑛2
. 
Còn số các số nguyên N-bit là 2𝑁−1 nên: 
 𝜌(𝑁) =
2𝑁−1
𝜋(2𝑁)−𝜋(2𝑁−1)
=
𝑁(𝑁−1)𝑙𝑛2
(𝑁−2)
. 
Do 𝑙𝑖𝑚
𝑁→∞
(𝑁−1)𝑙𝑛2
(𝑁−2)
= 𝑙𝑛2 < 1 nên với 𝑁 đủ 
lớn, ta có vế phải trên < 𝑁 hay (15) đã được 
chứng minh. 
Trước hết, số các số nguyên N-bit có dạng 
𝑡. 𝑓 + 1, ký hiệu là 𝐷𝑓(𝑁) đúng bằng số các số 
nguyên 𝑡 thỏa mãn ⌈
2𝑁−1
𝑓
⌉ − 1 ≤ 𝑡 ≤ ⌊
2𝑁−1
𝑓
⌋ − 1 
nên có ước lượng như sau: 
𝐷𝑓(𝑁) = (⌊
2𝑁 − 1
𝑓
⌋ − 1) − (⌈
2𝑁−1
𝑓
⌉ − 1) + 1 
 ≤
2𝑁−1
𝑓
−
2𝑁−1
𝑓
+ 1 = 
2𝑁−1+𝑓−1
𝑓
. 
Theo định lý Drichlet thì số các số nguyên tố 
N-bit có dạng 𝑡. 𝑓 + 1 là: 
 f(2
N) − f(2
N−1) ≈
1
φ(f)
(
2N
Nln2
−
2N−1
(N−1)ln2
) >
1
φ(f)
.
2N−1
N
. 
Do đó, 𝜌𝑓(𝑁) =
𝐷𝑓(𝑁)
 𝑓(2𝑁)− 𝑓(2𝑁−1)
≤ (
2𝑁−1 + 𝑓 − 1
𝑓
) : (
1
𝜑(𝑓)
.
2𝑁−1
𝑁
) 
=
𝜑(𝑓)
𝑓
.
𝑁(2𝑁−1+𝑓−1)
2𝑁−1
. 
Như vậy đã chứng minh xong bất đẳng thức 
trong phần b) của Bổ đề 8. 
Từ giả thiết 𝑓 là số chẵn nên 
𝜑(𝑓)
𝑓
<
1
2
, còn từ 
𝑓 < 2𝑁−1 nên 
(2𝑁−1+𝑓−1)
2𝑁−1
≤ 2, do đó khi thay vào 
vế phải của bất đẳng thức trên có ngay bất đẳng 
thức (16). Bổ đề 8 đã được chứng minh.■ 
B. Các đánh giá về Thuật toán 3 
Đánh giá 1. Thuật toán 3 là đúng đắn, hơn thế 
nữa nếu 
2𝑁
(𝐿−𝑁)𝐿
> 1 thì thuật toán luôn sinh được 
bộ (𝑝, 𝑞) an toàn theo Định nghĩa 1. 
Chứng minh 
Biết rằng với mọi số nguyên dương a thì 
𝑃𝑟𝑖𝑚𝑒(𝑎, 2𝑎) ≠ ∅ nên với mọi 𝑁 ta có 
𝑃𝑟𝑖𝑚𝑒(2𝑁−1, 2𝑁 − 1) = 𝑃𝑟𝑖𝑚𝑒(2𝑁−1, 2𝑁) ≠
∅, ngoài ra do 𝑞 là số nguyên tố N-bit nên 
𝑃𝑟𝑖𝑚𝑒(𝑞, 2𝑁 − 1) ≠ ∅ nên các bước 1, 5.2 và 
5.3 luôn thực hiện được và các số nguyên tố 𝑞𝑖 
tìm được trong các bước này đều thỏa mãn 𝑞𝑖 𝑞. 
Từ giả thiết 𝐿 2(𝑁 + 1) và từ 𝑀0 =
𝑙𝑒𝑛(2𝑞) = 𝑁 + 1 nên: 
⌊
𝐿−𝑀0−1
𝑁
⌋ ≥ ⌊
2(𝑁+1)−(𝑁+1)−1
𝑁
⌋ = 1 hay 
[1, ⌊
𝐿−𝑀0−1
𝑁
⌋] ≠ ∅. 
Vậy bước 3 là thực hiện được. 
Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 Số 1.CS (11) 2020 29 
Hệ quả 5 chính là điều kiện để bước 5.1 thực 
hiện được. 
Muốn chứng tỏ bước 7 cũng thực hiện được 
ta cần chỉ ra 𝑃𝑟𝑖𝑚𝑒(𝐴, 𝐵) ≠ ∅. 
Quả thật, do 
𝐵
𝐴
= ⌊
2𝐿−1
𝑓𝑘−1
⌋ : ⌈
2𝐿−1
𝑓𝑘−1
⌉ ≤
2𝐿−1
𝑓𝑘−1
:
2𝐿−1
𝑓𝑘−1
< 2 nên [𝐴, 𝐵] sẽ chỉ gồm những số 
nguyên cùng T-bit hoặc gồm hai loại số nguyên 
T-bit và (T–1)-bit (ở đây 𝑇 = 𝑙𝑒𝑛(𝐵)). 
Trong trường hợp thứ nhất, theo phần a) của 
Bổ đề 8 thì: 
# 𝑃𝑟𝑖𝑚𝑒(𝐴, 𝐵) ≥
𝐵−𝐴+1
𝑇
. 
Còn trong trường hợp thứ hai, cũng theo Bổ 
đề 8 thì: 
# 𝑃𝑟𝑖𝑚𝑒(𝐴, 𝐵) 
= # 𝑃𝑟𝑖𝑚𝑒(𝐴, 2𝑇−1 − 1) + # 𝑃𝑟𝑖𝑚𝑒(2𝑇−1, 𝐵) 
2𝑇−1−𝐴
𝑇−1
+
𝐵−2𝑇−1+1
𝑇
≥
𝐵−𝐴+1
𝑇
. 
Mặt khác, giá trị 𝐵 ứng với trường hợp 𝑘 = 1 
là lớn nhất, khi này 𝑓 = 2𝑞, nên 𝐵 < 2𝐿−𝑁. 
Bất đẳng thức trên có nghĩa 𝑇 = 𝑙𝑒𝑛(𝐵) <
 𝐿 – 𝑁 và kết hợp với bất đẳng thức (6) trong Hệ 
quả 7, thu được bất đẳng thức sau: 
# 𝑃𝑟𝑖𝑚𝑒(𝐴, 𝐵) >
2𝑁
𝐿−𝑁
. 
Cuối cùng, xét đến bước 9 của thuật toán. 
Trong bước này các số được duyệt là có dạng 
𝑝 ← 𝑓𝑘−1 ∗ 𝑞𝑘 + 1 với 𝑞𝑘 ∈ 𝑃𝑟𝑖𝑚𝑒(𝐴, 𝐵). 
Chúng gồm không dưới 
2𝑁
(𝐿−𝑁)
 các số L-bit và do 
𝑓𝑘−1 là số chẵn và nhỏ hơn 2
𝐿, nên theo phần c) 
của Bổ đề 8 số các số nguyên tố trong số này là: 
#
 𝑃𝑟𝑖𝑚𝑒(𝐴,𝐵)
𝜌𝑓𝑘−1
(𝐿)
2𝑁
(𝐿−𝑁)𝐿
. 
Từ bất đẳng thức trên, ta thấy rằng nếu vế phải 
của bất đẳng thức lớn hơn 1 thì thuật toán sẽ tìm 
được cặp (𝑝, 𝑞). Tính an toàn của (𝑝, 𝑞) được cho 
bởi Hệ quả 6. 
Kết quả tiếp theo sẽ trình bày đánh giá về chi 
phí tính toán của Thuật toán 3. Do trong thuật 
toán sử dụng đến việc kiểm tra tính nguyên tố của 
một số nguyên mà việc làm này có chi phí phụ 
thuộc vào phương pháp kiểm tra (chẳng hạn chi 
phí theo phương pháp như Miller và Rabin là 
𝑂(𝑁3) còn theo AKS là 𝑂(𝑁6)) nên tác giả dùng 
ký hiệu 𝑇𝑇𝑒𝑠𝑡(𝑁) để đại diện cho chi phí kiểm tra 
tính nguyên tố của một số nguyên N-bit. 
Đánh giá 2. Chi phí để sinh được 1 cặp (𝑝, 𝑞) an 
toàn với 𝑝 – 1 có 𝑘 + 2 ước nguyên tố kể cả bội, 
ký hiệu là 𝑇𝐺𝑒𝑛(𝑘), được cho bởi công thức sau. 
𝑇𝐺𝑒𝑛(𝑘) ≤
𝑘.𝑁
2
. 𝑇𝑇𝑒𝑠𝑡(𝑁) + 𝐿(𝑇𝑇𝑒𝑠𝑡(𝐿) +
𝑀. 𝑇𝑇𝑒𝑠𝑡(𝑀)). (17) 
Với 𝑀 = 𝐿 − 𝑘𝑁 + 𝑘 − 1. 
Chứng minh 
Từ giả thiết 𝑝 – 1 có 𝑘 + 2 ước nguyên tố kể 
cả bội, bỏ qua hai ước nguyên tố là 2 và 𝑞 thì còn 
thêm đúng 𝑘 ước nguyên tố nữa (đương nhiên 
theo thuật toán 3 thì 1 ≤ 𝑘 ≤ ⌊
𝐿−𝑀0−1
𝑁
⌋). Ngoài ra 
𝑇𝑇𝑒𝑠𝑡(𝑁) luôn có bậc cao nhất trong các phép 
tính số học dùng trong thuật toán nên ta chỉ quan 
tâm đến chi phí trên với thực tế nó là một đại 
lượng đơn điệu tăng theo 𝑁. 
Theo phần a) của Bổ đề 8 thì chi phí trung 
bình cho việc sinh một số nguyên tố N-bit (thực 
hiện 𝑞 ← 𝑅𝑎𝑛𝑑𝑜𝑚(𝑃𝑟𝑖𝑚𝑒(2𝑁−1, 2𝑁 − 1)) theo 
Thuật toán 1) sẽ là 
𝑁
2
. 𝑇𝑇𝑒𝑠𝑡(𝑁). 
Trong Thuật toán 3, cần đến việc sinh số 
nguyên tố N-bit q ở bước 1 và 𝑘 – 1 số nguyên 
tố Ni-bit 𝑞𝑖 (𝑖 = 1, . . , 𝑘 − 1) ở bước 5. Như vậy 
cho đến hết bước 5 cần một chi phí tính toán là: 
 𝑇1 =
1
2
(𝑁. 𝑇𝑇𝑒𝑠𝑡(𝑁) + ∑ 𝑁𝑖 . 𝑇𝑇𝑒𝑠𝑡(𝑁𝑖)
𝑘−1
𝑖=1 ). 
Bước 7 và bước 8 thực hiện sinh 1 số nguyên 
tố 𝑞𝑘 và kiểm tra tính nguyên tố của số L-bit 𝑝. 
Tương tự mỗi lần lặp ở bước 9, thì 9.1 thực hiện 
tìm số nguyên tố tiếp theo (thực hiện 
𝑞𝑘 ← 𝑁𝑒𝑥𝑡𝑃𝑟𝑖𝑚𝑒[𝐴,𝐵](𝑞𝑘) theo Thuật toán 2) và 
kiểm tra tính nguyên tố của số L-bit p (điều kiện 
dừng cho vòng 𝑤ℎ𝑖𝑙𝑒). Do các giá trị 𝑝 = 𝑓𝑘−1 ∗
𝑞𝑘 + 1 được kiểm tra trong bước 9 không phải là 
các số liền nhau trong tập các số dạng 𝑝 = 𝑓𝑘−1 ∗
𝑡 + 1, nên số lần lặp trung bình của bước này sẽ 
là 𝜌𝑓𝑘−1(𝐿) < 𝐿. 
Như vậy, chi phí cho các bước 7, 8 và 9 trung 
bình là: 
𝑇2 = 𝐿(𝑇𝑇𝑒𝑠𝑡(𝐿) + 𝑁𝑘 . 𝑇𝑇𝑒𝑠𝑡(𝑁𝑘)) (18) 
với 𝑁𝑘 = 𝑙𝑒𝑛(𝑞𝑘). 
Do 𝑘 < 𝐿 nên 𝑇𝐺𝑒𝑛(𝑘) = 𝑇1 + 𝑇2 sẽ lớn nhất 
khi 𝑁𝑘 lớn nhất, từ quan hệ: 
Journal of Science and Technology on Information security 
30 No 1.CS (11) 2020 
2𝐿−1 < 𝑓𝑘−1 ∗ 𝑞𝑘 + 1 ≤ 2
𝐿 − 1 
nên điều trên xảy ra khi 𝑓𝑘−1 bé nhất tức là 
𝑓𝑘−1 = 2. 𝑞
𝑘. 
Khi đó: 
𝑇1 =
𝑘.𝑁
2
. 𝑇𝑇𝑒𝑠𝑡(𝑁). 
Do 𝑞 > 2𝑁−1 nên: 
𝑓𝑘−1 > 2
𝑘(𝑁−1)+1 𝑞𝑘 < 2
𝐿−(𝑘(𝑁−1)+1) = 2𝑀 
 𝑁𝑘 < 𝑀. (19) 
Thay (19) vào (18) ta được: 
𝑇𝐺𝑒𝑛(𝑘) = 𝑇1 + 𝑇2 <
𝑘.𝑁
2
. 𝑇𝑇𝑒𝑠𝑡(𝑁) +
𝐿(𝑇𝑇𝑒𝑠𝑡(𝐿) + 𝑀. 𝑇𝑇𝑒𝑠𝑡(𝑀)). 
Và đây là điều cần chứng minh.■ 
Đánh giá 3. Thuật toán 3 không thể sinh toàn bộ 
các cặp (p, q) an toàn. 
Chứng minh 
Xét Thuật toán 3 với cặp đầu vào (𝐿, 𝑁) =
(8, 2). Với bước 3 của Thuật toán 3 thì số các 
ước nguyên tố lẻ của 𝑝 – 1, không kể 𝑞, tối đa là: 
𝑘 = ⌊
𝐿−𝑀0−1
𝑁
⌋ = ⌊
8−3−1
2
⌋ = 2. 
Như vậy Thuật toán 3 này không thể sinh 
được bộ (𝑝, 𝑞) = (163, 3) do 163 = 2. 34 + 1 
tương ứng với 𝑘 = 3. 
V. MỘT SỐ KẾT QUẢ CỦA CÀI ĐẶT THUẬT TOÁN 
Sử dụng bộ công cụ lập trình Visual Studio 
2013 kết hợp với thư viện mật mã Miracl để cài 
đặt Thuật toán 3, kết quả thu được các bộ tham 
số dùng cho các giao thức thỏa thuận khóa DH-
KE an toàn, chống lại được các tấn công như đã 
chỉ ra ở trên. 
Ví dụ về bộ tham số được sinh bởi chương trình: 
Bộ tham số: 
Số nguyên tố 𝒑 (2048 bit): 
8BF76C050D3DFB10C9FB37D722F986388
DE867CA00499826C96562867844430F74
BB0E04E141BED83E4930ECDCB268C8852
6E6A1F2E37D43543D60F9775A0F83F17D
523A8DF64A3A12CBC667E78F9BD0F4019
599D1E186AE9AAF6E56BD93CA053DE0E7
D6066A466D0E60DC96991B9006DC18EA1
B9C70726EDF99028DAD6E632B9A1B6E4B
070BA1C975250B986E6993EB58853A2AE
CC2B9F2CBE903338752ED080222192C08
1D757AED91E30DC6C5AC904AF07BFD723
87335331C279701849D2F652DD0A9EB35
ACD8C3F644B71D20635D34940FF7F9AC8
0E7A72AAF60A11D53FA8B08D4A8336749
CE9A723C5545461E11FDA4B7A9556B768
07F81948652F677A7 
Số nguyên tố 𝒒 (224 bit): 
8BF59EC7A4FA0349F4D76BF6D26BBE668
6D07B8B2DAFB3283D397337 
Các số nguyên tố 𝒑𝒊 : 
p0 (692 bit): 
DAC8F4EDD3FC57287873DC63AB8B6AD83
7722E0D211194CA80CEA267C24233FAA8
94E90DD62C89DCFA81663B83477468E8E
8280758A1507E36DF0876C07F498BD6B0
A54DF7E57B7B013DBC651AD019B1494E3
4A213581 
p1 (1132 bit): 
95C7B7C6166A3AB9CC497D086A82E87CF
32E2153FF491771BE334F45EE678C7B6F
E062DD86C07232E6B0CF29A53A1ACFC83
C870AD062335ECEB18D2350E6DE107A67
265B6E02923DFA621B19CAF96444D61D1
0EE946A6806342D6E97733683A108C4B0
F97B62828145C8AF53FA0AB44DA0F3EA3
DDCEA50B2229CBE583EB89570CDB2C8E2
1E3E0892C9A056616C5 
VI. KẾT LUẬN 
Đối với việc triển khai các giao thức trao đổi 
khóa kiểu DH-KE trong các ứng dụng bảo mật 
thông tin, thì việc sinh được các bộ tham số an 
toàn là rất quan trọng, nó đảm bảo cho giao thức 
DH-KE chống lại được một số tấn công để tìm ra 
khóa bí mật của người dùng (cụ thể là các tấn công 
liên quan đến nhóm con nhỏ). Bài báo đã đề xuất, 
xây dựng được một thuật toán sinh số nguyên tố 
an toàn và các đánh giá, phân tích về tính đúng 
đắn, độ phức tạp của thuật toán về mặt toán học. 
Đây là ưu điểm chính của thuật toán đề xuất so với 
thuật toán sinh số nguyên tố an toàn của Lim-Lee, 
vì thuật toán đó chỉ chú trọng vào việc sinh thực 
nghiệm cho những số nguyên tố dạng này nhưng 
không có đảm bảo chắc chắn về mặt toán học cho 
việc sinh chúng. Bài báo cũng đưa ra kết quả cài 
đặt thực tế của thuật toán để minh chứng cho tính 
khả thi của thuật toán đưa ra. 
Khoa học và Công nghệ trong lĩnh vực An toàn thông tin 
 Số 1.CS (11) 2020 31 
TÀI LIỆU THAM KHẢO 
[1] S. C. Pohlig and M. E. Hellman (1978), An 
improved algorithm for computing logarithms 
over GF(p) and its cryptographic significance, 
IEEE Trans. Inform. Theory, IT-24 (1), 
pp.106-110. 
[2] C. Lim and P. Lee (1997), A Key Recovery 
Attack on Discrete Log-based Schemes Using a 
Prime Order Subgroup, EUROCRYPT 1997. 
[3] J.M.Pollard (1978), Monte Carlo methods for 
index computation (rood p), Math. Comp., 
32(143), pp.918-924. 
[4] FIPS PUB 186-3 (2009), Digital Signature 
Standard (DSS), 
https://csrc.nist.gov/csrc/media/publications/fips/
186/3/archive/2009-06-25/documents/fips_186-
3.pdf, Accessed on 10/9/2020. 
[5] T. Matsumoto, Y. Takashima and H. Imai (1986), 
On seeking smart public-key distribution 
systems, The Transactions of the [EICE of Japan, 
E69, pp.99-106. 
[6] FSF, Gnu privacy guard,  
Accessed on 10/9/2020. 
[7] Gutmann. P, cryptlib, 
https://www.cs.auckland.ac.nz/~pgut001/cryptlib/, 
Accessed on 10/9/2020. 
[8] PGP. I, OpenPGP, https://www.openpgp.org/, 
Accessed on 10/9/2020. 
[9] MIRACL, MIRACL Cryptographic SDK, 
https://github.com/miracl/MIRACL, Accessed 
on 10/9/2020. 
[10] Rechard Crandall, Carl Pomerance (2005), 
Prime Numbers: A Computational Perspetive, 
Springer, 
https://www.springer.com/gp/book/9780387252
827, Accessed on 10/9/2020. 
[11] Nguyễn Quốc Toàn, Đỗ Đại Chí, Triệu Quang 
Phong (2016), Về một tiêu chuẩn tham số cho bài 
toán logarithm rời rạc, Nghiên cứu Khoa học và 
Công nghệ trong lĩnh vực An toàn thông tin, ISSN 
2615-9570. No 02. Vol 01. 2016. 
SƠ LƯỢC VỀ TÁC GIẢ 
ThS. Nguyễn Thanh Sơn 
Đơn vị công tác: Cục Quản lý mật mã 
dân sự và Kiểm định sản phẩm mật 
mã, Ban Cơ yếu Chính phủ. 
Email: vuphongthanhson@gmail.com 
Quá trình đào tạo: Tốt nghiệp Kỹ sư 
Kỹ thuật mật mã (1993-1998); Thạc 
sĩ Kỹ thuật mật mã (2002-2005) tại Học viện Kỹ thuật 
mật mã. 
Hướng nghiên cứu hiện nay: An toàn bảo mật thông tin, 
Kỹ thuật mật mã.