Chirơng 5
MỘT SỐ PHưONG PHẤP THAM mã dữ liệ u DES
5.1. THÁM MÃ VI SAI ĐỐI VỚI DES VÀ CÁC HỆ MÃ KHỐI LẶP GIỐNG OES
5.1.1. Mô tẳmã
M ột sự mô tả đầy đủ về D E S đước nêu trong Công báo v ề
ch u ẩn xử lý th ông tin Láên bang sô' 46 n g à y 15 th á n g 01 năm
1977. D E S mã hoá m ột dòng bit rõ
X
có độ d à i 64 với khoá K là
dòng 56bit, đưa ra bản m ã y cũng là m ột dăy bit có độ dài 64.
DES
-Ịr-
Hình 5.1. Mô tả DES
= 64;|y| = 64;|k| = 56;
Tiìuật toán mã/dịch DES gồm 3 phần:
A: T h u â t to á n m ã/dỉch
B: Lược đồ x â y dự ng hàm f(Rị, kị)
C: Lược đồ tạo khóa {kj i = 1,16
B ản rõ R được ch ia th à n h các bỉock,m ỗi bỉock gồm 6 4b ỉt
(8bjrte) m à ta k í h iệu là
X
và cũ n g được gọi là bản rõ
X.
154
Nhập môn Phân tích thông tin có bào mật
A. Thuật toán mã hoá gồm 3 giai đoạn
1.
C h o b ả n rõ X, ta tín h được Xo q u a v iệ c h o á n v ị các
b it c ủ a X th e o h o á n v ị đ ầ u IP.
X o=IP(x) = LoRo
L q ỉà 32bit đầu tiê n của Xq
còn Ro là 32bit còn lạ i và IP là hoán vỊ đầu
cố định.
IP
58
50
42
34
26
18
10
2
60
52
44
36
28
20
12
4
62
54
46
38
30
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
63
55
47
39
31
23
15
7
2. Lặp 16 vòng
Hình 5.2. Một vòng DES
155
Chương 5: M ột số phương pháp thám mã dữ liệu D E S
i-l
R i= L i_ ,© f ( R i_ „ k i)
D ấu "©" th ể h iệ n phép toán “hoặc loại trừ” h ai dãy bit, f
là m ột hàm m à c h ú n g ta sẽ để cập đến sau , kj là nhữ ng dãy
d à i 48 b it được tạo từ khoá k bỏi th u ậ t toán riêng.
3.
B ản m ã y được tín h bỏi hoán vỊ IP ’ cùa RieLie, chú ý
đảo ngược vỊ trí củ a Lie và Rig.
if ’
//
40
8
48
16
56
24
64
32
39
7
47
15
55
23
63
31
38
6
46
14
54
22
62
30
37
5
13
53
21
61
29
36
35
4
45
44
52
20
60
3
43
12
11
51
19
59
28
27
34
2
1
42
10
50
41
9
49
18
17
58
57
33
26
25
Hình 5.3
B • Hàm f(A,J)
Đ ầu vào của h à m f là đối s ố A, m ột dây 32bit, đối sô' th ứ
h a i là J gồm 48bit, v à đầu ra của f là m ột dãy 32bit. Các bưốc
sa u đây được thực hiện:
1.
Mỏ rộn g A từ 32bit th à n h 48bit: Đ ôl
rộng th àn h 4 8 b it nh ò toán tử E
số A được mỏ
156
Nhập môn Phân tích thông tin có hào mật
2. T ính B = E ( A ) 0 J : K ết quả B được tách th àn h 8 khối,
m ỗi
B
khối
gồm
6b it
liê n
tiếp
từ
B 1B2....BX cụ
th ể
là
—
3. Sử d ụ n g 8 hộp S: S |,S 2,...,S8
M ỗi hộp Sị là m ột m ả n g h a i chiều 4x16, m ỗi dòng chứa
các giá trị từ 0 đến 15. T a có đầu vào Bj là một dãy 6bit
Bj = bibababíbgbg. H ai b it bịbe xác định biểu diễn nhị phân
củ a r là chỉ sô' dòng củ a Sj (0 < r < 3) và 4bit b2b3b4bs xác định
b iểu diễn n h ị p h ân c ù a c là ch ỉ s ố cột củ a Sj (0 < c < 15). S au
đó Sj(Bj) là sô' n ằm ỏ tọ a độ (r,c) gồm 4bit.
T heo cách này, ta k ý h iệu Cj = Sj(Bj), (1 ^ ^ 8).
4. Dòng bit c = C,C2C3C4C5C6C7C8 với độ dài 32bit được
đổi chỗ th eo h o á n v ị p . K ết quả dăy P(C) ch ín h là f(A,J). Cụ
th ể f(A,J) = P(C).
Hàm f được thể hiện trong hình 5.4 dưối đây:
Chương 5: M ột sổ phương pháp thảm mã dừ liệ u D E S
157
Nhập môn Phăn tich thông tin có bảo mật
158
8 hộp
s
và hoán vị P:
Si
14
4
13
1
2
15
11
8
3
10
6
12
5
9
0
7
0
15
7
4
14
2
13
1
10
6
12
11
9
5
3
8
4
1
14
8
13
6
2
11
16
12
9
7
3
10
5
0
15
12
8
2
4
9
1
7
5
11
3
14
10
0
6
13
7
2
13
12
0
5
10
15
1
8
14
6
11
3
S2
4
9
3
4
7
15
2
8
14
12
0
1
10
6
9
11
5
0
13
14
7
11
10
4
1
5
8
9
3
2
15
8
10
1
3
15
2
11
6
12
7
6
13
13
4
12
0
5
14
9
S3
10
0
9
14
6
3
15
5
1
13
12
7
11
4
2
8
13
7
0
9
3
4
6
10
2
8
5
14
12
11
15
1
13
6
4
9
8
15
3
0
11
1
2
12
5
10
14
7
3
10
13
0
6
9
8
7
4
15
14
3
11
5
2
12
S4
7
13
14
3
0
6
9
10
1
2
8
5
11
12
4
15
13
8
11
5
6
15
0
3
4
7
2
12
1
10
14
9
10
6
9
0
12
11
7
13
15
1
3
14
5
2
8
4
3
15
0
6
10
1
13
8
9
4
5
11
12
7
2
14
8
5
3
15
13
0
14
9
5
0
15
10
3
9
8
6
Ss
2
12
4
1
7
10
11
14
11
2
12
4
7
13
6
1
4
2
1
11
10
13
7
8
15
9
12
5
6
3
0
14
11
8
12
7
1
14
2
13
6
15
0
9
10
4
5
3
159
Chương 5: M ột sổ phương pháp thám mà dừ liệ u D E S
Se
12
1
10
15
9
2
6
8
0
13
3
4
14
7
5
11
10
15
4
2
7
12
9
5
6
1
13
14
0
11
3
8
9
14
15
5
2
8
12
3
7
0
4
10
1
13
11
6
4
3
2
12
9
5
15
10
11
14
1
7
6
0
8
13
S7
4
11
2
14
15
0
8
13
3
12
9
7
5
10
6
1
13
0
11
7
4
9
1
10
14
3
5
12
2
15
8
6
1
4
11
13
12
3
7
14
10
15
6
8
0
5
9
2
6
11
13
8
1
4
10
7
9
5
0
15
14
2
3
12
Se
13
2
8
4
6
15
11
1
10
9
3
14
5
0
12
7
1
15
13
8
10
3
7
4
12
5
6
11
0
14
9
2
7
11
4
1
12
14
2
0
6
10
13
15
3
5
2
1
14
7
9
4
10
8
13
15
12
9
0
3
5
6
8
11
H oán vị P:
16
7
20
21
29
12
28
17
1
15
23
26
5
18
31
10
2
8
24
14
32
27
3
9
19
13
30
6
22
11
4
25
c - Lược đồ tạo hệ thỂmg ktìoá
Khoá K là m ột dãy 64bit trong đó các bit th ứ 8, 16, 24,
32,40, 48, 56, 64 là các bit k iểm tra. Các b it kiểm tra n ày sẽ
160
Nhập môn Phân tích thông tin cô bảo một
được bỏ qu a trong qu á trìn h tạo khoá, như vậy ta còn lại
56bit đầu vào. Cho 5 6 b it này hoán vị như theo bảng PC-1 ta
sẽ tìm được CqD q với Co là 28bit đầu tiê n của PC -1, Do là
28bit còn lại.
P C -l(K ) = CoDo
Với i = 1 ^ 16 ta tính:
Q = L S ì(C m )
Di = LS ì(D m )
LSị th ể h iện p h ép dịch trái quay vòng m ột hoặc hai bit,
phụ thuộc vào g iá trị của i, dịch một bit n ếu i = 1, 2, 9, 16 và
dịch h ai b it vổi các g iá trị còn lạ i của i. Kj được tính theo CịDị
qua bảng h oán vỊ P C -2.
Ki = PC-2(CiDi)
PC-2
PC-1
57
49
41
33
25
17
9
14
17
11
24
1
5
1
58
50
42
34
26
18
3
28
15
6
21
10
10
2
59
51
43
35
27
23
19
12
4
26
98
19
11
60
52
44
36
16
7
27
20
13
2
63
55
3
47
39
31
23
15
41
52
31
37
47
55
7
62
54
46
38
22
S3
51
48
61
40
46
6
30
33
14
45
30
37
13
5
28
20
12
4
49
39
56
34
21
44
53
46
42
50
36
29
32
29
Từ P C -1 ch u y ển s a n g P C -2 bỏ đi 8 sô" (8 vị trí): 54, 57,58,
59, 60, 61, 62, 63.
Chương 5: M ột số phương pháp thám mã dữ liệ u D E S
161
Co: 28bit đầu;
Do: 28bit cuối;
i = 1 . 2 , 9 . 16 thi La dịch trải vòng Ibit (bit)
Hình 5.5. Lược đồ tạo hệ thông khóa
é
N h ư vậy ta đã có m ột th u ậ t to á n h o à n ch ỉn h v ề m ã hoá
dữ liệ u theo tiê u ch u ẩn D E S.
162
Nhập môn Phân tích thông tin có bào mật
Hừih 5.6. Sơ đồ thuật toán mã hóa DES
Chương 5: M ột số phương pháp thảm mã dừ liệu D E S
163
5 .1 .2 . G iải m â DES
Tương tự nh ư m ă hoá, đ ể giải m ă m ột dăy ký tự đâ được
m ã hoá ta cũ n g thực h iệ n th eo trìn h tự các bưdc như trên ,
tu y n h iên h ệ th ổ h g kh oá lú c n ày đã được tạo th eo ch iều
ngước lại.
/. Thuật toán
Mã hoắ
Cho bản rõ X
Xo = IP(x) = LqRo
i = 1,2,..., 16
L i = R j.j
Yo ~
y = iP -‘(yo)
Giải mã
Cho b ản m ã y
Yo = IP(y) = RieLie = L’oR 0
i = 1,2,...,16
L’ = R V i
Xq ~ ( R 16^ le)
X = IP-*(Xo)
164_______________ Nhập môn Phân rích thông tin có báo một
2. Chúhg minh thuật toán
Có bản m ã y
yo = IP(y) = IP(IP-*(R,eL,6)) = R ,e L ,6 = L ’oR’o
V ậ y L ’o = R ,6 ;R ’o = L,e;
Với i = 1
L \ = R ’o = L,e = R,s;
R ’, = L ’o^f(R’o.Ki6)
~
~ Li5^f(Ri5KỊg)^f(Ri5KỊg) = Ljs;
Tóm lại:
♦
L 1= Risỉ
1~ L j5;
Tương tự như vậy cho đến khi i = 16 ta sẽ có:
L
1 6
~
R
1 5
~
=
R
q
;
R’,e = L’,s''f(R’,5.K,) = R,'^f(L„K,)
= LoAf(R^,K,)Af(R„,K,) = Lo;
L’i6 “
~
X = IP-‘(R\6, L’,6) = IP-’(Ro Lo) = IP-‘(Xo)
Từ đó ta th ấ y th u ậ t toán giải mâ ch ỉ k h á c với th u ậ t toán
m ã hoá
ỗ chỗ tạo h ệ th ốh g khoá. N ếu m ã hoá tạo khoá từ
k ],k2,.~.kj6 th i giải m ă tạo h ệ th ốhg khoá từ kje,k,g,..,ki.
165
Chương 5: M ộ i 5Óphương pháp thám mã dữ liệu D E S
5.1.3. Thám mã vi sai dối với các khôi mã lặp
T hông thường các h ệ m ã khôi khóa bí m ật được th iế t k ế
dự a trên cơ sò lặp m ột hàm tương đối yếu v ề m ặt m ật m ã nào
đó (để có tốc độ cao, th iế t k ế đdn giản...). M ỗi phép lặp được
gọỉ là m ột vòng. Đ ầu vào của mỗi vòng là hàm của đầu ra của
vòn g trước và m ột k h óa con đưỢc th iết k ế từ khóa bí m ật ban
đ ầ u theo lược
• đồ tạo
• khóa. M ột
• m ã khối khóa bí m ật
• vdi r
p h ép lặp như th ế được gọi là m ột m ã lặp r vòng. Các h ệ D E S
h a y ID EA đều là m à k h ổ ì lặp theo quan niệm trên. P h ần này
ta sẽ xem x é t n g u y ên lý tấ n công vi sa i đôì với m ã lặp có
d ạ n g tổng q u á t nh ư trên h ìn h 5.7.
H ìn h
5.7. Phép mả hóa một cặp bản rõ vói mã lặp r vòng
Với các ký h iệu n h ư trong h ìn h 5.7, ta có Y = f(X, Z) là
m ột hàm vòng sao ch o với m ỗi khóa con
z,
hàm f(., Z) th iế t
lập m ột tưdng ứ ng 1-1 giữ a đầu vào X và đầu ra Y.
Vi sai AX giữ a h a i b ản rõ (hay h ai bản mà) X và X* được
xác đ ịn h bỏi:
Àx =
X ® X*-‘
ỏ đây ® ký h iệu ỉà phép toán nhóm đă xác định nào đó
tr ên tập các bản rõ
(= tập
các bản mã), và
x*‘*là
ngh ịch đảo
c ủ a các phần tử X* tron g nhóm đó. H àm vòn g f(X, Z) được gọi
166
Nhập môn Phân tich thông tin có bảo mật
là yếu n ếu cho trước m ột vài bộ ba (AX, Y, Y*) là có thể xác
đ ịn h được khóa z . Từ cặp các phép m ã hóa ch ú n g ta có th ể
xác định được m ột dãy các vi sa i AY(0), AY(1),..., AY(r), ở đây
Y(0) = X, và ¥^(0) = X* là cặp bản rõ, cũ n g vậy AY(0) = AX,
còn Y(i) và Y*(i) là đầu ra của vòng th ứ i, chún g cũng là đầu
vào của vòng thứ (i+1). Khóa con cho vòng th ứ i ký hiệu là
z®. T rong các lập lu ậ n sa u này ta luôn giả thiết X * X*.
Thấm mã vi sai dựa trên yếu tô'là hàm vồng f trong một
mả khôi lặp là một hàm yếu về mật mà. Cạ thể nếu cập bản
mẵ được biết và bằng cách nào đó có thể đạt được vi sai của
cặp đấu vào tại vòng cuối cùng cùa mã khôĩ lặp đó, thì tốn
công vi sai có thể áp dụng dể đạt dược hoặc xác định được
khóa hay một phần khóa con tại vòng cuối cùng. Trong thám
mã vi sai điều đó dược thực hiện bằng cách chọn cặp bản rỗ
(X, X“) có vi sai ìà a sao cho VI sai AY(r-l) của cặp đầu vào tại
vòng cuối cùng sẽ lấy giá trị cạ th ểp với một xác suất cao. Vì
có xác suất cao nên các khóa con tại vòng cuổì được giải từ bộ
ba (AY(r-l), Y(r), Yir)) sẽ thường tập trung vào một sô'phần
tử có khả nàng nhất, thám mã sê quyết định để tim ra khóa
con đúng tại vồng cuôĩ cùng. Từ khóa con của vòng cuôĩ này,
tã có thểxảc định được lại khóa bí mật ban đầu (nếu lược đồ
tạo khóa là đơn giản).
Định nghĩa 1: M ột v ỉ sa i i vòng là m ột cặp (a , P), ỏ đây a
là vi sa i của m ột cặp b ản rõ khác n h au X v à x \ và p là m ột vi
s a i có th ể đôi với k ết quả đầu ra vòng th ứ i là Y(i) và Y*(i).
Xác su ấ t củ a v i sa i i vòng (a, P) là xác su ấ t có điều kiện sao
cho p là vi sa i AY(Ì) củ a cặp bản mă sa u i vòng với điều kiện
Chương 5: M ột sổ phương pháp thám mã dừ liệu D E S
167
cho trưốc cặp bản rõ (X, X*) có vi sa i AX = a khi bản rõ X và
các khóa con
là ngẫu nh iên độc lập phân bô' đều.
Ta ký hiệu xác su ấ t củ a vi sai này là P(AY(i) = p IAX = a).
Thủ tục cơ bản của tân công vi sai đối váf một mã khối lặp
*
r vòng:
1. T ìm m ột vi sa i (r-1) vòng (a, P) sao cho xác suất:
P(A Y (i-l) = P|AX = a ) là cực đại hoặc gần cực đại.
2. Lấy bản rõ X m ột cách ngẫu n h iên đều và tín h toán X*
sa o cho vi sa i AX giữ a X và X* là a . T iến h àn h m ã hóa X và X*
dưới m ột khóa bí m ật cụ th ể cần tìm z (m à đôl phương đang
sử dụng). Từ các bản m ã k ết quả Y(r) và Y*(r), tìm mỗi m ột
giá trị có th ể cù a kh óa con
của vòng cuối cùng tướng ứng
vối vi sa i đâ đ ịn h trước A Y (i-l) = p (tức là sử dụng bộ ba
AY(ì-1) đặt b ằn g p, Y(r), Y*(r) để tín h toán tìm
vào bộ đếm
T hêm 1
số lần x u ấ t h iện cùa mỗi giá trị có th ể có cùa
khóa con
3. Lặp lạ i bước 2 cho tới khi m ột hoặc n h iều giá t i ị của
khóa con
là được đếm n h iều hơn hẳn các giá trị khác. Lấy
ra khóa con đưỢc đếm n h iều n h ất hoặc m ột tập nhỏ các khóa
có sô' đếm lón nhất. S a u đó việc quyết định khóa đúng thuộc
v ề ngưòi thám mã.
C hú ý rằn g trong tấ n công vi sai, tấ t cả các khóa con là
n gẫu n h iên , độc lập v à có phân b ố đều. T uy n h iên trong tín h
toán xác su ấ t vi sai, ta luôn giả th iết bản rõ và tấ t cả các
kh óa con là độc lập n g ẫ u n h iên đều. D o đó chún g ta cần tạo
m ột g iả th iết sau:
168_______________ Nhập môn Phân tich thông tin có bảo mật
*
Giả thiết về tính tương đương ngẫu nhiên (Stocbastic
Equivalence)
Đ ối với m ột vi sa i (r-1) vòng (a, P), ta có:
P(AY(i-l) = p IAX = a ) « P(AY(i-l) = p IAX = a, z<» = 0)i....
2^-^^ với h ầu h ế t tập giá trị khóa con (0)i, 0 >2 , . . . ,
Do có 2™ - 1 giá trị cùa A Y (i-l), nên ch ú n g ta có th ể rút
ra k ết lu ậ n sau:
Giả sù giẳ thiết về tính tương đương là đúng, khi đó một
mả lặp r vòng với tập khóa con độc lập sẽ có thể bị tổn
thương đôì với tấn công vi sai nếu và chỉ nếu hàm vòng là
yếu và tồn tại một vi sai (r-1) vòng (a, P), sao cho
P(ÁY(i-l) - ậỊÁX = a) » 2’”', ở đây m là độ dài của khôi mã.
Ký h iệu Comp(r) là độ phức tạp của m ột tấ n công thám
m ã với m ã ỉặp r vòng, xem như là sô' phép m ã hóa cần sử dụng
trong tấn công. Khi đó ta có th ể chứ ng m inh kết quả sau:
Định lý 1: (Cận dưối v ề độ phức tạp của tấ n công v i sai
đôi với m ột m ã ỉặp r vòng)
G iả sử giả th iết v ề tín h tương đưdng n gẫu n h iên ỉà đúng,
k h i đó độ phức tạp của tấn công vi sa i sẽ thỏa m ãn đánh giá:
p.
1
^
T -\)
Ồ đầy
= maxainaxp P(A Y (i-l) = p IAX = a), trong đó m là
độ dài ỉdiôl mã.
Thực t ế nếu
th à n h công.
« 1/(2“ - 1), th ì tấ n công vi sai là không
Chương 5: M ột số phương pháp thảm mã dừ liệ u D ES
169
Chứng minh: Chú ý rằ n g giá trị tín h trước p cùa vi sa i
AY(ì-1> ít n h ất phải lấ y n h iều hơn m ột lầ n so vói giá trị khi
chọn tru n g bình ngẫu n h iên p', nếu nh ư tấn công vi sai
th àn h công. N hư vậy, ta có T P „ „ > (T/(2"‘ - 1)) + 1 là điều
k iện c ầ n cho sự th à n h công sa u T phép thử, ỏ đây m ỗi phép
thử gồm phép chọn m ột cặp b ản rõ có vi sa i a cho trước.
T ừ đó ta có: 2.T .(P „„ - 1/(2'" - 1)) > 2,
m à Comp(r) = 2.T (m ỗi phép thử có 2 phép m ã cho cặp bản
rõ), nên: Comp(r) = 2.T > 2/(Pmax -
- 1))
(đpcm).
5 .1 .4 . Sơ bộ về phương pháp tân công vi sai trên DES
Phương pháp tấ n công v i sa i (DC) trên D E S do B iham và
S h am ir đề x u ấ t là m ột tron g nhữ ng phưdng pháp tấ n công
nổi tiế n g n h ấ t đối với hệ D E S. Đ ây là phép tấn công với bản
rõ chọn lọc, và nó đã khai th á c triệt để điểm yếu của D E S tại
các hộp nén. B ây giò ta sẽ mô tả ý tư ỏng cơ bản dùng trong
tấ n công này.
Trước h ế t ta sẽ bỏ qua p h ép h o á n vỊ đ ầu IP và h oán v ị
ngưỢc củ a nó (k hông ản h h ư ỏ n g tới k ế t quả p h â n tích m ã),
k h i đó có th ể xem LộRo là b ả n rõ và L „R „ là bản m ă D E S
m vòn g.
Phương pháp th á m m ã m ã vi sa i xoay quanh việc so
sá n h k ết quả của phép XOR giữa 2 bản rõ vối k ết quả của
p h ép XOR giữa 2 bản m ã tương úng. Với giả th iết rằng các
b ản rõ được lấy ngẫu n h iên đểu trên không gian các đầu vào
có th ể, ta quan sá t p h ân bô' củ a các k ết quả phép XOR đầu ra
Nhập môn Phân tích thông tin có bảo mật
170
có tu ân theo phân bố n gẫu nhiên đểu hay không. N ếu bảng
phân b ố là không đều, th ì thám m ă sẻ lợi dụng để xây dựng
phương pháp tấn công bản rõ chọn lọc.
Định nghĩa 2: G iả sử Sj là một hộp nén (1 < j < 8). Xét 1
cặp đã sắp xếp của các xâu bit độ dài 6 (ký hiệu là
Ta nói rằng XOR vào của Sj là Bj 0 Bj và XOR ra của Sj là
Sj(Bi)eSj(B‘). VB' € z ị, ta đặt:
à (B ;) = { ( B j ,B j e B ') : B ; € Z 5 ì
Định nghĩa 3
Với 1 < j < 8, B' €
zị,c'
6 z ị , ta định nghĩa:
IN j(B ',C j) = {(Bj 6 z ị :S^(Bj)®Sj(Bj e B ' ) = C '}
V à N j(B ',C ') = ||lN j(B ',C ')
N hư vậy, N j(B j,C ' ) là s ố các cặp có XOR vào là B' và có
XOR ra là C ;.
Nhớ lạ i rằng, đầu vào của các hộp n én ỏ vòng thứ i là
B = E©J, trong đó E = E(Rị.i) là giá trị cùa hàm mồ rộng E
tác động vào Rj.i và J = Kj là các bit khóa vòng thứ i. Khi đó
XOR vào của tấ t cả 8 hộp nén có th ể được tín h như sau:
B0 B* = (E 0 J )e (E*®J) = E©E*
Đ ến đây ta th ấ y m ột điều rất quan trọng là XOR vào
không phụ thuộc vào các bit khóa J, như ng XOR ra chắc
Chương 5: M ột số phương pháp thám mã dừ liệu D E S
171
ch ắn phụ thuộc vào các bit khóa này, và các XOR vào của các
hộp nén sẽ được tín h qua giá trị của hàm mỏ rộng E đã được
b iết công khai.
Bây giờ ta viết B, E và J là m ột dây liên tiếp 8 xâu 6 bit:
B = B 1B2B3B4B5B6B7B8
E = E,E2E3E4E5E6E7Eg
J=J,J2J3J4J5W7J8
và B*, E' th eo cách tương tự. Khi đó nếu b iết các giá trị Ej, E*
và giá trị XOR ra của Sj là C j , th ì chắc ch ắn rằng:
E j0 J j€ lN j(E ',C j)
Từ đó ta định n gh ĩa các tập TEST cho đoạn khóa con Jj
như sau:
Định nghĩa 4
Vối các ký hiệu đã nêu ta xác định;
TESTj(EjE;,C'j) = {Bj © E j : Bj e INj(E',Cj)}
trong đó: Ej = Ej 0 Ej
Từ định nghĩa này ta có ngay k ết quả sa u đây:
Định lý 2
Giả sử Ej và E* là h a i xâu vào của hộp nén Sj còn XOR
ra của Sj là Cj. Khi đó các bit khóa Jj sẽ nằm trong tập
TESTj(EjE’ ,C ')-
Nhập môn Phân tich thông tin có bảo mật
172
B ây giò ta áp d ụ ng các ý tưỏng trên đây để mô tả phương
pháp tấ n công vi sa i trên D ES.
Với DES 3 vòng. Ta có th ể viết:
R3=L2©F(R2, K3)
= R, © F(R2, K3)
= Lo © F (R o,K ,)© F (R 2 ,K 3 )
B iểu diễn R3 m ột cách tương tự, ta có:
R*3 = L Í,eF (R o ,K ,) 0 F(R;,K,)®F(R 2 ,K 3 )® F (R ;,K 3 )
N ếu ta chọn R q= 00...0, thì:
R ;= L 'o e F (R 2 ,K 3 )e F (R ;,K 3 )
B ây giò, do R3,Lq đã biết nên có th ể tín h được:
F (R 2 , K 3 ) © F(R 2 , K 3 ) = R'3 © Ló
M ặt khác, ta CÓF(R2,K 3) = P(C), F(R2,K 3>= P ( c ‘ ) và do
tín h đồng cấu tu y ến tín h của phép h oán vị p n ên ta tín h
được:
c =cec
= p - '( R 3 0LÓ ). Đ ây là XOR ra cùa 8 hộp
n én ỏ vòng th ứ ba.
Còn R2 = L3 và R 2 = L*3 cũng được b iết (chúng là m ột
ph ần của các bản m ã), nên cố th ể tín h được các dữ ỉỉệu ỉiên
quan đến đầu vào của các hộp nén là E = EíLg) và E*= E(L*3).
N hư vậy ta đă b iết E, E* và C' củ a vòng thứ ba và từ đó
có th ể x â y dựng các tập TESTi...TESTg chứ a các g iá trị có th ể
củ a các bit khóa J iJ 2...Jg.
- Xem thêm -