Как сократить 64-битное хэш-значение до 48-битного значения?

У меня уже есть 64-битная хеш-функция в библиотеке (кодирование C), но мне нужно только 48 бит. Мне нужно обрезать 64-битное хэш-значение до 48-битного значения, но это должно быть безопасным образом, чтобы свести к минимуму коллизии.

Хеш-функция — это очень хорошая 64-битная хеш-функция. Он был протестирован с помощью SMHasher (хеш-тестирование «DieHarder») и оказался лучше, чем Murmur2. По словам моих коллег, реализованный в библиотеке алгоритм для 64-битного хеширования — это xxHash, протестированный с помощью SMHasher и получивший Q.Score 10! Для тех, кто хочет его увидеть, исходный код xxHash доступен на github.com: github. com/Cyan4973/xxHash/релизы/последние.

Основная идея состоит в том, чтобы все биты в 64-битном хеш-значении (или его часть) влияли на результирующее 48-битное хэш-значение. Есть ли способ сделать это?

[Поздняя редакция]:
Итак, я реализовал свой собственный генератор 48-битных (квази)-UUID.
Пожалуйста, ознакомьтесь с полным рабочим решением (включая исходный код) здесь: https://stackoverflow.com/a/47895889/4731718.


c uuid algorithm hash math
person סטנלי גרונן    schedule 02.10.2015    source источник
comment
Если это действительно хорошая 64-битная хэш-функция, то это, по сути, случайные биты, так что вы можете просто взять 48 из них любым удобным для вас способом.   -  person Lee Daniel Crocker    schedule 02.10.2015
comment
в хеш-коде не хранится никакой информации, если вы специально не используете некоторые специальные коды, такие как локальное чувствительное хеширование. Короче говоря, вы просто выбираете младшие 48 бит и все   -  person Jason Hu    schedule 02.10.2015
comment
Даже если это действительно хорошая хеш-функция, вы теряете 16 бит безопасности от столкновений, что бы вы ни делали. И если вы не знаете внутреннюю структуру, вы можете даже потерять больше, чем четверть безопасности при столкновении, чем вы ожидаете.   -  person SkryptX    schedule 02.10.2015
comment
@LeeDanielCrocker Да, это очень хорошая 64-битная хэш-функция. Проверено с помощью SMHasher и оказалось лучше, чем Murmur2.   -  person סטנלי גרונן    schedule 02.10.2015
comment
Есть 2^64 64-битных хэшей. Вы не можете поместить их в 2^48 48-битных хэшей без того, чтобы по крайней мере 2^16 из них не накапливались в одном и том же месте.   -  person Teepeemm    schedule 02.10.2015
comment
@Teepeemm: Вы абсолютно правы. Но я не стремлюсь к совершенству. Я просто просил достойное решение ... Вот почему я проголосовал за ответ Ли Дэниела Крокера.   -  person סטנלי גרונן    schedule 02.10.2015
comment
Я думаю, вы получаете бесполезные ответы (и отрицательные голоса), потому что вы не совсем понимаете, что ищете. «сохранять» информацию из всех 64 битов означает, что вы хотите иметь возможность отменить преобразование 64->48, что подразумевает отсутствие коллизий. минимизация коллизий подразумевает, что вы готовы принять некоторые коллизии (но не многие). Ваше голосование за комментарий Ли Дэниела Кокера (не ответ) означает, что вы удовлетворены любым решением, которое сводит к минимуму коллизии, сколько бы их ни было. Это три разных возможности.   -  person Teepeemm    schedule 02.10.2015
comment
Вероятно, он пытается создать собственную реализацию генератора UUID версии 1. Это единственное использование 48-битного хеша, которое я знаю в компьютерном мире. RFC 4122 позволяет заменить MAC-адрес в UUID версии 1 (или 2) случайным 48-битным идентификатором узла либо потому, что у узла нет MAC-адреса, либо потому, что его нежелательно раскрывать. Из соображений безопасности он, вероятно, не хочет раскрывать, что заменяет часть MAC-адреса UUID (48 бит) алгоритмом хеширования.   -  person Grigore Madalin    schedule 21.02.2017
comment
@Teepeemm: В результате этот вопрос не так странен, как кажется. Многие программисты по всему миру сталкиваются с этой 48-битной проблемой UUID v1, когда пытаются реализовать ее в соответствии с RFC 4122. Я проголосую за этот вопрос.   -  person Grigore Madalin    schedule 21.02.2017
comment
@Grigore Madalin: Очень интересные комментарии! Спасибо за упоминание UUID 48-bit и RFC-4122. Multumesc :)... Никогда не думал, что доживу до того дня, когда этот вопрос перестанет быть отрицательным... хе-хе :)   -  person סטנלי גרונן    schedule 21.02.2017
comment
Искреннее спасибо за отзыв.   -  person greybeard    schedule 16.03.2017

Ответы (3)


arrow_upward
11
arrow_downward

Если 64-битный хеш хорош, то выбор любых 48 бит также будет хорошим хешем. @Ли Дэниел. Конечно, информация теряется и необратима.

unsigned long long Mask48 = 0xFFFFFFFFFFFFu;
unsigned long long hash48 = hash64 & Mask48;

Если 64-битная хеш-функция слаба, то модифицируйте ее по наибольшему простому числу чуть меньше pow(2,48). Некоторые ведра будут потеряны. Это не повредит хорошему хешу, но определенно улучшит слабые хэши.

unsigned long long LargestPrime48 = 281474976710597u;  // FFFFFFFFFFC5
unsigned long long hash48 = hash64 % LargestPrime48;
person chux - Reinstate Monica    schedule 02.10.2015
comment
Наконец-то кто-то разбирается в математике... :) - person סטנלי גרונן; 03.10.2015

arrow_upward
2
arrow_downward 

hash >>= 16;

Но если вы чувствуете себя лучше, произвольно сохраняя остальные 16 бит, просто используйте XOR.

hash = (hash >> 16) ^ (hash & 0xFFFF);
person Louis Ricci    schedule 02.10.2015
comment
Спасибо, я думал о чем-то похожем/идентичном... но все же нужно посмотреть, может быть, кто-нибудь придет с какой-нибудь блестящей идеей. Кто-то с сильными математическими способностями может быть :) - person סטנלי גרונן; 02.10.2015

arrow_upward
2
arrow_downward

Насколько мне известно, 48-битных алгоритмов хеширования не существует. Также не существует 48-битных типов переменных, так что в любом случае это очень странный выбор дизайна.

И, конечно же, вы не можете без потерь сократить 64-битный хэш до 48-битного, а безопасное хэширование — это вообще отдельная тема. Вы можете сделать что-то вроде использования обычной 32-битной хеш-функции, такой как CRC32 или около того, и просто иметь 16 пустых битов. Или даже объединить 32-битную и 16-битную, но это кажется действительно очень странным. С точки зрения защиты от столкновений это даже не имеет значения, и я бы не хотел слышать ответ на этот вопрос от криптологически опытного человека.

Моя рекомендация: используйте установленные алгоритмы хеширования стандартного размера и не экспериментируйте. В любом случае, придумать хороший алгоритм хеширования уже достаточно сложно. Нет необходимости проявлять творческий подход, за исключением того, что вы являетесь экспертом в своей области и можете справиться с последствиями, которые могут иметь изменения (что, вероятно, является самой сложной частью).

person SkryptX    schedule 02.10.2015
comment
Кто вам сказал, что 48-битного типа переменной не существует? Существует множество компиляторов с родными 24/40/48-битными типами, например компиляторы TI или Motorola DSP5600x/3xx. Можно даже реализовать 48-битные переменные на 64-битных архитектурах. - person phuclv; 18.12.2017
comment
Я обнаружил, что 48-битные хэш-алгоритмы существуют, например, вы можете поискать в Интернете 48-битный хэш Bobcat. - person סטנלי גרונן; 20.12.2017