Bài giảng Mật mã học - Chương 4: Chứng thực thông điệp

p nhận 
được.
2. Mã chứng thực thông điệp (MAC)
Các yêu cầu đối với MAC
30
Trường hợp của MAC có những khác biệt do MAC 
là hàm nhiều-một. Giả sử k>n (kích thước khoá lớn 
hơn kích thước MAC) và MAC1 = C(K, M1), việc 
thám mã phải thực hiện MACi = C(Ki, M1) với tất cả 
các giá trị có thể của Ki. Ít nhất có một khoá đảm 
bảo MACi = MAC1.
Lưu ý rằng sẽ có 2k MACs được tạo ra nhưng chỉ 
có 2n < 2k giá trị MAC khác nhau. Do đó, một số 
khoá sẽ tạo ra các MAC chính xác và attacker 
không có cách nào để biết được đó là khoá nào. 
Trung bình, có 2k/2n = 2(k-n) khoá được tạo ra và 
attacker phải lặp đi lặp lại các cuộc tấn công.
2. Mã chứng thực thông điệp (MAC)
Các yêu cầu đối với MAC
31
Vòng 1
Cho: M1, MAC1 = C(K, M1)
Tính MACi = C(Ki, M1) đối với 2
k khoá
Số lượng khớp  2(k-n)
Vòng 2
Cho: M2, MAC2 = C(K, M2)
Tính MACi = C(Ki, M2) đối với 2
(k-n) khoá kết 
quả từ Vòng 1
Số lượng khớp  2(k-2n)
.......
2. Mã chứng thực thông điệp (MAC)
Các yêu cầu đối với MAC
32
Trung bình,  vòng sẽ cần thực hiện 
nếu k =  x n. Ví dụ, nếu một khoá 80 
bit được sử dụng và MAC dài 32 bit. 
– Vòng đầu tiên sẽ tạo ra khoảng 248 khoá 
có thể, 
– Vòng thứ hai sẽ tạo thu hẹp lại còn 216
khả năng, 
– Vòng thứ ba sẽ tạo ra chỉ một khoá duy 
nhất, chính là khoá của người gởi.
2. Mã chứng thực thông điệp (MAC)
Các yêu cầu đối với MAC
33
2. Mã chứng thực thông điệp (MAC)
MAC dựa trên giải thuật mã hoá DES
34
3. Hàm băm
Khái niệm
Một hàm băm nhận một chuỗi dài ở đầu vào, ngắt nó 
thành nhiều mảnh, trộn lẫn chúng và tạo ra một chuỗi 
mới với chiều dài ngắn.
Không phải mọi hàm băm đều thích hợp cho việc tạo 
ra một dấu vân tay kỹ thuật số.
Ví dụ: 
– Xét một hàm băm đơn giản H sử dụng toán tử 
XOR để biến đổi một chuỗi đầu vào có độ dài tuỳ ý 
để thu được một chuỗi 16 bit ở đầu ra. 
– Cho M = M1M2Mk, với mỗi Mi (có thể ngoại trừ 
khối Mk) là một chuỗi nhị phân 16 bit. Nếu Mk ngắn 
hơn 16 bit, thêm vào cuối một số bit 1 để được 
khối 16 bit.
35
3. Hàm băm
Khái niệm
Cho: H(M) = M1  M2    Mk.
– Hàm băm này không thích hợp để tạo ra dấu vân tay 
kỹ thuật số do có thể dễ dàng tìm được các chuỗi với 
nội dung khác nhau nhưng có cùng giá trị băm. 
– Cho hai chuỗi khác nhau như sau:
S1: “He likes you but I hate you”
S2: “He hates you but I like you”
Mã hoá hai chuỗi này bằng cách sử dụng mã ASCII 8 
bit và bỏ các khoảng trắng giữa các từ, ta sẽ thu được 
H(S1) = H(S2).
 Một hàm băm cần phải đáp ứng một số tiêu chuẩn 
cho trước mới có thể tạo ra dấu vân tay kỹ thuật số.
36
3. Hàm băm
Tiêu chuẩn xây dựng hàm băm
Cho H là hàm băm được xây dựng. 
Trước tiên cần thiết lập cận trên  cho chiều dài của 
chuỗi input (là số rất lớn, đơn vị bit).
 là chiều dài cố định của chuỗi output (< ).
Để sinh ra một dấu vân tay kỹ thuật số tốt, H cần 
phải có:
– Thuộc tính một chiều (one-way property)
– Thuộc tính duy nhất.
Hàm băm này được gọi là một hàm băm mật mã 
(Cryptographic Hash Function – CHF).
37
3. Hàm băm
Tìm kiếm hàm băm
Mặc dù đã có rất nhiều nỗ lực, người ta vẫn chưa 
thể xác định được có tồn tại một hàm băm thoả mãn 
tính chất một chiều và duy nhất hay không?
Đã có nhiều hàm băm được xây dựng và sử dụng 
trong thực tế.
Các hàm băm vẫn có thể chứa những lỗ hổng có 
thể được khai thác bởi kẻ tấn công.
 Cần xác định các điểm yếu nhằm đưa ra các 
hàm băm mạnh hơn.
38
3. Hàm băm
Tìm kiếm hàm băm
Năm 2004, nhà toán học Trung Quốc Xiaoyun 
Wang và cộng sự đã chứng minh rằng một số 
hàm băm được sử dụng rộng rãi lúc đó như MD4, 
MD5, HACAL-128, RIPEMD là không đáp ứng 
tiêu chí kháng đụng độ.
Năm 2005, họ cũng chứng minh rằng hàm băm 
sử dụng phổ biến là SHA-1 không kháng đụng độ 
mạnh như suy nghĩ của mọi người, và phát triển 
một phương pháp giúp tìm thấy hai chuỗi x và y 
khác nhau có cùng giá trị băm.
39
3. Hàm băm
Cấu trúc cơ bản của hàm băm chuẩn
Các giải thuật băm MD5, Whirlpool, SHA-1, SHA-
2 đều có cùng cấu trúc cơ bản được đề xuất bởi 
Ralph C. Merkle năm 1978. 
Trung tâm của cấu trúc cơ bản này là một hàm nén. 
Các giải thuật băm khác nhau sử dụng những hàm 
nén khác nhau.
Trong cấu trúc cơ bản này, M là khối rõ, IV là một 
vector khởi tạo, F là một hàm nén, + là một số dạng 
của toán tử cộng modular.
40
3. Hàm băm
Cấu trúc cơ bản của hàm băm chuẩn
41
3. Hàm băm
Các công dụng cơ bản của hàm băm
42
3. Hàm băm
Các công dụng cơ bản của hàm băm
43
3. Hàm băm
Các công dụng cơ bản của hàm băm
a. Mã hoá thông điệp cộng với mã băm
A  B: E(K, [M || H(M)])
Bảo mật: chỉ A và B chia sẻ K
Chứng thực: H(M) được bảo vệ bằng mật mã
b. Mã hoá mã băm chia sẻ với khoá bí mật
A  B: M || E(K, H(M))
Chứng thực: H(M) được bảo vệ bằng mật mã
c. Mã hoá khoá bí mật với mã băm của người gởi
A  B: M || E(PRA, H(M))
Chứng thực và chữ ký số: 
– H(M) được bảo vệ bằng mật mã
– Chỉ A có thể tạo E(PRA, H(M))
44
3. Hàm băm
Các công dụng cơ bản của hàm băm
d. Mã hoá kết quả của (c) với khoá bí mật chia sẻ
A  B: E(K, [M || E(PRA, H(M))])
Bảo mật: chỉ A và B chia sẻ K
Chứng thực và chữ ký số
e. Tính mã băm của thông điệp cộng với trị bí mật 
A  B: M || H(M || S)
Chứng thực: chỉ A và B chia sẻ S
f. Mã hoá kết quả của (e)
A  B: E(K, [M || H(M || S])
Chứng thực: chỉ A và B chia sẻ S
Bảo mật: chỉ A và B chia sẻ K
45
3. Hàm băm
Các công dụng cơ bản của hàm băm
46
3. Hàm băm
MD5
MD5 (Message-Digest algorithm 5) là một hàm băm 
mật mã với giá trị băm dài 128 bit diễn tả bởi một số 
thập lục phân 32 ký tự (RFC 1321).
Được dùng chủ yếu để kiểm tra tính toàn vẹn của tập 
tin trên nguyên tắc hai dữ liệu vào X và Y hoàn toàn 
khác nhau thì xác suất để có cùng một md5 hash 
giống nhau là rất nhỏ. 
Được thiết kế bởi giáo sư Ronald Rivest (MIT) vào 
năm 1991 để thay thế MD4 không còn an toàn.
Hiện nay, MD5 ít được sử dụng do kích thước bảng 
băm chỉ có 128 bit dễ bị tấn công brute-force và được 
thay thế bởi những giải thuật khác như Whirlpool, 
SHA-1
47
3. Hàm băm
MD5
Sửa T thành t
MD5 hash 
khác nhau
48
3. Hàm băm
SHA
SHA (Secure Hash Algorithm – Giải thuật băm an 
toàn) được phát triển bởi cục An ninh quốc gia Mỹ 
(National Security Agency – NSA).
Giải thuật an toàn:
– Cho một giá trị băm nhất định được tạo nên bởi 
một trong những giải thuật SHA, việc tìm lại được 
đoạn dữ liệu gốc là không khả thi.
– Việc tìm được hai đoạn dữ liệu nhất định có cùng 
kết quả băm tạo ra bởi một trong những giải thuật 
SHA là không khả thi. Bất cứ thay đổi nào trên 
đoạn dữ liệu gốc, dù nhỏ, cũng sẽ tạo nên một giá 
trị băm hoàn toàn khác với xác xuất rất cao.
49
3. Hàm băm
SHA
SHA gồm 2 phiên bản:
– SHA-1: trả lại kết quả dài 160 bit. Được sử dụng 
rộng rãi để thay thế MD5 trong nhiều ứng dụng và 
giao thức bảo mật khác nhau, bao gồm TLS, SSL, 
PGP, SSH, S/MIME, IPSec.
– SHA-2: gồm 4 giải thuật
SHA-224: trả lại kết quả dài 224 bit.
SHA-256: trả lại kết quả dài 256 bit.
SHA-384: trả lại kết quả dài 384 bit.
SHA-512: trả lại kết quả dài 512 bit (=512) và 
có =2128 -1.
50
3. Hàm băm
SHA-1 và MD5
51
4. Chữ ký số
Khái niệm chung
Sử dụng khoá công khai để tạo chữ ký số:
– Giả sử A cần gởi cho B một thông điệp mật kèm 
chữ ký điện tử, A sẽ sử dụng khoá công khai của 
B để mã hoá thông điệp rồi dùng khoá cá nhân 
của mình để mã hoá chữ ký, sau đó gởi cả thông 
điệp lẫn chữ ký cho B. B sẽ dùng khoá công khai 
của A để giải mã chữ ký, rồi dùng khoá cá nhân 
của mình để giải mã thông điệp của A.
– Việc tạo chữ ký và kiểm chứng chữ ký thường 
được thực hiện nhờ hàm băm.
52
4. Chữ ký số
Khái niệm chung
Ký vào thông điệp:
Dùng giải thuật băm để thay đổi thông điệp cần truyền đi 
để được một message digest (MD5 thu được digest có 
chiều dài 128-bit hoặc SHA thu được digest 160-bit).
Sử dụng khóa private key của người gửi để mã hóa 
message digest thu được ở bước trên. Bước này thường 
dùng giải thuật RSA. Kết quả thu được gọi là digital 
signature của thông điệp ban đầu. 
Gộp digital signature vào thông điệp ban đầu (“ký nhận” 
vào thông điệp). Sau đó, mọi sự thay đổi trên message 
sẽ bị phát hiện. Việc ký nhận này đảm bảo người nhận tin 
tưởng thông điệp này xuất phát từ người gửi chứ không 
phải là ai khác.
53
4. Chữ ký số
Khái niệm chung
Các bước kiểm tra:
Dùng public key của người gửi (khóa này được 
thông báo đến mọi người) để giải mã chữ ký số của 
thông điệp.
Dùng giải thuật (MD5 hoặc SHA) băm thông điệp 
nhận được. 
So sánh kết quả thu được ở bước 1 và 2. Nếu trùng 
nhau, ta kết luận thông điệp này không bị thay đổi 
trong quá trình truyền và thông điệp này là của 
người gửi .
54
4. Chữ ký số
Không mã hoá
55
4. Chữ ký số
Có mã hoá
56
5. Bài tập
1. Tìm hai câu tiếng Anh có ý nghĩa khác 
nhau nhưng có cùng giá trị băm với 
16-bit XOR-hash function H.
2. Cho h = 1001101000111 010 là một 
chuỗi nhị phân 16 bit. Tìm 4 chuỗi nhị 
phân tương tự có cùng giá trị băm h 
với 16-bit XOR-hash function H.
3. Mô tả chi tiết giải thuật MD5.
57
5. Bài tập
4. Vẽ lưu đồ minh hoạ giải thuật SHA-51.
5. Vẽ lưu đồ minh hoạ giải thuật HMAC.
6. Microsoft Windows XP, không giống 
như UNIX hoặc Linux, lưu user names 
và user passwords trong registry. Tìm 
kiếm và mô tả chi tiết tác vụ này. Cho 
biết độ bảo mật của giải thuật và đề 
xuất cách thức tấn công.
58
5. Bài tập
7. Nêu tên các ứng dụng có sử dụng chữ ký số 
nhằm đảm bảo an toàn thông tin.
8. Phân tích độ an toàn của các giải thuật 
MD5, SHA.
9. Mô tả các kỹ thuật có thể sử dụng để tấn 
công vào giải thuật MAC.
10. Chọn một trong số những giải thuật MAC và 
giải thuật băm để viết một ứng dụng sử 
dụng giải thuật này.
59
5. Bài tập
11. Tìm 3 phần mềm có kèm theo mã băm, 
kiểm tra mã băm (dùng phần mềm hoặc 
website) để suy ra độ tin cậy của các phần 
mềm này.
12. Tìm 3 chứng chỉ số đính kèm theo trên các 
trang web có yêu cầu bảo mật cao.
13. Sử dụng Cryptool, thực hiện một số ví dụ về 
dữ liệu giả mạo khi sử dụng chứng thực với 
giải thuật băm.
-----------