[請問] 每個雜湊函數都一定會有碰撞情形產生嗎?

作者: 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