Bài giảng Lý thuyết mật mã - Chương 4: Hệ mật AES - Đỗ Trọng Tuấn

 TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
 VIỆN ĐIỆN TỬ - VIỄN THÔNG 
 BỘ MÔN ĐIỆN TỬ HÀNG KHÔNG VŨ TRỤ
 Môn học:
 LÝ THUYẾT MẬT MÃ
 Giảng viên: PGS.TS. Đỗ Trọng Tuấn
 Email: dotrongtuan@gmail.com
4/27/2016 1
 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
 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ật AES
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/27/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
 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 4. Hệ mật AES
4.1. Giới thiệu sơ lược hệ mật AES
4.2. Cấu trúc hệ mật AES
4.3. Mở rộng bộ khóa hệ mật AES
4.4. Cách triển khai hệ mật AES
4.5. Thám mã hệ mật AES
 6
 4.1. Sơ lược hệ mật AES
The Advanced Encryption Standard (AES) is a symmetric-key
block cipher published by the National Institute of Standards
and Technology (NIST) in December 2001.
In February 2001, NIST announced that a draft of
the Federal Information Processing Standard (FIPS)
was available for public review and comment. Finally,
AES was published as FIPS 197 in the Federal
Register in December 2001.
 7
 4.1. Sơ lược hệ mật AES
The Advanced Encryption Standard (AES) is a symmetric-key
block cipher published by the National Institute of Standards
and Technology (NIST) in December 2001.
The criteria defined by NIST for selecting AES fall
into three areas:
1. Security
2. Cost
3. Implementation.
 8
 4.2. Cấu trúc hệ mật AES
AES is a non-Feistel cipher that encrypts and decrypts a data
block of 128 bits. It uses 10, 12, or 14 rounds. The key size,
which can be 128, 192, or 256 bits, depends on the number of
rounds.
 AES has defined three versions, with 10, 12, and 14 
 rounds.
Each version uses a different cipher key size (128, 192, 
 or 256), but the round keys are always 128 bits.
 9
 4.2. Cấu trúc hệ mật AES
General design of AES encryption cipher
 10
4.2. Cấu trúc hệ mật AES
 Data units used in AES
 11
4.2. Cấu trúc hệ mật AES
 Data units used in AES
 12
4.2. Cấu trúc hệ mật AES
 Data units used in AES
 13
 4.2. Cấu trúc hệ mật AES
Block-to-state and state-to-block transformation
 14
 4.2. Cấu trúc hệ mật AES
Structure of each round at 
the encryption site
 15
 4.2. Cấu trúc hệ mật AES
To provide security, AES
uses four types of
transformations:
substitution, permutation,
mixing, and key-adding.
 16
 4.2. Cấu trúc hệ mật AES
AES, like DES, uses substitution. AES uses two
invertible transformations.
SubBytes
The first transformation, SubBytes, is used at the
encryption site. To substitute a byte, we interpret the
byte as two hexadecimal digits.
The SubBytes operation involves 16 independent byte-
 to-byte transformations.
 17
4.2. Cấu trúc hệ mật AES
 18
 4.2. Cấu trúc hệ mật AES
SubBytes table
 19
 4.2. Cấu trúc hệ mật AES
invSubBytes
table
 20
 4.2. Cấu trúc hệ mật AES
This figure shows how a state is transformed using the SubBytes
transformation. The figure also shows that the InvSubBytes
transformation creates the original one. Note that if the two bytes
have the same values, their transformation is also the same.
 21
 4.2. Cấu trúc hệ mật AES
Transformation Using the GF(28) Field
AES also defines the transformation algebraically using the
GF(28) field with the irreducible polynomials
(x8 + x4 + x3+ x + 1).
 The SubBytes and InvSubBytes transformations are 
 inverses of each other.
 22
 4.2. Cấu trúc hệ mật AES
SubBytes and InvSubBytes processes 
 Constant matrix 
 X
 23
4.2. Cấu trúc hệ mật AES
 24
 4.2. Cấu trúc hệ mật AES
Another transformation found in a round is shifting, which permutes
the bytes.
ShiftRows
In the encryption, the transformation is called ShiftRows.
 ShiftRows transformation = Permutation
 25
 4.2. Cấu trúc hệ mật AES
InvShiftRows
In the decryption, the transformation is called InvShiftRows and the
shifting is to the right.
 26
 4.2. Cấu trúc hệ mật AES
This figure shows how a state is transformed using ShiftRows
transformation. The figure also shows that InvShiftRows
transformation creates the original state.
 ShiftRows transformation example
 27
 4.2. Cấu trúc hệ mật AES
 Mixing
We need an interbyte transformation that changes the bits inside
a byte, based on the bits inside the neighboring bytes. We need to
mix bytes to provide diffusion at the bit level.
 Mixing bytes using matrix multiplication
 28
 4.2. Cấu trúc hệ mật AES
Mixing
 Constant matrices used by MixColumns and InvMixColumns
 29
 4.2. Cấu trúc hệ mật AES
MixColumns
The MixColumns transformation operates at the column
level; it transforms each column of the state to a new
column.
 MixColumns transformation
 30
 4.2. Cấu trúc hệ mật AES
InvMixColumns
The InvMixColumns transformation is basically the
same as the MixColumns transformation.
 The MixColumns and InvMixColumns transformations 
 are inverses of each other.
 31
4.2. Cấu trúc hệ mật AES
 32
 4.2. Cấu trúc hệ mật AES
Figure below shows how a state is transformed using the MixColumns
transformation. The figure also shows that the InvMixColumns transformation
creates the original one.
 The MixColumns transformation example
 33
 4.2. Cấu trúc hệ mật AES
 Key Adding
AddRoundKey
• AddRoundKey proceeds one column at a time.
• AddRoundKey adds a round key word with each state
 column matrix
• The operation in AddRoundKey is matrix addition.
 The AddRoundKey transformation is the inverse of 
 itself.
 34
4.2. Cấu trúc hệ mật AES
 AddRoundKey transformation
 35
 4.3. Mở rộng bộ khóa hệ mật AES
KEY EXPANSION
 To create round keys for each round, AES uses a key-
 expansion process.
 If the number of rounds is Nr , the key-expansion routine
 creates Nr + 1 128-bit round keys from one single 128-bit
 cipher key.
• Key Expansion in AES-128
• Key Expansion in AES-192 and AES-256
• Key-Expansion Analysis
The key-expansion mechanism in AES has been designed to
provide several features that thwart the cryptanalyst.
 36
 4.3. Mở rộng bộ khóa hệ mật AES
To create round keys for each round, AES uses a key-expansion
process. If the number of rounds is Nr , the key-expansion
routine creates Nr + 1 128-bit round keys from one single 128-
bit cipher key.
 37
 4.3. Mở rộng bộ khóa hệ mật AES
Key Expansion in AES-128
 38
 4.3. Mở rộng bộ khóa hệ mật AES
Key Expansion in AES-128
 39
 4.3. Mở rộng bộ khóa hệ mật AES
Key Expansion in AES-128
 40
 4.3. Mở rộng bộ khóa hệ mật AES
Key Expansion in AES-128
 41
 4.3. Mở rộng bộ khóa hệ mật AES
 Key Expansion in AES-128
The key-expansion routine can either use the above table when
calculating the words or use the GF(28) field to calculate the
leftmost byte dynamically, as shown below (prime is the
irreducible polynomial):
 42
 4.3. Mở rộng bộ khóa hệ mật AES
Key Expansion in AES-128
 43
 4.3. Mở rộng bộ khóa hệ mật AES
Key Expansion in AES-128
Each round key in AES depends on the previous round key. The
dependency, however, is nonlinear because of SubWord
transformation. The addition of the round constants also
guarantees that each round key will be different from the previous
one.
 44
 4.3. Mở rộng bộ khóa hệ mật AES
 Ví dụ
This table shows how the keys for each round are calculated
assuming that the 128-bit cipher key agreed upon by Alice and
Bob is (24 75 A2 B3 34 75 56 88 31 E2 12 00 13 AA 54 87)16.
 45
 4.3. Mở rộng bộ khóa hệ mật AES
 Ví dụ
The concept of weak keys, as we discussed for DES in Chapter 3, does not
apply to AES. Assume that all bits in the cipher key are 0s. The following
shows the words for some rounds:
 The words in the pre-round and the first round are all the same. In the second
 round, the first word matches with the third; the second word matches with the
 fourth. However, after the second round the pattern disappears; every word is
 different.
 46
 4.3. Mở rộng bộ khóa hệ mật AES
Key-expansion algorithms in the AES-192 and AES-256
versions are very similar to the key expansion algorithm in
AES-128, with the following differences:
 47
 4.4. Cách triển khai hệ mật AES
• AES uses four types of transformations for
 encryption and decryption.
• In the standard, the encryption algorithm is referred
 to as the cipher and the decryption algorithm as the
 inverse cipher.
 - Original Design
 - Alternative Design
 48
 4.4. Cách triển khai hệ mật AES
Original Design
Ciphers and 
inverse ciphers of 
the original 
design
 49
4.4. Cách triển khai hệ mật AES
 50
 4.4. Cách triển khai hệ mật AES
Alternative Design
• In this version, the transformation in the reverse cipher are
 rearranged to make the order of transformations the same in the
 cipher and reverse cipher.
• In this design, invertibility is provided for a pair of
 transformations, not for each single transformation
 51
 4.4. Cách triển khai hệ mật AES
 Alternative Design
Cipher and reverse 
cipher in alternate 
design
 52
 4.4. Cách triển khai hệ mật AES
Alternative Design
Changing Key-Expansion Algorithm
Instead of using InvRoundKey transformation in the reverse
cipher, the key-expansion algorithm can be changed to create a
different set of round keys for the inverse cipher.
Note that: 
- The round key for the pre-round operation and the last round 
should not be changed.
- The round keys for round 1 to 9 need to be multiplied by the 
constant matrix
 53
 4.4. Cách triển khai hệ mật AES
Alternative Design
 Ví dụ
The following shows the ciphertext block created from a plaintext
block using a randomly selected cipher key.
 54
4.4. Cách triển khai hệ mật AES
 55
4.4. Cách triển khai hệ mật AES
 56
4.4. Cách triển khai hệ mật AES
 57
 4.4. Cách triển khai hệ mật AES
 This figure shows the state entries in one round, round 7.
 States in a single round
One may be curious to see the result of encryption when the
plaintext is made of all 0s.
 58
4.4. Cách triển khai hệ mật AES
 The avalanche effect
 59
 4.4. Cách triển khai hệ mật AES
The following shows the effect of using a cipher key in which all
bits are 0s.
 60
 4.5. Thám mã hệ mật AES
AES was designed after DES. Most of the known attacks on DES
were already tested on AES.
Brute-Force Attack
AES is definitely more secure than DES due to the larger-size key.
Statistical Attacks
Numerous tests have failed to do statistical analysis of the
ciphertext.
Differential and Linear Attacks
There are no differential and linear attacks on AES as yet.
 61
 4.5. Thám mã hệ mật AES
Statistical Attacks
Numerous tests have failed to do statistical analysis of
the ciphertext.
Differential and Linear Attacks
There are no differential and linear attacks on AES as
yet.
 62