ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
MỤC LỤC I .1 Giới thiệu....................................................................................................... 3

I.2 Các Hệ Mã Thông Dụng:................................................................................. 3

e. Phương pháp Affine...........................................................................................4

f. Phương pháp Vigenere....................................................................................... 5

I.2 LẬP MÃ DES................................................................................................. 14

I. 3 THÁM MÃ DES............................................................................................ 17

I.3.1. Thám mã hệ DES - 3 vòng
.................................................................20

II.3.2. Thám mã hệ DES 6-vòng .....................................................................24

II.3. 3 Các thám mã vi sai khác...................................................................... 28

III.

CÀI ĐẶT THÁM MÃ DES 3 VÒNG......................................................28

III.1 Giao Diện ....................................................................................................28

III.2 XỬ LÝ ............................................................................................................
LỜI NÓI ĐẦUHiện nay, nước ta đang trong giai đoạn tiến hành công nghiệp hóa, hiện đại hóa đất
nước. Tin học được xem là một trong những ngành mũi nhọn. Tin học đã và đang đóng góp
rất nhiều cho xã hội trong mọi khía cạnh của cuộc sống.

Mã hóa thông tin là một ngành quan trọng và có nhiều ứng dụng trong đời sống xã hội.
Ngày nay, các ứng dụng mã hóa và bảo mật thông tin đang được sử dụng ngày càng phổ
biến hơn trong các lónh vực khác nhau trên Thế giới, từ các lónh vực an ninh, quân sự, quốc
phòng…, cho đến các lónh vực dân sự như thương mại điện tử, ngân hàng…

Ứng dụng mã hóa và bảo mật thông tin trong các hệ thống thương mại điện tử, giao dòch
chứng khoán,… đã trở nên phổ biến trên thế giới và sẽ ngày càng trở nên quen thuộc với
người dân Việt Nam. Tháng 7/2000, thò trường chứng khoán lần đầu tiên được hình thành tại
Việt Nam; các thẻ tín dụng bắt đầu được sử dụng, các ứng dụng hệ thống thương mại điện
tử đang ở bước đầu được quan tâm và xây dựng. Do đó, nhu cầu về các ứng dụng mã hóa và
bảo mật thông tin trở nên rất cần thiết.


k
∈E và luật giải mã d
k
∈D tương ứng. Luật
mã hóa e
k
: P → C và luật giải mã e
k
: C → P là hai ánh xạ thỏa mãn
( )
( )
,
kk
dex x xP=∀∈

Tính chất 4. là tính chất chính và quan trọng của một hệ thống mã hóa. Tính chất này
bảo đảm việc mã hóa một mẩu tin x∈P bằng luật mã hóa e
k
∈E có thể được giải mã
chính xác bằng luật d
k
∈D.
Đònh nghóa 1.2: Z
m
được đònh nghóa là tập hợp {0, 1, ..., m-1}, được trang bò phép cộng
(ký hiệu +) và phép nhân (ký hiệu là ×). Phép cộng và phép nhân trong Z
m
được thực
hiện tương tự như trong Z, ngoại trừ kết quả tính theo modulo m
Ví dụ: Giả sử ta cần tính giá trò 11 × 13 trong Z

5. Mọi phần tử a trong Z
m
đều có phần tử đối là m – a
6. Phép nhân đóng trong Z
m
, i.e., ∀ a, b ∈ Z
m
, b∈ Z
m

7. Tính giao hoán của phép cộng trong Z
m
, i.e., ∀ a, b ∈ Z
m
, b=b×a
8. Tính kết hợp của phép cộng trong Z
m
, i.e., ∀ a, b, c ∈ Z
m
, (b)×c =(b×c)
9. Z
m
có phần tử đơn vò là 1, i.e., ∀ a ∈ Z
m
, 1=1×a=a
10. Tính phân phối của phép nhân đối với phép cộng, i.e., ∀ a, b, c ∈ Z
m
, (a+b)×c
=(c)+(b×c)
11. Z
trong đó 26 là số ký tự trong bảng chữ cái La tinh, một cách tương tự cũng có thể
đònh nghóa cho một bảng chữ cái bất kỳ. Đồng thời ta dễ dàng thấy rằng mã đẩy là một hệ
mật mã vì d
K
(e
K
(x)) = x với mọi x∈Z
26
.
b. Hệ KEYWORD-CEASAR
Trong hệ mã này khóa là một từ nào đó được chọn trước, ví dụ PLAIN. Từ này
xác đònh dãy số nguyên trong Z
26
(15,11,0,8,13) tương ứng với vò trí các chữ cái của các
chữ được chọn trong bảng chữ cái. Bây giờ bản rõ sẽ được mã hóa bằng cách dùng các
hàm lập mã theo thứ tự:
e
15
, e
11
, e
0
, e
8
, e
13
, e
15

(y)
với π
-1
là hoán vò ngược của hoán vò π.
Trong mã thế vò ta có thể lấy P và C là các bảng chữ cái La tinh. Ta sử dụng Z
26

trong mã đẩy vì lập mã và giải mã đều là các phép toán đại số.
e. Phương pháp Affine

ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
Cho P = C = Z
26
và cho
K = {(a,b) ∈ Z
26
× Z
26
: gcd(a,26) = 1}
Với K = (a,b) ∈ K, ta xác đònh
e
K
(x) = ax+b mod 26
và
d
K
= a
-1
(y-b) mod 26

26
và nguyên tố cùng nhau với 26.
Đònh lý 1.2: Nếu
∏
=
=
m
i
e
i
i
pn
1
với p
i
là các số nguyên tố khác nhau và e
i
∈ Z
+
, 1 ≤ i ≤ m thì
()
()
∏
=
−
−=
m
i
e
i


Phương pháp mã hóa Vigenere Cipher

Chọn số nguyên dương m. Đònh nghóa P = C = K = (Z
26
)
m

ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
K = { (k
0
, k
1
, ..., k
r-1
) ∈ (Z
26
)
r
}
Với mỗi khóa k = (k0, k1, ..., k
r-1
) ∈ K, đònh nghóa:
e
k
(x
1
, x
2

2
) mod n, ..., (y
m
–k
m
) mod 26)
với x, y ∈ (Z
26
)
mg. Hệ mã Hill
Phương pháp Hill Cipher được Lester S. Hill công bố năm 1929: Cho số nguyên dương
m, đònh nghóa P = C = (Z
26
)
m
. Mỗi phần tử x∈P là một bộ m thành phần, mỗi thành phần
thuộc Z
26
. Ý tưởng chính của phương pháp này là sử dụng m tổ hợp tuyến tính của m thành
phần trong mỗi phần tử x∈P để phát sinh ra m thành phần tạo thành phần tử y∈C.
Phương pháp mã hóa Hill Cipher

Chọn số nguyên dương m. Đònh nghóa:
P = C = (Z
26
)
m

MMM
LL
L
, đònh nghóa:
() ( )
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
==
mmmm
m
m
mk
kkk
kk
kkk
xxxxkxe
,2,1,
,21,2

cách sắp xếp lại các ký tự trong đó. Phương pháp mã hóa mã hoán vò

Chọn số nguyên dương m. Đònh nghóa:
P = C = (Z
26
)
m
và K là tập hợp các hoán vò của m phần tử {1, 2, ..., m}
Với mỗi khóa π ∈ K, đònh nghóa:
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
()
() ( ) ( )
( )
mm
xxxxxxe
ππππ
,...,,...,,
2121
=
và
()
() ( ) ( )
( )
m
m
yyyyyyd

,
ji
k
ji
π

Ma trận k
π
là ma trận mà mỗi dòng và mỗi cột có đúng một phần tử mang giá trò 1, các
phần tử còn lại trong ma trận đều bằng 0. Ma trận này có thể thu được bằng cách hoán vò
các hàng hay các cột của ma trận đơn vò I
m
nên k
π

là ma trận khả nghòch. Rõ ràng, mã hóa
bằng phương pháp Hill với ma trận k
π

hoàn toàn tương đương với mã hóa bằng phương pháp
mã hoán vò với hoán vò π.
d. Mã vòng
Trong các hệ trước đều cùng một cách thức là các phần tử kế tiếp nhau của bản rõ
đều được mã hóa với cùng một khóa K. Như vậy xâu mã y sẽ có dạng sau:
y = y
1
y
2
... = e
K

nhìn chung các hệ mã đối xứng là dễ cài đặt với tốc độ thực thi nhanh.
Tính an toàn của nó phụ thuộc vào các yếu tố :
• Không gian khoá phải đủ lớn
• với các phép trộn thích hợp các hệ mã đối xứng có thể tạo ra được một hệ
mã mới có tính an toàn cao.
• bảo mật cho việc truyền khóa cũng cần được xử lý một cách nghiêm túc.
Và một hệ mã hoá dữ liệu ra đời (DES). DES được xem như là chuẩn mã hóa dữ
liệu cho các ứng dụng từ ngày 15 tháng 1 năm 1977 do Ủy ban Quốc gia về Tiêu chuẩn
của Mỹ xác nhận và cứ 5 năm một lần lại có chỉnh sửa, bổ sung.
DES là một hệ mã được trộn bởi các phép thế và hoán vò. với phép trộn thích hợp
thì việc giải mã nó lại là một bài toán khá khó. Đồng thời việc cài đặt hệ mã này cho
những ứng dụng thực tế lại khá thuận lợi. Chính những lý do đó nó được ứng dụng rộng
rãi của DES trong suốt hơn 20 năm qua, không những tại Mỹ mà còn là hầu như trên khắp
thế giới. Mặc dù theo công bố mới nhất (năm 1998) thì mọi hệ DES, với những khả năng
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
của máy tính hiện nay, đều có thể bẻ khóa trong hơn 2 giờ. Tuy nhiên DES cho đến nay
vẫn là một mô hình chuẩn cho những ứng dụng bảo mật trong thực tế.
II. HỆ MÃ CHUẨN DES (Data Encryption Standard)
II.1 Đặc tả DES
Phương pháp DES mã hóa từ x có 64 bit với khóa k có 56 bit thành một từ có y 64 bit.
Thuật toán mã hóa bao gồm 3 giai đoạn:
1. Với từ cần mã hóa x có độ dài 64 bit, tạo ra từ x
0
(cũng có độ dài 64 bit) bằng cách
hoán vò các bit trong từ x theo một hoán vò cho trước IP (Initial Permutation). Biểu diễn
x
0
= IP(x) = L
0

i
= L
i-1
⊕ f (R
i-1
, K
i
)
với ⊕ biểu diễn phép toán XOR trên hai dãy bit, K
1
, K
2
, ..., K
16
là các dãy 48 bit phát
sinh từ khóa K cho trước (Trên thực tế, mỗi khóa K
i
được phát sinh bằng cách hoán vò
các bit trong khóa K cho trước).

L
i
-1
R
i
-1
f
K
i
⊕

ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825 Hàm f được sử dụng ở bước 2 là


5
B
6
B
7

B
8

S
1
J
E(A)
S
2
S
3
S
4
S
5
S
6
S
7
S
8

C
1

E(A).
• Thực hiện phép toán XOR cho 2 dãy 48 bit E(A) và J, ta thu được một dãy 48 bit B.
Biểu diễn B thành từng nhóm 6 bit như sau:B = B
1
B
2
B
3
B
4
B
5
B
6
B
7
B
8

• Sử dụng 8 ma trận S
1
, S
2
,..., S
8
, mỗi ma trận S
i
có kích thước 4×16 và mỗi dòng của
ma trận nhận đủ 16 giá trò từ 0 đến 15. Xét dãy gồm 6 bit B
j

b
5
.
Bằng cách này, ta xác đònh được các dãy 4 bit C
j
= S
j
(B
j
), 1 ≤ j ≤ 8.
• Tập hợp các dãy 4 bit C
j
lại. ta có được dãy 32 bit C = C
1
C
2
C
3
C
4
C
5
C
6
C
7
C
8
. Dãy 32
bit thu được bằng cách hoán vò C theo một quy luật P nhất đònh chính là kết quả của

7
6
5
48
47
46
45
16
15
14
13
56
55
54
53
24
23
22
21
64
63
62
61
32
31
30
29
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
36

25

Hàm mở rộng E được đặc tả theo bảng sau: E – bảng chọn bit
32
4
8
12
16
20
24
28
1
5
9
13
17
21
25
29
2
6
10
14
18


S
1

14
0
4
15
4
15
1
12
13
7
14
8
1
4
8
2
2
14
13
4
15
2
6
9
11
13

0
3
5
6
7
8
0
13

S
2

15
3
0
13
1
13
14
8
8
4
7
10
14
7
11
1
6
15

12
6
9
0
0
9
3
5
5
11
2
14
10
5
15
9

S
3

10
13
13
1
0
7
6
10
9
0

12
5
2
14
7
14
12
3
11
12
5
11
4
11
10
5
2
15
14
2
8
1
7
12

S
4

ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825

13
8
1
4
15
9
2
7
1
4
8
2
3
5
5
12
14
11
11
1
5
12
12
10
2
7
4
14
8
2

7
13
14
11
13
7
2
6
1
8
13
8
5
15
6
5
0
9
15
3
15
12
0
15
10
5
9
13
3
6

2
5
12
9
7
2
9
2
12
8
5
6
9
12
15
8
5
3
10
0
6
7
11
13
1
0
14
3
13
4

0
4
11
2
11
11
13
14
7
13
8
15
4
12
1
0
9
3
4
8
1
7
10
13
10
14
7
3
14
10

S
8

13
1
7
2
2
15
11
1
8
13
4
14
4
8
1
7
6
10
9
4
15
3
12
10

3
5
12
9
5
6
7
2
8
11

P
16
29
1
5
2
32
19
22
7
12
15
18
8
27
13
11
20
28

0
là 28 bit còn lại.
2. Với i nằm trong khoảng từ 1 đến 16, ta tính
C
i
= LS
i
(C
i-1
)
D
i
= LS
i
(D
i-1
)
và K
i
= PC-2(C
i
D
i
), LS
i
biểu diễn phép chuyển chu trình (cyclic shift) sang trái hoặc của
một hoặc của hai vò trí tùy thuộc vào trò của i; đẩy một vò trí nếu i = 1, 2, 9 hoặc 16 và
đẩy 2 vò trí trong những trường hợp còn lại. PC-2 là một hoán vò cố đònh khác.
Việc tính lòch khóa được minh họa như hình vẽ sau:


0
D
0

C
1
D
1
PC-2 K
1

LS
1
LS
1
LS
2

LS
2...

LS
16

LS
16


42
51
60
39
46
53
28
34
43
52
31
38
45
20
26
35
44
23
30
37
12
18
27
36
15
22
29
4
PC-2
14

36
1
21
26
13
47
33
34
29
5
10
8
2
55
48
53
32

Bây giờ ta sẽ hiển thò kết quả việc tính lòch khóa. Như đã nhận xét ở trên, mỗi
vòng sử dụng khóa 48 bit tương ứng với 48 bit trong K. Các thành phần trong các bảng sau
sẽ chỉ ra các bit trong K được sử dụng trong các vòng khác nhau.
I.2 LẬP MÃ DES
Đây là ví dụ về việc lập mã sử dụng DES. Giả sử ta mã hóa bản rõ sau trong dạng
thập lục phân (Hexadecimal)
0123456789ABCDEF
sử dụng khóa thập lục phân
133457799BBCDFF1
Khóa trong dạng nhò phân không có các bit kiểm tra sẽ là:
00010010011010010101101111001001101101111011011111111000.
p dụng IP, ta nhận được L

f(R
0
,K
1
)
L
2
= R
1

=
=
=
=
=
=
011110100001010101010101011110100001010101010101
000110110000001011101111111111000111000001110010
011000010001011110111010100001100110010100100111
01011100100000101011010110010111
00100011010010101010100110111011
11101111010010100110010101000100

E(R
1
) = 011101011110101001010100001100001010101000001001
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
K
2

)
K
3

E(R
2
) ⊕ K
3

S-box output
f(R
2
, K
3
)
L
4
= R
3

=
=
=
=
=
=
111001011000000000000010101110101110100001010011
010101011111110010001010010000101100111110011001
101100000111110010001000111110000010011111001010
00100111000100001110000101101111

=
010100000100001011111000000001010111111110101001
011100101010110111010110110110110011010100011101
001000101110111100101110110111100100101010110100
00100001111011011001111100111010
10111011001000110111011101001100
011101110

E(R
4
)
K
5

E(R
4
) ⊕ K
5

Xuất S-hộp
f(R
4
, K
5
)
L
6
= R
5


L
7
= R
6

=
=
=
=
=
=
110001010100001001011111110100001100000110101111
011000111010010100111110010100000111101100101111
101001101110011101100001100000001011101010000000
01000001111100110100110000111101
10011110010001011100110100101100
11101001011001111100110101101001

E(R
6
)
K
7

E(R
6
) ⊕ K
7

S-box output


E(R
7
) ⊕ K
8

S-box output
f(R
7
, K
8
)
L
9
= R
8

=
=
=
=
=
111101111000101000111010110000010011101111111011
111101110100100001101111100111100111101101011011
01101100000110000111110010101110
00111100000011101000011011111001
11010101011010010100101110010000

E(R
8

00100010001101100111110001101010
00100100011111001100011001111010

E(R
9
)
K
10

E(R
9
) ⊕ K
10

S-box output
f(R
9
, K
10
)
L
11
= R
10

=
=
=
=
=

=
=
=
=
=
010110101111111010101011111010101111110110100101
001000010101111111010011110111101101001110000110
011110111010000101111000001101000010111000100011
01110011000001011101000100000001
11100001000001001111101000000010
11000101011110000011110001111000

E(R
11
)
K
12

E(R
11
) ⊕ K
12

S-box output
f(R
11
, K
12
)
L

= R
13

=
=
=
=
=
=
001110101011110111111010100011110000001011110000
100101111100010111010001111110101011101001000001
101011010111100000101011011101011011100010110001
10011010110100011000101101001111
11011101101110110010100100100010
00011000110000110001010101011010

E(R
13
)
K
14

E(R
13
)⊕ K
14

=
=
=

14
)⊕ K
15

S-box output
f(R
14
, K
15
)
L
16
= R
15

=
=
=
=
=
=
111000000101010001011001010010101100000001011011
101111111001000110001101001111010011111100001010
010111111100010111010100011101111111111101010001
10110010111010001000110100111100
01011011100000010010011101101110
01000011010000100011001000110100

E(R
15

Cuối cùng, áp dụng IP
-1
cho R
16
L
16
ta nhận được bản mã trong dạng thập lục phân
như sau:
85E813540F0AB405 I. 3 THÁM MÃ DES
Một phương pháp rất nổi tiếng trong thám mã DES là “thám mã vi sai“
(differential cryptanalysic) do Biham và Shamir đề xuất. Đó là phương pháp thám với bản
rõ được chọn. Nó không được sử dụng trong thực tế để thám mã DES 16 vòng, mà chỉ
được sử dụng để thám các hệ DES có ít vòng hơn.
Bây giờ ta sẽ mô tả những ý tưởng cơ bản của kỹ thuật này. Để đạt mục đích thám
mã, ta có thể bỏ qua hoán vò khởi tạo IP và hoán vò đảo của nó (bởi vì điều đó không cần
thiết cho việc thám mã). Như đã nhận xét ở trên, ta xét các hệ DES n vòng, với n ≤ 16.
Trong cài đặt ta có thể coi L
0
R
0
là bản rõ và L
n
R
n
như là bản mã.
Thám mã vi sai đòi hỏi phải so sánh x-or (exclusive-or) của hai bản rõ với x-or của
hai bản mã tương ứng. Nói chung, ta sẽ quan sát hai bản rõ L

,B
j
*

).
Ta nói rằng, xâu nhập x-or (của S
j
) là B
j
⊕ B
j
*
và xâu xuất x-or (của S
j
) là S
j
(B
j
) ⊕ S
j
(B
j
*
).
Chú ý là xâu nhập x-or là xâu bit có độ dài 6, còn xâu xuất x-or có độ dài 4.
Đònh nghóa 3.2: Với bất kỳ B
j
’ ∈ (Z
2
)

∈ (Z
2
)
6
}

Với mỗi cặp trong Δ(B
j
’), ta có thể tính xâu x-or xuất của S
j
và lập được phân bố
kết quả. Có 64 xâu xuất x-or, được phân bố trong 2
4
= 16 giá trò có thể có. Tính không
đồng đều của các phân bố đó là cơ sở để mã thám.
Ví dụ 3.1: Giả sử ta xét S
1
là S-hộp đầu tiên và xâu nhập x-or là 110100. Khi đó
Δ(110100) = {(000000, 110100), (000001, 110101), ..., (111111, 001011)}
Với mỗi cặp trong tập Δ(110100), ta tính xâu xuất x-or của S
1
. Chẳng hạn,
S
1
(000000) = E
16
= 1110, S
1
(110100) = 1001,
như vậy xâu xuất x-or cho cặp (000000,110100) là 0111.

1
111
0
111
1
0 8 16 6 2 0 0 12 6 0 0 0 0 8 0 6

Trong ví dụ 3.1, chỉ có 8 trong số 16 xâu x-or xuất có thể có xuất hiện thật sự. Ví
dụ cụ thể này đã chỉ ra sự phân bố rất không đều của các xâu x-or xuất. Nói chung, nếu ta
cố đònh S-hộp S
j
và xâu nhập x-or B
j
’, thì trung bình có khoảng 75 - 80% các xâu x-or
xuất có thể có xuất hiện thực sự.
Để mô tả các phân bô đó ta đưa ra đònh nghóa sau.
Đònh nghóa 3.3: Với 1 ≤ j ≤ 8 và với các xâu bit B
j
’ độ dài 6 và Cj’ độ dài 4, ta
đònh nghóa:
IN
j
(B
j
’,C
j
’) = {B
j
∈ (Z
2

Bảng sau sẽ cho các xâu nhập có thể có với xâu x-or nhập 110100

Xâu xuất x-or Các xâu nhập có thể có
0000
0001 000011, 001111, 011110, 011111
101010, 101011, 110111, 111011

0010
000100, 000101, 001110, 010001
010010, 010100, 011010, 011011
100000, 100101, 010110, 101110
101111, 110000, 110001, 111010
0011 000001, 000010, 010101, 100001
110101, 110110
0100 010011, 100111
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
0101
0110

0111
000000, 001000, 001101, 010111
011000, 011101, 100011, 101001
101100, 110100, 111001, 111100
1000 001001, 001100, 011001, 101101
111000, 111101
1001
1010
1011
1100

j
’, C
j
’) /2 cặp, mỗi cặp có xâu x-or nhập bằng B
j
’.
Phân bố trong ví dụ 3.1 chứa các trò N
1
(110100, C
1
’), C
1
’∈ (Z
2
)
4
. Trong bảng trên
chứa các tập IN(110100, C
1
’).
Với mỗi tám S-hộp, có 64 xâu nhập x-or có thể có. Như vậy, có 512 phân bố có
thể tính được. Nhắc lại là, xâu nhập cho S-hộp ở vòng thứ i là B= E⊕ J, với E = E(R
i-1
) là
mở rộng của R
i-1
và J = K
i
gồm các bit khóa của vòng i. Bây giờ xâu nhập x-or (cho tất cả
tám S-hộp) có thể tính được như sau:

5
E
6
E
7
E
8

J = J
1
J
2
J
3
J
4
J
5
J
6
J
7
J
8

và ta cũng sẽ viết B
*
và E
*
như vậy. Bây giờ giả sử là ta đã biết các trò E

với E
j
’ = E
j
⊕ E
j
*
.
Đònh nghóa 3.4: Giả sử E
j
và E
j
*
là các xâu bit độ dài 6, và C
j
’ là xâu bit độ dài 4. Ta đònh
nghóa:

test
j
(E
j
, E
j
*
, C
j
’) = { B
j


j
*
là hai xâu nhập cho S-hộp S
j
, và xâu xuất x-or cho S
j
là C
j
’. Ký hiệu
E
j
’ = E
j

⊕
E
j
*
. Khi đó các bit khóa J
j
có trong tập test
j
(E
j
, E
j
*, C
j
’).
Để ý, đó chính là các xâu bit N

xâu bit trong tập test
1
(000001, 110101, 1101). Từ bảng trên ta thấy rằng
IN
1
(110100, 1101) = {000110, 010000, 010110, 011100, 100010, 100100, 101000,
110010}
Cho nên
test
1
(000001, 110101,1101) = {000111, 010001, 010111, 011101, 100011, 100101,
101001, 110011}
Nếu ta có một bộ ba thứ hai như thế E
1
, E
1
*
, C
1
’, khi đó ta sẽ nhận được tập thứ
hai test
1
của các trò cho các bit khóa trong J
1
. Trò đúng của J
1
cần phải nằm trong giao của
các S-hộp. Nếu ta có một vài bộ ba như vậy, khi đó ta có thể mau chóng tìm được các bit
khóa trong J
1

*
R
3
*
. Ta có thể
biểu diễn R
3
như sau:
R
3
= L
2
⊕ f(R
2
, K
3
)
= R
1
⊕ f(R
2
, K
3
)
= L
0
⊕ f(R
0
, K
1

)
Bây giờ, giả sử ta đã chọn được các bản rõ sao cho R
0
= R
0
*
, chẳng hạn:
R
0
’ = 00...0
Khi đó f(R
0
, K
1
) = f(R
0
*
, K
1
), và do đó:
R
3
’ = L
0
’⊕ f(R
2
, K
3
) ⊕ f(R
2

3
’ ⊕ L
0
’
Bây giờ f(R
2
, K
3
) = P(C) và f(R
2
*
, K
3
) = P(C
*
), với C và C
*
tương ứng là ký hiệu
của hai xâu xuất của tám S-hộp (nhắc lại, P là cố đònh, là hoán vò được biết công khai).
Nên:
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
P(C) ⊕ P(C
*
) = R
3
’ ⊕ L
0
’
và kết quả là:

, ..., J
8
.
Giải thuật vừa xét có thể biểu diễn bởi các mã sau:

Input: L
0
R
0
, L
0
*
R
0
*
, L
3
R
3
và L
3
*
R
3
*
, với R
0
= R
0
*

, là khóa cho vòng ba. 56 bit trong khóa khi
đó có thể tìm được hoàn toàn từ 2
8
= 256 khả năng cho 8 bit khóa.
Bây giờ ta sẽ minh họa điều đó qua ví dụ sau.
Ví dụ 3.3
Giả sử ta có ba cặp bản rõ và bản mã, với các bản mã cùng có các xâu x-or được
mã hóa bởi cùng một khóa. Để ngắn gọn ta sử dụng hệ thập lục phân:
Bản rõ
Bản mã
748502CD38451097
3874756438451097
03C70306D8A09F10
78560A0960E6D4CB
486911026ACDFF31
375BD31F6ACDFF31
45FA285BE5ADC730
134F7915AC253457
357418DA013FEC86
12549847013FEC86
D8A31B2F28BBC5CF
0F317AC2B23CB944

Từ cặp đầu tiên ta tính các xâu nhập của S-hộp (cho vòng 3) từ các phương trình
(2) và (3). Chúng là:
E = 000000000111111000001110100000000110100000001100
E
*
= 101111110000001010101100000001010100000001010010
Xâu xuất x-or của S-hộp được tính bằng phương trình (1) sẽ là:

Do E
1
= 000000 ta có:
J
1
∈ test
1
(000000, 101111, 1001) = {000000, 000111, 101000, 101111}
Do đó ta tăng các trò 0, 7, 40 và 47 trong các mảng đếm cho J
1
.
Cuối cùng ta sẽ trình bày các bảng. Nếu ta xem các xâu bit độ dài 6 như là biểu
diễn của các số nguyên trong khoảng 0-63, thì 64 trò sẽ tương ứng với 0, 1, ..., 63. Các
mảng đếm sẽ là như sau:

J
1

1 0 0 0 0 1010000000 0
0 0 0 0 0 1100001100 0
0 1 0 0 0 1001000000 3
0 0 0 0 0 0000000000 1

J
2

0 0 0 1 0 3001001000 0
0 1 0 0 0 2000000100 0
0 0 0 0 0 1001010001 0
0 0 1 1 0 0001010200 0

1 0 0 1 1 0030000100 1
0 0 0 0 1 1000000000 0
0 0 0 0 1 1010000000 0
1 0 0 1 1 0110000000 0
J
7

0 0 2 1 0 1030001100 0
0 1 0 0 0 0000001000 1
0 0 2 0 0 0200001211 0
0 0 0 0 0 0000000001 1

J
8

0 0 0 0 0 0000000000 0
0 0 0 0 0 0000000000 0
0 0 0 0 0 0001010010 1
0 3 0 0 0 0100000000 0

Trong mỗi tám mảng đếm, có duy nhất một bộ đếm có trò là 3. Vò trí của các bộ
đếm đó xác đònh các bit khóa trong J
1
, ..., J
8
. Các vò trí đó là: 47, 5, 19, 0, 24, 7, 7, 49.
Chuyển các số nguyên đó sang dạng nhò phân, ta nhận được J
1
, ..., J
8

dạng thập lục phân, gồm cả bit kiểm tra) sẽ là:
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
1A624C89520DEC46
II.3.2. Thám mã hệ DES 6-vòng
Bây giờ ta sẽ mô tả việc mở rộng ý tưởng trên cho việc thám mã trên hệ DES 6-vòng. Ý
tưỏng ở đây là lựa chọn một cách cẩn thận cặp bản rõ với xâu x-or đặc thù và sau đó xác
đònh các xác suất của các dãy đặc thù của các xâu x-or qua các vòng lập mã. Bây giờ ta
cần đònh nghóa một khái niệm quan trọng sau.
Đònh nghóa 3.5: Cho n ≥ 1 là số nguyên. Đặc trưng của vòng thứ n là một danh sách các
dạng
L
0
’, R
0
’, L
1
’, R
1
’, p
1
, ..., L
n
’, R
n
’, p
n

thỏa mãn các điều kiện sau:
1. L

i
, R
i
và L
i
*
, R
i
*
là tính được nhờ việc áp dụng một vòng
lập mã DES. Khi đó xác suất để L
i
⊕ L
*
i
= L
i
’ và R
i
⊕ R
*
i
= R
i
’ chính xác bằng p
i.
(Chú ý là, xác suất này được tính trên tất cả các bộ có thể có của J = J
1
...J
8

*
= R
0
’ và
ta áp dụng n vòng lập mã của DES, nhận được L
1
. ..., L
n
và R
1
, ..., R
n
. Khi đó ta không thể
đòi hỏi xác suất để L
i
⊕ L
i
*
= L
i
’ và R
i
⊕ R
i
*
= R
i
’ cho tất cả i ( 1 ≤ i ≤ n) là p
1
× ...× p

ba vòng trong hình sau (như ở trên, ta sẽ sử dụng cách biểu diễn theo hệ thập lục phân).

L’
0
= bất kỳ R’
0
= 00000000
16

L’
1
= 00000000
16
R’
1
= L’
0
p = 1

Ta cũng sẽ mô tả một đặc trưng vòng 1 khác như sau

L’
0
= 00000000
16
R’
0
= 60000000
16


1
là 001100 và các xâu x-or cho bảy S-hộp khác đều là 000000.
Các xâu xuất x-or cho S
2
đến S
8
đều là 0000. Xâu xuất x-or cho S
1
là 1110 với xác suất
14/64 (do N1(001100, 1110) = 14). Nên ta nhận được:
C’ = 11100000000000000000000000000000
với xác suất 14/64. p dụng P, ta nhận được:
P(C) ⊕ P(C
*
) = 00000000100000001000001000000000

trong dạng thập lục phân sẽ là 00808200
16
. Khi xâu này cộng x-or với L
0
’, ta nhận được
R
1
’ với xác suất 14/64. Do đó L
1
’ = R
0
’.

Việc thám mã DES sáu vòng dựa trên đặc trưng ba vòng được cho trong hình sau.

0
như sau:

L
0
’
L
1
’
L
2
’
L
3
’
=
=
=
=
40080000
16
04000000
16

00000000
16

04000000
16


p = 1
p = 1/4
R
6
= L
5
⊕ f(R
5
, K
6
)
= R
4
⊕ f(R
5
, K
6
)
= L
3
⊕ f(R
3
, K
4
) ⊕ f(R
5
, K
6
)
R

3
’ = 04000000
16
và R
3
’ = 40080000
16
với xác suất
1/16. Nếu như vậy, thì xâu nhập x-or cho S-hộp trong vòng 4 có thể tính được nhờ hàm
mở rộng phải là:
001000000000000001010000...0
Các xâu x-or cho S
2
, S
5
, S
6
, S
7
và S
8
tất cả đều bằng 000000, và vì thế xâu xuất x-or là
0000 cho tất cả năm S-hộp đó trong vòng 4. Điều này có nghóa là, ta có thể tính được các
xâu xuất x-or cho năm S-hộp đó trong vòng 6 nhờ phương trình (4). Do đó giả sử ta tính:
C
1
’C
2
’C
3

, S
5
, S
6
, S
7
và S
8
trong vòng 6. Các xâu nhập
cho các S-hộp đó trong vòng 6 có thể tính được là E
2
, E
5
, E
6
, E
7
và E
8
; và E
2
*
, E
5
*
, E
6
*
, E
7

*
E
2
*
E
3
*
E
4
*
E
5
*
E
6
*
E
7
*
E
8
*
= E(R
5
*
) = E(L
6
*
)