Простой, повторяемый хеш от UInt32 до UInt16

Question

У меня есть небольшая проблема, когда нужно сделать хэш из числа примерно 10 цифр в число из 6 цифр. Хеш должен быть детерминированным.

Более важно, что хеш не ресурсоемкий.

Например, скажем, что у меня есть какое-то число, х, как 123456789

Я хочу написать хеш-функцию, которая возвращает мне число y обратно как 987654.

Затем я хотел бы иметь функцию, которая принимает x и y в качестве параметров, повторно применяет хэш к x и проверяет, что результат равен y.

Должно быть трудно вычислить возможные входные значения, учитывая хеш.

Моя первая идея умножения пар цифр привела к множеству дублированных хэшированных значений.

У меня такое чувство, что у такого рода проблем есть какое-то элегантное решение, но я просто не могу думать об этом сам.

Может кто-нибудь помочь мне здесь? Заранее спасибо:)

Answer 1

То, что вам нужно, называется "хеширование".

Попробуйте CRC16.

Answer 2

Ваша проблема, как указано, не решаема.

Вы говорите, что хотите, чтобы система была "несколько трудно сломанной", и я предполагаю, что вы имеете в виду, что атакующему "довольно трудно" взять известный дайджест и получить из него возможный ввод, который хэширует данный дайджест. Поскольку в предлагаемой вами системе есть только 4 миллиарда возможных входов и только 65536 возможных хэшей, совершенно тривиально найти сообщение, соответствующее данному хешу, независимо от того, какой алгоритм хэширования используется . В среднем у злоумышленника будет около 65000 возможных сообщений на выбор, и поэтому он может выбрать сообщение, которое наилучшим образом соответствует его гнусной схеме.

Я ожидал бы, что "несколько трудная" проблема в области хэширования потребует, выделив, скажем, несколько миллионов долларов времени на работу суперкомпьютера. Ваше предложение может быть нарушено неопытными учениками старших классов, пишущими программы на Javascript, написание которых занимает пару минут и, возможно, минута, топы; это даже не очень близко к «несколько сложному».

Почему вы выбираете такие крошечные ограничения для вашего алгоритма, ограничения, которые по самой своей природе сделают тривиальным нарушение хеширования? И в этом отношении, каково значение хэширования такого небольшого количества данных, как 32-разрядное целое число?

Answer 3

((X >> 16) ^ (X)) & 0xFFFF

.......

Answer 4

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

ushort code = (ushort)value.ToString().GetHashCode();

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

Один простой алгоритм, который используется для хеш-кодов для некоторых значений в платформе, состоит в том, чтобы использовать исключительные значения или сделать так, чтобы все биты значения имели значение, когда хеш-код меньше данных:

byte[] b = BitConverter.GetBytes(value);
ushort code = (ushort)(BitConverter.ToUInt16(b, 0) ^ BitConverter.ToUInt16(b, 2));

или более эффективный, но менее очевидный способ сделать то же самое:

ushort code = (ushort)((value >> 16) ^ value);

Это, конечно, не имеет запутывающих свойств для небольших значений, поэтому вы можете добавить некоторые «случайные» биты, чтобы хэш-код значительно отличался от значения:

ushort code = (ushort)(0x56D4 ^ (value >> 16) ^ value);

Answer 5

Как насчет просто отбросить младшие 16 бит или последние 4 цифры?

1234567890 --> 123456

Легко сделать, просто сделав целочисленное деление на 10000.