首页
论坛
课程
招聘
[原创]如何设计简易的抗弱碰撞哈希函数
2021-11-12 13:30 15083

[原创]如何设计简易的抗弱碰撞哈希函数

2021-11-12 13:30
15083


这里介绍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值等价于原字符串的十进制形式,画图如下

IBqGaq.jpg


第二个理解阶段:

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

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

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

IBqTot.jpg

第三个理解阶段:

把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

未经许可禁止转载


【公告】看雪招聘大学实习生!看雪20年安全圈的口碑,助你快速成长!

最后于 2021-11-16 00:15 被KSr01dO编辑 ,原因:
收藏
点赞6
打赏
分享
最新回复 (4)
雪    币: 234
活跃值: 活跃值 (479)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
KSr01dO 活跃值 2021-11-12 13:45
2
2
如有任何错误,还请不吝赐教
雪    币: 234
活跃值: 活跃值 (479)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
KSr01dO 活跃值 2021-11-12 13:54
3
1
新人想要个正式会员,求波点赞收藏,万分感谢
雪    币: 8296
活跃值: 活跃值 (13854)
能力值: (RANK:750 )
在线值:
发帖
回帖
粉丝
ScUpax0s 活跃值 13 2021-11-12 15:11
4
1
加油
雪    币: 234
活跃值: 活跃值 (479)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
KSr01dO 活跃值 2021-11-16 00:12
5
0
ScUpax0s 加油
谢谢大大
游客
登录 | 注册 方可回帖
返回