HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
------------------------------------

LƯU THỊ THÚY LINH

NGHIÊN CỨU MỘT VÀI KHÍA CẠNH VỀ ĐỘ AN TOÀN
CỦA AES

CHUYÊN NGÀNH: KỸ THUẬT VIỄN THÔNG
Mã số: 60.52.02.08

TÓM TẮT LUẬN VĂN THẠC SĨ

HÀ NỘI - NĂM 2013


Luận văn được hoàn thành tại:
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

Người hướng dẫn khoa học: GS-TS. NGUYỄN BÌNH

Phản biện 1:…………………………………………….

Phản biện 2:…………………………………………….

Luận văn sẽ được bảo vệ trước hội đồng chấm luận văn thạc sĩ tại
Học viện Công nghệ Bưu chính Viễn thông
Vào lúc:….giờ…..ngày….tháng….năm…..

Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu chính Viễn thông

Phạm vi nghiên cứu: Độ an toàn của AES với thám mã lượng sai.

4. Phƣơng pháp nghiên cứu
 Khảo sát các nghiên cứu, tài liệu liên quan để thu thập thông tin về cơ sở lý
thuyết từ nhiều nguồn (tài liệu, sách giáo trình, Internet…)


2

 Tổng hợp các kết quả nghiên cứu để lựa chọn cách tiếp cận phù hợp với nội
dung nghiên cứu

5. Kết cấu của luận văn
Ngoài phần mở đầu, kết luận và danh mục tài liệu tham khảo, luận văn được
kết cấu gồm 3 chương:
Chƣơng I: Trong chương này em giới thiệu chung về mật mã, một số loại mã ,
độ an toàn của mã
Chƣơng II: Chương này em nghiên cứu về chuẩn mã AES. Giới thiệu về
chuẩn mã AES, cơ sở toán học, quy trình mã hóa và giải mã AES.
Chƣơng III: Trong chương này em đã nghiên cứu độ an toàn của AES chống
lại thám mã lượng sai – một trong những tấn công mật mã mạnh nhất cho tới nay đối
với mã khối nói chung. Tập hợp kết quả nghiên cứu về phương pháp để xác định chặt
các xác suất lượng sai cực đại MEDP của các cấu trúc SPN nói chung và AES nói
riêng nhằm mục tiêu xem xét độ an toàn của chúng trước thám mã lượng sai. Gồm
các kết quả nghiên cứu của các tác giả: J.Daemen và V.Rijment; nhóm S.Park,
S.H.Sung, S.Lee và J.Lim; Keliher


3



Hệ mật mã gồm
 Hệ mật mã đối xứng (Mật mã cổ điển: hệ sử dụng chung một khóa bí mật
K cho cả quá trình mã hóa (Encryption) và giải mã (Decryption). Một số
đại diện: hệ mật thay thê, hệ mật hoán vị, DES, AES…
 Hệ mật mã bất đối xứng (Hệ mật mã công khai): Mật mã bất đối xứng sử
dụng khóa để mã hóa là KE và khóa để giải mã KDlà khác nhau. Các khóa
này tạo thành một cặp chuyển đổi ngược nhau và không có khóa nào có
thể suy ra từ khóa kia. Một số đại diện: RSA, DSA…

1.2 Một số loại mật mã
Đề tài luận văn : “Nghiên cứu một vài khía cạnh về độ an toàn của AES” nên ta
sẽ tìm hiểu một số loại mật mã trong hệ mật cổ điển


4

1.2.1 Mật mã thay thế
1.2.2 Mật mã hoán vị
1.2.3 Chuẩn mã dữ liệu (DES – Data Encryption Standard)
1.3 Độ an toàn của mã – Các loại thám mã
1.3.1 Độ an toàn của mã
Trong hệ mật cổ điển hệ mật hoán vị, thay thế không đảm bảo độ an toàn cần
thiết. Chính vì vậy ta phải xây dựng hệ mật tích là phương pháp kết hợp các phương
pháp hoán vị, thay thế mà điển hình là chuẩn mã dữ liệu DES (DES – Data
Encryption Standard) của Mỹ.
Hiện nay DES được xem là không đủ an toàn cho nhiều ứng dụng. Nguyên
nhân chủ yếu là độ dài 56 bit của khóa là quá nhỏ. Gần đây DES đã được thay thế
bằng hệ mật sáng giá là AES (Advanced Encryption Standard, hay Tiêu chuẩn Mã
hóa Tiên tiến.

giản nhất là tấn công tổng lực – tìm khóa vét cạn. Thứ hai: Phải đảm bảo an toàn
trước mọi tấn công. Với 2 tiêu chí đó, AES được chọn để thay thế cho DES.
Các tấn công có rất nhiều loạinhư: tấn công tổng lực - tìm khóa vét cạn, tấn
công dựa trên thông tin bản rõ, bản mã… Với từng hệ mật tấn công này có ưu thế còn
với những hệ mật khác có thể các tấn công khác có ưu thế (phụ thuộc vào đặc điểm
của từng hệ mật).


6

CHƢƠNG II: CHUẨN MÃ DỮ LIỆU TIÊN TIẾN AES
2.1 Giới thiệu về chuẩn mã dữ liệu tiên tiến AES

Chuẩn mã hóa dữ liệu tiên tiến AES (Advanced Encryption Standard) là một
hệ mã khóa bí mật có tên là Rijdael (do hai nhà mật mã học người Bỉ là Joan Daemen
và Vincent Rijmen đưa ra và trở thành chuẩn từ năm 2002) 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ã Rijdael được thiết kế để có thể làm việc với các khóa và các khối dữ liệu có độ
dài lớn hơn tuy nhiên khi được chọn là một chuẩn do Ủy ban tiêu chuẩn của Hoa Kỳ
đưa ra năm 2001, nó được qui định chỉ làm việc với các 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 các tên AES-128, AES-192,
AES-256 tương ứng với độ dài khóa sử dụng).
Cơ sở toán học của AES
Trong AES các phép toán cộng và nhân được thực hiện trên các byte trong

 

trường hữu hạn GF 28 .
Phép cộng
Phép nhân

phép biến đổi affine khả nghịch. Hộp S-box này cũng được chọn để tránh các điểm
bất động (fixed point).


8

Thao tác SubBytes tác động trên từng byte của trạng thái

2.1.2 Phép biến đổi ShiftRows
Các hàng được dịch vòng một số bước nhất định. Đối với AES, hàng đầu được giữ
nguyên. Mỗi byte của hàng thứ 2 được dịch vòng trái một vị trí. Tương tự, các hàng
thứ 3 và 4 được dịch vòng 2 và 3 vị trí. Do vậy, mỗi cột khối đầu ra của bước này sẽ
bao gồm các byte ở đủ 4 cột khối đầu vào. Đối với Rijndael với độ dài khối khác
nhau thì số vị trí dịch chuyển cũng khác nhau

Thao tác ShiftRows tác động trên từng dòng của trạng thái

2.2.3 Phép biến đổi MixColumns
Bốn byte trong từng cột được kết hợp lại theo một phép biến đổi tuyến tính khả
nghịch. Mỗi khối 4 byte đầu vào sẽ cho một khối 4 byte ở đầu ra với tính chất là
mỗi byte ở đầu vào đều ảnh hưởng tới cả 4 byte đầu ra. Cùng với bước
ShiftRows, MixColumns đã tạo ra tính chất khuyếch tán cho thuật toán. Mỗi cột

được xem như một đa thức trong trường hữu hạn và được nhân với đa thức
(modulo

). Vì thế, bước này có thể được xem là

phép nhân ma trận trong trường hữu hạn.


byte state[4,Nb]
state = in
AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1])
for round = Nr-1 step -1 down to 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

2.3.1 Phép biến đổi InvShifRows
InvShiftRows chính là phép biến đổi ngược của phép biến đổi ShiftRows

2.3.2. Phép biến đổi InvSuBytes
Phép biến đổi ngược của thao tác SubBytes, ký hiệu là InvSubBytes

2.3.3. Phép biến đổi InvMixColumns
InvMixColumns là biến đổi ngược của phép biến đổi MixColumns\

2.3.4. Thuật toán giải mã tương đương
Trong thuật toán giải mã được trình bày ở trên chúng ta thấy thự tự của các
hàm biến đổi được áp dụng khác so với thuật toán mã hóa trong khi dạng của danh
sách khóa cho cả 2 thuật toán vẫn giữ nguyên. Tuy vậy một số đặc điểm của AES cho
phép chúng ta có một thuật toán giải mã tương đương có thự tự áp dụng các hàm biến


Nhược điểm
 AES không đủ an toàn đối vớidạng tấn (side channel attack]).
 Cấu trúc toán họccủa AES có mô tả toán học khá đơn giản. Tuy điều này
chưa dẫn đến mối nguy hiểm nào nhưng một số nhà nghiên cứu sợ rằng sẽ có người
lợi dụng được cấu trúc này trong tương lai.


12

2.4.3 Ứng dụng của AES
 Hiện nay, AES được sử dụng phổ biến trên toàn thế giới để bảo vệ dữ liệu ở
các tổ chức ngân hàng, tài chính, chính phủ, thương mại điện tử, chữ ký điện tử;…

 Mã hóa AES được ứng dụng nhanh đối với cả phần cứng và phần mềm, và
chỉ yêu cầu một không gian lưu trữ nhỏ, lý tưởng để sử dụng cho việc mã hóa những
thiết bị cầm tay nhỏ như ổ USB flash, ổ đĩa CD;…
 Sử dụng như một hàm băm

 Xây dựng các hàm băm. Hàm băm Whilrpool là một ví dụ điển hình.
2.5 Kết luận chƣơng II
AES (viết tắt của từ tiếng Anh: Advanced Encryption Standard, hay Tiêu
chuẩn mã hóa tiên tiến) là một thuật toán mã hóa khối được chính phủ Hoa kỳ áp
dụng làm tiêu chuẩn mã hóa thay thế tiêu chuẩn tiền nhiệm DES.
AES là mã khối dạng SPN với mỗi hàm vòng gồm các phép biến đổi: SubByte,
ShiftRows, MixColumn, AddRoundKey


13

CHƢƠNG III: ĐỘ AN TOÀN CỦA AES VỚI THÁM MÃ

SPN nói chung và AES nói riêng, nhằm mục tiêu đánh giá độ an toàn của chúng
trước thám mã lượng sai.


14

3.2 Các khái niệm cơ sở
3.2.1 Cấu trúc SPN và mã khối AES

………
…….

Khóa vòng

Phép biến đổi tuyến tính

………
…….

Khóa vòng

2 vòng của cấu trúc SPN

AES là mã khối dạng SPN với mỗi hàm vòng gồm các phép biến đổi sau:


SubByte: Thay thế từng byte dữ liệu bằng 1 byte khác.





được định nghĩa là:

Trong đó E[] là kì vọng và k là một biến ngẫu nhiên phân bố đều trên không
gian khóa.
Tuy nhiên ta không thể tính toán trước giá trị này vì:
 Một là, với mọi giá trị sai khác đầu vào/đầu ra (đối với thám mã lượng sai, ta
phải mã hóa tất cả bản mã/bản rõ có thể
 Hai là các giá trị này còn phụ thuộc vào khóa chưa biết. Do đó người ta sử
dụng khái niệm giá trị trung bình EDP, và giả thiết rằng với hầu hết các giá trị của
khóa k thì:
Định nghĩa 3.2: Xác suất lượng sai cực đại p của S được định nghĩa bởi:
Xác suất lượng sai cực đại p cho S là một S-hộp mạnh cần phải đủ nhỏ đối với sai
khác đầu vào bất kỳ
Thực thể A tạo một chữ ký s vào ánh xạ M và được xác nhận bởi thực thể B.

b. Đặc trưng lượng sai
Để tính toán các giá trị EDP, cac nhà nghiên cứu phải sử dụng khái niệm đặc
trưng lượng sai
Định nghĩa 3.3: Một đặc trưng lượng sai cho các vòng 1…T là một (T+1)-bộ
sai khác N-bit

; Ta coi

và

tương ứng là

các sai khác đầu vào và đầu ra của vòng t
Định nghĩa 3.4: Gọi

ShiftRows chuyển các byte của mỗi cột tới 4 cột khác nhau, nên nó tạo ra tính khuếch
tán tối ưu. Do đó, định lý lan truyền 4-vòng chứng minh rằng số các S-hộp chủ động
trong một vệt lượng sai 4 vòng bị chặn dưới bởi 25.
S-hộp của AES đã được chọn sao xác suất lan truyền sai khác lớn nhất là
Điều này cho ta lan truyền lượng sai cực đại là

.

cho một vệt lượng sai 4 vòng

bất kỳ. Kết quả này đúng với mọi độ dài khối của Rijindael và là độc lập với giá trị
của các khóa vòng. Vì thế, không có các vệt 8 vòng với xác suất lan truyền lượng sai
lớn hơn

( tuy nhiên thực tế nó

, vì kích cỡ khối la 128 bit). Theo tác giả,

như vậy là đủ để chống lại các tấn công lượng sai. Để tạo hanh lang an toàn cho mã
khối Rijindael và Daemen đã chọn số vòng là 10 (với kích thước cỡ khóa 128 bít), 12
(với kích cỡ khóa 192 bit) và 14 vòng (với kích cỡ khóa là 256 bit)


17

3.3.2 Đánh giá độ an toàn bằng lý thuyết của S. Park, S.H.Sung, S.Lee và
J.Lim
Trước tiên tác giả đã chứng minh một số kết quả về độ an toàn của 2 vòng
mạng SPN với thám mã lượng sai:
3.3.2.1 Độ an toàn của mạng SPN trƣớc thám mã lƣợng sai


ii.

(Điều kiện cho

) mỗi byte của
là đầu vào của

iii.

(Điều kiện cho

đến từ các
;

khác nhau, ở đây
là đầu ra của

). Khi chúng ta xem xét mỗi một

là một tuyến tính, có điều kiện sau:

như


18

Định nghĩa 3.13 Với
bởi


Từ định lý 3.2 và bảng 3.1, ta có

Định lý 3.4: Khi

, cận trên của xác suất lượng sai cực đại 2 vòng của

AES là như sau:
Vì thế xác suất lượng sai cực đại của 2 vòng AES bị chặn bởi

.

Định lý 3.5: Xác suất lượng sai cho 4 vòng của AES bị chặn bởi

3.3.3 Xác định chính xác các cận an toàn của AES trước thám mã lượng sai
của Keliher
3.3.3.1 Phân tích chung MEDP với SPN 2 vòng
3.3.3.2 Các cận dƣới của MEDP với AES 2 vòng
Việc tính MEDP cho AES 2 vòng là tương đương vơi việc tính MEDP cho
SPN “được rút gọn” như mô tả trong Hình 3.2:


19

32 – bit LT

AES 2 vòng rút gọn
1. LowerBound = 0
2. For s = 1 to 56
3.


11.

End For

12.

If (Sum > LowerBound)

13.

LowerBond = Sum

14.
15.

16.

End If
End For
End For
Thuật toán xác định cận dƣới MEDP 2 vòng cho AES

Sử dụng thuật toán ở trên, cận dưới trên MELP 2 vòng cho AES là
. Vì cận trên tốt nhất là

, MELP 2 vòng bây giờ

được biết gần chính xác. Cận dưới đối với MEDP 2 vòng bây giờ được biết gần chính
xác. Cận dưới đối với MEDP 2 vòng là


toán (chương trình) để tính toán, Daemen phân tích bằng lý thuyết và kết quả là giống
nhau. Đáng chú ý hơn cả hai thuật toán KMT1-DC và KMT2-DC của Keliher cho
phép chúng ta có thể xác định các cận an toàn của các mã pháp SPN bất kỳ và với số
vòng bất kỳ.


21

KẾT LUẬN
Tóm tắt kết quả nghiên cứu
Với tốc độ và khả năng xử lý ngày càng được nâng cao của các bộ vi xử lý
hiện nay, phương pháp mã hóa chuẩn (DES - Data Encryption Standard) đã trở nên
không an toàn trong bảo mật thông tin. Do đó, Viện tiêu chuẩn và công nghệ Hoa kỳ
(NIST - National Institute Standards of Technology) đã quyết định chọn một chuẩn
mã hóa mới với độ an toàn cao nhằm phục vụ nhu cầu bảo mật thông tin liên lạc của
Chính phủ Hoa Kỳ cũng như trong các ứng dụng dân sự. Thuật toán Rijndael do
Vincent Rijmen và Joan Daeman đã được chính thức chọn trở thành chuẩn mã hóa
nâng cao (AES - Advanced Encryption Standard) từ ngày 02 tháng 10 năm 2000.
Ngày nay, ứng dụng của AES đang được sử dụng ngày càng phổ biến trong các
lĩnh vực khác nhau trên thế giới. AES không chỉ đơn thuần là mã hóa và giải mã
thông tin mà còn bao gồm nhiều vấn đề khác nhau cần được nghiên cứu và giải quyết
như ứng dụng xây dựng các hàm băm phục vụ việc chứng thực nguồn gốc nội dung
thông tin (kỹ thuật chữ ký điện tử), xác thực tính nguyên vẹn dữ liệu...
Với sự phát triển ngày càng nhanh chóng của Internet và các ứng dụng giao
dịch điện tử trên mạng, nhu cầu bảo vệ thông tin trong các hệ thống và ứng dụng điện
tử ngày càng được quan tâm. Vì thế việc nghiên cứu về AES và độ an toàn của nó
trong các lĩnh vực bảo mật thông tin ý nghĩa hết sức quan trọng.
Để xem xét độ an toàn của AES các nghiên cứu về thám mã là cần thiết. Với
mục tiêu đó luận văn đã tìm hiểu về mật mã, độ an toàn của mã, các phương pháp tấn
công AES mà chủ yếu là tấn công lượng sai (Differential Cryptanalysis) .