Bài giảng Lý thuyết mật mã - Chương 3: Hệ mật DES - Hán Trọng Thanh

4/12/2016 1 BỘ MÔN ĐIỆN TỬ HÀNG KHÔNG VŨ TRỤ 4/12/2016 1 TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN ĐIỆN TỬ - VIỄN THÔNG Môn học: LÝ THUYẾT MẬT MÃ Giảng viên: TS. Hán Trọng Thanh Email: httbkhn@gmail.com Mục tiêu học phần Cung cấp kiến thức cơ bản về mật mã đảm bảo an toàn và bảo mật thông tin:  Các phương pháp mật mã khóa đối xứng; Phương pháp mật mã khóa công khai;  Các hệ mật dòng và vấn đề tạo dãy giả ngẫu nhiên;  Lược đồ chữ ký số Elgamal và chuẩn chữ ký số ECDSA;  Độ phức tạp xử lý và độ phức tạp dữ liệu của một tấn công cụ thể vào hệ thống mật mã;  Đặc trưng an toàn của phương thức mã hóa;  Thám mã tuyến tính, thám mã vi sai và các vấn đề về xây dựng hệ mã bảo mật cho các ứng dụng. 2 4/12/2016 2 Nội Dung 1. Chương 1. Tổng quan 2. Chương 2. Mật mã khóa đối xứng 3. Chương 3. Hệ mật DES 4. Chương 4. Hàm băm và chữ ký số 5. Chương 5. Dãy giả ngẫu nhiên và hệ mật dòng 6. Chương 6. Kỹ thuật quản lý khóa 4/12/2016 3 Tài liệu tham khảo 1. A. J. Menezes, P. C. Van Oorschot, S. A. Vanstone, Handbook of applied cryptography, CRC Press 1998. 2. B. Schneier, Applied Cryptography. John Wiley Press 1996. 3. M. R. A. Huth, Secure Communicating Systems, Cambridge University Press 2001. 4. W. Stallings, Network Security Essentials, Applications and Standards, Prentice Hall. 2000. 4 4/12/2016 3 Nhiệm vụ của Sinh viên 1. Chấp hành nội quy lớp học 2. Thực hiện đầy đủ bài tập 3. Nắm vững ngôn ngữ lập trình Matlab 5 Chương 3. Hệ mật DES 3.1. Giới thiệu sơ lược hệ mật DES 3.2. Cấu trúc hệ mật DES 3.3. Thám mã hệ mật DES 6 4/12/2016 4 3.1. Sơ lược hệ mật DES 7 The Data Encryption Standard (DES) is a symmetric-key block cipher published by the National Institute of Standards and Technology (NIST). In 1973, NIST published a request for proposals for a national symmetric-key cryptosystem. A proposal from IBM, a modification of a project called Lucifer, was accepted as DES. DES was published in the Federal Register in March 1975 as a draft of the Federal Information Processing Standard (FIPS). 3.2. Cấu trúc hệ mật DES 8 DES is a block cipher 4/12/2016 5 3.2. Cấu trúc hệ mật DES 9 The encryption process is made of two permutations (P-boxes), which we call initial and final permutations, and sixteen Feistel rounds. 3.2. Cấu trúc hệ mật DES 10 Initial and final permutation steps in DES 4/12/2016 6 3.2. Cấu trúc hệ mật DES 11 Initial and final permutation steps in DES 3.2. Cấu trúc hệ mật DES 12 Ví dụ Find the output of the final permutation box when the input is given in hexadecimal as: 4/12/2016 7 3.2. Cấu trúc hệ mật DES 13 The initial and final permutations are straight P-boxes that are inverses of each other. They have no cryptography significance in DES. 3.2. Cấu trúc hệ mật DES 14 DES uses 16 rounds. Each round of DES is a Feistel cipher. 4/12/2016 8 3.2. Cấu trúc hệ mật DES 15 The heart of DES is the DES function. The DES function applies a 48-bit key to the rightmost 32 bits to produce a 32-bit output. DES Function 3.2. Cấu trúc hệ mật DES 16 Since RI−1 is a 32-bit input and KI is a 48-bit key. Expansion P-box It needs to expand RI−1 to 48 bits. 4/12/2016 9 3.2. Cấu trúc hệ mật DES 17 DES uses this table to define this P-box 3.2. Cấu trúc hệ mật DES 18 Whitener (XOR) After the expansion permutation, DES uses the XOR operation on the expanded right section and the round key. • Note that: • Both the right section and the key are 48-bits in length. • The round key is used only in this operation. 4/12/2016 10 3.2. Cấu trúc hệ mật DES 19 S-Boxes The S-boxes do the real mixing (confusion). DES uses 8 S-boxes, each with a 6-bit input and a 4-bit output. 3.2. Cấu trúc hệ mật DES 20 4/12/2016 11 3.2. Cấu trúc hệ mật DES 21 S-box 1 S-box 2 3.2. Cấu trúc hệ mật DES 22 S-box 3 S-box 4 4/12/2016 12 3.2. Cấu trúc hệ mật DES 23 S-box 5 S-box 6 3.2. Cấu trúc hệ mật DES 24 S-box 7 S-box 8 4/12/2016 13 3.2. Cấu trúc hệ mật DES 25 Straight Permutation 3.2. Cấu trúc hệ mật DES 26 Using mixers and swappers, we can create the cipher and reverse cipher, each having 16 rounds. First Approach To achieve this goal, one approach is to make the last round (round 16) different from the others; it has only a mixer and no swapper. In the first approach, there is no swapper in the last round. 4/12/2016 14 3.2. Cấu trúc hệ mật DES 27 Using mixers and swappers, we can create the cipher and reverse cipher, each having 16 rounds. 3.2. Cấu trúc hệ mật DES 28 Key Generation The round-key generator creates sixteen 48-bit keys out of a 56-bit cipher key. 4/12/2016 15 3.2. Cấu trúc hệ mật DES 29 3.2. Cấu trúc hệ mật DES 30 4/12/2016 16 3.2. Cấu trúc hệ mật DES 31 Key-compression table 3.2. Cấu trúc hệ mật DES 32 Ví dụ We choose a random plaintext block and a random key, and determine what the ciphertext block would be (all in hexadecimal): 4/12/2016 17 3.2. Cấu trúc hệ mật DES 33 3.2. Cấu trúc hệ mật DES 34 4/12/2016 18 3.2. Cấu trúc hệ mật DES 35 At the destination, Bob can decipher the ciphertext received from Alice using the same key. 3.3. Thám mã hệ mật DES 36 Two desired properties of a block cipher are the avalanche effect and the completeness. Completeness effect Completeness effect means that each bit of the ciphertext needs to depend on many bits on the plaintext. 4/12/2016 19 3.3. Thám mã hệ mật DES 37 During the last few years critics have found some weaknesses in DES. Weaknesses in Cipher Design 1. Weaknesses in S-boxes 2. Weaknesses in P-boxes 3. Weaknesses in Key 3.3. Thám mã hệ mật DES 38 4/12/2016 20 3.3. Thám mã hệ mật DES 39 3.3. Thám mã hệ mật DES 40 Trong 2 trường hợp khóa K có 4 khóa có độ an toàn rất kém đó là các khóa toàn 0 hoặc 1 4/12/2016 21 3.3. Thám mã hệ mật DES 41 3.3. Thám mã hệ mật DES 42 Let’s try the first weak key to encrypt a block two times. After two encryptions with the same key the original plaintext block is created. Note that we have used the encryption algorithm two times, not one encryption followed by another decryption. Weak key should be avoided 4/12/2016 22 3.3. Thám mã hệ mật DES 43 3.3. Thám mã hệ mật DES 44 4/12/2016 23 3.3. Thám mã hệ mật DES 45 A pair of semi-weak keys in encryption and decryption 3.3. Thám mã hệ mật DES 46