ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN BÁ THÁI NGHIÊN CỨU LƯỢC ĐỒ CHIA SẺ BÍ MẬT VÀ
ỨNG DỤNG CỦA CHÚNG VÀO VIỆC
THI TUYỂN SINH ĐẠI HỌC Nghành : Công nghệ Điện tử - Viễn thông
Chuyên nghành : Kỹ thuật Điện tử
Mã số : 60 52 70 LUẬN VĂN THẠC SỸ

NGƯỜI HƯỚNG DẪN KHOA HỌC: TS Hồ Văn Canh
Hà nội, ngày 20 tháng 05 năm 2011
Tác giả luận văn

Nguyễn Bá Thái
- -


2. 2.2.1. Các biến trong hàm f: 26
2.2.2.2 Cách tính hàm f: 30
2.2.3 Xác định bản mã y: 35
2.3 Giải mã DES 43
2.3.1 Thuật toán 43
2.3.2 Chứng minh thuật toán 43
2.4 Các vấn xung quanh DES 46
2.4.1 Những ý kiến phản hồi 46
2.4.2 DES trong thực tế 47
2.4.3. Một vài kết luận về mã DES 48
CHƯƠNG 3. CÁC SƠ ĐỒ CHIA SẺ BÍ MẬT 49
3.1 Khái niệm về chia sẻ bí mật: 49
3.2 Sơ đồ chia sẻ bí mật 50
3.2.1 Khái niệm “Sơ đồ chia sẻ bí mật”: 50
3.2.2 Định nghĩa: 50
3.3 Cấu trúc truy nhập và sơ đồ chia sẻ bí mật 55
3.3.1 Định nghĩa sơ đồ chia sẻ bí mật hoàn thiện 55
- -

43.3.2 Định nghĩa tập hợp thức” tối thiểu 56
3.4 Mạch đơn điệu: 56
3.4.1 Định nghĩa( mạch đơn điệu): 56
3.4.2 Chia sẻ Khóa bí mật dựa vào “ mạch đơn điệu” 57
CHƯƠNG 4. ỨNG DỤNG THUẬT TOÁN DES VÀ LƯỢC ĐỒ CHIA SẺ BÍ
MẬT VÀO THI TUYỂN SINH 61
4.1 Các ứng dụng: 61
4.2 Quy trình thực hiện giải bài toán: 61

Trên thế giới có rất nhiều quốc gia, nhiều nhà khoa học nghiên cứu về vấn đề
bảo mật, đưa ra nhiều thuật toán với mục đích thông tin truyền đi không bị lấy
cắp hoặc nếu bị lấy cắp thì cũng không sử dụng được.Trong đề tài của em đưa ra
một thuật toán đó là thuật toán DES (Data encryption standar) đây là thuật toán
chuẩn của mỹ, được mỹ và nhiều nước trên thế giới sử dụng, thuật toán này đã
được đưa vào sử dụng nhiều năm nhưng vẫn giữ được tính bảo mật của nó. Tuy
nhiên với công nghệ phát triển như hiện nay thì thuật toán DES trở lên không
được an toàn tuyệt đối nữa, người ta đã đưa ra thuật toán 3DES về nguyên tắc
thuật toán 3DES dựa trên nền tảng của thuật toán DES nhưng số bít được mã
hóa tăng lên.

Mã hóa và các lược đồ chia sẻ bí mật có thể được ứng dung trong rất nhiều lĩnh
vực ví dụ: phát hành thẻ ATM trong ngân hàng, đấu thầu từ xa, trong thi tuyển
sinh, trong lĩnh vực quân sự….Trong đề tài của em đề cập tới một lĩnh vực đó là
ứng dụng trong thi tuyển sinh đại học.

Vấn đề thi tuyển sinh đại học ở nước ta trở thành gánh nặng cho nghành Giáo
Dục và các ban nghành khác liên quan. Nó làm tổn hại về kinh tế và công sức
không chỉ đối các ban nghành tham gia tổ chức kỳ thi mà ngay cả đối với các thí
sinh dự thi, nhưng đó là điều bắt buộc phải được tổ chức hàng năm. Do vậy làm
sao để giảm thiểu các khâu trong thi tuyển sinh mà vẫn đảm bảo tính công bằng
và chính xác là điều cần thiết, theo tôi để làm được điều đó ta nên ứng dụng
công nghệ thông tin vào việc thi tuyển sinh đại học, một trong các ứng dụng đó
là ứng dụng LƯỢC ĐỒ CHIA SẺ BÍ MẬT vì nó đảm bảo được tính bí mật và
chính xác mà trong thi tuyển sinh hai điều đó là quan trọng nhất.

Phạm vi luận văn đề cập đến vấn đề mật mã, thuật toán DES, lược đồ chia sẻ bí
mật và ứng dụng của chúng trong thi tuyển sinh.

Luận văn gồm 4 chương:


- -

7
CHƯƠNG 1. MẬT MÃ CỔ ĐIỂN
1.1 KHÁI NIỆM VÀ ĐỊNH NGHĨA VỀ 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)

P



C
và một quy tắcv giải
mã tương ứng d
k


D. Mỗi e
k
:
P



C
và

d
k
:
C



P
là những hàm
sao cho:




P
, 1  i 
n. Mỗi x
i
sẽ được mã hoá bằng quy tắc mã e
k
với khoá K xác định trước đó.
Bản mã thu được là:
y = y
1
,y
2
,. . .,y
n
Trong đó y
k
=e
k
(x
i
) i=1,2,…,n. còn kєK
Khi Bob nhận đươc y
1
,y
2
,. . .,y
n

(x
2
)
trong đó x
1
 x
2
, thì B sẽ không có cách nào để biết liệu bản rõ là x
1
hay x
2 .

Hình 1.1. Kênh liên lạc

C
B
ộ giải m
ã

B
ộ m
ã hoá

B

A

Kênh an toàn
Nguồn khoá
x

Ví dụ tính 11 13 trong Z
16
. Tương tự như với các số nguyên ta có 11
13 = 143. Để rút gọn 143 theo modulo 16, ta thực hiện phép chia bình thường:
143 = 8  16 + 15, bởi vậy 143 mod 16 = 15 trong Z
16
.
Các định nghĩa trên phép cộng và phép nhân Z
m
thảo mãn hầu hết các quy
tắc quen thuộc trong số học. Sau đây ta sẽ liệt kê mà không chứng minh các tính
chất này:
1. Phép cộng là đóng, tức với bất kì a,b  Z
m
,a +b  Z
m

2. Phép cộng là giao hoán, tức là với a,b bất kì  Z
m

a+b = b+a
3. Phép cộng là kết hợp, tức là với bất kì a,b,c  Z
m

(a+b)+c = a+(b+c)
4. 0 là phần tử đơn vị của phép cộng, có nghĩa là với a bất kì  Z
m

a+0 = 0+a = a
5. Phép nhân là đóng , tức là với a,b bất kì  Z

Vì phần tử ngược của phép cộng tồn tại trong Z
m
nên cũng có thể trừ các
phần tử trong Z
m
. Ta định nghĩa a-b trong Z
m
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 Z
31
, 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 Z
26
(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 Z
m
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à d
K
(e
K
(x)) = x với mọi x Z
26
.

Hình 1.2: Mã dịch vòng

11

13 14 15 16 17 18 19 20 21 22 23 24 25

- -

12

Ví dụ 1.1:
Giả sử khoá cho MDV là K = 11 và bản rõ là:
wewillmeetatmidnight
Trước tiên biến đổi bản rõ thành dãy các số nguyên nhờ dùng phép tương
ứng trên. Ta có:
22 4 22 8 11 11 12 4 4 19
0 19 12 8 3 13 8 6 7 19
sau đó cộng 11 vào mỗi giá trị rồi rút gọn tổng theo modulo 26
7 15 7 19 22 22 23 15 15 4
11 4 23 19 14 24 19 17 18 4
Cuối cùng biến đổi dãy số nguyên này thành các kí tự thu được bản mã
sau:
HPHTWWXPPELEXTOYTRSE
Để giải bản mã này, trước tiên, Bob sẽ biến đổi bản mã thành dãy các số
nguyên rồi trừ đi cho 11 ( 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ự.
Nhận xét rằng, MDV (theo modulo 26) là không an toàn vì nó có thể bị
thám theo phương pháp vét cạn. Do chỉ có 26 khoá nên dễ dàng thử mọi khoá d
K

có thể cho tới khi nhận được bản rõ có nghĩa.
1.2.2 Mã thay thế (MTT)

trong đó

-1
là
hoán v
ị ng
ư
ợc của

.

- -

13Sau đâ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 bản mã là chữ in hoa).

a b c d e F g h i j k l M
X N Y A H P O G Z Q W B T

n o p q r S t u v w x y Z
S F L R C V M U E K J D I

Như vậy, e

(a) = X, e


Để việc giải mã có thể thực hiện được, yêu cầu cần thiết là hàm Affine
phải là đơn ánh. Nói cách khác, với bất kỳ y  Z
26
, ta muốn có đồng nhất thức
sau:
ax + b  y (mod 26)
phải có nghiệm x duy nhất. Đồng dư thức này tương đương với:
ax  y-b (mod 26)
Vì y thay đổi trên Z
26
nên y-b cũng thay đổi trên Z
26
. Bởi vậy, ta chỉ cần nghiên
cứu phương trình đồng dư:
ax  y (mod 26) (y Z
26
).
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

Z
m
với mọi b

Z
m
khi và chỉ khi UCLN(a,m) = 1.


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 = 2
3
 3  5 và 98 = 2  7
2
).
Ta sẽ ghi lại công thức cho (m) trong định lí sau:
Định lý
Giả sử m =


n
i
e
i
i
p
1

Trong đó các số nguyên tố p
i
khác nhau và e
i
>0 , 1

i

n. Khi đó

)(m

1
=>(60) = (2
2
-2
1
)( 3
1
-3
0
)(5
1
-5
0
) = 16
và số các khoá trong mã Affine là:
16 x 60=960.
Một vài tính chất đáng lưu ý của hàm Erler().
(a) Nếu p là số nguyên tố thì
(p)=p-1.
(b) Nếu p,q là hai số nguyên tố khác nhau.Khi đó,
(p.q)= (p). (q)=(p-1)(q-1)
(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=p
k
với p là số nguyên tố ,thì
(m)= (p

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 Z
P
đề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  15 =
105  1 mod 26, bởi vậy 7
-1
= 15).

Cho m,n là hai số nguyên dương
Ta hãy tìm x,y,k sao cho mx + ny =k.
- -

17Đầu vào (input) : m,n (giả sử m>n).
đầu ra: x,y,k.
cho (a
1
,a
2
,a
3
),( b
1
,b
2
,b
3
),(c
1
,c
2
,c
3
) là 3vectơ
Bước 1: (a
1

3
]; (là phần nguyên của a
3
/b
3
, tức q là số nguyên lớn
nhất nhưng không vượt quá a
3
/b
3
) và (c
1
,c
2
,c
3
)← (a
1
,a
2
,a
3
)-q( b
1
,b
2
,b
3
);
(a
Vậy x=1, y=-10 và k=2.
Ví dụ 2 : m=95, n=8.
Quá trình tính toán được cho trong bảng sau:

Vậy x=-1, y=12, k=1.

q a
1
a
2
a
3
b
1
b
2
b
3
c
1
c
2
c
3

11 1 0 95 0 1 8 1 -11 7
1 0 1 8 1 -11 7 -1 12 1
7 1 -11 7 -1 12 1 8 -95 0

2 0 1 4 1 -10 2 -2 21 0
1
-
10 2
-
2
21 0

- -

18Chú ý : số trong ô a
2
chính là nghịch đảo của 8mod95 (tức số y là nghịch
đảo của n theo module m) (Trong trường hợp k=1).
Thật vậy ta có 12.8≡1mod95 Do đó từ định nghĩa 12 là nghịch đảo của 8
theo module95 (vì UCLN(8,95)=1 nên tồn tại nghịch đảo của 8 theo mod95).
Hình 1.4 cho mô tả đầy đủ về mã Affine.

Hình 1.4 Mật mã Affine
Ví dụ 1.3
Giả sử K = (7,3). Như đã nêu ở trên, 7
-1
mod 26 = 15. Hàm mã hoá là
e
K
(x) = 7x+3
Và hàm giải mã tương ứng là:

Cho
P = C
= Z
26
và giả sử

P
= { (a,b)  Z
26
 Z
26
: UCLN(a,26) =1 }
Với K = (a,b) 
K
, ta định nghĩa:
e
K
(x) = ax +b mod 26
và
d
K
(y) = a
-1
(y-b) mod 26,
x,y  Z
26

- -

19

1
và x
2
. Chẳng hạn, có thể lấy
y
1
= 11x
1
+ 3x
2

y
2
= 8x
1
+ 7x
2

Tất nhiên có thể viết gọn hơn theo ký hiệu ma trận như sau
Nói chung, có thể lấy một ma trận K kích thước m  m làm khoá. Nếu một phần
tử ở hàng i và cột j của K là k
i,,j
thì có thể viết K = (k
i,,j
), với x = (x
1
, x


k
1,1
k
1,2
k
1,m

k
2,1
k
2,2
k
2,m

. .
k
m,1
k
m,2
k
m,m(y
1
,. . .,y
m
)=(x
1

A = I
m
. Không phải mọi ma trận đều có
nghịch đảo, nhưng nếu tồn tại thì nó duy nhất.
Với các định nghĩa trên, có thể dễ dàng xây dựng công thức giải mã đã
nêu: Vì y = xK, ta có thể nhân cả hai vế của đẳng thức với K
-1
và nhận được:
yK
-1
= (xK)K
-1
= x(KK
-1
) = xI
m
= x
1.2.4.3 Định nghĩa (Định thức của ma trận):
Định thức của ma trận A = (a
,i j
) cấp 2

2 là giá trị
det A = a
1,1
a
2,2
- a
1,2
a

0 1

A
-1
= (det A)
-1

a
2,2
-a
1,2

-a
2,1
a
1,1 K =
11 8 3 7
- -

21det K = 11x7 – 8x3 mod 26 = 77 – 24 mod 26 = 53 mod 26 = 1
Vậy ma trận K có nghịch đảo.

(11,24)
11 8
3 7

= (121+72, 88+168) = (11,22)

(11,22)
7 18
23 11

= (11,24)
Cho m là một số nguyên dương có định. Cho
P = C =
(Z
26
)
m
và cho

K
= { các ma trận khả nghịch cấp m  m trên Z
26
}
Với một khoá K 
K
ta xác định
e
K
(x) = xK
và d

Bây giờ mỗi nhóm 6 chữ cái được sắp xếp lại theo phép hoán vị , ta có:
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
.
Thực tế mã hoán vị là trường hợp đặc biệt của mật mã Hill. Khi cho phép (3,4)
7 18
23 11

= (9,20)
Cho m là một số nguyên dương xác định nào đó. Cho
P = C =
(Z
26
)
m
và
cho
K
gồm tất cả các hoán vị của {1, . . ., m}. Đối một khoá  ( tức là một
hoán vị) ta xác định
e

(x
1

hoán vị  của tập {1, . . . ,m}, ta có thể xác định một ma trận hoán vị m  m
thích hợp K

= { k
i,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).
Dễ dàng thấy rằng, phép mã Hill dùng ma trận K

trên thực tế tương
đương với phép mã hoán vị dùng hoán vị . Hơn nữa K
-1

= K

-1
tức ma trận
nghịch đảo của K

là ma trận hoán vị xác định theo hoán vị 
-1
. Như vậy, phép
giải mã Hill tương đương với phép giải mã hoán vị.
Đối với hoán vị  được dùng trong ví dụ trên, các ma trận hoán vị kết hợp
là:

0 0 0 0 0 1
0 0 0 1 0 0
0 1 0 0 0 0
- -

24
CHƯƠNG 2. CHUẨN MÃ DỮ LIỆU (DES)

Các hệ mật mã truyền thống được trình bày ở chương 1 có một số ưu
điểm là mã hóa và giải mã bằng thủ công được thực hiện rất dễ dàng , việc trao
đổi khóa mã cũng đơn giản bằng thủ công hoặc bằng qui ước. Song với lượng
thông tin quá phong phú như hiện nay và với mạng truyền thông như hiện nay
thì mật mã thủ công vừa không đảm bảo bí mật lại việc mã hóa quá chậm khó tự
động hóa mã và giải mã .Mặt khác các thuật toán mã hóa thủ công đòi hỏi phải
tuyệt đối dữ bí mật…Như vậy mật mã thủ công đòi hỏi bảo mật cả thuật toán mã
hoa svaf cả khóa mã.
Sau nhưng năm 70 của thế kỷ trước, các nhà toán học đã nghiên cứu và
tạo ra nhiều phương thức mật mã với tốc độ mã hóa rất nhanh (hàng chục thậm
chí hàng trăm kilo Byte trong một giây) và người ta chỉ cần giữ bí mật khóa mã
và mã hóa được mọi dữ liệu tùy ý. Đó là một bước tiến vĩ đại của kỹ thuật mật
mã .Trong đó mã DES (Data Encryption Standard) là một điển hình của bước
tiến này. Chương này, em muốn mô phỏng mã hóa và giải mã của thuật toán
DES.
2.1 MÔ TẢ DES (Data Encryption Standard)
DES mã hoá một xâu bít x:
Bản rõ x độ dài 64 bit.
khoá k độ dài 56 bít.

i
= L
i-1
 f(R
i-1
,K
i
)
trong đó
- -

25

 kí hiệu cộng theo
modulo 2 của hai xâu bít.

f là một hàm mà của R
i-1
,K
i
mô tả sau.
K
i
là các xâu bít độ dài 48 được tính như hàm của khoá K. ( trên
thực tế mỗi K
i
là một phép chọn hoán vị bít trong K).
3. Áp dụng phép hoán vị ngược IP
-1
cho xâu bít R

58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 31 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
L
i-1
R
i-1

A

J

f

K
i

+

L
i
R
i