Giáo trình Lý thuyết mật mã và an toàn thông tin - Phan Đình Diệu (Phần 1)

Tóm tắt Giáo trình Lý thuyết mật mã và an toàn thông tin - Phan Đình Diệu (Phần 1): ...n). Tất cả d nghiệm đó khác nhau theo modn , nh−ng cùng đồng d− với nhau theo modn. Bây giờ ta xét hệ thống các ph−ơng trình đồng d− tuyến tính. Một hệ nh− vậy có thể đ−a về dạng 1 1 1 2 2 2 (mod ) (mod ) ........................ (mod )k k k x a n x a n x a n ⎧ ≡⎪⎪⎪⎪ ≡⎪⎨⎪⎪⎪⎪ ≡⎪⎪... { }2 . 1:1 1, ( 1mod ) ( 1mod ) 4ku u na a n a n k e a n −≤ ≤ − ≡ ∨∃ < ≡− ≤ . Các tiêu chuẩn kể trên là cơ sở để ta xây dựng các thuật toán xác suất kiểu Monte-Carlo thử tính nguyên tố (hay hợp số) của các số nguyên. Chẳng hạn, từ tiêu chuẩn thứ nhất ta có thuật toán Euler- Solovay-Stras... bản mã đều đ−ợc xây dựng trên bảng ký tự tiếng Anh, và hơn nữa các thông báo là các văn bản tiếng Anh. Nh− vậy, ta luôn có P = C = Z26 hay 26Z , và có thêm thông tin là các bản rõ tuân theo các qui tắc từ pháp và cú pháp của ngôn ngữ tiếng Anh. Đây là một căn cứ quan trọng của các ph−ơng ph...

pdf95 trang | Chia sẻ: havih72 | Lượt xem: 440 | Lượt tải: 0download
Nội dung tài liệu Giáo trình Lý thuyết mật mã và an toàn thông tin - Phan Đình Diệu (Phần 1), để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
ên BBS đ−ợc mô tả nh− sau : Chọn 
n =p.q là tích của hai số nguyên tố dạng 4m +3, tức p ≡ 3(mod4) và 
q ≡ 3 (mod4). Gọi QR(n ) là tập các thặng d− bậc hai theo modn. Lấy 
R =QR(n ) , và với mỗi r ∈R xác định dãy số s 0, s1, s2,.... nh− sau: 
 0
2
1
,
mod ,i i
s r
s s n+
=⎧⎪⎨ =⎪⎩
và sau đó định nghĩa zi =ϕ (r ,i ) = si mod2, tức zi là bit thấp nhất 
trong biểu diễn nhị phân của số si. Dãy K = z1z2....zi.... là dòng bit 
đồng bộ đ−ợc tạo ra bởi mầm r. 
Thí dụ : Lấy n = 192649 = 383.503, r = 20749 (= 1013552 modn). Có 
thể tính 20 số đầu của dãy s1,...,s20,... lần l−ợt là: 
 143135, 177671, 97048, 89992, 174051, 80649, 45663, 
 69442, 186894, 177046, 137922, 123175, 8630, 114386, 
 14863, 133015, 106065, 45870, 137171, 18460. 
Và 20 bit đầu của dòng bit giả ngẫu nhiên đ−ợc sinh ra là: 
 z1...z20 = 11001110000100111010. 
Tạo bit giả ngẫu nhiên dựa vào bài toán logarit rời rạc : 
 Chọn p là một số nguyên tố lớn, và α là một phần tử nguyên 
thuỷ theo modp. Tập các mầm khoá là R = pZ
∗ . Với mỗi mầm khoá 
r ∈R ta xác định dãy số s0,...,si .... bởi : 
 0
1
,
mod .isi
s r
s pα+
=
=
 78
 79
s
Sau đó định nghĩa zi = ϕ (r ,i )(i =1,2,....) nh− sau: zi = 1 nếu si > p/2, 
và zi = 0 nếu i < p/2. Và K =z1....zi...... là dòng khoá, tức dòng bit giả 
ngẫu nhiên, đ−ợc tạo ra. 
 Trên đây là một vài cơ chế tạo dòng khoá, và để các dòng 
khoá đ−ợc tạo ra đó là những dòng bit giả ngẫu nhiên tốt , ta đã cố ý 
dựa vào một số bài toán số học khó theo nghĩa là ch−a tìm đ−ợc 
những thuật toán làm việc trong thời gian đa thức để giải chúng, 
nh− các bài toán RSA, bài toán thặng d− bậc hai và bài toán lôgarit 
rời rạc. Các cơ chế tạo dòng khoá đó đ−ợc xem là an toàn nếu ta 
chứng minh đ−ợc rằng không thể có các thuật toán ε-đoán bit tiếp 
theo đối với chúng; hay một cách khác, nếu có thuật toán ε-đoán bit 
tiếp theo đối với chúng thì cũng sẽ có thuật toán (tất định hoặc xác 
suất) giải các bài toán số học t−ơng ứng. Tiếc thay, đến nay ta ch−a 
chứng minh đ−ợc một kết quả nào theo h−ớng mong muốn đó; tuy 
nhiên cũng đã có một vài kết quả yếu hơn, thí dụ, đối với bộ tạo bit 
giả ngẫu nhiên BBS ng−ời ta đã chứng minh đ−ợc rằng : nếu với mọi 
ε > 0 có thuật toán ε- đoán bit có tr−ớc (đối với ϕ và r ) thì với mọi δ 
> 0 cũng có thể xây dựng một thuật toán xác suất giải bài toán thặng 
d− bậc hai với xác suất trả lời sai là < δ (Định nghĩa của thuật toán 
ε- đoán bit có tr−ớc t−ơng tự nh− với thuật toán ε- đoán bit tiếp 
theo, chỉ khác là thay công thức (4) bởi công thức sau đây 
1
1 1
1 1 1 1 1 0
...
1( ... ). ( ( , ... ) ) .
2i
i
i i
z z Z
p z z p B i z z z ε
−−
− −
∈
= ≥ +∑ 
trong đó z0 = s0 mod2 là bit có tr−ớc dãy z1...zi-1). 
 Trong thực tiễn, các hệ mã dòng với dòng khoá là dãy bit 
ngẫu nhiên đã đ−ợc sử dụng từ lâu và còn đ−ợc sử dụng cho đến 
ngày nay, với dòng bit ngẫu nhiên đ−ợc tạo ra một cách cơ học nh− 
việc tung đồng xu liên tiếp và ghi liên tiếp các kết quả “sấp, ngửa” 
của các lần tung. Các hệ mã dòng với dòng khoá ngẫu nhiên và với 
sơ đồ mật mã nền cho bởi các hệ thức (2) có thể đ−ợc xem là “bí mật 
hoàn toàn” theo nghĩa Shannon, do đó rất đ−ợc −a chuộng trong 
ứng dụng thực tế, chúng th−ờng đ−ợc gọi là các hệ đệm một lần 
(one-time pad), đ−ợc mô tả và sử dụng đầu tiên bởi Gilbert Vernam 
năm 1917. Tuy nhiên, việc tạo các dòng bit ngẫu nhiên một cách thủ 
công là không hiệu quả, việc giữ bí mật các dòng khoá nh− vậy lại 
 80
càng khó hơn, nên không thể sử dụng một cách phổ biến đ−ợc, do 
đó ngày nay các hệ mã nh− vậy chỉ còn đ−ợc sử dụng trong những 
tr−ờng hợp thật đặc biệt. 
3.4. Hệ mật mã chuẩn DES. 
3.4.1. Giới thiệu hệ mã chuẩn. 
 B−ớc sang kỷ nguyên máy tính, việc sử dụng máy tính nhanh 
chóng đ−ợc phổ cập trong mọi hoạt động của con ng−ời, và tất 
nhiên việc dùng máy tính trong truyền tin bảo mật đã đ−ợc hết sức 
chú ý. Các hệ mật mã với các thuật toán lập mật mã và giải mã thực 
hiện bằng máy tính đ−ợc phát triển nhanh chóng, đồng thời các lĩnh 
vực truyền tin cần sử dụng mật mã cũng đ−ợc mở rộng sang nhiều 
địa hạt kinh tế xã hội ngoài các địa hạt truyền thống. Vào đầu thập 
niên 1970, tr−ớc tình hình phát triển đó đã nẩy sinh nhu cầu phải 
chuẩn hoá các giải pháp mật mã đ−ợc sử dụng trong xã hội, để một 
mặt, h−ớng dẫn các thành viên trong xã hội thực hiện quyền truyền 
tin bảo mật hợp pháp của mình, mặt khác, bảo đảm sự quản lý và 
giám sát của nhà n−ơc đối với các hoạt động bảo mật đó. Do đó, tại 
Hoa kỳ, ngày 15/5/1973, Văn phòng quốc gia về Chuẩn (NBS - 
National Bureau of Standards) công bố một yêu cầu công khai xây 
dựng và đề xuất một thuật toán mật mã chuẩn, đáp ứng các đòi hỏi 
chủ yếu là: 
- Thuật toán phải đ−ợc định nghĩa đầy đủ và dễ hiểu; 
 - Thuật toán phải có độ an toàn cao, độ an toàn đó phải không 
phu thuộc vào sự giữ bí mật của bản thân thuật toán, mà chỉ nằm ở 
sự giữ bí mật của khoá; 
 - Thuật toán phải đ−ợc sẵn sàng cung cấp cho mọi ng−ời dùng; 
- Thuật toán phải thích nghi đ−ợc với việc dùng cho các ứng 
dụng khác nhau; 
- Thuật toán phải cài đặt đ−ợc một cách tiết kiệm trong các 
thiết bị điện tử; 
- Thuật toán phải sử dụng đ−ợc có hiệu quả; 
- Thuật toán phải có khả năng đ−ợc hợp thức hoá; 
- Thuật toán phải xuất khẩu đ−ợc. 
 Vào thời điểm NBS đ−a ra yêu cầu nói trên, ch−a có một cơ 
quan nào đề xuất đ−ợc một giải pháp đáp ứng tất cả các đòi hỏi đó. 
Một năm sau, ngày 27/4/1974, yêu cầu đó lại đ−ợc nhắc lại; và lần 
này hãng IBM chấp nhận dự tuyển với sản phẩm sẽ đ−ợc đệ trình là 
một thuật toán cải tiến từ một thuật toán đã đ−ợc phát triển tr−ớc đó 
là LUCIFER. Kết quả là, sản phẩm DES (Data Encryption Standard) 
đ−ợc công bố, lần đầu tiên vào ngày 17/3/1975. Sau nhiều tranh 
luận, cuối cùng DES đ−ợc chấp nhận nh− một chuẩn liên bang vào 
ngày 23/11/1976, và đ−ợc công bố ngày 15/1/1977; đến năm 1980 
lại công bố thêm ôcác cách dùng DESằ, cho phép ng−ời dùng có thể 
sử dụng DES theo nhiều cách khác nhau. Từ đó, DES đ−ợc cài đặt 
sẵn vào các thiết bị cứng thành các máy mã, hoặc đ−ợc cài đặt nh− 
một phần mềm trong các thiết bị tính toán đa dụng, và đã đ−ợc sử 
dụng rộng rãi trong các lĩnh vực quản lý hành chính, kinh tế, th−ơng 
mại, ngân hàng, v.v... không những ở Hoa kỳ mà còn ở nhiều quốc 
gia khác. Theo qui định của NBS, văn phòng quốc gia về chuẩn của 
Hoa kỳ, cứ khoảng 5 năm DES lại phải đ−ợc xem xét lại một lần để 
đ−ợc cải tiến và bổ sung. Sau khi các hệ mật mã có khoá công khai 
đ−ợc phát triển và sử dụng rộng rãi, cũng đã có nhiều ý kiến đề nghị 
thay đổi chuẩn mới cho các hệ mật mã, nh−ng trên thực tế, DES vẫn 
còn đ−ợc sử dụng nh− một chuẩn cho đến ngày nay trong nhiều 
lĩnh vực hoạt động. 
3.4.2. Mô tả hệ mật mã chuẩn DES. 
 Sơ đồ khái quát. D−ới đây ta sẽ trình bày sơ đồ của thuật 
toán lập mật mã DES. Hệ mật mã DES là một hệ mật mã theo khối, 
mỗi khối bản rõ là một từ 64 bit, tức là một phần tử thuộc 642Z , và các 
khối bản mã cũng là các từ 64 bit, nh− vậy P = C = 642Z . DES có tập 
khoá K = 562Z , tức mỗi khoá là một từ 56 bit. Với mỗi khoá K và bản 
rõ x, quá trình lập mật mã diễn ra nh− sau: Thoạt đầu, dùng một 
phép hoán vị ban đầu IP, từ x 64 bit sẽ biến thành một từ mới IP (x ), 
từ này đ−ợc chia thành hai nửa L0 và R0 , mỗi nửa là một từ 32 bit. 
Từ đây, sẽ dùng 15 lần những phép toán giống nhau để liên tiếp 
đ−ợc các cặp (L1,R1 ),...., (L15 ,R15 ), sau đó dùng phép hoán vị nghịch 
 81
 82
đảo IP -1 cho từ đảo ng−ợc R15L15 ta sẽ đ−ợc bản mã y t−ơng ứng. Sơ 
đồ khái quát của phép lập mật mã đ−ợc cho bởi hình vẽ sau đây: 
 K1 
 K2
K16 
 L0 R0 
f
 L1 R1 
f
 L15 R15
f
 R16 L16
+
+
IP -1
Thuật toán 
 G tạo 
 các khoá 
 K1,....., K16
 từ 
 khoá K 
I
+
P
 Bản rõ xKhoá K 
 Bản mã y 
 Sơ đồ khái quát của thuật toán lập mật mã DES 
 Để hoàn chỉnh sơ đồ thuật toán lập mật mã, ta còn phải trình bày 
các thuật toán IP ( và do đó, cả IP -1 ), thuật toán f , và thuật toán G 
tạo ra các khoá K1,...,K16 . 
 IP là một phép hoán vị vị trí của các ký tự trong mỗi từ 64 bit, 
từ vị trí thứ 1 đến vị trí thứ 64. Bảng d−ới đây cho ta phép hoán vị 
IP, với cách hiểu là bit thứ nhất của IP (x ) là bit thứ 58 của từ x (có 
 82
64 bit), bit thứ hai của IP (x) là bit thứ 50 của x, v.v... Bảng của phép 
hoán vị IP -1 cũng đ−ợc hiểu t−ơng tự. 
 IP 
58 50 42 34 26 18 10 2 
60 52 44 36 28 20 12 4 
62 54 46 38 30 22 14 6 
64 56 48 40 32 24 16 8 
57 49 41 33 25 17 9 1 
59 51 43 35 27 19 11 3 
61 53 45 37 29 21 13 5 
63 55 47 39 31 23 15 7 
 IP -1 
40 8 48 16 56 24 64 32 
39 7 47 15 55 23 63 31 
38 6 46 14 54 22 62 30 
37 5 45 13 53 21 61 29 
36 4 44 12 52 20 60 28 
35 3 43 11 51 19 59 27 
34 2 42 10 50 18 58 26 
33 1 41 9 49 17 57 25
Sơ đồ hàm f : Hàm f lấy đầu vào là hai từ : R có 32 bit và K có 48 bit, 
và có kết quả ở đầu ra là từ f (R,K ) có 32 bit, đ−ợc xác định bởi sơ 
đồ sau đây: 
 R (32 bit)
 E (R) 48 bit
E
+
 K (48 bit) 
 Mỗi Bi là một từ 6 bit B1 B2 B3 B4 B5 B6 B7 B8
 Mỗi Ci là một từ 
4 bit 
S
1
S
2
S
3
S
4
S
5
S
6
S
8
S
8
C1 C2 C3 C4 C5 C6 C7 C8
P
 83
 f (R,K ) 32 bit 
Trong sơ đồ ở trên của hàm f , E là một phép hoán vị “mở rộng” 
theo nghĩa là nó biến mỗi từ R 32 bit thành từ E (R ) bằng cách hoán 
vị 32 bit của R nh−ng có một số cặp bit đ−ợc lặp lại để E (R ) thành 
một từ có 48 bit, cụ thể phép hoán vị “mở rộng” đó đ−ợc cho bởi 
bảng sau đây : 
Phép hoán vị “mở rộng” E 
32 1 2 3 4 5 
 4 5 6 7 8 9 
 8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
Theo định nghĩa đó, mỗi từ R = a1a2a3......a32 sè biến thành từ 
 E (R ) = a32 a1a2a3a4a 5a4a 5a6a7a8a9a8a9 .......a32a1 . 
Sau khi thực hiện E, E (R ) sẽ đ−ợc cộng (từng bit theo mod2) với K , 
đ−ợc một từ 48 bit, chia thành 8 đoạn B1, ..., B8 . Mỗi hộp S i (i = 
1,...,8) là một phép thay thế, biến mỗi từ Bj 6 bit thành một từ Cj 4 
bit; các hộp Si đ−ợc cho bởi các bảng d−ới đây với cách hiểu nh− 
sau: mỗi từ Bj = b1b2b3b4b5b6 ứng với một vị trí (r,s) ở hàng thứ r và 
cột thứ s trong bảng, các hàng đ−ợc đánh số từ thứ 0 đến thứ 3 ứng 
với biểu diễn nhị phân b1b6 và các cột đ−ợc đánh số từ thứ 0 đến 
thứ 15 ứng với biểu diễn nhị phân b2b3b4b5 . Giá trị của Si (Bj )= Cj = 
c1c2c3c4 là một từ 4 bit, biểu diễn nhị phân của số tại hàng r cột s 
trong bảng. Thí dụ ta có S1(101110) = 0101, S2(011000) = 1110, v.v... 
 S1
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 
 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 
 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 
 S2
15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 
 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 
 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 
13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 
 S3
10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 
13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 
13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 
 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 
 84
 S4
 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 
13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 
10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 
 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14 
 S5
 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 
14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 
 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 
11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 
 S6
12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 
10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 
 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 
 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 
 S7
 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 
13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 
 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 
 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 
 S8
13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 
 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 
 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 
 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 
Phép hoán vị P trong sơ đồ của hàm f đ−ợc cho bởi bảng ở trang 
sau đây. Nh− vậy, hàm f đã đ−ợc xác định hoàn toàn. Chú ý rằng 
các hộp S1,..., S8 là phần quan trọng nhất trong việc bảo đảm tính bí 
mật của hệ mã DES. 
 P 
16 7 20 21 
29 12 28 17 
 1 15 23 26 
 5 18 31 10 
 2 8 24 14 
32 27 3 9 
19 13 30 6 
22 11 4 25 
 85
Sơ đồ thuật toán G tạo các từ khoá K1,...,K16 : 
 Sơ đồ thuật toán G 
 Khoá K
PC-1
 C0 D0 
LS1 LS1 
 ............................................ ............... .............. 
 K1 PC2 C1 D1 
 K2 PC2 C2 D2 
 K16PC2
LS16
 C16 D16
LS2 
LS16
LS2
Thuật toán G tạo ra các từ khoá K1,...,K16 từ khoá mật mã K đ−ợc 
thực hiện theo sơ đồ thuật toán mô tả ở trên. Khoá mật mã K là một 
từ 56 bit, ta chia thành 8 đoạn, mỗi đoạn 7 bit, ta thêm cho mỗi đoạn 
7 bit đó một bit thử tính chẵn lẻ vào vị trí cuối để đ−ợc một từ 64 
bit, ta vẫn ký hiệu là K , từ mới K này là từ xuất phát cho quá trình 
tính toán của thuật toán G (nh− sẽ thấy về sau, các bit thử tính chẵn 
lẻ mà ta thêm vào chỉ đ−ợc dùng để phát hiện sai trong từng đoạn 
bit của khoá chứ thực tế không tham gia vào chính quá trình tính 
toán của G ). 
 86
 Tr−ớc tiên, thuật toán PC-1 biến K thành một từ 56 bit mà ta 
chia thành hai nửa C0D0 , mỗi nửa có 28 bit. Phép hoán vị PC-1 đ−ợc 
xác định bởi bảng sau đây (chú ý là trong bảng không có các số 
8,16,24,32,40,48,56,64 là vị trí của những bit đ−ợc thêm vào khi hình 
thành từ mới K ). Nhớ rằng theo qui −ớc của phép hoán vị, bit thứ 
nhất của PC-1(x ) là bit thứ 57 của x , bit thứ hai của 
PC-1(x ) là bit thứ 49 của x , v.v... 
 PC-1 
57 49 41 33 25 17 9 
 1 58 50 42 34 26 18 
10 2 59 51 43 35 27 
19 11 3 60 52 44 36 
63 55 47 39 31 23 15 
 7 62 54 46 38 30 22 
14 6 61 53 45 37 29 
21 13 5 28 20 12 4 
Với mỗi i = 1,2,...16, LSi là phép chuyển dịch vòng sang trái, chuyển 
dịch một vị trí nếu i = 1,2,9,16, và chuyển dịch hai vị trí với những 
giá trị i còn lại. 
Cuối cùng, phép hoán vị PC-2 biến mỗi từ 56 bit CiDi (i =1,2,...16) 
thành từ 48 bit Ki theo bảng d−ới đây: 
 PC-2 
14 17 11 24 1 5 
 3 28 15 6 21 10 
23 19 12 4 26 8 
16 7 27 20 13 2 
41 52 31 37 47 55 
30 40 51 45 33 48 
44 49 39 56 34 53 
46 42 50 36 29 32
Nh− vậy, ta đã mô tả đầy đủ quá trình tính toán của thuật toán G 
để từ khoa mã ban đầu K thu đ−ợc các từ khoá K1 ,..., K16 cung cấp 
cho thuật toán f, và từ đó cho toàn bộ thuật toán lập mật mã DES. 
Ta chú ý rằng mỗi Ki có 48 bit đều do hoán vị 56 bit (có bỏ bớt 8 bit) 
của K mà thành, do đó có thể cho trực tiếp bằng cách cho các bảng 
mô tả các phép hoán vị đó. Bạn đọc có thể tìm đọc 16 bảng ứng với 
16 Ki đó trong sách của D.R. Stinson (có trong phần Sách tham 
khảo). 
 Với việc trình bày sơ đồ khái quát cùng với các bảng, các sơ 
đồ của các thuật toán phụ, ta đã hoàn thành việc giới thiệu thuật 
 87
toán lập mật mã E của hệ mật mã DES , cho ta y = E (K,x ) với 
mối khoá K và bản rõ x. 
 Thuật toán giải mã D, cho ta x =D (K ,y ), đ−ợc thực hiện 
bằng cùng một quá trình tính toán nh− quá trình lập mã, chỉ khác là 
thứ tự dùng các Ki đ−ợc đảo ng−ợc lại theo thứ tự K16,K15,...,K1. 
 Có thể thực hiện thử các thuật toán lập mã và giải mã kể trên 
với thí dụ sau đây: Cho K và x là 
 K = 12695BC9B7B7F8 
 x = 0123456789ABCDEF, 
ở đây các số đ−ợc viết theo cơ số 16 (hexadecimal), mỗi ký tự thay 
cho 4 bit. Bản mã y t−ơng ứng sẽ là 
 y = 85E813540F0AB405. 
3.4.3. Các cách dùng DES. 
 Năm 1981, NBS công bố các chuẩn xử lý thông tin liên bang 
có liên quan đến DES, trong đó đã hợp thức hoá bốn cách dùng DES 
trong thực tế là các cách: ECB (electronic codebook mode), CFB 
(cipher feedback mode), CBC ( cipher block chaining mode) và OFB 
(output feedback mode). 
 ECB là cách sử dụng thông th−ờng và đơn giản của DES. Với 
cách sử dụng đó, ta chia bản rõ (là một dãy bit) thành từng khối 64 
bit x = x1x2....xn , và dùng cùng một khoá K để mã các khối đó rồi 
ghép lại để đ−ợc bản mã y = y1y2... yn , trong đó yi = eK (xi ). 
 Với cách dùng CFB, để đ−ợc khối mã yi ta dùng DES cho 
không phải xi mà là cho xi⊕yi -1 ,tức là có yi = eK (xi⊕yi -1) với mọi 
i > 1. 
 Trong hai cách CBC và OFB, ta dùng DES để tạo ra một dòng 
từ khoá z1...zi....., rồi sau đó lập mã yi = xi ⊕ zi (i ≥ 1). Dòng khoá 
z1...zi..... trong cách CBC đ−ợc xác định bởi 
 z0 = K* (là một từ 64 bit đ−ợc chọn từ khoá K), 
 zi = eK (zi -1); 
còn trong cách OFB đ−ợc xác định bởi 
 y0 = K* 
 zi = eK (yi -1) 
 yi = xi ⊕ zi (i ≥1). 
Trong thực tế, các cách ECB và CBC đ−ợc nhiều ngân hàng dùng 
làm chuẩn mật mã của mình, còn các cách CFB và òB th−ờng đ−ợc 
dùng cả với các mục đích xác nhận. 
3.4.4. Về tính an toàn và việc thám mã đối với DES. 
 88
 1.Về tính an toàn bảo mật của DES. Sau khi DES đ−ợc công 
bố nh− một chuẩn chính thức cho truyền tin bảo mật của quốc gia, 
nhiều vấn đề về tính an toàn và khả năng bảo mật của DES đ−ợc 
đặt ra và nhiều biện pháp thám mã cũng đ−ợc nghiên cứu, trong 
suốt hơn hai m−ơi năm qua và cho đến nay. 
Ta chú ý rằng trong cấu trúc của thuật toán DES, ở mỗi vòng 
lặp đều có các phép chuyển dịch và thay thế xen kẽ liên tiếp nhau, 
có tác dụng tăng thêm độ bảo mật của mật mã. Thuật toán DES nói 
chung đáp ứng các yêu cầu mà NBS đề ra từ đầu cho một chuẩn 
mật mã, và do đó yếu tố bảo mật chủ yếu tập trung vào việc giữ bí 
mật của khoá, hay nói cách khác, thám mã chủ yếu phải là phát hiện 
khoá đ−ợc sử dụng. Trong các khâu của sơ đò DES thì các yếu tố 
phi tuyến duy nhất nằm ở các hộp S1,..., S8. Ng−ời ta không biết 
ng−ời thiết kế các hộp đó đã chọ chúng theo những tiêu chuẩn nào, 
và Cục an ninh quốc gia NSA có cài vào đó những “cửa sập” nào 
không; nh−ng sau nhiều cố gắng thám mã không thành công, ng−ời 
ta đã công bố một số các tiêu chuẩn chon các hộp S1,..., S8 nh− sau: 
 1. Mỗi hàng của một hộp Si phải là một hoán vị của 0,1,...,15; 
 2. Không một hộp Si nào là một hàm tuyến tính hay apphin 
đối với các đầu vào của nó; 
 3. Với mỗi hộp Si , việc thay đổi một bit ở đầu vào gây ra sự 
thay đổi ít nhất hai bit ở đầu ra của nó; 
 4. Nếu hai từ vào của một hộp Si giống nhau ở hai bit đầu 
và hai bit cuối, thì hai từ ra phải khác nhau ở hai bit; 
 5. Nếu hai từ vào của một hộp Si khác nhau ở hai bit đầu và 
giống nhau ở hai bit cuối, thì hai từ ra phải khác nhau; 
 6. Với mỗi hộp Si , nếu ta cố định giá trị một bit vào và xét 
giá trị của bit ra ở một vị trí nào đó, thì số các từ vào tạo ra giá trị 0 
và số các từ vào tạo ra giá trị 1 ở cùngvị trí đó phải xấp xỉ bằng 
nhau. 
Nói chung, độ bảo mật của DES đã đ−ợc thử thách qua hơn 
hai m−ơi năm sử dụng và đ−ợc chứng tỏ là tin cậy. Các ph−ơng 
pháp thám mã, tuy đã đ−ợc tìm kiếm khá nhiều, nh−ng gần nh− 
không tránh đ−ợc độ phức tạp của cách tầm th−ờng là duyệt toàn 
bộ, mà theo cách này thì dù là thám mã theo kiểu “biết cả bản rõ” ta 
cũng phải duyệt qua 256 khoá có thể có, điều đó đòi hỏi một l−ợng 
tính toán khổng lồ khó mà khắc phục nổi ! 
Về việc thám mã đối với DES. 
Hệ mã chuẩn DES có thể xem là hệ mã đầu tiên đ−ợc dùng 
phổ biến một cách rộng rãi không chỉ trong một quốc gia mà cả trên 
phạm vi toàn thế giới, toàn bộ cấu trúc thuật toán đ−ợc công bố 
công khai, cả phép lập mã và giải mã, thậm chí các sản phẩm phần 
cứng cũng nh− phần mềm của nó đ−ợc th−ơng mại hoá; do đó bí 
mật của thông tin đ−ợc truyền đi chỉ còn nằm ở chìa khoá đ−ợc 
 89
chon, đó là một từ 56 bit. Việc thám mã đối với DES dã hấp dẫn 
nhiều nhà toán học và chuyên gia mật mã nghiên cứu, đề xuất 
nhiều ph−ơng pháp khác nhau. Ngoài ph−ơng pháp “duyệt toàn 
bộ” nh− nói trên, ng−ời ta đã đề xuất một số ph−ơng pháp khác, 
nh−: 
- ph−ơng pháp phân tích độ chênh lệch (differential analysis) 
do Biham và Shamir đề xuất năm 1990, 
 - ph−ơng pháp phân tích liên quan đến khoá, do Biham đề 
xuất vào khaỏng 1992-1994, 
 - ph−ơng pháp phân tích tuyến tính, do Matsui đ−a ra năm 
1993-1994, 
- ph−ơng pháp phân tích chênh lệch-tuyến tính, do Langfort 
và Hellman đ−a ra năm 1994, 
- v.v... 
Các ph−ơng pháp này đều chứa đựng nhiều ý t−ởng sâu sắc 
và tinh tế, nh−ng vẫn đòi hỏi những khối l−ợng tính toán rất lớn, 
nên trong thực tế vẫn chỉ dừng lại ở những minh hoạ t−ơng đối đơn 
giản chứ ch−a đ−ợc sử dụng thực sự. 
 90

File đính kèm:

  • pdfgiao_trinh_ly_thuyet_mat_ma_va_an_toan_thong_tin_phan_dinh_d.pdf