我需要一个可逆的哈希函数(显然输入的大小要小于输出),它以一种随机的方式将输入映射到输出.基本上,我想要一种方法将像"123"这样的数字转换为更大的数字,如"9874362483910978",但不是以保留比较的方式,所以如果x1> x2,f(x1)则不能总是如此)> f(x2)(但也不一定总是假).
对此的用例是我需要找到一种方法将小数字转换为更大的,随机的数字.它们实际上并不需要是随机的(事实上,它们需要是确定性的,所以相同的输入总是映射到相同的输出),但它们确实需要看起来是随机的(至少当base64编码为字符串时,所以移位Z位将无法工作,因为类似的数字将具有类似的MSB).
此外,简单(快速)计算和反转是一个加号,但不是必需的.
我不知道我是否清楚,或者是否存在这样的算法,但我会感激任何帮助!
Mik*_*ans 38
鉴于这个问题,所提供的答案似乎都没有特别有用.我有同样的问题,需要一个简单的,可逆的哈希用于非安全目的,并决定使用位重定位.它很简单,速度很快,并且不需要了解布尔数学或crypo算法或任何其他需要实际思考的内容.
最简单的可能是向左移动一半,另一半向右移动:
def hash(n):
return ((0x0000FFFF & n)<<16) + ((0xFFFF0000 & n)>>16)
这是可逆的,因为散列(hash(n))= n,并且具有非顺序对{n,m},n <m,其中hash(m)<hash(n).
为了获得不那么顺序的实现,您可能还需要考虑从[msb,z,...,a,lsb]到[msb,lsb,z,a,...]或[lsb,msb]的交错重新排序,a,z,...]或您认为的任何其他重定位为您处理的数字提供了一个适当的非连续序列.
(上述函数对于适合32位的数字是安全的,更大的数字保证会引起冲突,并且需要更多位掩码覆盖以防止出现问题.也就是说,对于任何非安全uid,32位通常就足够了).
另请参阅下面的Andy Hayden给出的乘法逆答案.
caf*_*caf 16
你要的是加密.处于其基本操作模式的块密码ECB可逆地将输入块映射到相同大小的输出块.输入和输出块可以解释为数字.
例如,AES是128位分组密码,因此它将输入128位数映射到输出128位数.如果128位足以满足您的需要,那么您只需将输入数字填充到128位,使用AES转换该单个块,然后将输出格式化为128位数.
如果128位太大,您可以使用64位分组密码,如3DES,IDEA或Blowfish.
ECB模式被认为是弱的,但它的弱点是你假定为一个要求的约束(即,映射是"确定性的").这是一个弱点,因为一旦攻击者观察到123映射到9874362483910978,从那时起每当她看到后一个数字时,她就知道明文是123.攻击者可以执行频率分析和/或建立已知明文的字典/密文对.
And*_*den 14
另一个简单的解决方案是使用乘法逆(参见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的数字.
您可能希望使用十六进制(以打包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
如果你选择一个相对较大的共同素数,那么这将是随机的,非顺序的,也可以快速计算.