RSA 算法的描述

来源：超时代软件     更新时间：2014年06月05日 19:03:31

作者：鄢喜爱 杨金民 田华

由于公开密钥加密具有很大的优点, 许多研究人员悉心研究解决这一难题的算法。其中一个较好的算法是由美国麻省理工学院的Rivest、Shamir 和Adleman 三人研究小组于 1978 年提出的RSA 加密算法, 该方法基于数论原理。 超时代手机视频加密软件应用先进的加密算法，使加密视频在手机实现授权播放。

 

RSA 算法公开密钥的产生
(1) 选择两个大素数p 和q;
(2) 计算n= p @ q 和z= (p- 1) @ (q- 1) ;
(3) 选择一整数e, 要满足0< e< z , 且gcd(z, e) = 1;
(4) 公开密钥PK= { e, n} 。

 

RSA 算法私有密钥的产生

 

1 Euclid 扩展算法

 

RSA 算法中的私有密钥通常利用Euclid 扩展算法来计算。Euclid 扩展算法在数论中应用广泛, 它被用来求解形如ax=b(mod n) 的方程。

Euclid 扩展算法首先确定两个整数x 和y, 满足:xa+ yb= 1。

为了使x 和y 存在( x, y 不一定) , 必须有gcd(a,b) = 1。它的算法(伪代码) 描述如下:
(1) 初始化a1= 1, a2 = 1,b1= 0,b2 = 1;
(2) n1= q* n2 + r;
(3) If (r= = 0) gcd( n1, n2) = n2 , a= a2 , b=b2 , 算法结束;
(4) Else n1= n2, n2= r, t= a2, a2= a1- q*a2 , a1 = t,t= b2 , b2 = b1 - q* b2 ,b1 = t, 转(2) 。

例1:找出x 和y, 使得7x+ 120y= 1。其运算过程见表1。

表1 Euclid 扩展算法的运算过程

 

所以,7* ( - 17) + 120* 1= 1。

对于解形如ax=b(mod n) 的方程, 只要稍作变换即可。

例2:找出x, 使得7x=1(mod 120) 。

由例1得7* ( - 17) + 120* 1= 1, 可找出x= (- 17mod 120) = 103。可以验证7x= 7* 103= 721, 满足721 mod 120= 1成立。

 

2 扩展算法解出RSA 算法中的私钥

RSA 中的私钥d 要满足deS 1(mod z) , d是e在模z下的乘法逆元, 因为e与z互素, 由模运算可知, 它的乘法逆元一定存在。这个方程可以利用Euclid 扩展算法解出。于是得到私钥SK={d, n} 。

 

3 RSA 算法中的加密和解密

若用整数M表示明文, 用整数C表示密文(M和C均小于n) , 则加密和解密运算为:

加密: C= Me( mod n) ;
解密: M= Cd(mod n) 。

 

4 RSA 算法实例

选择两个素数, p= 11, q= 13, 得出 n=143, z= 120。再选取一个与z= 120 互质的数,例如e= 7, 解方程7d= 1(mod 120) , 利用Euclid扩展算法可得出d= 103, 则公开密钥= (n, e) =( 143,7) , 秘密密钥= (n, d) = ( 143, 103) 。

设A 需要发送机密信息( 明文) m= 85 给 B, A 已经从公开媒体得到了B 的公开密钥(n, e) =( 143,7) , 于是A 可以算出加密值: c= m mod n= 85 mod 143= 123, 并发送给 B。

B 在收到密文c= 123 后, 利用只有自己知道的秘密密钥计算: m= c mod n = 123的103次方mod143= 85, 所以, B 可以得到A 发来的真正的信息m= 85, 实现了解密。

 

超时代软件：www.360drm.com