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

(1) 执行过程如下：

• 密钥产生：选择两个大素数p、q，计算g=α^((p-1)/q) mod p，其中α是p的原根。选择私钥x∈Zq，计算公钥y=g^x mod p。
• 签名产生：对于要签名的消息m，计算h=hash(m) mod q，选择随机数k∈Zq，计算r=g^k mod p，计算s=k^(-1)(h+xr) mod q，签名为(r,s)。
• 签名验证：对于收到的签名(r,s)和消息m，计算h=hash(m) mod q，计算u1=s^(-1)h mod q，u2=s^(-1)r mod q，计算v=g^(u1)y^(u2) mod p，若v=r，则签名合法，否则非法。

在该签名方案中，签名的合法性取决于s的计算过程中z=xh^(-1) modq的正确性。因此，我们需要证明s=g^z mod p等价于y'=s^h mod p=g^(xh^(-1)*h) mod p=y mod p。

首先，根据s的计算过程，有s=g^z mod p，其中z=xh^(-1) modq。将z带入得到s=g^(xh^(-1)) mod p * g^h mod p=y^h mod p。因此，y'=s^h mod p=(y^h mod p)^h mod p=y^(h^2) mod p。

然后，我们证明y'=y^(h^2) mod p=y mod p。由于y=g^x mod p，因此y^h mod p=(g^x mod p)^h mod p=g^(xh) mod p。因此，y^(h^2) mod p=g^(xh^2) mod p=y mod p。因此，y'=y^(h^2) mod p=y mod p，签名合法。

(2) 窃听者可以伪造签名的过程如下：

• 窃听者截获Alice的公钥y。
• 窃听者选择一个随机数k∈Zq，计算r=g^k mod p。
• 窃听者计算h=hash(m) mod q，选择一个随机数z∈Zq，计算s=z+hx mod q。
• 窃听者构造签名为(r,s)发送给Bob。

由于窃听者并不知道Alice的私钥x，因此无法计算出正确的签名。但是，对于任意的(r,s)，窃听者都可以构造一个合法的公钥y'，使得y' = r。因此，Bob在验证签名时会误认为签名合法。这种攻击被称为存在公钥替换攻击