Thuật toán băm¶
Hai phần trước đã giới thiệu nguyên lý hoạt động của bảng băm và các phương pháp xử lý đụng độ mã băm. Tuy nhiên, cả địa chỉ mở và chuỗi kề chỉ có thể đảm bảo bảng băm hoạt động bình thường khi xảy ra đụng độ băm, chứ không thể giảm tần suất xảy ra đụng độ.
Nếu đụng độ mã băm xảy ra quá thường xuyên, hiệu suất của bảng băm sẽ bị giảm sút nghiêm trọng. Như hình bên dưới, đối với bảng băm chuỗi kề, trong trường hợp lý tưởng, các cặp khóa-giá trị được phân bổ đều trên các ngăn, đạt hiệu suất truy vấn tối ưu; trong trường hợp xấu nhất, tất cả các cặp khóa-giá trị được lưu trữ trong cùng một ngăn, làm giảm độ phức tạp thời gian xuống còn \(O(n)\).
Sự phân bổ của các cặp khóa-giá trị được quyết định bởi hàm băm. Hãy nhớ lại các bước của hàm băm: đầu tiên tính giá trị băm, sau đó lấy giá trị đó chia lấy dư cho độ dài của mảng:
Quan sát công thức trên, khi dung lượng bảng băm capacity cố định, thuật toán băm hash() quyết định giá trị đầu ra, từ đó quyết định sự phân bổ của các cặp khóa-giá trị trong bảng băm.
Điều này có nghĩa là, để giảm xác suất xảy ra đụng độ băm, chúng ta nên tập trung vào việc thiết kế thuật toán băm hash().
Mục tiêu của Thuật toán băm¶
Để xây dựng một bảng băm vừa nhanh vừa mạnh mẽ, thuật toán băm cần có các đặc điểm sau:
- Tính xác định: Đối với cùng một đầu vào, thuật toán băm phải luôn tạo ra cùng một đầu ra. Chỉ khi đó bảng băm mới có thể đáng tin cậy.
- Hiệu suất cao: Quá trình tính toán giá trị băm phải đủ nhanh. Chi phí tính toán càng nhỏ thì bảng băm càng có tính thực tiễn cao.
- Phân phối đều: Thuật toán băm nên đảm bảo các cặp khóa-giá trị được phân bổ đều trong bảng băm. Phân phối càng đều thì xác suất đụng độ mã băm càng thấp.
Trên thực tế, thuật toán băm không chỉ được sử dụng để triển khai bảng băm mà còn được áp dụng rộng rãi trong các lĩnh vực khác.
- Lưu trữ mật khẩu: Để bảo vệ tính bảo mật của mật khẩu người dùng, hệ thống thường không lưu trữ mật khẩu dưới dạng văn bản rõ (plaintext) mà lưu trữ giá trị băm của mật khẩu. Khi người dùng nhập mật khẩu, hệ thống tính toán giá trị băm của đầu vào và so sánh với giá trị băm đã lưu trữ. Nếu chúng khớp nhau, mật khẩu được coi là chính xác.
- Kiểm tra tính toàn vẹn dữ liệu: Người gửi dữ liệu có thể tính toán giá trị băm của dữ liệu và gửi kèm theo; người nhận có thể tính toán lại giá trị băm của dữ liệu nhận được và so sánh với giá trị băm nhận kèm. Nếu chúng khớp nhau, dữ liệu được coi là nguyên vẹn.
Đối với các ứng dụng mật mã học, thuật toán băm cần có các đặc tính bảo mật mạnh hơn để ngăn chặn việc dịch ngược, chẳng hạn như việc suy ra mật khẩu gốc từ một giá trị băm.
- Tính một chiều: Không thể suy ra bất kỳ thông tin nào về dữ liệu đầu vào từ giá trị băm.
- Tính chống đụng độ: Cực kỳ khó tìm được hai đầu vào khác nhau mà tạo ra cùng một giá trị băm.
- Hiệu ứng lở tuyết: Những thay đổi nhỏ ở đầu vào sẽ dẫn đến những thay đổi lớn và không thể dự đoán trước ở đầu ra.
Lưu ý rằng "phân phối đều" và "tính chống đụng độ" là hai khái niệm độc lập. Việc thỏa mãn phân phối đều không nhất thiết có nghĩa là chống được đụng độ. Ví dụ, với đầu vào ngẫu nhiên key, hàm băm key % 100 có thể tạo ra đầu ra phân phối đều. Tuy nhiên, thuật toán băm này quá đơn giản, tất cả các key có cùng hai chữ số cuối sẽ có cùng một đầu ra, giúp dễ dàng suy ra một key hợp lệ từ giá trị băm, từ đó bẻ khóa mật khẩu.
Thiết kế Thuật toán băm¶
Thiết kế thuật toán băm là một vấn đề phức tạp đòi hỏi phải cân nhắc nhiều yếu tố. Tuy nhiên, đối với một số tình huống không yêu cầu quá khắt khe, chúng ta cũng có thể thiết kế một số thuật toán băm đơn giản.
- Băm cộng tính: Cộng mã ASCII của từng ký tự trong đầu vào và sử dụng tổng số đó làm giá trị băm.
- Băm nhân tính: Tận dụng mối tương quan thấp được tạo ra bởi phép nhân: nhân với một hằng số ở mỗi bước và tích lũy mã ASCII của các ký tự vào giá trị băm.
- Băm XOR: Tích lũy giá trị băm bằng cách thực hiện phép toán XOR trên từng phần tử của dữ liệu đầu vào.
- Băm xoay: Tích lũy mã ASCII của từng ký tự vào giá trị băm, thực hiện thao tác xoay bit trên giá trị băm trước mỗi lần tích lũy.
Chúng ta có thể thấy rằng bước cuối cùng của mỗi thuật toán băm là lấy kết quả chia lấy dư cho số nguyên tố lớn \(1000000007\), đảm bảo rằng giá trị băm nằm trong một phạm vi phù hợp. Điều này tự nhiên đặt ra một câu hỏi: tại sao lại nhấn mạnh việc sử dụng modulo là một số nguyên tố, và nhược điểm của việc sử dụng modulo là một hợp số là gì?
Nói ngắn gọn: sử dụng một số nguyên tố lớn làm số chia (modulo) giúp tối đa hóa tính phân phối đều của các giá trị băm. Vì số nguyên tố không có ước chung với các số khác, nó có thể làm giảm các quy luật tuần hoàn do phép toán chia lấy dư tạo ra, từ đó giảm thiểu đụng độ mã băm.
Ví dụ, giả sử chúng ta chọn hợp số \(9\) làm số chia, số chia này có thể chia hết cho \(3\), khi đó tất cả các key chia hết cho \(3\) sẽ được ánh xạ tới các giá trị băm \(0\), \(3\), \(6\).
Nếu các giá trị key đầu vào tình cờ tuân theo cấp số cộng này, các giá trị băm sẽ bị tập trung lại một chỗ, làm trầm trọng thêm đụng độ mã băm. Bây giờ, giả sử chúng ta thay thế modulus bằng số nguyên tố \(13\). Vì key và modulus không có ước chung, các giá trị băm đầu ra sẽ được phân bổ đều hơn nhiều.
Đáng lưu ý là nếu key được đảm bảo phân bổ ngẫu nhiên và đều, thì việc chọn số nguyên tố hay hợp số làm số chia đều có thể tạo ra các giá trị băm phân phối đều. Tuy nhiên, khi phân phối của key có tính chu kỳ, việc chia lấy dư cho một hợp số sẽ dễ dẫn đến hiện tượng kết cụm hơn.
Tóm lại, chúng ta thường chọn số nguyên tố làm số chia, và số nguyên tố này phải đủ lớn để loại bỏ các quy luật tuần hoàn nhiều nhất có thể, nâng cao tính mạnh mẽ của thuật toán băm.
Các Thuật toán băm Phổ biến¶
Dễ thấy rằng các thuật toán băm đơn giản được giới thiệu ở trên khá "mong manh" và còn lâu mới đạt được mục tiêu thiết kế của thuật toán băm. Ví dụ, vì phép cộng và XOR có tính giao hoán, băm cộng tính và băm XOR không thể phân biệt các chuỗi có cùng các ký tự nhưng khác thứ tự, điều này có thể làm trầm trọng thêm đụng độ băm và mang lại rủi ro bảo mật.
Trong thực tế, chúng ta thường sử dụng một số thuật toán băm tiêu chuẩn, chẳng hạn như MD5, SHA-1, SHA-2 và SHA-3. Chúng có thể ánh xạ dữ liệu đầu vào có độ dài bất kỳ thành một giá trị băm có độ dài cố định.
Trong thế kỷ qua, các thuật toán băm liên tục trải qua quá trình nâng cấp và tối ưu hóa. Một số nhà nghiên cứu nỗ lực nâng cao hiệu suất của thuật toán băm, trong khi những người khác, bao gồm cả các hacker, tận tụy tìm kiếm các vấn đề bảo mật trong thuật toán băm. Bảng dưới đây hiển thị các thuật toán băm thường được sử dụng trong các ứng dụng thực tế.
- MD5 và SHA-1 đã bị tấn công thành công nhiều lần và do đó bị loại bỏ trong các ứng dụng bảo mật khác nhau.
- Dòng SHA-2, đặc biệt là SHA-256, là một trong những thuật toán băm an toàn nhất cho đến nay, chưa có báo cáo nào về việc bị tấn công thành công, do đó thường được sử dụng trong các giao thức và ứng dụng bảo mật khác nhau.
- SHA-3 có chi phí triển khai thấp hơn và hiệu suất tính toán cao hơn so với SHA-2, nhưng mức độ sử dụng hiện tại của nó chưa rộng rãi như dòng SHA-2.
Bảng
| MD5 | SHA-1 | SHA-2 | SHA-3 | |
|---|---|---|---|---|
| Năm phát hành | 1992 | 1995 | 2002 | 2008 |
| Độ dài đầu ra | 128 bit | 160 bit | 256/512 bit | 224/256/384/512 bit |
| Đụng độ mã băm | Thường xuyên | Thường xuyên | Hiếm gặp | Hiếm gặp |
| Mức độ bảo mật | Thấp, đã bị tấn công thành công | Thấp, đã bị tấn công thành công | Cao | Cao |
| Ứng dụng | Bị loại bỏ, vẫn dùng để kiểm tra tính toàn vẹn dữ liệu | Bị loại bỏ | Xác thực giao dịch tiền mã hóa, chữ ký số, v.v. | Có thể dùng để thay thế SHA-2 |
Giá trị băm trong Cấu trúc dữ liệu¶
Chúng ta biết rằng khóa của bảng băm có thể là số nguyên, số thực dấu phẩy động, chuỗi ký tự và các kiểu dữ liệu khác. Các ngôn ngữ lập trình thường cung cấp các thuật toán băm tích hợp sẵn cho các kiểu dữ liệu này để tính toán chỉ số ngăn trong bảng băm. Lấy Python làm ví dụ, chúng ta có thể gọi hàm hash() để tính giá trị băm cho các kiểu dữ liệu khác nhau.
- Giá trị băm của số nguyên và kiểu logic là chính giá trị của chúng.
- Việc tính toán giá trị băm cho số thực dấu phẩy động và chuỗi ký tự phức tạp hơn, độc giả quan tâm được khuyến khích tự tìm hiểu.
- Giá trị băm của một tuple thu được bằng cách băm từng phần tử của nó và kết hợp các kết quả đó thành một giá trị băm duy nhất.
- Giá trị băm của một đối tượng thường được tạo ra từ địa chỉ bộ nhớ của nó. Bằng cách ghi đè phương thức băm của đối tượng, giá trị băm có thể được tạo ra từ nội dung của đối tượng đó.
Tip
Hãy lưu ý rằng định nghĩa và phương pháp tính toán giá trị băm tích hợp sẵn trong các ngôn ngữ lập trình khác nhau là khác nhau.
num = 3
hash_num = hash(num)
# Giá trị băm của số nguyên 3 là 3
bol = True
hash_bol = hash(bol)
# Giá trị băm của biến logic True là 1
dec = 3.14159
hash_dec = hash(dec)
# Giá trị băm của số thập phân 3.14159 là 326484311674566659
str = "Hello 算法"
hash_str = hash(str)
# Giá trị băm của chuỗi "Hello 算法" là 4617003410720528961
tup = (12836, "小哈")
hash_tup = hash(tup)
# Giá trị băm của tuple (12836, '小哈') là 1029005403108185979
obj = ListNode(0)
hash_obj = hash(obj)
# Giá trị băm của đối tượng ListNode tại 0x1058fd810 là 274267521
int num = 3;
size_t hashNum = hash<int>()(num);
// Giá trị băm của số nguyên 3 là 3
bool bol = true;
size_t hashBol = hash<bool>()(bol);
// Giá trị băm của biến logic 1 là 1
double dec = 3.14159;
size_t hashDec = hash<double>()(dec);
// Giá trị băm của số thập phân 3.14159 là 4614256650576692846
string str = "Hello 算法";
size_t hashStr = hash<string>()(str);
// Giá trị băm của chuỗi "Hello 算法" là 15466937326284535026
// Trong C++, std::hash() tích hợp sẵn chỉ cung cấp giá trị băm cho các kiểu dữ liệu cơ bản
// Giá trị băm cho mảng và đối tượng cần được triển khai riêng
int num = 3;
int hashNum = Integer.hashCode(num);
// Giá trị băm của số nguyên 3 là 3
boolean bol = true;
int hashBol = Boolean.hashCode(bol);
// Giá trị băm của biến logic true là 1231
double dec = 3.14159;
int hashDec = Double.hashCode(dec);
// Giá trị băm của số thập phân 3.14159 là -1340954729
String str = "Hello 算法";
int hashStr = str.hashCode();
// Giá trị băm của chuỗi "Hello 算法" là -727081396
Object[] arr = { 12836, "小哈" };
int hashTup = Arrays.hashCode(arr);
// Giá trị băm của mảng [12836, 小哈] là 1151158
ListNode obj = new ListNode(0);
int hashObj = obj.hashCode();
// Giá trị băm của đối tượng ListNode utils.ListNode@7dc5e7b4 là 2110121908
int num = 3;
int hashNum = num.GetHashCode();
// Giá trị băm của số nguyên 3 là 3;
bool bol = true;
int hashBol = bol.GetHashCode();
// Giá trị băm của biến logic true là 1;
double dec = 3.14159;
int hashDec = dec.GetHashCode();
// Giá trị băm của số thập phân 3.14159 là -1340954729;
string str = "Hello 算法";
int hashStr = str.GetHashCode();
// Giá trị băm của chuỗi "Hello 算法" là -586107568;
object[] arr = [12836, "小哈"];
int hashTup = arr.GetHashCode();
// Giá trị băm của mảng [12836, 小哈] là 42931033;
ListNode obj = new(0);
int hashObj = obj.GetHashCode();
// Giá trị băm của đối tượng ListNode 0 là 39053774;
let num = 3
let hashNum = num.hashValue
// Giá trị băm của số nguyên 3 là 9047044699613009734
let bol = true
let hashBol = bol.hashValue
// Giá trị băm của biến logic true là -4431640247352757451
let dec = 3.14159
let hashDec = dec.hashValue
// Giá trị băm của số thập phân 3.14159 là -2465384235396674631
let str = "Hello 算法"
let hashStr = str.hashValue
// Giá trị băm của chuỗi "Hello 算法" là -7850626797806988787
let arr = [AnyHashable(12836), AnyHashable("小哈")]
let hashTup = arr.hashValue
// Giá trị băm của mảng [AnyHashable(12836), AnyHashable("小哈")] là -2308633508154532996
let obj = ListNode(x: 0)
let hashObj = obj.hashValue
// Giá trị băm của đối tượng ListNode utils.ListNode là -2434780518035996159
int num = 3;
int hashNum = num.hashCode;
// Giá trị băm của số nguyên 3 là 34803
bool bol = true;
int hashBol = bol.hashCode;
// Giá trị băm của biến logic true là 1231
double dec = 3.14159;
int hashDec = dec.hashCode;
// Giá trị băm của số thập phân 3.14159 là 2570631074981783
String str = "Hello 算法";
int hashStr = str.hashCode;
// Giá trị băm của chuỗi "Hello 算法" là 468167534
List arr = [12836, "小哈"];
int hashArr = arr.hashCode;
// Giá trị băm của mảng [12836, 小哈] là 976512528
ListNode obj = new ListNode(0);
int hashObj = obj.hashCode;
// Giá trị băm của đối tượng ListNode Instance of 'ListNode' là 1033450432
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};
let num = 3;
let mut num_hasher = DefaultHasher::new();
num.hash(&mut num_hasher);
let hash_num = num_hasher.finish();
// Giá trị băm của số nguyên 3 là 568126464209439262
let bol = true;
let mut bol_hasher = DefaultHasher::new();
bol.hash(&mut bol_hasher);
let hash_bol = bol_hasher.finish();
// Giá trị băm của biến logic true là 4952851536318644461
let dec: f32 = 3.14159;
let mut dec_hasher = DefaultHasher::new();
dec.to_bits().hash(&mut dec_hasher);
let hash_dec = dec_hasher.finish();
// Giá trị băm của số thập phân 3.14159 là 2566941990314602357
let str = "Hello 算法";
let mut str_hasher = DefaultHasher::new();
str.hash(&mut str_hasher);
let hash_str = str_hasher.finish();
// Giá trị băm của chuỗi "Hello 算法" là 16092673739211250988
let arr = (&12836, &"小哈");
let mut tup_hasher = DefaultHasher::new();
arr.hash(&mut tup_hasher);
let hash_tup = tup_hasher.finish();
// Giá trị băm của tuple (12836, "小哈") là 1885128010422702749
let node = ListNode::new(42);
let mut hasher = DefaultHasher::new();
node.borrow().val.hash(&mut hasher);
let hash = hasher.finish();
// Giá trị băm của đối tượng ListNode RefCell { value: ListNode { val: 42, next: None } } là 15387811073369036852
val num = 3
val hashNum = num.hashCode()
// Giá trị băm của số nguyên 3 là 3
val bol = true
val hashBol = bol.hashCode()
// Giá trị băm của biến logic true là 1231
val dec = 3.14159
val hashDec = dec.hashCode()
// Giá trị băm của số thập phân 3.14159 là -1340954729
val str = "Hello 算法"
val hashStr = str.hashCode()
// Giá trị băm của chuỗi "Hello 算法" là -727081396
val arr = arrayOf<Any>(12836, "小哈")
val hashTup = arr.hashCode()
// Giá trị băm của mảng [12836, 小哈] là 189568618
val obj = ListNode(0)
val hashObj = obj.hashCode()
// Giá trị băm của đối tượng ListNode utils.ListNode@1d81eb93 là 495053715
num = 3
hash_num = num.hash
# Giá trị băm của số nguyên 3 là -4385856518450339636
bol = true
hash_bol = bol.hash
# Giá trị băm của biến logic true là -1617938112149317027
dec = 3.14159
hash_dec = dec.hash
# Giá trị băm của số thập phân 3.14159 là -1479186995943067893
str = "Hello 算法"
hash_str = str.hash
# Giá trị băm của chuỗi "Hello 算法" là -4075943250025831763
tup = [12836, '小哈']
hash_tup = tup.hash
# Giá trị băm của tuple (12836, '小哈') là 1999544809202288822
obj = ListNode.new(0)
hash_obj = obj.hash
# Giá trị băm của đối tượng ListNode #<ListNode:0x000078133140ab70> là 4302940560806366381
Minh họa thực thi
https://pythontutor.com/render.html#code=class%20ListNode%3A%0A%20%20%20%20%22%22%22%E9%93%BE%E8%A1%A8%E8%8A%82%E7%82%B9%E7%B1%BB%22%22%22%0A%20%20%20%20def%20__init__%28self,%20val%3A%20int%29%3A%0A%20%20%20%20%20%20%20%20self.val%3A%20int%20%3D%20val%20%20%23%20%E8%8A%82%E7%82%B9%E5%80%BC%0A%20%20%20%20%20%20%20%20self.next%3A%20ListNode%20%7C%20None%20%3D%20None%20%20%23%20%E5%90%8E%E7%BB%A7%E8%8A%82%E7%82%B9%E5%BC%95%E7%94%A8%0A%0A%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20num%20%3D%203%0A%20%20%20%20hash_num%20%3D%20hash%28num%29%0A%20%20%20%20%23%20%E6%95%B4%E6%95%B0%203%20%E7%9A%84%E5%93%88%E5%B8%8C%E5%80%BC%E4%B8%BA%203%0A%0A%20%20%20%20bol%20%3D%20True%0A%20%20%20%20hash_bol%20%3D%20hash%28bol%29%0A%20%20%20%20%23%20%E5%B8%83%E5%B0%94%E9%87%8F%20True%20%E7%9A%84%E5%93%88%E5%B8%8C%E5%80%BC%E4%B8%BA%201%0A%0A%20%20%20%20dec%20%3D%203.14159%0A%20%20%20%20hash_dec%20%3D%20hash%28dec%29%0A%20%20%20%20%23%20%E5%B0%8F%E6%95%B0%203.14159%20%E7%9A%84%E5%93%88%E5%B8%8C%E5%80%BC%E4%B8%BA%20326484311674566659%0A%0A%20%20%20%20str%20%3D%20%22Hello%20%E7%AE%97%E6%B3%95%22%0A%20%20%20%20hash_str%20%3D%20hash%28str%29%0A%20%20%20%20%23%20%E5%AD%97%E7%AC%A6%E4%B8%B2%E2%80%9CHello%20%E7%AE%97%E6%B3%95%E2%80%9D%E7%9A%84%E5%93%88%E5%B8%8C%E5%80%BC%E4%B8%BA%204617003410720528961%0A%0A%20%20%20%20tup%20%3D%20%2812836,%20%22%E5%B0%8F%E5%93%88%22%29%0A%20%20%20%20hash_tup%20%3D%20hash%28tup%29%0A%20%20%20%20%23%20%E5%85%83%E7%BB%84%20%2812836,%20'%E5%B0%8F%E5%93%88'%29%20%E7%9A%84%E5%93%88%E5%B8%8C%E5%80%BC%E4%B8%BA%201029005403108185979%0A%0A%20%20%20%20obj%20%3D%20ListNode%280%29%0A%20%20%20%20hash_obj%20%3D%20hash%28obj%29%0A%20%20%20%20%23%20%E8%8A%82%E7%82%B9%E5%AF%B9%E8%B1%A1%20%3CListNode%20object%20at%200x1058fd810%3E%20%E7%9A%84%E5%93%88%E5%B8%8C%E5%80%BC%E4%B8%BA%20274267521&cumulative=false&curInstr=19&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false
Trong nhiều ngôn ngữ lập trình, chỉ các đối tượng bất biến (immutable) mới có thể làm key trong bảng băm. Nếu chúng ta sử dụng một danh sách (mảng động) làm key, khi nội dung của danh sách thay đổi, giá trị băm của nó cũng thay đổi, và chúng ta không còn có thể tìm thấy value ban đầu trong bảng băm.
Mặc dù các biến thành viên của một đối tượng tùy chỉnh (chẳng hạn như một nút danh sách liên kết) là có thể thay đổi, đối tượng đó vẫn băm được (hashable). Điều này là do giá trị băm của một đối tượng thường được tạo dựa trên địa chỉ bộ nhớ của nó, và ngay cả khi nội dung của đối tượng thay đổi, địa chỉ bộ nhớ vẫn giữ nguyên, do đó giá trị băm không thay đổi.
Bạn có thể nhận thấy rằng các giá trị băm được in ra ở các môi trường (console) khác nhau là khác nhau. Điều này là do trình thông dịch Python thêm một chuỗi ngẫu nhiên (salt) vào hàm băm chuỗi ký tự mỗi khi khởi động. Cách tiếp cận này giúp ngăn chặn hiệu quả các cuộc tấn công HashDoS và nâng cao tính bảo mật của thuật toán băm.