Mã nén lecture3- DES

Mã nén

Lecture 3: Chuẩn mã hóa dữ liệu

DES (Data Encryption Standard)

1 Vài nét về lịch sử phát triển DES

3 Chi tiết giải thuật mã hóa DES

I Vài nét về lịch sử phát triển DES

DES được công bố vào tháng 1 năm 1977, DES là một chuẩn đã được sử dụng rộng rãi cho bảo mật dữ liệu trong các hệ thống máy tính

Kể từ đó cứ 5 năm một lần, DES lại được Uỷ ban Tiêu chuẩn Quốc gia Mỹ xem xét lại Theo công bố năm 1998 thì mọi hệ DES, với những khả năng của máy tính hiện nay, đều có thể bẻ khóa trong vòng 2 giờ.

Tuy nhiên, cho đến nay DES vẫn là một mô hình chuẩn cho các ứng dụng bảo mật trong thực tế.

II Khái quát thuật toán mã hóa DES

- DES là thuật toán mã hóa khối (block cipher) nghĩa là

nó làm việc trên các khối bản rõ (plaintext blocks) 64

bít, (tương đương với 16 số hecxa) và trả về các khối

mã hóa (ciphertext blocks) cùng kích thước 64 bít.

- Để mã hóa, DES dùng các “keys” cũng có độ dài 64 bít

Tuy nhiên mỗi key đó có 8 bít bị lờ đi trong giải thuật

DES, vì vậy kích thước “key” thực sự là 56 bít.

Mô hình mã hóa DES

Bản tin rõ

Bản tin mã hóa

Khóa để mã hóa

Bản tin cần mã hóa

Bản đã mã hóa

0000000000000000

• Sơ đồ khối thực hiện giải thuật DES

- Input: Bản rõ M

- Output: Bản mã hóa C

* Các bước (lời giải thô):

B1: Khối bản rõ 64 bít được hoán vị(hoán vị khởi đầu) để thay đổi thứ tựcủa các bít

B2 : Chia bản rõ vừa hoán vị bít làm

hai nửa trái L0 và phải R0, mỗi nửa

32 bít

B3: Dùng 16 vòng lặp, tính LnRn(n=1 16) theo quy tắc:

Ln = Rn-1

Rn =Ln-1 + f(Rn-1 ,Kn)

B4: Tại vòng lặp cuối cùng n=16, tađươc L16 R16 , đổi vị trí 2 nửa này chonhau thành R16L16

B5: Hoán vị thứ tự bít cho R16L16, tađược đầu ra là bản mã hóa cần tìm

• Chi tiết các bước thực hiện của giải thuật DES

Để chi tiết hóa thuật toán DES, cần

D1 (28bits) C1 (28bits)

<< <<

D16 (28bits) C16 (28bits)

Ví dụ tạo các khóa con

• Giả sử khóa K ban đầu, áp dụng bảng PC-1 tính K+:

Ví dụ tạo các khóa con (tiếp)

• Vậy, qua 16 vòng lặp ta sẽ có các cặp từ C1D1 đến C16D16

• Để hình thành các khóa Kn, 1≤n≤16, ta phải dựa vào các

cặp CnDn đã tính ở trên và tra vào bảng hoán vị bít PC-2

?

?

f(R,K)

15 21 25 31

Bước 2: Tính E(Rn-1) ⊕ Kn và kết quả

48 bít được viết thành 8 khối: B1 B2 B3

B4 B5 B6 B7 B8, mỗi khối dài 6 bít: Bi= b1 b2 b3 b4 b5 b6 (i=1 8)

- Ví dụ: Giả sử khối đầu vào B 1 = 011011

* 2 bít b 1 b 6 = 01 , có giá trị thập phân là 1, nên

9 14

5 0

12 7

6 11

2 4

15 3

1 10

13

3

15 2

3 9

6 12

8 5

1 13

4 10

11 7

0

2

5 11

9 6

10 1

0 12

14 8

2 15

7 4

3

1

10 5

0 12

13 2

7 9

4 3

11 6

14 8

15

0

15 14

13 12

11 10

9 8

7 6

5 4

3 2

0

S 3

10 6 7 0

1

12 2

5 11

3 14

15 4

7 8

9 6

0 13

1

3

7 14

10 5

12 2

1 11

0 3

15 8

9 4

13

2

1 15

11 12

14 5

8 2

10 6

4 3

9 0

13

1

8 2

4 11

7 12

13 1

5 15

3 6

14 9

10

0

15 14

13 12

11 10

9 8

7 6

5 4

3 2

0

3 5

4 10

9 0

15 6

13 2

14 1

7 12

11

3

14 0

3 6

5 12

9 15

8 7

13 10

11 1

4

2

6 8

9 3

10 15

0 5

1 13

7 4

12 2

14

1

9 14

0 13

15 3

5 8

6 11

10 7

1 4

2

0

15 14

13 12

11 10

9 8

7 6

5 4

3 2

0

S 6

3 14 15 1

1

13 8

0 6

7 1

14 11

10 15

5 9

12 2

4

3

6 11

13 1

10 4

0 7

3 12

8 2

5 15

9

2

8 3

11 0

14 13

1 6

5 9

12 7

2 4

10

1

11 5

7 14

4 3

13 0

8 6

2 9

15 10

12

0

15 14

13 12

11 10

9 8

7 6

5 4

3 2

0

11 6

5 3

0 9

12 15

13 8

10 4

7 14

2

3

8 5

3 15

13 10

6 0

2 14

12 9

1 4

7

2

2 9

14 0

11 6

5 12

4 7

3 10

8 13

1

1

7 12

0 5

14 3

9 10

1 11

15 6

4 8

13

0

15 14

13 12

11 10

9 8

7 6

5 4

3 2

0

27 11

17

27 11

17

Vậy đến đây ta đã thực hiện xong

công việc tính toán hàm f

Vậy với bản rõ M: 0123456789ABCDEF

sau khi thực hiện giải thuật DES với khóa K=abcdefaa

sẽ cho ra bản mã là: 85E813540F0AB405.

1 Triple DES (DES3)

Thời gian của DES khá lâu, đôi khi không thích hợp với mọi loại ứng dụng.

2 Véc tơ khởi tạo (IV)

Véc tơ khởi tạo IV- Đó một khối giả để để kích

hoạt quá trình xử lý cho khối dữ liệu thật đầu tiên,

và đồng thời nó cũng cung cấp tính ngẫu nhiên cho quá trình xử lý

Các phương án sử dụng

Phương thức mã điện tử ECB

- Đây là chế độ đơn giản nhất trong các chế độ

- Bản tin được chia thành các khối và các khối được mã hoá độc lập với nhau.

- Nhược điểm: các khối plaintext giống nhau sẽ được mã hoá thành các khối ciphertext giống nhau Do vậy, nó không tốt trong việc giấu các mẫu dữ liệu và không được khuyến khích sử dụng trong các giao thức mật mã

Các phương án sử dụng (tiếp)

Phương thức mã liên kết CBC

- Mỗi khối dữ liệu plaintext trước khi được mã hoá sẽ được XOR với khối

ciphertext của khối plaintext trước đó.

- Như vậy: mỗi khối dữ liệu ciphertext sẽ phụ thuộc vào tất cả các khối plaintext đã được xử lý cho đến thời điểm đó.

- Để đảm bảo tính duy nhất của bản tin thì một véc tơ khởi tạo sẽ được sử dụng trước khối dữ liệu đầu tiên.

- Nếu khối đầu tiên có chỉ số là 1 thì công thức toán học cho việc mã hoá là:

Ci = Ek(Pi XOR Ci-1), Co = IV

C: khối dữ liệu mã hoá, P: khối dữ liệu rõ

và công thức toán học cho giải mã là:

Pi = Dk(Ci) XOR (Ci-1), Co = IV Các phương án sử dụng (tiếp)

Phương thức mã phản hồi CFB

- Mỗi khối dữ liệu plaintext sẽ được XOR với mã hoá của khối ciphertext trước đó để tạo thành khối ciphertext mới.

- Nếu khối đầu tiên có chỉ số là 1 thì công thức toán học cho việc mã hoá là:

Ci = Ek (Ci-1) XOR Pi, Co = IV

C: khối dữ liệu mã hoá, P: khối dữ liệu rõ

và công thức toán học cho giải mã là:

Pi = Ek(Ci-1) XOR Ci, Co = IV

Các phương án sử dụng (tiếp)

Phương thức phản hồi đầu ra OFB

- Nếu khối đầu tiên có chỉ số là 1 thì công thức toán học cho việc mã hoá là:

• Khoảng 1975, Diffie và Hellman đã đưa ra ý tưởng

có thể vét cạn 2^56 keys bằng "parallel computer” dùng 1 triệu con chips để thử 1 triệu keys mỗi giây,

và ước tính khoảng 20 triệu đô.

• Tháng 7- 1998, có một công bố rằng họ có thể

cracked 56 bít khóa trong vòng 56 giờ Máy tính đó

gọi là Deep Crack, dùng 27 bản mạch, mỗi bản

mạch chứa 64 chips, và khả năng testing 90 billion

keys/ giây.