在处理一系列数字并希望出于安全考虑使用哈希结果时,从给定的数字序列生成哈希值的最佳方法是什么?输入示例可以是信用卡号码或银行帐号。首选输出将是一个无符号整数,以帮助匹配。
我认为大多数字符串实现在针对这样一个短字符范围运行时似乎具有较低的熵,因此碰撞率可能会比针对更大样本运行时高。
目标语言是Delphi,但如果其他语言能提供可以导致最优解决方案的数学基础,则欢迎回答。
该程序的目的是确定先前接收的卡/帐户是否已经被处理。输入文件可能针对多条记录与多条记录的数据库,因此性能是一个因素。
在处理一系列数字并希望出于安全考虑使用哈希结果时,从给定的数字序列生成哈希值的最佳方法是什么?输入示例可以是信用卡号码或银行帐号。首选输出将是一个无符号整数,以帮助匹配。
我认为大多数字符串实现在针对这样一个短字符范围运行时似乎具有较低的熵,因此碰撞率可能会比针对更大样本运行时高。
目标语言是Delphi,但如果其他语言能提供可以导致最优解决方案的数学基础,则欢迎回答。
该程序的目的是确定先前接收的卡/帐户是否已经被处理。输入文件可能针对多条记录与多条记录的数据库,因此性能是一个因素。
安全问题的答案可以从最安全到最方便的“连续性”中选择。我给你两个答案,一个非常安全,一个非常方便。根据每个答案的解释,你可以为你的系统选择最佳解决方案。
你提到你的目标是将这个值存储起来,代替实际的信用卡,以便日后知道是否再次使用相同的信用卡号码。这意味着它必须仅包含信用卡号码和可能的一致的盐。如果包括CCV,过期日期,姓名等信息,它将变得无用,因为对于相同的信用卡号码,它们的值可能不同。因此,我们假设你将所有信用卡号码都用相同的盐值填充,这个盐值在所有条目中保持一致。
方便的解决方案是使用FNV(如Zebrabox和Nick建议的那样)。这将产生一个32位数字,可以快速索引搜索。当然,缺点是它最多只允许4十亿个不同的数字,并且在实践中会更快地产生冲突。由于它具有如此高的碰撞率,暴力攻击可能会产生足够的无效结果,使其几乎没有用处。
安全的解决方案是依靠SHA哈希函数(越大越好),但是要进行多次迭代。我建议大约进行1万次迭代。是的,我知道,10000次迭代很多,而且需要一段时间,但是在对抗暴力攻击时,速度是敌人。如果你想要安全,那么你希望它是慢的。SHA被设计为对于任何输入大小都不会发生碰撞。如果发现碰撞,则认为哈希不再可用。据我所知,SHA-2系列仍然可用。
如果您想要一个安全且快速的解决方案来搜索数据库,那么我建议使用安全解决方案(SHA-2 x 10K),然后将完整哈希值存储在一个列中,并将前32位存储在另一列中,并在第二列上创建索引。首先执行对32位值的查找。如果没有匹配项,则没有匹配项。如果它确实产生了匹配项,那么您可以比较完整的SHA值并查看它是否相同。这意味着您正在对一个更小的集合执行完整的二进制比较(哈希实际上是二进制的,但仅表示为字符串以便于人类阅读并进行基于文本的协议传输)。仅使用加密哈希函数(如SHA系列)可以给您所需的分布,但对于非常有限的输入空间(如信用卡号码),它们很容易受到暴力攻击,因为这些哈希算法通常设计得尽可能快。
更新
好吧,安全对于您的任务不是问题。因为您已经有一个数字输入,所以可以将此(账户)号码模数哈希表大小。如果将其处理为字符串,则可能确实会遇到糟糕的分布,因为十个数字仅形成所有可能字符的一小部分子集。
另一个问题可能是数字形成大量已分配(账户)号码的聚集区域,并在它们之间留下大片未分配的数字区域。在这种情况下,我建议尝试高度非线性的哈希函数来扩散这些聚集区域。这让我们回到了加密哈希函数。也许是老好人MD5。只需将128位哈希分为四组32位,使用XOR将它们组合起来,并将结果解释为32位整数。
虽然不是直接相关的,但您也可以查看本福德定律 - 它提供了一些关于为什么数字通常不均匀分布的见解。
如果您需要安全性,请使用加密安全哈希算法,例如SHA-256。
几个月前,我需要深入了解哈希函数。以下是我发现的一些内容。
您希望哈希在整个目标空间(通常为32位,但也可能是16位或64位)中均匀随机地分布。您希望输入的每个字符对输出产生同样大的影响。
所有简单的哈希函数(如ELF或PJW),只需循环遍历字符串并使用移位或模运算将每个字节与XOR结合起来,就会因一个简单的原因而无法满足这个标准:添加的最后几个字符具有最大的影响力。
但是在Delphi和asm中有一些非常好的算法。以下是一些参考资料:
请参见1997年Dr. Dobbs文章burtleburtle.net/bob/hash/doobs.html
代码在burtleburtle.net/bob/c/lookup3.c
SuperFastHash Function c2004-2008由Paul Hsieh创建(也称为HsiehHash)
www.azillionmonkeys.com/qed/hash.html
您将在此引用中找到Delphi(可选asm)源代码:
http://landman-code.blogspot.com/2008/06/superfasthash-from-paul-hsieh.html
2008年7月13日
“一年多以前,Juhani Suhonen要求快速哈希表使用的快速哈希。我建议使用旧的但表现良好的elf-hash,但也注意到最近发现了一个更好的哈希函数。它被称为SuperFastHash(SFH),由Paul Hsieh创建,以克服他对Bob Jenkins的哈希函数的“问题”。Juhani问是否有人可以用basm编写SFH函数。一些人致力于实现basm并发布了它。”
抱歉,如果上述内容看起来很混乱。 我只能复制粘贴它。
以上引用中至少有一种方法可以输出64位哈希值,在信用卡号码空间中肯定没有冲突,并且可以轻松存储在MySQL的bigint字段中。
您不需要加密散列函数。 它们需要更多的CPU资源。 而“加密”的目的是防止黑客攻击,而不是避免冲突。
根据定义,加密哈希对于您的用例非常适用。即使字符相似,哈希值也应该分布良好。
因此,我建议您使用任何加密哈希(例如SHA-256),并加入盐。
对于非加密方法,您可以查看FNV哈希,它速度快,冲突率低。
作为一种非常快速的替代方案,我也使用了这个算法几年,并且很少出现冲突问题,但我无法给出其固有健全性的数学分析,但就其价值而言,这里是它
=编辑 - 我的代码示例不正确 - 现已修复=
在c/c++中
unsigned int Hash(const char *s)
{
int hash = 0;
while (*s != 0)
{
hash *= 37;
hash += *s;
s++;
}
return hash;
}
自然数的最佳哈希函数为
f(n)=n
没有冲突 ;)