Giáo trình Bảo mật thông tin

Giáo trình Bảo mật thông tin 
1 
MỤC LỤC 
LỜI NÓI ĐẦU ................................................................................................................. 5 
CHƢƠNG 1: GIỚI THIỆU CHUNG VỀ MẬT MÃ ...................................................... 6 
1.1. Sơ lƣợc về lịch sử mật mã .................................................................................... 6 
1.1.1. Mật mã cổ điển ................................................................................................ 7 
1.1.2. Mật mã hiện đại ............................................................................................... 7 
1.2. Các hệ thống mật mã ............................................................................................ 8 
1.2.1. Sơ đồ hệ thống mật mã .................................................................................... 8 
1.2.2. Yêu cầu của một hệ mật mã ............................................................................ 9 
1.2.3. Mã khối và mã dòng ........................................................................................ 9 
1.3. Mật mã khóa đối xứng và mật mã khóa công khai ............................................ 10 
1.3.1. Hệ mật mã khóa đối xứng ............................................................................. 10 
1.3.2. Hệ mật mã khóa công khai ............................................................................ 11 
1.4. Các bài toán trong an toàn thông tin .................................................................. 12 
1.5. Thám mã và tính an toàn của các hệ mật mã ..................................................... 13 
1.5.1. Vấn đề thám mã ............................................................................................. 13 
1.5.2. Tính an toàn của một hệ mật mã ................................................................... 14 
CHƢƠNG 2: MẬT MÃ CỔ ĐIỂN .............................................................................. 16 
2.1. Giới thiệu ............................................................................................................ 16 
2.2. Cơ sở toán học .................................................................................................... 17 
2.2.1. Tính chia hết của các số nguyên .................................................................... 17 
2.2.2. Thuật toán Euclide và thuật toán Euclid mở rộng ......................................... 18 
2.2.3. Quan hệ đồng dƣ và số học modulo m .......................................................... 21 
2.2.4. Phƣơng trình đồng dƣ .................................................................................... 24 
2.2.5. Các lớp thặng dƣ ........................................................................................... 25 
2.2.6. Hàm Euler ...................................................................................................... 26 
2.3. Một số hệ mật mã đơn giản ................................................................................ 26 
2.3.1. Hệ mật mã dịch chuyển (Shift cipher) .......................................................... 26 
2.3.2. Hệ mật mã thay thế (substitution cipher). ..................................................... 28 
2.3.3. Hệ mật mã Affine .......................................................................................... 29 
2.3.4. Hệ mật mã Vigenere ...................................................................................... 31 
2.3.5. Hệ mật mã Hill .............................................................................................. 32 
2.3.6. Hệ mật mã hoán vị......................................................................................... 36 
Giáo trình Bảo mật thông tin 
2 
2.3.7. Các hệ mật mã dòng ...................................................................................... 37 
2.4. Mã thám các hệ mật mã cổ điển......................................................................... 40 
2.4.1. Thám hệ mật mã Affine ................................................................................ 42 
2.4.2. Thám hệ mật mã thay thế .............................................................................. 43 
2.4.3. Tấn công với bản rõ đã biết trên hệ mật mã Hill. ......................................... 45 
2.4.4. Thám mã đối với hệ mật mã Vigenère. ......................................................... 46 
2.4.5. Thám mã hệ mã dòng xây dựng trên LFSR .................................................. 51 
BÀI TẬP ........................................................................................................................ 54 
CHƢƠNG 3: CHUẨN MÃ DỮ LIỆU .......................................................................... 58 
3.1. Giới thiệu hệ mật mã chuẩn ............................................................................... 58 
3.2. Hệ mật mã DES ................................................................................................. 59 
3.2.1. Mô tả DES ..................................................................................................... 59 
3.2.2. Cách hoán vị bit ............................................................................................ 61 
3.2.3. Cách tính bảng khoá từ khoá ban đầu K ....................................................... 62 
3.2.4. Cách tính hàm f (Feistel Function) ............................................................... 67 
3.2.5. DES trong thực tế .......................................................................................... 76 
3.2.6. Phép tối ƣu hoá thời gian - bộ nhớ ................................................................ 76 
3.2.7. Độ an toàn và việc thám mã đối với DES ..................................................... 79 
3.3. Hệ mật IDEA ..................................................................................................... 82 
3.3.1. Khái quát chung về hệ mật IDE ...  tạp nhỏ hơn tấn công duyệt 
toàn bộ. Tuy nhiên các phƣơng pháp này đòi hỏi một số lƣợng bản rõ quá lớn (để tấn 
công lựa chọn bản rõ) nên hầu nhƣ không thể thực hiện đƣợc trong thực tế. 
a. Tấn công kiểu duyệt toàn bộ 
Giáo trình Bảo mật thông tin 
80 
Đối với bất cứ phƣơng pháp mã hoá nào, kiểu tấn công cơ bản và đơn giản nhất 
là tấn công kiểu duyệt toàn bộ: thử lần lƣợt tất cả các khoá có thể cho đến khi tìm ta 
khoá đúng. Độ dài của khoá sẽ xác định số lƣợng phép thử tối đa cần thực hiện và do 
đó thể hiện tính khả thi của phƣơng pháp. Trong trƣờng hợp của DES, nghi ngờ về độ 
an toàn của nó đã đƣợc đặt ra ngay từ khi nó chƣa trở thành tiêu chuẩn. Ngƣời ta cho 
rằng chính NSA đã ủng hộ (nếu không muốn nói là thuyết phục) IBM giảm độ dài 
khoá từ 128 bít xuống 64 bít và tiếp tục xuống 56 bít. Điều này dẫn đến suy đoán rằng 
NSA đã có hệ thống tính toán đủ mạnh để phá vỡ khoá 56 bít ngay từ những năm 
1970. 
Trong giới nghiên cứu, nhiều đề xuất về các hệ thống phá mã DES đƣợc đề ra. 
Năm 1977, Diffie và Hellman dự thảo một hệ thống có giá trị khoảng 20 triệu đô la 
Mỹ và có khả năng phá khoá DES trong 1 ngày. Năm 1993, Wiener dự thảo một hệ 
thống khác có khả năng phá mã trong vòng 7 giờ với giá 1 triệu đô la Mỹ. Những điểm 
yếu của DES đƣợc thực sự chứng minh vào cuối những năm 1990. Vào năm 1997, 
công ty bảo mật RSA đã tài trợ một chuỗi cuộc thi với giải thƣởng 10.000 đô la Mỹ 
cho đội đầu tiên phá mã đƣợc một bản tin mã hoá bằng DES. Đội chiến thắng trong 
cuộc thi này là dự án DESCHALL với những ngƣời dẫn đầu bao gồm Rocke Verser, 
Matt Curtin và Justin Dolske. Họ đã sử dụng hàng nghìn máy tính nối mạng để phá 
mã. Khả năng phá mã DES đƣợc chứng minh thêm lần nữa vào năm 1998 khi tổ chức 
Electronic Frontier Foundation(EEF), một tổ chức hoạt động cho quyền công dân trên 
Internet, xây dựng một hệ thống chuyên biệt để phá mã với giá thành 250000 đô la 
Mỹ. Động cơ thúc đẩy EEF trong hành động này là nhằm chứng minh DES có thể bị 
phá vỡ trên lý thuyết cũng nhƣ trên thực tế: “ Nhiều ngƣời không tin vào chân lý cho 
đến khi họ nhìn thấy sự việc bằng chính mắt mình. Xây dựng một bộ máy có thể phá 
khoá DES trong vòng vài ngày là cách duy nhất chứng tỏ với mọi ngƣời rằng họ không 
thể đảm bảo an ninh thông tin dựa vào DES”. Hệ thống này đã tìm đƣợc khoá DES 
bằng phƣơng pháp duyệt toàn bộ trong thời gian hơn 2 ngày; 
b. Các kiểu tấn công khác hiệu quả hơn duyệt toàn bộ 
Hiện nay có 3 kiểu tấn công có khả năng phá vỡ DES (với đủ 16 chu trình) với độ 
phức tạp thấp hơn duyệt toàn bộ: phá mã vi sai (differential cryptanalysis - DC), phá 
Giáo trình Bảo mật thông tin 
81 
mã tuyến tính (linear cryptanalysis - LC) và phá mã Davies (Davies' attack). Tuy 
nhiên các dạng tấn công này chƣa thực hiện đƣợc trong thực tế. 
Phá mã vi sai đƣợc Eli Biham và Adi Shamir tìm ra vào cuối những năm 1980 
mặc dù nó đã đƣợc IBM và NSA biết đến trƣớc đó. Để phá mã DES với đủ 16 chu 
trình, phá mã vi sai cần đến 247 văn bản rõ. DES đã đƣợc thiết kế để chống lại tấn công 
dạng này. 
Phá mã tuyến tính đƣợc tìm ra bởi Mitsuru Matsui và nó đòi hỏi 243 văn bản rõ. 
Phƣơng pháp này đã đƣợc Matsui thực hiện và là thực nghiệm phá mã đầu tiên đƣợc 
công bố. Không có bằng chứng chứng tỏ DES có khả năng chống lại tấn công dạng 
này. Một phƣơng pháp tổng quát hơn, phá mã tuyến tính đa chiều (multiple linear 
cryptanalysis) đƣợc Kaliski và Robshaw nêu ra vào năm 1994, Biryukov và cộng sự 
tiếp tục cải tiến vào năm 2004. Nghiên cứu của họ cho thấy mô phỏng tuyến tính đa 
chiều có thể sử dụng để giảm độ phức tạp của quá trình phá mã tới 4 lần (chỉ còn 241 
văn bản rõ). Kết quả tƣơng tự cũng có thể đạt đƣợc với kiểu tấn công tuyến tính kết 
hợp với lựa chọn bản rõ (Knudsen and Mathiassen, 2000). Junod (2001) đã thực hiện 
một số thực nghiệm để tìm ra độ phức tạp thực tế của phá mã tuyến tính và thấy rằng 
quá trình thực tế nhanh hơn dự đoán: 239x241. 
Phá mã Davies: trong khi phá mã vi sai và phá mã tuyến tính là các kỹ thuật phá 
mã tổng quát, có thể áp dụng cho các thuật toán khác nhau, phá mã Davies là một kỹ 
thuật dành riêng cho DES. Dạng tấn công này đƣợc đề xuất lần đầu bởi Davies vào 
cuối những năm 1980 và cải tiến bởi Biham và Biryukov (1997). Dạng tấn công mạnh 
nhất đòi hỏi 250 văn bản rõ, độ phức tạp là 250 và có tỷ lệ thành công là 51%. 
Ngoài ra còn có những kiểu tấn công dựa trên bản thu gọn của DES - DES với ít 
hơn 16 chu trình. Những nghiên cứu này cho chúng ta biết số lƣợng chu trình cần có 
và ranh giới an toàn của hệ thống. Năm 1994, Langford và Hellman đề xuất phá mã vi 
sai - tuyến tính (differential-linear cryptanalysis) kết hợp giữa phá mã vi sai và tuyến 
tính. Một dạng cải tiến của phƣơng pháp này có thể phá vỡ DES 9 chu trình với 215.8 
văn bản rõ và có độ phức tạp là 229.2 
Giáo trình Bảo mật thông tin 
82 
3.3. Hệ mật IDEA 
3.3.1. Khái quát chung về hệ mật IDEA 
IDEA (International Data Encryption Algorithm) đƣợc công bố lần đầu tiên năm 
1991 bởi Lai Học Gia và James L.Massey của ETH Zurich. Tiền thân của IDEA là 
PES (Proposed Encryption Standard). Ban đầu IDEA còn có tên là IPES (Improved 
PES), đƣợc đƣa ra nhƣ là sự thay thế DES (Data Encryption Standard). Ngày nay, 
IDEA thuộc quyền sở hữu của MediaCrypt. IDEA đƣợc sử dụng trong Pretty Good 
Privacy (PGP) V2.0, một công cụ mã hóa thƣờng đƣợc dùng trong các chƣơng trình e-
mail. 
IDEA là phƣơng pháp mã khối sử dụng 128 bits khoá để mã hoá khối dữ liệu 64 
bits. IDEA đã từng đƣợc thừa nhận và xem nhƣ một sự chọn lựa tốt hơn cả DES (Data 
Encrytion Standard) với tốc độ hóa cao, hiện thực trên các chip có thể mã hóa ở tốc độ 
177 Mbits/sec. Giải thuật đƣợc phép sử dụng tự do, không đòi hỏi bản quyền, đƣợc 
xem là phù hợp cho thƣơng mại điện tử và có thể áp dụng cho toàn thế giới. 
3.3.2. Một số phép toán 
a. Phép loại bit XOR 
Đây là phép toán thực hiện trên các bit. Nguyên tắc thực hiện của phép XOR 
chính là việc thực hiện phép cộng không nhớ trên số nhị phân. 
 Ví dụ: 10101010 
 XOR 11100011 
 01001001 
b. Phép toán cộng  
(A+B) Mod 2
16
 (65536): trả về phần dƣ của phép chia tổng (A+B) cho 216. 
Ví dụ: (23457 + 61245) Mod 216 = 84702 mod 2 16 = 29166 
c. Phép toán cộng nghịch đảo mod 216: 
Trả về giá trị là một số mà sau khi cộng cho tổng của 2 số ban đầu thì chia hết 
cho 2
16
[(23457 + 61245) Mod 2
16
]
-1
 = [84702 mod 2 
16
 ]
-1
= (65536-29166) Mod 2
16
 = 36370 
Giáo trình Bảo mật thông tin 
83 
d. Phép toán nhân mod 2
16
 + 1: 
Kết quả trả về phần dƣ của phép chia tích (A*B) cho 216 + 1. 
[(23457 * 61245) Mod (2
16
 + 1)] 
= [1436623965 mod (2
16
 + 1)]
 = 52925 
e. Phép toán nhân nghịch đảo mod (216 + 1): 
 A*B Mod (2
16
 + 1) = C 
Thì [A*B Mod (2
16
 + 1)]
-1
 = C‟ mà (C*C‟) Mod (216 + 1) =1. 
3.3.3. Mô tả thuật toán IDEA 
a. Tổng quan về thuật toán 
1. IDEA là hệ mã thao tác trên từng khối 64bit, mã khối 64bit plantext thành khối 
64bit ciphertext, sử dụng 52 khoá con (đƣợc sinh ra từ 1 khóa ban đầu có độ dài 
128bits). Mỗi khối dữ liệu thực hiện qua 8 lần biến đổi (vòng) liên tiếp và 1 lần 
biến đổi đầu ra. 
2. Mỗi khoá con có độ dài 16 bits. 
3. Mỗi khối dữ liệu có độ dài 64 bits và đƣợc chia thành 4 phần (mỗi phần 16 bit). 
4. Lần biến đổi thứ r (1<= r <=8) sử dụng 6 khối khóa con 16 bit Ki(r), 1<= i <=6, 
để biến đổi 64bit đầu vào X thành 1 đầu ra với 4 khối 16bit và đầu ra này lại là 
đầu vào cho lần biến đổi tiếp theo. Tại mỗi vòng, IDEA sử dụng 6 khoá con 
(16bits) để biến đổi 64 bits đầu vào X thành 1 đầu ra với 4 khối 16bits và đầu ra 
này lại là đầu vào cho lần biến đổi tiếp theo. (4 khoá dùng để chỉnh dữ liệu 
trƣớc khi vào vòng, 2 khoá dùng cho việc biến đổi bên trong của từng vòng). 
5. Đầu ra của vòng 8 là đầu vào cho lần biến đổi cuối cùng là đầu ra khối 64bits. 
Tại lần biến đổi này, IDEA dùng 4 khóa con Ki(9), 1<= i <=4, để tính toán mật 
mã cuối cùng Y= (Y1,Y2, Y3, Y4). 
6. IDEA sử dụng các phép toán: loại bit (XOR), cộng ( ) và nhân ( ). Phép 
cộng ở thuật toán này là phép cộng thông thƣờng theo modulo 65536216 , 
phép nhân cũng là phép nhân thông thƣờng theo modulo 655371216 với quy 
ƣớc 162 biểu diễn là 0. 
Thuật toán đƣợc mô tả nhƣ sau: 
Giáo trình Bảo mật thông tin 
84 
Tổng quan Chi tiết 
b. Sinh khoá lập mã 
1. Khóa 128 bits ban đầu (chìa gốc) đƣợc chia thành 8 khoá con đầu tiên, mỗi 
khoá 16 bits, 1K ... 8K . 
2. Xoay trái khoá ban đầu 25 bits, phân chia thành 8 phần để đƣợc 8 khoá con tiếp 
theo K9...K16 
3. Tiếp tục xoay trái 25 bits, phân chia thành 8 phần để đƣợc các khoá tiếp theo 
(mỗi lần xoay trái đƣợc 1 bộ 8 khoá) cho đến khi đủ 52 khoá 
K1... K52 đƣợc gọi là khoá con lập mã. 
Giáo trình Bảo mật thông tin 
85 
Ví dụ: 
Với khoá K ban đầu: aq014236, ta có bảng khoá lập mã nhƣ sau: 
Vòng K[1] K[2] K[3] K[4] K[5] K[6] 
1 97 113 48 49 52 50 
2 51 54 57856 24576 25088 26624 
3 25600 26112 27648 49664 196 208 
4 200 204 216 388 452 192 
5 40961 36865 38913 45059 2051 34817 
6 32769 34817 816 864 1552 1808 
7 768 784 832 800 49164 8206 
8 8198 6 8198 32774 16390 24582 
9 7232 3072 3136 3328 
Bảng sinh khóa lập mã 
c. Mã hoá 
Khối dữ liệu 64bits đƣợc phân chia thành 4 phần: A, B, C, D 
Mỗi khối dữ liệu đƣợc thực hiện qua 8 lần biến đổi (vòng) liên tiếp và 1 lần biến đổi 
đầu ra. Tại mỗi vòng, sử dụng 6 khoá con 16bits (4 khoá dùng để chỉnh dữ liệu, 2 khoá 
dùng cho việc biến đổi bên trong). Việc mã hoá đƣợc tiến hành nhƣ sau 
Vòng 1 
1. Chỉnh trang dữ liệu (sử dụng 4 khoá), bƣớc này đƣợc thực hiện bằng cách cho 
từng phần dữ liệu kết hợp với chìa khóa con thông qua phép cộng hoặc phép 
nhân. 
- Nhân A với 1K : 1KA . 
- Cộng 2K vào B: BK 2 . 
- Cộng 3K vào C: CK 3 . 
- Nhân D với 4K : 4KD . 
2. Biến đổi dữ liệu (2 khoá): 
a. CxorAE ; DxorBF . 
b. Nhân E với 5K để đƣợc E mới rồi cộng với F. 
c. Nhân F với 6K để đƣợc F mới rồi cộng với E. 
d. Lấy giá trị của F đem loại bit với A và C để đƣợc A mới và C mới. 
Tƣơng tự, lấy E loại bit với B, D để có đƣợc B mới và D mới. 
Giáo trình Bảo mật thông tin 
86 
e. Tráo đổi vị trí giữa B và C. 
Vòng 2-8: 
Làm tƣơng tự nhƣ vòng 1 với A, B, C, D là kết quả thu đƣợc ở vòng trƣớc đó. Đến 
đây, đã có 48 khoá tham gia vào các vòng. 
ở vòng 8, không thực hiện việc tráo đổi B và C. 
Sử dụng 4 khoá còn lại và kết quả khối A, B, C, D thu đƣợc sau vòng 8 để thực 
hiện biến đổi đƣa ra kết quả: 
Nhân A với 49K : 49KA . 
Cộng 50K vào B: BK 50 . 
Cộng 51K vào C: CK 51 . 
Nhân D với 52K : 52KD 
Với khối dữ liệu đầu vào là abcd4, quá trình mã khoá đƣợc phân bổ qua bảng nhƣ sau: 
Vòng X[1] X[2] X[3] X[4] 
1 35901 43119 2382 105 
2 15384 10074 44288 23164 
3 55904 35815 29535 19818 
4 3299 57986 62694 11366 
5 12258 18387 64006 3625 
6 50189 11978 60169 61164 
7 10329 58020 35161 9749 
8 54176 30709 11578 40675 
 Kết quả mã hoá trung gian 
Kết quả mã hoá đƣợc khối dữ liệu 64bits: 20646 14650 33845 32495 
d. Giải mã 
Quy trình giải mã hoàn toàn tƣơng tự với quy trình lập mã, khoá giải mã đƣợc 
sinh ra từ khoá lập mã bằng cách sử dụng các phép toán nghịch đảo của phép cộng 
hoặc phép nhân. Quy ƣớc, zero cũng có nghịch đảo với phép nhân là chính nó. 
Sinh khoá giải mã 
Các khoá giải mã đƣợc sinh ra từ các khoá lập mã. 
Quá trình sinh khoá giải mã đƣợc tiến hành nhƣ sau: 
1. Sinh 6 khoá đầu tiên: 
491 /1 KKD 
Giáo trình Bảo mật thông tin 
87 
502 KKD 
513 KKD 
524 /1 KKD 
475 KKD 
486 KKD 
2. Các khoá con khác đƣợc sinh bằng cách thêm 6 vào chỉ số của khoá con giải mã 
và bớt 6 từ chỉ số của chìa con lập mã, ví dụ: 
437 /1 KKD 
448 KKD 
459 KKD 
4610 /1 KKD 
Nhƣ vậy, với khoá k ban đầu, sinh đƣợc khoá giải mã nhƣ sau: 
DK1 
42329 
DK2 
62464 
DK3 
62400 
DK4 
60476 
DK5 
16390 
DK6 
24582 
DK7 
9761 
DK8 
57338 
DK9 
65530 
DK10 
11916 
DK11 
49164 
DK12 
8206 
... ... ... ... ... ... 
DK49 
41214 
DK50 
65423 
DK51 
65488 
DK52 
2675 
Bảng khoá giải mã 
Giải mã 
Với khối dữ liệu đã đƣợc mã hoá, quá trình giải mã đƣợc mô tả qua bảng sau: 
Vòng Y[1] Y[2] Y[3] Y[4] 
1 3338 43359 58026 20851 
2 9396 61001 12762 40598 
3 6129 64822 53204 51761 
4 58582 36071 29315 34476 
5 39510 29751 36019 21555 
6 18567 6400 36019 21555 
7 61452 60238 43173 24537 
8 9409 147 211 2548 
Bảng quá trình giải mã 
Giáo trình Bảo mật thông tin 
88 
Kết quả giải mã đƣợc khối dữ liệu đầu vào abc4 
3.3.4. Những đặc tính quan trọng 
a. Độ an toàn của IDEA 
Độ dài của khóa 128 bit (gấp đôi so với DES) làm cho IDEA an toàn hơn nhiều so 
với DES. Để tấn công bằng phép duyệt toàn bộ, ngƣời ta cần thực hiện 2128(1038) lần 
lập mã. 
Gần đây, ngƣời ta đã chỉ ra một số chìa khóa yếu của IDEA. Tuy nhiên, nếu dùng 
giải pháp sinh khóa ngẫu nhiên thì xác suất sinh khóa yếu là rất bé (2-96). 
b. Các modes hoạt động và các biến thể của IDEA 
Để chống lại các kiểu tấn công hay hệ thống song song, có thể dùng mô hình kép 
(double IDEA) hay mô hình bội ba (triple IDEA) : C = EK1(DK2(EK1(P))) 
Vì các khoá con có dáng vẻ độc lập, nên ngƣời ta có thể dùng các khoá con độc lập 
cho 52 khoá, do đó, thuật toán có khoá dài 832 bits. 
c. Khả năng mở rộng độ dài khối lên 128 bít 
 Ngƣời ta đã mở rộng thuật toán IDEA cho trƣờng hợp độ dài khối là 128 bít với 
thuật toán có tên là MMB (Modulo Multiplication-base Block Cipher), trong đó thay 
phép loại 16 bít thành phép loại 32 bít, phép nhân modulo 216+1 thay bằng phép nhân 
modulo 2
32
-1, thuật toán làm việc trên các khối con có độ dài 32 bít do đó khá thuận 
tiện trong việc triển khai trên các máy 32-bít hiện nay. Tuy nhiên thuật toán này vẫn 
chƣa trải qua nhiều thử nghiệm, kiểm định. 
d. Tốc độ và khả năng ứng dụng của IDEA 
Dƣới dạng phần mềm thì tốc độ của IDEA tƣơng đƣơng với DES. Do tính bảo 
mật cao và tốc độ xử lý nhanh, IDEA đang là thuật toán mã hóa khóa đối xứng đƣợc 
ƣu chuộng. Cũng vì thế mà IDEA cũng đã trải qua nhiều cuộc tấn công không khoan 
nhƣợng từ phía các nhà thám mã.