Chế độ Des. Tiêu chuẩn mã hóa dữ liệu (DES)

Thuật toán DES

Ưu điểm chính của thuật toán DES:

· chỉ sử dụng một khóa có độ dài 56 bit;

· đã mã hóa tin nhắn bằng một gói, bạn có thể sử dụng bất kỳ gói nào khác để giải mã nó;

· Sự đơn giản tương đối của thuật toán đảm bảo tốc độ cao xử lý thông tin;

· Tính ổn định đủ cao của thuật toán.

DES mã hóa khối dữ liệu 64 bit bằng khóa 56 bit. Giải mã trong DES là hoạt động ngược lại của mã hóa và được thực hiện bằng cách lặp lại các hoạt động mã hóa theo thứ tự ngược lại (mặc dù rõ ràng là điều này không phải lúc nào cũng được thực hiện. Sau này chúng ta sẽ xem xét các mật mã trong đó việc mã hóa và giải mã được thực hiện bằng các thuật toán khác nhau) .

Quá trình mã hóa bao gồm hoán vị ban đầu các bit của khối 64 bit, mười sáu chu kỳ mã hóa và cuối cùng là hoán vị ngược của các bit (Hình 1).

Cần lưu ý ngay rằng TẤT CẢ các bảng được đưa ra trong bài viết này đều là TIÊU CHUẨN và do đó nên được đưa vào quá trình triển khai thuật toán của bạn mà không thay đổi. Tất cả các hoán vị và mã trong bảng đều được các nhà phát triển lựa chọn theo cách làm cho quá trình giải mã trở nên khó khăn nhất có thể bằng cách chọn một khóa. Cấu trúc của thuật toán DES được hiển thị trong Hình 2.

Hình 2. Cấu trúc của thuật toán mã hóa DES

Để khối 8 byte tiếp theo T được đọc từ tệp, được chuyển đổi bằng cách sử dụng ma trận hoán vị ban đầu IP (Bảng 1) như sau: bit 58 của khối T trở thành bit 1, bit 50 trở thành bit 2, v.v., điều này sẽ kết quả là: T(0) = IP(T).

Chuỗi bit kết quả T(0) được chia thành hai chuỗi, mỗi chuỗi 32 bit: L(0) - bit trái hoặc bit thứ tự cao, R(0) - bit phải hoặc bit thứ tự thấp.

Bảng 1: Ma trận hoán vị ban đầu IP

58 50 42 34 26 18 10 02

60 52 44 36 28 20 12 04

62 54 46 38 30 22 14 06

64 56 48 40 32 24 16 08

57 49 41 33 25 17 09 01

59 51 43 35 27 19 11 03

61 53 45 37 29 21 13 05

63 55 47 39 31 23 15 07

Sau đó, mã hóa được thực hiện, bao gồm 16 lần lặp. Kết quả tôi lặp được mô tả bằng công thức sau:

R(i) = L(i-1) xor f(R(i-1), K(i)) ,

trong đó xor là hoạt động ĐỘC QUYỀN HOẶC.

Hàm f được gọi là hàm mã hóa. Đối số của nó là chuỗi 32-bit R(i-1), thu được ở lần lặp thứ (i-1), và khóa 48-bit K(i), là kết quả của việc chuyển đổi khóa 64-bit K. Cụ thể, chức năng mã hóa và thuật toán lấy khóa K(i) được mô tả dưới đây.

Ở lần lặp thứ 16, thu được các chuỗi R(16) và L(16) (không hoán vị), được nối thành chuỗi 64-bit R(16)L(16).

Sau đó vị trí các bit của dãy này được sắp xếp lại theo ma trận IP -1 (Bảng 2).

Bảng 2: Ma trận hoán vị nghịch đảo IP -1

40 08 48 16 56 24 64 32

39 07 47 15 55 23 63 31

38 06 46 14 54 22 62 30

37 05 45 13 53 21 61 29

36 04 44 12 52 20 60 28

35 03 43 11 51 19 59 27

34 02 42 10 50 18 58 26

33 01 41 09 49 17 57 25

Ma trận IP -1 và IP có liên hệ với nhau như sau: giá trị phần tử thứ 1 của ma trận IP -1 là 40, giá trị phần tử thứ 40 của ma trận IP là 1, giá trị của phần tử thứ 2 phần tử của ma trận IP -1 là 8 và giá trị của phần tử ma trận IP thứ 8 bằng 2, v.v.

Quá trình giải mã dữ liệu ngược lại với quá trình mã hóa. Mọi hành động phải được thực hiện trong thứ tự ngược lại. Điều này có nghĩa là dữ liệu được giải mã trước tiên được sắp xếp lại theo ma trận IP-1, sau đó các hành động tương tự được thực hiện trên chuỗi bit R(16)L(16) như trong quy trình mã hóa, nhưng theo thứ tự ngược lại.

Quá trình giải mã lặp lại có thể được mô tả bằng các công thức sau:

R(i-1) = L(i), i = 1, 2, ..., 16;

L(i-1) = R(i) xor f(L(i), K(i)), i = 1, 2, ..., 16 .

Ở lần lặp thứ 16, thu được các chuỗi L(0) và R(0), được nối thành chuỗi 64-bit L(0)R(0).

Vị trí bit của chuỗi này sau đó được sắp xếp lại theo ma trận IP. Kết quả của sự hoán vị như vậy là chuỗi 64 bit ban đầu.

Bây giờ hãy xem xét hàm mã hóa f(R(i-1),K(i)). Nó được thể hiện dưới dạng sơ đồ trong Hình. 3.

Hình 3. Tính hàm số f(R(i-1), K(i))

Để tính giá trị của hàm f, các hàm ma trận sau được sử dụng:

E - phần mở rộng của chuỗi 32 bit thành 48 bit,

S1, S2, ..., S8 - chuyển đổi khối 6 bit thành khối 4 bit,

P - hoán vị các bit trong chuỗi 32 bit.

Hàm mở rộng E được xác định trong Bảng 3. Theo bảng này, 3 bit đầu tiên của E(R(i-1)) là các bit 32, 1 và 2, và các bit cuối cùng là 31, 32 và 1.

Bảng 3: Hàm mở rộng E

32 01 02 03 04 05

04 05 06 07 08 09

08 09 10 11 12 13

12 13 14 15 16 17

16 17 18 19 20 21

20 21 22 23 24 25

24 25 26 27 28 29

28 29 30 31 32 01

Kết quả của hàm E(R(i-1)) là một chuỗi 48 bit được thêm modulo 2 (thao tác xor) với khóa 48 bit K(i). Chuỗi 48 bit thu được được chia thành 8 khối 6 bit B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8). Đó là:

E(R(i-1)) xor K(i) = B(1)B(2)...B(8) .

Các hàm S1, S2, ..., S8 được xác định trong Bảng 4.

Bảng 4

Vào bảng 4. cần phải làm rõ thêm. Giả sử đầu vào của hàm ma trận Sj là khối 6 bit B(j) = b1b2b3b4b5b6, khi đó số hai bit b1b6 chỉ số hàng của ma trận và b2b3b4b5 chỉ số cột. Kết quả của Sj(B(j)) sẽ là phần tử 4 bit nằm ở giao điểm của hàng và cột được chỉ định.

Ví dụ: B(1)=011011. Khi đó S1(B(1)) nằm ở giao điểm của hàng 1 và cột 13. Trong cột 13 của hàng 1 giá trị là 5. Điều này có nghĩa là S1(011011)=0101.

Áp dụng thao tác lựa chọn cho từng khối 6 bit B(1), B(2), ..., B(8), chúng ta thu được chuỗi 32 bit S1(B(1))S2(B(2) ))S3(B(3))...S8(B(8)).

Cuối cùng, để có được kết quả của hàm mã hóa, các bit của chuỗi này phải được sắp xếp lại. Với mục đích này, hàm hoán vị P được sử dụng (Bảng 5). Trong chuỗi đầu vào, các bit được sắp xếp lại sao cho bit 16 trở thành bit 1, bit 7 trở thành bit 2, v.v.

Bảng 5: Hàm hoán vị P

Như vậy,

f(R(i-1), K(i)) = P(S1(B(1)),...S8(B(8)))

Để hoàn thành phần mô tả thuật toán mã hóa dữ liệu, vẫn còn phải trình bày thuật toán lấy khóa 48 bit K(i), i=1...16. Tại mỗi lần lặp, một giá trị khóa mới K(i) được sử dụng, được tính từ khóa ban đầu K. K là khối 64 bit có 8 bit chẵn lẻ nằm ở các vị trí 8,16,24,32,40,48,56,64.

Để loại bỏ các bit điều khiển và sắp xếp lại các bit còn lại, chức năng G của việc chuẩn bị khóa ban đầu được sử dụng (Bảng 6).

Bảng 6

Ma trận G chuẩn bị khóa ban đầu

57 49 41 33 25 17 09

01 58 50 42 34 26 18

10 02 59 51 43 35 27

19 11 03 60 52 44 36

63 55 47 39 31 23 15

07 62 54 46 38 30 22

14 06 61 53 45 37 29

21 13 05 28 20 12 04

Kết quả của phép biến đổi G(K) được chia thành hai khối 28 bit C(0) và D(0), và C(0) sẽ gồm các bit 57, 49, ..., 44, 36 của khóa K, và D(0 ) sẽ gồm các bit 63, 55, ..., 12, 4 của khóa K. Sau khi xác định C(0) và D(0), C(i) và D(i), i= 1...16, được xác định đệ quy. Để thực hiện điều này, áp dụng dịch chuyển tuần hoàn sang trái một hoặc hai bit, tùy thuộc vào số lần lặp, như trong Bảng 7.

Bảng 7

Bảng dịch chuyển để tính toán khóa

Số lần lặp	Dịch chuyển (bit)
01	1
02	1
03	2
04	2
05	2
06	2
07	2
08	2
09	1
10	2
11	2
12	2
13	2
14	2
15	2
16	1

Giá trị thu được lại được “trộn” theo ma trận H (Bảng 8).

Bảng 8: Ma trận hoàn thành khóa H

14 17 11 24 01 05

03 28 15 06 21 10

23 19 12 04 26 08

16 07 27 20 13 02

41 52 31 37 47 55

30 40 51 45 33 48

44 49 39 56 34 53

46 42 50 36 29 32

Khóa K(i) sẽ bao gồm các bit 14, 17, ..., 29, 32 của chuỗi C(i)D(i). Như vậy:

K(i) = H(C(i)D(i))

Sơ đồ khối của thuật toán tính toán khóa được hiển thị trong Hình 4.

Hình 4. Sơ đồ khối thuật toán tính khóa K(i)

Sự hồi phục văn bản nguồnđược thực hiện theo thuật toán này, nhưng trước tiên bạn sử dụng khóa

K(15), rồi K(14), v.v. Bây giờ bạn đã hiểu tại sao tác giả nhất quyết khuyên bạn nên sử dụng các ma trận đã cho. Nếu bạn lừa đảo, bạn có thể nhận được một mã rất bí mật, nhưng bạn sẽ không thể tự mình giải mã được!

Các chế độ hoạt động của thuật toán DES

Để đáp ứng đầy đủ nhất tất cả các yêu cầu đối với hệ thống mã hóa thương mại, một số chế độ hoạt động của thuật toán DES được triển khai. Các chế độ được sử dụng rộng rãi nhất là:

· Sách mã điện tử (Electronic Codebook) - ECB;

· Chuỗi khối kỹ thuật số (Cipher Block Chaining) - CBC;

· Phản hồi số (Cipher Phản hồi) - CFB;

· Phản hồi bên ngoài (Output Phản hồi) - OFB.

Ở chế độ này tập tin gốc M được chia thành các khối 64-bit (mỗi khối 8 byte): M = M(1)M(2)...M(n). Mỗi khối này được mã hóa độc lập bằng cách sử dụng cùng một khóa mã hóa (Hình 5). Ưu điểm chính của thuật toán này là dễ thực hiện. Điểm bất lợi là nó tương đối yếu trước các nhà giải mã lành nghề.

Tiêu chuẩn DES được thiết kế để bảo vệ chống truy cập trái phép vào thông tin nhạy cảm nhưng chưa được phân loại trong các tổ chức thương mại và chính phủ Hoa Kỳ. Thuật toán làm cơ sở cho tiêu chuẩn này lan truyền khá nhanh và đã được phê duyệt vào năm 1980. Viện quốc gia Tiêu chuẩn và công nghệ Hoa Kỳ. Kể từ thời điểm này, DES trở thành một tiêu chuẩn không chỉ trên danh nghĩa mà còn trên thực tế. Xuất hiện phần mềm và các máy vi tính chuyên dụng được thiết kế để mã hóa và giải mã thông tin trong mạng dữ liệu.

Đến nay, DES là thuật toán phổ biến nhất được sử dụng trong các hệ thống bảo mật thông tin thương mại. Hơn nữa, việc triển khai thuật toán DES trong các hệ thống như vậy trở thành một dấu hiệu tốt.

Ưu điểm chính của thuật toán DES:

· chỉ sử dụng một khóa có độ dài 56 bit;

· đã mã hóa tin nhắn bằng một gói, bạn có thể sử dụng bất kỳ gói nào khác để giải mã nó;

· Tính đơn giản tương đối của thuật toán đảm bảo tốc độ xử lý thông tin cao;

· Tính ổn định đủ cao của thuật toán.

Quá trình mã hóa bao gồm hoán vị bit ban đầu của khối 64 bit, mười sáu chu kỳ mã hóa và cuối cùng là hoán vị bit ngược (Hình 1).

Cơm. 2.

Để khối 8 byte tiếp theo T được đọc từ tệp, khối này được chuyển đổi bằng cách sử dụng ma trận hoán vị ban đầu IP (Bảng 1) như sau: bit 58 của khối T trở thành bit 1, bit 50 trở thành bit 2, v.v., điều này sẽ kết quả là: T(0) = IP(T).

Chuỗi bit kết quả T(0) được chia thành hai chuỗi, mỗi chuỗi 32 bit: L(0) - bit trái hoặc bit thứ tự cao, R(0) - bit phải hoặc bit thứ tự thấp.

Bảng 1: Ma trận hoán vị ban đầu IP

58 50 42 34 26 18 10 02

60 52 44 36 28 20 12 04

62 54 46 38 30 22 14 06

64 56 48 40 32 24 16 08

57 49 41 33 25 17 09 01

59 51 43 35 27 19 11 03

61 53 45 37 29 21 13 05

63 55 47 39 31 23 15 07

Sau đó, mã hóa được thực hiện, bao gồm 16 lần lặp. Kết quả của lần lặp thứ i được mô tả bằng công thức sau:

R(i) = L(i-1) xor f(R(i-1), K(i)),

trong đó xor là hoạt động ĐỘC QUYỀN HOẶC.

Hàm f được gọi là hàm mã hóa. Các đối số của nó là chuỗi 32-bit R(i-1), thu được ở lần lặp thứ (i-1), và khóa 48-bit K(i), là kết quả của việc chuyển đổi khóa 64-bit K. Cụ thể, chức năng mã hóa và thuật toán lấy khóa K(i) được mô tả dưới đây.

Ở lần lặp thứ 16, thu được các chuỗi R(16) và L(16) (không hoán vị), được nối thành chuỗi 64-bit R(16) L(16).

Sau đó các vị trí bit của chuỗi này được sắp xếp lại theo ma trận IP -1 (Bảng 2).

Bảng 2: Ma trận hoán vị nghịch đảo IP -1

40 08 48 16 56 24 64 32

39 07 47 15 55 23 63 31

38 06 46 14 54 22 62 30

37 05 45 13 53 21 61 29

36 04 44 12 52 20 60 28

35 03 43 11 51 19 59 27

34 02 42 10 50 18 58 26

33 01 41 09 49 17 57 25

Quá trình giải mã dữ liệu ngược lại với quá trình mã hóa. Tất cả các bước phải được thực hiện theo thứ tự ngược lại. Điều này có nghĩa là dữ liệu cần giải mã trước tiên được sắp xếp lại theo ma trận IP-1, sau đó các hành động tương tự được thực hiện trên chuỗi bit R(16) L(16) như trong quy trình mã hóa, nhưng theo thứ tự ngược lại.

Quá trình giải mã lặp lại có thể được mô tả bằng các công thức sau:

R(i-1) = L(i), i = 1, 2,…, 16;

L(i-1) = R(i) xor f(L(i), K(i)), i = 1, 2,…, 16.

Ở lần lặp thứ 16, thu được các chuỗi L(0) và R(0), được nối thành chuỗi 64 bit L(0) R(0).

Vị trí bit của chuỗi này sau đó được sắp xếp lại theo ma trận IP. Kết quả của sự hoán vị như vậy là chuỗi 64 bit ban đầu.

Bây giờ hãy xem xét hàm mã hóa f (R(i-1), K(i)). Nó được thể hiện dưới dạng sơ đồ trong Hình. 3.

Cơm. 3.

Để tính giá trị của hàm f, các hàm ma trận sau được sử dụng:

E - phần mở rộng của chuỗi 32 bit thành 48 bit,

S1, S2,…, S8 - chuyển đổi khối 6 bit thành khối 4 bit,

P - hoán vị các bit trong chuỗi 32 bit.

Hàm mở rộng E được xác định theo bảng. 3. Theo bảng này, 3 bit đầu tiên của E (R(i-1)) là các bit 32, 1 và 2, còn lại là 31, 32 và 1.

Bảng 3: Hàm mở rộng E

32 01 02 03 04 05

04 05 06 07 08 09

08 09 10 11 12 13

12 13 14 15 16 17

16 17 18 19 20 21

20 21 22 23 24 25

24 25 26 27 28 29

28 29 30 31 32 01

Kết quả của hàm E (R(i-1)) là một chuỗi 48 bit được thêm modulo 2 (thao tác xor) với khóa 48 bit K(i). Chuỗi 48 bit thu được được chia thành 8 khối 6 bit B(1) B(2) B(3) B(4) B(5) B(6) B(7) B(8). Đó là:

E (R(i-1)) xor K(i) = B(1) B(2)… B(8).

Các hàm S1, S2,…, S8 được định nghĩa trong bảng. 4.

Bảng 4

Đến bàn 4. Cần phải làm rõ thêm. Giả sử đầu vào của hàm ma trận Sj là khối 6 bit B(j) = b1b2b3b4b5b6, khi đó số hai bit b1b6 chỉ số hàng của ma trận và b2b3b4b5 chỉ số cột. Kết quả của Sj (B(j)) sẽ là phần tử 4 bit nằm ở giao điểm của hàng và cột được chỉ định.

Ví dụ: B(1)=011011. Khi đó S1 (B(1)) nằm ở giao điểm của hàng 1 và cột 13. Trong cột 13 của hàng 1 giá trị là 5. Điều này có nghĩa là S1 (011011)=0101.

Áp dụng thao tác lựa chọn cho từng khối 6 bit B(1), B(2),…, B(8), chúng ta thu được chuỗi 32 bit S1 (B(1)) S2 (B(2)) S3 (B(3))... S8 (B(8)).

Bảng 5: Hàm hoán vị P

Như vậy,

f (R(i-1), K(i)) = P (S1(B(1)),… S8 (B(8)))

Để hoàn thành phần mô tả thuật toán mã hóa dữ liệu, vẫn còn phải trình bày thuật toán lấy khóa 48 bit K(i), i=1...16. Ở mỗi lần lặp, một giá trị khóa mới K(i) được sử dụng, được tính từ khóa ban đầu K. K là một khối 64 bit với 8 bit chẵn lẻ nằm ở các vị trí 8,16,24,32,40,48, 56. 64.

Để loại bỏ các bit điều khiển và sắp xếp lại phần còn lại, chức năng G của việc chuẩn bị khóa ban đầu được sử dụng (Bảng 6).

Bảng 6

Ma trận G chuẩn bị khóa ban đầu

57 49 41 33 25 17 09

01 58 50 42 34 26 18

10 02 59 51 43 35 27

19 11 03 60 52 44 36

63 55 47 39 31 23 15

07 62 54 46 38 30 22

14 06 61 53 45 37 29

21 13 05 28 20 12 04

Kết quả của phép biến đổi G(K) được chia thành hai khối 28 bit C(0) và D(0), và C(0) sẽ gồm các bit 57, 49, ..., 44, 36 của khóa K, và D(0) sẽ gồm các bit 63, 55,…, 12, 4 khóa K. Sau khi xác định C(0) và D(0), C(i) và D(i), i=1… 16, được xác định đệ quy. Để thực hiện việc này, áp dụng dịch chuyển tuần hoàn sang trái một hoặc hai bit, tùy thuộc vào số lần lặp, như được hiển thị trong bảng. 7.

Bảng 7. Bảng dịch chuyển tính toán khóa

Số lần lặp	Dịch chuyển (bit)

Giá trị thu được lại được “trộn” theo ma trận H (Bảng 8).

Bảng 8: Ma trận hoàn thành khóa H

14 17 11 24 01 05

03 28 15 06 21 10

23 19 12 04 26 08

16 07 27 20 13 02

41 52 31 37 47 55

30 40 51 45 33 48

44 49 39 56 34 53

46 42 50 36 29 32

Khóa K(i) sẽ bao gồm các bit 14, 17,…, 29, 32 của chuỗi C(i) D(i). Như vậy:

K(i) = H(C(i) D(i))

Sơ đồ khối của thuật toán tính toán khóa được hiển thị trong Hình 2. 4.

Cơm. 4.

Việc khôi phục văn bản gốc được thực hiện bằng thuật toán này, nhưng trước tiên bạn sử dụng phím K(15), sau đó là K(14), v.v. Bây giờ bạn đã hiểu tại sao tác giả nhất quyết khuyên bạn nên sử dụng các ma trận đã cho. Nếu bạn lừa đảo, bạn có thể nhận được một mã rất bí mật, nhưng bạn sẽ không thể tự mình giải mã được!

Đã hơn 30 năm trôi qua kể từ khi thuật toán DES được áp dụng làm tiêu chuẩn mã hóa của Hoa Kỳ. DES là một thuật toán mã hóa có lịch sử phong phú và thú vị nhất.

Lịch sử hình thành thuật toán

Một trong những nhà mật mã học nổi tiếng nhất thế giới, Bruce Schneier, trong cuốn sách nổi tiếng “Mật mã ứng dụng” đã mô tả các vấn đề của người dùng các công cụ bảo mật thông tin vào đầu những năm 70. Thế kỷ XX (dĩ nhiên Chúng ta đang nói về về người dùng ở phía bên kia Bức màn sắt):

Không có một tiêu chuẩn được chấp nhận chung nào cho việc mã hóa dữ liệu cũng như không có các thuật toán bảo mật thông tin được sử dụng rộng rãi, do đó khả năng tương thích giữa các công cụ mã hóa phần mềm hoặc phần cứng khác nhau là không thể;

Hầu hết mọi công cụ mã hóa đều là một “hộp đen” với nội dung khá không rõ ràng: thuật toán mã hóa nào được sử dụng, độ mạnh của mật mã như thế nào, liệu nó có được triển khai chính xác hay không, liệu các khóa mã hóa có được tạo, lưu trữ, sử dụng chính xác hay không, liệu có bất kỳ khóa nào được chèn bởi các nhà phát triển trong công cụ tính năng không có giấy tờ v.v. - tất cả điều này là rất Thông tin quan trọng cho đại đa số người mua phương tiện mật mãđã không có sẵn.

Cục Tiêu chuẩn Quốc gia (NBS) của Hoa Kỳ quan tâm đến vấn đề này. Kết quả là vào năm 1973, cuộc thi mở đầu tiên dành cho tiêu chuẩn mã hóa đã được công bố. NBS sẵn sàng kiểm tra các thuật toán ứng viên đáp ứng các tiêu chí sau để chọn ra tiêu chuẩn:

Thuật toán phải mạnh về mặt mật mã;

Thuật toán phải nhanh;

Cấu trúc của thuật toán phải rõ ràng và chính xác;

Độ mạnh của mã hóa chỉ phụ thuộc vào khóa, bản thân thuật toán không được bí mật;

Thuật toán phải dễ dàng áp dụng cho nhiều mục đích khác nhau;

Thuật toán phải được thực hiện dễ dàng trong phần cứng bằng cách sử dụng các thành phần phần cứng hiện có.

Giả định rằng các tổ chức hoặc chuyên gia quan tâm sẽ gửi tới NBS thông số kỹ thuật chi tiết về các thuật toán đủ để triển khai, tức là không có bất kỳ “điểm mù” nào. Người ta cũng giả định rằng thuật toán sẽ được NBS chứng nhận để sử dụng chung và tất cả các hạn chế về bằng sáng chế và xuất khẩu sẽ bị loại bỏ khỏi thuật toán đó, do đó, tiêu chuẩn như vậy sẽ phải giải quyết tất cả các vấn đề về khả năng tương thích mã hóa. Ngoài ra, NBS còn đảm nhận chức năng chứng nhận các công cụ mã hóa - tức là “hộp đen” lẽ ra đã trở thành dĩ vãng.

Trên thực tế, chỉ có một thuật toán ứng cử viên duy nhất: đó là thuật toán mã hóa Lucifer do ShM phát triển. (xem phần 3.31). Trong suốt hai năm, thuật toán đã được cải tiến:

Đầu tiên, NBS cùng với Cơ quan An ninh Quốc gia (NSA, Cơ quan An ninh Quốc gia) của Hoa Kỳ đã tiến hành phân tích kỹ lưỡng thuật toán, dẫn đến sự sửa đổi khá đáng kể;

Thứ hai, những ý kiến, phê bình của tất cả các tổ chức, cá nhân quan tâm đều được xem xét.

Kết quả là Các hoạt động chung IBM, NBS và NSA vào tháng 1 năm 1977 DES đã được xuất bản dưới dạng tiêu chuẩn Hoa Kỳ ( phiên bản mới nhất của tiêu chuẩn này - trong tài liệu) về thuật toán mã hóa dữ liệu (ngoại trừ thông tin có mức độ bí mật cao). Thuật toán DES đã được YuM cấp bằng sáng chế, nhưng trên thực tế, NBS đã nhận được giấy phép sử dụng miễn phí và không giới hạn của thuật toán này. Một tên thay thế nhưng ít được sử dụng hơn cho thuật toán là DEA (Thuật toán mã hóa dữ liệu).

Đặc điểm và cấu trúc chính của thuật toán

Thuật toán DES mã hóa thông tin trong các khối 64 bit bằng khóa mã hóa 64 bit chỉ sử dụng 56 bit (quy trình mở rộng khóa được mô tả chi tiết bên dưới).

Việc mã hóa thông tin được thực hiện như sau (Hình 3.56):

1. Hoán vị ban đầu được thực hiện trên khối dữ liệu 64 bit theo bảng. 3.16.

Bảng 3.16

Bảng được hiểu như sau: giá trị của bit đầu vào 58 (sau đây gọi là tất cả các bit được đánh số từ trái sang phải, bắt đầu từ 1) được đặt trong bit đầu ra 1, giá trị của bit 50 được đặt trong bit 2, v.v.

2. Kết quả của thao tác trước được chia thành 2 khối con 32 bit (mỗi khối

cơm. 3,56 được đánh dấu A 0 và B 0), trong đó 16 vòng được thực hiện

các phép biến đổi sau:

Như đã đề cập ở trên, từ khóa mã hóa 64 bit thuật toán DES chỉ sử dụng 56 bit. Mỗi bit thứ 8 sẽ bị loại bỏ và không được sử dụng theo bất kỳ cách nào trong thuật toán và việc sử dụng các bit còn lại của khóa mã hóa trong việc triển khai thuật toán DES không bị giới hạn bởi tiêu chuẩn. Quy trình trích xuất 56 bit quan trọng của khóa 64 bit trong Hình. 3.59 được ký hiệu là E. Ngoài việc chiết xuất, thủ tục này cũng thực hiện hoán vị các bit khóa theo bảng. 3,19 và 3,20.

Bảng 3.19

Bảng 3.20

Kết quả của hoán vị là hình thành hai giá trị 28 bit C và D. Bảng 3.19 xác định việc lựa chọn các bit khóa cho C, bảng. 3,20 - cho D.

Sau đó, 16 vòng biến đổi được thực hiện, mỗi vòng mang lại một trong các phím tròn K t. Trong mỗi vòng của quy trình mở rộng khóa, các hành động sau được thực hiện:

1. Giá trị hiện tại của C và D dịch chuyển theo chu kỳ sang trái một số bit thay đổi P.Đối với các vòng 1, 2, 9 và 16 P= 1, trong các vòng còn lại, phép dịch theo chu kỳ 2 bit được thực hiện.

2. C và Dđược kết hợp thành giá trị 56 bit, áp dụng hoán vị nén CP, kết quả là khóa tròn 48 bit K (. Hoán vị nén được thực hiện theo Bảng 3.21.

Bảng 3.21

Khi giải mã dữ liệu, bạn có thể sử dụng quy trình mở rộng khóa tương tự nhưng áp dụng các phím tròn theo thứ tự ngược lại. Có một lựa chọn khác: trong mỗi vòng của thủ tục mở rộng khóa, thay vì dịch chuyển tuần hoàn sang trái, thực hiện dịch chuyển tuần hoàn sang phải n bit, trong đó rc' = 0 cho vòng đầu tiên, u' = 1 cho vòng 2, 9, 16 và n = 2 cho các vòng còn lại. Thủ tục mở rộng khóa này sẽ ngay lập tức cung cấp các khóa tròn cần thiết để giải mã.

Điều đáng nói là khả năng thực hiện mở rộng khóa “nhanh chóng” (đặc biệt nếu khả năng này tồn tại cả trong quá trình mã hóa và giải mã) được coi là một lợi thế của thuật toán mã hóa, vì trong trường hợp này, việc mở rộng khóa có thể được thực hiện song song với mã hóa. và không lãng phí bộ nhớ vào việc lưu trữ khóa của các vòng khác ngoài vòng hiện tại.

Thuật toán DES khá phù hợp cho cả việc mã hóa và xác thực dữ liệu. Nó cho phép đầu vào văn bản gốc 64 bit được chuyển đổi trực tiếp thành đầu ra văn bản mã hóa 64 bit, nhưng dữ liệu hiếm khi bị giới hạn ở 64 bit.

Để sử dụng thuật toán DES giải quyết nhiều vấn đề về mật mã, bốn chế độ hoạt động đã được phát triển:

· Sách mã điện tử ECB (Sách mã điện tử);

· nối các khối mật mã CBC (Chuỗi khối mật mã);

· Phản hồi văn bản mã hóa CFB (Cipher Feed Back);

· Phản hồi về đầu ra OFB (Output Feed Back).

Chế độ “Sổ mã điện tử”

Tệp dàiđược chia thành các đoạn (khối) 64 bit 8 byte. Mỗi khối này được mã hóa độc lập bằng cách sử dụng cùng một khóa mã hóa (Hình 3.6).

Ưu điểm chính là dễ thực hiện. Nhược điểm: Khả năng chống chịu tương đối yếu trước các nhà giải mã lành nghề. Do tính chất cố định của mã hóa, với độ dài khối giới hạn là 64 bit, việc phân tích mật mã "từ điển" là có thể. Một khối có kích thước này có thể được lặp lại trong một tin nhắn do tính dư thừa cao trong văn bản ngôn ngữ tự nhiên.

Hình 3.6 – Sơ đồ thuật toán DES ở chế độ sổ mã điện tử

Điều này làm cho các khối văn bản gốc giống hệt nhau trong một tin nhắn được biểu diễn bằng các khối văn bản mã hóa giống hệt nhau, cung cấp cho người giải mã một số thông tin về nội dung của tin nhắn.

Chế độ "Xâu chuỗi khối mật mã"

Ở chế độ này, tệp nguồn M được chia thành các khối 64 bit: M = M 1 M 2 ...M n. Khối đầu tiên M 1 được thêm modulo 2 với vectơ IV ban đầu 64 bit, thay đổi hàng ngày và được giữ bí mật (Hình 3.7). Số tiền nhận được sau đó được mã hóa bằng khóa DES mà cả người gửi và người nhận thông tin đều biết. Mật mã 64 bit thu được C 1 được thêm modulo 2 với khối văn bản thứ hai, kết quả được mã hóa và thu được mật mã 64 bit thứ hai C 2, v.v. Quy trình được lặp lại cho đến khi tất cả các khối văn bản được xử lý.

Như vậy, với mọi i = 1…n (n là số khối), kết quả mã hóa C i được xác định như sau: C i =

DES (M i  C i –1), trong đó C 0 = IV – giá trị ban đầu mật mã, bằng vectơ ban đầu (vectơ khởi tạo).

Rõ ràng, khối bản mã 64-bit cuối cùng là một hàm của khóa bí mật, vectơ hạt giống và mỗi bit

Hình 3.7 – Sơ đồ thuật toán DES trong chế độ chuỗi khối mật mã

bản rõ bất kể độ dài của nó. Khối bản mã này được gọi là mã xác thực tin nhắn (MAC).

Mã CAS có thể được xác minh dễ dàng bởi người nhận, người có khóa bí mật và vectơ hạt giống, bằng cách lặp lại quy trình do người gửi thực hiện. Tuy nhiên, người ngoài không thể tạo UAS được người nhận coi là chính hãng để thêm vào tin nhắn sai hoặc tách UAS khỏi tin nhắn thật để sử dụng với tin nhắn đã sửa đổi hoặc sai.

Phẩm giá chế độ này là nó không cho phép tích lũy lỗi trong quá trình truyền.

Khối M i chỉ là hàm của C i –1 và C i . Vì vậy, một lỗi truyền tải sẽ dẫn đến việc chỉ mất đi hai khối văn bản nguồn.

Chế độ "Phản hồi của Cypher"

Ở chế độ này, kích thước khối có thể khác với 64 bit (Hình 3.8). Tệp cần mã hóa (giải mã) được đọc theo từng khối có độ dài k bit liên tiếp (k=1...64).

Khối đầu vào (thanh ghi dịch chuyển 64 bit) trước tiên chứa vectơ khởi tạo căn phải.

Giả sử rằng nhờ chia thành các khối, chúng ta nhận được n khối có độ dài k bit mỗi khối (phần còn lại được thêm vào bằng số 0 hoặc dấu cách). Sau đó, với bất kỳ khối bản mã i=1…n nào

С i = M i  P i –1 ,

trong đó P i–1 biểu thị k bit quan trọng nhất của khối được mã hóa trước đó.

Thanh ghi dịch được cập nhật bằng cách loại bỏ k bit cao nhất của nó và ghi C i vào thanh ghi. Việc khôi phục dữ liệu bị mã hóa cũng tương đối đơn giản: P i –1 và C i được tính theo cách tương tự và

М tôi = С tôi  Р tôi –1 .

Hình 3.8 – Sơ đồ thuật toán DES trong nhận xét bằng bản mã

Chế độ phản hồi đầu ra

Chế độ này cũng sử dụng kích thước khối thay đổi và đăng kí ca, được khởi tạo theo cách tương tự như trong chế độ CFB, cụ thể là khối đầu vào trước tiên chứa vectơ khởi tạo IV, được căn chỉnh sang phải (Hình 3.9). Trong trường hợp này, đối với mỗi phiên mã hóa dữ liệu, cần phải sử dụng trạng thái ban đầu mới của thanh ghi, trạng thái này phải được gửi qua kênh ở dạng văn bản rõ ràng.

M = M 1 M 2 ... M n.

Với mọi i = 1…n

C i = M i  P i ,

trong đó Р i là k bit cao nhất của phép toán DES (С i –1).

Sự khác biệt so với chế độ phản hồi bản mã là phương pháp cập nhật thanh ghi dịch.

Điều này được thực hiện bằng cách loại bỏ k bit cao nhất và thêm P i vào bên phải.

Hình 3.9 – Sơ đồ thuật toán DES ở chế độ phản hồi đầu ra

3.3. Các lĩnh vực ứng dụng của thuật toán DES

Mỗi chế độ được xem xét (ECB, CBC, CFB, OFB) đều có những ưu điểm và nhược điểm riêng, quyết định lĩnh vực ứng dụng của chúng.

Chế độ ECB rất phù hợp để mã hóa khóa: chế độ CFB, theo quy định, được dùng để mã hóa các ký tự riêng lẻ và chế độ OFB thường được sử dụng để mã hóa trong hệ thống vệ tinh thông tin liên lạc.

Chế độ CBC và CFB phù hợp để xác thực dữ liệu. Các chế độ này cho phép bạn sử dụng thuật toán DES để:

· mã hóa tương tác khi trao đổi dữ liệu giữa thiết bị đầu cuối và máy tính chủ;

· mã hóa khóa mật mã trong thực hành phân phối khóa tự động;

· mã hóa tập tin, bưu phẩm, dữ liệu vệ tinh và các vấn đề thực tế khác.

Ban đầu, tiêu chuẩn DES được dùng để mã hóa và giải mã dữ liệu máy tính. Tuy nhiên, ứng dụng của nó đã được khái quát hóa để xác thực.

Trong các hệ thống xử lý tự động dữ liệu, một người không thể xem lại dữ liệu để xác định liệu có bất kỳ thay đổi nào đã được thực hiện đối với dữ liệu đó hay không. Với lượng dữ liệu khổng lồ đi qua hệ thống hiện đại quá trình xử lý, xem sẽ mất quá nhiều thời gian. Ngoài ra, sự dư thừa dữ liệu có thể không đủ để phát hiện lỗi. Ngay cả trong trường hợp có thể thực hiện đánh giá của con người, dữ liệu có thể bị thay đổi theo cách khiến con người rất khó phát hiện ra những thay đổi đó. Ví dụ: “làm” có thể được thay thế bằng “không”, “$1900” bằng “$9100”. Không có thông tin thêm một người xem nó có thể dễ dàng nhầm dữ liệu đã thay đổi với dữ liệu chính hãng. Những mối nguy hiểm như vậy có thể tồn tại ngay cả khi sử dụng mã hóa dữ liệu. Vì vậy nên có công cụ tự động phát hiện những thay đổi dữ liệu có chủ ý và vô ý.

Các mã thông thường phát hiện lỗi là không phù hợp, vì nếu biết thuật toán tạo mã, kẻ thù có thể phát triển mã đúng sau khi thực hiện thay đổi dữ liệu. Tuy nhiên, bằng cách sử dụng thuật toán DES có thể tạo ra một mật mã tổng kiểm tra, có thể bảo vệ khỏi những thay đổi vô tình và cố ý nhưng trái phép đối với dữ liệu.

Quá trình này mô tả tiêu chuẩn xác thực dữ liệu máy tính (FIPS 113). Bản chất của tiêu chuẩn là dữ liệu được mã hóa ở chế độ phản hồi bản mã (chế độ CFB) hoặc ở chế độ nối khối mật mã (chế độ CBC), dẫn đến khối mật mã cuối cùng là chức năng của tất cả các bit văn bản gốc. Sau đó, thông báo chứa văn bản gốc có thể được truyền đi bằng cách sử dụng khối mật mã cuối cùng được tính toán, đóng vai trò là tổng kiểm tra mật mã.

Dữ liệu giống nhau có thể được bảo vệ bằng cả mã hóa và xác thực. Dữ liệu được bảo vệ khỏi sự truy cập bằng mã hóa và các thay đổi được phát hiện thông qua xác thực. Thuật toán xác thực có thể được áp dụng cho cả bản rõ và bản mã. Trong các giao dịch tài chính, trong hầu hết các trường hợp, cả mã hóa và xác thực đều được triển khai, điều sau cũng áp dụng cho giao dịch mở.

văn bản mu.

Mã hóa và xác thực được sử dụng để bảo vệ dữ liệu được lưu trữ trong máy tính. Trong nhiều máy tính, mật khẩu được mã hóa không thể đảo ngược và được lưu trong bộ nhớ của máy. Khi người dùng truy cập vào máy tính và nhập mật khẩu, mật khẩu sau sẽ được mã hóa và so sánh với giá trị được lưu trữ. Nếu cả hai giá trị được mã hóa giống nhau, người dùng sẽ có quyền truy cập vào máy, nếu không thì bị từ chối.

Thông thường, mật khẩu được mã hóa được tạo bằng thuật toán DES, với khóa bằng mật khẩu và bản rõ bằng mã nhận dạng người dùng.

Sử dụng thuật toán DES, bạn cũng có thể mã hóa các tệp máy tính để lưu trữ.

Một trong ứng dụng quan trọng nhất thuật toán DES là bảo vệ tin nhắn hệ thống điện tử thanh toán (ESP) cho các giao dịch với nhiều khách hàng và giữa các ngân hàng.

Thuật toán DES được triển khai trong các máy ATM, thiết bị đầu cuối ở các cửa hàng bán lẻ, máy trạm tự động và máy tính lớn. Phạm vi dữ liệu mà nó bảo vệ rất rộng - từ khoản thanh toán 50 đô la đến chuyển khoản hàng triệu đô la. Tính linh hoạt của thuật toán DES cốt lõi cho phép nó được sử dụng trong nhiều ứng dụng hệ thống thanh toán điện tử.

Hướng dẫn

Xin chào %tên người dùng%!
Nhiều người biết rằng tiêu chuẩn mặc định trong lĩnh vực này mã hóa đối xứng trong một khoảng thời gian dài Thuật toán DES đã được xem xét. Cuộc tấn công thành công đầu tiên vào thuật toán không thể thành công này được xuất bản vào năm 1993, 16 năm sau khi nó được áp dụng làm tiêu chuẩn. Phương pháp mà tác giả gọi là phân tích mật mã tuyến tính, với sự có mặt của 247 cặp bản rõ/bản mã, có thể bẻ khóa được Chìa khóa bí mật Mật mã DES trong 2 43 phép toán.
Bên dưới phần cắt, tôi sẽ cố gắng phác thảo ngắn gọn những điểm chính của cuộc tấn công này.

Giải mã tuyến tính

Phân tích mật mã tuyến tính là một kiểu tấn công đặc biệt vào mật mã đối xứng, nhằm mục đích khôi phục khóa mã hóa không xác định từ khóa đã biết mở tin nhắn và các bản mã tương ứng của chúng.

TRONG trường hợp chung Một cuộc tấn công dựa trên phân tích mật mã tuyến tính sẽ đạt được các điều kiện sau. Kẻ tấn công có một lượng lớn các cặp bản rõ/bản mã thu được bằng cách sử dụng cùng một khóa mã hóa K. Mục tiêu của kẻ tấn công là khôi phục một phần hoặc toàn bộ khóa K.

Trước hết, kẻ tấn công kiểm tra mật mã và tìm ra cái gọi là tương tự thống kê, tức là phương trình loại sau, thực thi với xác suất P ≠ 1/2 đối với cặp văn bản công khai/riêng tư tùy ý và khóa cố định:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib = K I1 ⊕ K I2 ⊕… ⊕ K Ic (1) ,
trong đó Pn, Cn, Kn là các bit thứ n của văn bản, bản mã và khóa.
Khi tìm thấy phương trình như vậy, kẻ tấn công có thể khôi phục 1 bit thông tin chính bằng thuật toán sau

Thuật toán 1
Gọi T là số văn bản chứa bên trái phương trình (1) bằng 0 thì
Nếu T>N/2 thì N là số bản rõ đã biết.
Giả sử K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (khi P>1/2) hoặc 1 (khi P<1/2).
Nếu không thì
Giả sử K I1 ⊕ K I2 ⊕… ⊕ K Ic = 1 (khi P>1/2) hoặc 0 (khi P<1/2).
Rõ ràng là sự thành công của thuật toán phụ thuộc trực tiếp vào giá trị của |P-1/2| và về số lượng cặp văn bản mở/đóng có sẵn N. Xác suất P của đẳng thức (1) khác 1/2 càng nhiều thì số lượng văn bản mở N cần thiết cho cuộc tấn công càng ít.

Có hai vấn đề cần giải quyết để cuộc tấn công thành công:

Làm thế nào để tìm một phương trình hiệu quả của dạng (1).
Cách sử dụng phương trình này để có được nhiều hơn một bit thông tin về khóa.

Hãy xem xét giải pháp cho những vấn đề này bằng cách sử dụng mật mã DES làm ví dụ.

Mô tả của DES

Nhưng trước tiên, hãy mô tả ngắn gọn cách hoạt động của thuật toán. Đã nói đủ về DES rồi. Bạn có thể tìm thấy mô tả đầy đủ về mật mã trên Wikipedia. Tuy nhiên, để giải thích sâu hơn về cuộc tấn công, chúng ta sẽ cần một số định nghĩa được giới thiệu trước một cách tốt nhất.

Vì vậy, DES là mật mã khối dựa trên mạng Feistel. Mật mã có kích thước khối là 64 bit và kích thước khóa là 56 bit. Hãy xem xét sơ đồ mã hóa của thuật toán DES.

Như có thể thấy trong hình, khi mã hóa văn bản, các thao tác sau được thực hiện:

Hoán vị bit ban đầu. Ở giai đoạn này, các bit của khối đầu vào được xáo trộn theo một thứ tự nhất định.
Sau đó, các bit hỗn hợp được chia thành hai nửa, được đưa vào đầu vào của hàm Feistel. Đối với DES tiêu chuẩn, mạng Feistel bao gồm 16 vòng, nhưng vẫn tồn tại các biến thể khác của thuật toán.
Hai khối thu được ở vòng biến đổi cuối cùng được kết hợp và một hoán vị khác được thực hiện trên khối kết quả.

Trong mỗi vòng của mạng Feistel, 32 bit ít quan trọng nhất của thông báo được truyền qua hàm f:

Hãy xem các hoạt động được thực hiện ở giai đoạn này:

Khối đầu vào được chuyển qua hàm mở rộng E, hàm này chuyển đổi khối 32 bit thành khối 48 bit.
Khối kết quả được thêm vào khóa tròn K i .
Kết quả của bước trước được chia thành 8 khối, mỗi khối 6 bit.
Mỗi khối B i nhận được được chuyển qua hàm thay thế S-Box i, hàm này thay thế chuỗi 6 bit bằng khối 4 bit.
Khối 32 bit thu được được chuyển qua hoán vị P và được trả về dưới dạng kết quả của hàm f.

Mối quan tâm lớn nhất của chúng tôi từ quan điểm giải mã mật mã là các khối S, được thiết kế để che giấu kết nối giữa dữ liệu đầu vào và đầu ra của hàm f. Để tấn công thành công DES, trước tiên chúng ta sẽ xây dựng các đối tượng thống kê tương tự cho từng hộp S, sau đó mở rộng chúng cho toàn bộ mật mã.

Phân tích khối S

Mỗi hộp S lấy một chuỗi 6 bit làm đầu vào và với mỗi chuỗi như vậy, một giá trị 4 bit cố định được trả về. Những thứ kia. có tổng cộng 64 tùy chọn đầu vào và đầu ra. Nhiệm vụ của chúng ta là chỉ ra mối quan hệ giữa dữ liệu đầu vào và đầu ra của khối S. Ví dụ: đối với hộp S thứ ba của mật mã DES, bit thứ 3 của chuỗi đầu vào bằng bit thứ 3 của chuỗi đầu ra trong 38 trên 64 trường hợp. Do đó, chúng tôi đã tìm thấy sự tương tự thống kê sau đây cho S thứ ba -hộp:
S 3 (x) = x, thỏa mãn với xác suất P=38/64.
Cả hai vế của phương trình biểu thị 1 bit thông tin. Do đó, nếu bên trái và bên phải độc lập với nhau thì phương trình sẽ phải thỏa mãn với xác suất là 1/2. Như vậy, chúng ta vừa chứng minh được mối quan hệ giữa đầu vào và đầu ra của hộp S thứ 3 của thuật toán DES.

Hãy xem xét cách chúng ta có thể tìm thấy sự tương tự thống kê của hộp S trong trường hợp chung.

Đối với hộp S S a , 1  α  63 và 1   15, giá trị NS a (α, β) mô tả số lần trong số 64 bit đầu vào XOR có thể có S a được xếp chồng lên các bit α bằng các bit đầu ra XOR được xếp chồng lên các bit α β, tức là:
trong đó ký hiệu là logic AND.
Các giá trị của α và β mà NS a (α, β) khác biệt nhất so với 32 mô tả sự tương tự thống kê hiệu quả nhất của hộp S a .

Chất tương tự hiệu quả nhất được tìm thấy trong hộp S thứ 5 của mật mã DES với α = 16 và β = 15 NS 5 (16, 15) = 12. Điều này có nghĩa là phương trình sau đúng: Z=Y ⊕ Y ⊕ Y ⊕ Y, trong đó Z là chuỗi đầu vào của hộp S và Y là chuỗi đầu ra.
Hoặc có tính đến thực tế là trong thuật toán DES, trước khi vào hộp S, dữ liệu được thêm modulo 2 bằng một phím tròn, tức là. Z = X ⊕ K ta có
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, trong đó X và Y là dữ liệu đầu vào và đầu ra của hàm f mà không tính đến các hoán vị.
Phương trình kết quả được thực hiện trên tất cả các vòng của thuật toán DES với cùng xác suất P=12/64.
Bảng sau đây hiển thị danh sách những cái hiệu quả, tức là. có độ lệch lớn nhất so với P=1/2, tương tự thống kê cho từng khối s của thuật toán DES.

Xây dựng các tương tự thống kê cho nhiều vòng DES

Bây giờ chúng ta hãy chỉ ra cách chúng ta có thể kết hợp các điểm tương tự thống kê của một số vòng DES và cuối cùng thu được một điểm tương tự thống kê cho toàn bộ mật mã.
Để làm điều này, hãy xem xét phiên bản ba vòng của thuật toán:

Hãy sử dụng phép tương tự thống kê hiệu quả của hộp s thứ 5 để tính các bit nhất định của giá trị X(2).
Chúng ta biết rằng với xác suất 12/64 đẳng thức đúng trong hàm f X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, trong đó X là bit đầu vào thứ hai của hộp S thứ 5, về cơ bản nó là bit thứ 26 của chuỗi thu được sau khi mở rộng các bit đầu vào. Bằng cách phân tích hàm mở rộng, chúng ta có thể xác định rằng bit thứ 26 được thay thế bằng bit thứ 17 của chuỗi X(1).
Tương tự, Y,..., Y thực chất là các bit thứ 17, 18, 19 và 20 của dãy thu được trước hoán vị P. Xét hoán vị P, ta thấy các bit Y,..., Y thực chất là các bit Y (1), Y(1), Y(1), Y(1).
Bit khóa K liên quan đến các phương trình là bit thứ 26 của khóa con vòng đầu tiên K1 và sau đó dữ liệu tương tự thống kê có dạng sau:
X(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y1 ⊕ Y(1) = K1.
Kể từ đây, X(1) ⊕ K1 = Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1)(2) với xác suất P=12/64.
Biết 3, 8, 14, 25 bit của chuỗi Y(1), bạn có thể tìm được 3, 8, 14, 25 bit của chuỗi X(2):
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) hoặc tính đến phương trình (2)
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 (3) với xác suất là 12/64.

Hãy tìm một biểu thức tương tự bằng cách sử dụng vòng cuối cùng. Lần này chúng ta có phương trình
X(3) ⊕ K3 = Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3).
Bởi vì
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
chúng tôi hiểu điều đó
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3(4) với xác suất là 12/64.

Đánh đồng vế phải của phương trình (3) và (4) ta thu được
CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3 = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 với xác suất (12/64) 2 +(1-12/64) 2.
Có tính đến thực tế là X(1) = PR và X(3) = CR, chúng ta thu được một kết quả tương tự về mặt thống kê
СL ⊕ CR ⊕ PL ⊕ PR = K1 ⊕ K3 (5) ,
được thực hiện với xác suất (12/64) 2 + (1-12/64) 2 =0,7.
Tương tự thống kê được mô tả ở trên có thể được biểu diễn bằng đồ họa như sau (các bit trong hình được đánh số từ phải sang trái và bắt đầu từ 0):

Kẻ tấn công đã biết tất cả các bit ở vế trái của phương trình, vì vậy hắn có thể áp dụng Thuật toán 1 và tìm ra giá trị của K1 ⊕ K3. Hãy chỉ ra cách sử dụng phép tương tự thống kê này, bạn có thể mở không phải 1 mà là 12 bit của khóa mã hóa K.

Tấn công DES bằng bản rõ đã biết

Hãy để chúng tôi trình bày một phương pháp mà bạn có thể mở rộng cuộc tấn công và ngay lập tức thu được 6 bit của vòng kết nối đầu tiên.
Khi soạn phương trình (5), chúng ta đã tính đến thực tế là chúng ta không biết giá trị của F1(PR, K1). Do đó, chúng tôi đã sử dụng tín hiệu tương tự thống kê K1 ⊕ PR của nó.
Chúng ta hãy trả về giá trị F1(PR, K1) thay cho biểu thức K1 ⊕ PR và thu được phương trình sau:
СL ⊕ CR ⊕ PL ⊕ F1(PR, K1) = K3 (6) , sẽ được thực hiện với xác suất 12/64. Xác suất đã thay đổi vì chúng tôi chỉ để lại kết quả thống kê tương tự từ vòng thứ ba, tất cả các giá trị khác đều cố định.

Ở trên chúng ta đã xác định rằng giá trị của F1(PR, K1) bị ảnh hưởng bởi các bit đầu vào của hộp S thứ 5, cụ thể là các bit khóa K1 và các bit của khối PR. Hãy chỉ ra cách chỉ cần một tập hợp văn bản mở/đóng, bạn có thể khôi phục giá trị của K1. Để làm điều này, chúng tôi sẽ sử dụng Thuật toán 2.

Thuật toán 2
Gọi N là số cặp văn bản mở/đóng đã biết trước cuộc tấn công. Sau đó để mở key bạn cần thực hiện các bước sau.
Với (i=0; tôi<64; i++) do
{
Vì(j=0; j {
if(СL j ⊕ CR j ⊕ PL j ⊕ F1(PR j , i)=0) thì
T tôi =T tôi +1
}
}
Là một chuỗi có thể xảy ra K1, giá trị của i được lấy sao cho biểu thức |T i -N/2| có giá trị lớn nhất.

Với đủ số lượng bản rõ đã biết, thuật toán sẽ có xác suất cao trả về giá trị đúng của sáu bit của khóa con vòng đầu tiên K1. Điều này được giải thích là do nếu biến i không bằng K1 thì giá trị của hàm F1(PR j, K) sẽ là ngẫu nhiên và số phương trình cho giá trị i đó mà vế trái là bằng 0 sẽ có xu hướng N/2. Nếu đoán đúng khóa con thì phía bên trái sẽ bằng bit cố định K3 với xác suất là 12/64. Những thứ kia. sẽ có sự sai lệch đáng kể so với N/2.

Sau khi nhận được 6 bit của khóa con K1, bạn có thể mở 6 bit của khóa con K3 theo cách tương tự. Tất cả những gì bạn cần làm là thay thế C bằng P và K1 bằng K3 trong phương trình (6):
PL ⊕ PR ⊕ CL ⊕ F3(CR, K3) = K1.
Thuật toán 2 sẽ trả về giá trị K3 chính xác vì quá trình giải mã của thuật toán DES giống hệt quá trình mã hóa, chỉ có dãy khóa bị đảo ngược. Vì vậy, ở vòng giải mã đầu tiên, khóa K3 được sử dụng và ở vòng giải mã cuối cùng, khóa K1 được sử dụng.

Sau khi nhận được 6 bit khóa con K1 và K3, kẻ tấn công sẽ khôi phục được 12 bit khóa chung của mật mã K, bởi vì các khóa tròn là hoán vị thông thường của khóa K. Số lượng bản rõ cần thiết để tấn công thành công phụ thuộc vào xác suất của sự tương tự thống kê. Để bẻ khóa DES 3 vòng 12 bit, 100 cặp văn bản công khai/riêng tư là đủ. Để mở 12 bit của khóa DES 16 vòng, cần khoảng 244 cặp văn bản. 44 bit còn lại của khóa được mở bằng cách sử dụng lực mạnh thông thường.