数字签名方案的安全性分析：基于离散对数的攻击

(1) 执行过程如下：

• 密钥产生：选择两个大素数p和q，计算g=α^((p-1)/q) mod p，其中α是p的原根。选择私钥x∈Zq，计算公钥y=g^x mod p。
• 签名产生：对于消息m，计算h=hash(m) mod q，其中hash是一个密码学哈希函数。选择随机数k∈Zq，计算r=g^k mod p，然后计算s=(h+x*r)*k^(-1) mod q。
• 签名验证：接收到消息m和签名(r,s)，计算h=hash(m) mod q，计算u1=s^(-1)*h mod q，u2=s^(-1)r mod q，计算v=(g^u1y^u2 mod p) mod q。如果v=r，则签名合法。

要证明y'=y，我们需要计算： y' = s^h mod p = (g^z)^h mod p = g^(x*h^(-1)*h) mod p = g^x mod p = y

因此，如果签名合法，y'=y。

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

• 窃听者截获Alice发送的消息m和签名(r,s)。
• 窃听者可以选择任意的随机数k∈Zq，计算r=g^k mod p，然后计算s'=(h+x*r)*k^(-1) mod q。
• 窃听者将(r,s')作为伪造的签名发送给Bob。
• Bob计算v=(g^u1*y^u2 mod p) mod q，其中u1=s'^(-1)*h mod q，u2=s'^(-1)*r mod q。由于r=g^k mod p，u2=s'^(-1)*g^k mod q，窃听者可以选择一个合适的s'使得u2等于窃听者想要的值。这样，v=r，Bob会接受伪造的签名。

因此，该签名方案不是安全的，容易受到伪造攻击。