数字签名---RSA算法

保证信息在传输过程中的安全性：

保密通信、密钥交换、数字签名。

	RSA算法	Diffie-Hellman算法	DSA算法
保密通信	√	×	×
密钥交换	√	√	×
数字签名	√	×	√

数字签名具有抗否认、抗假冒、抗篡改伪造的特性

M----明文

Keb----B的公钥

Kdb----B的私钥

当先用私钥加密时，将相当于B对明文进行了数字签名，B不可抵赖。

RSA算法：

速度：

1.由于都是大数计算，RSA最快的情况也比DES慢许多倍，无论是硬件还是软件实现。速度一直是RSA的缺陷。一般来说只用于少量的数据加密。

2.RSA是被研究是最广泛的公钥算法，提出到现在已经历了二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。

执行过程：

1.生成两个大素数p和q

2.计算这两个素数的乘积n=p*q

3.计算小于n并且与n互质的整数的个数，即欧拉函数φ(n)=(p-1)*(q-1)

4.选择一个随机数e满足1<e<φ(n),并且e和φ(n)互质，即gcd(e,φ(n))==1

5.解方程 e*d ≡1 mod φ(n),求出d

6.保密d，p和q（销毁），公开n和e

公钥公开：PU={e,n}

私钥保密：PR={d,n}

RSA使用：

加密一个报文M，发送方：

1.获取接收方的公钥 PU={e,n}

2.计算：C = M^e mod n, where 0<=M<n

解密密文C，接收方：

1.用自己的私钥PR={d,n}

2.计算：M=C^d mod n

RSA注意：

1.RSA加密时，明文以分组的形式加密，每一个分组的比特数应该小于log₂n比特，即M<n

2.选取的素数p和q要足够大，从而乘积n足够大，在事先不知道p和q的情况下，分解n是计算上不可行的。

如何得到足够大的随机素数？

实际应用所采用的方法是：首先，产生一个足够大的随机数，然后，通过采用一个概率多项式时间算法来检测该随机数是否为素数（即是否具有素性）

常用的两个素性测试算法：Solovay-Strassen和Miller-Rabin

RSA例子----密钥

1.挑选质数：p=17 & q=11

2.计算 n=p*q=17*11=187

3.计算 φ(n)=(p-1)*(q-1)=16*10=160

4.选择 e:gcd(e,160)=1; 选择 e=7

5.求解 d:e*d≡1 mod 160 且 d<160 , d=23,显然 23*7=161=160+1

Public key Pu={7.187}

Private key PR={23,187}

RSA 加密/解密： M=88（注意88<187）

加密： C = 88⁷ mod 187 = 11

解密: M = 11²³ mod 187 = 88

求解方程 e*d≡ 1 mod φ(n)

当e=1001 , φ(n)=3837时：

1.欧几里得算法（辗转相除法）：

3837 = 3 * 1001 + 834

1001 = 1 * 834 +167

834 = 4 * 167 + 166

167 = 166 + 1

2.回代：

1 = 167 - 166

= 167 - （834 - 4*167 ）

= 5 * 167 -834

= 5 * （1001 - 834）-834

= 5 * 1001 - 6 * 834

= 5 * 1001 - 6 *（3837 - 3 * 1001）

= 23 * 1001 - 6 * 3837

巴特西

数字签名---RSA算法

最新文章

热门文章