1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
BỘ MÔN ANH NINH HỆ THỐNG THÔNG TIN
HỆ MÃ HÓA AES
Giảng viên:
PGS.TS Trịnh Nhật Tiến
Thực hiện:
Nguyễn Thị Dung
Hà Nội, 2013
MỤC LỤC
1. Giới thiệu chung
Vào những năm 1990, nhận thấy nguy cơ của mã hóa DES là kích thước khóa ngắn, nó
có thể bị phá mã trong tương lai gần nên cục tiêu chuẩn quốc gia Hoa Kỳ đã kêu gọi xây
dựng một phương pháp mã hóa mới. Cuối cùng một thuật toán có tên là Rijndael được
chọn và đổi tên thành Andvanced Encryption Standard hay AES.
Chuẩn mã hóa dữ liệu cao cấp AES là một hệ mã hóa khóa bí mật có tên là Rijndael do
hai nhà mật mã học người Bỉ là Joan Deamen và Vincent Rijmen đưa ra và trở thành
chuẩn từ năm 2000. Chuẩn mã hóa AES cho phép xử lý các khối dữ liệu input có kích
thước 128 bit sử dụng các khóa có độ dài 128, 192 hoặc 256 bit. Hệ mã hóa Rijndael
được thiết kế để có thể làm việc với các khóa và khối dữ liệu có độ dài lớn hơn, tuy
nhiên, khi được chọn là chuẩn do ủy ban tiêu chuẩn của Hoa kỳ đưa ra vào năm 2001, nó
được quy định chỉ làm việc với khối dữ liệu 128 bit và các khóa có độ dài 128, 192, hoặc
256 bit (do đó còn đặt cho nó các tên AES-128, AES-192, AES-256 tương ứng với độ dài
khóa sử dụng)
1.1. Ưu điểm của AES
• AES đã được chính phủ Hoa Kỳ tuyên bố là có độ an toàn cao, và được sử dụng trong
thông tin mật.
• AES sử dụng bảng tra và phép thế có tính chất phi tuyến mạnh dẫn đến mức độ phân
tán thông tin phức tạp làm tăng độ an toàn cho thuật toán
• AES có mô tả toán học đơn giản, cấu trúc rõ ràng đơn giản

Tất cả các giá trị byte sử dụng trong thuật toán AES đều được biểu diễn dưới dạng một
dãy các bit 0 và 1 theo định dạng {b
7
, b
6
, b
5
, b
4,
b
3
, b
2,
b
1
, b
0
}. Các byte này sau được hiểu
là phần tử trên trường hữu hạn bằng cách sử dụng biểu diễn thành dạng đa thức:
b
7
x
7
+ b
6
x
6
+ b
5
x

1
, , in
15
đầu vào vào mảng trạng thái s theo công thức sau:
s[r,c]=in[r+4c], với 0≤c,r≤4
Vào cuối quá trình mã hóa hay giải mã, mảng trạng thái sẽ được sao chéo vào mảng byte
đầu ra theo công thức out
0
, out
1
, …,out
15
out[r+4c]=s[r,c], với 0≤c,r≤4
2.2. Cơ sở toán học của AES
AES sử dụng trường hữu hạn Galois GF(2
8
) để thực hiện các phép toán: phép cộng, phép
trừ, phép nhân, và phép chia. Các phần tử của trường GF(2
8
) được xem như là các đa
thức
2.2.1. Phép cộng
Phép cộng ở đây được hiểu là phép XOR trên hai bit tương ứng trong byte và có ký hiệu
là ⊕
2.2.2. Phép nhân
Phép nhân trên trường GF(2
8
) tương ứng với phép nhân thông thường của hai đa thức
đem chia lấy dư (modulo) cho một đa thức tối giản bậc 8. Trong thuật toán AES, đa thức
tối giản được chọn là:

d(x) = d
3
X
3
+d
2
X
2
+d
1
X+d0, trong đó:
d
0
= (a
0
●b
0
) ⊕ (a
3
●b
1
) ⊕ (a
2
●b
2
) ⊕ (a
1
●b
3
)

0
●b
2
) ⊕ (a
3
●b
3
)
d
3
= (a
3
●b
0
) ⊕ (a
2
●b
1
) ⊕ (a
1
●b
2
) ⊕ (a
0
●b
3
)
5
3. Thuật toán mã hóa
Thuật toán AES được thực hiện bởi tuần tự gồm nhiều bước biến đổi, kết quả đầu ra của

tác trên mỗi byte một cách độc lập
InvMixColumns() Hàm biến đổi được sử dụng trong thuật toán giải mã, là hàm ngược
của hàm MixColumns()
InvShiftRows() Hàm biến đổi được sử dụng trong thuật toán giải mã, là hàm ngược
của hàm ShiftRows()
Inv SubBytes() Hàm biến đổi được sử dụng trong thuật toán giải mã, là hàm ngược
của hàm SubBytes()
3.1. Quá trình mã hóa
Bắt đầu thuật toán, bản rõ được sao chép vào mảng trạng thái sử dụng các quy ước được
mô tả ở phần trên. Sau khi cộng với khóa RoundKey, mảng trạng thái khởi tạo được biến
đổi bằng cách thực hiện một hàm vòng Nr lần (10, 12 hoặc 14 phụ thuộc vào độ dài của
khóa) trong đó lần cuối cùng thực hiện khác với các lần trước đó. Trạng thái sau lần lặp
cuối cùng sẽ được chuyển thành output của thuật toán
Hàm vòng được tham số hóa bằng cách sử dụng một dãy các khóa được biểu diễn như là
mảng một chiều của các word 4 byte được sinh ra từ thử tục sinh khóa (Key Expansion)
Tất cả các vong đều thực hiện công việc giống nhau dựa trên 4 hàm theo thứ tự
SubBytes(), ShiftRows(), MixColumns(), và AddRoundKey() trừ vòng cuối cùng bỏ qua
việc thực hiện hàm MixColumns()
Thuật toán được mô tả chi tiết qua đoạn mã giả sau:
Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])
begin
byte state[4,Nb]
state=in
AddRoundKey(state, w[0,Nb-1])
for round=1 step 1 to Nr-1
SubBytes(state)
ShiftRows(state)
MixColumns(state)
AddRoundKey(state, w[round*Nb,(round+1)*Nb-1])
8

của byte b tương ứng và c
i
là bit thứ I của byte c với giá trị {63} hay {01100011}
Hình dưới đây minh họa kết quả của việc áp dụng hàm biến đổi SubBytes() đối với mảng
trạng thái
3.1.2. Hàm ShiftRows()
Trong hàm này các byte trong ba hàng cuối của mảng trạng thái sẽ được dịch vòng với số
lần dịch (hay số byte bị dịch) khác nhau. Hàng đầu tiên r=0 không bị dịch. Cụ thể hàm
này sẽ tiến hành bước đổi sau:
9
S’
rc
= S
r,(c+shift(r,Nb))modNb
(Nb=4) trong đó giá trị dịch shift(r,Nb) phụ thuộc vào số
hàng r như sau:
shift(1,4)=1, shift(2,4)=2, shift(3,4)=3
Thao tác này sẽ chuyển các byte tới các vị trí thấp hơn trong các hàng, trong khi các byte
thấp nhất sẽ được chuyển lên đầu hàng. Tất cả các mô tả trên có thể minh họa qua hình vẽ
sau:
3.1.3. Hàm MixColumns()
Hàm này làm việc trên các cột của mảng trạng thái, nó coi mỗi cột của mảng trạng thái
như là một đa thức gồm 4 hạng tử. Các cột sẽ được xem như là các đa thức trên GF(2
8
) và
được nhân trên modulo x
4
+1 với một đa thức cố định a(x):
a(x) = {03}x
3

2,c
= s
0,c
⊕ s
1,c
⊕ ({02}●s
2,c
) ⊕ ({03}●s
3,c
)
s’
3,c
= ({03}●s
0,c
) ⊕ s
1,c
⊕ s
2,c
⊕ ({02}●s
3,c
)
Có thể minh họa việc thực hiện hàm này bằng hình vẽ sau:
3.1.4. Hàm AddRoundKey()
Trong hàm này, một khóa vòng (Round Key) sẽ được cộng vào mảng trạng thái bằng một
thao tác XOR bit. Mỗi khóa vòng gồm Nb word được sinh ra bởi thủ tục sinh khóa. Các
word này sẽ được cộng vào mỗi cột của mảng trạng thái như sau:
11
[s’
0,c
, s’

] trong đó 0≤i<Nb(Nr+1).
Sự mở rộng khóa thành dãy khóa được mô tả qua đoạn mã giả sau:
KeyExpansion(byte key[4*Nb], word w[Nb*(Nr+1), Nk])
begin
word temp
i=0
while(i<Nk)
w[i] = word(key[4*i], key[4*i] +1, key[4*i] +2, key[4*i]+3)
12
i = i +1
end while
i = Nk
while (i< Nb*(Nr+1))
temp = w[i-1]
if(i mod Nk = 0)
temp = SubWord(RotWord(temp)) xor Rcon[i/Nk]
else if (Nk>6 and I mod Nk = 4)
temp = SubWord(temp)
end if
w[i] = w[i-Nk] xor temp
i = i+1
end while
end
SubWord() là hàm nhận một input 4 byte và áp dụng bảng thế S-box lên input để nhận
được một word output. Hàm RotWord() nhận một word input [a
0
, a
1
, a
2

3.2. Quá trình giải mã
Quá trình giải mã khá giống với quá trình mã hóa về mặt cấu trúc nhưng 4 hàm cơ bản sử
dụng là các hàm ngược của các hàm trong thuật toán giải mã. Dưới đây là đoạn mã giả
cho thuật toán giải mã sau:
InvCipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])
begin
byte state[4,Nb]
state = in
AddRoundKey(state, w[Nr*Nb,(Nr+1)*Nb-1)])
for round = Nr -1 step-1 downto 1
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state,w[round*Nb,(round+1)*Nb-1])
InvMixColumns(state)
end for
InvShiftRows(state)
InvSubBytes(state)
AddRoundKey(state, w[0,Nb-1])
out = state
end
3.2.1. Hàm InvShiftRow()
Hàm này là hàm ngược của hàm ShiftRows(). Các byte của ba hàng cuối của mảng trạng
thái sẽ được dịch vòng với vị trí dịch khác nhau. Hàng đầu tiên không bị dịch, ba hàng
cuối bị dịch đi Nb-shift(r,Nb) byte trong đó giá trị shift(r,Nb) phụ thuộc vào số hàng
Cụ thể hàm này tiến hành xử lý như sau:
s’
r,(c+shift(r,Nb))modNb
= s
r,c
0<r<4, 0≤c<Nb (Nb=4)

trong đó 0≤c<Nb
Kết quả là bốn byte trong mỗi cột sẽ được thay thế theo công thức sau:
s’
0,c
= ({0e}●s
0,c
) ⊕ ({0b}●s
1,c
) ⊕ ({0d}●s
2,c
) ⊕ ({09}●s
3,c
)
s’
1,c
= ({09}●s
0,c
) ⊕ ({0e}●s
1,c
) ⊕ ({0b}●s
2,c
) ⊕ ({0d}●s
3,c
)
s’
2,c
= ({0d}●s
0,c
) ⊕ ({09}●s
1,c

mật mã dựa vào khóa tương đương hay các khóa có liên quan trở nên không khả thi.
Đối với phương pháp vi phân rút gọn, việc phân tích chủ yếu khai thác đặc tính tập trung
thành vùng của các vết vi phân trong một số phương pháp mã hóa. Trong thuật toán AES,
số lượng chu kỳ lớn hơn 6, không tồn tại phương pháp công phá mật mã nào hiệu quả
hơn phương pháp thử sai. Tính chất phức tạp của biểu thức S-box cùng với hiệu ứng
khuếch tán giúp cho thuật toán không thể bị phân tích bằng phương pháp nội suy.
Đối với phương pháp thử sai với chiều dài khóa 256-bit tương ứng 2
256
hay 1.2 x 10
77
khả
năng có thể xảy ra. Thậm chí nếu sử dụng một trong những siêu máy tính mạnh nhất
hiện nay là Roadrunner 54 của IBM để xử lý thì cũng cần 3.5 x 10
54
năm để kiểm tra tất
cả khả năng (Roadrunner có khả năng thực hiện 1.042 triệu tỉ phép tính / giây).
4.2. Đánh giá thuật toán
• Thuật toán AES thích hợp cho việc triển khai trên nhiều hệ thống khác nhau, không
chỉ trên các máy tính cá nhân, mà cả trên các hệ thống thẻ thông minh.
• Tất cả các bước xử lý của việc mã hóa và giải mã đều được thiết kế thích hợp với cơ
chế xử lý song song nên AES càng chứng tỏ thế mạnh của mình trên các hệ thống
thiết bị mới.
• Do đặc tính của việc xử lý thao tác trên từng byte dữ liệu nên không có sự khác biệt
nào được đặt ra khi triển khai trên hệ thống big-endian hay little-endian.
17
• Độ lớn của khóa mã có thể thay đổi linh hoạt từ 128 đến 256 bit. Số lượng chu kỳ có
thể được thay đổi tùy thuộc vào yêu cầu riêng được đặt ra cho từng ứng dụng và hệ
thống cụ thể.
Phụ lục A: Ví dụ về mở rộng khóa 128 bit
Giả sử ta có khóa mã hóa sau: