Đồ án tốt nghiệp
Bảo mật thông tin


ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
I.
MỘT SỐ PHƯƠNG PHÁP MÃ HÓA
I .1 Giới thiệu
Đònh nghóa 1.1: Một hệ mã mật (cryptosystem) là một bộ-năm (
P
,
C
,
K
,
E

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
∈

Z
16
.
Một số tính chất của
Z
m

1. Phép cộng đóng trong
Z
m
, i.e., ∀
a
,
b
∈
Z
m
, a+b
∈
Z
m

2. Tính giao hoán của phép cộng trong
Z
m
, i.e., ∀
a
,
b
∈

c
)
4.
Z
m
có phần tử trung hòa là 0, i.e., ∀
a
∈
Z
m
,

a
+0=0+
a
=
a

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

×
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
,
(
a
×
b
)×
c
=
a
×(
b
×
c

a
+
b
)×
c

=(
a
×
c
)+(
b
×
c
)
11.
Z
m

có các tính chất 1, 3 – 5 nên tạo thành 1 nhóm. Do
Z
m
có tính chất 2 nên tạo thành
nhóm Abel.
Z
m
có các tính chất (1) – (10) nên tạo thành 1 vành
I.2 Các Hệ Mã Thông Dụng:
a. Hệ Mã Đầy (Shift Cipher )
Shift Cipher là một trong những phương pháp lâu đời nhất được sử dụng để mã

(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
, e
11
, e
0
, e
8
, e,...
với e

e. Phương pháp Affine

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
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
và
d
K
= a
-1
(y-b) mod 26
(x,y ∈ Z
26
)

Phương pháp Affine lại là một trường hợp đặc biệt khác của Substitution Cipher.
Để có thể giải mã chính xác thông tin đã được mã hóa bằng hàm
e
k

(mod 26) tương đương với
ax
≡(
y
–
b
) (mod 26). Vậy, ta chỉ cần khảo
sát phương trình
ax
≡(
y
–
b
) (mod
26
)
Đònh lý1.1: Phương trình
ax
+
b
≡
y
(mod
26
) có nghiệm duy nhất
x
∈
Z
26
với mỗi giá trò

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

.
f. Phương pháp Vigenere
phương pháp mã hóa Vigenere sử dụng một từ khóa (keyword) có độ dài
m
. Có thể xem
như phương pháp mã hóa Vigenere Cipher bao gồm
m
phép mã hóa Shift Cipher được áp
dụng luân phiên nhau theo chu kỳ.
Không gian khóa
K
của phương pháp Vigenere có số phần tử là 26, lớn hơn hẳn phương
pháp số lượng phần tử của không gian khóa
K
trong phương pháp Shift Cipher. Do đó, việc
tìm ra mã khóa
k
để giải mã thông điệp đã được mã hóa sẽ khó khăn hơn đối với phương
pháp Shift Cipher.
Phương pháp mã hóa Vigenere Cipher

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

k
1, ...,
k
r
-1
) ∈
K
, đònh nghóa:
e
k
(
x
1
,
x
2
, ...,
x
m
) = ((
x
1
+
k
1
) mod
26
, (
x
2

n
, (
y
2
–
k
2
) mod
n
, ..., (
y
m
–
k
m
) mod
26
)
với
x
,
y
∈ (
Z
26
)
m

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

∈
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
và
K
là tập hợp các ma trận
m
×
m
khả nghòch
Với mỗi khóa

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

C

Mọi phép toán số học đều được thực hiện trên
Z
n

h. Mã 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ã hoán vò là vẫn giữ nguyên các ký tự trong thông điệp
nguồn mà chỉ thay đổi vò trí các ký tự; nói cách khác thông điệp nguồn được mã hóa bằng
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

21
−−−
=
πππ
π

với π
–1
hoán vò ngược của π

ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
Phương pháp mã hoán vò chính là một trường hợp đặc biệt của phương pháp 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
π
= (
k
i
,
j
) theo công thức sau:

( )
⎩
⎨
⎧
=

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
(x
1
) e
K
(x
2
)...
Các hệ mã loại này thường được gọi là
mã khối
(block cipher).
Còn đối với các hệ mã dòng. Ý tưởng ở đây là sinh ra một chuỗi khóa z = z
1
z
2
..., và
sử dụng nó để mã hóa xâu bản rõ x = x
1
x
2
...theo qui tắc sau:
)...()(...

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:
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
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
R

i
,
R
i
với 1≤
i
≤ 16theo quy tắc sau:
L
i
=
R
i
-1
R
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,

i
R
i

Hình.2 Quy trình phát sinh dãy 64 bit
L
i
R
i
từ dãy 64 bit
L
i
-1
R
i
-1
và khóa
K
i

3. Áp dụng hoán vò ngược
IP
-1
đối với dãy bit
R
16
L
16
, thu được từ
y

Hàm
f
được sử dụng ở bước 2 là

bằng cách hoán vò theo một
thứ tự nhất đònh 32 bit của
A
, trong đó có 16 bit của
A
được lập lại 2 lần trong
E
(
A
).
A

B
1
B
2
B
3
B
4
B
5
B
6
B
7

B
8


6
C
7
C
8

f(A,J)
E
+
P
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
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
1
b
2
b
3
b
4
b
5
b
6
,
S
j
(
B
j
) được xác đònh bằng giá trò của phần tử tại dòng
r
cột
c
của
S
j
, trong đó, chỉ số
dòng
r
có biểu diễn nhò phân là
b

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 hàm
F
(
A
,

35
34
33
8
7
6
5
4
3
2
1
48
47
46
45
44
43
42
41
16
15
14
13
12
11
10
9
56
55
54

Hàm mở rộng E được đặc tả theo bảng sau:

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

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
10

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
4
13

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

S
4
7
13
10
3
13

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
15
9
4
14


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

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
1
4
14
10
7

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
9
12
3
15
5

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

7
2
8
11

P
16
29
1
5
2
32
19
22
7
12
15
18
8
27
13
11
20
28
23
31
24
3
30
4

i-1
)
D
i
= LS
i
(D
i-1
)
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
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:


2
11
55
62
6
13
41
50
59
34
7
54
61
5
33
42
51
60
39
46
53
28
25
34
43
52
31
38
45
20

PC-1
C
0
D
0

C
1
D
1
PC-2 K
1

LS
1
LS
1
LS
2

LS
2...

LS
16

LS

20
37
45
56
36
26
13
47
33
34
29
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
)
K
2

E(R

)
K
3

E(R
2
) ⊕ K
3

S-box output
f(R
2
, K
3
)
=
=
=
=
=
111001011000000000000010101110101110100001010011
010101011111110010001010010000101100111110011001
101100000111110010001000111110000010011111001010
00100111000100001110000101101111
01001101000101100110111010110000
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
L
4
= R

=
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

7
) ⊕ K
8

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

=
=
=
=
=
=
000000001100001001010101010111110100000010100000
111101111000101000111010110000010011101111111011
111101110100100001101111100111100111101101011011
01101100000110000111110010101110
00111100000011101000011011111001
11010101011010010100101110010000

E(R
8

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

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
14
= R
13

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

E(R
13
)
K
14

E(R
13
)⊕ K
14

S-box output

14
)⊕ K
15

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

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

E(R
15

11001000110000000100111110011000
00001010010011001101100110010101
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ã.

Cho S
j
là một S-hộp (1 ≤ j ≤ 8). Xét một cặp xâu 6-bit là (B
j
,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
’) : B
j
∈ (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

j
’) = {B
j
∈ (Z
2
)
6
: S
j
(B
j
) ⊕ S
j
(B
j
⊕ B
j
’) = C
j
’}
và
N
j
(B
j
’, C
j
’) = ⎮IN
j
(B

1001
1010
1011
1100
1101 000110, 010000, 010110, 011100
110010, 100100, 101000, 110010
1110
1111 000111, 001010, 001011, 110011
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
111110, 111111

N
j
(B
j
’, C
j
’) tính số các cặp với xâu nhập x-or bằng B
j
’ có xâu xuất x-or bằng C
j
’ với
S-hộp S
j
. Các cặp đó có các xâu nhập x-or được đặc tả và đưa ra cách tính các xâu xuất x-
or có thể nhận được từ tập IN
j
(B
j

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:
B ⊕ B* = (E ⊕ J) ⊕ (E* ⊕ J) = E ⊕ E*
Điều này rất quan trọng để thấy rằng, xâu nhập x-or không phụ thuộc vào các bit
khóa J. (Do đó, xâu xuất x-or cũng không phụ thuộc vào các bit khóa.)
Ta sẽ viết mỗi B, E và J như là nối của tám xâu 6-bit:
B = B
1
B
2
B
3
B
4
B
5
B
6
B
7
B
8

E = E
1
E


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
j
và E
j
*
với một j
nào đó, 1 ≤ j ≤ 8, và trò của xâu xuất x-or cho S
j
, C
j
’ = S
j
(B
j
) ⊕ S
j
(B
j
*
). Khi đó sẽ là:
E
j
⊕ J
j
∈ IN

j
, E
j
*
, C
j
’) = { B
j
⊕ E
j
: B
j
∈ IN
j
(E
j
’, C
j
’) },
với E
j
’ = E
j
⊕ E
j
*
.
Đònh lý 3.1:
Giả sử E
j

(E
j
’, C
j
’) độ dài 6 trong tập test
j
(E
j
, E
j
*
, C
j
’); giá trò
chính xác của J
j
phải là một trong số đó.

Ví dụ 3.2
:
Giả sử E
1
= 000001, E
1
*
= 110101 và C
1
’= 1101. Do đó N
1
(110101,1101) = 8, đúng bằng 8

khóa trong J
1
. Một cách rõ ràng hơn để thực hiện điều đó là lập một bảng của 64 bộ đếm
biểu diễn cho 64 khả năng của của 6 khóa bit trong J
1
. Bộ đếm sẽ tăng mỗi lần, tương ứng
với sự xuất hiện của các bit khóa trong tập
test
1
cho một bộ ba cụ thể. Cho t bộ ba, ta hy
vọng tìm được duy nhất một bộ đếm có trò t; trò đó sẽ tương ứng với trò đúng của các bit
khóa trong J
1
.

I.3.1. Thám mã hệ DES - 3 vòng
Bây giờ ta sẽ xét ý tưởng vừa trình bày cho việc thám mã hệ DES - ba vòng. Ta sẽ
bắt đầu với cặp bản rõ và các bản mã tương ứng: L
0
R
0
, L
0
*
R
0
*
, L
3
R

0
, K
1
) ⊕ f(R
2
, K
3
)
R
3
* có thể biểu diễn một cách tương tự , do vậy:
R
3
’ = L
0
’ ⊕ f(R
0
, K
1
) ⊕ f(R
0
*
, K
1
) ⊕ f(R
2
, K
3
) ⊕ f(R
2

3
) ⊕ f(R
2
*
, K
3
)
Ở điểm này R
3
’ là được biết khi nó có thể tính được từ hai bản mã, và L
0
’ là biết
được khi nó có thể tính được từ hai bản rõ. Nghóa là ta có thể tính được f(R
2
,K
3
)⊕f(R
2
*
,K
3
)
từ phương trình:
f(R
2
, K
3
) ⊕ f(R
2
*

và kết quả là:
C’ = C ⊕ C* = P
-1
(R
3
’ ⊕ L
0
’) (1)
Đó là xâu xuất x-or cho tám S-hộp trong vòng ba.
Bây giờ, R
2
= L3 và R2* = L3* là đã biết (chúng là một phần của các bản mã). Từ
đây ta có thể tính:
E = E(L
3
) (2)
và
E
*
= E(L
3
*
) (3)
sử dụng hàm mở rộng E được biết công khai. Chúng là những xâu nhập cho các S-hộp cho
vòng ba. Như vậy giờ ta đã biết E, E*, và C’ cho vòng ba và ta có thể tiếp tục xây dựng
các tập
test
1
, ..., test
8

0
*

1. Tính C’ = P
-1
(R
3
’ ⊕ L
0
’)
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
2. Tính E = E(L
3
) và E
*
= E(L
*
)
3. for j = 1 to 8 do
compute
test
j
(E
j
, E
j
*
, C
j

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à:
C’ = 10010110010111010101101101100111
Từ cặp thứ hai, ta tính được các xâu nhập cho S-hộp là:
E = 101000001011111111110100000101010000001011110110
E
*
= 100010100110101001011110101111110010100010101001
và xâu xuất x-or của S-hộp là:
C’ = 10011100100111000001111101010110

Từ cặp thứ ba, các xâu nhập cho S-hộp sẽ là:
E = 111011110001010100000110100011110110100101011111
E
*
= 000001011110100110100010101111110101011000000100
và xâu xuất x-or của S-hộp là:
C’ = 11010101011101011101101100101011
Tiếp theo, ta lập bảng các trò trong tám mảng bộ đếm cho mỗi cặp. Ta sẽ minh họa
thủ tục với các mảng đếm cho J
1
từ cặp đầu tiên. Trong cặp này, ta có E
1
’= 101111 và C
1
’

J
2
0 0 0 1 0 3 0 0 1 0 0 1 0 0 0 0
0 1 0 0 0 2 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0
0 0 1 1 0 0 0 0 1 0 1 0 2 0 0 0

J
3
0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0
0 0 0 3 0 0 0 0 0 0 0 0 0 0 1 1
0 2 0 0 0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0

J
4
3 1 0 0 0 0 0 0 0 0 2 2 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1
1 1 1 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 0 0 1 1 0 0 0 0 0 0 0 0 2 1

J
5
0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
0 0 0 0 2 0 0 0 3 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 2 0 0 0 0 0 0 1 0 0 0 0 2 0

J
6

, ..., J
8
:
J
1
= 101111
J
2
= 000101
J
3
= 010011
J
4
= 000000
J
5
= 011000
J
6
= 000111
J
7
= 000111
J
8
= 110001
Bây giờ ta có thể tạo ra 48 bit khóa, bằng cách quan sát lòch khóa cho vòng ba. Suy
ra là K có dạng:
0001101 0110001 01?01?0 1?00100

i
’ = R
i-1
’ với 1 ≤ i ≤ n
2. Cho 1 ≤ i ≤ n và L
i-1
, R
i-1
và L
*
i-1
, R
*
i-1
là đã được chọn sao cho L
i-1
⊕ L
*
i-1
= L’
i-1
và R
i-
1
⊕ R
*
i-1
= R’
i-1
. Giả sử L

8
) .
Xác suất đặc trưng được đònh nghóa bằng tích p = p
1
× ...× p
n
.

ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825
Nhận xét
: Giả sử ta chọn L
0
, R
0
và L
0
*
, R
0
*
sao cho L
0
⊕ L
0
*
= L
0
’


i
’ cho tất cả i ( 1 ≤ i ≤ n) là p
1
× ...× p
n
. Bởi vì
các bộ -48 trong lòch khóa K
1
, ..., K
n
không phải là độc lập lẫn nhau. (Nếu n bộ-48 này
đïc chọn độc lập một cách ngẫu nhiên, thì điều xác nhận là đúng). Nhưng ta sẽ coi rằng
p
1
× ... × p
n
chính xác là xác xuất đó.

Ta còn cần xác nhận là, các xác suất p
i
trong đặc trưng là các cặp bản rõ được xác đònh tùy
ý (nhưng cố đònh) được đặc tả bằng xâu x-or, với 48 bit khóa cho một vòng lập mã DES là
có 2
48
khả năng. Do đó việc thám mã sẽ nhằm vào việc xác đònh khóa cố đònh (nhưng chưa
biết). Do đó cần cố chọn các bản mã ngẫu nhiên (nhưng chúng có các xâu x-or được đặc
tả), hy vọng rằng các xác suất để các xâu x-or trong n vòng lập mã trùng hợp với các xâu
x-or, được đặc tả trong đặc trưng, từng đôi một p
1
, ..., p

= 60000000
16
L’
1
= 60000000
16
R’
1
= 00808200
16
p = 14/64

Ta hãy xét đặc trưng sau một cách chi tiết hơn. Khi f(R
0
, K
1
) và f(R
0
*
, K
1
) được tính, bước
đầu tiên là mở rộng R
0
và R
0
*
. Xâu x-or kết quả của hai mở rộng là:
001100...0
Tức là xâu x-or nhập cho S

Trong thám mã 6-vòng, ta bắt đầu với L
0
R
0
. L
0
*
R
0
*
, L
6
R
6
và L
6
*
R
6
*
, mà ta phải chọn bản rõ
sao cho L
0
’= 40080000
16
và R
.0
’= 04000000
16
, ta có thể biểu diễn R

16

04000000
16

R
1
’
R
2
’
R
3
’
=
=
=
00000000
16

04000000
16

40080000
16

p = 1/4
p = 1
p = 1/4
R

R
0
’ = L
3
’ ⊕ f(R
3
, K
4
) ⊕ f(R
3
*
, K
4
) ⊕ f(R
5
, K
6
) ⊕ f(R
5
*
, K
6
) (4)
(Để ý là tương tự như thám mã 3-vòng)
R
6
’ là được biết. Từ đặc trưng ta tính L
3
’ = 04000000
16

5
’C
6
’C
7
’C
8
’ = P
-1
(R
6
’ ⊕ 04000000)
mỗi C
i
là xâu bit có độ dài 4. Khi đó với xác suất 1/16, thì sẽ dẫn đến là C
2
’, C
5
’, C
6
’, C
7
’
và C
8
’ tương ứng là các xâu x-or xuất của S
2
, S
5
, S

8
*
, với
E
1
E
2
E
3
E
4
E
5
E
6
E
7
E
8
= E(R
5
) = E(L
6
)
và
E
1
*
E
2

0
R
0
, L
0
*
R
0
*
, L
6
R
6
và L
6
*
R
6
*
; với L
0
’ = 40080000
16

và R
0
’ = 04000000
16
.
1. Tính C’ = P

, J
7
và J
8
như trong thám mã 3-vòng.
Bài toán, để xâu xuất x-or giả đònh cho vòng 6 là chính xác chỉ với xác suất 1/16. Còn
15/16 phần còn lại ta sẽ thường nhận được những xâu vô dụng ngẫu nhiên hơn là các bit
khóa.

Đònh nghóa 3.6:

Giả sử L
0
⊕ L
0
*
= L
0
’ và R
0
⊕ R
0
*
= R
0
’. Ta nói rằng, cặp bản rõ L
0
R
0
và