ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

TRƯƠNG HÀ DIỆP

NGHIÊN CỨU TÌM HIỂU
HỆ MÃ HÓA ĐỒNG CẤU VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

THÁI NGUYÊN - 2016


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

TRƯƠNG HÀ DIỆP

NGHIÊN CỨU TÌM HIỂU
HỆ MÃ HÓA ĐỒNG CẤU VÀ ỨNG DỤNG
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Người hướng dẫn khoa học: TS HỒ VĂN CANH

THÁI NGUYÊN - 2016


i

Thái Nguyên, ngày 28 tháng 12 năm 2016
HỌC VIÊN

Trương Hà Diệp


iii

MỤC LỤC

LỜI CAM ĐOAN ...................................................................................... i
LỜI CẢM ƠN ........................................................................................... ii
MỤC LỤC................................................................................................iii
MỤC CÁC HÌNH VẼ, ĐỒ THỊ .............................................................. vi
MỞ ĐẦU................................................................................................... 1
CHƯƠNG 1 .............................................................................................. 3
MẬT MÃ CỔ ĐIỂN VÀ HỆ MẬT MÃ ĐỒNG CẤU ............................ 3
1.1 Khái quát hệ mật mã .......................................................................... 3
1.1.1 Khái niệm ........................................................................................ 3
1.1.2 Định nghĩa ........................................................................................ 3
1.1.3 Những yêu cầu đối với hệ mật mã ................................................... 4
1.2 Một số hệ mật mã đơn giản ................................................................. 5
1.2.1 Mã dịch vòng ( shift cipher) ............................................................ 5
1.2.1.1 Định nghĩa (modulo): Định nghĩa về đồng dư ............................. 5
1.2.1.2 Định nghĩa mã dịch vòng:............................................................. 6
1.2.2 Mã thay thế (MTT) ......................................................................... 7
1.2.3 Mã Anffine ........................................................................................ 8
1.2.3.1 Định lý (đồng dư thức) ................................................................. 9
1.2.3.2 Định nghĩa (hàm Euler) ................................................................ 9
1.2.3.3 Định nghĩa (phần tử nghich đảo trong phép nhân) ..................... 10

2.1.2.4 Ví dụ ............................................................................................ 32
2.1.3 Quá trình giải mã .......................................................................... 36
2.1.3.1 Thuật toán ................................................................................... 37


v

2.1.3.2 Chứng minh thuật toán ............................................................... 37
2.1.4 Ưu nhược điểm của hệ mật DES ................................................... 39
2.1.4.1 Ưu điể m....................................................................................... 39
2.1.4.2 Nhược điểm của DES ................................................................ 39
2.1.5 Độ an toàn của DES ....................................................................... 41
2.1.5.1 Các đặc trưng an toàn cơ bản của một hệ mã khối ..................... 41
2.1.5.2 Độ an toàn của DES trước một vài phương pháp tấn công phá mã42
2.2 Hệ mật IDEA .................................................................................... 43
2.2.1 Mô tả hệ mật IDEA ........................................................................ 43
2.2.2 Các phép toán sử dụng trong IDEA ............................................... 43
2.2.3 Mã hoá và giải mã trong IDEA...................................................... 45
2.2.3.1 Mã hoá......................................................................................... 45
2.2.4 Quá trình làm việc của một Modul ................................................ 51
CHƯƠNG 3 NGHIÊN CỨU PHƯƠNG PHÁP MÃ HÓA TỰ ĐỒNG
CẤU MỞ RỘNG KHÔNG GIAN KHÓA CHO CÁC MÃ CỔ ĐIỂN . 55
3.1 Mở đầu .............................................................................................. 55
3.2 Nội dung phương pháp ...................................................................... 55

3.2.1 Khái niệm, định nghĩa .................................................................... 55
3.2.2 Thuật toán mã hóa .......................................................................... 55
3.2.3. Ví dụ .............................................................................................. 55
3.2.4 Thuật toán giải mã ......................................................................... 59
3.3 Đánh giá độ an toàn của thuật toán ................................................... 61

Hình 3.2: Giải mã thông điệp.................................................................. 61


vii

DANH MỤC BẢNG BIỂU

Bảng 2.2 Bảng chọn E bít ....................................................................... 26
Bảng 2.3 Hoán vi ̣IP-1 .............................................................................. 27
Bảng 2.5 Hoán vi ̣PC - 2 ......................................................................... 27
Bảng 2.7 8 hô ̣p S-Box ............................................................................ 31
Bảng 2.8 Phép hoán vị P ......................................................................... 31
Bảng2.9 16 vòng lặp mã ........................................................................ 36
Bảng 2.10 Các khóa yếu của DES ........................................................... 40
Bảng 2.11 Các khóa nửa yếu của DES .................................................... 40


1

MỞ ĐẦU
1. Đặt vấn đề
Để đảm bảo các thông tin quan trọng liên quan đến Quốc phòng, An ninh và
Thương mại, người ta sử dụng công nghệ mật mã. Có hai loại hệ mật mã được dùng
là mật mã khóa đối xứng và mật mã khóa bất đối xứng (Asymmetric key). Hệ thống
mật mã bất đối xứng chủ yếu được sử dụng trong môi trường chữ ký số (digital
signatures), trong xác thực và trong việc trao đổi các khóa mã đối xứng (symmetric
keys). Mật mã đối xứng đóng vai trò quan trọng trong lĩnh vực bảo mật dữ liệu. Mật
mã đối xứng có hai loại chính là mật mã hiện đại như mật mã DES (Data
Enecryption Standard), mật mã AES (Advanced Encryption Standard), mật mã
IDEA (International Data Encryption Algorithm)… và mật mã truyền thống. Mật

an toàn cao.


3

CHƯƠNG 1
MẬT MÃ CỔ ĐIỂN VÀ HỆ MẬT MÃ ĐỒNG CẤU
1.1 Khái quát hệ mật mã
1.1.1 Khái niệm
- Chức năng cơ bản của mật mã là tạo ra khả năng liên lạc trên một kênh
không mật cho hai người sử dụng (tạm gọi là A và B) sao cho đối phương (C)
không thể hiểu được thông tin được truyền đi.
- Kênh liên lạc có thể là một đường dây điện thoại hoặc một mạng máy tính.
- Thông tin mà A muốn gửi cho B bản rõ có thể là một văn bản tiếng Anh, các
dữ liệu bằng số hoặc bất cứ tài liệu nào có cấu trúc tuỳ ý.
- A sẽ mã hoá bản rõ bằng một khóa đã được xác định trước và gửi bản
mã kết quả trên kênh. C có bản mã thu trộm được trên kênh song không thể xác
định nội dung của bản rõ, nhưng B (người đã biết khoá mã) có thể giải mã và
thu được bản rõ.
1.1.2 Định nghĩa
Một hệ mật là một bộ 5 (P,C, K, E, D) thoả mãn các điều kiện sau:
1. P là một tập hữu hạn các bản rõ có thể.
2. C là một tập hữu hạn các bản mã có thể.
3. K (không gian khoá) là tập hữu hạn các khoá có thể.
4. Đối với mỗi k  K có một quy tắc mã ek: P  C và một quy tắc v giải

mã tương ứng dk  D. Mỗi ek: P  C và dk: C  P là những hàm sao
cho: dk(ek (x)) = x với mọi bản rõ x  P.
Trong đó, chúng ta cần lưu ý tính chất 4: Nội dung của nó là nếu một bản rõ x
được mã hoá bằng ek và bản mã nhận được sau đó được giải mã bằng dk thì ta phải

k
Kênh an toàn

k
Nguồn khoá

Hình 1.1. Kênh liên lạc
Rõ ràng là trong trường hợp này hàm mã hoá phải là hàm đơn ánh (tức là ánh xạ

1-1), nếu không việc giải mã sẽ không thực hiện được một cách tường minh.

Ví dụ: y = ek(x1) = ek(x2), trong đó x1  x2, thì B sẽ không có cách nào để biết
liệu bản rõ là x1 hay x2 .
1.1.3 Những yêu cầu đối với hệ mật mã
Cung cấp một mức cao về tính bảo mật, tính toàn vẹn, tính chống chối bỏ và
tính xác thực:
 Tính bảo mật: Bảo đảm bí mật cho các thông báo và dữ liệu bằng việc che
dấu thông tin nhờ các kỹ thuật mã hóa.
 Tính toàn vẹn (integrity): Bảo đảm với các bên rằng bản tin không bị thay
đổi trên đường truyền tin.
 Tính không thể chối bỏ (Non-repudiation): Có thể xác nhận rằng tài liệu đã
đến từ ai đó, ngay cả khi họ cố gắng từ chối nó.
 Tính xác thực (Authentication): Cung cấp hai dịch vụ:
o

Nhận dạng nguồn gốc của một thông báo và cung cấp một vài bảo

đảm rằng nó là đúng sự thực.



7. Phép nhân là kết hợp, nghĩa là với a, b, c  Zm, (ab)c = a(cb)
8. 1 là phần tử đơn vị của phép nhân, tức là với bất kỳ a  Zm
9. Phần tử nghịch đảo của phép cộng của phần tử bất kì (a  Zm) là m-a, nghĩa
là a + (m-a) = (m-a) + a = 0 với bất kì a  Zm.
10. Phép nhân có tính chất phân phối đối với phép cộng, tức là đối với a, b, c


6
 Zm, (a+b)c = (ac)+(bc) và a(b+c) = (ab) + (ac)

Vì phần tử ngược của phép cộng tồn tại trong Zm nên cũng có thể trừ các phần
tử trong Zm. Ta định nghĩa a-b trong Zm là a+m-b mod m. Một cách tương tự có thể
tính số nguyên a-b rồi rút gọn theo modulo m.
Ví dụ: Để tính 11-18 trong Z31, ta tính 11+13 mod 31 = 24. Ngược lại, có thể
lấy 11-18 được -7 rồi sau đó tính -7 mod 31 = 24.
1.2.1.2 Định nghĩa mã dịch vòng:
Mã dịch vòng được xác định trên Z26 (do có 26 chữ cái trên bảng chữ cái tiếng
Anh) mặc dù có thể xác định nó trên Zm với modulus m tuỳ ý. Dễ dàng thấy rằng,
mã dịch vọng (MDV) sẽ tạo nên một hệ mật như đã xác định ở trên, tức là dK
(eK(x)) = x với mọi x  Z26.
Cho P = C = K = Zn
Với mỗi khóa k  K, định nghĩa:
ek (x)= (x + k) mod n và
dk (y)= (y - k) mod n với x, y  Zn
E={ ek , k  K} và D={ dk, k  K}
Hình 1.2 Mã dịch vòng
Ta sẽ sử dụng MDV (với modulo 26) để mã hoá một văn bản tiếng Anh thông

thường bằng cách thiết lập sự tương ứng giữa các kí tự và các thặng dư theo modulo
26 như sau: A  0, B  1, . . ., Z  25. Vì phép tương ứng này còn dùng trong một

7

9

10 11 12

N O

P

Q

R

S

T

U V W X Y Z

8

13 14 15 16 17 18 19 20 21 22 23 24 25
Ví dụ: Dùng khoá k = 9 để mã hoá dòng thư: “toinaydichoi” dòng thư đó tương ứng
với dòng số
T

o

i


3

8

2

7

14

8


7

Qua phép mã hoá e9: cộng 9 vào mỗi giá trị rồi rút gọn theo tổng modulo 26 ta có:
2

23

17

22

9

7

12


x

r

Bản mã sẽ là: “qnwcxrcqdkjh”
Để giải được bản mã này, trước tiên người nhận biến đổi bản mã này thành
dãy các số nguyên rồi trừ đi 9 (rút gọn theo modulo 26) và cuối cùng biến đổi lại
dãy này thành các ký tự.
Cách đây 2000 năm mã dịch chuyển đã được Julius Ceasar sử dụng Với khoá k
= 3 mã dịch vòng được gọi là mã Ceasar.
Tập khoá phụ thuộc vào Zm với m là số khoá có thể. Trong tiếng anh tập khóa
chỉ có 26 khóa có thể, việc thám mã có thể được thực hiện bằng cách duyệt tuần tự
26 khóa đó, vì vậy độ an toàn của mã dịch chuyển rất thấp.
1.2.2 Mã thay thế (MTT)
Trên thực tế mã thay thế có thể lấy cả P và C đều là bộ chữ cái tiếng anh, gồm 26

chữ cái. Ta dùng Z26 trong MDV vì các phép mã và giải mã đều là các phép toán đại
số. Tuy nhiên, trong MTT, thích hợp hơn là xem phép mã và giải mã như các hoán
vị của các kí tự.
Cho P = C = Zn. K là tập hợp tất cả các hoán vị của n phần tử 0, 1, ..., n-1. Như
vậy, mỗi khóa   K là một hoán vị của n phần tử 0, 1, ..., n-1.
Với mỗi khóa   K, định nghĩa :
e (x)= (x) và
d(y)=-1(y) với x,y  Zn
E={e,  K} và D={D, K}
Hình 1.3 Mã thay thế
Sau đây là một ví dụ về phép hoán vị ngẫu nhiên  tạo nên một hàm mã hoá (cũng

như trước, các kí hiệu của bản rõ được viết bằng chữ thường còn các kí hiệu của

V

g
O
t
M

h
G
u
U

i
Z
v
E

j
Q
w
K

k
W
x
J

l
B
y


J

K

L

M

d

l

r

y

v

O

h

e

z

x

w


b

g

f

j

q

N

m

u

s

k

a

c

i

Mỗi khoá của MTT là một phép hoán vị của 26 kí tự. Số các hoán vị này là 26!,
lớn hơn 4 x1026 là một số rất lớn. Bởi vậy, phép tìm khoá vét cạn không thể thực hiện
được, thậm chí bằng máy tính. Tuy nhiên, sau này sẽ thấy rằng MTT có thể dễ dàng bị


(y  Z26 ).

1.2.3.1 Định lý (đồng dư thức)
Đồng dư thức ax  b mod m chỉ có một nghiệm duy nhất x  Zm với mọi b  Zm khi

và chỉ khi UCLN(a,m) = 1.
Vì 26 = 2 x 13 nên các giá trị a  Z26 thoả mãn UCLN(a, 26) = 1 là a = 1, 3, 5, 7, 9,
11, 13, 15, 17, 19, 21, 23 và 25. Tham số b có thể là một phần tử bất kỳ trong Z26. Như
vậy, mã Affine có 13 x 25 = 325 (vì k = 0 bị loại) khoá có thể (dĩ nhiên con số này quá

nhỏ để bảo đảm an toàn).
Bây giờ ta sẽ xét bài toán chung với modulo m. Ta cần một định nghĩa khác
trong lý thuyết số.
1.2.3.2 Định nghĩa (hàm Euler)
Giả sử a  1 và m  2 là các số nguyên. UCLN(a,m) = 1 thì ta nói rằng a và m là
nguyên tố cùng nhau. Số các số nguyên trong Zm nguyên tố cùng nhau với m thường
được ký hiệu là  (m) ( hàm này được gọi là hàm Euler).
Một kết quả quan trọng trong lý thuyết số cho ta giá trị của  (m) theo các thừa số trong
phép phân tích theo luỹ thừa các số nguyên tố của m. (Một số nguyên p  1 là số nguyên tố

nếu nó không có ước dương nào khác ngoài 1 và p. Mọi số nguyên m >1 có thể
phân tích được thành tích của các luỹ thừa các số nguyên tố theo cách duy nhất. Ví
dụ 60 = 23 x 3 x 5 và 98 = 2 x 72).
Ta sẽ ghi lại công thức cho (m) trong định lí sau:
n

Định lý: Giả sử m   pie

i

(c)

Giả sử m, n là hai số nguyên dương tùy ý sao cho UCLN(m, n)=1 (tức m, n

nguyên tố cùng nhau). Khi đó,  (m,n) =  (m).  (n)
Ví dụ m = 15, n = 16 Khi đó  (m,n) =  (15,16) =  (15).  (16) = 8.8 = 64.
(d) Nếu m = pk với p là số nguyên tố, thì  (m) =  (pk) = pk-1(p-1).
Từ đó suy ra rằng  (2) =1,  (1) = 0
1.2.3.3 Định nghĩa (phần tử nghich đảo trong phép nhân)
Giả sử a  Zm. Phần tử nghịch đảo (theo phép nhân) của a là phần tử a-1  Zm sao cho

aa-1  a-1a  1 (mod m).
Bằng các lý luận tương tự như trên, có thể chứng tỏ rằng a có nghịch đảo theo modulo m
khi và chỉ khi UCLN(a, m) =1, và nếu nghịch đảo này tồn tại thì nó phải là duy nhất. Ta cũng
thấy rằng, nếu b = a-1 thì a = b-1. Nếu p là số nguyên tố thì mọi phần tử khác không của ZP đều
có nghịch đảo. Một vành trong đó mọi phần tử khác 0 đều có nghịch đảo được gọi là

một trường.
Bằng phương pháp thử và sai ta có thể tìm được các nghịch đảo của các phần tử nguyên
tố cùng nhau với 26: 1-1 = 1, 3-1 = 9, 5-1 = 21, 7-1 = 15, 11-1 = 19, 17-1 =23, 25-1 = 25. (Có

thể dễ dàng kiểm chứng lại điều này, ví dụ: 7 x 15 = 105  1 mod 26, bởi vậy 7-1 = 15).
Xét phương trình đồng dư y  ax+b (mod 26).
Phương trình này tương đương với:
ax  y - b ( mod 26).


11

Vì UCLN(a, 26) =1 nên a có nghịch đảo theo modulo 26. Nhân cả hai vế của


a3

b1

b2

b3 c1

c2

4

1

-10 2

-2

21

10 1

0

42 0

1

2

Ví dụ 2: Cho m = 95, n = 8.
Quá trình tính toán được cho trong bảng sau:
q a1 a2
11 1 0
1 0 1
7 1 -11
Vậy x = -1, y =12, k =1.

a3
95
8
7

b1
0
1
-1

b2
1
-11
12

b3
8
7
1

c1
1

= x +45 -19
= x.
Để minh hoạ, ta hãy mã hoá bản rõ "hot". Trước tiên biến đổi các chữ h, o, t
thành các thặng dư theo modulo 26. Ta được các số tương ứng là 7, 14 và 19. Bây
giờ sẽ mã hoá:


13

7 x 7 +3 mod 26 = 52 mod 26 = 0
7 x 14 + 3 mod 26 = 101 mod 26 =23
7 x 19 +3 mod 26 = 136 mod 26 = 6
Bởi vậy 3 ký hiệu của bản mã là 0, 23 và 6 tương ứng với xâu ký tự AXG.

Việc thử tất cả các khoá để thám mã trong trường hợp này tuy khá mất thì giờ
nếu tính bằng tay nhưng không khó khăn gì nếu dùng máy tính.
Do vậy, mã Apphin cũng không phải là mã an toàn.
Chú ý: khi a = 1 ta có mã dịch vòng.
1.2.4 Mã Vigenere
m

Mã Vigenere: (P, C, K, E, D) Cho m là số nguyên dương. P = C = K = Z26
với mỗi khoá k = (k1, k2, …, km) є K có:
eK(x1, ..., xm ) = ( x1+k1, ...., xm+ km ) mod 26
dK(y1, ..., ym ) = ( y1 - k1 , ..., ym - km ) mod 26
với mỗi x = (x1, ..., xm ) ∈ P , y = (y1, ..., ym ) ∈ C , K = (k1, ..., km)∈ K .
các phép cộng phép trừ đều lấy theo modulo 26
Hình 1.5. Phương pháp mã hóa Vigenere

Ví dụ: Giả sử m = 6 và khoá k là từ CIPHER - tức k = (2, 8, 15, 7, 4, 17).


8

12

0

24

3

8

2

7

14

8

k

2

8

15

7


5

16

17

14

18

25

v

W

x

u

e

p

f

q

r

Ví dụ nếu m = 2 ta có thể viết một phần tử của bản rõ là x = (x1, x2) và một phần tử
của bản mã là y = (y1, y2). Ở đây, y1cũng như y2 đều là một tổ hợp tuyến tính của
x1và x2. Chẳng hạn, có thể lấy
y1 = 11x1+ 3x2
y2 = 8x1+ 7x2
Tất nhiên có thể viết gọn hơn theo ký hiệu ma trận như sau:
11 8 
(y1 y2) = (x1 x2) 

3 7 
Nói chung, có thể lấy một ma trận K kích thước m x m làm khoá. Nếu một phần tử ở hàng
i và cột j của K là ki,j thì có thể viết K = (ki,j), với x = (x1, x2, . . . ,xm)  P và K  K , ta tính

y = eK(x) = (y1, y2, . . . ,ym) như sau:
 K1,1

K
(y1, . . ., ym) = (x1, …., xm)  2,1
...

 K m,1

K1,2 ... K1,m 

K 2,2 ... K 2,m 
... ... ... 

K m,2 ... K m,m 

Nói một cách khác y = xK.

A 1  (det A) 1 

  a2,1 a1,1 

Ví dụ: Có 1 ma trận K
11 8 
det 
  11 x 7 - 8 x 3 mod26
3 7
= 77 - 24 mod26  53mod26
1
Vậy ma trận K có nghịch đảo.

1.2.5.5 Định nghĩa mật mã Hill
Cho ̣n số nguyên dương m. Đinh
̣ nghiã : P = C = (Z26)m. Và K là tâ ̣p hơ ̣p các ma
trâ ̣n m x m khả nghich
̣ trên Z26
Với mỗi khóa k K ta xác định:
ek(x) = xK
và dk(y) = yK-1
Tất cả các phép toán thực hiện trong Z26
Hình 1.6. Mật mã Hill

1.2.6 Mã hóa hoán vị
Những phương pháp mã hóa nêu trên đều dựa trên ý tưởng chung: thay thế mỗi
ký tự trong thông điệp nguồn bằng một ký tự khác để tạo thành thông điệp đã được
mã hóa.Ý tưởng chính của phương pháp mã hóa hoán vị (Permutation) là vẫn giữ



EESLSH | SALSES | LSHBLE | HSYEET | HRAEOS
Như vậy bản mã là:
EESLSH SALSES LSHBLE HSYEET HRAEOS
Để giải bản mã này ta dùng phép hoán vị  -1.
Phương pháp mã hóa hoán vị là một trường hợp đặc biệt của mã hóa Hill. Với
mỗi hoán vị  của tập hợp {1, 2, …, m}, ta xác định ma trận k = (ki,j) theo công thức:

(ma trận hoán vị là ma trận trong đó mỗi hàng và mỗi cột chỉ có một số "1", còn tất
cả các giá trị khác đều là số "0". Ta có thể thu được một ma trận hoán vị từ ma trận
đơn vị bằng cách hoán vị các hàng hoặc cột).