区块链中的数学 - RSA签名过程 | 登链社区

区块链中的数学 - RSA签名过程

blocksight
更新于 2020-07-01 21:30
阅读 3350

本节主要介绍了RSA签名过程，并就其安全性做了一定程度的分析。可以看到如果直接使用RSA原理的执行过程，会有不少风险。关于安全分析，还没有说完，还有硬件故障攻击和选择密文攻击，尤其后者很重要。

## 写在前面

上一节介绍了[欧拉函数积性和扩展剩余定理](https://learnblockchain.cn/article/1561)。有了最近这几篇的铺垫再回头看[RSA原理](https://learnblockchain.cn/article/1548)会觉得清晰很多。
这一节我们继续讲RSA原理部分中的签名部分和安全分析。

## RSA签名

这里先说一下加密和签名的区别：
简单来说，加密是为了防止信息被泄露，而签名是为了防止信息被篡改，确保是特定用户行为。
签名过程如下：

1. 对原始消息做摘要得到M

2. 签名者使用私钥d 计算签名 $c =M^d\ mod\ n$

3. 验签者使用签名者的公钥验签：
$M =C^e\ mod\ n$
    对原始消息做同样摘要， 结果与M对比，如相同则验证通过，否则验证失败。

可以看出过程与RSA加密解密过程类似，不同的是加密采用公钥加密，这里使用私钥加密。

所以也可以理解为用私钥加密即是签名。

## RSA安全性

RSA算法有以下攻击方式（其实不只是RSA，其他密钥体系也可能有）：

1. 穷举攻击

2. 数学攻击

3. 计时攻击

4. 基于硬件故障分析

5. 选择密文攻击

本节细说下前三种：

#### 穷举攻击

容易理解，通过穷举所有的可能数据来猜测密钥或者密文。
当然RSA参数比较小的时候，可以使用该方法奏效。
例如用户公钥n = 35, e = 5 密文C = 10 被截获后，由于$C =M^e\ mod\ n=M^5\ mod\ 35=10$, 计算循环1到35，很容易破解原始消息M = 5.

抵抗该种攻击的方式是使用大密钥空间，公私钥均为很长比特位，如2048位等

#### 数学攻击

数学攻击的方法实质是试图分解两个素数的乘积，根据RSA原理𝑛 = 𝑝 × 𝑞，
找到素数对用的p,q, 进而计算出𝜙(𝑛)和私钥d.
目前因子分解大素数n 依然是一个难题，随着时间的推移，但也不像之前那么困难。
计算能力的不断发展和因子分解算法的改进，给该难题带来不断的挑战。
下表列出了因子分解的进展情况【截止2010】：

| 十进制位数 | 二进制位数（近似） | 完成日期 |
| :-: | :-: | :-: |
| 155 | 512 | 1999年8月 |
| 160 | 530 | 2003年4月 |
| 174 | 576 | 2003年12月 |
| 200 | 663 | 2005年5月 |
| 193 | 640 | 2005年11月 |
| 232 | 768 | 2009年12月 |

据说最新破解的已经很接近1000比特位的数， 所以现在一般推荐2048位或者更高密钥。
具体的分解方法有一般数域筛法等，超出本文范围，感兴趣可自查。

#### 计时攻击

攻击者通过记录计算机解密消息所需要的时间，来确定私钥的信息。该攻击方法也可以攻击其他加密算法。这种攻击仅依赖密文，有较大的潜在威胁。

通俗来说，这种攻击类似于盗窃者观察转动保险柜拨号盘的时间长短来猜测密码。
就RSA算法而言，加解密过程大量用到了幂模运算。幂模运算是按位计算实现的，如果当前位是1，则需要执行一次模乘运算。多次观察运算时间会给攻击者提供一些有效信息。

需要说明的是，实际中幂模运算没有较大的时间差异，对于1或0位来说。而且这种攻击也有一些简单实用的方法来消除。

1. 恒定的幂运算时间
    即保证幂运算在返回结果前，执行时间相同，这样消除了时间差异，但是降低了性能。

2. 随机延时
    在算法中随机加入延时时间，使得运行总时间差异不能反映密钥的一些位特征，比较容易理解

3. 隐蔽
    能隐身那自然最好，怎么做呢？在执行幂运算之前将密文乘上一个随机数，这个额外过程可以使攻击者不知道计算机正在处理的是密文的哪些位。即使攻击者一位一位分析也难以得到准确值。

下面介绍一种RSA数据安全公司采用的一种隐蔽方法，
在原始计算密文 $C =M^e\ mod\ n$ 之后，添加如下过程
（1）产生[1,n]之间的秘密随机数r
（2）计算$C' =C*r^e\ mod\ n$
（3）计算$M' =C'^d\ mod\ n$
（4）计算$M =M'r^{-1}\ mod\ n$ , $r^{-1}$  是r模n的逆元【[关于逆元参照](https://learnblockchain.cn/article/1556)】

有$r^{ed}\ mod\ n = r$ 可以证明这样算出的M是正确的。
至于这个等式$r^{ed}\ mod\ n = r$ 为什么成立？其实就是RSA解密的证明过程[RSA原理解密证明](https://learnblockchain.cn/article/1548)，感兴趣的可以再看看。

天下没有免费的午餐，这种方案也不是完全免费的：由于增加了额外的随机数的相关运算，算法性能据RSA数据安全公司说降低了2%--10%

## 小结

本节主要介绍了RSA签名过程，并就其安全性做了一定程度的分析。可以看到如果直接使用RSA原理的执行过程，会有不少风险。
关于安全分析，还没有说完，还有硬件故障攻击和选择密文攻击，尤其后者很重要。

好了，下一篇继续说[RSA的余下的选择密文攻击](https://learnblockchain.cn/article/1562)。

欢迎关注公众号：blocksight

写在前面

上一节介绍了欧拉函数积性和扩展剩余定理。有了最近这几篇的铺垫再回头看RSA原理会觉得清晰很多。这一节我们继续讲RSA原理部分中的签名部分和安全分析。

RSA签名

这里先说一下加密和签名的区别：简单来说，加密是为了防止信息被泄露，而签名是为了防止信息被篡改，确保是特定用户行为。签名过程如下：

对原始消息做摘要得到M
签名者使用私钥d 计算签名 $c =M^d\ mod\ n$
验签者使用签名者的公钥验签： $M =C^e\ mod\ n$ 对原始消息做同样摘要，结果与M对比，如相同则验证通过，否则验证失败。

可以看出过程与RSA加密解密过程类似，不同的是加密采用公钥加密，这里使用私钥加密。

所以也可以理解为用私钥加密即是签名。

RSA安全性

RSA算法有以下攻击方式（其实不只是RSA，其他密钥体系也可能有）：

穷举攻击
数学攻击
计时攻击
基于硬件故障分析
选择密文攻击

本节细说下前三种：

穷举攻击

容易理解，通过穷举所有的可能数据来猜测密钥或者密文。当然RSA参数比较小的时候，可以使用该方法奏效。例如用户公钥n = 35, e = 5 密文C = 10 被截获后，由于$C =M^e\ mod\ n=M^5\ mod\ 35=10$, 计算循环1到35，很容易破解原始消息M = 5.

抵抗该种攻击的方式是使用大密钥空间，公私钥均为很长比特位，如2048位等

数学攻击

数学攻击的方法实质是试图分解两个素数的乘积，根据RSA原理𝑛 = 𝑝 × 𝑞，找到素数对用的p,q, 进而计算出𝜙(𝑛)和私钥d. 目前因子分解大素数n 依然是一个难题，随着时间的推移，但也不像之前那么困难。计算能力的不断发展和因子分解算法的改进，给该难题带来不断的挑战。下表列出了因子分解的进展情况【截止2010】：

十进制位数	二进制位数（近似）	完成日期
155	512	1999年8月
160	530	2003年4月
174	576	2003年12月
200	663	2005年5月
193	640	2005年11月
232	768	2009年12月

据说最新破解的已经很接近1000比特位的数，所以现在一般推荐2048位或者更高密钥。具体的分解方法有一般数域筛法等，超出本文范围，感兴趣可自查。

计时攻击

攻击者通过记录计算机解密消息所需要的时间，来确定私钥的信息。该攻击方法也可以攻击其他加密算法。这种攻击仅依赖密文，有较大的潜在威胁。

通俗来说，这种攻击类似于盗窃者观察转动保险柜拨号盘的时间长短来猜测密码。就RSA算法而言，加解密过程大量用到了幂模运算。幂模运算是按位计算实现的，如果当前位是1，则需要执行一次模乘运算。多次观察运算时间会给攻击者提供一些有效信息。

需要说明的是，实际中幂模运算没有较大的时间差异，对于1或0位来说。而且这种攻击也有一些简单实用的方法来消除。

恒定的幂运算时间即保证幂运算在返回结果前，执行时间相同，这样消除了时间差异，但是降低了性能。
随机延时在算法中随机加入延时时间，使得运行总时间差异不能反映密钥的一些位特征，比较容易理解
隐蔽能隐身那自然最好，怎么做呢？在执行幂运算之前将密文乘上一个随机数，这个额外过程可以使攻击者不知道计算机正在处理的是密文的哪些位。即使攻击者一位一位分析也难以得到准确值。

下面介绍一种RSA数据安全公司采用的一种隐蔽方法，在原始计算密文 $C =M^e\ mod\ n$ 之后，添加如下过程（1）产生[1,n]之间的秘密随机数r （2）计算$C' =C*r^e\ mod\ n$ （3）计算$M' =C'^d\ mod\ n$ （4）计算$M =M'r^{-1}\ mod\ n$ , $r^{-1}$ 是r模n的逆元【关于逆元参照】

有$r^{ed}\ mod\ n = r$ 可以证明这样算出的M是正确的。至于这个等式$r^{ed}\ mod\ n = r$ 为什么成立？其实就是RSA解密的证明过程RSA原理解密证明，感兴趣的可以再看看。

天下没有免费的午餐，这种方案也不是完全免费的：由于增加了额外的随机数的相关运算，算法性能据RSA数据安全公司说降低了2%--10%