i

S húa bi Trung tõm Hc liu
i

đại học thái nguyên
Tr-ờng đại học CÔNG NGHệ THÔNG TIN Và TRUYềN THÔNG
Lấ HU TH

MT S PHNG PHP THM M
H MT M I XNG V NG DNG TRONG
PHT TRIN H MT M

LUN VN THC S KHOA HC MY TNH thái nguyên - năm 2014
ii

Số hóa bởi Trung tâm Học liệu
ii

®¹i häc th¸i nguyªn
Tr-êng ®¹i häc C¤NG NGHÖ TH¤NG TIN Vµ TRUYÒN TH¤NG



Số hóa bởi Trung tâm Học liệu
iii

LỜI CẢM ƠN

Em xin chân thành cảm ơn trƣờng Đại học Công nghệ thông tin và truyền
thông Thái Nguyên đã tạo điều kiện thuận lợi cho em trong quá trình học tập, công
tác và thực hiện đề tài luận văn.
Em xin nói lên lòng biết ơn sâu sắc và lời cảm ơn chân thành đến thầy giáo
TS. Nguyễn Duy Minh, ngƣời Thầy mà đã luôn tận tình hƣớng dẫn, truyền thụ cho
em những kiến thức, kinh nghiệm quý báu và giúp em trong suốt quá trình học tập,
nghiên cứu cũng nhƣ quá trình thực hiện luận văn.
Cuối cùng em xin đƣợc gửi lời cảm ơn sâu sắc tới gia đình, bạn bè, đồng nghiệp
đã luôn ủng hộ, động viên em trong quá trình học tập và thực hiện luận văn này.
Mặc dù đã cố gắng hoàn thành luận văn trong phạm vi và khả năng cho phép
nhƣng chắc chắn sẽ không tránh khỏi những thiếu sót, kính mong nhận đƣợc sự tận
tình chỉ bảo của quý thầy cô và các bạn.

Thái nguyên, Tháng 9 năm 2014
Lê Hữu Thọ iv

Số hóa bởi Trung tâm Học liệu
iv

2.3.3. Phƣơng pháp thám mã vi sai 42
v

Số hóa bởi Trung tâm Học liệu
v

2.4. Đánh giá độ an toàn của DES trƣớc một vài phƣơng pháp tấn công phá mã 47
2.5. Kết luận 48
CHƢƠNG 3: CÀI ĐẶT MỘT SỐ PHƢƠNG PHÁP THÁM MÃ HỆ MÃ DES 49
TRONG PHÁT TRIỂN HỆ MẬT MÃ 49
3.1. Đặt vấn đề 49
3.2. Mô tả về DES 50
3.3. Lập mã DES 62
3.4. Xây dựng chƣơng trình thám mã DES 66
3.5. Kết luận 71
KẾT LUẬN 72
TÀI LIỆU THAM KHẢO 73 vi

Số hóa bởi Trung tâm Học liệu
vi

DANH MỤC HÌNH

Hình 1.1. Sơ đồ mã hóa DES 7
Hình 1.2. Một vòng lặp DES 9
Hình 1.3. Mô phỏng mã hóa (a) và giải mã (b) theo DES 10
Hình 1.4. Chế độ CBC 11

trực tiếp bản mã khi không có khóa mã trong tay mà ngƣời ta gọi là thám mã.
Ngày nay, nhu cầu trao đổi thông tin mật giữa các thành viên trong một nhóm,
một tổ chức ngày càng lớn thì việc đảm bảo an toàn thông tin là rất cần thiết. Cùng
với sự phát triển của mật mã nói chung và của các hệ mã đối xứng nói riêng thì thám
mã là một lĩnh vực cũng thƣờng đƣợc quan tâm nghiên cứu, nhƣng ít khi đƣợc công
khai, hoặc công khai không đầy đủ. Mặc dù, trong thời gian qua đã có nhiều kết quả
nghiên cứu về DES đƣợc công bố, DES có thể bị phá khóa 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 rất cần
thiết để hƣớng tới thám mã các hệ mật mã hiện đại có độ dài khóa lớn hơn, đã và
đang dần thay thế DES. 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 tấn
công mới. Đồng thời nó có ý nghĩa hỗ trợ công tác tình báo, phản gián.
Chính vì những lý do trình bày ở trên, em đã chọn đề tài: “Một số phương
pháp thám mã hệ mật mã đối xứng và ứng dụng trong phát triển hệ mật mã”,
nhằm tìm hiểu các phƣơng pháp thám mã và xây dựng qui trình thám mã cho hệ mật
mã đối xứng DES.
Trong khuôn khổ đề tài đƣợc giao, luận văn đƣợc trình bày trong 3 chƣơng có phần
mở đầu, phần kết luận, phần mục lục, tài liệu tham khảo. Các nội dung cơ bản của
luận văn đƣợc trình bày nhƣ sau:
2

2
Số hóa bởi Trung tâm Học liệu

Chƣơng 1: “Tổng quan về chuẩn mã hóa dữ liệu DES”, trong chƣơng này tập
chung trình bày về các khái niệm mã hóa, các hệ mật mã, các chế độ mã hóa và quá
trình mã hóa, giải mã DES.
Chƣơng 2: “Các phƣơng pháp thám mã hệ mật mã đối xứng”, trong chƣơng này
trình bày các thuật ngữ cơ bản về mật mã và thám mã, khái niệm về thám mã, các
bƣớc để tiến hành thám mã, đặc biệt trong chƣơng này tập trung trình bày về 3

TỔNG QUAN VỀ CHUẨN MÃ HÓA DỮ LIỆU DES
1.1. Các hệ mã khóa
1.1.1. Hệ mật mã đối xứng
Thuật toán đối xứng hay còn gọi là thuật toán mã hóa cổ điển. Thuật toán
này còn có nhiều tên gọi khác nhƣ thuật toán khóa bí mật, thuật toán đơn giản, thuật
toán một khóa.
Là thuật toán mà tại đó khóa mã hóa có thể tính toán ra đƣợc từ khóa giải mã.
Trong rất nhiều trƣờng hợp, khóa mã hóa và khóa giải mã là giống nhau.
Thuật toán này yêu cầu ngƣời gửi và ngƣời nhận phải thỏa thuận một khóa
trƣớc khi thông báo đƣợc gửi, và khóa này phải đƣợc cất giữ bí mật. Độ an toàn của
thuật toán này vẫn phụ thuộc vào khóa, nếu để lộ ra khóa này nghĩa là bất kì ngƣời
nào cũng có thể mã hóa và giải mã hệ thống mật mã.
Sự mã hóa và giải mã của thuật toán đối xứng đƣợc biểu thị bởi:
E
K
(P) = C
D
K
(C) = P
K
1
K
2 Bản rõ Bản mã Bản rõ gốc

K
1
có thể trùng K

khóa. Việc thay đổi khóa là rất khó và rất dễ bị lộ.
- Khuynh hƣớng cung cấp khóa dài mà nó phải đƣợc thay đổi thƣờng xuyên
cho mọi ngƣời trong khi vẫn duy trì cả tính an toàn lẫn hiệu quả chi phí sẽ cản trở
rất nhiều tới sự phát triển của hệ mật mã cổ điển.
Thuật toán đối xứng có thể đƣợc chia làm hai loại, mật mã luồng (stream
ciphers) và mật mã khối (block ciphers). Mật mã luồng mã hóa từng bit của thông
điệp trong khi mật mã khối gộp một số bit lại và mật mã hóa chúng nhƣ một đơn vị.
Cỡ khối đƣợc dùng thƣờng là các khối 64 bit. Thuật toán tiêu chuẩn mã hóa tân tiến
(Advanced Encryption Standard), đƣợc NIST công nhận tháng 12 năm 2001, sử
dụng các khối gồm 128 bit.
1.1.2. Hệ mật mã bất đối xứng
Vào những năm 1970 Diffie và Hellman đã phát minh ra một hệ mã hóa mới
đƣợc gọi là hệ mã hóa bất đối xứng hay hệ mã hóa công khai.
Thuật toán mã hóa bất đối xứng khác hoàn toàn so với thuật toán mã hóa đối
xứng. Khóa của hệ mã bất đối xứng phải đƣợc gửi trên những kênh thông tin không
an toàn.
Chúng đƣợc thiết kế sao cho khóa sử dụng vào việc mã hóa là khác so với
khóa giải mã. Hơn nữa khóa giải mã không thể tính toán đƣợc từ khóa mã hóa.
Chúng đƣợc gọi với tên hệ thống mã hóa công khai bởi vì khóa để mã hóa có thể
công khai, một ngƣời bất kì có thể sử dụng khóa công khai để mã hóa thông báo,
nhƣng chỉ một vài ngƣời có đúng khóa giải mã thì mới có thể giải mã. Trong nhiều
5

5
Số hóa bởi Trung tâm Học liệu

hệ thống, khóa mã hóa đƣợc gọi là khóa công khai (public key), khóa giải mã
thƣờng đƣợc gọi là khóa riêng (private key).
(P) = EBP
Trong đó:
E: Thuật toán mã hóa
K
B
: khóa công khai
P: Bản tin cần gửi đi
C: Bản tin mã hóa
Công việc này cũng trong thời gian đa thức.
2. Ngƣời nhận B khi nhận đƣợc bản tin mã hóa C với khóa bí mật k
B
thì có thể giải
mã bản tin trong thời gian đa thức
P = Dk
B
(C) = DB[EB(M)]
Trong đó:
D: Thuật toán giải mã
Mã hóa
Mã hóa
6

6
Số hóa bởi Trung tâm Học liệu

k
B
: Khóa bí mật
C: Bản tin mã hóa
3. Nếu kẻ địch biết khóa công khai K

đó theo tính bù sẵn.
7

7
Số hóa bởi Trung tâm Học liệu

Nền tảng để xây dựng khối của DES là sự kết hợp đơn giản của các kỹ thuật
thay thế và hoán vị bản rõ dựa trên khóa. Đó là các vòng lặp. DES sử dụng 16 vòng
lặp, nó áp dụng cùng một kiểu kết hợp của các kỹ thuật trên khối bản vẽ 16 lần.
Thuật toán chỉ sử dụng các phép toán số học và logic trên các số 64 bit, vì
vậy nó dễ dàng thực hiện vào những năm 1970 trong điều kiện công nghệ về phần
cứng lúc bấy giờ. Ban đầu, sự thực hiện các phần mềm kiểu này rất thô sơ, nhƣng
hiện tại thì việc đó đã tốt hơn, và với đặc tính lặp đi lặp lại của thuật toán đã tạo nên
ý tƣởng sử dụng chip với mục đích đặc biệt này.

Hình 1.1. Sơ đồ mã hóa DES
Tóm lại DES có một số đặc điểm sau:
Sử dụng khóa 56 bit
Xử lý khối vào 64 bit, biến đổi khối vào thành khối ra 64 bit.
Mã hóa và giải mã đƣợc sử dụng cùng một khóa.
8

8
Số hóa bởi Trung tâm Học liệu

DES đƣợc thiết kế để chạy trên phần cứng.
DES thƣờng đƣợc sử dụng để mã hóa các dòng dữ liệu mạng và mã hóa
dữ liệu đƣợc lƣu trữ trên đĩa.
1.3. Quy trình mã hóa DES
DES thực hiện trên từng khối 64 bit bản rõ. Sau khi thực hiện hoán vị khởi

R
i
=L
i-1
XOR f(R
i-1,
K
i
)
9

9
Số hóa bởi Trung tâm Học liệu Hình 1.2. Một vòng lặp DES
Quy trình mã hóa của mật mã khối nói chung và theo mã hóa DES nói riêng
đƣợc thực hiện qua 5 giai đoạn sau:

Giai đoạn 1:
Bản rõ chữ
→
Bản rõ số
(Dạng nhị phân)
Giai đoạn 2:
Bản rõ số
→
Các đoạn 64
bit rõ số


- Mã hóa khối: E
k
(M)
- Giải mã khối: M = D
k
(E
k
(M))
Trong đó M là khối thông tin 64 bit và K là khóa 56 bit.

a.Quy trình mã hóa b.Quy trình giải mã
Hình 1.3: Mô phỏng mã hóa (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 khóa), 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.5. Các chế độ mã hóa theo DES
Có 4 chế độ làm việc đã đƣợc phát triển cho DES: Chế độ chuyển mã điện tử
(ECB), chế độ phản hồi mã (CFB), chế độ liên kết khối mã (CBC) và chế độ phản
hồi đầu ra (OFB). Chế độ ECB tƣơng ứng với cách dùng thông thƣờng của mã khối:
với một dãy các khối bản rõ cho trƣớc x
1
, x
2…
(mỗi khối có 64 bit), mỗi x
i
sẽ đƣợc
mã hóa bằng cùng một khóa K để tạo thành một chuỗi các khối bản mã y

1
=e
k
(z
i-1
), i≥1. Dãy bản rõ x
1
x
2…
sau đó sẽ đƣợc mã hóa bằng
cách tính y
i
= x
i
z
i
, i≥1.
Trong chế độ CFB, ta bắt đầu với y
0
= IV( là một véc tơ khởi tạo 64 bit) và
tạo phần tử z
i
của dòng khóa bằng cách mã hóa khối bản mã trƣớc đó. Tức z
i
= e
k
(y
i-
1
), i≥1. Cũng nhƣ trong chế độ OFB: y

Mặt khác ở các chế độ CBC và CFB, nếu một khối bản rõ x
i
bị thay đổi thì
y
i
và tất cả các khối bản mã tiếp theo sẽ bị ảnh hƣởng. Nhƣ vậy các chế độ CBC và
CFB có thể đƣợc sử dụng rất hiệu quả cho mục đích xác thực. Đặc biệt hơn, các chế
độ này có thể đƣợc dùng để tạo mã xác thực bản tin (MAC- Message Authentication
Code). MAC đƣợc gắn thêm vào các khối bản rõ để thuyết phục Bob tin rằng, dãy
13

13
Số hóa bởi Trung tâm Học liệu

bản rõ đó thực sự là của Alice mà không bị Oscar giả mạo. Nhƣ vậy MAC đảm bảo
tính toàn vẹn (hay tính xác thực) của một bản tin ( nhƣng tất nhiên là MAC không
đảm bảo độ mật).
Ta sẽ mô tả cách sử dụng chế độ BCB để tạo ra một MAC. Ta bắt đầu bằng
véc tơ khởi tạo IV chứa toàn số 0. Sau đó dùng chế độ CBC để tạo các khối bản mã
y
1
, ,y
n
theo khóa K. Cuối cùng ta xác định MAC là y
n
, Alice sẽ phát đi dãy các
khối bản rõ x
1
,x
2

. Sau
đó Alice xác định X
n+1
là MAC rồi mã hóa dãy x
1
…x
n+1
bằng khóa thứ hai K
2
để
tạo ra bản mã y
1
…y
n+1
. Khi đó Bob thu đƣợc y
1
…y
n+1
, trƣớc tiên Bob sẽ giải mã
(bằng K
2
) và kiểm tra xem x
n+1
có phải là MAC đối với dãy x
1
…x
n
dùng K
1
hay

1.6. Độ an toàn của DES
Đã có rất nhiều sự nghiên cứu về độ dài của khoá, số vòng lặp, và thiết kế
của hộp S (S-boxes). Hộp S có đặc điểm là khó hiểu, không có bất cứ sự rõ ràng
nào nhƣ tại sao chúng phải nhƣ vậy. Mọi tính toán trong DES ngoại trừ các hộp S
đều tuyến tính, tức việc tính XOR của hai đầu ra cũng giống nhƣ phép XOR hai đầu
vào rồi tính toán đầu ra. Các hộp S chứa đựng thành phần phi tuyến của hệ là yếu tố
14

14
Số hóa bởi Trung tâm Học liệu

quan trọng nhất đối với sự an toàn của hệ thống. Tính bảo mật của một hệ mã hoá
đối xứng là một hàm hai tham số: độ phức tạp của thuật toán và độ dài của khoá.
Giả sử rằng tính bảo mật chỉ phụ thuộc vào độ phức tạp của thuật toán.Có
nghĩa rằng sẽ không có phƣơng pháp nào để phá vỡ hệ thống mật mã hơn là cố gắng
thử mọi khoá có thể, phƣơng pháp đó đƣợc gọi là brute-forceattack. Nếu khoá có độ
dài 8 bít, suy ra sẽ có 2
8
=256 khoá. Vì vậy, sẽ mất nhiều nhất 256 lần thử để tìm ra
khoá đúng. Nếu khoá có độ dài 56 bít, thì sẽ có 2
56
khoá có thể sử dụng. Giả sử một
Suppercomputer có thể thử một triệu khoá trong một giây, thì nó sẽ cần 2000 năm
để tìm ra khoá đúng. Nếu khoá có độ dài 64 bít, thì với chiếc máy trên sẽ cần
600,000 năm để tìm ra khoá đúng trong số 2
64
khoá. Nếu khoá có độ dài 128 bít, thì
sẽ mất 10
25
năm để tìm ra khoá đúng. Vũ trụ chỉ mới tồn tại 10

15
Số hóa bởi Trung tâm Học liệu

các chế độ mã hóa theo DES, độ an toàn của DES. Nội dung trình bày ở chƣơng 1 là
cơ sở lý thuyết cơ bản để vận dụng vào chƣơng 2 và chƣơng 3 trong luận văn.

16

16
Số hóa bởi Trung tâm Học liệu

CHƢƠNG 2
CÁC PHƢƠNG PHÁP THÁM MÃ HỆ MẬT MÃ ĐỐI XỨNG
2.1. Các thuật ngữ cơ bản
2.1.1. Mật mã (Cryptography)
Mật mã là tập hợp mọi phƣơng pháp (hoặc quy tắc) biến đổi nào đó nhằm
chuyển các thông báo (messges) dƣới dạng nhận thức đƣợc nội dung (nhƣ chữ viết,
tiếng nói, hình vẽ, hình ảnh,…) thành dạng bí mật mà ngƣời ngoài cuộc không hiểu
đƣợc nội dung nếu họ không biết đƣợc phƣơng pháp (hoặc quy tắc) biến đổi đó.
Còn mật mã học (Crytology) là một bộ môn khoa học chuyên nghiên cứu về
mật mã và thám mã.
2.1.2. Bản rõ (Plain text)
Ta hiểu rõ tức là một bản thông báo có mang nội dung thông tin mà ngƣời
đọc có thể tìm hiểu đƣợc nó nói cái gì hoặc là nó có ý nghĩa rõ ràng. Bản rõ (bản
thông báo) có thể tồn tại dƣới dạng chữ viết, tiếng nói, hình vẽ, biểu bảng… tƣơng
ứng ta sẽ có khái niệm mã ký tự, mã thoại, mã fax, mã dữ liệu…
Bản rõ thƣờng đƣợc biểu diễn (viết) dƣới dạng một dãy các chữ cái theo quy
tắc cú pháp nào đó hoặc ký hiệu thuộc bảng chữ cái A hữu hạn đƣợc xác định trƣớc.
Để trình bày, ta ký hiệu M là không gian các bản rõ (message space).
Ví dụ: M có thể là gồm các dãy nhị phân, các văn bản tiếng Việt hoặc mã

d
vào bản mã C để tạo ra bản rõ m tƣơng
ứng đƣợc gọi là giải mã (decryption hoặc deciphering).
- Lƣợc đồ mã hóa (enryption scheme) là gồm tập hợp tất cả các hàm mã hóa
E
e
ứng với mỗi e K và tất cả các hàm gải mã D
d
ứng với d K. Hàm D
d
và E
e

phải thỏa mãn hệ thức:
D
d
= E
e
-1
với (e,d) K x K
Tức là m = D
d
(c) = E
e
-1
(E
e
(m)) m M
Nhƣ vậy để ngƣời nhận đích thực dịch đƣợc bản mã từ ngƣời gửi tới thì
đƣơng nhiên ngƣời nhận phải có khóa dịch d và quy tắc dịch D

ngữ tự nhiên đều có những đặc trƣng bất biến mà mã thám viên cần nắm vững để
phục vụ việc phân tích các bản mã. Đó là quy luật tần số, quy luật trùng lặp, quy
luật văn phong, v.v
a. Tần số (Frequency)
Ngƣời ta định nghĩa tần số xuất hiện một ký tự, một nhóm ký tự, một từ hay
một vần v.v trong một văn bản là số lần xuất hiện của ký tự, nhóm ký tự, từ, vần
đó trong văn bản đã cho.
Ngƣời ta có thể tính tần số từ một hoặc nhiều văn bản (thông báo) của một
loại ngôn ngữ nào đó để rút ra những quy luật riêng của ngôn ngữ đó. Có nhiều loại
tần số nhƣ: Tần số từng ký tự (tần số đơn), tần số từng cặp 2 ký tự (tần số bộ đôi).
Ngay tần số bộ đôi cũng có nhiều cách tính khác nhau nhƣ: Tần số bộ đôi thông
thƣờng; Tần số bộ đôi móc xích (concatenate); Tần số bộ k ký tự (k=1, 2, 3, 4 ).
Ngoài ra còn có: tần số từ, tần số vần chữ cái (ví dụ – tion, trong tiếng Anh), tần số
các nhóm nguyên âm, tần số các ký tự đứng đầu từ, tần số ký tự đứng cuối từ. Một
điểm cần lƣu ý là mỗi loại ngôn ngữ tự nhiên khác nhau có các tần số không giống
nhau. Ngay trong một ngôn ngữ, các loại văn bản có tính chất văn học sẽ có các tần
19

19
Số hóa bởi Trung tâm Học liệu

số không hoàn toàn giống nhau. Những tính chất đó ngƣời ta gọi là các đặc trƣng
ngôn ngữ.
Ta lƣu ý rằng, các văn bản khác nhau thƣờng có độ dài (số lƣợng các ký tự
trong văn bản đó) khác nhau. Do đó khái niệm tần số nhƣ định nghĩa trên có nhiều
trƣờng hợp rất khó trong thực hành. Vì vậy ngƣời ta đƣa ra khái niệm tần số tƣơng
đối (tần suất - relative frequency). Tần suất của một ký tự x nào đó trong văn bản là
số lần xuất hiện ký tự đó chia cho độ dài của văn bản đó. Còn tần suất bộ đôi móc
xích xy nào đó trong một văn bản là số lần xuất hiện bộ đôi đó có trong văn bản
chia cho độ dài của văn bản trừ đi một. Ví dụ, giả sử văn bản có độ dài n, khi đó số