Môn học An ninh Cơ sở dữ liệu
Bài tập lớn: HÀM BĂM
Thầy giáo: Trịnh Nhật Tiến
Học viên: Bùi Trung Hiếu
Khóa: K20 – Hệ thống thông tin
Mã số học viên: 13025006

Hàm Băm
1. Giới thiệu:
- Hàm băm (Hash) là giải thuật nhằm sinh ra các giá trị băm
tương ứng với mỗi khối dữ liệu (chuỗi ký tự, một đối tượng
lập trình trong lập trình hướng đối tượng…)
- Giá trị băm đóng vai trò gần như một khóa để phân biệt các
khối dữ liệu.
- Hàm băm thường được dùng trong bảng băm nhằm giảm
chi phí tính toán khi tìm một khối dữ liệu trong một tập hợp.
- Hàm băm mật mã học (Cryptographic hash) là một hàm băm
với một số tính chất bảo mật nhất định để phù hợp việc sử
dụng trong nhiều ứng dụng bảo mật thông tin đa dạng như
chứng thực, kiểm tra tính nguyên vẹn của thông tin. Một hàm
băm nhận đầu vào là một xâu ký tự dài có độ dài tùy ý và tạo
ra kết quả là một xâu ký tự có độ dài cố định, được gói là
tóm tắt thông điệp hoặc chữ ký số.

Giới thiệu (tiếp)
- Một hàm băm tốt phải thỏa mãn các điều kiện sau:
+ Tính toán nhanh
+ Các khóa được phân bổ đều trong bảng
+ Ít xảy ra đụng độ
+ Xử lý được các loại khóa có kiểu dữ liệu khác nhau


Giới thiệu (tiếp)
- Hầu hết các trường hợp trên đều có thể xảy ra xung đột, nên
có 2 phương pháp để loại bỏ xung đột là phương pháp dò
tuyến tính và phương pháp dây chuyền. Phương pháp dò
tuyến tính là tìm vị trí trống tiếp theo rồi chèn phần tử
đụng độ vào đó. Phương pháp dây chuyền là liên kết các
khóa khác nhau, nhưng có cùng một giá trị băm thành
một danh sách
- Các loại hàm băm mật mã:
+ Sử dụng khóa: Message Authentication Codes (MAC)
+ Không sử dụng khóa: Manipulation Detection Codes
(MDC): One-Way Hash Functions (OWHF), Collision
Resistant Hash Functions (CRHF)
- Ví dụ hàm băm mật mã học: MD2, MD4, MD5, SHA-0, SHA-1…

2. Ứng dụng của hàm băm mật mã
+ Xác thực mật khẩu: Mật khẩu không được lưu dạng văn
bản rõ (clear text) mà ở dạng tóm tắt, tức là người dùng
nhập mật khẩu vào, mật khẩu đó được băm ra, sau đó so
sánh với kết quả băm ở trong dữ liệu lưu trữ.
+ Xác thực thông điệp: Khi giá trị đầu vào thay đổi thì
tương ứng giá trị băm cũng thay đổi, từ đó xác định được
thông điệp đã bị sửa đổi hay chưa.
+ Bảo vệ tính toàn vẹn của thông tin gửi trên mạng: Dựa
vào tính chất một chiều của hàm băm, khi gửi một gói tin
trên mạng, người ta so sánh kết quả băm của gói tin
trước khi gửi với kết quả băm của gói tin khi nhận được.
Nếu kết quả trùng nhau thì gói tin không thay đổi.
+ Tạo chữ ký điện tử: Chữ ký số được tạo ra bằng cách

là bội số của 512.

3. Phương pháp thực hiện hàm băm
Thuật toán SHA-1
+ Bước 3: Khởi tạo bộ nhớ đệm MD
Một bộ đệm 160 bits được dùng để lưu trữ các giá trị băm
trung gian và kết quả. Bộ đệm được biểu diễn bằng 5
thanh ghi 32-bit với các giá trị khởi tạo ở dạng big-endian
(byte có trọng số lớn nhất trong từ, nằm ở địa chỉ thấp
nhất) và có 2 bộ đệm. 5 thanh ghi của bộ đệm đầu tiên
được đặt tên là A, B, C, D, E và tương tự cho bộ đệm thứ
2 là H0, H1, H2, H3, H4, H5. Giá trị các thanh ghi (theo
dạng HEX) như sau:
= 67452301
= EFCDAB89
= 98BADCFE
= 10325476
= C3D2E1F0
+ Bước 4: Xử lý các khối dữ liệu 512 bit

3. Phương pháp thực hiện hàm băm
Thuật toán SHA-1

3. Phương pháp thực hiện hàm băm
Thuật toán SHA-1
Thuật toán gồm 4 vòng lặp, tất cả 80 bước. Các vòng lặp
có cấu trúc như nhau, chỉ khác nhau ở hàm logic F(t)

3. Phương pháp thực hiện hàm băm
Thuật toán MD5

[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22
12]
[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22
16]
- Vòng 2 (Round 2): Tương tự, ký hiệu [abcd k s t] là của biểu thức:
a = b + ((a + G(b, c, d) + X[k] + T[t]) <<< s) Quá trình thực hiện
16 bước:
[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]
[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]
[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]
[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]
Nhận xét: Vòng 2 dùng hàm G, với t từ 17 -> 32 và k = 1 + 5k mod 16

3. Phương pháp thực hiện hàm băm
Thuật toán MD5
- Vòng 3 (Round 3):
Tương tự, ký hiệu [abcd k s t] là của biểu thức: a = b + ((a + H(b,
c, d) + X[k] + T[t]) <<< s)
Quá trình thực hiện 16 bước:
[ABCD 5 4 33] [DABC 8 11 34] [CDAB 1 16 35] [BCDA 14 23 36]
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]
[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]
[ABCD 9 4 45] [DABC 12 11 46] [CDAB 5 16 47] [BCDA 2 23 48]
Nhận xét: Vòng 3 dùng hàm H, với t từ 33 -> 48 và k =5 + 3k mod
16
- Vòng (Round 4):
Tương tự, ký hiệu [abcd k s t] là của biểu thức:
a = b + ((a + I(b,c,d) + X[k] + T[t]) <<< s)
Quá trình thực hiện 16 bước:
[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]