可逆散列函数? [英] Reversible hash function?

问题描述

我需要一个可逆散列函数(显然输入的大小将比输出小得多)以随机方式将输入映射到输出.基本上，我想要一种将123"之类的数字转换为9874362483910978"之类的更大数字的方法，但不是以保留比较的方式，因此，如果 x1 > x2，f(x1) > f(x2)(但也不能总是假).

I need a reversible hash function (obviously the input will be much smaller in size than the output) that maps the input to the output in a random-looking way. Basically, I want a way to transform a number like "123" to a larger number like "9874362483910978", but not in a way that will preserve comparisons, so it must not be always true that, if x1 > x2, f(x1) > f(x2) (but neither must it be always false).

这个用例是我需要找到一种方法将小数字转换为更大的、看起来随机的数字.它们实际上并不需要是随机的(事实上，它们需要是确定性的，因此相同的输入总是映射到相同的输出)，但它们确实需要看起来随机(至少在 base64encoded 时)转换成字符串，因此移动 Z 位将不起作用，因为相似的数字将具有相似的 MSB).

The use case for this is that I need to find a way to transform small numbers into larger, random-looking ones. They don't actually need to be random (in fact, they need to be deterministic, so the same input always maps to the same output), but they do need to look random (at least when base64encoded into strings, so shifting by Z bits won't work as similar numbers will have similar MSBs).

此外，简单(快速)计算和反转是一个优点，但不是必需的.

Also, easy (fast) calculation and reversal is a plus, but not required.

我不知道我是否清楚，或者是否存在这样的算法，但我希望得到任何帮助！

I don't know if I'm being clear, or if such an algorithm exists, but I'd appreciate any and all help!

推荐答案

鉴于问题，所提供的答案似乎都不是特别有用.我遇到了同样的问题，出于非安全目的需要一个简单的可逆散列，并决定进行位重定位.它很简单，速度很快，而且不需要了解布尔数学或密码算法或任何其他需要实际思考的知识.

None of the answers provided seemed particularly useful, given the question. I had the same problem, needing a simple, reversible hash for not-security purposes, and decided to go with bit relocation. It's simple, it's fast, and it doesn't require knowing anything about boolean maths or crypo algorithms or anything else that requires actual thinking.

最简单的可能是只向左移动一半位，另一半向右移动:

The simplest would probably be to just move half the bits left, and the other half right:

def hash(n):
  return ((0x0000FFFF & n)<<16) + ((0xFFFF0000 & n)>>16)

这是可逆的，因为 hash(hash(n)) = n，并且有非序列对 {n,m}，n

This is reversible, in that hash(hash(n)) = n, and has non-sequential pairs {n,m}, n < m, where hash(m) < hash(n).

为了获得更少顺序的实现，您可能还需要考虑从 [msb,z,...,a,lsb] 到 [msb,lsb,z,a,...] 或 [lsb,msb,a,z,...] 或您认为的任何其他重定位为您处理的数字提供了适当的非顺序序列，甚至在其上添加 XOR 以使其看起来更不连续.

To get a less sequential looking implementation, you might also want to consider an interlace reordering from [msb,z,...,a,lsb] to [msb,lsb,z,a,...] or [lsb,msb,a,z,...] or any other relocation you feel gives an appropriately non-sequential sequence for the numbers you deal with, or even add a XOR on top of that to make it look even less sequential.

(上述函数对于适合 32 位的数字是安全的，较大的数字肯定会导致冲突，并且需要更多的位掩码覆盖以防止出现问题.也就是说，对于任何非安全 uid，32 位通常就足够了).

(The above function is safe for numbers that fit in 32 bits, larger numbers are guaranteed to cause collisions and would need some more bit mask coverage to prevent problems. That said, 32 bits is usually enough for any non-security uid).

另请参阅下面安迪·海登 (Andy Hayden) 给出的乘法逆答案.

Also have a look at the multiplicative inverse answer given by Andy Hayden, below.

这篇关于可逆散列函数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！