实验步骤

1 密钥生成算法步骤如下：

1. 选取大素数 $p$ , $g$∈$𝑍_𝑝^∗$ 是一个原根。 $p$ 和 $g$ 公开；
2. 随机选取整数 $x$ , $1 < x < p-1$，计算 $y = g^x mod p$。
3. 公钥为 ${p,g,y}$，私钥为 $x$。

2 签名算法

1. 给定待签消息 $𝑚 ，选择随机整数$𝑘∈$𝑍_{𝑝−1}^∗$ ， 满足 gcd(k, p-1) = 1;
2. 计算 $H(𝑚)$, 本次实验可以采用SHA256，如果使用其他 Hash 算法，请在实验报告模板中说明。
3. 计算 $𝑟=𝑔^𝑘 mod ⁡𝑝$， $𝑠=𝑘^{−1} (𝐻(𝑚)−𝑥𝑟)mod⁡ (𝑝−1)$
4. 定义 $𝑆𝑖𝑔(𝑚,𝑘)=(𝑟,𝑠)$， 将 $m$ 和 $(r, s)$ 发送给对方。

3 验证算法

1. 接收方收到 $m$ 和 $(r, s)$， 计算 $H(𝑚)$;
2. 验证：$𝑣𝑒𝑟(𝑚,(𝑟,𝑠),𝑦)=真$⇔$𝑦^𝑟 𝑟^𝑠≡𝑔^{𝐻(𝑚)} mod⁡ 𝑝$

说明

可以重用RSA公钥加密算法中的 gcd，exgcd， fastmod 等算法， Hash算法建议用 SHA256，可以直接调用，如果使用了其他 Hash 算法，请在实验报告中说明。

4 实验任务

本次实验需要大家完成 ElGamal 数字签名算法，推荐大家用 Java 或者 Python 实现，签名的信息 m 是你的学号, 需要随机生成两次不同的 k 进行签名并验证签名，并且验证假设消息 m 在传送过程中被篡改的情况。

1. 需要将公钥（p, g, y）和私钥 x 以及每次使用的随机数 k 打印输出。
2. 用学号作为消息 m ，并打印输出随机生成两次不同的 k 的签名信息和签名验证的结果。
3. 验证签名时，假设消息 m 被篡改的情况，要输出验证签名不通过的信息。
4. Hash 算法使用 SHA256 对消息 m 进行 Hash 运算。