代码之家 › 专栏 › 技术社区 › skamradt

散列数值的最佳算法?

numbers hash delphi algorithm

skamradt · 技术社区 · 17 年前

在处理一系列数字时,为了安全起见,希望使用哈希结果,从给定的数字序列生成哈希值的最佳方法是什么?输入的示例是信用卡号或银行账号。首选输出为单个无符号整数,以帮助进行匹配。

我的感觉是,当运行在如此短的字符范围内时,大多数字符串实现似乎具有低熵,因此,冲突率可能比运行在更大样本上时更高。

目标语言是Delphi,但是如果其他语言能够提供数学基础,从而得出最佳解决方案,则欢迎使用其他语言的答案。

此例行程序的目的是确定先前收到的卡/账户是否已被预先处理。输入文件可能有多个记录,而数据库中有多个记录,因此性能是一个因素。

8 回复 | 直到 17 年前

Jim McKeeth 17 年前

关于安全问题,所有答案都取决于 连续体 从…起 最安全的 到 最方便 . 我给你两个答案,一个非常安全,另一个非常方便。考虑到这一点以及每个问题的解释,您可以为您的系统选择最佳解决方案。

您表示,您的目标是存储此值以代替实际的信用卡,以便稍后知道是否再次使用相同的信用卡号。这意味着它必须只包含信用卡号码,可能还包含一个统一的盐。包含CCV、到期日期、名称等将使其无效,因为它的值可能与同一信用卡号不同。因此,我们假设您将所有信用卡号填充为相同的salt值,这将在所有条目中保持一致。

这个 方便的解决方案 就是使用 FNV

这个是依赖SHA哈希函数(越大越好),但需要多次迭代。我建议在10000左右。是的,我知道,10000次迭代非常多,这需要一段时间,但是当涉及到对抗蛮力攻击的力量时,速度是敌人。如果你想要安全,那么你就希望它是缓慢的。SHA被设计为对任何大小的输入都没有冲突。如果发现冲突,则认为哈希不再可行。AFAIK SHA-2系列仍然可行。

安全快捷 要在数据库中搜索,我建议使用安全解决方案(SHA-2 x 10K),然后将完整哈希存储在一列中,然后获取前32位并将其存储在另一列中,索引位于第二列。首先对32位值执行查找。如果没有产生匹配项,那么就没有匹配项。如果它确实产生了一个匹配,那么您可以比较完整的SHA值,看看它是否相同。这意味着您要在更小的集合上执行完整的二进制比较(散列实际上是二进制的,但仅表示为字符串,以便于人类阅读和在基于文本的协议中传输)。

如果你真的关心速度,那么你可以减少迭代次数。坦率地说,即使有1000次迭代,它仍然很快。您需要对数据库的预期大小以及可能影响持续时间的其他因素(通信速度、硬件响应、负载等)做出一些现实的判断。您可能会发现您的优化 最快点

另外,我建议你基准 容易的 方法当我们试图变得聪明时,我们有时只是放慢速度。关于过早优化的那句话是什么?

Daniel Brückner 17 年前

这似乎是一个很好的例子 key derivation functions . 看看 PBKDF2 .

仅使用加密散列函数(如SHA系列)即可获得所需的分布,但对于非常有限的输入空间(如信用卡号),它们很容易受到暴力攻击,因为这种散列算法通常设计为尽可能快。

使现代化

另一个问题可能是,这些数字形成了分配(帐户)数字的大簇,它们之间有很大的未分配数字区域。在这种情况下,我建议尝试使用高度非线性的散列函数来扩展这些集群。这让我们回到加密散列函数。也许是好的旧MD5。只需将128位散列分成四组,每组32位,使用XOR组合,并将结果解释为32位整数。

虽然没有直接关系,但你也可以看看 Benford's law

Ants Aasma 17 年前

如果需要安全性,请使用加密安全哈希,如SHA-256。

Guy Gordon 17 年前

几个月前,我需要深入研究散列函数。这是我找到的一些东西。

您希望散列在整个目标空间(通常为32位,但可以是16位或64位)中均匀、随机地分布命中数。您希望输入的每个字符都对输出产生同样大的影响。

但是在Delphi和asm中有一些非常好的算法可用。以下是一些参考资料:

见1997年Dobbs博士在burtleburtle.net/bob/hash/doobs.html上的文章

SuperFashish函数c2004-2008作者:Paul Xieh(又名Xiehhash)
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哈希,但也注意到我最近发现了一个更好的散列函数。它被称为超级灰烬(SFH) 鲍勃·詹金斯。Juhani问是否有人可以在basm中编写SFH函数。一些人参与了basm实现并发布了它。”

散列传奇继续:
2007-03-13安德鲁:什么时候坏的散列意味着好的缓存

2007-03-29安德鲁:打破超级灰烬
floodyberry.wordpress.com/2007/03/29/breaking-Superfash/
2008-03-03奥斯汀·阿普尔比:2.0

超级灰烬-985.335173 mb/秒
查找3-988.080652 mb/秒
2.0-2056.885653 mb/秒
提供C++代码PHMURHRAH2.CPP和对齐只读实现
杂音2.cpp
//========================================================================

//2009年02月25日戴维·兰德曼(Davy Landman)实现了超级哈希和杂音哈希2

//
//Landman在C#中实现了SuperFashhash和Murruhash2 4种方式:
//1:托管代码2:内联位转换器3:Int Hack 4:不安全指针
//超级高速缓存1:2812:7803:12044:1308MB/s

上面至少有一个引用为您提供了获取64位散列的选项,该散列肯定不会在信用卡号空间中发生冲突,并且可以轻松地存储在MySQL中的bigint字段中。

您不需要加密哈希。它们的CPU密集度更高。“加密”的目的是阻止黑客攻击,而不是避免冲突。

BenMorel Manish Pradhan 12 年前

CodeCentral entry

默认情况下,它使用P.J.Weinberger ELF hashing function . 但也提供了其他服务。

tonfa 17 年前

因此,我建议您使用任何加密哈希(例如SHA-256)和salt。

zebrabox 17 年前

FNV hash 它速度快,碰撞率低。

作为一个非常快速的替代方案,我也使用了这个算法好几年了,几乎没有碰撞问题,但是我不能给你一个数学分析,它的内在可靠性,但它的价值在这里

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

以信用证支付++

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

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

    return hash;
}

请注意,“37”是一个幻数,之所以选择它是因为它是素数

ldog 17 年前

自然数let的最佳散列函数

 f(n)=n

没有冲突;)