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

3/21/2016  1  BỘ MÔN ĐIỆN TỬ HÀNG KHÔNG VŨ TRỤ 3/21/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  3/21/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 3/21/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  3/21/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 6  3/21/2016  4  2.1. Giới thiệu sơ lược hệ mật mã khóa đối xứng cổ điển 7  Figure shows the general idea behind a symmetric-key cipher. The original message from Alice to Bob is called plaintext; the message that is sent through the channel is called the ciphertext. To create the ciphertext from the plaintext, Alice uses an encryption algorithm and a shared secret key. To create the plaintext from ciphertext, Bob uses a decryption algorithm and the same secret key.  2.1. Giới thiệu sơ lược hệ mật mã khóa đối xứng cổ điển • Based on Kirchhoff's principle, one should always assume that the adversary, Eve, knows the encryption/decryption algorithm. The resistance of the cipher to attack must be based only on the secrecy of the key. 8  Locking and unlocking with the same key 3/21/2016  5  2.2. Một số hệ mật mã khóa đối xứng cổ điển • Đây là hệ mật mã thay thế một ký tự này thành một ký tự khác. • Phân loại: – Mật mã thay thế đơn ký tự - monoalphabetic – Mật mã thay thế đa ký tự - polyalphabetic 9  2.2.1. Hệ mật mã khóa đối xứng thay thế A substitution cipher replaces one symbol with another. 2.2. Một số hệ mật mã khóa đối xứng cổ điển 10  a. Hệ mật thay thế đơn ký tự - monoalphabetic In monoalphabetic substitution, the relationship between a symbol in the plaintext to a symbol in the cipher text is always one-to-one. 3/21/2016  6  2.2. Một số hệ mật mã khóa đối xứng cổ điển • The simplest monoalphabetic cipher is the additive cipher. This cipher is sometimes called a shift cipher and sometimes a Caesar cipher, but the term additive cipher better reveals its mathematical nature. 11  a. Hệ mật thay thế đơn ký tự - monoalphabetic Plaintext and ciphertext in Z26 2.2. Một số hệ mật mã khóa đối xứng cổ điển 12  a. Hệ mật thay thế đơn ký tự - monoalphabetic 3/21/2016  7  2.2. Một số hệ mật mã khóa đối xứng cổ điển • Ví dụ 1: Hãy sử dụng mã cộng để mã hóa chữ hello với khóa K = 15. 13  a. Hệ mật thay thế đơn ký tự - monoalphabetic Plaintext: hello Ciphertext: WTAAD Additive cipher  2.2. Một số hệ mật mã khóa đối xứng cổ điển • Ví dụ 2: Hãy sử dụng mã cộng để giải mã chữ WTAAD với khóa K = 15. 14  a. Hệ mật thay thế đơn ký tự - monoalphabetic Plaintext: WTAAD Ciphertext: hello Additive cipher  3/21/2016  8  2.2. Một số hệ mật mã khóa đối xứng cổ điển • Historically, additive ciphers are called shift ciphers. Julius Caesar used an additive cipher to communicate with his officers. For this reason, additive ciphers are sometimes referred to as the Caesar cipher. Caesar used a key of 3 for his communications. 15  a. Hệ mật thay thế đơn ký tự - monoalphabetic Additive ciphers are sometimes referred to as shift ciphers or Caesar cipher. 2.2. Một số hệ mật mã khóa đối xứng cổ điển • Ví dụ 3: Hacker lấy được đoạn mã “UVACLYFZLJBYL”, khi đó anh ta làm thế nào để giải mã được đoạn mã đó?? • He tries keys from 1 to 25. With a key of 7, the plaintext is “not very secure”, which makes sense 16  a. Hệ mật thay thế đơn ký tự - monoalphabetic 3/21/2016  9  2.2. Một số hệ mật mã khóa đối xứng cổ điển 17  a. Hệ mật thay thế đơn ký tự - monoalphabetic 2.2. Một số hệ mật mã khóa đối xứng cổ điển • Ví dụ: Hacker lấy được đoạn mã 18  a. Hệ mật thay thế đơn ký tự - monoalphabetic • Số lần xuất hiện chữ cái I = 14 là nhiều nhất, do đó I tương ứng với chữ e tức là đã dịch đi 4 đơn vị hay K = 4, từ đó ta có 3/21/2016  10  2.2. Một số hệ mật mã khóa đối xứng cổ điển 19  a. Hệ mật thay thế đơn ký tự - monoalphabetic Multiplicative Ciphers In a multiplicative cipher, the plaintext and ciphertext are integers in Z26; the key is an integer in Z26*. 2.2. Một số hệ mật mã khóa đối xứng cổ điển • Ví dụ 4: What is the key domain for any multiplicative cipher? 20  a. Hệ mật thay thế đơn ký tự - monoalphabetic The key needs to be in Z26*. This set has only 12 members: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25. Tập các thặng dư thu gọn theo ݉݋݀ ݊ được định nghĩa là tập ࢆ࢔∗ ൌ ሼܽ ∈ ࢆ࢔: gcd ሺܽ , ݊ሻ ൌ 1ሽ , tức ࢆ࢔∗ là tập con của ࢆ࢔ bao gồm tất cả các phần tử nguyên tố với ݊  3/21/2016  11  2.2. Một số hệ mật mã khóa đối xứng cổ điển Ví dụ 5: Hãy sử dụng mã nhân để giải mã hóa chữ “hello” với K = 7? 21  a. Hệ mật thay thế đơn ký tự - monoalphabetic 2.2. Một số hệ mật mã khóa đối xứng cổ điển 22  a. Hệ mật thay thế đơn ký tự - monoalphabetic Affine Ciphers 3/21/2016  12  2.2. Một số hệ mật mã khóa đối xứng cổ điển 23  a. Hệ mật thay thế đơn ký tự - monoalphabetic Affine Ciphers The affine cipher uses a pair of keys in which the first key is from Z26* and the second is from Z26. What is the size of the key domain? The size of the key domain is 26 × 12 = 312. 2.2. Một số hệ mật mã khóa đối xứng cổ điển Ví dụ 6: Hãy sử dụng mã Affine để mã hóa chữ “hello” với K = (7,2)? 24  a. Hệ mật thay thế đơn ký tự - monoalphabetic 3/21/2016  13  2.2. Một số hệ mật mã khóa đối xứng cổ điển Ví dụ 7: Hãy sử dụng mã Affine để giải mã hóa chữ “ZEBBW” với K = (7,2)? 25  a. Hệ mật thay thế đơn ký tự - monoalphabetic 2.2. Một số hệ mật mã khóa đối xứng cổ điển Hãy so sánh Affine Cipher với Additive Cipher? 26  a. Hệ mật thay thế đơn ký tự - monoalphabetic The additive cipher is a special case of an affine cipher in which k1 = 1. Hãy so sánh Affine Cipher với multiplicative Cipher? The multiplicative cipher is a special case of affine cipher in which k2 = 0. 3/21/2016  14  2.2. Một số hệ mật mã khóa đối xứng cổ điển 27  a. Hệ mật thay thế đơn ký tự - monoalphabetic Monoalphabetic Substitution Cipher Because additive, multiplicative, and affine ciphers have small key domains, they are very vulnerable to brute-force attack. A better solution is to create a mapping between each plaintext character and the corresponding ciphertext character. Alice and Bob can agree on a table showing the mapping for each character. 2.2. Một số hệ mật mã khóa đối xứng cổ điển 28  a. Hệ mật thay thế đơn ký tự - monoalphabetic Monoalphabetic Substitution Cipher 3/21/2016  15  2.2. Một số hệ mật mã khóa đối xứng cổ điển 29  b. Hệ mật thay thế đa ký tự - Polyalphabetic In polyalphabetic substitution, each occurrence of a character may have a different substitute. The relationship between a character in the plaintext to a character in the ciphertext is one-to-many. Autokey Cipher 2.2. Một số hệ mật mã khóa đối xứng cổ điển 30  b. Hệ mật thay thế đa ký tự - Polyalphabetic Assume that Alice and Bob agreed to use an autokey cipher with initial key value k1 = 12. Now Alice wants to send Bob the message “Attack is today”. Enciphering is done character by character. 3/21/2016  16  2.2. Một số hệ mật mã khóa đối xứng cổ điển 31  b. Hệ mật thay thế đa ký tự - Polyalphabetic Vigenere Cipher We can encrypt the message “She is listening” using the 6- character keyword “PASCAL”. 2.2. Một số hệ mật mã khóa đối xứng cổ điển 32  b. Hệ mật thay thế đa ký tự - Polyalphabetic Vigenere Cipher We can encrypt the message “She is listening” using the 6- character keyword “PASCAL”. The initial key stream is (15, 0, 18, 2, 0, 11) 3/21/2016  17  2.2. Một số hệ mật mã khóa đối xứng cổ điển Hãy so sánh Vigenere cipher với Additive Cipher? 33  A Vigenere cipher as a combination of m additive ciphers b. Hệ mật thay thế đa ký tự - Polyalphabetic 2.2. Một số hệ mật mã khóa đối xứng cổ điển Hãy so sánh Vigenere cipher với Additive Cipher? 34  Ngược lại: the additive cipher is a special case of Vigenere cipher in which m = 1. b. Hệ mật thay thế đa ký tự - Polyalphabetic 3/21/2016  18  2.2. Một số hệ mật mã khóa đối xứng cổ điển 35  b. Hệ mật thay thế đa ký tự - Polyalphabetic Thám mã Vigenere Cipher Giả sử hacker nhận được bản tin mật sau: Làm thế nào để giải mã???? Theo phương pháp Kasiski, từng cụm 3 chữ liên tiếp được khảo sát trong cả đoạn để tìm khoảng cách ngắn nhất mà cụm đó xuất hiện lặp lại 2.2. Một số hệ mật mã khóa đối xứng cổ điển 36  b. Hệ mật thay thế đa ký tự - Polyalphabetic Thám mã Vigenere Cipher Giả sử hacker nhận được bản tin mật sau: Theo phương pháp Kasiski, từng cụm 3 chữ liên tiếp được khảo sát trong cả đoạn để tìm khoảng cách ngắn nhất mà cụm đó xuất hiện lặp lại 3/21/2016  19  2.2. Một số hệ mật mã khóa đối xứng cổ điển 37  b. Hệ mật thay thế đa ký tự - Polyalphabetic Thám mã Vigenere Cipher The greatest common divisor of differences is 4, which means that the key length is multiple of 4. First try m = 4. 2.2. Một số hệ mật mã khóa đối xứng cổ điển 38  b. Hệ mật thay thế đa ký tự - Polyalphabetic Hill Cipher Key in the Hill cipher The key matrix in the Hill cipher needs to have a multiplicative inverse. 3/21/2016  20  2.2. Một số hệ mật mã khóa đối xứng cổ điển 39  b. Hệ mật thay thế đa ký tự - Polyalphabetic Hill Cipher Ví dụ 9: Hãy mã hóa bản tin “code is ready” bằng hệ mật Hill với khóa K 2.2. Một số hệ mật mã khóa đối xứng cổ điển 40  b. Hệ mật thay thế đa ký tự - Polyalphabetic Hill Cipher 3/21/2016  21  2.2. Một số hệ mật mã khóa đối xứng cổ điển 41  b. Hệ mật thay thế đa ký tự - Polyalphabetic Thám mã hệ mật Hill • Việc thám mã hệ mật Hill bằng cách dò lần lượt các từ khóa là dường như không thực hiện được. • Hệ mật này gần như chỉ có thể bị phá được khi biết được giá trị ݉ và các cặp chữ tương ứng giữa bản mật và bản rõ. • Ví dụ: với ݉ ൌ 3 2.2. Một số hệ mật mã khóa đối xứng cổ điển 42  b. Hệ mật thay thế đa ký tự - Polyalphabetic Thám mã hệ mật Hill • Do P là ma trận khả nghịch, nên người thám mã sẽ tìm ma trận P-1, rồi tìm khóa K Từ đó, người thám mã sẽ phá được tất cả các bản mật sử dụng khóa K nói trên 3/21/2016  22  2.2. Một số hệ mật mã khóa đối xứng cổ điển 43  2.2.2. Hệ mật mã khóa đối xứng dịch chuyển vị trí – Transposition Ciphers A transposition cipher does not substitute one symbol for another, instead it changes the location of the symbols. A transposition cipher reorders symbols. a. Hệ mật dịch chuyển không khóa - Keyless Transposition Ciphers b. Hệ mật dịch chuyển có khóa - Keyed Transposition Ciphers c. Hệ mật dịch chuyển kết hợp - Combination of Two Approaches 2.2. Một số hệ mật mã khóa đối xứng cổ điển • Đây là hệ mật mã cổ điển đơn giản, được sử dụng từ lâu. • Hệ mật mã dựa trên sự hoán vị của các ký tự trong bản rõ để có được bản mật. • Có 2 phương pháp: – Chia cột – ghép hàng – Chia hàng – ghép cột 44  a. Hệ mật dịch chuyển không khóa 3/21/2016  23  2.2. Một số hệ mật mã khóa đối xứng cổ điển • A good example of a keyless cipher using the first method is the rail fence cipher. • The plaintext is arranged in 2 lines as a zigzag pattern. • The ciphertext is created by reading the pattern row by row. 45  a. Hệ mật dịch chuyển không khóa 2.2. Một số hệ mật mã khóa đối xứng cổ điển • Alice and Bob can agree on the number of columns and use the second method. • Alice writes the same plaintext, row by row, in a table of four columns. 46  a. Hệ mật dịch chuyển không khóa 3/21/2016  24  2.2. Một số hệ mật mã khóa đối xứng cổ điển • The keyless ciphers permute the characters by using writing plaintext in one way and reading it in another way. • The permutation is done on the whole plaintext to create the whole ciphertext. • Another method is to divide the plaintext into groups of predetermined size, called blocks, and then use a key to permute the characters in each block separately. => Keyed transposition ciphers 47  b. Hệ mật dịch chuyển có khóa 2.2. Một số hệ mật mã khóa đối xứng cổ điển 48  b. Hệ mật dịch chuyển có khóa Alice needs to send the message “Enemy attacks tonight” to Bob. The key used for encryption and decryption is a permutation key. Key 3/21/2016  25  2.2. Một số hệ mật mã khóa đối xứng cổ điển 49  c. Hệ mật dịch chuyển kết hợp 2.2. Một số hệ mật mã khóa đối xứng cổ điển 50  c. Hệ mật dịch chuyển kết hợp 3/21/2016  26  2.2. Một số hệ mật mã khóa đối xứng cổ điển 51  Biểu diễn hệ mật dịch chuyển bằng ma trận 2.3. Sơ lược hệ mật mã dòng và mã khối • Các hệ mật mã khóa đối xứng có thể được phân loại thành 2 loại hệ mật: Hệ mật mã dòng và hệ mật mã khối 52  3/21/2016  27  2.3. Sơ lược hệ mật mã dòng và mã khối 53  2.3.1. Hệ mật mã dòng Với bản rõ dòng P, bản mật dòng C và khóa dòng K, ta có: Ví dụ 2.3. Sơ lược hệ mật mã dòng và mã khối 54  2.3.1. Hệ mật mã dòng Hệ mật mã cộng có phải là hệ mật dòng hay không? Hệ mật mã thay thế đơn ký tự có phải là hệ mật dòng hay không? 3/21/2016  28  2.3. Sơ lược hệ mật mã dòng và mã khối 55  2.3.2. Hệ mật mã khối A group of plaintext symbols of size m (m > 1) are encrypted together creating a group of ciphertext of the same size 2.3. Sơ lược hệ mật mã dòng và mã khối • Hill ciphers are block ciphers. • A block of plaintext, of size 2 or more is encrypted together using a single key (a matrix). • In these ciphers, the value of each character in the ciphertext depends on all the values of the characters in the plaintext. • The key is made of m × m values, it is considered as a single key. 56  2.3.2. Hệ mật mã khối 3/21/2016  29  2.3. Sơ lược hệ mật mã dòng và mã khối • In practice, blocks of plaintext are encrypted individually, but they use a stream of keys to encrypt the whole message block by block. • In other words, the cipher is a block cipher when looking at the individual blocks, but it is a stream cipher when looking at the whole message considering each block as a single unit. 57  2.3.1. 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 58  Nhóm Vành Trường 3/21/2016  30  2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại • A group (G) is a set of elements with a binary operation (•) that satisfies four properties: – Closure – Associativity – Existence of identity – Existence of inverse 59  2.4.1. Nhóm 2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại • A commutative group satisfies an extra property, commutatively or abelian group – Closure – Commutativity – Associativity – Existence of identity – Existence of inverse 60  2.4.1. Nhóm 3/21/2016  31  2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại • A commutative group satisfies an extra property, commutatively or abelian group – Closure: ܽ, ܾ ∈ ܩ ݐ݄ì ܿ ൌ a ሺ•) b ∈ ܩ – Commutatively: ܽ ∙ ܾ ൌ ܾ ∙ ܽ – Associativity: cሺ•)ሺܽ ∙ ܾሻ ൌ cሺ•)ܽ ∙ ܾ – Existence of identity: ܽ ∙ ݁ ൌ ݁ ∙ ܽ ൌ ܽ – Existence of inverse: ܽ ∙ ܽᇱ ൌ ܽᇱ ∙ ܽ ൌ ݁ 61  2.4.1. Nhóm 2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại • A very interesting group is the permutation group. The set is the set of all permutations, and the operation is composition: applying one permutation after another. 62  2.4.1. Nhóm 3/21/2016  32  2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại • A very interesting group is the permutation group. The set is the set of all permutations, and the operation is composition: applying one permutation after another. 63  2.4.1. Nhóm 2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại • Finite Group 64  2.4.1. Nhóm Nhóm hữu hạn là nhóm có số hữu hạn các phần tử • Order of a Group Cấp của nhóm là số phần tử của nhóm đó • Subgroup Nhóm con của một nhóm G là nhóm bao gồm các phần tử thuộc G đồng thời thỏa mãn phép toán đóng trong G 3/21/2016  33  2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại • Tính chất của subgroup 65  2.4.1. Nhóm 2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại • Nhóm con Cyclic là nhóm được tạo ra bởi cấp số của 1 phần tử nhóm gốc • Cấp số của phần tử là số lần thực hiện lặp lại phép toán đối với phần tử đó 66  2.4.1. Nhóm Cyclic Subgroups 3/21/2016  34  2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại • Nhóm G là nhóm Cyclic khi G chính là nhóm con Cyclic 67  2.4.1. Nhóm Cyclic Group 2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 68  2.4.1. Nhóm Lagrange’s Theorem Assume that G is a group, and H is a subgroup of G. If the order of G and H are |G| and |H|, respectively, then, based on this theorem, |H| divides |G|. Order of an Element The order of an element, ord(a), is the smallest integer that ܽ௡ ൌ ݁. 3/21/2016  35  2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 69  2.4.2. Vành A ring, R = , is an algebraic structure with two operations. The second operation must be distributed over the first ܽ∎ ܾ ∘ ܿ ൌ ሺܽ∎ܾሻ ∘ ሺܽ∎ܿሻ  ሺܽ ∘ ܾሻ∎ܿ ൌ ሺܽ∎ܿሻ ∘ ሺܾ∎ܿሻ  2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 70  2.4.2. Vành The second operation must be distributed over the first ܽ∎ ܾ ∘ ܿ ൌ ሺܽ∎ܾሻ ∘ ሺܽ∎ܿሻ  ሺܽ ∘ ܾሻ∎ܿ ൌ ሺܽ∎ܿሻ ∘ ሺܾ∎ܿሻ  The set Z with two operations, addition and multiplication, is a commutative ring. We show it by R = . Addition satisfies all of the five properties; multiplication satisfies only three properties. 3/21/2016  36  2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 71  2.4.3. Trường A field, denoted by F = is a commutative ring in which the second operation satisfies all five properties defined for the first operation except that the identity of the first operation has no inverse. 2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 72  2.4.3. Trường • A finite field, a field with a finite number of elements, are very important structures in cryptography. • Galois showed that for a field to be finite, the number of elements should be ݌௡, where p is a prime and n is a positive integer. A Galois field, GF(pn), is a finite field with pn elements. 3/21/2016  37  2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 73  2.4.3. Trường A Galois field, GF(pn), is a finite field with pn elements. When n = 1, we have GF(p) field. This field can be the set Zp, {0, 1, , p − 1}, with two arithmetic operations. A very common field in this category is GF(2) with the set {0, 1} and two operations, addition and multiplication. a 0 1 a 0 1 -a 0 1 a-1 N/A 1 2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 74  2.4.3. Trường GF(2n) In cryptography, we often need to use four operations  (addition, subtraction, multiplication, and division).  In  other  words,  we  need  to  use  fields.  We  can  work  in  GF(2n) and uses a set of 2n elements. The elements  in  this set are n‐bit words.   4.2.1   Polynomials  4.2.2   Using A Generator  4.2.3   Summary  3/21/2016  38  2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 75  2.4.3. Trường GF(2n) Let us define a GF(22) field in which the set has four 2-bit words: {00, 01, 10, 11}. We can redefine addition and multiplication for this field in such a way that all properties of these operations are satisfied. An example of GF(22) field 2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 76  2.4.3. Trường GF(2n) Polynomials  A polynomial of degree n − 1 is an expression of the form where xi is called the ith term and ai is called coefficient of the ith term. 3/21/2016  39  2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 77  2.4.3. Trường GF(2n) How we can represent the 8-bit word (10011001) using a polynomials? Polynomials  2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 78  2.4.3. Trường GF(2n) Polynomials  To find the 8-bit word related to the polynomial x5 + x2 + x, we first supply the omitted terms. Since n = 8, it means the polynomial is of degree 7. This is related to the 8-bit word 00100110. The expanded polynomial is 3/21/2016  40  2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 79  2.4.3. Trường GF(2n) Polynomials  Polynomials representing n-bit words use two fields: GF(2) and GF(2n) Lưu ý:   2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 80  2.4.3. Trường GF(2n) Modulus For the sets of polynomials in GF(2n), a group of polynomials of degree n is defined as the modulus. Such polynomials are referred to as irreducible polynomials. 3/21/2016  41  2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 81  2.4.3. Trường GF(2n) Modulus Addition and subtraction operations on polynomials are the same operation. Lưu ý:   2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 82  2.4.3. Trường GF(2n) Modulus Let us do (x5 + x2 + x)  (x3 + x2 + 1) in GF(28). We use the symbol  to show that we mean polynomial addition. The following shows the procedure: 3/21/2016  42  2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 83  2.4.3. Trường GF(2n) Modulus There is also another short cut. Because the addition in GF(2) means the exclusive-or (XOR) operation. So we can exclusive-or the two words, bits by bits, to get the result. In the previous example, x5 + x2 + x is 00100110 and x3 + x2 + 1 is 00001101. The result is 00101011 or in polynomial notation x5 + x3 + x + 1. 2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 84  2.4.3. Trường GF(2n) Multiplication 1. The coefficient multiplication is done in GF(2). 3. The multiplication may create terms with degree more than n − 1, which means the result needs to be reduced using a modulus polynomial. 2. The multiplying xi by xj results in xi+j 3/21/2016  43  2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 85  2.4.3. Trường GF(2n) Generator Sometimes it is easier to define the elements of the GF(2n) field using a generator. 2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 86  2.4.3. Trường GF(2n) Generator Generate the elements of the field GF(24) using the irreducible polynomial ƒ(x) = x4 + x + 1. 3/21/2016  44  2.4. Cơ sở toán học cho hệ mật mã khóa đối xứng hiện đại 87  2.4.3. Trường GF(2n) The finite field GF(2n) can be used to define four operations of addition, subtraction, multiplication and division over n-bit words. The only restriction is that division by zero is not defined. Summary