固定生成器的取冪模是質數抗碰撞的嗎？

讓 $ p $ 是一個素數，並且 $ g $ 一個生成器 $ \mathbb Z/p\mathbb Z $ . 留言 $ m $ , 定義散列函式

$$ h(m) = g^m \pmod p. $$ 是 $ h $ 耐碰撞？

讓 $ m $ 隨意。然後 $ m’=m+p-1 $ 產生碰撞 $ h(m)=h(m’) $ 作為 $ m\equiv m’\pmod{p-1} $ 因此通過 $ p-1 $ 作為相關組的訂單 $ g^m\equiv g^{m’}\pmod p $ .

或以不同的方式製定（使用 $ g^{p-1}\bmod p=1 $ ):

$$ h(m’)=g^{m+p-1}=g^m\underbrace{g^{p-1}}_{1}\equiv g^m=h(m)\pmod p $$

引用自：https://crypto.stackexchange.com/questions/58527