同态哈希函数

同态哈希是一种特殊的哈希函数。如果$a$的哈希是$h(a)$，$b$的哈希是$h(b)$，$f(a,b)$是$a$和$b$的函数，那么$f(a,b)$的哈希可以通过$h(a)$和$h(b)$的某种计算获得。
在论文《A Practical Scheme for Non-interactive Verifiable Secret Sharing》中就使用了同态哈希来验证秘密分享是否被篡改。

RSA实例

假设有一个RSA的加密方案，公钥为$(n,e)$，n是两个素数的乘积。
现在定义哈希函数： h ( m ) = m e m o d    n h(m)=m^e \mod n h(m)=memodn.
那么 h ( a ) = a e m o d    n h(a)=a^e \mod n h(a)=aemodn， h ( b ) = b e m o d    n h(b)=b^e \mod n h(b)=bemodn.
则， h ( a b ) = ( a b ) e m o d    n = ( a e m o d    n ) ⋅ ( b e m o d    n ) m o d    n = h ( a ) ⋅ h ( b ) m o d    n h(ab)=(ab)^e \mod n = (a^e \mod n) \cdot (b^e \mod n) \mod n=h(a) \cdot h(b) \mod n h(ab)=(ab)emodn=(aemodn)⋅(bemodn)modn=h(a)⋅h(b)modn.
因为RSA加密是安全的，不知道私钥时，RSA的加密可以看作是不可逆的，即满足hash函数的不可逆性。

加法同态哈希

设有p是一个大素数，可以找到阶为q的生成元g。那么哈希函数定义为： h ( m ) = g m m o d    p . h(m)=g^m \mod p. h(m)=gmmodp.
那么 h ( a ) = g a m o d    p h(a)=g^a \mod p h(a)=gamodp， h ( b ) = g b m o d    p h(b)=g^b \mod p h(b)=gbmodp.
则， h ( a b ) = g a b m o d    p = ( g a m o d    p ) ⋅ ( g b m o d    p ) m o d    p = h ( a ) h ( b ) m o d    p h(a b)=g^{a b} \mod p = (g^a \mod p) \cdot (g^b \mod p) \mod p=h(a)h(b) \mod p h(a b)=ga bmodp=(gamodp)⋅(gbmodp)modp=h(a)h(b)modp.
离散对数问题是困难的，求这个哈希函数的逆是等价于解离散对数问题。所以，该哈希是可逆的。

应用

假设收到a和b，如果有a和b的加法同态哈希值$h(a),h(b)$，则，可以验证a和b是否被篡改。
计算$h(ab)$，然后判断$h(ab)$是否等于$h(a)h(b)\mathrm{m}\mathrm{o}\mathrm{d}p$。如果不相等，那么说明a或者b，或者其哈希值被改变了。

这篇好文章是转载于：学新通技术网