Реверсивная хеш-функция?

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

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

TripleDES
AES

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

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