Xem mẫu
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
. Con số này rất gần 0
mã bămx, xác suất tìm được một dữ liệum thỏa mãn H(m) = x chỉ là
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
dài tối đa
đột.
, ánh xạ các xâu nhị phân độ
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
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.
1
Vì 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
. Thuật toán sau đây có thể được dùng để tìm xung
Xét hàm băm
đột cho các hàm băm trong thời gian
.
Thuật toán:
1. Chọn ngẫu nhiên
phân biệt là cao).
xâu trong
(xác suất chúng đôi một
:
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
nhiên độc lập. Nếu
là các biến ngẫ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à
Hàm băm
và không gian cần là
.
Kích thước mã băm
Tốc độ (MB/s)
SHA-1
160
153
SHA-256
256
111
SHA-512
512
99
Whirlpool
512
Thời gian tấn công
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ơ đồ MerkleDamgard 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
D).
lần tính (E,
Để 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
là dãy 256 bit được chia thành 8 khối liên tiếp
• Vector khởi tạo
• 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
Trư ng Đ i h c Thăng Long
Mô tả
15
nguon tai.lieu . vn
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
. Con số này rất gần 0
mã bămx, xác suất tìm được một dữ liệum thỏa mãn H(m) = x chỉ là
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
dài tối đa
đột.
, ánh xạ các xâu nhị phân độ
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
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.
1
Vì 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
. Thuật toán sau đây có thể được dùng để tìm xung
Xét hàm băm
đột cho các hàm băm trong thời gian
.
Thuật toán:
1. Chọn ngẫu nhiên
phân biệt là cao).
xâu trong
(xác suất chúng đôi một
:
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
nhiên độc lập. Nếu
là các biến ngẫ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à
Hàm băm
và không gian cần là
.
Kích thước mã băm
Tốc độ (MB/s)
SHA-1
160
153
SHA-256
256
111
SHA-512
512
99
Whirlpool
512
Thời gian tấn công
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ơ đồ MerkleDamgard 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
D).
lần tính (E,
Để 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
là dãy 256 bit được chia thành 8 khối liên tiếp
• Vector khởi tạo
• 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
Trư ng Đ i h c Thăng Long
Mô tả
15