1

Nghiên cứu phương pháp tấn công
Chuẩn mật mã khối (DES) nhờ
hệ thống tính toán hiệu năng cao
Researching on cryptanalytic method of Data Encryption Standard (DES)
bases on high performance computing system
NXB H. : ĐHCN, 2012 Số trang 70 tr. +

Nguyễn Quốc Thắng Trường Đại học Công nghệ
Luận văn ThS ngành: Hệ thống thông tin; Mã số: 60 48 05
Người hướng dẫn: PGS.TS. Hồ Văn Canh
Năm bảo vệ: 2012

Abstract: Giới thiệu về chuẩn mã hoá dữ liệu - DES (Data Encryption Standard). Trình
bày các phương pháp thám mã: thám mã đường tắt; Thám mã vi sai; Thám mã tuyến tính;
Thám mã phi tuyến; Thám mã vi sai tuyến tính và một số phương pháp thám mã đường tắt
khác huẩn mã hoá dữ liệu DES, các hệ thống chuyên dụng phục vụ thám mã DES. Nghiên
cứu, đề xuất phương pháp thám mã DES: mô tả bài toán tham mã DES; Xây dựng thuật
toán nhận dạng bản rõ tiếng Anh; Tìm hiểu thuật toán di truyền (GAs) và đề xuất phương
pháp thám mã DES

Keywords: Công nghệ thông tin; Mật mã khối; An ninh thông tin; Hệ thống thông tin; Mã
hoá dữ liệu

Content
DES (viết tắt của Data Encryption Standard, hay Chuẩn mã hóa dữ liệu) là một phương pháp
mật mã hóa do Công ty IBM thiết kế và được FIPS (Tiêu chuẩn xử lý thông tin Liên bang Hoa

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õ” tiếng Anh 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.
- 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á (K
2
) 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), mà 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,
đòi hỏi sự kết hợp nhiều lĩnh vực liên quan. Đề tài đã kết hợp, vận dụng giữa thuật toán nhận dạng
bản rõ và thuật toán di truyền. Khi ứng dụng thuật toán di truyền thì “Tiêu chuẩn bản rõ” có thể
được xem như là hàm “phù hợp” - đặc thù của thuật toán di truyền thám mã.
Mục tiêu nghiên cứu của đề tài là xây dựng thuật toán tấn công thám mã. Tuy nhiên để để
tăng tốc độ tính toán, rút ngắn thời gian thám mã, 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.
3 CHƢƠNG I
GIỚI THIỆU VỀ CHUẨN MÃ HÓA DỮ LIỆU –
DES (DATA ENCRYPTION STANDARD) [4]

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á

(E
k
(M)),
trong đó, M là khối thông tin 64 bit và k là khoá 56 bit.
4

Thuật toán mã hóa
DES
Khoá K
56 bit
Bản rõ 64 bit
Bản mã 64 bit
Thuật toán giải mã
DES
-1
Khoá K
56 bit
Bản mã 64 bit
Bản rõ 64 bit

a. Quy trình mã hoá b. Quy trình giải mã
Hình 1.1. Mô phỏng mã hoá (a) và giải mã (b) theo DES
Quy trình giải mã của DES là quy trình ngược lại với quy trình mã hóa DES, xuất phát từ bản
mã Y (đầu vào), kết quả là bản rõ X (đầu ra).
Do xác định mục tiêu, phương pháp thám mã khối DES là thám mã “hộp đen”, thám mã “vét
cạn có định hướng” dựa trên các yếu tố độ dài khóa (số lượng bit của khoá), bản mã, và độ dài
khối mã nên khi xây dựng thuật toán thám mã không cần phân tích chi tiết thuật toán DES.
1.3. Các chế độ mã hoá theo 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, gồm
chế độ mã hoá cơ bản (ECB - electronic codebook mode), chế độ liên kết khối mã (CBC - cipher

Giải mã
mã khối
Khoá
Bản mã
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) [15]
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
5

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.
1.4. Độ an toàn của DES
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.
Số khóa có thể là 2
56
, 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 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
e
k
(X) = Y.


sai bậc cao, thám mã nội suy v.v..
2.2.2. Thám mã hộp đen (vét cạn để tìm khoá) [1][2][8]
Thám mã hộp đen nói chung và tấn công vét cạn nói riêng là phương pháp thám mã không
phân tích sâu cấu trúc bên trong của hệ mật mã. Cơ sở của phương pháp này chủ yếu dựa vào sức
mạnh của các hệ thống tính toán hiệu năng cao để thực hiện vét cạn và tìm ra khoá mật. Đây là
phương pháp thám mã đơn giản nhất đối với hệ mật mã khối. Việc thám mã đơn thuần chỉ là thử
tất cả các khóa, khóa này nối tiếp khóa kia, cho đến khi tìm ra khóa đúng. Như vậy, trong trường
hợp xấu nhất ta cần phải thử 2
l
khóa, nếu độ dài khóa là l. Và riêng đối với hệ DES thì trường hợp
xấu nhất ta cần phải thử 2
56
khóa (khoảng hơn 72 triệu tỷ khóa).
Trong mọi trường hợp thám mã nói trên, mục đích là tìm ra khóa mật được sử dụng cho hệ
mã hoá. Dựa vào cách thức phân loại thám mã này để xác định bài toán thám mã được nghiên
cứu, đề xuất trong đề tài này thuộc phương pháp thám mã hộp đen, đồng thời là thám mã chỉ biết
bản mã, và người thám mã biết thuật toán mã hóa/giải mã (có thể truy cập vào chức năng mã
hóa/giải mã của DES).
2.3. Các hệ thống chuyên dụng thám mã DES
Công việc thám mã nói chung và thám mã hộp đen, vét cạn để tìm khóa nói riêng do có
không gian khóa thử là rất lớn, độ phức tạp tính toán cao. Do vậy, thám mã không thể sử dụng
những máy tính thông thường mà cần phải sử dụng các hệ thống tính toán hiệu năng cao, hay các
hệ thống vận dụng được đồng thời rất nhiều nguồn lực tính toán. Cụ thể, các hệ thống này gồm có
các phần cứng chuyên dụng thám mã, điện toán lưới, điện toán đám mây, siêu máy tính, máy tính
song song, hệ thống máy tính cụm cluster v.v.. Đặc biệt, đối với thuật toán di truyền thám mã rất
thích hợp với ứng dụng các máy tính song song hoặc hệ thống tính toán song song (hệ thống máy
tính cụm - cluster).

CHƢƠNG III
NGHIÊN CỨU, ĐỀ XUẤT PHƢƠNG PHÁP THÁM MÃ DES

(Chế độ ECB)

(a) Giả thiết (b) Bài toán đặt ra
Hình 3.1. Mô tả giả thiết (a) và bài toán thám mã DES (b)
Với giả thiết bài toán như trên, tác giả đề xuất phương pháp thám mã hộp đen áp dụng thuật
toán di truyền với sự hỗ trợ của hệ thống tính toán song song.
Theo như phần tìm hiểu về phương pháp thám mã hộp đen, công việc thám mã không cần
phân tích chi tiết thuật toán bên trong DES, mà xem như các biến đổi bên trong khối mã là một
“hộp đen”. Do vậy, thám mã ở đây thực chất là thực hiện vét cạn khóa trên không gian đã được
giới hạn. Tuy nhiên, sự “vét cạn” là “có định hướng” nhờ thuật toán di truyền, và sự “tiến hóa”
qua các thế hệ (vòng lặp) của thuật toán di truyền.
3.2. Xây dựng thuật toán nhận dạng bản rõ tiếng Anh
3.2.1. Vai trò của nhận dạng bản rõ tự động trong thám mã “vét cạn”
Đọc bằng mắt thường
Giải mã toàn bộ bản mã
Kết thúc
Ghi nhận khóa đúng
Sinh khóa
Đúng
Sai
Module nhận dạng
bản rõ tự động
Giải mã một phần bản mã
Đọc được
(là bản rõ tiếng Anh)?
Kết thúc
Ghi nhận khóa đúng,
giải mã cho đến hết
Sinh khóa
Đúng

1
x
2
...x
m
. Trong đó, x
i
∈ A = {a, b, c,..., z}, i = .
Hãy xây dựng một thuật toán để máy tính trả lời cho câu hỏi: dãy X là “bản rõ” tiếng Anh hay là
dãy giả ngẫu nhiên (một dãy vô nghĩa)?
b) Cách tiếp cận
Đặc trưng của một chữ viết thuộc ngôn ngữ nào đó có thể được xác định dựa trên thống kê
tần suất đơn hoặc tần suất bộ đôi của sự xuất hiện các chữ cái. Phần này sẽ tập trung nghiên cứu
xây dựng thuật toán nhận dạng “bản rõ” tự động dựa trên thống kê tần suất bộ đôi.
Tần suất bộ đôi là xác suất để một chữ cái liền kề sau chữ cái khác hay xác suất để hai chữ
cái bất kỳ trong bảng chữ cái đứng cạnh nhau. Đặc trưng này của ngôn ngữ được thể hiện ở mô
hình nổi tiếng được ứng dụng rộng rãi trong lĩnh vực xử lý ngôn ngữ tự nhiên - Mô hình xích
Markov. Dựa vào mô hình này để xây thuật toán giúp máy tính phân biệt được chữ viết một ngôn
ngữ xác định với một xâu ký tự ngẫu nhiên, hoặc phân biệt chữ viết của hai hay nhiều ngôn ngữ
khác nhau. Tuy nhiên, trong phạm vi nghiên cứu của đề tài, việc xây dựng thuật toán nhận dạng
“bản rõ” (“valid” plain-text) là để phân biệt được một thông điệp tiếng Anh với một xâu ký tự
ngẫu nhiên. Trong trường hợp này, xâu ký tự ngẫu nhiên được sinh ra do thực hiện giải mã bản
mã cho trước (“valid” cipher-text) bởi một khóa thử bất kỳ, mà không phải là khóa đúng.
c) Phương pháp giải
Đối với xâu đầu vào X chỉ cần tính tần số bộ đôi, tức số lần xuất hiện các bộ đôi chữ cái trong
xâu (không cần tính tần suất), các bộ đôi chữ cái (thuộc không gian 26
2
bộ đôi) không xuất hiện
trong xâu X coi như có tần số bằng 0. Từ đây, kết hợp với đặc trưng tần suất bộ đôi đã được lưu
vào cơ sở dữ liệu để kết luận xâu X là “bản rõ”, hay dãy ngẫu nhiên, vô nghĩa.

Kiểm tra hội tụ
Có
Không
Chọn lọc

Hình 3.5. Biểu đồ luồng của thuật toán di truyền nhị phân [12, pp.29]
3.4. Đề xuất phƣơng pháp thám mã DES
10

3.4.1. Xây dựng thuật toán di truyền dò tìm khóa
Vận dụng kết quả nghiên cứu thuật toán di truyền nhị phân và đặc trưng của bài toán thám mã
hộp đen để xây dựng quy trình dò tìm khóa đúng như hình dưới đây:
Định nghĩa hàm phù hợp,
các biến
Tạo lập họ khóa khởi tạo
Giải mã bản mã cho trước
với các khóa trong họ
Tính các giá trị mức phù hợp
của các bản giải mã
Loại bỏ 50% khóa
có mức phù hợp thấp
Chọn từng cặp khóa để kết hợp
Kết hợp,
sinh khóa mới
Đột biến
Kết thúc
Kiểm tra hội tụ ?
Có
Không
100 khóa

}
Tập P đạt
100 khóa
Kết thúc
Đúng
Đúng
Sai
Sinh khóa mới
Sai

Hình 3.8. Quy trình tạo lập tập khóa khởi tạo P gồm 100 khóa
Không gian khóa {K
2
} là không gian khóa gồm các khóa k nếu sử dụng để giải mã Y thì
cho kết quả là xâu X gồm các chữ cái tiếng Anh.
Theo như đã tìm hiểu về thuật toán di truyền thì ký hiệu N
pop
là dân số khởi tạo, N
bits
là số
bit của nhiễm sắc thế, nên ở đây, N
pop
= 100 do họ khóa khởi tạo P là 100, và N
bits
= 64, vì mỗi
khóa của DES có 64 bit (gồm cả 8 bit kiểm tra chẵn lẻ - parity). Như vậy, họ khóa k khởi tạo là
một ma trận gồm các bit không (0) và một (1), có 100 dòng, 64 cột.
3.4.1.3. Giải mã bản mã cho trước với các khóa trong họ
Không giống như áp dụng thuật toán di truyền trong các trường hợp khác, để tính toán mức
độ phù hợp (chí phí) cho các khóa, thuật toán không tính trực tiếp trên các bit khóa, mà dựa trên

1 k
1,1
k
1,2
... k
1,64
f
1

2 k
2,1
k
2,2
... k
2,64
f
2

12

3 k
3,1
k
3,2
... k
3,64
f
3

... ... ...

Bố(3) + Mẹ(4) → Con(53), Con(54)
....
Bố(49) + Mẹ(50) → Con(99), Con(100)
hay:
k
1
+ k
2
→ k
51
, k
52

k
3
+ k
4
→ k
53
, k
54

....
k
49
+ k
50
→ k
99
, k

i
(5)
k
i
(6)
k
i
(7)
k
i
(8)
.
Chẳng hạn khi khoá k
1
kết hợp với khoá k
2
sẽ tạo ra hai con k
51
và k
52
là:
k
51
= k
1
(1)
k
2
(2)
k

(4)
k
2
(5)
k
1
(6)
k
2
(7)
k
1
(8)
Tiến hành như vậy đối với 24 cặp bố mẹ còn lại để tạo ra 24 cặp con cái. Kết thúc giai đoạn
sinh sản này, họ khoá trở về số lượng 100 như ban đầu.

3.4.1.8. Đột biến
13

Để mô tả quá trình đột biến, ta vẫn sử dụng ký hiệu khoá k
i
= k
i1
k
i2
... k
i8
... k
i64
để biểu thị 64

554 thành phần
mcol = [2 12 5 18 56 1 44 3 11 ... 26 9 18 4 19 31]
554 thành phần
Với các giá trị mrow và mcol được tạo ra như trên, 634 bit đột biến sẽ là các bit ở các toạ độ
dòng và cột tương ứng (5, 2), (92, 12), (6, 5), ..., (5, 19), (34, 31). Những bit tại các toạ độ này nếu
có giá trị là 0 thì sẽ được chuyển thành 1, và ngược lại.
Mã lệnh đột biến cho một phần tử của ma trận các bit như sau:
pop(mrow,mcol)=1-pop(mrow,mcol)
Sau khi thực hiện xong sự đột biến cho 634 bit của họ, thuật toán tiếp tục thế hệ mới với công
việc đầu tiên là giải bản mã gốc với 100 khoá (đã qua kết hợp và đột biến) rồi tính các giá trị mức
phù hợp (fitness) để xác định f
1
, f
2
, ..., f
100
tương ứng. Sau đó sắp xếp lại các khoá (nhiễm sắc thể)
của họ khoá theo thứ tự các giá trị f
i
thấp nhất đến cao nhất. Dựa trên bảng phân hạng mức phù
hợp này, thực hiện kiểm tra sự hội tụ. Nếu chưa có hội tụ, tiếp tục loại 50 khoá có giá trị f
i
cao
nhất, giữ lại 50 khoá có giá trị f
i
thấp nhất. 50 khoá được giữ lại này lại tiếp tục các tiến trình ghép
cặp, kết hợp, đột biến. Ở mỗi thế hệ, kể từ thế hệ thứ hai đều lặp lại bắt đầu từ bước giải bản mã
cho trước với các khoá trong họ.
3.4.1.9. Kiểm tra hội tụ
Quá trình lặp trên đây cứ tiếp tục diễn ra từ thế hệ này đến thế hệ khác cho đến khi có sự hội

nên có 26
8
khoá k thuộc không gian khóa K
2
, tương đương khoảng 209 tỷ khóa k. Đồng thời, toàn
bộ không gian khóa K của DES là 2
56
khóa (khoảng 72 triệu tỷ khóa), nên theo tỷ lệ và xác suất,
để tìm được 100 khóa thuộc không gian khóa K
2
trong toàn bộ không gian khóa K thì cần phải thử
khoảng:
100 x (72 triệu tỷ khóa / 209 tỷ khóa) 34.500.000 khóa.
Với tốc độ 35 Kb/s thì mỗi giây DES duyệt 4.375 khóa để giải mã 8 byte bản mã. Có nghĩa,
để thử với giải mã 1 khóa, cần tiêu tốn 1/4.375 giây, hay T
d
= 0,000229. Do vậy, thời gian tạo lập
tập P gồm 100 khóa là Tp = 34.500.000 x 0,000229 = 7900 giây (khoảng 132 phút).
b) Thời gian tính toán qua các thế hệ
Giả định rằng, thuật toán di truyền thám mã đạt được sự hội tụ qua 2.000.000 thế hệ. Khi đó,
số lượng khóa k phải duyệt là 2.000.000 x 100 = 200.000.000 khóa (trong số 2
56
hay khoảng 72
triệu tỷ khóa của toàn bộ không gian khóa của DES), và chỉ bằng khoảng một phần ba trăm sáu
mươi triệu (1 / 360.000.000) so với vét cạn toàn bộ không gian khóa.
Thời gian duyệt một khóa trong mỗi vòng lặp gồm:
- Thời gian giải mã bản mã cho trước với khóa được duyệt
- Thời gian tính giá trị hàm phù hợp của bản giải mã tương ứng với khóa được duyệt.
Với tốc độ 35 Kb/s để giải mã bản mã cho trước, thì để giải mã với một khóa bất kỳ thì cần
một khoảng thời gian là 0,000229 giây (hay T

c
: thời gian trung bình truyền dữ liệu từ một
bộ vi xử lý tới một bộ vi xử lý khác, P: số lượng bộ vi xử lý, : tham biến phụ thuộc vào phương
pháp lập trình, đặc điểm hệ thống tính toán song song, N
pop
: là dân số của một

thế hệ.
Với đặc trưng bài toán thám mã, đẳng thức 3.14 có thể được bổ sung như sau:
,
(3.15)
trong đó T
d
là thời gian giải bản mã (8 byte) với một khóa thử k bất kỳ.
Nếu áp dụng mô hình tính toán song song đối thuật toán di truyền đó là “GA master - slaver”
một cách hiệu quả, thì thời gian truyền thông hay giá trị là không đáng kể và có thể bỏ
qua khi ước lượng tổng thời gian tính toán. Trong trường hợp này mô hình sẽ đạt hiệu quả cao,
tăng tốc khoảng 100 lần khi sử dụng một máy chủ (master) và 100 thành viên (slave).
Thời gian thám mã khi ứng dụng mô hình GA master - slave có 100 máy slave nói trên là:
1.162 phút / 100 = 11,62 phút.

KẾT LUẬN
1. Kết quả nghiên cứu
Đề tài đã ứng dụng thuật toán di truyền cùng với “tiêu chuẩn bản rõ” tiếng Anh để xây dựng
thuật toán “vét cạn có định hướng” trên không gian khoá đã giới hạn. Thuật toán này thực hiện dò
tìm khoá mật với một bản mã cho trước được mã hóa bởi Chuẩn mã hóa dữ liệu DES.
Đề tài đã đạt được những kết quả nghiên cứu chính sau:
- Xây dựng thuật toán nhận dạng “bản rõ” và “tiêu chuẩn bản rõ” đối với tiếng Anh là cơ sở
để xác định hàm “phù hợp” áp dụng cho thuật toán di truyền.
- Xây dựng quy trình thám mã dựa trên thuật toán di truyền gồm các bước tạo lập họ khoá

4. Trịnh Nhật Tiến (2008), Giáo trình An toàn dữ liệu, Đại học Quốc gia, Hà Nội, tr.59-70.
Tiếng Anh
5. Alan Silvester (2004), “Differential Cryptanalysis and the Data Encryption Standard”.
6. Billingsley, Patrick (1961), “Statistical Methods in Markov Chains”. Annals of
mathematical statistics, 23:1.
7. C.R. Rao’s (1968), Linear statistical methods and their applications, Moscow, pp.45-60.
8. Curtin, Matt (2005): Brute-Force: Cracking the DES, Springer - Verlag.
9. Erick Cantú-Paz (2001), A Survey of Parallel Genetic Algorithms, Department of Computer
Science and Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-
Champaign, United States.
17

10. Juan M. E. Tapiador, Julio C. Hernandez-Castro, John A. Clark (2007), “Heuristic Search
for Non-Linear Cryptanalytic Approximations”, IEEE Congress on Evolutionary
Computation (CEC 2007)
11. Mitsuru Matsui (1998), “Linear Cryptanalysis Method for DES Cipher”, Springer-Verlag.
12. Randy L. Haupt, Sue Ellen Haupt (2004), Practical Genetic Algorithms (second edition),
John Wiley & Sons, Canada.
13. Ravi Ganesan, Alan T.Sherman (1993), Statistical Techniques for Language Recognition:
An Introduction and Guide for Cryptanalysts, IEEE - Transactions on Information Theory,
IT-28(4).
14. Susan K. Langford, Martin E. Hellman (1994) “Differential-Linear Cryptanalysis”,
Springer-Verlag.
Websites
15. http://www.wikipedia.org