基于数论的RSA算法研究

《基于数论的RSA算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于数论的RSA算法研究【摘要】基于数论的公钥密码体制的RSA算法是最完善的加密算法.通过RSA算法基本原理可以将大数的幕模运算转换为小数幕模运算，并对一些模块进行适当的改进，从而提出快速求解加密和解密的计算方法，提高RSA的运算速度。【关键词】公钥密码算法RSA算法幕模运算【基金项目】河南省教育厅科学技术研究重点项目资助计划(14A110016)o【中图分类号】029【文献标识码】A【文章编号】2095-3089(2014)05-0137-021.前言RSA公钥密码算法是美国麻省理工学院的三位学者Rivest.Shamir和Adieman在1978年提出的［1］,既可以用于加密，又可

2、用于数字签名，它安全，易懂，易实现，是目前广泛应用的一种密码算法。其理论基础是数论中的大合数因子分解困难性，即求两个人素数之积，在计算机上很容易实现。但是要将一个大合数分解成两个素数的乘积，在计算机上很难实现。由于RSA算法采用的幕模运算耗时太多，大量的数据处理时速度很慢，所以提高RSA的运算效率便成为非常重要的研究内容［4］。2•基本定义与定理定义1：若a,b,c都是整数，且a

3、b,a

4、c,那么a就是b和c的公因数。在所有公因数中最大一个，称为最大公因数，并记为gcd(b,c)[3]o定义2：若a和b的最大公因数是1,即gcd(b,c)=l,则称a和b互素⑵。定义3：设a,beZ,n

5、HO如果n

6、(a-b),则称a和b模n同余，记为a三b(modn),整数n称为模数[3]。定义4：元素xeZn有乘法逆元xT,当但仅当x和n的最大公因子是1,即gcd(x,n=l),即x和n互质。如果x的逆元存在，必定满足xXx-lmodn二1[3]。定理1：若a•和n互素，则a(n)=lmodn,称为欧拉定理(简称Euler定理)。证明：设Zn={al,a2,...a*(n)}是模n的一个群集，由于gcd(a,n)=l,根据同余性质ab=albl(modn),故aZn={aal,aa2,...aa4)(n)}也是模n的一个群集，即・al=H(aal)(modn)。因此a<1)(

7、n)=lmodn0定理2：若是p素数，a是正整数且gcd(a,p)=l则ap-1三lmodp,称为费尔玛定理。(简称Fermat定理)[1]。定理3：设n是一正整数，小于n但与n互质的正整数的个数称为n的欧拉函数，记为4)(n),若n是素数，则显然有<1)(n)=n-l[1]o推论1：若n是两个素数p和q的乘积，则<1>(n)=4)(p)Xe(q)=(p-l)X(q-1)推论2：对任意非负整数a和正整数b有gcd(a,b)=gcd(b,amodb)。证明：因为b是正整数，所以可将a表示为a=kb+r=rmodb,amodb=r,其中为k一整数，所以amodb=a-kb,设d是a,b的公

8、因子，即d

9、o,d

10、b,所以d

11、kb,由d

12、a和d

13、kb得d

14、(amodb),因此a是b和amodb的公因子。所以得出a,b的公因子集合与b,amodb的公因子集合相等，两个集合的最大值也相等。3.RSA公钥算法描述3.1密钥选择RSA加密算法的密钥选择方法是该算法的核心，RSA密钥的选择和牛成方法保证了RSA公钥加密算法的安全性。先选择两个素数p和q。这两个素数的乘积就是RSA密钥中的正整数n,即n二pXq,如果p和q足够大,那么乘积n也就足够大，如再分解p和q困难性极大，这样就可以满足了公钥密码系统的耍求，根据欧拉函数计算出*(n)=(p-l)(q-l)o然后，随机选収整数0,满足

15、1

16、式两边同乘以e将等式转化为dXe二lmod©(n)。根据模运算性质可知dXe=k4)(n)+l,其中k是一个大于等于的整数。根据加密公式和模运算性质可知cdmodn=(me)dmodn^mk4)(n)+lmodn,利用指数运算性质mXmk(n)modn=mXlmodn二m。3.4计算问题通过分析RSA算法的求解过程，可知RSA通过乘法与除法加以实现的。可想而知，RSA算法将执行大量的乘除法运算，从而导致RSA算法的加密与解密速度十分慢［6］。因