Реверсивная хеш-функция?
Мне нужна обратимая хеш-функция (очевидно, вход будет намного меньше по размеру, чем выход), который отображает входной сигнал на вывод случайным образом. В принципе, я хочу, чтобы преобразовать число, подобное "123", в большее число, например "9874362483910978", но не таким образом, чтобы сохранить сравнения, поэтому не всегда должно быть верно, что если x1 > x2, f (x1 ) > f (x2) (но не всегда должно быть ложным).
В этом случае я должен найти способ преобразования небольших чисел в более крупные, случайные. На самом деле они не должны быть случайными (на самом деле они должны быть детерминированными, поэтому один и тот же ввод всегда сопоставляется с одним и тем же результатом), но они должны выглядеть случайными (по крайней мере, когда base64encoded в строки, поэтому сдвиг на Z биты не будут работать, так как похожие номера будут иметь похожие MSB).
Кроме того, простой (быстрый) расчет и разворот являются плюсом, но не требуются.
Я не знаю, ясно ли я, или если такой алгоритм существует, но я был бы признателен за любую помощь!
Ответы
Ответ 1
Ни один из представленных ответов не казался особенно полезным, учитывая этот вопрос. У меня была одна и та же проблема, требующая простой, обратимой хеш-функции для не-безопасности, и решил пойти с перемещением бит. Простейшим может быть:
def hash(n):
return ((0x0000FFFF & n)<<16) + ((0xFFFF0000 & n)>>16)
Это обратимо в том, что хэш (hash (n)) = n и имеет несекретные пары {n, m}, n < м, где хеш (м) хэш (п).
Чтобы получить менее последовательную реализацию, вы также можете рассмотреть переупорядочение чередования из [msb, z,..., a, lsb] в [msb, lsb, z, a,...] или [ lsb, msb, a, z,...] или любое другое перемещение, которое вы чувствуете, дает соответствующую последовательность, не соответствующую последовательности, с которой вы имеете дело.
(Вышеуказанная функция безопасна для чисел, которые соответствуют 32 битам, большее число гарантированно вызывает конфликты, и для предотвращения проблем потребуется еще немного покрытия маски для битов). Таким образом, 32 бита обычно достаточно для любого uid).
Ответ 2
То, что вы запрашиваете, - это шифрование. Блок-шифр в своем основном режиме работы, ECB, обратимо отображает входной блок на выходной блок того же размера. Блоки ввода и вывода могут быть интерпретированы как числа.
Например, AES представляет собой 128-битный блочный шифр, поэтому он отображает входной 128-разрядный номер на 128-разрядный номер вывода. Если 128 бит достаточно хороши для ваших целей, вы можете просто поместить свой входной номер на 128 бит, преобразовать этот одиночный блок с AES, а затем форматировать вывод как 128-битное число.
Если 128 бит слишком велико, вы можете использовать 64-битный блочный шифр, например 3DES, IDEA или Blowfish.
Режим ЕЦБ считается слабым, но его слабость - это ограничение, которое вы постулировали как требование (а именно, что отображение должно быть "детерминированным" ). Это слабость, потому что, как только злоумышленник заметил, что 123 карты на 9874362483910978, с тех пор, когда она видит последнее число, она знает, что открытый текст был 123. Злоумышленник может выполнять частотный анализ и/или создавать словарь известного открытого текста /ciphertext пар.
Ответ 3
Другим простым решением является использование мультипликативных обратных (см. блог Eri Clippert):
мы показали, как вы можете взять любые два взаимно простых натуральных числа x и m и вычислить третье положительное целое число y с тем свойством, что (x * y)% m == 1, и поэтому (x * z * y)% m == z% m для любого положительного целого z. То есть всегда существует "мультипликативный обратный", который "отменяет" результаты умножения на x по модулю m.
Возьмем большое число, например. 4000000000 и большое общее число, например. 387420489:
def rhash(n):
return n * 387420489 % 4000000000
>>> rhash(12)
649045868
Сначала вычислим мультипликативный обратный с modinv, который окажется 3513180409:
>>> 3513180409 * 387420489 % 4000000000
1
Теперь мы можем определить обратное:
def un_rhash(h):
return h * 3513180409 % 4000000000
>>> un_rhash(649045868) # un_rhash(rhash(12))
12
Примечание. Этот ответ быстро вычисляется и работает для чисел до 4000000000, если вам нужно обрабатывать большие числа, выберите достаточно большое число (и другое совместное задание).
Вы можете сделать это с помощью hexidecimal (для пакета int):
def rhash(n):
return "%08x" % (n * 387420489 % 4000000000)
>>> rhash(12)
'26afa76c'
def un_rhash(h):
return int(h, 16) * 3513180409 % 4000000000
>>> un_rhash('26afa76c') # un_rhash(rhash(12))
12
Если вы выберете относительно большое совместное праймер, тогда это будет казаться случайным, быть непоследовательным и также быстро вычислить.
Ответ 4
Почему не просто XOR с хорошим длинным номером?
Легко. Быстро. Реверсивный.
Или, если это не должно быть ужасно безопасным, вы можете конвертировать из базы 10 в некоторую меньшую базу (например, базу 8 или базовую 4, в зависимости от того, как долго вы хотите, чтобы номера были).
Ответ 5
В принципе, вы ищете двухстороннее шифрование и, возможно, использует salt.
У вас есть несколько вариантов:
Вот пример: Простой небезопасный двухсторонний "обфускация" для С#
На каком языке вы смотрите? Если .NET затем рассмотрит пространство имен шифрования для некоторых идей.
