MỤC LỤC
Trang phụ bìa .....................................................................................................................
Lời cam đoan .................................................................................................................... i
Lời cảm ơn .......................................................................................................................ii
Mục lục .......................................................................................................................... iii
Danh mục các từ viết tắt tiếng Anh ................................................................................ vi
Danh mục các bảng .......................................................................................................vii
Danh mục các hình vẽ, đồ thị ...................................................................................... viii
MỞ ĐẦU ........................................................................................................................ 1
Chƣơng I. GIỚI THIỆU VỀ CHUẨN MÃ HÓA DỮ LIỆU DES (DATA
ENCRYPTION STANDARD) ....................................................................................... 3
1.1. Giới thiệu về Thuật toán mã hoá DES .................................................................. 3
1.2. Quy trình mã hóa theo DES .................................................................................. 4
1.3. Lập mã và giải mã DES.......................................................................................... 4
1.3.1. Quy trình lập mã DES ....................................................................................... 4
1.3.2. Thực hiện mã hóa DES theo sơ đồ.................................................................... 6
1.3.3. Tính các khóa con k1, k2, ..., k16 từ khóa gốc K ................................................ 7
1.3.4. Tính hàm f(Ri-1, ki) ............................................................................................ 9
1.3.5. Quy trình giải mã DES .................................................................................... 12
1.3.6. Độ an toàn của Chuẩn mã hóa dữ liệu DES .................................................... 12
1.4. Các chế độ mã hóa của DES ................................................................................ 13
1.4.1. Chế độ bản mã cơ bản (EBC) ......................................................................... 13
1.4.2. Chế độ liên kết khối mã (CBC) ....................................................................... 14
Chƣơng II. CÁC PHƢƠNG PHÁP THÁM MÃ CHUẨN MÃ HÓA DỮ LIỆU DES,
CÁC HỆ THỐNG CHUYÊN DỤNG PHỤC VỤ THÁM MÃ DES ............................ 15
2.1. Một số khái niệm cơ bản ...................................................................................... 15
2.2. Các phƣơng pháp thám mã ................................................................................. 16
2.2.1. Thám mã đƣờng tắt ......................................................................................... 16
2.2.1.1. Thám mã vi sai......................................................................................... 16
iii
2.2.1.2. Thám mã tuyến tính ................................................................................. 19
2.2.1.3. Thám mã phi tuyến .................................................................................. 19
2.2.1.4. Thám mã vi sai tuyến tính ....................................................................... 20
2.2.1.5. Một số phƣơng pháp thám mã đƣờng tắt khác ........................................ 20
2.2.2. Thám mã hộp đen (vét cạn để tìm khóa) ......................................................... 20
2.3. Các hệ thống chuyên dụng phục vụ thám mã .................................................... 21
2.3.1. Các phần cứng chuyên dụng ........................................................................... 21
2.3.2. Các hệ thống tính toán hiệu năng cao ............................................................. 22
Chƣơng III. NGHIÊN CỨU, ĐỀ XUẤT PHƢƠNG PHÁP THÁM MÃ DES............. 24
3.1. Mô tả bài toán thám mã DES .............................................................................. 24
3.1.1. Các giả thiết của bài toán ................................................................................ 24
3.1.2. Chi tiết hóa bài toán và các yếu tố đầu vào..................................................... 24
3.2. Xây dựng thuật toán nhận dạng bản rõ tiếng Anh ........................................... 25
3.2.1. Vai trò của nhận dạng bản rõ tự động trong thám mã “vét cạn” ................... 26
3.2.2. Một số phƣơng pháp nhận dạng bản rõ tự động ............................................. 26
3.2.2.1. Nhận dạng dựa vào từ điển ...................................................................... 26
3.2.2.2. Nhận dạng dựa trên tập hợp từ, cụm từ giả định ..................................... 27
3.2.2.3. Nhận dạng dựa vào phƣơng pháp thống kê đặc trƣng ngôn ngữ ............. 27
3.2.3. Xây dựng thuật toán nhận dạng bản rõ dựa vào phƣơng pháp thống kê đặc
trƣng ngôn ngữ .......................................................................................................... 28
3.2.3.1. Một số khái niệm cơ sở về “bản rõ” ........................................................ 28
3.2.3.2. Thuật toán nhận dạng bản rõ ................................................................... 29
3.3. Tìm hiểu thuật toán di truyền (GAs) .................................................................. 36
3.3.1. Giới thiệu......................................................................................................... 36
3.3.2. Thuật toán di truyền nhị phân ......................................................................... 36
3.3.2.1. Thuật toán di truyền nhị phân - sự chọn lọc tự nhiên trên máy tính ....... 36
3.3.2.2. Các thành phần của thuật toán di truyền nhị phân ................................... 37
3.4. Đề xuất phƣơng pháp thám mã DES .................................................................. 46
3.4.1. Xây dựng thuật toán di truyền dò tìm khóa .................................................... 46
3.4.1.1. Xác định hàm phù hợp (hàm chi phí) ...................................................... 47
iv
3.4.1.2. Tạo lập họ khóa khởi tạo ......................................................................... 48
3.4.1.3. Giải mã bản mã cho trƣớc với các khóa trong họ .................................... 49
3.4.1.4. Tính mức độ phù hợp của các khóa ......................................................... 50
3.4.1.5. Chọn lọc ................................................................................................... 50
3.4.1.6. Ghép cặp .................................................................................................. 50
3.4.1.7. Kết hợp..................................................................................................... 51
3.4.1.8. Đột biến.................................................................................................... 51
3.4.1.9. Thế hệ tiếp theo ....................................................................................... 52
3.4.1.10. Kiểm tra hội tụ ....................................................................................... 53
3.4.2. Vai trò của hệ thống tính toán song song ........................................................ 53
3.4.3. Ƣớc lƣợng thời gian, độ phức tạp của tính toán ............................................. 56
KẾT LUẬN ................................................................................................................... 58
TÀI LIỆU THAM KHẢO ............................................................................................. 59
PHỤ LỤC 1. Bảng trọng số tần suất bộ đôi chữ cái tiếng Anh..................................... 60
PHỤ LỤC 2. Mã nguồn chƣơng trình thám mã DES áp dụng thuật toán di truyền chạy
trên máy tính đơn ........................................................................................................... 61
v
DANH MỤC CÁC TỪ VIẾT TẮT TIẾNG ANH
Viết tắt
DES
Viết đầy đủ
Nghĩa tiếng Việt
Data Encryption Standard
Chuẩn mã hoá dữ liệu
Fast Data Encipherment Algorithm
Thuật toán mã hóa dữ liệu nhanh
AES
Advanced Encryption Standard
Chuẩn mã hoá tiến bộ
IDEA
International
Algorithm
3 DES
Triple Data Encryption Standard
Một phiên bản mới của DES
GA
Genetic Algorithm
Thuật toán di truyền
ECB
Electronic Codebook
Chế độ mã hoá cơ bản
CBC
Cipher Block Chaining
Chế độ mã hoá liên kết khối mã
FEAL
Data
Encryption Thuật toán mã hoá dữ liệu quốc tế
vi
DANH MỤC CÁC BẢNG
Số hiệu
Tên bảng
Trang
Bảng 2.1
Tổng hợp về khả năng tấn công thám mã vi sai đối với
DES
18
Bảng 3.1
Ví dụ về trình diễn mã hóa nhị phân
39
Bảng 3.2
Ví dụ về tiến trình ghép cặp và giao phối theo hình thức
lai ghép điểm đơn
43
Bảng 3.3
Tính toán mức độ phù hợp của các khoá trong một thế hệ
50
vii
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Số hiệu
Tên hình vẽ, đồ thị
Trang
Hình 1.1
Mô phỏng sự mã hoá (a) và giải mã (b) theo DES
3
Hình 1.2
Sơ đồ quy trình lập mã DES
5
Hình 1.3
Sơ đồ quy trình tính các khóa con k1, k2, ..., k16
7
Hình 1.4
Sơ đồ quy trình tính hàm f (Ri-1, ki)
9
Hình 1.5
Mã hóa và giải mã theo chế độ mã hóa cơ bản (EBC)
13
Hình 1.6
Mã hóa và giải mã theo chế độ liên kết khối mã (CBC)
14
Hình 2.1
So sánh mức an toàn giữa DES và AES dƣới góc độ thám
mã vi sai
19
Hình 3.1
Mô tả giả thiết và bài toán thám mã DES
24
Hình 3.2
So sánh thám mã dựa trên nhận dạng bản rõ thủ công
và nhận dạng bản rõ tự động
25
Hình 3.3
Mô phỏng về xác suất chuyển giữa hai chữ cái liền kề trong
chữ viết tiếng Anh
28
Hình 3.4
Sự tƣơng tự giữa thuật toán di truyền và di truyền sinh
học
36
Hình 3.5
Biểu đồ luồng của thuật toán di truyền nhị phân
37
Hình 3.6
Biểu diễn giao phối với hình thức lai ghép điểm đơn
42
Hình 3.7
Quy trình thám mã dựa trên thuật toán di truyền
46
Hình 3.8
Quy trình tạo lập tập khóa khởi tạo P (Npop) gồm 100
khóa
49
Hình 3.9
Mức độ tăng tốc theo lý thuyết của GA với Npop = 100
54
Hình 3.10
Mô hình của một GA song song master - slave
54
Hình 3.11
Số lƣợng bộ vi xử lý tối ƣu khi áp dụng mô hình GA
master - slave theo tỷ lệ Tf/Tc và Npop
viii
55
MỞ ĐẦU
DES (viết tắt của Data Encryption Standard, hay Chuẩn mã hóa dữ liệu) là một hệ
mật mã khóa đối xứng do Công ty IBM thiết kế dựa trên hệ mật mã do chính họ đã nghiên
cứu trƣớc đó - hệ mật mã Lucifer và đƣợc FIPS (Tiêu chuẩn xử lý thông tin Liên bang
Hoa Kỳ) chọn làm chuẩn chính thức vào năm 1976. Sau đó, Chuẩn này đƣợc sử dụng
rộng rãi trên phạm vi thế giới.
Ngay từ đầu, thuật toán của nó đã gây ra rất nhiều tranh luận liên quan đến các
thành phần thiết kế mật, độ dài khóa tƣơng đối ngắn. Do đó, DES đã đƣợc giới nghiên
cứu xem xét rất kỹ lƣỡng, việc này đã thúc đẩy hiểu biết hiện đại về mật mã khối (block
cipher) và các phƣơng pháp tấn công (hay thám mã) tƣơng ứng. Có thể nói, sự xuất hiện
của DES đã tạo nên một làn sóng, một nguồn cảm hứng nghiên cứu trong giới khoa học
về lĩnh vực mật mã học, đặc biệt là các phƣơng pháp thám mã mã khối. Với DES, giới
khoa học đã có một thuật toán mật mã để nghiên cứu.
Mặc dù trong thời gian qua đã có rất nhiều kết quả nghiên cứu về thám mã DES đã
đƣợc công bố, DES có thể bị phá khoá bởi các hệ thống chuyên dụng trong vòng chƣa đầy
24 giờ, nhƣng việc nghiên cứu thám mã DES vẫn có ý nghĩa để hƣớng tới thám mã các hệ
mật mã khối có độ dài khóa mật lớn hơn, đã và đang dần thay thế DES nhƣ AES, IDEA, 3
DES, RC4, RC5,... Phân tích mật mã hay thám mã còn đƣa ra những khuyến cáo, phản
hồi cho các chuyên gia trong thiết kế lại các hệ mật mã để chống lại các dạng tấn công
mới. Đồng thời, nó cũng có ý nghĩa trong hỗ trợ công tác tình báo, phản gián v.v..
Với lý do trên, tác giả chọn đề tài: “Nghiên cứu phƣơng pháp thám mã Chuẩn
mật mã DES nhờ hệ thống tính toán hiệu năng cao”. Trong phạm vi nghiên cứu của đề
tài này, bài toán đặt ra là với một bản mã đƣợc mã hoá từ một thông điệp tiếng Anh bởi
Thuật toán mã hoá DES, với giả thiết ngƣời thám mã có thể truy cập đến chức năng mã
hóa/giải mã của DES. Từ giả thiết này, yêu cầu ứng dụng hệ thống tính toán hiệu năng
cao, thuật toán di truyền (Genetic Algorithm) để xây dựng thuật toán dạng thám mã “hộp
đen” để tìm ra khoá mật đã sử dụng để mã hoá thông điệp đó trong thời gian ngắn (dự
kiến khoảng 8 đến 15 phút).
Tác giả đã nghiên cứu, trình bày Luận văn thành ba chƣơng. Nội dung chính, kết
quả nghiên cứu của các chƣơng nhƣ sau:
Chƣơng I: Giới thiệu về chuẩn mã hoá dữ liệu - DES (Data Encryption Standard).
Chƣơng II: Các phƣơng pháp thám mã Chuẩn mã hoá dữ liệu DES, các hệ thống
chuyên dụng phục vụ thám mã DES.
1
Chƣơng III: Nghiên cứu, đề xuất phƣơng pháp thám mã DES
Do mức độ phức tạp của công việc thám mã là rất lớn nên bài toán đặt ra với giả
thiết ngƣời thám mã biết đƣợc các thông tin về bản mã đƣợc mã hóa bởi DES (chế độ
ECB) từ “bản rõ” tƣơng ứng là một thông điệp tiếng Anh. Từ giả thiết này, xây dựng
thuật toán di truyền để xác định khóa mật k đã sử dụng để mã hóa cũng nhƣ tìm ra “bản
rõ” tƣơng ứng.
Để giải quyết yêu cầu đặt ra và các bài toán nói trên, bài toán đƣợc chia thành các
bài toán con để gải quyết vấn đề:
- Xây dựng thuật toán nhận dạng “bản rõ” và “tiêu chuẩn bản rõ” là cơ sở xác định
hàm “phù hợp”, một thành phần quan trọng của thuật toán di truyền nói chung và của
thuật toán di truyền thám mã nói riêng.
- Tìm hiểu về thuật toán di truyền, xây dựng thuật toán di truyền để thực hiện tìm
kiếm khoá mật với phƣơng pháp “vét cạn có định hƣớng” trong không gian khoá (K2) xác
định khoảng 209 tỷ khóa.
Độ phức tạp của phƣơng pháp này chủ yếu phụ thuộc sự phán đoán, nhận dạng
ngôn ngữ của “bản rõ” tƣơng ứng với bản mã và phụ thuộc độ dài của khóa (số lƣợng bit
khóa), hoàn toàn không phụ thuộc vào thuật toán mã hóa khối mã của DES. Vì vậy, để đạt
đƣợc kết quả, mục tiêu nghiên cứu, tác giả đã sử dụng phƣơng pháp thống kê đặc trƣng
ngôn ngữ và áp dụng thuật toán di truyền.
Đề tài tập trung nghiên cứu, xây dựng thuật toán nhận dạng bản rõ và thuật toán di
truyền. Đồng thời, tác giả đã đề xuất ứng dụng mô hình hệ thống tính toán song song, mô
hình GA master - slave giúp rút ngắn thời gian thám mã khoảng 100 lần. Để đạt đƣợc kết
quả thám mã một cách tốt nhất, đòi hỏi phải có đƣợc một hệ thống tính toán song song và
kỹ năng lập trình song song. Tuy nhiên, với điều kiện và khả năng thực tế, tác giả đã xây
dựng dựng chƣơng trình thám mã thử nghiệm bằng ngôn ngữ Visual Basic .NET 2008
chạy trên một máy tính đơn, và giả định thuật toán di truyền hội tụ sau hai triệu thế hệ thì
tổng thời gian thám mã ƣớc lƣợng khoảng 19,4 giờ.
2
Chƣơng I. GIỚI THIỆU VỀ CHUẨN MÃ HÓA DỮ LIỆU - DES (DATA ENCRYPTION
STANDARD) [4]
1.1. GIỚI THIỆU VỀ THUẬT TOÁN MÃ HOÁ DES
DES đƣợc phân biệt giữa hai khái niệm là Chuẩn mã hoá dữ liệu (DES - Data
Encryption Standard) và Thuật toán mã hoá dữ liệu (DEA - Data Encryption Algorithm).
Thuật toán mã hoá là thành phần cơ bản của Chuẩn mã hoá. Việc nghiên cứu, phân tích về
DES chính là nghiên cứu, phân tích về thuật toán của nó.
Trong lĩnh vực mật mã học, có hai loại hệ mật mã thƣờng đƣợc đề cập đến, đó là
mật mã khoá công khai (khoá bất đối xứng) và mật mã khoá bí mật (khoá đối xứng).
Riêng đối với hệ mật mã đối xứng lại chia ra làm hai loại là mã hoá, giải mã theo khối và
mã hoá, giải mã theo dòng. DES (Data Encryption Standard) hay Chuẩn mã hóa dữ liệu
thuộc hệ mật mã khoá đối xứng và thực hiện mã hoá, giải mã theo khối. Độ dài của khối
thông tin mã hoá, giải mã là 64 bit.
Quy trình mã hoá, giải mã khối gồm hai thuật toán là mã hoá (ký hiệu là E) và giải
mã (ký hiệu là D). Cả hai thuật toán đều tác động lên một khối đầu vào 64 bit sử dụng
khoá 56 bit để cho ra khối 64 bit. Đối với bất kỳ khoá nào, giải mã là hàm ngƣợc của mã
hoá, nghĩa là:
- Mã hoá khối: Ek(M),
- Giải mã khối: M = Dk(Ek(M)),
trong đó, M là khối thông tin 64 bit và k là khoá 56 bit.
Khoá K
56 bit
Bản rõ 64 bit
Bản mã 64 bit
Thuật toán mã hóa
DES
Thuật toán giải mã
DES-1
Bản mã 64 bit
Bản rõ 64 bit
a. Quy trình mã hoá
Khoá K
56 bit
b. Quy trình giải mã
Hình 1.1. Mô phỏng sự mã hoá (a) và giải mã (b) theo DES
3
1.2. QUY TRÌNH MÃ HÓA THEO DES
Quy trình mã hoá của mật mã khối nói chung và mã hoá theo DES nói riêng đƣợc
thực hiện qua năm giai đoạn sau:
Giai đoạn 1:
“bản rõ” chữ
“bản rõ” số
Giai đoạn 2:
“bản rõ” số
Giai đoạn 3:
64 bit Rõ số
64 bit Mã số
Giai đoạn 4:
Các đoạn 64 bit Mã số
Bản Mã số
Giai đoạn 5:
Bản Mã số
Bản Mã chữ
(Dạng nhị phân)
Các đoạn 64 bit
Rõ số
(Dạng nhị phân)
1.3. LẬP MÃ VÀ GIẢI MÃ DES
1.3.1. Quy trình lập mã DES
Thuật toán DES tập trung thực hiện Giai đoạn 3 của quy trình mã hóa. Đó là
chuyển đổi “bản rõ” số với 64 bit thành bản Mã số với 64 bit.
4
“bản rõ”: 64
bit
IP
R0
L0
f
k1
R1 = L0 ⊕ f (R0, k1)
L1 = R0
f
R2 = L1 ⊕ f (R1, k2)
L1 = R0
L15 = R14
R15 = L14 ⊕ f (R14, k15)
f
k16
R16 = L15 ⊕ f (R15, k16)
L16 = R15
IP
Bản mã: 64 bit
Hình 1.2. Sơ đồ quy trình lập mã DES
5
k2
1.3.2. Thực hiện mã hóa DES theo sơ đồ
* “bản rõ” là xâu X, bản mã là xâu Y, khóa là xâu k, đều có độ dài 64 bit
* Thuật toán mã hóa DES thực hiện qua 3 bƣớc chính sau:
Bƣớc 1: “bản rõ” x đƣợc hoán vị theo hoán vị IP, thành IP (x).
IP (x) = L0R0, trong đó L0 là 32 bit đầu (left), R0 là 32 bit cuối (right). (IP (x) tách
thành L0R0).
Bƣớc 2: Thực hiện 16 vòng mã hóa với những phép toán giống nhau.
Dữ liệu đƣợc kết hợp với khóa thông qua hàm f:
Li = Ri-1,
Ri = Li-1 ⊕ f (Ri-1, ki), trong đó:
⊕ là phép toán hoặc loại trừ của hai dãy bit (cộng theo modulo 2).
k1, k2, ..., k16 là các khóa con (48 bit) đƣợc tính từ khóa gốc K.
Bƣớc 3: Thực hiện phép hoán vị ngƣợc IP-1 cho xâu R16L16, thu đƣợc bản mã y.
Y = IP-1 (R16L16).
(Lƣu ý thứ tự bit R16 và L16).
* Hoán vị ban đầu IP
+ bit 1 của IP(x) là bit 58 của x
58
50
42
34
26
18
10
2
+ bit 2 của IP(x) là bit 50 của x
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
6
* Hoán vị cuối cùng 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
1.3.3. Tính các khóa con k1, k2, ..., k16 từ khóa gốc K
Sơ đồ
K
PC-1
C0
D0
LS1
LS1
C1
D1
LS2
LS2
C2
LS16
C16
D12
PC-2
K1
PC-2
K2
PC-2
K16
LS16
D16
Hình 1.3. Sơ đồ quy trình tính các khóa con k1, k2, ..., k16
7
* Tính khóa ki (48 bit):
- Khóa K là xâu 64 bit, trong đó 56 bit là khóa và 8 bit để kiểm tra chẵn lẻ nhằm
phát hiện sai, các bit này không tham gia vào quá trình tính toán.
Các bit kiểm tra tính chẵn lẻ nằm ở vị trị 8, 16, 24, 32, 40, 48, 56, 64, sao cho mỗi
byte chứa một số lẻ các bit 1. Bởi vậy mỗi sai sót đơn lẻ đƣợc xác định trong mỗi nhóm 8
bit.
- Tính khóa ki nhƣ sau:
+ Với khóa K có độ dài 64 bit, ta loại bỏ các bit kiểm tra tính chẵn lẻ, hoán vị 56
bit còn lại theo phép hoán vị PC-1:
PC-1(K) = C0D0
Trong đó C0 là 28 bit đầu, D0 là 28 bit cuối cùng của PC-1(K)
+ Với i = 1, 2, ..., 16, ta tính Ci = LSi(Ci-1), Di = LSi(Di-1)
Trong đó, LSi là phép chuyển dịch vòng trái:
→ Dịch 1 vị trí nếu i = 1, 2, 9, 16. Dịch 2 vị trí với những giá trị i khác.
+ Với i = 1, 2, ..., 16, khóa ki đƣợc tính theo phép hoán vị PC-2 từ CiDi:
ki = PC-2(CiDi)
(48 bit)
* Phép hoán vị PC-1
* Phép hoán vị PC-2
57
49
41
33
25
17
9
14
17
11
24
1
5
1
58
50
42
34
26
18
3
28
15
6
21
10
10
2
59
51
43
35
27
23
19
12
4
26
8
19
11
3
60
52
44
36
16
7
27
20
13
2
63
55
47
39
31
23
15
41
52
31
37
47
55
7
62
54
46
38
30
22
30
40
51
45
33
48
14
6
61
53
45
37
29
44
49
39
56
34
53
21
13
5
28
20
12
4
46
42
50
36
29
32
8
1.3.4. Tính hàm f(Ri-1, ki)
Ri-1
k1
32 bit
E
48 bit
E(Ri-1)
48 bit
+
B1
B2
B3
B4
B5
B6
B7
B8
S1
S2
S3
S4
S5
S6
S7
S8
C1
C2
C4
C5
C3
C6
C7
C8
P
f (Ri-1, ki)
Hình 1.4. Sơ đồ quy trình tính hàm f (Ri-1, ki)
Để cho đơn giản, ta không ghi chỉ số i-1, i, và mô tả cách tính f(R, k):
a) Mở rộng xâu R (32 bit) thành xâu 48 bit, theo hàm mở rộng E
E: R (32 bit) → E(R) (48 bit)
E(R) gồm 32 bit cũ của R và 16 bit của R xuất hiện lần thứ 2.
b) Tính E(R) ⊕ k, trong đó E(R) (48 bit) và k (48 bit)
Kết quả gồm 8 xâu Bj có 6 bit (8 * 6 = 48):
B = B1 B2 B3 B4 B5 B6 B7 B8
9
c) Tính Cj = Sj (Bj), j = 1, ..., 8. Dùng 8 bảng S1, S2, ..., S8.
Sj là bảng cố định với r * c số nguyên từ 0 --> 15, (0 ≤ r ≤ 3), (0 ≤ c ≤ 15).
Sj thể hiện việc thay thế mỗi Bj thành Cj (Cj là xâu 4 bit) theo quy tắc sau:
* Giả sử Bj = b1 b2 b3 b4 b5 b6
(6 bit)
+ b1 b6 xác định biểu diễn nhị phân của hàng r trong Sj (0 ≤ r ≤ 3)
+ b2 b3 b4 b5 xác định biểu diễn nhị phân của cột c trong Sj (0 ≤ c ≤ 15)
Xâu Cj (4 bit) đƣợc định nghĩa là biểu diễn nhị phân của phần tử Sj(r, c)
d) Thực hiện 8 lần c), ta nhận đƣợc xâu C = C1 C2 ... C8
(32 bit).
Sau hoán vị P, cho kết quả P(C), đó chính là f(R, k).
* Phép hoán vị mở rộng E
32
4
8
12
16
20
24
28
1
5
9
13
17
21
25
29
2
6
10
14
18
22
26
30
3
7
11
15
19
23
27
31
4
8
12
16
20
24
28
32
* Phép hoán vị P
5
9
13
17
21
25
29
1
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
* Các bảng S1, S2, ..., S8:
S1
1
0
0
1
1
6
0
1
0
1
0
14
0
4
15
1
4
15
1
12
2
13
7
14
8
3
1
4
8
2
4
2
14
13
4
5
15
2
6
9
6
11
13
2
1
7
8
1
11
7
8
3
10
15
5
9
10
6
12
11
10
6
12
9
3
11
12
11
7
14
12
5
9
3
10
13
9
5
10
0
14
0
3
5
6
15
7
8
0
13
12
0
1
0
1
0
15
3
0
13
1
1
13
14
8
2
8
4
7
10
3
14
7
11
1
4
6
15
10
3
5
11
2
4
15
6
3
8
13
4
7
4
14
1
2
8
9
12
5
11
9
7
0
8
6
10
2
1
12
7
11
13
10
6
12
12
12
6
9
0
13
0
9
3
5
14
5
11
2
14
15
10
5
15
9
S2
7
0
0
1
1
10
S3
1
0
0
1
1
6
0
1
0
1
0
10
13
13
1
1
0
7
6
10
2
9
0
4
13
3
14
9
9
0
4
6
3
8
6
5
3
4
15
9
6
15
6
3
8
7
5
10
0
7
8
1
2
11
4
9
13
8
1
15
10
12
5
2
14
11
7
14
12
3
12
11
12
5
11
13
4
11
10
5
14
2
15
14
2
15
8
1
7
12
6
0
1
0
1
0
7
13
10
3
1
13
8
6
15
2
14
11
9
0
3
3
5
0
6
4
0
6
12
10
5
6
15
11
1
6
9
0
7
13
7
10
3
13
8
8
1
4
15
9
9
2
7
1
4
10
8
2
3
5
11
5
12
14
11
12
11
1
5
12
13
12
10
2
7
14
4
14
8
2
15
15
9
4
14
6
0
1
0
1
0
2
14
4
11
1
12
11
2
8
2
4
2
1
12
3
1
12
11
7
4
7
4
10
1
5
10
7
13
14
6
11
13
7
2
7
6
1
8
13
8
8
5
15
6
9
5
0
9
15
10
3
15
12
0
11
15
10
5
9
12
13
3
6
10
13
0
9
3
4
14
14
8
0
5
15
9
6
14
3
6
0
1
0
1
0
12
10
9
4
1
1
15
14
3
2
10
4
15
2
3
15
2
5
12
4
9
7
2
9
5
2
12
8
5
6
6
9
12
15
7
8
5
3
10
8
0
6
7
11
9
13
1
0
14
10
3
13
4
1
11
4
14
10
7
12
14
0
1
6
13
7
11
13
0
14
5
3
11
8
15
11
8
6
13
6
0
1
0
1
0
4
13
1
6
1
11
0
4
11
2
2
11
11
13
3
14
7
13
8
4
15
4
12
1
5
0
9
3
4
6
8
1
7
10
7
13
10
14
7
8
3
14
10
9
9
12
3
15
5
10
9
5
6
0
11
7
12
8
15
12
5
2
0
14
13
10
15
5
2
14
6
8
9
3
15
1
6
2
12
6
0
1
0
1
0
13
1
7
2
1
2
15
11
1
2
8
13
4
14
3
4
8
1
7
4
6
10
9
4
5
15
3
12
10
6
11
7
14
8
7
1
4
2
13
8
10
12
0
15
9
9
5
6
12
10
3
6
10
9
11
14
11
13
0
12
5
0
15
3
13
0
14
3
5
14
12
9
5
6
15
7
2
8
11
S4
1
0
0
1
1
S5
1
0
0
1
1
S6
1
0
0
1
1
S7
1
0
0
1
1
S8
1
0
0
1
1
11
* Quy định lập bảng Sj:
- Mỗi hàng của bảng S phải là một hoán vị của 0, 1, ..., 15.
- Không có bảng S nào là hàm tuyến tính hay Apphin của các đầu vào của nó.
- Thay đổi 1 bit vào ở một bảng S, sẽ gây ra sự thay đổi ít nhất 2 bit ra của nó.
- Nếu 2 xâu vào của một bảng S giống nhau ở 2 bit đầu và 2 bit cuối, thì 2 xâu ra
phải khác nhau.
- Với mỗi bảng S, nếu cố định 1 bit vào xét giá trị của 1 bit ra nào đó, thì số các
xâu vào tạo ra giá trị 0 ở bit ra đó cũng phải xấp xỉ bằng số các xâu vào tạo ra giá trị 1 ở
bit ra đó.
1.3.5. Quy trình giải mã DES
Quy trình giải mã của DES tƣơng tự nhƣ quy trình lập mã, nhƣng sử dụng các khóa
theo thứ tự ngƣợc lại: k16, k15, ..., k1.
Xuất phát từ bản mã Y (đầu vào), kết quả là “bản rõ” X (đầu ra).
1.3.6. Độ an toàn của Chuẩn mã hóa DES
a) Độ an toàn của Chuẩn mã hóa DES có liên quan đến các bảng Sj:
Ngoại trừ các bảng S, mọi tính toán trong DES đều tuyến tính, tức là việc tính phép
hoặc loại trừ của hai đầu ra cũng giống nhƣ phép hoặc loại trừ của hai đầu vào, rồi tính
toán đầu ra.
Các bảng S chứa đựng nhiều thành phần phi tuyến của hệ mật, là yếu tố quan trọng
nhất đối với độ an toàn của hệ thống.
Khi mới xây dựng hệ mật DES, thì tiêu chuẩn xây dựng các hộp S không đƣợc biết
đầy đủ. Và có thể các hộp S này có thể chứa các “cửa sập” đƣợc giấu kín. Và đó cũng là
một điểm đảm bảo tính an toàn của hệ mật DES.
b) Hạn chế của DES chính là kích thƣớc không gian khóa:
Số khóa có thể là 256, không gian này là nhỏ để đảm bảo an toàn thực sự. Nhiều
thiết bị chuyên dụng đã đƣợc đề xuất nhằm phục vụ tấn công với một cặp “bản rõ” - bản
mã đã biết. Phép tấn công này chủ yếu thực hiện theo phƣơng pháp “vét cạn”. Tức là với
12
“bản rõ” X và bản mã Y tƣơng ứng (64 bit), mỗi khóa có thể đƣợc kiểm tra cho tới khi
tìm đƣợc một khóa K thỏa mãn ek(X) = Y.
1.4. CÁC CHẾ ĐỘ MÃ HÓA DES [15]
Các hệ mật mã khối nói chung và chuẩn mã hóa khối DES có 6 (sáu) chế độ mã
hóa chính, gồm chế độ mã hoá cơ bản (ECB - electronic codebook mode), chế độ liên kết
khối mã (CBC - cipher block chaining mode), chế độ phản hồi mã (CFB - cipher feedback
mode), PCBC (propagating cipher-block chaining), OFB (output feedback), CTR
(counter). Trong đó, chế độ mã hóa cơ bản ECB là đơn giản nhất.
Dƣới đây là sơ đồ mô tả chế độ mã hoá cơ bản và chế độ mã hoá liên kết khối mã.
1.4.1. Chế độ mã cơ bản (ECB - electronic codebook)
Bản rõ
Khoá
Mã hoá
mã khối
Bản rõ
Khoá
Bản mã
Mã hoá
mã khối
Bản rõ
Khoá
Bản mã
Mã hoá
mã khối
Bản mã
a. Mã hoá
Bản mã
Khoá
Giải mã
mã khối
Bản rõ
Bản mã
Khoá
Giải mã
mã khối
Bản rõ
Bản mã
Khoá
Giải mã
mã khối
Bản rõ
b. Giải mã
Hình 1.5. Mã hóa (a) và giải mã (b) theo chế độ mã cơ bản (ECB)
13
1.4.2. Chế độ liên kết khối mã (CBC - cipher block chaining)
Bản rõ
Bản rõ
Bản rõ
Vector khởi tạo
(Initialization Vector – IV)
Khoá
Mã hoá
mã khối
Khoá
Bản mã
Mã hoá
mã khối
Khoá
Mã hoá
mã khối
Bản mã
Bản mã
Bản mã
Bản mã
a. Mã hoá
Bản mã
Vector khởi tạo
(Initialization Vector – IV)
Khoá
Giải mã
mã khối
Khoá
Bản rõ
Giải mã
mã khối
Bản rõ
Khoá
Giải mã
mã khối
Bản rõ
b. Giải mã
Hình 1.6. Mã hóa (a) và giải mã (b) theo chế độ liên kết khối mã (CBC)
DES có thể áp dụng một trong các chế độ mã hoá nhƣ đã nói trên. Nhƣng để giới
hạn phạm vi nghiên cứu của đề tài, khi thực hiện hiện công việc thám mã đƣơng nhiên
chúng ta giả định bản mã cho trƣớc đƣợc mã hóa bởi chuẩn mã hóa DES, đồng thời cũng
giả định rằng bản mã đƣợc mã hóa theo chế độ mã cơ bản (ECB). Tức là “bản rõ” đƣợc
chia nhỏ thành các khối độc lập, mỗi khối 64 bit. Mỗi khối này đƣợc mã hóa bởi cùng
một khóa k nào đó để tạo ra các khối mã 64 bit độc lập.
Ngày nay, Thuật toán mã hóa dữ liệu (DEA - Data Encryption Algorithm) của
Chuẩn mã hóa dữ liệu DES đã đƣợc công bố chi tiết, cho nên các chƣơng trình mã hóa
DES, các thƣ viện mã nguồn mở vể DES đƣợc công bố rộng rãi. Phụ lục 1 của Luận văn
là một ví dụ về sử dụng Thƣ viện mã nguồn mở Chilkat.Crypt2 về DES để thực hiện mã
hóa, giải mã một thông điệp, với các chế độ mã hóa cơ bản (ECB), chế độ mã hóa liên kết
khối mã (CBC).
14
- Xem thêm -
.PDF 
76 
196 
95 
