Обратимая хеш-функция?

Question

Мне нужна обратимая хеш-функция (очевидно, что вход будет намного меньше по размеру, чем выход), который отображает вход в выход случайным образом.По сути, я хочу, чтобы был способ преобразования числа типа «123» в большее число, например «9874362483910978», но не таким образом, чтобы сохранить сравнения, поэтому не всегда должно быть так, что, если x1> x2, f (x1))> f (x2) (но не всегда должно быть ложным).

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

Кроме того, простой (быстрый) расчет и обращение является плюсом, но не обязательным.

Iне знаю, насколько я ясен, или такой алгоритм существует, но я был бы признателен за любую помощь!

Answer 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 бита обычно достаточно для любого пользователя, не связанного с безопасностью).

Также взгляните на мультипликативный обратный ответ, данный Энди Хейденом, ниже.

Answer 2

То, что вы запрашиваете , - это шифрование. Блочный шифр в своем основном режиме работы, ECB, обратимо отображает входной блок на выходной блок того же размера. Блоки ввода и вывода можно интерпретировать как числа.

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

Если 128 бит слишком велик, вы можете использовать 64-битный блочный шифр, например 3DES, IDEA или Blowfish.

Режим ECB считается слабым, но его слабость является ограничением, которое вы постулировали как требование (а именно, что отображение должно быть "детерминированным"). Это слабое место, поскольку после того, как злоумышленник заметил, что 123 соответствует 9874362483910978, с тех пор всякий раз, когда он видит последнее число, он знает, что открытым текстом было 123. Злоумышленник может выполнить частотный анализ и / или создать словарь известного открытого текста. / шифротекстовые пары.

Answer 3

Другое простое решение - использовать мультипликативные инверсии (см. Блог Эри Клипперт) :

мы показали, как вы можете взять любые два взаимно простых положительных целых числа 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, если вам нужно обрабатывать большие числа, выберите достаточно большое число (и другое двойное число).

---

Вы можете сделать это с шестнадцатеричной (для упаковки 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

Если вы выберете относительно большое сопростое число, тогда оно будет казаться случайным, непоследовательным, а также быстрым для вычисления.

Answer 4

Почему бы не просто XOR с красивым длинным номером?

Легко.Быстро.Обратимый.

Или, если это не требует особой безопасности, вы можете конвертировать из базы 10 в какую-то меньшую базу (например, базу 8 или базу 4, в зависимости от того, как долго вы хотите, чтобы числа были).

Answer 5

По сути, вы ищете 2-х стороннее шифрование, и, вероятно, использует salt.

У вас есть несколько вариантов:

1. TripleDES
2. AES

Вот пример: " Простая небезопасная двусторонняя" обфускация "для C #

На каком языке вы смотрите? Если .NET, то посмотрите на пространство имен шифрования для некоторых идей.