实验原理

说明

p 代码一个大素数，可以使得 $Z_p$中求解离散对数为困难问题， g 是 $Z^*_p$的一个生成元或者叫本元根， M 代表消息空间，S 代表签名空间，x 代表用户私钥，y 代表公钥参数，(p,g,y) 代表公钥。

1 数字签名

数字签名是用于对数字消息签名,以防消息的伪造或篡改,也可用于通信双方的身份鉴别。它可以用来对身份认证，保持数据完整性、不可否认性。数字签名应该具有如下几个特点：

1. 签名是可信的：任何人可验证签名的有效性。
2. 签名是不可伪造的：除合法签名者外，其他人伪造签名是困难的。
3. 签名是不可复制的：一消息的签名不能复制为另一消息的签名。
4. 签名的消息是不可改变的：经签名的消息不能被篡改。
5. 签名是不可抵赖的：签名者事后不能否认自己的签名。

1.1 数字签名与公钥加密

公钥加密： Alice 采用 Bob 的公钥对信息加密， Alice 将密文发送给 Bob ； Bob 用其本身的私钥对收到的密文解密，恢复出明文。

数字签名： Alice 采用 自己的私钥对消息 m 签名， Alice 将 m 和签名发送给 Bob ； Bob 收到 m 和签名后， Bob 采用 Alice 的公钥验证签名的有效性。

1.2 数字签名与消息认证

消息认证： 收发方没有利害冲突时，消息认证用于防止第三者的破坏。收方能够验证消息发送者身份或者发送者发送的消息内容是否被篡改。

数字签名：当收发双发存在利害冲突时，消息认证技术无法解决收发双方之间的纠纷，必须要采用数字签名技术。 数字签名能确定消息来源的真实性，能够保证实体身份的真实性，也能够保证不可否认性。

1.3 数字签名的分类

按照消息是否被压缩分类：分为对整体消息进行签名和对压缩的消息进行签名两类。

按照消息/签名的对应关系分类：分为确定性签名和随机化数字签名两类。确定性签名是消息与签名一一对应，对同一消息的签名永远不会变化，比如RSA；随机化数字签名是对同一消息的签名是变化的，本次实验所采用的 ElGamal 数字签名算法就是随机化的。

1.4 数字签名方案的3个算法

1. 密钥生成：产生用户的公私钥
2. 签名算法：产生消息的签名
3. 验证算法：验证消息的签名是否是合法

2 ElGamal 数字签名

1985年， EIGamal 提出了一个基于离散对数问题的签名方案，后来称为 ElGamal 数字签名方案。1991年该数字签名方案的变形被美国国家标准局 (NIST) 确定为数字签名标准 (DSS) 。

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

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

2.2 签名算法

1. 给定待签消息 $𝑚 ，选择随机整数$𝑘∈$𝑍_{𝑝−1}^∗$ ， 满足 gcd(k, p-1) = 1;
2. 计算 $H(𝑚)$
3. 计算 $𝑟=𝑔^𝑘 mod ⁡𝑝$， $𝑠=𝑘^{−1} (𝐻(𝑚)−𝑥𝑟)mod⁡ (𝑝−1)$
4. 定义 $𝑆𝑖𝑔(𝑚,𝑘)=(𝑟,𝑠)$， 将 $m$ 和 $(r, s)$ 发送给对方。

2.3 验证算法

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

签名的正确性说明：

因为有 $𝑠=𝑘^{−1} (𝐻(𝑚)−𝑥𝑟)mod⁡(𝑝−1)$

所以有 $r𝑥+𝑠𝑘=𝐻(𝑚) mod⁡(𝑝−1)$

所以 $𝑦^𝑟 𝑟^𝑠≡𝑔^{xr} 𝑔^{sk} mod⁡𝑝 ≡𝑔^{xr+sk}mod⁡𝑝≡𝑔^{𝐻(𝑚)} mod⁡𝑝$