RSA签名方案优化

1978年，Rivest、Shamir和Adleman联合提出了目前应用最广泛的RSA公钥密码体制。RSA密码体制既可用于加密又可用于数字签名。RSA数字签名方案是现有签名方案中最容易理解和实现的签名方案，它的安全性依赖于大整数因子分解的困难性。

1.RSA签名的生成与验证算法

（1）参数定义和密钥生成

●选两个大素数p和q；（p，q保密）

●计算n=p×q，φ（n）=（p-1）×（q-1）；（n公开，φ（n）保密）

●随机选一整数e，满足1＜e＜φ（n），且gcd（φ（n），e）=1；（e公开）

●计算d，满足

d×e≡1（mod φ（n））

即d是e在模φ（n）下的乘法逆元，因e与φ（n）互素，由模运算可知，它的乘法逆元一定存在，（d保密）。则公钥为k₁=（n，e）；私钥为k₂=（p，q，d）。

（2）签名算法

设待签名的消息为x∈M，私有密钥d∈K，经过签名算法后得到y，且y∈A，即

（3）验证算法

签名接收者收到签名（y，x）时，可用

验证签名是否有效。

若等式成立，则y是发送者对x的有效签名。由于y是用发送者使用他的私钥经过签名算法所得，别人做不出这样的签名，可有效防止发送者的抵赖行为。

【例6-1】 在RSA数字签名方案中，已知两个素数分别是p=5，q=17，取e=5，设待签名的消息为x=10时，计算签名y并验证签名的有效性。

【解析】 发送者A首先计算

n=p×q=5×17=85

φ（n）=（p-1）×（q-1）=4×16=64

取e=5，满足

gcd（64，5）=1

得知公钥为（n，e）=（85，5）

求出私钥d，满足

d×e≡1（mod φ（n））

d≡e^-1（mod φ（n））≡5^-1（mod 64）≡13

由于待签名的消息x=10，计算签名得

y≡x^d（mod n）≡10¹³（mod n）≡45（mod 85）

接收者B收到（45，10）后，验证

y^e（mod n）≡45⁵（mod n）≡10（mod 85）≡x

说明发送者A发过来的签名是真实有效的。

2.RSA签名方案的安全性

RSA数字签名方案的安全性依赖于n=p×q分解的困难性。密码分析者可以采用穷举攻击、数学攻击、计时攻击等手段来攻击和破解。签名方案的使用者，可以通过大密钥空间即增加e和d的位数抵抗攻击，不过这样就会使密钥的产生、签名、验证过程的计算量增大，系统运行速度变慢。

RSA数字签名的弱点表现在以下几个方面：

1）任何人都可以伪造某签名者对于随机消息x的签名y。其方法是先选取y，用某签名者的公钥（n，e），计算出x≡y^e（mod n），y就是某签名者对消息x的签名。(www.xing528.com)

2）若攻击者掌握某签名者对消息x₁、x₂的签名y₁、y₂，则攻击者可以伪造x₁·x₂，这是因为，（y₁·y₂）e=y^e₁·y^e₂≡x₁·x₂（mod n）。

3）当对较长的消息采用分组链接结构时，需对每个分组分别进行签名，这样运算量就很大，而且对于分组的丢失也不敏感。

为了增强RSA数字签名方案的安全性，当对大容量消息签名前，发送者可使用一个安全的Hash函数h来产生消息摘要h（x），再用签名算法计算签名

y=Sig_k（x）≡（h（x））d（mod n）

接收者收到签名后，在验证签名时，先计算h（x），再检验等式

h（x）≡y^e（mod n）

若等式成立，则y是发送者对x的有效签名；否则，签名无效。

3.签名和加密的组合

由于在RSA数字签名方案中，任何人都可以用发送者的公钥解出x，与原来的消息x进行比对，所以通常的做法是：不仅要认证签名，还要加密明文，不让合法接收者以外的其他人看到明文x，这就要进行双重“加密”。如发送者A给接收者B发送消息x，有以下两种方案。

（1）先加密再签名

发送者A先使用接收者B的公开加密函数E_B加密得

z=E_B（x）

A再用他的签名算法签名得

y=Sig_A（z）=Sig_A（E_B（x））

并将（z，y）传送给B。

接收者B收到（z，y）后，解密

x=D_B（z）

再用验证算法验证

Ver_A（z，y）=TRUE

是否成立。

这种方案的不安全之处在于如果窃听者C收到（z，y），它可以用自己的密文z′=E_B（x′）替代z，并对z′作自己的签名：Sig_C（z′）=y′，再用y′代替y。而B收到（z′，y′）后，可能会误解发送者是C，因为用C的公钥（e_C，n′）能够证明签名Ver_C（z′，y′）的有效性，从而相信了C发来的密文x′。

（2）先签名再加密

对于消息x，发送者A先计算他的签名

y=Sig_A（x）

再使用接收者B的公开加密函数E_B加密得

z=E_B（x，y）

A将z发送给B，B收到z后先解密

（x，y）=D_B（z）

得到签名，再用验证算法进行验证

Ver_A（x，y）=TRUE

是否成立。

这种方案中，窃听者C即使收到z，也因无法知道A的私钥而不能获得更多有效的内容，所以相对于第（1）种方案来说这种方案要安全一些。