[请问] 每个杂凑函数都一定会有碰撞情形产生吗?

楼主: red0whale (red whale)   2019-04-14 20:45:44
一般而言杂凑值都是固定长度的
但是我有个疑惑
一个要进行杂凑前的字串本来长度就可无限长
也就是说在进行杂凑前原文并没有限制长度为何
但是出来的结果永远都是一样的长度
这样不是很奇怪吗?
那么理论上所有出来的结果为固定长度的杂凑函数都应该会有碰撞(Collision)情形产生呀
但是据中文维基百科(https://zh.wikipedia.org/wiki/%E6%95%A3%E5%88%97)
部分杂凑算法没有碰撞情形产生
但又根据英文维基百科(https://en.wikipedia.org/wiki/Collision_resistance)
“Every hash function with more inputs than outputs will necessarily have
collisions.”
“每一个杂凑函数当输入多于输出必然产生碰撞”
又从http://crypto.nknu.edu.tw/textbook/chap4.pdf找到对于Collision Resistance的定义
“找不到两个相异的讯息M1与M2会被计算出相同的输出讯息指纹”
也就是找不到两个不同的原文,其经过同一杂凑函数后会是相同的杂凑值
这搞得我好头疼
所以每一个杂凑函数是否都具有碰撞?还是部份杂凑函数不具有碰撞?
谢谢
作者: Ricestone (麦饭石)   2019-04-14 21:04:00
那wiki指的是有没有存在有效的冲突攻击法吧
作者: chienweichih ((゚д゚))   2019-04-14 21:04:00
既然输出的长度是固定的 就一定会碰撞
作者: Ricestone (麦饭石)   2019-04-14 21:06:00
你找的这两个中文资料都写得太简略了,没定义清楚
作者: newacc (XD)   2019-04-16 18:42:00
标准的鸽笼问题

Links booklink

Contact Us: admin [ a t ] ucptt.com