B
Ộ GIÁO DỤC V
À ĐÀO T
ẠO

B
Ộ QUỐC PH
ÒNG

VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ
HOÀNG VĂN THỨC HỆ TIÊU CHUẨN THAM SỐ AN TOÀN
CHO HỆ MẬT RSA VÀ ỨNG DỤNG Chuyên ngành: Bảo đảm toán học cho máy tính
và hệ thống tính toán
Mã số:
62 46 35 01


họp tại Viện Khoa học và Công nghệ quân sự vào hồi
giờ ngày tháng năm 2011
Có thể tìm hiểu luận án tại thư viện:
- Thư viện Viện Khoa học và Công nghệ quân sự
- Thư viện Quốc gia Việt Nam

1

MỞ ĐẦU

Hệ thống mật mã khoá công khai RSA cũng như hầu hết các
nguyên thuỷ mật mã khác về mô hình hệ mật, cấu trúc thuật toán là
công khai. Tuy nhiên, việc lựa chọn và sử dụng các tham số cho hệ
thống mật mã này sao cho an toàn và hiệu quả là một vấn đề khó.
Việc xây dựng các tiêu chuẩn an toàn cho các tham số RSA là
vấn đề được không ít các nhà khoa học trên thế giới cũng như trong
nước quan tâm nghiên cứu. Bởi vậy, hiện nay có khá nhiều tài liệu
liên quan đến lĩnh vực này đã được công bố, ví dụ như ANSI X9.31,
.NIST 800-57, FIPS 186-3.
Tuy nhiên, cùng với sự phát triển của khoa học lập mã thì khoa
học mã thám cũng không ngừng phát triển với nhiều hình thức tấn
công mới đối với hệ thống mật mã RSA. Việc xem xét lại các tiêu
chuẩn an toàn đã có và nghiên cứu, xây dựng thêm các tiêu chuẩn an
toàn mới cho các tham số RSA là rất cần thiết.
Xuất phát từ những yêu cầu thực tế trên, luận án đã chọn đề tài
"Hệ tiêu chuẩn tham số an toàn cho hệ mật RSA và ứng dụng" để
nghiên cứu là phù hợp.

hoá liên tiếp đối với hệ thống mật mã RSA.
 Xây dựng, cài đặt chương trình thuật toán sinh tham số RSA an
toàn và tích hợp vào bộ chương trình sinh chứng chỉ số theo
chuẩn X509.
 Sửa đổi phần mềm trình duyệt Web để có thể áp dụng các tham
số RSA an toàn trong giao thức bảo mật giao dịch Web. 3

CHƯƠNG 1
TỔNG QUAN VỀ TIÊU CHUẨN THAM SỐ RSA
VÀ CÁC GIAO THỨC BẢO MẬT WEB

Để luận giải về sự cần thiết đồng thời tạo cơ sở cho việc thực
hiện các nội dung nghiên cứu của đề tài luận án, chương này của
luận án trình bày một số kết quả nghiên cứu có liên quan đã được
công bố trong và ngoài nước.

1.1. MỘT SỐ ĐỊNH NGHĨA VÀ KÝ HIỆU
Các ước tầm thường (Trivial Divisor): Các ước 1, -1, N và –N
được gọi là các ước tầm thường của số nguyên N.
Số nguyên tố (Prime Number): Số nguyên N>1 là nguyên tố khi
nó chỉ có các ước tầm thường.
Hợp số (Composit number): Số nguyên N>1 là hợp số nếu nó
không là nguyên tố.
Chứng nhận tính nguyên tố (Primality Certificate): Chứng minh
toán học rằng một số cho trước là thực sự nguyên tố.
Phép chia thử (Trial Division): Phép chia thử của một số N có
nghĩa là kiểm tra tất cả các số nguyên tố nhỏ hơn hoặc bằng N

N pq

,
( ) ( 1, 1)
N lcm p q

  
;
Bước 3: Chọn e thỏa mãn
1 ( )
e N

 
sao cho

gcd( , ( )) 1
e N


;
Bước 4: Tính số nguyên dương d thỏa mãn:
1 ( )
d N

 
và
1(mod ( ))
ed N



d
s m N
 trên m.
Qui trình kiểm tra chữ ký: B sử dụng khoá công khai (N, e) của A
để kiểm tra chữ ký trên m, thông qua việc tính
' (mod )
e
m s N
 , nếu
m = m' thì kết luận chữ ký của A trên m hợp lệ, ngược lại kết luận
không hợp lệ.
1.2.4. Hệ thống mật mã dựa trên RSA
Hiện tại trong các ứng dụng bảo mật thông tin người ta thường
sử dụng hệ mật RSA và lược đồ chữ ký RSA có định dạng. Trong hệ

5

mật RSA có định dạng và lược đồ chữ ký RSA có định dạng người ta
sử dụng thêm tập các hàm chuẩn bị thông báo:
* *
{ : }
N N
G g 
 
.
Khi đó thay vì tính toán trực tiếp trên thông điệp m trong các lược đồ
nguyên thuỷ thì các lược đồ có định dạng tính toán trên
( )
x g m


Chuẩn X9.31 khuyến cáo sử dụng modulus có độ dài 1024+256s,
với s là số nguyên và s0.
Các tiêu chuẩn về các số nguyên tố p, q
Chuẩn X9.31 đưa 07 tiêu chuẩn cho các số nguyên tố p, q dùng
để tạo RSA modulus.
Tiêu chuẩn tham số cho e
e là số nguyên dương thoả mãn
160
2 2
nlen
e

  .
Tiêu chuẩn tham số cho d
d được tính bởi công thức d=e
-1
(mod lcm(p-1, q-1)) và thoả mãn
512 128
2
s
d

 .

1.4.2. Tiêu chuẩn tham số RSA được đưa ra trong FIPS 186-3 và
NIST 800-57
Độ dài tối thiểu của RSA modulus
NIST 800-57 đưa ra tiêu chuẩn về độ dài tối thiểu của RSA
modulus an toàn đến các năm 2010, 2030 và sau năm 2030.
Tiêu chuẩn cho các tham số p và q

1.5.1. Giới thiệu về giao thức bảo mật SSL/TLS
SSL là một giao thức cung cấp dịch vụ truyền thông có bảo mật
giữa các ứng dụng client và server.
1.5.2. Giao thức SSL phiên bản 3.0
Giao thức bảo mật SSL phiên bản 3.0 gồm 4 thành phần chính:
giao thức bắt tay, giao thức bản ghi, giao thức báo lệnh và giao thức
xác định thay đổi mã pháp.
1.5.3. Cơ chế tính khoá phiên trong giao thức SSL
Khoá dùng cho phiên liên lạc sẽ được tính từ các thành phần
ClientHello.random, ServerHello.random, pre_master_secret thông qua
việc sử dụng các hàm băm mật mã. Trong đó thành phần
pre_master_secret được trao đổi có bảo mật sử dụng hệ mật khoá công
khai RSA.
1.5.4. Hệ thống mật mã RSA và bảo mật dịch vụ Web
Hệ thống mật mã khoá công khai RSA được sử dụng trong giao thức
bảo mật SSL với mục đích xác thực và thiết lập khoá chung cho
phiên liên lạc. Tuy nhiên, để áp dụng được các tham số RSA có độ

8

an toàn cao cho các giao thức bảo mật trong các ứng dụng Web ta
cần sửa đổi các mô đun mật mã trong các ứng dụng này.
1.6. KẾT LUẬN CHƯƠNG 1
Trong chương này của luận án đã trình bày tổng quan về các kết
quả nghiên cứu đã được công bố trong và ngoài nước có liên quan
đến các nội dung cần giải quyết của luận án. Nhận xét, đánh giá về
ưu, nhược điểm; đề xuất giải pháp nhằm khắc phục các nhược điểm
và bổ sung những hạn chế còn tồn tại trong các kết quả đó, cụ thể:
 Trên cơ sở tìm hiểu các tiêu chuẩn an toàn cho các tham số của
hệ thống mật mã RSA hiện có để thấy được sự cần thiết của việc

secure_strength(nlen)
".
Bảng 2.1: Độ an toàn của hệ thống mật mã RSA theo độ dài modulus
nlen secure_strength(nlen)
1024 bít 89
1536 bít 106
1792 bít 113
2048 bít 120
Định nghĩa 2.2. Hệ thống mật mã RSA với độ dài modulus nlen
bít là an toàn trước một tấn công cho trước nếu độ phức tạp tính
toán của tấn công đó lớn hơn 2
secure_strength(nlen)
.
2.1.2. Tiêu chuẩn về độ dài RSA modulus
Luận án đề xuất độ dài tối thiểu của RSA modulus an toàn đến
các năm 2015, 2020 và 2025 như bảng 2.3.
Bảng 2.3: Tiêu chuẩn độ dài tối thiểu RSA modulus
Năm nlen
2015 1536 bít
2020 1792 bít
2025 2048 bít

10
Cơ sở đề xuất:
Đảm bảo cho hệ thống mật mã RSA trước tấn công tổng quát: sử
dụng thuật toán phân tích số sàng trường số (NFS) để phân tích N.
2.1.3. Các tiêu chuẩn cho các số nguyên tố p, q
2.1.3.1. Tiêu chuẩn về phương pháp sinh các số nguyên tố
Các số nguyên tố p, q và các số nguyên tố bổ trợ p
1

4

1536 bít 212 bít
1792 bít 226 bít
2048 bít 240 bít
Cơ sở đề xuất:
Nhằm chống lại các kiểu tấn công dựa vào tính chất của các số
nguyên tố p, q: tấn công phân tích số p-1 của Pollard, phân tích số
p1 của Williams và tấn công phân tích số dựa trên thuật toán
Williams cải biên.
2.1.3.3. Tiêu chuẩn về độ dài của các số nguyên tố p, q
p và q được chọn ngẫu nhiên từ các số nguyên tố có độ dài:

  
( / 2) 1 / 2
( 2)(2 ) , (2 1)
nlen nlen
p q

11
Cơ sở đề xuất:
Đảm bảo cho hệ thống mật mã RSA an toàn trước các tấn công
dựa vào các thuật toán phân tích số có độ phức tạp phụ thuộc vào
kích thước các nhân tử nguyên tố, đồng thời tăng tính hiệu quả của
các lược đồ bảo mật và xác thực RSA.
2.1.3.4. Tiêu chuẩn về độ lớn của hiệu |p-q|
Bảng 2.5: Tiêu chuẩn độ dài tối thiểu của |p-q|.
nlen Độ dài tối thiểu của |p-q|
1536 bít 668 bít
1792 bít 796 bít

các tấn công như tấn công của Wiener, tấn công của Boneh và
Durfee.
Trong đó tấn công của Boneh và Durfee thành công khi bất đẳng
thức dưới đây được thoả mãn:
 
1 2
7 1
1 6
6 3
 
   , với
e N

 và
d N

 .
2.1.4.3. Đề xuất tiêu chuẩn cho e và d
Số mũ công khai e có độ dài tối thiểu là 32 bít.
Số mũ bí mật d thoả mãn
0.82
d N .
Cơ sở đề xuất:
Chống lại các tấn công đã đề cập trong các mục 2.1.4.1 và
2.1.4.2.
2.2. CÁC TIÊU CHUẨN MỚI CHỐNG LẠI TẤN CÔNG MÃ HOÁ
LIÊN TIẾP
2.2.1. Chu kỳ RSA và các tính chất của nó
Định nghĩa 2.3. Giá trị t>0 nhỏ nhất sao cho (mod )
t


Tính chất 2.2. Cho M là ước của N. Khi đó với mọi
*
N
m

ta
có: |
M N
ord m ord m

Chứng minh các tính chất 2.1, 2.2 và mệnh đề 2.2 được trình bày
chi tiết trong luận án.
2.2.2. Tiêu chuẩn mới chống lại tấn công mã hoá liên tiếp
Phép tấn công mã hoá liên tiếp
Đầu vào:
*
N
m

;
Đầu ra: c thoả mãn (mod )
e
c N m

;
Thực thi:
Bước 1: z

m;

p

và
1
q

;
11
p

và
11
q
tương ứng là các ước nguyên tố của
1
1
p

và
1
1
q

;và
11
p
,
11
q
>B. Khi đó nếu chọn e sao cho

chống lại được kiểu tấn công mã hoá liên tiếp.
Tiêu chuẩn về độ dài tối thiểu của p
11
, q
11

Độ dài tối thiểu các ước nguyên tố p
11
, q
11
tương ứng của p
1
-1,
và q
1
-1 được cho như bảng Bảng 2.7.
Bảng 2.7: Độ dài tối thiểu của p
11
, q
11

nlen n
5
, n
6

1536 bít 106 bít
1792 bít 113 bít
2048 bít 120 bít


1
, q
2
đều là
các số nguyên tố chứng minh được.
Tiêu chuẩn PQ2 (Tiêu chuẩn thứ hai cho các số nguyên tố p, q):
Độ dài tối thiểu theo bít của các số nguyên tố bổ trợ p
1
, p
2
, q
1
, q
2

được cho như bảng 2.4.

15
Tiêu chuẩn PQ3 (Tiêu chuẩn thứ ba cho các số nguyên tố p, q):
p và q được chọn ngẫu nhiên từ các số nguyên tố thoả mãn:


  
( / 2) 1 / 2
( 2)(2 ) , (2 1)
nlen nlen
p q .
Tiêu chuẩn PQ4 (Tiêu chuẩn thứ tư cho các số nguyên tố p, q):
Độ dài tối thiểu theo bít của |p-q| được cho như bảng 2.5.
Tiêu chuẩn PQ5 (Tiêu chuẩn thứ năm cho các số nguyên tố p, q):

ord e
là bội của
11
q
. 16
2.4.KẾT LUẬN CHƯƠNG 2
Chương này của luận án đã nghiên cứu và đề xuất được hệ tiêu
chuẩn cho các tham số RSA nhằm nâng cao độ an toàn và tính hiệu
quả trong sử dụng của hệ thống mật mã RSA. Hệ tiêu chuẩn được
xây dựng trên cơ sở:
 Xem xét, đánh giá cơ sở đảm bảo sự an toàn cho hệ mật mã RSA
trước các tấn công có liên quan, từ đó đề xuất các tiêu chuẩn đã
có trên thế giới (gồm 08 tiêu chuẩn). Đặc biệt trong đó có 04 tiêu
chuẩn được luận án đề xuất mới về mặt định lượng, gồm: tiêu
chuẩn N1, PQ2, D1 và tiêu chuẩn E1.
 Xây dựng được các tiêu chuẩn mới, gồm 01 tiêu chuẩn cho các
số nguyên tố p, q (tiêu chuẩn PQ6) và 01 tiêu chuẩn cho số mũ
công khai e (tiêu chuẩn E2), nhằm đảm bảo cho hệ thống mật mã
RSA an toàn trước kiểu tấn công mã hoá liên tiếp.

17
CHƯƠNG 3
SINH VÀ TÍCH HỢP THAM SỐ RSA AN TOÀN
CHO DỊCH VỤ BẢO MẬT WEB

3.1. THUẬT TOÁN SINH THAM SỐ RSA AN TOÀN
Trong các thuật toán có sử dụng các ký hiệu dưới đây:

log
2
(qlen) - 5.
 n
0
< nlen - dlen.
3.1.1. Các hằng số và các hàm được sử dụng trong thuật toán
 SS[3] = {106; 113; 120}.
 Dlen[3] = {1260; 1470; 1680}.
 PQlen[3] = {768; 896; 1024}.
 random(x) hàm sinh ngẫu nhiên một số nguyên nhỏ hơn hoặc
bằng số nguyên x.
3.1.2. Thuật toán SinhP (Thuật sinh số nguyên tố thứ nhất)
3.1.2.1. Thuật toán 3.1
Đầu vào: level;
Đầu ra: p, p
0
, p
1
, p
11
;
Giá trị trả về: Sinh p thành công trả về 1, ngược lại trả về 0.
Thực thi:
Bước 1: Lấy plen = PQlen[level]; s = SS[level]; dlen =
Dlen[level]; condlen=log
2
(plen)+2; res = 0;

18

p
có độ dài n
1
bít và
1
1
p

có ước
nguyên tố là
11 1
p
p  ;
Bước 7: Sinh số nguyên tố
2
p
có độ dài n
2
bít;
Bước 8: Sinh ngẫu nhiên một số nguyên:




1
2 2 1,2 1
plen plen
x

  

tp y p p   thì lấy
1
0 1 0 1 2
(2 ( 2)(2 ) )/(2 )
plen
t yp p p p p

 
 
 
 
 
;
Bước 12: Lấy
2 0 1
2( ) 1
p tp y p p
  
; counter = counter+1
Bước 13: Sinh ngẫu nhiên số nguyên
2, 2
a p
 
 
 
;
Bước 14: Tính:
a.
2 1
2( )

Bước 16: Nếu counter<8plen thì lấy t = t + 1, quay về Bước 11;
Bước 17: Cho đầu ra (q, q
1
, q
11
) và trả về res;

19

3.1.2.2. Phân tích thuật toán 3.1
Với việc phân tích chi tiết thuật toán 3.1 ta thu được một số
khẳng định dưới đây:
 Số nguyên p ở đầu ra của thuật toán trên là số nguyên tố
 p
1
là ước của p-1 và p
2
là ước của p+1
3.1.3. Thuật toán SinhQ (Thuật toán sinh số nguyên tố thứ hai)
3.1.3.1. Thuật toán 3.2
Đầu vào: level, p, p
0
;
Đầu ra: q, q
1
, q
11
;
Giá trị trả về: Sinh q thành công trả về 1, ngược lại trả về 0;
Thực thi:

1
q
có độ dài n
3
bít và
1
1
q

có ước
nguyên tố là
11 1
q q
 ;
Bước 5: Sinh số nguyên tố
2
q
có độ dài n
4
bít;
Bước 6: Sinh ngẫu nhiên một số nguyên:




1
2 2 1,2 1
qlen qlen
x


2( ) 1 2
qlen
tq y p q   thì lấy
1
0 1 0 1 2
(2 ( 2)(2 ) )/(2 )
qlen
t yp p
q q q

 
 
 
 
 
;

20
Bước 10: counter=counter + 1;
2 0 1
2( ) 1
q tq y p q
  
; nếu |p-q|

dist thì thực hiện:
a. Nếu counter > 8qlen thì chuyển sang bước 15;
b. Lấy t = t + 1 và quay lại bước 9;
Bước 11: Sinh ngẫu nhiên số nguyên
2, 2

Bước 13: Nếu gcd(u – 1 , q) = 1 và gcd(v – 1 , q) = 1 và
1
z


thì lấy res = 1 và chuyển sang bước 15;
Bước 14: Nếu counter

8qlen lấy t = t + 1 và quay về Bước 9;
Bước 15: Cho đầu ra (q, q
1
, q
11
) và trả về res;
3.1.3.2. Phân tích thuật toán 3.2
Việc phân tích thuật toán 3.2 tương tự như phân tích thuật toán
3.1, ta có các khẳng định dưới đây:
 Số nguyên q được sinh bởi Thuật toán 3.2 chắc chắn là số
nguyên tố.
 q - 1 có ước là q
1
và q +1 có ước là q
2
.
3.1.4. Tính chất của các tham số p, q
Sử dụng thuật toán 3.1 và thuật toán 3.2 để sinh các số nguyên tố
p, q thì các số nguyên tố này sẽ thoả mãn 06 tiêu chuẩn từ tiêu chuẩn
PQ1 đến tiêu chuẩn PQ6 đã trình bày trong chương 2.
3.1.5. Thuật toán SinhED
3.1.5.1. Thuật toán 3.3

( 1)/
1
mod 1
q q
e q


thì
quay lại bước 2;
Bước 4: Tính d = e
-1
mod lmc((p-1),(q-1));
Bước 5: Nếu
2
log ( )
d dlen

thì chuyển sang bước 6, ngược lại
chuyển về bước 2;
Bước 6: Cho đầu ra e, d;
3.1.5.2. Phân tích thuật toán 3.3
Số mũ công khai e và số mũ bí mật d được sinh bằng thuật toán
3.3 thoả mãn tiêu chuẩn E2 và tiêu chuẩn D1.
3.1.6. Thuật toán sinh tham số SinhThamSo
3.1.6.1. Thuật toán 3.4
Đầu vào: level, elen;
Đầu ra: N, e, d;
Thực thi:
Bước 1: Nếu
{0,1,2}

máy tính cá nhân (PC) Dell Optiplex 2100L với cấu hình: CPU Intel
Pentium IV 3 GHz, 256 Mb RAM. Để sinh mỗi loại theo độ dài
modulus là 100 bộ, thời gian chạy được thống kê trong bảng 3.2.
Bảng 3.2: Thời gian sinh các bộ tham số RSA an toàn
Thời gian sinh (giây)
Độ dài
modulus

(bít)
Bộ sinh
nhanh
nhất
Bộ
sinh
lâu
nhất
Tổng
thời
gian
Thời
gian
trung
bình
1536 8 234 8234 82,34
1792 11 530 14493 144,93
2048 20 641 29447 294,47

23
3.2.3. Bằng chứng về tính nguyên tố
Kết quả chạy chương trình lưu lại các số nguyên tố p, q, p

chương trình sinh các chứng chỉ số theo chuẩn X509.
 Nghiên cứu, sửa đổi mã nguồn của một phần mềm trình duyệt
Web mã nguồn mở để có thể áp dụng các tham số RSA an toàn
cho các giao thức bảo mật giao dịch Web.