我有以下哈希函数,我试图让我的方法来反转它,以便我可以从哈希值中找到密钥.
uint Hash(string s)
{
uint result = 0;
for (int i = 0; i < s.Length; i++)
{
result = ((result << 5) + result) + s[i];
}
return result;
}
代码在C#中,但我认为很清楚.
我知道,对于一个散列值,可以有多个键,但我的意图不是找到它们,只需要满足散列函数就足够了.
编辑：
函数接受的字符串仅由数字0到9以及字符’*’和’#’组成,因此Unhash函数也必须遵守此条件.
有任何想法吗？谢谢.
解决方法
如果uint为32位,则强力应该有效.尝试至少2 ^ 32个字符串,其中一个可能会散列到相同的值.在现代电脑上只需几分钟.
你有12个可能的字符,12 ^ 9大约是2 ^ 32,所以如果你尝试9个字符串你很可能找到你的目标哈希.为了安全,我会做10个字符串.
(在C中简单的递归实现,不太了解C#)
#define NUM_VALID_CHARS 12
#define STRING_LENGTH 10
const char valid_chars[NUM_VALID_CHARS] = {'0',...,'#','*'};
void unhash(uint hash_value,char *string,int nchars) {
if (nchars == STRING_LENGTH) {
string[STRING_LENGTH] = 0;
if (Hash(string) == hash_value) { printf("%s\n",string); }
} else {
for (int i = 0; i < NUM_VALID_CHARS; i++) {
string[nchars] = valid_chars[i];
unhash(hash_value,string,nchars + 1);
}
}
}
然后用：
char string[STRING_LENGTH + 1]; unhash(hash_value,0);
