Bài giảng Lý thuyết mật mã - Chương 2: Mật mã khóa đối xứng - Đỗ Trọng Tuấn

i xứng
 cổ điển
 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”.
 31
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
 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)
 32
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
 b. Hệ mật thay thế đa ký tự - Polyalphabetic
Hãy so sánh Vigenere cipher với Additive Cipher?
A Vigenere cipher as a combination of m additive ciphers
 33
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
 b. Hệ mật thay thế đa ký tự - Polyalphabetic
Hãy so sánh Vigenere cipher với Additive Cipher?
Ngược lại: the additive 
cipher is a special case 
of Vigenere cipher in 
which m = 1.
 34
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
 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
 35
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
 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
 36
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
 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.
 37
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
 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.
 38
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
 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
 39
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
 b. Hệ mật thay thế đa ký tự - Polyalphabetic
Hill Cipher
 40
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
 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
 41
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
 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
 42
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
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
 43
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
 a. Hệ mật dịch chuyển không khóa
• Đâ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
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
 a. Hệ mật dịch chuyển không khóa
• 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
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
 a. Hệ mật dịch chuyển không khóa
• 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
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
 b. Hệ mật dịch chuyển có khóa
• 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
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
 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
 48
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
c. Hệ mật dịch chuyển kết hợp
 49
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
c. Hệ mật dịch chuyển kết hợp
 50
 2.2. Một số hệ mật mã khóa đối xứng
 cổ điển
Biểu diễn hệ mật dịch chuyển bằng ma trận
 51
 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
 2.3. Sơ lược hệ mật mã dòng và mã 
 khối
 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ụ
 53
 2.3. Sơ lược hệ mật mã dòng và mã 
 khối
 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?
 54
 2.3. Sơ lược hệ mật mã dòng và mã 
 khối
 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
 55
 2.3. Sơ lược hệ mật mã dòng và mã 
 khối
 2.3.2. Hệ mật 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. Sơ lược hệ mật mã dòng và mã 
 khối
 2.3.1. Hệ mật 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.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
Nhóm Vành Trường
 58
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 2.4.1. Nhóm
• 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. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 2.4.1. Nhóm
• A commutative group satisfies an extra property,
 commutatively or abelian group
 – Closure
 – Commutativity
 – Associativity
 – Existence of identity
 – Existence of inverse
 60
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 2.4.1. Nhóm
• 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. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 2.4.1. Nhóm
• 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. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 2.4.1. Nhóm
• 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. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
2.4.1. Nhóm
• Finite Group
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
 64
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
2.4.1. Nhóm
• Tính chất của subgroup
 65
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
2.4.1. Nhóm
Cyclic Subgroups
• 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. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
2.4.1. Nhóm
Cyclic Group
• Nhóm G là nhóm Cyclic khi G chính là nhóm con Cyclic
 67
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 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
 = .
 68
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
2.4.2. Vành
A ring, R = , is an algebraic structure with two operations.
The second operation must be distributed over the first
 ∎  ∘  = (∎) ∘ (∎)
 ( ∘ )∎ = (∎) ∘ (∎)
 69
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 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.
 70
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 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.
 71
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 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.
 72
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 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
 73
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 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
 74
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 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 75
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 2.4.3. Trường GF(2n) Polynomials
A polynomial of degree n − 1 is an expression
of the form
 i th
where x is called the i term and ai is called coefficient
of the ith term.
 76
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 2.4.3. Trường GF(2n) Polynomials
How we can represent the 8-bit word (10011001)
using a polynomials?
 77
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 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.
The expanded polynomial is
 This is related to the 8-bit word 00100110.
 78
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 2.4.3. Trường GF(2n) Polynomials
Lưu ý: 
 Polynomials representing n-bit words 
 use two fields: GF(2) and GF(2n)
 79
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 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.
 80
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 2.4.3. Trường GF(2n) Modulus
Lưu ý: 
 Addition and subtraction operations on 
 polynomials are the same operation.
 81
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 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:
 82
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 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.
 83
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 2.4.3. Trường GF(2n) Multiplication
1. The coefficient multiplication is done in GF(2).
2. The multiplying xi by xj results in xi+j
3. The multiplication may create terms with degree more
than n − 1, which means the result needs to be reduced
using a modulus polynomial.
 84
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 2.4.3. Trường GF(2n) Generator
Sometimes it is easier to define the elements of the
GF(2n) field using a generator.
 85
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 2.4.3. Trường GF(2n) Generator
Generate the elements of the field GF(24) using the irreducible
polynomial ƒ(x) = x4 + x + 1.
 86
 2.4. Cơ sở toán học cho hệ mật mã 
 khóa đối xứng hiện đại
 2.4.3. Trường GF(2n) Summary
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.
 87