Легкий 8-байтовый алгоритм хэш-функции
Мне нужно извлечь 8-байтовый дайджест из строки переменной длины, поэтому я ищу такой алгоритм, который я буду реализовывать в c / c ++. Это будет частью процедуры цифровой подписи на микроконтроллере, поэтому она должна быть:
- записываемый в несколько строк кода, так как прошивка должна быть как можно меньше;
- низкое потребление ресурсов, особенно оперативная память (предпочтительно менее 100 байт);
- достаточно сильным, что изменение одного символа в любой точке строки изменит общий дайджест.
Я взглянул на существующие алгоритмы, такие как crc64, но они кажутся слишком тяжелыми для моей платформы.
Решение
Как сказал AndrewTomazos-Fathomling, невозможно сделать безопасный хэш в 64 битах, поэтому, если вы намерены, тогда мой совет СТОП, возьмите книгу и прочитайте о криптографически безопасном хешировании.
Если вы не планируете использовать это в качестве безопасного хэша и не заботитесь о столкновениях или атаках, то ответ, который он дал вам, прекрасно работает, и вы можете при необходимости подправить простые числа P1 и P2. Я дам вам другую альтернативу, которая позволит вам делать хэширование с тегами и больше перемешивать.
// 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);
}
Другие решения
Нет никакого шанса сделать безопасный хеш в 64 битах. Даже SHA-1 на 160 бит считается теоретически сломанным. Вам следует использовать SHA2-256, если вы действительно заботитесь о безопасной цифровой подписи. Если вы не заботитесь о безопасности и просто хотите использовать хеш-функцию, которая предотвращает несостязательные конфликты, просто используйте следующее, это нормально:
constexpr uint64 P1 = 7;
constexpr uint64 P2 = 31;
uint64 hash = P1;
for (const char* p = s; *p != 0; p++) {
hash = hash * P2 + *p;
}
Вот модифицированная версия 32-битной версии, которую я нашел в моих старых исходных файлах
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;
}
Но хеширование всегда приводит к коллизиям. Конечно, некоторые алгоритмы лучше, чем другие.
Редактировать:
Я нашел источник 32-битной версии: http://www.cse.yorku.ca/~oz/hash.html
У меня было точно такое же требование, и я согласился на FNV-1A, после исключения SIP хеша (реализовано Bloomberg здесь).
Я нашел реализацию FNV здесь:
https://github.com/foonathan/string_id/blob/master/hash.hpp
который:
constexpr uint64_t fnv_basis = 14695981039346656037ull;
constexpr uint64_t fnv_prime = 1099511628211ull;
// FNV-1a 64 bit hash of null terminated buffer
uint64_t fnv1a_hash(const char* str, uint64_t hash = fnv_basis)
{
return *str ? fnv1a_hash(str + 1, (hash ^ *str) * fnv_prime) : hash;
}
Похоже, он зацикливается, используя хвостовую рекурсию. И условие остановки null байт.
(буст использует hash_range который hash_combining каждый элемент в цепи, я думаю.)
Лицензия Zlib и авторское право — Джонатан Мюллер. Хотя я не уверен, что oneliner может быть юридически лицензирован, если он осуществляет исследования других лиц (Фаулер-Нолл-Vo).
detector