1、考虑下面的数宇签名方案。1密钥产生p、q是两个大素数g属于Zpordg= q私钥x属于 Zq公钥 y = g^x mod p。2签名产生Alice 对消息m进行签名时她计算 h = hashm mod qz = xh^-1 mod qs=g^z mod p即为m的签名。3签名验证 Bob 对签名验证他计算 h = hashm mod qy = s^h mod p验证等式y = y是否成立。如果

(1) 执行过程如下：

• 密钥产生：选择两个大素数p、q，计算g，使得g是Z*p的一个原根，即ord(g)=q。选择一个私钥x属于Zq，计算公钥y=g^x mod p。
• 签名产生：对消息m进行签名，计算哈希值h=hash(m) mod q，计算z=x*h^(-1) mod q，计算签名s=g^z mod p。
• 签名验证：对签名进行验证，计算哈希值h=hash(m) mod q，计算y'=s^h mod p，判断是否有y'=y，如果成立则接受签名，否则拒绝签名。

在签名合法的条件下，有： y' = s^h mod p = (g^z)^h mod p = g^(zh) mod p = g^(x*h^(-1)*h) mod p = g^x mod p = y

(2) 窃听者可以伪造签名的方法是：窃听者可以选择一个随机数z'属于Zq，然后计算s'=g^z' mod p作为伪造的签名。对于任意的消息m，窃听者可以通过计算哈希值h=hash(m) mod q，然后计算y'=s'^h mod p来进行伪造的签名验证。由于s'=g^z' mod p，所以有y'=(g^z')^h mod p=g^(z'h) mod p。如果窃听者能够找到一个z'，使得z'h=xh^(-1) mod q成立，则伪造的签名就能够通过验证。这个条件可以通过求解同余方程来得到：z' = xh^(-1)*h^(-1) mod q，因为h^(-1) mod q存在，所以窃听者可以得到一个合法的伪造签名