Hash 32bit int đến 16bit int?

Question

Một số cách đơn giản để băm số nguyên 32 bit (ví dụ: địa chỉ IP, ví dụ: Unix time_t, v.v.) xuống số nguyên 16 bit?

Ví dụ: hash_32b_to_16b(0x12345678) có thể trả lại 0xABCD.

Hãy bắt đầu với điều này như một giải pháp dụ khủng khiếp nhưng chức năng:

function hash_32b_to_16b(val32b) { 
    return val32b % 0xffff; 
} 

Câu hỏi là cụ thể về JavaScript, nhưng cảm thấy tự do để thêm bất kỳ giải pháp ngôn ngữ trung tính, tốt nhất là không sử dụng các hàm thư viện.

Ngữ cảnh cho câu hỏi này là tạo ID duy nhất (ví dụ: ID 64 bit có thể bao gồm một số băm 16 bit có giá trị 32 bit khác nhau). Tránh va chạm là quan trọng.

Đơn giản = tốt. Wacky + obfuscated = vui.

Answer 1

Điều này phụ thuộc vào bản chất của các số nguyên. Nếu chúng có thể chứa một số mặt nạ bit, hoặc có thể khác nhau theo hai lũy thừa, thì các XOR đơn giản sẽ có xác suất va chạm cao. Bạn có thể thử một cái gì đó như (i>>16)^((i&0xffff) * p) với p là số nguyên tố.

Các băm bảo mật như MD5 đều tốt, nhưng chúng rõ ràng là quá mức cần thiết ở đây. Bất cứ điều gì phức tạp hơn CRC16 là quá mức cần thiết.

Answer 2

Tôi nghĩ đây là điều tốt nhất bạn sẽ nhận được. Bạn có thể nén các mã để một dòng duy nhất nhưng var của đang có bây giờ như tài liệu:

function hash_32b_to_16b(val32b) { 
    var rightBits = val32b & 0xffff; // Left-most 16 bits 
    var leftBits = val32b & 0xffff0000; // Right-most 16 bits 

    leftBits = leftBits >>> 16; // Shift the left-most 16 bits to a 16-bit value 

    return rightBits^leftBits; // XOR the left-most and right-most bits 
} 

Với các thông số của vấn đề, giải pháp tốt nhất sẽ có mỗi băm 16-bit tương ứng với chính xác 2^16 số 32 bit. Nó cũng sẽ IMO băm tuần tự 32-bit số khác nhau. Trừ khi tôi đang thiếu một cái gì đó, tôi tin rằng giải pháp này làm hai điều đó.

Tôi cho rằng bảo mật không thể xem xét trong vấn đề này, vì giá trị băm chỉ là quá ít bit. Tôi tin rằng giải pháp tôi đã cung cấp thậm chí phân phối số 32-bit đến 16-bit băm

Answer 3

Something đơn giản như thế này ....

function hash_32b_to_16b(val32b) {  
    var h = hmac(secretKey, sha512); 
    var v = val32b; 
    for(var i = 0; i < 4096; ++i) 
     v = h(v); 
    return v % 0xffff; 
} 

Answer 4

tôi sẽ nói chỉ áp dụng một tiêu chuẩn như băm SHA1 hoặc md5 và sau đó lấy 16 bit cuối cùng.

Answer 5

Giả sử bạn mong đợi các bit quan trọng nhất để 'thay đổi' nhiều nhất, tôi nghĩ bạn có thể sẽ nhận được phân phối đủ tốt bằng cách chỉ sử dụng 16 bit thấp hơn của giá trị dưới dạng băm.

Nếu các số bạn sắp băm sẽ không có loại phân phối đó, thì bước bổ sung xor-ing trong 16 bit trên có thể hữu ích. Tất nhiên, gợi ý này là nếu bạn dự định sử dụng băm chỉ cho một số loại lược đồ tìm kiếm/lưu trữ và không tìm kiếm các thuộc tính liên quan đến mật mã của khả năng không đoán trước và không đảo ngược (trong đó xor đề xuất -ing không thực sự mua cho bạn một trong hai).