- FNV
-
FNV (англ. Fowler–Noll–Vo) — простая хэш-функция для общего применения, разработанная Гленом Фаулером, Лондоном Керт Нолом и Фогном Во. Не является криптографической функцией. Существуют варианты для 32-, 64-, 128-, 256-, 512-, и 1024 — битных хэшей.
Содержание
Математическая запись
Функция FNV:
- ,
- ,
- ,
- — простое число,
- — входная последовательность двойных слов.
Модифицированная функция FNV:
- ,
- .
Пример кода
Функция проста в реализации. Ее основа — умножение на простое число и сложение по модулю 2 с входным текстом.
#define FNV_32_PRIME ((unsigned int)0x01000193) unsigned int FNV1Hash (char *buf, unsigned int len) { unsigned char *bp = (unsigned char *)buf; unsigned char *be = bp + len; unsigned int hval = 0x811c9dc5; while (bp < be) { hval *= FNV_32_PRIME; hval ^= (unsigned int)*bp++; } return hval; }
Модификации
Существует модификация алгоритма, решающая некоторые его проблемы. В частности, проблему последнего байта. Весь смысл модификации — замена порядка операций на обратный. Сначала сложение, затем трансформация хэша (умножение на простое число).
unsigned int FNV1aHash (char *buf, unsigned int len) { unsigned char *bp = (unsigned char *)buf; unsigned char *be = bp + len; unsigned int hval = 0x811c9dc5; while (bp < be) { hval ^= (unsigned int)*bp++; hval *= FNV_32_PRIME; } return hval; }
Помимо вышеуказанной модификации были разработаны некоторые редакции алгоритма, улучшающие производительность. Примером таких функций являются FNV1A_Jesteress и FNV1A_Yorikke. Помимо работы над ускорением алгоритма, автор уделил внимание и качеству распределения[1].
Коллизии
Так как значение хэш-функции 32-битное, вероятность появления коллизии значительно выше, чем у хэш-функций, возвращающих, к примеру, 128-битный хэш.
Примеры коллизий
62274fb9: ИЗБИТЫЕ НЕВЗНАЧАЙ 65194ecd: EKSISTENCIALIZEM ГРОБОКОПАТЕЛЬСТВО
Ссылки
- Хэш-функции общего назначения
- Исходные тексты хэш-функий общего назначения
- Страничка алгоритма (авторская)
- Тестирование FNV и иных хеш-функций общего назначения на предмет коллизий и производительности
Примечания
Хеш-функции Общего назначения Криптографические JH • HAVAL • Keccak • LM-хеш • MD2 • MD4 • MD5 • MD6 • N-Hash • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 • SHA-1 • SHA-2 • Skein • Snefru • Tiger • Whirlpool • ГОСТ Р 34.11-94
Категория:- Хеш-функции
Wikimedia Foundation. 2010.