logo标签列表

最适合哈希数值的算法是什么？

algorithmdelphihashnumbers
12

在处理一系列数字并希望出于安全考虑使用哈希结果时，从给定的数字序列生成哈希值的最佳方法是什么？输入示例可以是信用卡号码或银行帐号。首选输出将是一个无符号整数，以帮助匹配。

我认为大多数字符串实现在针对这样一个短字符范围运行时似乎具有较低的熵，因此碰撞率可能会比针对更大样本运行时高。

目标语言是Delphi，但如果其他语言能提供可以导致最优解决方案的数学基础，则欢迎回答。

该程序的目的是确定先前接收的卡/帐户是否已经被处理。输入文件可能针对多条记录与多条记录的数据库，因此性能是一个因素。

重新阅读您的问题...您想要对哈希做什么？您提到了安全原因，但问题的其余部分听起来有点像哈希表查找。或者您想执行输入验证 - 一种校验和？ - Daniel Brückner
我不确定一个单独的整数是否提供足够的空间来满足此需求。对于16位信用卡号码，您将会遇到冲突（10^16 >> 2^32）。在发生冲突时，您该怎么办？这是一种软性故障吗？它会在其他地方处理，从而抵消了可能提供的性能改进吗？ - Will Bickford
最优是根据什么标准来衡量的？计算速度？内存占用？攻击难度？可移植性？ - Rob Kennedy
为了我的目的，我很可能还会结合其他信息来帮助识别不当的碰撞。我试图找到最佳算法以获得相当均匀的哈希值分布。由于字母没有被考虑在内，我想知道是否有更好的方法来哈希数字。 - skamradt
@Rob，计算速度。由于存在重要数字的损失，如果解决为整数，则安全性并不是真正的问题。 - skamradt
显然并不存在10^16个信用卡账户。据我回忆，前8位数字所包含的信息非常少 - 你能利用这一点来简化吗？ - Argalatyr
8个回答
12

安全问题的答案可以从最安全到最方便的“连续性”中选择。我给你两个答案，一个非常安全，一个非常方便。根据每个答案的解释，你可以为你的系统选择最佳解决方案。

你提到你的目标是将这个值存储起来，代替实际的信用卡，以便日后知道是否再次使用相同的信用卡号码。这意味着它必须仅包含信用卡号码和可能的一致的盐。如果包括CCV，过期日期，姓名等信息，它将变得无用，因为对于相同的信用卡号码，它们的值可能不同。因此，我们假设你将所有信用卡号码都用相同的盐值填充，这个盐值在所有条目中保持一致。

方便的解决方案是使用FNV（如Zebrabox和Nick建议的那样）。这将产生一个32位数字，可以快速索引搜索。当然，缺点是它最多只允许4十亿个不同的数字，并且在实践中会更快地产生冲突。由于它具有如此高的碰撞率，暴力攻击可能会产生足够的无效结果，使其几乎没有用处。

安全的解决方案是依靠SHA哈希函数（越大越好），但是要进行多次迭代。我建议大约进行1万次迭代。是的，我知道，10000次迭代很多，而且需要一段时间，但是在对抗暴力攻击时，速度是敌人。如果你想要安全，那么你希望它是慢的。SHA被设计为对于任何输入大小都不会发生碰撞。如果发现碰撞，则认为哈希不再可用。据我所知，SHA-2系列仍然可用。

如果您想要一个安全且快速的解决方案来搜索数据库，那么我建议使用安全解决方案（SHA-2 x 10K），然后将完整哈希值存储在一个列中，并将前32位存储在另一列中，并在第二列上创建索引。首先执行对32位值的查找。如果没有匹配项，则没有匹配项。如果它确实产生了匹配项，那么您可以比较完整的SHA值并查看它是否相同。这意味着您正在对一个更小的集合执行完整的二进制比较（哈希实际上是二进制的，但仅表示为字符串以便于人类阅读并进行基于文本的协议传输）。
如果您真的关心速度，那么您可以减少迭代次数。即使有1000次迭代，也会非常快。您需要对您预期数据库变得多大以及其他因素（通信速度、硬件响应、负载等）做出一些现实判断，这可能会影响持续时间。您可能会发现自己在优化过程中的“最快点”，但实际上几乎没有任何影响。
此外，我建议您对完整哈希和32位子集的查找进行基准测试。大多数现代数据库系统都非常快，并包含许多优化，通常优化我们以“简单”方式执行任务的方式。当我们试图变得聪明时，有时只会减慢速度。还记得那句关于过早优化的话吗？
好的建议，除了CRC32根本不是这种情况下的好哈希函数。它旨在检测传输错误，并且在这方面表现良好，但并不保证碰撞率。像FNV32这样的非加密哈希将是更好的选择。 - Nick Johnson
我最终使用了一个SHA实现，它似乎是无碰撞的。 - skamradt
理论上，SHA不是防碰撞的。但在实践中，它是防碰撞的。我们可以说成功的几率非常高。 - Jim McKeeth
32位不是给你大约40亿个数字吗？比65536大一点点吧？或者我漏看了什么明显的东西？顺便说一句，回答得很好。 - Alister
@Alister，你说得对。我会更新我的答案。 - Jim McKeeth
6

这似乎是一个关于密钥派生函数的案例。请查看PBKDF2。

仅使用加密哈希函数（如SHA系列）可以给您所需的分布，但对于非常有限的输入空间（如信用卡号码），它们很容易受到暴力攻击，因为这些哈希算法通常设计得尽可能快。

更新

好吧，安全对于您的任务不是问题。因为您已经有一个数字输入，所以可以将此（账户）号码模数哈希表大小。如果将其处理为字符串，则可能确实会遇到糟糕的分布，因为十个数字仅形成所有可能字符的一小部分子集。

另一个问题可能是数字形成大量已分配（账户）号码的聚集区域，并在它们之间留下大片未分配的数字区域。在这种情况下，我建议尝试高度非线性的哈希函数来扩散这些聚集区域。这让我们回到了加密哈希函数。也许是老好人MD5。只需将128位哈希分为四组32位，使用XOR将它们组合起来，并将结果解释为32位整数。

虽然不是直接相关的，但您也可以查看本福德定律 - 它提供了一些关于为什么数字通常不均匀分布的见解。

有趣的是，但对于 PBKDF2，最少循环 1000 次并不像对我来说是最优的。 - skamradt
3
如果您需要用于安全关键操作的哈希值，请不必担心执行时间。时间是攻击者的敌人。如果您不需要进行安全关键操作，PBKDF2 可能并不是最好的选择。 - Daniel Brückner
3

如果您需要安全性，请使用加密安全哈希算法，例如SHA-256。

1
理想情况下，结果应该是一个整数。SHA-256 对我的使用有些过度了。 - skamradt
对于短输入，简单的加密哈希函数过于简单，因为它们很容易受到暴力攻击。 - Daniel Brückner
建议使用像scrypt这样的派生函数使计算更困难。整数大小的输出将在约65k个条目处产生冲突。并且这还没有考虑到可能会因舍弃输出部分而导致的可能的密码分析攻击。 - Ants Aasma
信用卡号码有17位及以上（日期有限制，我甚至不会给它们两位数的数据）。这很难被暴力破解。至于SHA-256是否过于复杂 - 使用它，然后通过XOR将块缩小到你决定使用的任何大小。 - Loren Pechtel
@Daniel：问题不在于函数，而在于输入。没有任何算法可以神奇地将可枚举范围变成不可枚举范围。你所能做的就是利用最好的原语（在这种情况下是安全哈希），并为了额外的安全性进行迭代。 - Nick Johnson
2
如果性能是一个因素，我建议看一下Peter Below的CodeCentral entry。它对于大量项目的表现非常好。
默认情况下，它使用P.J. Weinberger ELF 哈希函数。但也提供了其他选项。
2

几个月前，我需要深入了解哈希函数。以下是我发现的一些内容。

您希望哈希在整个目标空间（通常为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并发布了它。”

散列函数的故事继续：
2007-03-13 Andrew: 当坏的散列意味着好的缓存
www.team5150.com/~andrew/blog/2007/03/hash_algorithm_attacks.html
2007-03-29 Andrew: 打破SuperFastHash
floodyberry.wordpress.com/2007/03/29/breaking-superfasthash/
2008-03-03 Austin Appleby: MurmurHash 2.0
murmurhash.googlepages.com/
SuperFastHash-985.335173 mb/sec
lookup3-988.080652 mb/sec
MurmurHash 2.0-2056.885653 mb/sec
提供c++代码MurmurrHash2.cpp和对齐只读实现-MurmurHashAligned2.cpp
//========================================================================
//以下是Landman's MurmurHash2的C#代码
//2009-02-25 Davy Landman在SuperFashHash和MurmurHash2中执行C#实现
//landman-code.blogspot.com/search?updated-min=2009-01-01T00%3A00%3A00%2B01%3A00&updated-max=2010-01-01T00%3A00%3A00%2B01%3A00&max-results=2
//
//Landman使用C#实现了四种方式的SuperFastHash和MurmurHash2：
//1：托管代码 2：内联位转换器 3：Int Hack 4：不安全指针
//SuperFastHash 1：281 2：780 3：1204 4：1308 MB/s
//MurmurHash2 1：486 2：759 3：1430 4：2196

抱歉，如果上述内容看起来很混乱。 我只能复制粘贴它。

以上引用中至少有一种方法可以输出64位哈希值，在信用卡号码空间中肯定没有冲突，并且可以轻松存储在MySQL的bigint字段中。

您不需要加密散列函数。 它们需要更多的CPU资源。 而“加密”的目的是防止黑客攻击，而不是避免冲突。

1

根据定义，加密哈希对于您的用例非常适用。即使字符相似，哈希值也应该分布良好。

因此，我建议您使用任何加密哈希（例如SHA-256），并加入盐。

对于较短的输入，简单的加密哈希函数过于简单，因为它们很容易受到暴力攻击。 - Daniel Brückner
1

对于非加密方法，您可以查看FNV哈希，它速度快，冲突率低。

作为一种非常快速的替代方案，我也使用了这个算法几年，并且很少出现冲突问题，但我无法给出其固有健全性的数学分析，但就其价值而言，这里是它

=编辑 - 我的代码示例不正确 - 现已修复=

在c/c++中

unsigned int Hash(const char *s)
{
    int hash = 0;

    while (*s != 0)
    {
        hash *= 37;
            hash += *s;
        s++;
    }

    return hash;
}

请注意，'37'是一个魔数，因为它是质数而被选择。
这个看起来很有前途，没有任何分析。你可能想指出37是一个可选参数（必须是质数）。 - Will Bickford
你发布的代码与提供的链接中的代码不匹配。链接中的代码使用异或运算，而不是加法，并将哈希乘以质数值，而不仅仅是对被哈希的每个字节进行操作。 - Rob Kennedy
@Rob Kennedy。代码示例与链接无关 - 它们完全不同。我提供代码示例作为快速替代方案。 - zebrabox
0

自然数的最佳哈希函数为

 f(n)=n

没有冲突 ;)

(-1)因为这个答案只包含幽默。别误会，我是一个经常阅读Slashdot的读者——喜欢那里的幽默评论！——但我认为这种东西不适合在这里出现。请参见[此讨论][1]。 [1]: http://meta.stackexchange.com/questions/17782/why-do-stackers-consistently-vote-down-humorous-responses - paprika
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接