Chương 3
Chuẩn mã dữ liệu DES
(Data Encryption Standard)
3.1. Giới thiệu chung về DES
Chuẩn mã hoá dữ liệu DES được Văn phòng tiêu chuẩn của Mỹ (U.S
National Bureau for Standards) công bố năm 1971 để sử dụng trong các cơ
quan chính phủ liên bang. Giải thuật được phát triển tại Công ty IBM dựa
trên hệ mã hoá LUCIFER của Feistel.
DES là thuật toán mã hoá khối (block algrithm), với cỡ của một khối
là 64 bít. Một khối 64 bít bản rõ được đưa vào, sau khi mã hoá dữ liệu đưa
ra là một khối bản mã 64 bít. Cả mã hoá và giải mã đều sử dụng cùng một
thuật toán và khoá.
Khoá mã có độ dài 64 bít, trong đó có 8 bít chẵn lẻ được sử dụng để
kiểm soát lỗi. Các bít chẵn lẻ nằm ở các vị trí 8, 16, 24,..., 64. Tức là cứ 8
bít khoá thì trong đó có 1 bít kiểm soát lỗi, bít này qui định số bít có giá trị
“1” của khối 8 bít đó theo tính bù chẵn.
Nền tảng để xây dựng khối của DES là sự kết hợp đơn giản của các
kỹ thuật thay thế và hoán vị bản rõ dựa trên khoá. DES sử dụng 16 vòng
lặp, nó áp dụng cùng một kiểu kết hợp của các kỹ thuật trên khối bản rõ 16
lần (Như sơ đồ mã)
Thuật toán chỉ sử dụng các phép toán số học và lôgíc trên các số 64
bít, vì vậy nó dễ dàng thực hiện vào những năm 1970 trong điều kiện về
công nghệ phần cứng lúc bấy giờ. Ban đầu, sự thực hiện các phần mềm
kiểu này rất thô sơ, nhưng hiện tại thì việc đó đã tốt hơn, và với đặc tính lặp

55


đi lặp lại của thuật toán đã tạo nên ý tưởng sử dụng chíp với mục đích đặc
biệt này.
DES có một số đặc điểm sau:


Ri-1

Ki

E

E(Ri-1)
+
B1B2B3B4B5B6B7B8

S1

S2

S3

S4

S5

S6

S7

c1c2c3c4c5c6c7c8

f(Ri-1,Ki)

Khối Ri-1 có độ dài 32 bít cho đi qua hoàn vị mở rộng E được một


LS1
C1

D0
LS1

D1

D1

PC-2

K1

PC-2

K16

.
.
LS16
C16

LS16
D16

D16

60


12

13

14

15

16

Số bít dịch

1 1 2

2

2

2

2

2

1

2

2


2

60

52

44

36

28

20

12

4

62

54

46

38

30

22


17

9

1

59

51

43

35

27

19

11

3

61

53

45

37


3.4. Hoán vị chọn
Đầu tiên, khoá 64 bít được giảm xuống thành một khoá 56 bít bằng
cách bỏ qua 8 bít chẵn lẻ. Sự loại bỏ được thực hiện theo Bảng sau:
Bảng hoán vị chọn PC1:
57

49

41

33

25

17

9

1

58

50

42

34

26


63

55

47

39

31

23

15

7

62

54

46

38

30

22

14

Bảng hoán vị chọn PC2:
14

17

11

24

1

5

3

28

15

6

21

10

23

19

12


30

40

51

45

33

48

44

49

39

56

34

53

46

42

50

3

4

5

4

5

6

7

8

9

8

9

10

11

12

12


23

24

25

24

25

26

27

28

29

28

29

30

31

32

1


3.6. Hộp thay thế S
Sau khi được nén, khoá được XOR với khối mở rộng, 48 bít kết quả
được chuyển sang giai đoạn thay thế. Sự thay thế được thực hiện bởi 8 hộp
thay thế (substitution boxes, S-boxes). Khối 48 bít được chia thành 8 khối 6
bít. Mỗi khối được thực hiện trên một hộp S riêng biệt (separate S-box):
khối 1 được thực hiện trên hộp S1, khối 2 được thực hiện trên hộp S 2,... ,
khối 8 được thực hiện trên hộp S8.
Hộp S thứ nhất
14

4

13

1

2

15

11

8

3

10

6


12

11

9

5

3

8

4

1

14

8

13

6

2

11

15


5

11

3

14

10

0

6

13

Hộp S thứ 2
15

1

8

14

6

11

3


8

14

12

0

1

10

6

9

11

5

0

14

7

11

10


3

15

4

2

11

6

7

12

0

5

14

9

Hộp S thứ 3
10

0


7

0

9

3

4

6

10

2

8

5

14

12

11

15

1


7

1

10

13

0

6

9

8

7

4

15

14

3

11

5


5

11

12

4

15

13

8

11

5

6

15

0

3

4

7


1

3

14

5

2

8

4

3

15

0

6

10

1

13

8



6

8

5

3

15

13

0

14

9

14

11

2

12

4

7


13

7

8

15

9

12

5

6

3

0

14

11

8

12

7


1

10

15

9

2

6

8

0

13

3

4

14

7

5

11


8

9

14

15

5

2

8

12

3

7

0

4

10

1

13


0

8

13

Hộp S thứ 7
4

11

2

14

15

0

8

13

3

12

9


5

12

2

15

8

6

1

4

11

13

12

3

7

14

10


9

5

0

15

14

2

3

12

Hộp S thứ 8
13

2

8

4

6

15

11


7

4

12

5

6

11

0

14

9

2

7

11

4

1

9


4

10

8

13

15

12

9

0

3

5

6

11

3.7. Hộp hoán vị P
Khối dữ liệu 32 bít ra của hộp thay thế S được hoán vị tiếp trong hộp
P. Sự hoán vị này ánh xạ mỗi bít dữ liệu vào tới một vị trí trong khối dữ
liệu ra, không bít nào được sử dụng hai lần và cũng không bít nào bị bỏ
qua. Nó được gọi là hoán vị trực tiếp (straight permutation). Bảng hoán vị

vòng mới được tiếp tục.
3.8. Hoán vị cuối cùng
Hoán vị cuối cùng là nghịch đảo của hoán vị khởi đầu, và nó được
mô tả trong bảng dưới. Chú ý rằng nửa trái và nửa phải không được tráo
đổi sau vòng cuối cùng của DES, thay vào đó khối nối R 16L16 được sử dụng
như khối dữ liệu ra của hoán vị cuối cùng. Không có gì đưa ra ở đây; tráo
đổi các nửa và dịch vòng hoán vị sẽ cho chính xác như kết quả trước, điều
đó có nghĩa là thuật toán có thể được sử dụng cho cả mã hoá và giải mã.
Bảng hoán vị cuối cùng:
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

45 13 53 21 61 29

36 4

44 12 52 20 60 28 35 3

43 11 51 19 59 27

34 2

42 10 50 18 58 26 33 1

và Motorola.
Bảng tốc độ của DES trên các bộ vi xử lý khác nhau
Tốc độ

BUS

Khối DES

Bộ vi xử lý

( Mhz )

( bít )

(/giây)

8088

4.7

8

370

68000

7.6

16



25.0

16

5.000

68030

50.0

32

9.600

68040

25.0

32

16.000

68040

40.0

32

23.200



mất nhiều nhất 256 lần thử để tìm ra khoá đúng. Nếu khoá có độ dài 56 bít,
thì sẽ có 256 khoá có thể sử dụng. Giả sử một Suppercomputer có thể thử
một triệu khoá trong một giây, thì nó sẽ cần 2000 năm để tìm ra khoá đúng.
Nếu khoá có độ dài 64 bít, thì với chiếc máy trên sẽ cần 600,000 năm để
tìm ra khoá đúng trong số 264 khoá. Nếu khoá có độ dài 128 bít, thì sẽ mất
1025 năm để tìm ra khoá đúng. Vũ trụ chỉ mới tồn tại 10 10 năm, vì vậy 1025
thì một thời gian quá dài. Với một khoá 2048 bít, một máy tính song song
thực hiện hàng tỉ tỉ phép thử trong một giây sẽ tiêu tốn một khoảng thời
gian là 10597 năm để tìm ra khoá. Lúc đó vũ trụ có lẽ không còn tồn tại nữa.
Khi IBM đưa ra thiết kế đầu tiên của hệ mã hoá LUCIFER, nó có
khoá dài 128 bít. Ngày nay, DES đã trở thành một chuẩn về mã hoá dữ liệu
sử dụng khoá 56 bít, tức kích thước không gian khoá là 2 56. Rất nhiều nhà
mã hoá hiện đang tranh luận về một khoá dài hơn của DES. Nhiều thiết bị
chuyên dụng đã được đề xuất nhằm phục vụ cho việc tấn công DES với bản
rõ đã biết. Sự tấn công này chủ yếu thực hiện tìm khoá theo phương pháp
vét cạn. Tức với bản rõ X 64 bít và bản mã Y tương ứng, mỗi khoá có thể
đều được kiểm tra cho tới khi tìm được một khoá k thoả mãn E k(X)=Y (có
thể có nhiều hơn một khoá k như vậy).
Vào năm 1979, Diffie và Hellman tuyên bố rằng với một máy tính
chuyên dụng bản mã hoá DES có thể được phá bằng cách thử mọi trường
hợp của khoá trong vòng một ngày và giá của máy tính đó là 20 triệu đôla.
Vào năm 1981, Diffie đã tăng lên là cần hai ngày để tìm kiếm và giá của
chiếc máy tính đó là 50 triệu đôla.
3.12. Tranh luận về DES.
Khi DES được đề xuất như một chuẩn mật mã, đã có rất nhiều ý kiến
phê phán. Một lý do phản đối DES có liên quan đến các hộp S. Mọi tính
toán liên quan đến DES ngoại trừ các hộp S đều tuyến tính, tức việc tính


72


mẫu vào làm cho bít này bằng 1. Với các bít vào từ bít thứ hai đến bít thứ 5
thì điều này không còn đúng nữa. Tuy nhiên phân bố kết quả vẫn gần với
phân bố đều. Chính xác hơn, với một hộp S bất kì, nếu ta cố định giá trị của
một bít vào bất kì thì số mẫu vào làm cho một bít ra cố định nào đó có giá
trị 0 (hoặc 1) luôn nằm trong khoảng từ 13 đến 19.
Người ta không biết rõ là liệu có còn một chuẩn thiết kế nào đầy đủ
hơn được dùng trong việc xây dựng hộp S hay không.
Sự phản đối xác đáng nhất về DES chính là kích thước của không
gian khoá: 256 là quá nhỏ để đảm bảo an toàn thực sự. Nhiều thiết bi chuyên
dụng đã được đè xuất nhằm phục vụ cho việc tấn công với bản rõ đã biết.
Phép tấn công này chủ yếu thực hiện tìm khoá theo phương pháp vét cạn.
Tức với bản rõ x 64 bít và bản mã y tương ứng, mỗi khoá đều có thể được
kiểm tra cho tới khi tìm được một khoá K thảo mãn e K(x) = y. Cần chú ý là
có thể có nhiều hơn một khoá K như vậy).
Ngay từ năm 1977, Diffie và Hellman đã gợi ý rằng có thể xây dựng
một chíp VLSI (mạch tích hợp mật độ lớn) có khả năng kiểm tra được
106khoá/giây. Một máy có thể tìm toàn bộ không gian khoá cỡ 10 6 trong
khoảng 1 ngày. Họ ước tính chi phí để tạo một máy như vậy khoảng 2.107$.
Trong cuộc hội thảo tại hội nghị CRYPTO’93, Michael Wiener đã
đưa ra một thiết kế rất cụ thể về máy tìm khoá. Máy này có khả năng thực
hiện đồng thời 16 phép mã và tốc độ tới 5× 107 khoá/giây. Với công nghệ
hiện nay, chi phí chế tạo khoảng 10,5$/khung. Giá của một khung máy
chứa 5760 chíp vào khoảng 100.000$ và như vậy nó có khả năng tìm ra
một khoá của DES trong khoảng 1,5 ngày. Một thiết bị khung 10 khung
máy như vậy có giá chừng 106 $ sẽ giảm thời gian tìm kiếm khoá trng bình
xuống còn 3,5 giờ.


74


dãy các khối bản rõ cho trước x1,x2,. . .( mỗi khối có 64 bít), mỗi xi sẽ được
mã hoá bằng cùng một khoá k để tạo thành một chuỗi các khối bản mã y1y2
Ở chế độ CBC mỗi khối bản mã yi sẽ thực hiện phép XOR với bản rõ
xi+1 sau đó mới thực hiện mã theo quy tắc yi+1 = eK(yi⊕ xi+1) i ≥ 1. Việc sử
dụng chế độ CBC được mô tả như sau:

Chế độ CBC.
Chế độ CFB cũng xuất phát từ véc tơ khởi tạo ban đầu y 0=IV có độ dài 64
bít, được mã theo quy tắc: yi=ek(yi-1) ⊕xi-1 . Giải mã của cơ chế CFB theo
quy tắc: xi= ek(xi-1) ⊕ yi
Chế độ OFB cũng sử dụng véc tơ khởi tạo y 0=IV có độ dài 64 bít, mã theo
quy tắc: z1=ek(y0)
zi=ek(zi-1) với i=2,3,…
yi=zi ⊕ xi
75


Chế độ này sinh viên tự vẽ sơ đồ
Trong các chế độ OFB và CFB dòng khoá được tạo ra sẽ được cộng mod 2
với bản rõ (tức là nó hoạt động như một hệ mã dòng). OFB thực sự là một
hệ mã dòng đồng bộ: dòng khoá được tạo bởi việc mã lặp véc tơ khởi tạo
64 bít (véc tơ IV). Ta xác định z 0 =IV và rồi tính dòng khoá z1z2 . . . theo
quy tắc zi = eK(zi-1), i≥ 1. Dãy bản rõ x1x2 . . . sau đó sẽ được mã hoá bằng
cách tính yi = xi ⊕ zi,i ≥ 1.
Trong chế độ CFB, ta bắt đầu với y 0 = IV (là một véc tơ khởi tạo 64
bít) và tạo phần tử zi của dòng khoá bằng cách mã hoá khối bản mã trước
đó. Tức zi = eK(yi-1), i ≥ 1. Cũng như trong chế độ OFB: yi = xi ⊕ zi,i ≥ 1.

tạo các khối bản mã y 1,. . . ,yn theo khoá K. Cuối cùng ta xác định MAC là
yn. Alice sẽ phát đi dãy các khối bản rõ x 1,x2,. . . ,xn cùng với MAC. Khi
Bob thu được x1. . .xn anh ta sẽ khôi phục lại y1. . .yn bằng khoá K bí mật và
xác minh xem liệu yn có giống với MAC mà mình đã thu được hay không.
Nhận thấy Oscar không thể tạo ra một MAC hợp lệ do anh ta không
biết khoá K mà Alice và Bob đang dùng. Hơn nữa Oscar thu chặn được dãy
khối bản rõ x1. . .xn và thay đổi ít nhiều nội dung thì thì chắc chắn là Oscar
không thể thay đổi MAC để được Bob chấp nhận.
Thông thường ta muốn kết hợp cả tính xác thực lẫn độ bảo mật. Điều
đó có thể thực hiện như sau: Trước tiên Alice dùng khoá K1 để tạo MAC
cho x1. . . xn . Sau đó Alice xác định xn+1 là MAC rồi mã hoá dãy x1. . .x n+1
bằng khoá thứ hai K2 để tạo ra bản mã y1. . .yn+1 . Khi Bob thu được
y1. . .yn+1 , trước tiên Bob sẽ giải mã ( bằng K 2) và kiểm tra xem xn+1 có
phải là MAC đối với dãy x1. . .xn dùng K1 hay không.
Ngược lại, Alice có thể dùng K1 để mã hoá x1. . .xn và tạo ra
được y1...yn , sau đó dùng K2 để tạo MAC yn+1 đối với dãy y1. . .yn. Bob sẽ
dùng K2 để xác minh MAC và dung K1 để giải mã y1. . .yn

78


Chương 4
Mật mã công khai
4.1. Giới thiệu về hệ mật mã khóa công khai.
4.1.1. Giới thiệu.
Trong mô hình mật mã cổ điển mà cho tới nay vẫn còn đang được
nghiên cứu Alice (người gửi) và Bob (người nhận) bằng cách chọn một
khoá bí mật K. Sau đó Alice dùng khoá K để mã hoá theo luật e K và Bod
dùng khoá K đó để giải mã theo luật giải d K . Trong hệ mật này, d K hoặc
giống như eK hoặc dễ dàng nhận được từ nó vì quá trình giải mã hoàn