数字签名

1. 基本概念

一个数字签名方案包括如下3个算法：

• 密钥生成：产生用户的公私钥
• 签名算法：产生消息的签名
• 验证算法：验收消息的签名是否是合法

数字签名方案为了实现安全认证，需要满足如下条件：

• 必须相对容易生成该数字签名
• 必须相对容易识别和验证该数字签名
• 伪造该数字签名在计算上不可行，既包括对一个已 有的数字签名构造新的消息，也包括对一个消息伪 造一个数字签名

2. RSA签名算法

2.1 密钥生成算法

1、选两个保密的大素数 p 和 q ，计算 n = p × q ， φ ( n )=( p -1)( q -1)；

2、选一整数 e ，满足1< e < φ ( n )，且 gcd ( φ ( n ), e )=1；

3、计算 d ，满足 d · e ≡1 mod φ ( n )；

4、以{ e , n }为公钥, { d,n }为私钥。

2.2 签名算法

2.3 验证算法

2.4 正确性

2.5 缺点

3. ElGamal签名算法

1. 密钥生成

1、选取大素数 p , g, Z * p 是一个本原元。 p 和 g 公开；

2、随机选取整数 x ,1≤ x ≤ p - 2，计算 y = g^x mod p 。

3、公钥为 y ，私钥为 x

2. 签名算法

对于消息 m，首先随机选取整数 k, 1≤ k≤ p-2 ，然后计算：

则 m的签名为( r, s)，其中 h为Hash函数。

3. 验证算法

接收方在收到消息 m和签名 ( r,s)后，验证

如果等式成立，则 ( r,s)是消息 m的有效签名；反之，则是无效签名 。