Bài giảng An toàn và bảo mật thông tin - Đại Học Nha Trang

 aA1 - aQB1 + bA2 - bQB2 
 = A3 – QB3 
 aR1 + bR2 = R3 (3) 
Vậy trong suốt quá trình lặp của thuật toán các đẳng thức (1), (2), (3) luôn được thỏa 
mãn. 
Trong trường hợp gcd(a, b) 1, thuật toán trên hoạt động tương tự như thuật toán 
Euclid chuẩn (A3 và B3 tương tự như A và B trong thuật toán chuẩn). Khi kết thúc vòng lặp 
B3 = 0, A3 là ước số chung lớn nhất). 
Trong trường hợp gcd(a, b) = 1. Theo thuật toán Euclid chuẩn thì A3 = 1, B3= 0. Suy 
ra trong lần lặp ngay trước đó B3 = 1. Trong thuật toán mở rộng vòng lặp sẽ kết thúc khi B3 
= 1. Ta có: 
 aB1 + bB2 = B3 
  aB1 + bB2 = 1 
  bB2  1 mod a 
Vậy B2 là nghịch đảo của b trong phép modulo m. 
176 
Ví dụ: a = 63, b= 35 
Ví dụ: a = 25, b= 7 
Phương pháp kiểm tra số nguyên tố lớn Miller-Rabin 
Để kiểm tra xem một số p có phải là số nguyên tố hay không, một thuật toán cổ điển 
là kiểm tra xem p có chia hết cho 2 và p chia hết cho các số lẻ từ 3 đến ⌊√ ⌋ hay không. 
Nếu p không chia hết cho các số trên thì p là số nguyên tố, ngược lại chỉ cần p chia hết cho 
một trong các số trên, thì p không phải là số nguyên tố. Tuy nhiên nếu p là số nguyên tố 
lớn thì việc kiểm tra các số như vậy không hiệu quả về mặt thời gian. 
Đối với số nguyên tố, ta có hai bổ đề sau: 
Bổ đề 1: với p là số nguyên tố, x là số nguyên, x2  1 mod p khi và chỉ khi x  1 mod 
p hoặc x  (p1) mod p. 
Chứng minh: x2  1 mod p  x2 - 1  0 mod p  (x – 1)(x+1)  0 mod p (*) 
Vì p là số nguyên tố nên (*) tương đương với x10 mod p hay x+1 0 mod p. Hay 
nói các khác x  1 mod p hay x  (p1) mod p. (đpcm) 
Bổ đề 2: với p là số nguyên tố, viết lại p dưới dạng p = 2kq + 1 trong đó q là số lẻ. 
Với a là số nguyên dương nhỏ hơn p, ta có kết luận sau: 
*) Hoặc 1 
**) Hoặc trong dãy số 
 tồn tại một số mà đồng dư với 
 1 (mod p) 
Chứng minh: 
Đặt ta viết lại dãy số trên thành 
A3 B3 Q R3 A2 B2 Q R2 
63 = 35 × 1 + 28 0 = 1 × 1 - 1 
35 = 28 × 1 + 7 1 = -1 × 1 + 2 
28 = 7 × 4 + 0 -1 = 2 × 4 - 9 
 0 
Không có nghịch đảo 
A3 B3 Q R3 A2 B2 Q R2 
25 = 7 × 3 + 4 0 = 1 × 3 - 3 
 7 = 4 × 1 + 3 1 = -3 × 1 + 4 
 4 = 3 × 1 + 1 -3 = 4 × 1 - 7 
 1 -7 
Nghịch đảo là: -7 + 25 = 18 (7*18 = 126  1 mod 25) 
177 
Theo định lý Fermat, ta có 1 suy ra 
 1 
hay 
 1 
Như vậy trong dãy số 
 có số cuối cùng đồng dư với 1. Vận 
dụng bổ đề 1, ta có kết luận sau: 
 Hoặc là 1 và do đó các phần tử còn lại trong dãy đều đồng dư với 
1. Trong trường hợp này ta có kết luận *). 
 Hoặc là có một số 
 1 tuy nhiên 
 1 . Đo 
đó theo bổ đề 1 thì 
 p 1 . Trong trường hợp này ta có kết luận 
**). (đpcm) 
Như vậy nếu p là số nguyên tố thì p phải thỏa mãn hai bổ đề trên. Tuy nhiên mệnh đề 
ngược lại thì chưa chắc đúng, có nghĩa là một số hợp số cũng có thể thỏa mãn hai bổ đề 
này. 
Từ nhận xét trên, người ta xây dựng thuật toán kiểm tra số nguyên tố Miller-Rabin 
như sau: 
/* Thuật toán Miller-Rabin kiểm tra tính nguyên tố của số nguyên p /* 
TEST(p) 
Tìm k, q với k> 0, q lẻ thỏa mãn 2 1 
Chọn số ngẫu nhiên a trong khoảng [2, p - 1] 
If 1 Then return ‚p có thể là số nguyên tố‛; 
For j= 0 to k-1 do 
 If 
 1 Then return ‚p có thể là số nguyên tố‛; 
return ‚p không phải là số nguyên tố‛; 
Ví dụ 1 : kiểm tra số p = 29 
29 2 7 1 do đó k = 2, q = 7. 
Nếu chọn a = 10: 107 mod 29 = 17 do đó ta sẽ tiếp tục tính (107)2 mod 29 = 28 thủ 
tục kiểm tra sẽ trả về “có thể là số nguyên tố”. 
Nếu chọn a = 2: 27 mod 29 = 12 do đó ta sẽ tiếp tục tính (27)2 mod 29 = 28 thủ tục 
cũng sẽ trả về “có thể là số nguyên tố”. 
Vì vậy, nếu chỉ thử một vài giá trị a, ta chưa thể kết luận gì về tính nguyên tố của p. 
Tuy nhiên nếu thử hết các giá trị a từ 2 đến 28 ta đều nhận được kết quả “có thể là số 
nguyên tố”. Vì vậy có thể chắc chắn rằng 29 là số nguyên tố. 
Ví dụ 2 : kiểm tra số p = 221 
221 2 55 1 do đó k = 2, q = 55. 
Nếu chọn a = 5: 555 mod 221 = 112 do đó ta sẽ tiếp tục tính (555)2 mod 29 = 168, 
do đó thủ tục kiểm tra sẽ trả về ‚không phải là số nguyên tố‛. Điều này đúng vì 
221 = 13 x 17. 
178 
Tuy nhiên nếu chọn a = 21: 2155 mod 221 = 200 do đó ta sẽ tiếp tục tính (2155)2 
mod 29 = 220, lúc này thủ tục sẽ trả về ‚có thể là số nguyên tố‛. Nghĩa là trong 
một số trường hợp của a, thuật Miller-Rabin không xác định được tính nguyên tố của 221. 
Người ta đã tính được xác suất để trong trường hợp p là hợp số, thuật toán Miller-
Rabin đưa ra khẳng định ‚không phải là số nguyên tố‛ là 75%. Trong 25% còn lại, 
Miller-Rabin không xác định được p nguyên tố hay hợp số. Do đó nếu chúng ta áp dụng 
thuật toán t lần (mỗi lần với các giá trị a khác nhau) thì xác suất không xác định (trong cả t 
lần) là (0.25)t. Với t bằng 10, xác suất trên là rất bé, nhỏ hơn 0.000001. 
Tóm lại nguyên tắc kiểm tra tính nguyên tố của số nguyên p thực hiện như sau: 
- Thực hiện thuật toán Miller-Rabin 10 lần với 10 số a ngẫu nhiên khác nhau. 
- Nếu cả 10 lần thuật toán cho ra kết quả ‚có thể là số nguyên tố‛, thì ta 
khẳng định p là số nguyên tố. 
- Chỉ cần một lần thuật toán cho ra kết quả ‚không phải là số nguyên tố‛, 
thì ta khẳng định p là hợp số. 
Ví dụ 3: p = 41, 41 2 5 1 do đó k = 3, q = 5, p-1 = 40 . 
 a aq mod p a2q mod p a4q mod p 
7 38 9 40 
8 9 40 
9 9 40 
12 3 9 40 
13 38 9 40 
16 1 
24 14 32 40 
25 40 
31 40 
37 1 
  41 là số nguyên tố 
Ví dụ 4: p = 133, 133 2 33 1 do đó k = 2, q = 33, p-1 = 132 . 
 a aq mod p a2q mod p 
11 1 
17 83 106 
27 132 
30 1 
38 76 57 
58 1 
75 132 
94 132 
102 1 
121 1 
  133 không phải là số nguyên tố (133 = 7 * 19) 
Tuy tính toán hơi phức tạp nhưng thuật toán Miller-Rabin là thuật toán kiểm tra số 
nguyên tố hiệu quả nhất, thực hiện nhanh nhất trong các thuật toán kiểm tra số nguyên tố 
đã biết. 
179 
Định lý số dƣ Trung Hoa 
Định lý số dư Trung Hoa cho phép thay vì phải thực hiện các phép toán mod T trong 
trường hợp T lớn, ta có thể chuyển về tính toán trên các phép mod ti , với các ti nhỏ hơn T. 
Do đó định lý số dư Trung Hoa giúp tăng tốc độ tính toán của thuật toán RSA. 
 Giả sử: ∏ 
 . Trong đó các số nguyên tố cùng nhau 
từng đôi một. Xét tập ZT và tập X là tích Decarte của các tập (ZT là tập các số nguyên từ 
0 đến T-1): 
Ta có hai định lý số dư Trung Hoa sau: 
Định lý 1: Tồn tại một song ánh giữa tập ZT và tập X. Nghĩa là: 
 sao cho A = f(a1, a2, …, ak) 
 và sao cho (a1, a2, …, ak) = f -1(A) 
Chứng minh: 
1) Ánh xạ thuận: Để chuyển A thành (a1, a2, …, ak), ta có thể tính ai = A mod ti . 
2) Ánh xạ nghịch: Để chuyển (a1, a2, …, ak) thành A, ta thực hiện như sau: 
Phương án 1 (do nhà toán học người Trung Quốc Chin Chiu-Shao đề xuất vào năm 1247): 
Đặt Ti = T/ti = t1.t2…ti-1.ti+1...tk , như vậy Ti  0 mod tj , i≠j. Ngoài ra còn có Ti 
nguyên tố cùng nhau với ti (theo giả thiết các ti đều nguyên tố cùng nhau). Suy ra tồn tại 
phần tử nghịch đảo 
 sao cho : 
 1 . 
 Ta tính A bằng công thức: 
Để bảo đảm ánh xạ nghịch là đúng, ta cần chứng minh ai = A mod ti . Ta có: 
 ( 
 ) 
 (vì T chia hết cho ti) 
 (vì Tj  0 mod ti , i≠j) 
 1 (vì 
 1 ) 
 (đpcm) 
Phương án 2 (do nhà toán học H.L.Garner đề xuất vào năm 1959): 
Trong phương án này dùng thuật toán Euclid mở rộng, chúng ta lập 
 hằng số 
 1 như sau: 
 1 
j i t1 t2 t3 t4 
t1 c12 c13 c14 
t2 c23 c24 
t3 c34 
t4 
180 
Và tính k giá trị trung gian bi như sau: 
 ( ) 
…. 
 ( ) 
Và A được tính theo công thức: 
Để bảo đảm ánh xạ nghịch là đúng, ta cần chứng minh ai = A mod ti . Ta có: 
Ta có: 
 ( ) 
Đặt , ta có: 
 … 
Vậy ta có kết luận: 
Định lý 2: Các phép toán số học modulo thực hiện trên ZM có thể được thực hiện 
bằng k phép toán tương tự lần lượt trên: . Cụ thể, nếu A  (a1, a2, …, ak), B 
 (b1, b2, …, bk) thì: 
Dựa vào định lý này nếu A, B, M là các số rất lớn thuộc không gian ZT khó tính toán, 
ta có thể chuyển đổi A, B, M về dạng ai, bi, ti . Sau đó thực hiện tính toán trên không gian 
các tập , cuối cùng chuyển ngược kết quả lại về không gian ZT. Do đó nếu số phép tính 
nhiều, thì việc thực hiện trên không gian các tập sẽ mang lại hiệu quả cao so với chi phí 
chuyển đổi. 
181 
Ví dụ định lý số dư Trung Hoa: 
 Cho T = 1813 = 37 x 49. Tính X+Y = 678+973 mod 1813. 
Ta có t1 = 37, t2 = 49. 
Vậy X được biểu diễn thành: (678 mod 37, 678 mod 49) = (12, 41). Y được biểu 
diễn thành (973 mod 37, 973 mod 49) = (11, 42). Do đó: 
(678+973) mod 1813 = ((12+11) mod 37, (41+42) mod 49) = (23, 34) 
Và cuối cùng kết quả của phép cộng là: 
Theo phương án 1: 
T1 = 49, T2 = 37 
 34 
 4 
 23 49 34 34 37 4 1813 
 = 38318 5 32 1813 
 = 4335 1813 
 = 1651 chính là 678 973 
Theo phương án 2: 
c12 = 4 
b1 = 23, b2 = (34 – 23)4 mod 49 = 44 
 23 44 37 = 1651. 
Cài đặt giao thức SSL cho Web server IIS 
(Xem nội dung tại MSOpenLab  
182 
TÀI LIỆU THAM KHẢO 
[1]. Bảo mật thông tin, mô hình và ứng dụng  Nguyễn Xuân Dũng  Nhà xuất bản 
Thống Kê  2007. 
[2]. Cryptography and Network Security Principles and Practices, 4
th
 Edition  
William Stallings  Prentice Hall  2005. 
[3]. Information Security Principles and Practices  Mark Stamp  John 
Wiley&Son, Inc  2006. 
[4]. Applied Cryptography, 2
nd
 Edition  Bruce Sneider John Wiley&Son, Inc  
1996. 
[5]. AES Proposal: Rijndael Block Cipher Joan Deamen, Vincent Rijmen. 
[6]. Differential Cryptanalysis of DES-like cryptosystem – Edi Biham, Adi Shamir. 
- 1990 
[7]. Linear Cryptanalysis Method for DES cipher – Matsui – Springer-Velag – 
1998 
[8]. Guide to elliptic curve cryptography – Hankerson, Menezes, Vanstone –
Springer, 2004 
[9]. How Secure Is Your Wireless Network  Lee Barken  Prentice Hall  2003 
183 
BỘ GIÁO DỤC VÀ ĐÀO TẠO 
TRƢỜNG ĐẠI HỌC NHA TRANG 
KHOA CÔNG NGHỆ THÔNG TIN 
----- ----- 
BÀI GIẢNG 
AN TOÀN VÀ BẢO MẬT 
THÔNG TIN 
(Lưu hành nội bộ) 
Nha Trang, tháng 6 năm 2008 
184 
BÀI GIẢNG 
AN TOÀN VÀ BẢO MẬT 
THÔNG TIN 
 Biên soạn: Trần Minh Văn 
(Tài liệu tham khảo chính: Cryptography and Network Security Principles and Practices, 
4
th
 Edition  William Stallings  Prentice Hall  2005)