Bài giảng Lý thuyết mật mã - Chương 2, Phần 2: Mật mã khóa đối xứng - Hán Trọng Thanh

4/7/2016 1 BỘ MÔN ĐIỆN TỬ HÀNG KHÔNG VŨ TRỤ 4/7/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/7/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. Mật mã khóa công khai 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/7/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/7/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 2. Mật mã khóa đối xứng 2.1. Giới thiệu sơ lược mật mã khóa đối xứng cổ điển 2.2. Một số hệ mật mã khóa đối xứng cổ điển 2.3. Sơ lược hệ mật mã dòng và hệ mật mã khối 2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại. 2.5 Sơ lược hệ mật mã đối xứng hiện đại 6 4/7/2016 4 2.5. Sơ lược hệ mật mã đối xứng hiện đại 7 2.5.1. Hệ mật mã khối hiện đại A symmetric-key modern block cipher encrypts an n-bit block of plaintext or decrypts an n-bit block of ciphertext. The encryption or decryption algorithm uses a k-bit key. 2.5. Sơ lược hệ mật mã đối xứng hiện đại 8 2.5.1. Hệ mật mã khối hiện đại A modern block cipher can be designed to act as a substitution cipher or a transposition cipher. To be resistant to exhaustive-search attack, a modern block cipher needs to be designed as a substitution cipher. 4/7/2016 5 2.5. Sơ lược hệ mật mã đối xứng hiện đại 9 2.5.1. Hệ mật mã khối hiện đại A substitution block cipher model as a permutation Full-Size Key Substitution Block Ciphers A full-size key substitution cipher does not transpose bits; it substitutes bits. We can model the substitution cipher as a permutation if we can decode the input and encode the output. 2.5. Sơ lược hệ mật mã đối xứng hiện đại 10 2.5.1. Hệ mật mã khối hiện đại Full-Size Key Transposition Block Ciphers In a full-size key transposition cipher we need to have n! possible keys, so the key should have ! bits. A transposition block cipher modeled as a permutation 4/7/2016 6 2.5. Sơ lược hệ mật mã đối xứng hiện đại 11 2.5.1. Hệ mật mã khối hiện đại A substitution block cipher model as a permutation 2.5. Sơ lược hệ mật mã đối xứng hiện đại 12 2.5.1. Hệ mật mã khối hiện đại The model and the set of permutation table? -> Using decoder before permutation and coder after permutation! The key is also much longer, log240,320 = 16 bits. Show the model and the set of permutation tables for a 3-bit block substitution cipher. 4/7/2016 7 2.5. Sơ lược hệ mật mã đối xứng hiện đại 13 2.5.1. Hệ mật mã khối hiện đại A substitution block cipher model as a permutation 2.5. Sơ lược hệ mật mã đối xứng hiện đại 14 2.5.1. Hệ mật mã khối hiện đại Full-Size Key Substitution Block Ciphers A partial-key cipher is a group under the composition operation if it is a subgroup of the corresponding full-size key cipher. A full-size key n-bit transposition cipher or a substitution block cipher can be modeled as a permutation, but their key sizes are different:  Transposition: the key is log2n!  bits long.  Substitution: the key is log2(2 n)!  bits long. 4/7/2016 8 2.5. Sơ lược hệ mật mã đối xứng hiện đại 15 2.5.1. Hệ mật mã khối hiện đại Modern block ciphers normally are keyed substitution ciphers in which the key allows only partial mappings from the possible inputs to the possible outputs. A P-box (Permutation Box) parallels the traditional transposition cipher for characters. It transposes bits. P-Boxes Components of a Modern Block Cipher 2.5. Sơ lược hệ mật mã đối xứng hiện đại 16 2.5.1. Hệ mật mã khối hiện đại Three types of P-boxes 4/7/2016 9 2.5. Sơ lược hệ mật mã đối xứng hiện đại 17 2.5.1. Hệ mật mã khối hiện đại Shows all 6 possible mappings of a 3 × 3 P-Box ? 2.5. Sơ lược hệ mật mã đối xứng hiện đại 18 2.5.1. Hệ mật mã khối hiện đại Example of a permutation table for a straight P-box 4/7/2016 10 2.5. Sơ lược hệ mật mã đối xứng hiện đại 19 2.5.1. Hệ mật mã khối hiện đại Compression P-Boxes A compression P-box is a P-box with n inputs and m outputs where m < n. Example of a 32 × 24 permutation table 2.5. Sơ lược hệ mật mã đối xứng hiện đại 20 2.5.1. Hệ mật mã khối hiện đại Expansion P-Boxes An expansion P-box is a P-box with n inputs and m outputs where m > n. Example of a 12 × 16 permutation table 4/7/2016 11 2.5. Sơ lược hệ mật mã đối xứng hiện đại 21 2.5.1. Hệ mật mã khối hiện đại Lưu ý A straight P-box is invertible, but compression and expansion P-boxes are not. 2.5. Sơ lược hệ mật mã đối xứng hiện đại 22 2.5.1. Hệ mật mã khối hiện đại How to invert a permutation table represented as a one-dimensional table? 4/7/2016 12 2.5. Sơ lược hệ mật mã đối xứng hiện đại 23 2.5.1. Hệ mật mã khối hiện đại Compression and expansion P-boxes are non-invertible 2.5. Sơ lược hệ mật mã đối xứng hiện đại 24 2.5.1. Hệ mật mã khối hiện đại S-Box An S-box (Substitution Box) can be thought of as a miniature substitution cipher. An S-box is an m × n substitution unit, where m and n are not necessarily the same. Lưu ý 4/7/2016 13 2.5. Sơ lược hệ mật mã đối xứng hiện đại 25 2.5.1. Hệ mật mã khối hiện đại In an S-box with three inputs and two outputs, we have This S-Box is linear because a1,1 = a1,2 = a1,3 = a2,1 = 1 and a2,2 = a2,3 = 0. 2.5. Sơ lược hệ mật mã đối xứng hiện đại 26 2.5.1. Hệ mật mã khối hiện đại In an S-box with three inputs and two outputs, we have where multiplication and addition is in GF(2). The S-box is nonlinear because there is no linear relationship between the inputs and the outputs. 4/7/2016 14 2.5. Sơ lược hệ mật mã đối xứng hiện đại 27 2.5.1. Hệ mật mã khối hiện đại The following table defines the input/output relationship for an S-box of size 3 × 2. The leftmost bit of the input defines the row; the two rightmost bits of the input define the column. The two output bits are values on the cross section of the selected row and column. Input: 010 – output: 01 Input: 101 – output: 00 2.5. Sơ lược hệ mật mã đối xứng hiện đại 28 2.5.1. Hệ mật mã khối hiện đại An S-box may or may not be invertible. In an invertible S-box, the number of input bits should be the same as the number of output bits. Lưu ý 4/7/2016 15 2.5. Sơ lược hệ mật mã đối xứng hiện đại 29 2.5.1. Hệ mật mã khối hiện đại An example of an invertible S-box Encryption: input: 001 -> output ? Decryption: input: 101 -> output ? 2.5. Sơ lược hệ mật mã đối xứng hiện đại 30 2.5.1. Hệ mật mã khối hiện đại Exclusive-Or An important component in most block ciphers is the exclusive-or operation. Invertibility of the exclusive-or operation 4/7/2016 16 2.5. Sơ lược hệ mật mã đối xứng hiện đại 31 2.5.1. Hệ mật mã khối hiện đại Addition and subtraction operations in the GF(2n) field are performed by a single operation called the exclusive- or (XOR). The five properties of the exclusive-or operation in the GF(2n) field makes this operation a very interesting component for use in a block cipher: closure, associativity, commutativity, existence of identity, and existence of inverse. 2.5. Sơ lược hệ mật mã đối xứng hiện đại 32 2.5.1. Hệ mật mã khối hiện đại Circular Shift Another component found in some modern block ciphers is the circular shift operation. Circular shifting an 8-bit word to the left or right 4/7/2016 17 2.5. Sơ lược hệ mật mã đối xứng hiện đại 33 2.5.1. Hệ mật mã khối hiện đại Swap The swap operation is a special case of the circular shift operation where k = n/2. Swap operation on an 8-bit word 2.5. Sơ lược hệ mật mã đối xứng hiện đại 34 2.5.1. Hệ mật mã khối hiện đại Split and Combine Two other operations found in some block ciphers are split and combine. Split and combine operations on an 8-bit word 4/7/2016 18 2.5. Sơ lược hệ mật mã đối xứng hiện đại 35 2.5.1. Hệ mật mã khối hiện đại Shannon introduced the concept of a product cipher. A product cipher is a complex cipher combining substitution, permutation, and other components discussed in previous sections. Product Ciphers 2.5. Sơ lược hệ mật mã đối xứng hiện đại 36 2.5.1. Hệ mật mã khối hiện đại Diffusion The idea of diffusion is to hide the relationship between the ciphertext and the plaintext. Diffusion hides the relationship between the ciphertext and the plaintext. Lưu ý 4/7/2016 19 2.5. Sơ lược hệ mật mã đối xứng hiện đại 37 2.5.1. Hệ mật mã khối hiện đại Confusion The idea of confusion is to hide the relationship between the ciphertext and the key. Lưu ý Confusion hides the relationship between the ciphertext and the key. 2.5. Sơ lược hệ mật mã đối xứng hiện đại 38 2.5.1. Hệ mật mã khối hiện đại Rounds Diffusion and confusion can be achieved using iterated product ciphers where each iteration is a combination of S-boxes, P-boxes, and other components. 4/7/2016 20 2.5. Sơ lược hệ mật mã đối xứng hiện đại 39 2.5.1. Hệ mật mã khối hiện đại A product cipher made of two rounds 2.5. Sơ lược hệ mật mã đối xứng hiện đại 40 2.5.1. Hệ mật mã khối hiện đại Two Classes of Product Ciphers Modern block ciphers are all product ciphers, but they are divided into two classes. 1. Feistel ciphers 2. Non-Feistel ciphers 4/7/2016 21 2.5. Sơ lược hệ mật mã đối xứng hiện đại 41 2.5.1. Hệ mật mã khối hiện đại Feistel Ciphers Feistel designed a very intelligent and interesting cipher that has been used for decades. A Feistel cipher can have three types of components: self-invertible, invertible, and noninvertible. 2.5. Sơ lược hệ mật mã đối xứng hiện đại 42 2.5.1. Hệ mật mã khối hiện đại The first thought in Feistel cipher design Diffusion hides the relationship between the ciphertext and the plaintext. 4/7/2016 22 2.5. Sơ lược hệ mật mã đối xứng hiện đại 43 2.5.1. Hệ mật mã khối hiện đại Improvement of the previous Feistel design 2.5. Sơ lược hệ mật mã đối xứng hiện đại 44 2.5.1. Hệ mật mã khối hiện đại Final design of a Feistel cipher with two rounds 4/7/2016 23 2.5. Sơ lược hệ mật mã đối xứng hiện đại 45 2.5.1. Hệ mật mã khối hiện đại Non-Feistel Ciphers A non-Feistel cipher uses only invertible components. A component in the encryption cipher has the corresponding component in the decryption cipher. 2.5. Sơ lược hệ mật mã đối xứng hiện đại 46 2.5.2. Thám mã hệ mật mã khối hiện đại Differential Cryptanalysis Eli Biham and Adi Shamir introduced the idea of differential cryptanalysis. This is a chosen-plaintext attack. Assume that the cipher is made only of one exclusive-or operation. Without knowing the value of the key, Eve can easily find the relationship between plaintext differences and ciphertext differences if by plaintext difference P1  P2 and by ciphertext difference, C1 C2 => C1  C2 = P1  P2 4/7/2016 24 2.5. Sơ lược hệ mật mã đối xứng hiện đại 47 2.5.2. Thám mã hệ mật mã khối hiện đại Ví dụ: Hãy tìm khóa K của hệ mật như sau 2.5. Sơ lược hệ mật mã đối xứng hiện đại 48 2.5.2. Thám mã hệ mật mã khối hiện đại Differential cryptanalysis is based on a nonuniform differential distribution table of the S-boxes in a block cipher. Linear Cryptanalysis Linear cryptanalysis was presented by Mitsuru Matsui in 1993. The analysis uses known plaintext attacks. 4/7/2016 25 2.5. Sơ lược hệ mật mã đối xứng hiện đại 49 2.5.2. Thám mã hệ mật mã khối hiện đại A simple cipher with a linear S-box 2.5. Sơ lược hệ mật mã đối xứng hiện đại 50 2.5.2. Thám mã hệ mật mã khối hiện đại A simple cipher with a linear S-box This means that three known-plaintext attacks can find the values of k0, k1, and k2 . 4/7/2016 26 2.5. Sơ lược hệ mật mã đối xứng hiện đại 51 2.5.2. Thám mã hệ mật mã khối hiện đại In some modern block ciphers, it may happen that some S- boxes are not totally nonlinear; they can be approximated, probabilistically, by some linear functions. where 1 ≤ x ≤ m, 1 ≤ y ≤ n, and 1 ≤ z ≤ n. 2.5. Sơ lược hệ mật mã đối xứng hiện đại 52 2.5.3. Hệ mật mã dòng hiện đại In a modern stream cipher, encryption and decryption are done r bits at a time. We have a plaintext bit stream P = pnp2 p1, a ciphertext bit stream C = cnc2 c1, and a key bit stream K = knk2 k1, in which pi , ci , and ki are r-bit words. • Synchronous Stream Ciphers • Nonsynchronous Stream Ciphers 4/7/2016 27 2.5. Sơ lược hệ mật mã đối xứng hiện đại 53 2.5.3. Hệ mật mã dòng hiện đại In a modern stream cipher, each r-bit word in the plaintext stream is enciphered using an r-bit word in the key stream to create the corresponding r-bit word in the ciphertext stream. 2.5. Sơ lược hệ mật mã đối xứng hiện đại 54 2.5.3. Hệ mật mã dòng hiện đại In a synchronous stream cipher the key is independent of the plaintext or ciphertext. One-time pad 4/7/2016 28 2.5. Sơ lược hệ mật mã đối xứng hiện đại 55 2.5.3. Hệ mật mã dòng hiện đại In a synchronous stream cipher the key is independent of the plaintext or ciphertext. One-time pad 2.5. Sơ lược hệ mật mã đối xứng hiện đại 56 2.5.3. Hệ mật mã dòng hiện đại Feedback shift register (FSR) 4/7/2016 29 2.5. Sơ lược hệ mật mã đối xứng hiện đại 57 2.5.3. Hệ mật mã dòng hiện đại Ví dụ: Create a linear feedback shift register with 5 cells in which b5 = b4  b2  b0 . 2.5. Sơ lược hệ mật mã đối xứng hiện đại 58 2.5.3. Hệ mật mã dòng hiện đại Ví dụ: Create a linear feedback shift register with 4 cells in which b4 = b1  b0. Show the value of output for 20 transitions (shifts) if the seed is (0001)2. 4/7/2016 30 2.5. Sơ lược hệ mật mã đối xứng hiện đại 59 2.5.3. Hệ mật mã dòng hiện đại The key stream generated from a LFSR is a pseudorandom sequence in which the the sequence is repeated after N bits. The maximum period of an LFSR is to 2m − 1. 2.5. Sơ lược hệ mật mã đối xứng hiện đại 60 2.5.3. Hệ mật mã dòng hiện đại In a nonsynchronous stream cipher, the key depends on either the plaintext or ciphertext.