Hàm băm mật mã

Kỷ yếu công trình khoa học 2015 – Phần I 
HÀM BĂM MẬT MÃ 
Nguyễn Minh Hòa 
Khoa Toán-Tin, Đại học Thăng Long 
Email: mr.nmh175@gmail.com 
Tóm tắt: Khái niệm hàm băm đã xuất hiện từ lâu trong lĩnh vực máy tính. Nó ánh xạ 
một xâu nhị phân (văn bản, hình ảnh, âm thanh,) có độ dài bất kỳ thành một xâu có độ dài 
cố định. Bản chất của mã băm có thể coi như “dấu vân tay” của một văn bản. Nhờ có nó ta 
có thể đảm bảo rằng một văn bản là chính xác và không bị sửa đổi. Hiện nay trên thế giới có 
rất nhiều hàm băm phục vụ cho nhiều mục đích khác nhau như quân sự, truyền tin, xác thực 
Với mong muốn làm chủ mã nguồn, làm chủ chương trình, chúng tôi đã cố gắng tìm hiểu và 
cài đặt hàm băm SHA-256 phục vụ cho đề tài Xây dựng hệ thống chữ ký số cho trường Đại 
học Thăng Long. Trong bài báo sẽ mô tả chi tiết về hàm băm này. 
Từ khóa:Hàm băm, Mã băm, Chữ ký số, SHA-256. 
1. Giới thiệu 
Hàm băm là hàm ánh xạ một xâu nhị phân có độ dài bất kỳ thành một xâu nhị phân có độ dài 
cố định (thường được gọi là mã băm). Thông thường, độ dài của mã băm có thể là 128, 160, 
256 hoặc 512 bit.Hàm băm có thể coi là hàm nén thông điệp một cách hợp lý. 
Để có thể dùng trong thực tế, hàm băm cần đảm bảo các tính chất như: thời gian tính toán 
nhanh, mã băm sinh ra phải ngẫu nhiên và thuật toán phải công khai. Nhằm mục đích đáp ứng 
các tính chất trên, hàm băm SHA-256 đã được xây dựng dựa trên sơ đồ Merkle-Damgard Ứng 
và hàm nén Davies-Meyer.Ứng dụng của nó là để kiểm tra tính toàn vẹn của thông điệp. 
Bài báo này sẽ trình bày chi tiết các lý thuyết và cách thức hoạt động của hàm băm SHA-256. 
Nội dung các phần bao gồm: Phần 2 sẽ mô tả về hàm băm kháng xung đột - một mô hình hàm 
băm phù hợp với thực tế; Phần 3 mô tả về hàm băm SHA-256; Phần cuối cũng sẽ nói về thực 
tế cài đặt hàm băm SHA-256 của dự án. 
2. Hàm băm kháng xung đột 
2.1. Các định nghĩa 
Định nghĩa 1.Hàm băm là hàm tính được một cách “hiệu quả” 
Nó ánh xạ một xâu nhị phân độ dài bất kỳ trong không gian thông điệp thành một xâu 
nhị phân độ dài cố định, gọi là mã băm. 
Thông thường độ dài của mã băm là d= 128, 160, 256 hoặc 512 bit. 
Ví dụ 1. Một số hàm băm trong thực tế. 
Trường Đại học Thăng Long 11 
Kỷ yếu công trình khoa học 2015 – Phần I 
Hàm băm d 
MD4 128 
SHA-1 160 
SHA-256 256 
SHA-512 512 
SHA-3 (Keccak) 224, 256, 384, 512 
Giả sử hàm băm được thiết kế một cách lý tưởng (như ngẫu nhiên), khi đó cho trước 
mã bămx, xác suất tìm được một dữ liệum thỏa mãn H(m) = x chỉ là . Con số này rất gần 0 
khi d đủ lớn. Như vậy hàm băm cho ta một biểu diễn nén hợp lý của dữ liệu. 
Bên cạnh đó, để có thể dùng trong thực tế, hàm băm cần có một số tính chất sau: 
• Tính hiệu quả: có thuật toán “nhanh” (trong thời gian đa thức ) để tính h. 
• Tính ngẫu nhiên: giá trị H(m) là khó dự đoán. 
• Tính công khai. 
Định nghĩa 2.Một xung đột cho hàm H là một cặp thỏa mãn 
Rõ ràng, vì kích thước đầu vào của hàm băm lớn hơn so với kích thước đầu ra, nên 
theo nguyên lý “chuồng bồ câu”, luôn tồn tại xung đột. Tuy vậy, để hàm băm là an toàn thì 
việc tìm thấy xung đột phải rất “khó”. Có nghĩa rằng, xác suất tìm thấy xung đột phải “nhỏ”. 
Định nghĩa 3.Hàm H gọi là kháng xung độtnếu với mọi thuật toán (tường minh1) 
“hiệu quả” A, ta có 
là nhỏ “không đáng kể”. 
Hiệnnay, hàm băm , ánh xạ các xâu nhị phân độ 
dài tối đa sang các xâu độ dài 256, được thừa nhận một cách rộng rãi là kháng xung 
đột. 
Mục đích của hàm băm không phải là giữ bí mật không điệp mà là đảm bảo tính toàn 
vẹn thông điệp. 
1Vì xung đột luôn tồn tại, nên ta có ngay thuật toán in ra xung đột đó. Tường minh ở đây hiểu rẳng thuật 
toán phải xây dựng xung đột từ mô tả của hàm băm, chứ không phải từ xung đột đã có. 
Trường Đại học Thăng Long 12 
Kỷ yếu công trình khoa học 2015 – Phần I 
2.2. Tấn công dùng nghịch lý ngày sinh 
Xét hàm băm . Thuật toán sau đây có thể được dùng để tìm xung 
đột cho các hàm băm trong thời gian . 
Thuật toán: 
1. Chọn ngẫu nhiên xâu trong : (xác suất chúng đôi một 
phân biệt là cao). 
2. Với , ta tính . 
3. Tìm xung đột . Nếu không tìm thấy thì quay lại bước 1. 
Thuật toán được đánh giá dựa trên định lý sau đây: 
Định lý 1 (Nghịch lý ngày sinh nhật). Xét là các biến ngẫu 
nhiên độc lập. Nếu thì 
Từ định lý trên, ta thấy rằng kỳ vọng tìm được xung đột của thuật toán trên là 2. Thời 
gian cần cho thuật toán là và không gian cần là . 
Hàm băm Kích thước mã băm Tốc độ (MB/s) Thời gian tấn công 
SHA-1 160 153 
SHA-256 256 111 
SHA-512 512 99 
Whirlpool 512 57 
2.3. Sơ đồ Merkle-Damgard 
Để xây dựng hàm băm kháng xung đột, kích thước mã băm tối thiểu nên là 160 bit. 
Tuy nhiên đầu vào có thể là một xâu với kích thước tùy ý. Trên thực tế, việc thiết kế hàm 
băm trên miền vô hạn là khó. Bởi vậy người ta thường thiết kế một hàm nén ánh xạ các xâu 
bit độ dài cố định s thành các xâu bít độ dài cố định d, sau đó thực hiện tính toán lặp với hàm 
nén để được hàm băm với đầu vào tùy ý. 
Phép biến đổi Merkle-Damgard là một cách phổ biến để mở rộng một hàm nén kháng 
xung đột với kích thước đầu vào cố định thành hàm băm kháng xung đột kích thước đầu vào 
tùy ý. Trong sơ đồ Merkle-Damgard, ta sử dụng hàm nén kích thước đầu vào cố định 
Trường Đại học Thăng Long 13 
Kỷ yếu công trình khoa học 2015 – Phần I 
Hình 1. Sơ đồ Merkle-Damgard 
Mục đích của ta là xây dựng hàm băm kích thước đầu vào tùy ý 
Sơ đồ Merkle-Damgard được mô tả như trong Hình 1. 
Thuật toán Merkle-Damgard được mô tả như sau: 
1. Dữ liệu cần bămm với độ dài |m| = L sẽ được ghép với dãy bit 
với l là số nguyên không âm nhỏ nhất để độ dài củam||PB chia hết cho k. 
2. Thông điệp m||PB sẽ được chia thành các khốik bit: 
3. Gán là một dãy d bit cố định. 
4. Với i = 0, 1, , t ta tính 
5. Output . 
Tính an toàn của sơ đồ Merkle-Damgard được chỉ ra bởi định lý sau. 
Định lý 2. Nếu hàm nén h là kháng xung đột, vậy hàm H xây dựng theo sơ đồ Merkle-
Damgard cũng là kháng xung đột. 
2.4. Xây dựng hàm nén 
Sơ đồ trước cho phép ta đưa bài toán thiết kế hàm băm kháng xung đột với đầu vào bất 
kỳ về bài toán thiết kế hàm nén với đầu vào cố định. Bây giờ ta xem xét một cách thiết kế 
hàm nén dựa trên mã khối an toàn. 
Xét hệ mã khối E trên không gian khóa K và không gian thông điệp : 
Hàm nén Davies-Meyer định nghĩa bởi: 
Trường Đại học Thăng Long 14 
Kỷ yếu công trình khoa học 2015 – Phần I 
Giả sử (E,D) là một hệ mã khối “lý tưởng” (tập gồm |K| hoán vị ngẫu nhiên). Tìm một 
xung độth(x,y)= h(x',y')cho hàm nén Davies-Meyer định nghĩa ở trên mất lần tính (E, 
D). 
Để phù hợp với tiêu chuẩn quốc gia Việt Nam về chữ ký số (TCVN 7635:2007), 
chúng tôi sử dụng SHA-256 là hàm băm phục vụ dự án chữ ký số của trường Đại học Thăng 
Long. Hàm băm chuẩn SHA-256 được xây dựng dựa trên sơ đồ Merkle-Damgard,hàm nén 
Davies-Meyer và hệ mã khối SHACAL-2 với kích thước khối là 256.Phần tiếp theo, chúng ta 
sẽ mô tả chi tiết SHA-256 và SHACAL-2. 
3. Hàm băm SHA-256 
Hàm băm SHA256 nhận đầu vào là một xâu bit (ký tự, tập tin) bất kỳ có độ dài tối 
đa bit và tạo ra một mã băm có độ dài 256 bit và thường được biểu diễn dưới dạng 64 
chữ số trong hệ cơ số 16. 
3.1. Sơ đồ chung 
Hàm băm này được xây dựng dựa trên sơ đồ Merkle-Damgard với 
• Vector khởi tạo là dãy 256 bit được chia thành 8 khối liên tiếp 
• Dữ liệu đầu vào được chia thành các khối m[i] kích thước 512 bit, và 
• Hàm nén Davies-Meyer 
định nghĩa bởi 
trong đó E là hệ mã khối an toàn 
3.2. Hệ mã khối SHACAL-2 
Ta sử dụng một số ký hiệu sau để mô tả hệ mã khối SHACAL-2: 
Ký hiệu Mô tả 
Trường Đại học Thăng Long 15 
Kỷ yếu công trình khoa học 2015 – Phần I 
⋀ 
Phép toán AND 
⊕ 
Phép toán XOR 
¬ Phép đảo bit 
Phép quay phải n bit 
Phép dịch phải n bit 
Dựa vào các ký hiệu trên, ta xây dựng các hàm sau 
Ta cũng sử dụng các hằng số độ dài 32 bit 
Đây chính là 32 bit đầu tiên của giá trị căn bậc ba của 64 số nguyên tố đầu tiên. Các 
hằng số này được mô tả dưới đây (ở dạng hexa). 
Quá trình tính toán diễn ra như sau: 
Trường Đại học Thăng Long 16 
Kỷ yếu công trình khoa học 2015 – Phần I 
4. Cài đặt và thử nghiệm 
Hiện nay có khá nhiều thư viện hỗ trợ sẵn hàm băm SHA-256. Tuy nhiên, với mong 
muốn làm chủ mã nguồn cũng như giúp chương trình sau này linh hoạt hơn trong việc xử lý, 
thay thế, nâng cấp các modul, chúng tôi quyết định tự cài đặt lại thuật toán SHA-256 theo các 
mô tả trong tài liệu FIPS PUB 180-4 và đã cài đặt thành công bằng ngôn ngữ lập trình C++ 
trên hệ điều hành Windows 8 - 64bits.Chương trình đã được kiểm tra bằng các vector test của 
NIST cũng như so sánh với các chương trình sinh mã SHA256 khác. 
Đầu vào của chương trình là đường dẫn một tập tin bất kỳ (văn bản, hình ảnh, âm 
thanh,). Đầu ra của chương trình là một xâu dài 64 ký tự (mỗi ký tự là một số ở hệ cơ số 
16), chính là mã băm SHA-256 của tập tin đầu vào ở dạng hexa. 
Chúng tôi đã chạy thử nghiệm chương trình trên máy laptop có bộ xử lý Core i5 
1.8Ghz, với 4GB Ram, hệ điều hành Windows 8, 64 bit. Thời gian sinh mã băm của chương 
trình phụ thuộc vào kích thước của tập tin đầu vào. Với những tập tin có kích thước dưới 
Trường Đại học Thăng Long 17 
Kỷ yếu công trình khoa học 2015 – Phần I 
200MB, thời gian sinh mã băm trung bình là xấp xỉ 1 giây. Trong quá trình kiểm thử, chúng 
tôi đã băm một tập tin hình video kích thước 1,05GB, thời gian sinh mã băm là xấp xỉ 13 giây. 
5. Tài liệu tham khảo 
[1]. Khóa học Cryptography I : https://www.coursera.org/course/crypto 
[2]. Jonathan Katz và Yehuda Lindell, Introduction to Modern Cryptography, 
Chapman & Hall/CRC, 2007. 
[3]. NIST, Federal Information Processing Standards Publication 180-4, SecureHash 
Standards (SHS), March 2012. 
Abstract: The concept “hash function” has appeared long ago in Computer Science. 
It maps a binary string (text, images, audio, ...) with any length into a fixed-length string. The 
nature of the hash code can be viewed as a "fingerprint" of a document.And we can use it to 
guarantee that a document is correct and not be modified.Today, there are many hash 
functions which are usedformany different purposes, such as military, communications, 
authentic ...With a desire to control the source code and program, we have tried to learn and 
install SHA-256 in digital signature system for Thang Long University project. In the paper, 
we will describe the details of this hash function. 
Keyword:Hash function, Hash digest, Digital signature, SHA-256. 
Trường Đại học Thăng Long 18