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

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
) .
Xác suất đặc trưng được đònh nghóa bằng tích p = p
1

’ 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
n
.
Bởi vì các bộ -48 trong lòch khóa K

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

L’
1
= 60000000

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.
Trong thám mã 6-vòng, ta bắt đầu với L
0
R

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

00000000
16

04000000
16

R
0
’

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
6
*
cũng có thể biểu diễn tương tự, ta có

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
’C
4
’C

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
*

và E

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

có thể tính được từ các bản rõ như sau:
ĐỒ ÁN BẢO MẬT THÔNG TIN HỆ MÃ DES
NGÔ THỊ TUYẾT HÀ – T012825

.
1. Tính C’ = P
-1
(R
6
’ ⊕ 04000000
16
)
2. Tính E = E(L
6
) và E
*
= E(L
6
*
)
3. for j ∈ {2,5,6,7,8} do
tính test
j
( E
j
, E
j
*, Cj’)

Ta cũng sẽ xác đònh 30 bit khóa trong J
2
, J
5
, J

0
*
R
0
*
là đúng (right) ứng với đặc trưng nếu L
i
⊕ L
i
*
= L
i
’ và R
i
⊕ R
i
*
= R
i
’ cho mọi i, 1 ≤ i
≤ n. Cặp trái với cặp được đònh nghóa gọi là cặp sai (wrong).
Ta mong rằng, khoảng 1/16 số cặp của ta là đúng, còn các cặp còn lại là cặp sai ứng với
đặc trưng vòng ba của ta.
Chiến lược của ta là tính E
j
. E
j
*
và C
j

j
(E
j
’, C
j
’) = ⎪test
j
⎪ và như đã nhận xét từ trước, xác suất để N
j
(E
j
’, C
j
’) = 0 là xấp xỉ 1/5.
Xác suất để cả năm test
j
đều dương là vào khoảng 0.8
5
≈ 0.33, quả vậy xác suất để ít nhất
một test
j
bằng 0 là vào khoảng 0.67. Nên ta có khoảng 2/3 số cặp là sai, nhờ vào một
nhận xét đơn giản, được gọi là phép lọc (filtering operation). Tỷ số của các cặp đúng trên
các cặp còn lại sau phép lọc là vào khoảng:
61
311615161
161
=
×+


2
5
6
7
8
111100
111101
011010
101111
111110
010010
111100
000101
010110
101100
1101
0001
0010
1100
1101

Khi đó các tập test
j
sẽ là như sau:

j test
j

2 14, 15,26, 30, 32, 33, 48, 52
5


∏
∈ 8,7,6,5,2j
j
testĐó là bình thường với số xâu bit được đề xuất là khá lớn. (Chẳng hạn. lớn hơn
80000)
Giả sử, ta lập bảng cho tất cả các xâu được đề xuất nhận được từ N cặp, mà không bò loại
bởi phép lọc. Với mỗi cặp đúng, thì xâu bit đúng J
2
J
5
J
6
J
7
J
8
sẽ là xâu được đề xuất. Xâu bit
đúng sẽ được tính khoảng 3N/16 lần. Xâu bit sai thường xuất hiện ít hơn, bởi vì chúng
xuất hiện ngẫu nhiên và có khoảng 2
30
khả năng. (Là một số rất lớn.)
Ta nhận được một bảng cực lớn tất cả các xâu được đề xuất, nên ta sử dụng một
thuật toán chỉ đòi hỏi một không gian và thời gian ít nhất. Ta có thể mã hóa bất kỳ một
tập test
j
nào thành một véc tơ T

14
bản rõ chọn và các hệ 10-, 12-, 14- và 16-vòng đòi
hỏi có tương ứng 2
24
, 2
31
, 2
39
và 2
47
bản mã chọn. Nên nói chung là khá phức tạp.
Các kỹ thuật thám mã vi sai được Biham và Shamir phát triển. Các phương pháp thám mã
DES khác đã được Matsui sử dụng như là thám mã tuyến tính.