Trước khi tôi nêu câu hỏi thực sự của mình, trước tiên hãy để tôi đưa ra năm thuật ngữ để tất cả chúng ta đều hiểu:
Để cho $U=\{k_1,...,k_u\}$ vũ trụ của các chìa khóa có thể, $|U|=u$.
Chúng tôi sử dụng bảng băm $T$ với $m$ tế bào, đếm từ $0$ đến $m-1$.
Chúng tôi sử dụng một họ các hàm băm $H$, sao cho mỗi $h\in H$ có khả năng $1/m$ hai khóa riêng biệt đó $k$ và $k'$ băm để cùng một giá trị, tức là, $P(h(k)=h(k'))=1/m$.
Cuối cùng, băm phổ quát có nghĩa là để băm, một hàm băm ngẫu nhiên (thỏa mãn $1/m$ yêu cầu đã đề cập ở trên) được chọn từ H. Theo nghiên cứu của tôi (và điều này có vẻ phù hợp với sách giáo khoa thuật toán CLRS nổi tiếng), chúng tôi luôn chỉ sử dụng một Độc thân hàm băm trong toàn bộ thời gian chạy của bảng băm của chúng tôi. Do đó, các phần tử khác trong họ hàm băm chỉ có liên quan trong khi bảng đang được tạo (tức là trong lệnh gọi chương trình đầu tiên), nhưng một hàm này đã được chọn là cố định và tất cả các phần tử khác không còn liên quan nữa. Điều này cũng hợp lý, bởi vì nếu bạn chọn các hàm băm khác nhau cho các khóa khác nhau, thì bạn cần phải ánh xạ lại từ khóa đến hàm đã sử dụng -- điều này sẽ không có ý nghĩa gì nhiều, đây là vấn đề chúng ta sẽ giải quyết : biết nơi lưu trữ khóa; nhưng hàm băm đã chọn sẽ phụ thuộc vào khóa, vì vậy chúng ta sẽ gặp một nghịch lý. :) Vì vậy, khá hợp lý khi chúng tôi chỉ chọn một chức năng trong toàn bộ thời gian chạy.
Đã làm rõ điều đó, câu hỏi của tôi:
Làm thế nào để chọn một hàm băm ngẫu nhiên giúp chúng ta phòng thủ trước kẻ thù, nếu nó vẫn cố định trong suốt thời gian tồn tại của bảng? Tôi không thấy bất kỳ sự khác biệt nào khi có một hàm băm duy nhất được sửa trước.
Động lực duy nhất được đề cập trong bất kỳ bài giảng và tài liệu học thuật nào là làm cho cuộc sống của kẻ thù trở nên khó khăn hơn bởi vì đối với bất kỳ hàm băm cố định nào, chúng ta có thể tạo ra một chuỗi các khóa băm thành cùng một giá trị, do đó gây ra hành vi trong trường hợp xấu nhất của bảng băm. Vì vậy, tuyên bố là vì bây giờ chúng tôi chọn một hàm băm ngẫu nhiên mà bạn không biết nó đang được sử dụng nữa, vì vậy bạn cũng không thể nghĩ ra một chuỗi khóa tấn công như vậy. Tôi chỉ không mua lập luận đó.
Sau khi bảng băm của bạn với hàm băm phổ quát đã được tạo, bạn Mà còn có một hàm băm duy nhất mà bạn có thể tìm thấy một chuỗi như vậy, vì vậy chúng tôi thực sự không giải quyết được vấn đề. Tôi tin rằng câu hỏi quan trọng là từ đâu mà đối thủ nên biết hàm băm nào đang được sử dụng!
Vì vậy, nếu chúng ta chỉ sử dụng một hàm băm duy nhất và thậm chí công khai nó, thì tất nhiên bạn có thể bị tấn công. Nhưng tại sao chức năng đó phải được công khai? Mã gần như không bao giờ được công khai, phải không? Vì vậy, giả sử rằng mã đó không được công khai, kẻ thù không biết hàm băm nào được sử dụng -- cho dù bạn có một mã duy nhất hay một mã được chọn ngẫu nhiên từ cả gia đình.
Do đó, nếu chúng ta cho rằng hàm không công khai và đối thủ có thể suy ra nó "bằng cách nào đó" (điều đó thậm chí có khả thi không? bằng cách đo thời gian chạy chẳng hạn?), thì một lần nữa, nó không tạo ra sự khác biệt cho dù có một cái được sửa trước hoặc liệu nó chỉ được sửa sau khi bảng được khởi tạo hay không.
Do đó, dù bằng cách nào, đối số đối thủ dường như không hoạt động - nó có vẻ sai trừ khi hàm băm được sử dụng thực sự công khai, điều mà tôi đơn giản là không thể tin được. Vì vậy, những gì đang xảy ra ở đây?
