An toàn và bảo mật thông tin - Mã hóa DES - Đại học Công nghiệp Hà Nội

Nội dung text: An toàn và bảo mật thông tin - Mã hóa DES - Đại học Công nghiệp Hà Nội

1. ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI Lớp KHMT3-K3 DES Thực hiện: Nguyễn Đình Mạnh Dương Văn Minh Trần Anh Nam (Team Header) Nguyễn Danh Nam Trần Tuấn Nghĩa Nguyễn Thị Nhài Hoàng Ninh Nhật 1
2. Mô hình về DES Hoán Vị Khởi Đầu DES Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Giải Mã DES ▪ Giới thiệu về DES ▪ Hoán Vị Khởi Đầu ▪ Mô Tả Thuật Toán ▪ Hàm f ▪ Khóa Chuyển Đổi ▪ Giải Mã DES 2
3. Mô hình về DES Hoán Vị Khởi Đầu Giới thiệu về DES Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Giải Mã DES ▪ Ngày 13/5/1973 ủy ban quốc gia về tiêu chuẩn của Mỹ công bố yêu cầu về hệ mật mã áp dụng cho toàn quốc. ▪ Des được công ty IBM công bố vào năm 1975. 3
4. Mô hình về DES Hoán Vị Khởi Đầu Giới thiệu về DES Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Giải Mã DES ▪ DES là thuật toán mã hóa khối, độ dài mỗi khối là 64 bit . ▪ Khóa dùng trong DES có độ dài toàn bộ là 64 bit. Tuy nhiên chỉ có 56 bit thực sự được sử dụng; 8 bit còn lại chỉ dùng cho việc kiểm tra. ▪ Des xuất ra bãn mã 64 bit. 4
5. Văn Bản Gốc Mô hình về DES Hoán Vị Khởi Đầu IP Key K Mô Tả Thuật Toán Hàm f L0 R0 Khóa Chuyển Đổi Giải Mã DES f Vòng 1 K1 Biến đổi 1 f(R K ) L1=R0 R1=L0 0 1 f(R K ) L15=R14 R15 =L14 14 15 f Vòng 16 K16 Biến đổi 16 f(R K ) L16=R15 R16 =L15  15 16 IP-1 Văn Bản Mã Hóa 5
6. Mô hình về DES Hoán Vị Khởi Đầu Hoán vị khởi đầu Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Hoán vị khởi đầu (Kí hiệu là IP) đổi chỗ khối dữ Giải Mã DES liệu vào, thay đổi vị trí các bit trong khối dữ liệu vào. Tất cả các bảng hoán vị khởi đầu được đọc từ trái qua phải từ trên xuống dưới. X IP 1 2 3 4 5 6 7 8 58 50 42 34 26 18 10 2 9 10 11 12 13 14 15 16 60 52 44 36 28 20 12 4 17 18 19 20 21 22 23 24 62 54 46 38 30 22 14 6 25 26 27 28 29 30 31 32 64 56 48 40 32 24 16 8 33 34 35 36 37 38 39 40 57 49 41 33 25 17 9 1 41 42 43 44 45 46 47 48 59 51 43 35 27 19 11 3 49 50 51 52 53 54 55 56 61 53 45 37 29 21 13 5 57 58 59 60 61 62 63 64 63 55 47 39 31 23 15 7 6
7. Mô hình về DES Hoán Vị Khởi Đầu Hoán vị khởi đầu Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Giải Mã DES Trong bảng trên hoán vị khởi đầu chuyển bit 1 thành bit 58, bit 2 thành bit 50, bit 3 thành bit 42. 7
8. Mô hình về DES Hoán Vị Khởi Đầu Hoán Vị Cuối Cùng Mô Tả Thuật Toán Hàm f - Hoán vị cuối cùng là nghịch đảo của hoán vị khởi Khóa Chuyển Đổi đầu. Giải Mã DES - Khối L16R16 được sử dụng như khối dữ liệu ra của hoán vị cuối cùng. IP-1 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 41 9 49 17 57 25 8
9. Mô hình về DES Hoán Vị Khởi Đầu Hoán Vị Cuối Cùng Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Giải Mã DES Chú ý: IP-1 (IP(X))=X 9
10. Mô hình về DES Hoán Vị Khởi Đầu Hàm f Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Li = Ri-1 Giải Mã DES Ri = Li-1 XOR f(Ri-1, ki) L0 R0 f K1 ⊕f(R K ) L1=R0 R1=L0 0 1 10
11. Mô hình về DES Hoán Vị Khởi Đầu Mô Tả Thuật Toán Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Với 1<=i<=16. Theo qui tắc: Giải Mã DES for(i=1;i<=16,i++){ Li=Ri-1 Ri=Li-1f(Ri-1,Ki) }  là phép XOR của hai xâu bit: 0  0=0 , 1  1=0 1  0=1, 0  1=1 f là hàm mà ta sẽ mô tả sau. Ki là các xâu có độ dài 48 bit được tính như là các hàm của khóa K. K1 đến K16 lập nên một lịch khóa. 11
12. Mô hình về DES Hoán Vị Khởi Đầu Hàm Mô Tả Thuật Toán f Hàm f Khóa Chuyển Đổi Hàm f lấy đối số đầu là xâu Giải Mã DES nhập Ri-1 (32 bit) đối số thứ hai là Ki (48bit) và tạo ra xâu xuất có độ dài 32 bit. Đối số đầu Ri-1 sẽ được “mở rộng” thành xâu có độ dài 48 bit tương ứng với hàm mở rộng E cố định. 12
13. Mô hình về DES Hoán Vị Khởi Đầu Hàm Mô Tả Thuật Toán f Hàm f E(Ri) bao gồm 32 bit từ Ri, được Khóa Chuyển Đổi hoán vị theo một cách thức xác định, với Giải Mã DES 16 bit được tạo ra 2 lần. Với mỗi bộ 4 bit của dữ liệu vào, bit đầu tiên và bit thứ 4 tương ứng với 2 bit của dữ liệu ra, còn bit số 2 và số 3 tương ứng với 1 bit của dữ liệu ra Dữ liệu vào E bit table 1 2 3 4 32 1 2 3 4 5 5 6 7 8 4 5 6 7 8 9 9 10 11 12 8 9 10 11 12 13 13 14 15 16 12 13 14 15 16 17 17 18 19 20 16 17 18 19 20 21 21 22 23 24 20 21 22 23 24 25 25 26 27 28 24 25 26 27 28 29 29 30 31 32 28 29 30 31 32 113
14. Mô hình về DES Hoán Vị Khởi Đầu Hộp Thay Thế - S Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi ▪ Sau khi được nén khóa XOR với khối mở rộng , 48 Giải Mã DES bit 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ế. Khối 48 bit được chia thành 8 khối 6 bit. Mỗi khối được thực hiện trên 1 hộp S riêng biệt: 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 S2, , khối 8 được thực hiện trên hộp S8 48 6 6 S1 S8 4 4 32 14
15. Mô hình về DES Hoán Vị Khởi Đầu Hộp Thay Thế - S Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Giải Mã DES 15
16. Mô hình về DES Hoán Vị Khởi Đầu Khóa Chuyển Đổi Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi - K là một xâu có độ dài 64 bit trong đó 56 Giải Mã DES bit dùng làm khóa và 8 bit dùng để kiểm tra lỗi. 7 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 8 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 56 bit 16
17. Mô hình về DES Hoán Vị Khởi Đầu Khóa Chuyển Đổi Mô Tả Thuật Toán Hàm f 64 Khóa Chuyển Đổi K PC-1 Giải Mã DES 56 C0 D0 28 LS1 LS1 28 48 56 K1 PC-2 C1 D1 . 28 LS2 LS2 28 . . . . . . . . . LS16 LS16 . 48 56 K16 PC-2 C16 D16 17
18. Mô hình về DES Hoán Vị Khởi Đầu Khóa Chuyển Đổi Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Quá trình tạo các khóa con (subkeys) từ Giải Mã DES khóa K 1. Sau khi loại bỏ các bit kiểm tra hoán vị các bit còn lại của K tương ứng với hoán vị cố định PC-1. Ta viết PC1(K) = C0D0, với C0 bao gồm 28 bít đầu tiên của PC-1(k) và D0 là 28 bit còn lại. 18
19. Mô hình về DES Hoán Vị Khởi Đầu Khóa Chuyển Đổi Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Giải Mã DES ▪ Hoán vị cố định PC1 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 PC1 19 11 34 60 52 44 36 63 55 7 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 19
20. Mô hình về DES Hoán Vị Khởi Đầu Khóa Chuyển Đổi Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Thuật toán tính C , D như sau: Giải Mã DES i i C for(i=1;i<=16;i++){ 0 Ci = LSi(Ci-1) LS1 Di = LSi(Di-1) } C1 Ki = PC-2(CiDi). LSi biểu diễn phép chuyển chu trình sang trái của 1 hoặc 2 vi trí tùy thuộc vào giá trị của i. 20
21. Mô hình về DES Hoán Vị Khởi Đầu Khóa Chuyển Đổi Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Giải Mã DES Sang 1 vị trí 1 2 9 16 3 4 5 6 7 8 Sang 2 vị trí 10 11 12 13 14 15 Đẩy sang trái 1 vị trí nếu i= 1, 2, 9 hoặc 16, và đẩy 2 vị trí trong những trường hợp còn lại. 21
22. Mô hình về DES Hoán Vị Khởi Đầu Khóa Chuyển Đổi Mô Tả Thuật Toán Hàm f Sau khi được dịch chuyển vị trí, 48 bít Khóa Chuyển Đổi Giải Mã DES được lựa chọn ra từ 56 bít. Thực hiện này đổi chỗ thứ tự các bít như lựa chọn một tập con các bít, nó được gọi là hoán vị nén hoặc hoán vị lựa chọn (PC-2). 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 PC2 16 7 27 20 13 2 41 50 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 22
23. Mô hình về DES Hoán Vị Khởi Đầu Giải Mã DES Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Giải Mã DES Việc giải mã dùng cùng một thuật toán như việc mã hoá. Để giải mã dữ liệu đã được mã hoá, quá trình giống như mã hoá được lặp lại nhưng các chìa khoá phụ được dùng theo thứ tự ngược lại từ K16 đến K1, nghĩa là trong bước 2 của quá trình mã hoá dữ liệu đầu vào ở trên Ri-1 sẽ được XOR với K17-i chứ không phải với Ki. 23
24. Mô hình về DES Hoán Vị Khởi Đầu Giải Mã DES Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Giải Mã DES 24
25. Mô hình về DES Hoán Vị Khởi Đầu Đặc Điểm Mã Des Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Phần Cứng Phần Mềm Giải Mã DES Các phép tính số học duy nhất được thực hiện là phép XOR các xâu bít. Hàm mở rộng E, các hộp S, các hoán vị khởi đầu IP, hoán vị cuối cùng IP-1 và việc tính toán các khoá k1, k2, , k16 đều có thể thực hiện được cùng lúc bằng tra bảng (trong phần mềm) hoặc bằng cách nối cứng chúng thành mạch. Ứng dụng rất quan trọng của DES là trong giao dịch ngân hàng Mỹ. DES được dùng để mã hoá các số định danh các nhân (PIN) và việc chuyển tài khoảnđược thực hiện bằng máy thủ quỹ tự động (ATM). 25
26. Mô hình về DES Hoán Vị Khởi Đầu Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Giải Mã DES 26
27. Mô hình về DES Hoán Vị Khởi Đầu Tấn Công Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Có hai điểm chỉ trích nghiêm trọng về DES Giải Mã DES từ phần đầu: - Kích cỡ khóa quá nhỏ - S-boxes chứa chuẩn thiết kế không công khai. 27
28. Mô hình về DES Hoán Vị Khởi Đầu Tìm kiếm khóa đầy đủ Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi Giải Mã DES Tìm kiếm bản rõ : Biết : X và Y . Tìm K , sao cho Y=DESk(X). Ý tưởng : kiểm tra tất cả 256 trường hợp có thể là khóa 28
29. Mô hình về DES Hoán Vị Khởi Đầu Tìm kiếm khóa đầy đủ Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi víi mét cÆp râ - m· cho tríc, h·y thö tÊt c¶ Giải Mã DES 256 kho¸ cô thÓ. điÒu nµy kh«ng yªu cÇu bé nhí, nhng trung binh ph¶i thö 255 kho¸ tríc khi tim ®îc kho¸ ®óng. MÆt kh¸c, víi mét b¶n râ x cho tríc, Oscar cã thÓ tÝnh tríc yK = eK(x) ®èi víi toµn bé 256 kho¸ K vµ x©y dùng mét b¶ng c¸c cÆp (yK,K) ®îc s¾p xÕp theo c¸c t¹o ®é ®Çu cña chóng. Sau ®ã khi Oscar thu ®îc b¶n m· y ( lµ kÕt qu¶ cña phÐp m· b¶n râ x), anh ta ph¶i nh×n vµo gi¸ trÞ y trong b¶ng vµ lËp tøc t×m ®- îc kho¸ K. 29
30. Mô hình về DES Hoán Vị Khởi Đầu Thám mã vi sai Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi ▪ Được đề xuất bởi Biham và Shamir năm 1990. Giải Mã DES ▪ Nguyên tắc : Đây là một kỹ thuật sử dụng những phỏng đoán khác nhau trong bản rõ để đưa ra những thông tin trong bản mã ▪ Phá mã vi sai là thuật toán xem xét những cặp mã hoá khác nhau, đây là những cặp mã hoá mà bản rõ của chúng là khác biệt. Người ta sẽ phân tích tiến trình biến đổi của những cặp mã này thông qua các vòng của DES khi chúng được mã hoá với cùng một khoá K. Sau đó sẽ chọn hai bản rõ khác nhau một cách ngẫu nhiên hợp lý nhất. Sử dụng sự khác nhau của kết quả mã hoá và gán cho những khoá khác nhau một cách phù hợp nhất. Khi phân tích nhiều hơn những cặp bản mã, chúng ta sẽ tìm ra một khoá được xem là đúng nhất 30
31. Mô hình về DES Hoán Vị Khởi Đầu Thám mã vi sai Mô Tả Thuật Toán Hàm f Khóa Chuyển Đổi ▪ Để phá mã DES với đầy đủ 16 chu trình : Giải Mã DES Phá mã vi sai cần đến 247 cặp bản rõ (X,Y). ▪ Để hiểu được một văn bản đã được mã hóa cần 255 cặp bản rõ (X,Y). ▪ Phải cần đến 237 phép tính số học ▪ Mỗi cặp (X,Y ) có độ dài là 128bit , cần lưu trữ lớn thì việc tấn công này là không thực tế 31