Chức năng băm tốt là gì?

Question

Chức năng Hash tốt là gì? Tôi thấy rất nhiều hàm băm và các ứng dụng trong các khóa học cấu trúc dữ liệu của tôi ở đại học, nhưng tôi chủ yếu nhận ra rằng khá khó để tạo ra hàm băm tốt. Như một quy tắc của ngón tay cái để tránh va chạm giáo sư của tôi nói rằng:

function Hash(key) 
    return key mod PrimeNumber 
end 

(mod là các nhà điều hành% trong C và các ngôn ngữ tương tự)

với số nguyên tố là kích thước của bảng băm. Tôi nhận được đó là một chức năng khá tốt để tránh va chạm và nhanh chóng, nhưng làm thế nào tôi có thể làm tốt hơn? Có chức năng băm tốt hơn cho các phím chuỗi đối với các phím số không?

Answer 1

Để thực hiện tra cứu bảng băm "bình thường" về cơ bản bất kỳ loại dữ liệu nào - cái này của Paul Hsieh là tốt nhất mà tôi từng sử dụng.

http://www.azillionmonkeys.com/qed/hash.html

Nếu bạn quan tâm đến mã hóa an toàn hoặc bất cứ điều gì khác cao cấp hơn, sau đó YMMV. Nếu bạn chỉ muốn một hàm băm có mục đích chung cho một bảng băm tra cứu, thì đây là những gì bạn đang tìm kiếm.

Answer 2

Tôi muốn nói rằng quy tắc chính của ngón tay cái không phải là để cuộn của riêng bạn. Hãy thử sử dụng thứ gì đó đã được kiểm tra kỹ lưỡng, ví dụ: SHA-1 hoặc thứ gì đó dọc theo các dòng đó.

Answer 3

Không có chức năng nào như "hàm băm tốt" cho băm phổ quát (vâng, tôi biết có một thứ như "băm chung" nhưng đó không phải là ý tôi). Tùy thuộc vào bối cảnh các tiêu chí khác nhau xác định chất lượng của một băm. Hai người đã đề cập đến SHA. Đây là một băm mật mã và nó không phải là ở tất cả tốt cho bảng băm mà bạn có thể có nghĩa là.

Bảng băm có các yêu cầu rất khác nhau. Nhưng vẫn còn, việc tìm kiếm một hàm băm tốt phổ biến là khó bởi vì các kiểu dữ liệu khác nhau cho thấy các thông tin khác nhau có thể được băm. Theo quy tắc chung, tốt nhất là xem xét tất cả thông tin một loại giữ như nhau. Điều này không phải luôn luôn dễ dàng hoặc thậm chí có thể. Vì các lý do thống kê (và do đó va chạm), điều quan trọng là tạo ra sự lây lan tốt trên không gian vấn đề, tức là tất cả các đối tượng có thể. Điều này có nghĩa là khi các số băm trong khoảng từ 100 đến 1050 thì không nên để chữ số quan trọng nhất đóng một phần lớn trong băm bởi vì ~ 90% các đối tượng, con số này sẽ bằng 0. Điều quan trọng hơn là để cho ba chữ số xác định hàm băm.

Tương tự, khi các chuỗi băm, điều quan trọng là phải xem xét tất cả các ký tự - ngoại trừ khi nó được biết trước rằng ba ký tự đầu tiên của tất cả các chuỗi sẽ giống nhau; xem xét những điều này sau đó là một sự lãng phí.

Đây thực sự là một trong những trường hợp tôi khuyên đọc những gì Knuth phải nói trong Nghệ thuật lập trình máy tính, vol. 3. Một bài đọc hay khác là bài hát The Art of Hashing của Julienne Walker.

Answer 4

Một hàm băm tốt có các thuộc tính sau:

1. Cho một băm của thông điệp đó là tính toán không khả thi đối với một kẻ tấn công để tìm thông điệp khác mà băm của họ giống hệt nhau.

2. Cho một cặp thông điệp, m 'và m, nó là tính toán để tìm hai ví dụ rằng h (m) = h (m')

Hai trường hợp là không giống nhau. Trong trường hợp đầu tiên, có một băm đã tồn tại từ trước mà bạn đang cố gắng tìm ra một vụ va chạm. Trong trường hợp thứ hai, bạn đang cố gắng tìm bất kỳ hai thư nào va chạm. Nhiệm vụ thứ hai là dễ dàng hơn đáng kể do sinh nhật "nghịch lý".

Trường hợp hiệu suất không phải là vấn đề lớn, bạn nên luôn sử dụng hàm băm an toàn.Có những cuộc tấn công rất thông minh có thể được thực hiện bằng cách ép xung đột trong một băm. Nếu bạn sử dụng một cái gì đó mạnh mẽ ngay từ đầu, bạn sẽ bảo vệ mình chống lại những điều này.

Không sử dụng MD5 hoặc SHA-1 trong thiết kế mới. Hầu hết các nhà mật mã, tôi đưa vào, sẽ xem chúng bị hỏng. Nguồn gốc của sự yếu kém trong cả hai thiết kế này là tài sản thứ hai, mà tôi đã nêu ở trên, không giữ cho những công trình này. Nếu kẻ tấn công có thể tạo ra hai thông điệp, m và m ', thì cả hai hàm băm đều có cùng giá trị mà chúng có thể sử dụng những thông điệp này chống lại bạn. SHA-1 và MD5 cũng bị tấn công tin nhắn mở rộng, có thể làm suy yếu nghiêm trọng ứng dụng của bạn nếu bạn không cẩn thận.

Một hàm băm hiện đại hơn như Whirpool là lựa chọn tốt hơn. Nó không bị các cuộc tấn công tin nhắn mở rộng và sử dụng cùng một toán học như AES sử dụng để chứng minh an ninh chống lại một loạt các cuộc tấn công.

Hy vọng điều đó sẽ hữu ích!

Answer 5

Có hai mục đích chính của chức năng băm:

• để giải tán các điểm dữ liệu thống nhất thành n bit.
• để xác định một cách an toàn dữ liệu đầu vào.

Không thể đề xuất giá trị băm mà không biết bạn đang sử dụng hàm băm nào.

Nếu bạn chỉ cần tạo bảng băm trong chương trình, bạn không cần phải lo lắng về thuật toán đảo ngược hoặc có thể hack được ... SHA-1 hoặc AES hoàn toàn không cần thiết cho điều này, bạn tốt hơn là sử dụng một số variation of FNV. FNV đạt được sự phân tán tốt hơn (và do đó ít va chạm hơn) so với một mod nguyên tố đơn giản như bạn đã đề cập, và nó thích nghi hơn với các kích thước đầu vào khác nhau.

Nếu bạn đang sử dụng băm để ẩn và xác thực thông tin công cộng (chẳng hạn như băm mật khẩu hoặc tài liệu), thì bạn nên sử dụng một trong các thuật toán băm chính được kiểm tra công khai. The Hash Function Lounge là một nơi tốt để bắt đầu.

Answer 6

Đây là ví dụ về một ví dụ hay và cũng là ví dụ về lý do bạn không bao giờ muốn viết. Nó là một Fowler/Noll/Võ (FNV) Hash đó là phần bằng nhau khoa học máy tính thiên tài và voodoo tinh khiết:

unsigned fnv_hash_1a_32 (void *key, int len) { 
    unsigned char *p = key; 
    unsigned h = 0x811c9dc5; 
    int i; 

    for (i = 0; i < len; i++) 
     h = (h^p[i]) * 0x01000193; 

    return h; 
} 

unsigned long long fnv_hash_1a_64 (void *key, int len) { 
    unsigned char *p = key; 
    unsigned long long h = 0xcbf29ce484222325ULL; 
    int i; 

    for (i = 0; i < len; i++) 
     h = (h^p[i]) * 0x100000001b3ULL; 

    return h; 
} 

Edit:

• Landon Curt Noll khuyến cáo trên his site các FVN-1A thuật toán trên thuật toán FVN-1 ban đầu: Thuật toán được cải tiến phân tán tốt hơn byte cuối cùng trong băm. Tôi đã điều chỉnh thuật toán cho phù hợp.

Answer 7

Điều bạn đang nói ở đây là bạn muốn sử dụng thiết bị có khả năng chống va chạm. Hãy thử sử dụng SHA-2.Hoặc thử sử dụng một mật mã khối (tốt) trong một chức năng nén một chiều (không bao giờ thử trước đó), như AES ở chế độ Miyaguchi-Preenel. Vấn đề với điều đó là bạn cần phải:

1) có IV. Hãy thử sử dụng 256 bit đầu tiên của các phần phân đoạn của hằng số Khinchin hoặc một cái gì đó như thế. 2) có sơ đồ đệm. Dễ dàng. Barrow nó từ một băm như MD5 hoặc SHA-3 (Keccak [phát âm 'ket-chak']). Nếu bạn không quan tâm đến bảo mật (một vài người khác đã nói điều này), hãy xem FNV hoặc lookup2 của Bob Jenkins (thực sự tôi là người đầu tiên khuyên bạn nên tra cứu2) Ngoài ra hãy thử MurmurHash, nó nhanh (kiểm tra điều này: .16 cpb).