Giáo trình Bảo mật thông tin (Phần 1)

tiền tính toán dễ dàng thấy là cỡ O(N). 
 Việc phân tích thời gian chạy của thuật toán có khó hơn hơn một chút: Trƣớc 
hết ta thấy rằng, bƣớc 3 có thể chạy trong một thời gian không đổi (sử dụng phép mã 
hash) hoặc trong trƣờng hợp xấu nhất, bƣớc 3 có thể chạy với thời gian O(logm) khi 
dùng phép tìm kiếm nhị phân. Nếu bƣớc 3 không thoả mãn (tức là phép tìm kiếm 
không thành công) thì thời gian chạy là O(N2/3). Các phân tích chi tiết hơn chứng tỏ 
rằng, ngay cả khi tính cả thời gian chạy của các bƣớc 4 và5 thì thời gian chạy trung 
bình chỉ tăng một lƣợng là hằng số. 
 3.2.7. Độ an toàn và việc thám mã đối với DES 
 Mặc dù đã có nhiều nghiên cứu về phá mã DES hơn bất kỳ phƣơng pháp mã 
hoá khối nào khác nhƣng phƣơng pháp phá mã thực tế nhất hiện nay vẫn là tấn công 
kiểu duyệt toàn bộ. Nhiều đặc tính mật mã hoá của DES đã đƣợc xác định và từ đó ba 
phƣơng pháp phá mã khác đƣợc xác định với mức độ phức 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ộ 
 79 
Giáo trình Bảo mật thông tin 
 Đố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á 
 80 
 Giáo trình Bảo mật thông tin 
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 
 81 
Giáo trình Bảo mật thông tin 
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 216 (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 216 
 [(23457 + 61245) Mod 216]-1 = [84702 mod 2 16 ]-1 
 = (65536-29166) Mod 216 = 36370 
 82 
 Giáo trình Bảo mật thông tin 
d. Phép toán nhân mod 216 + 1: 
 Kết quả trả về phần dƣ của phép chia tích (A*B) cho 216 + 1. 
 16
 [(23457 * 61245) Mod (2 + 1)] 
 16 
 = [1436623965 mod (2 + 1)] = 52925 
e. Phép toán nhân nghịch đảo mod (216 + 1): 
 A*B Mod (216 + 1) = C 
Thì [A*B Mod (216 + 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 216 65536 , 
 phép nhân cũng là phép nhân thông thƣờng theo modulo 216 1 65537 với quy 
 ƣớc 216 biểu diễn là 0. 
 Thuật toán đƣợc mô tả nhƣ sau: 
 83 
Giáo trình Bảo mật thông tin 
 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, K1 ... K8 . 
 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ã. 
 84 
 Giáo trình Bảo mật thông tin 
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 K1 : A K1 . 
 - Cộng K2 vào B: K2  B . 
 - Cộng K3 vào C: K3  C . 
 - Nhân D với K4 : D  K4 . 
 2. Biến đổi dữ liệu (2 khoá): 
 a. E A xor C ; F B xor D . 
 b. Nhân E với K5 để đƣợc E mới rồi cộng với F. 
 c. Nhân F với K6 để đƣợ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. 
 85 
Giáo trình Bảo mật thông tin 
 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 K49 : A K49. 
 Cộng K50 vào B: K50  B . 
 Cộng K51 vào C: K51  C . 
 Nhân D với K52 : D  K52 
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: 
 KD1 1/ K49 
 86 
 Giáo trình Bảo mật thông tin 
 KD2 K50 
 KD3 K51 
 KD4 1/ K52 
 KD5 K47 
 KD6 K48 
 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ụ: 
 KD7 1/ K43 
 KD8 K44 
 KD9 K45 
 KD10 1/ K46 
Nhƣ vậy, với khoá k ban đầu, sinh đƣợc khoá giải mã nhƣ sau: 
 DK1 DK2 DK3 DK4 DK5 DK6 
 42329 62464 62400 60476 16390 24582 
 DK7 DK8 DK9 DK10 DK11 DK12 
 9761 57338 65530 11916 49164 8206 
 ... ... ... ... ... ... 
 DK49 DK50 DK51 DK52 
 41214 65423 65488 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ã 
 87 
Giáo trình Bảo mật thông tin 
 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 232-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ã. 
 88