这里介绍knuth multiplicative法

公式思路如下

this_hash=( (R*last_hash).operateX( f(Magic_Num, this_block) ) ) % M

看似有点复杂,我们一步步讲,保证0基础看懂

operateX指的是某种运算,可以是加减乘除四则运算,也可以是位运算,也可以是更复杂的运算组合

这个运算的左操作数为R*last_hash,右操作数为函数f()的返回值

函数f的参数:

Magic_Num不多说,随意定的一个值就行

this_block是本轮hash加密的加密块的内容

M是hash表的表长

这里分为三个理解阶段,在数学上并不严谨,但对我们的理解非常有帮助

首先我们规定,待处理的原数据是长度和内容随机的字符串

字符范围为大小写字母和十个阿拉伯数字,以ASCII表示

接下来我们举一个用上面公式衍生出来的例子

//main.cpp
int hash = 0; //这里我们应当将hash变量理解为计数器
//这里的计数器指的是计算从自然数N累加到自然数M这一操作所需的那个中间变量;而非计数器这一数据结构
for(int i = 0; i<strlen ; i++){
 hash = (R *hash + Str[i] ) % M
}

本例当中略去magic_Num

第一个理解阶段:

我们先把M看作是足够大的,也就说对M的模永远等于这个数本身,同时我们把str中的每一个字符的ASCII码都看作是小于10的,同时令R为10

此时,hash值等价于原字符串的十进制形式,画图如下

第二个理解阶段:

由于ASCII值并非小于10(前面已经说了字符范围)

因此我们假设R为128(只要大于字符串当中,ASCII意义上的最大字符就行,是多少无所谓)

此时算出来的值相当于128进制的整数

第三个理解阶段:

把M理解为一个并非足够大的数,这样可以做到"扩散"

比如:

字符串A = "abcdefg"

字符串B = "abcdeff"

如果M足够大,我们会发现A和B的hash值几乎是相同的,即,只有图中的Y会受到改变

而我们希望元数据中,改变任意一位,最终的hash值会改变50%以上(一种安全性的考量,50%这个值的证明本文略过)

因此我们会在每一轮运算中加入取模

如果改变的这一位出现在字符串的前50%的位置,则目标可以因此轻易达成(可以照着上面的流程图过一下,很容易推导)

如果出现在后50%的位置,则我们无法达成这一目标,主要原因在于我们的block分块的顺序,是完全按照元数据顺序的,且一个block内只有一位字符的内容

这里有多种做法,最简单常见的做法是:让每个block的内容是元数据当中多个乱序区域的内容的直接或间接的集合,比如第一个字符和倒数第一个字符组成一个block,然后第二个和倒数第二个字符组合起来

如果字符长度是奇数则填充为偶数,等等

不过这些细节实现就可以自由发挥了

至此结束

参考资料

https://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec21.html

https://stackoverflow.com/questions/11871245/knuth-multiplicative-hash

《Algorithms 4th》

欢迎交流，www.ksroido.art

未经许可禁止转载

[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界