Thuật toán hàm băm 8 byte nhẹ

Question

Tôi cần trích xuất một thông báo 8 byte từ chuỗi có độ dài thay đổi nên tôi đang tìm một thuật toán mà tôi sẽ triển khai trong c/C++. Đó sẽ là một phần của một thủ tục chữ ký kỹ thuật số trên một vi điều khiển, vì vậy nó phải là:

• ghi trong vài dòng mã, kể từ firmware phải được giữ càng ít càng tốt;
• mức tiêu thụ tài nguyên thấp, expecially ram (tốt hơn ít hơn 100 byte);
• đủ mạnh để thay đổi một ký tự đơn tại bất kỳ điểm nào của chuỗi sẽ thay đổi thông báo tổng thể.

Tôi đã xem xét các thuật toán hiện có như crc64 nhưng dường như chúng quá nặng đối với nền tảng của tôi.

Answer 1

Như AndrewTomazos-Fathomling nói, nó không thể làm một băm an toàn trong 64 bit, vì vậy nếu đó là ý định của bạn sau đó lời khuyên của tôi là STOP, chọn một cuốn sách và đọc về băm mật mã an toàn.

Nếu bạn không có kế hoạch sử dụng băm bảo mật và bạn không quan tâm đến va chạm hoặc tấn công, thì câu trả lời mà anh ấy cung cấp cho bạn hoạt động tốt và bạn có thể chỉnh sửa số nguyên tố P1 và P2 nếu cần. Tôi sẽ cung cấp cho bạn một giải pháp thay thế khác cho phép bạn gắn thẻ băm và trộn lẫn nhiều thứ hơn.

// Disclaimer: I make no claims about the quality of this particular hash - it's 
// certainly not a cryptographically secure hash, nor should it *ever* be 
// construed as such. 

unsigned long long quickhash64(const char *str, unsigned long long mix = 0) 
{ // set 'mix' to some value other than zero if you want a tagged hash   
    const unsigned long long mulp = 2654435789; 

    mix ^= 104395301; 

    while(*str) 
     mix += (*str++ * mulp)^(mix >> 23); 

    return mix^(mix << 37); 
} 

Answer 2

Không có cơ hội để thực hiện băm an toàn trong 64 bit. Ngay cả SHA-1 ở 160 bit được coi là lý thuyết bị hỏng. Bạn nên sử dụng SHA2-256 nếu bạn thực sự quan tâm đến việc ký số an toàn. Nếu bạn không quan tâm về an ninh và chỉ muốn có một hàm băm mà tránh va chạm không gây tranh cãi chỉ cần sử dụng những điều sau đây, nó là tốt:

constexpr uint64 P1 = 7; 
constexpr uint64 P2 = 31; 

uint64 hash = P1; 
for (const char* p = s; *p != 0; p++) { 
    hash = hash * P2 + *p; 
} 

Answer 3

Đây là một phiên bản sửa đổi của một phiên bản 32 bit tôi tìm thấy trong tôi các tệp nguồn cũ

static unsigned long long llhash(const char *str) 
{ 
    unsigned long long hash = 5381; 
    int c; 

    while (c = *str++) 
     hash = ((hash << 5) + hash) + c; 

    return hash; 
} 

Nhưng băm sẽ luôn dẫn đến xung đột. Tất nhiên một số thuật toán tốt hơn các thuật toán khác.

Edit: tôi tìm thấy nguồn gốc của phiên bản 32 bit: http://www.cse.yorku.ca/~oz/hash.html