基于数论的RSA算法研究

【摘要】基于数论的公钥密码体制的RSA算法是最完善的加密算法. 通过RSA算法基本原理可以将大数的幂模运算转换为小数幂模运算，并对一些模块进行适当的改进，从而提出快速求解加密和解密的计算方法，提高RSA的运算速度。

【关键词】公钥密码算法RSA算法幂模运算

【基金项目】河南省教育厅科学技术研究重点项目资助计划（14A110016）。

【中图分类号】O29 【文献标识码】A 【文章编号】2095-3089（2014）05-0137-02

1.前言

RSA公钥密码算法是美国麻省理工学院的三位学者Rivest、Shamir和Adleman在1978年提出的[1]，既可以用于加密，又可用于数字签名，它安全，易懂，易实现，是目前广泛应用的一种密码算法。其理论基础是数论中的大合数因子分解困难性，即求两个大素数之积，在计算机上很容易实现。但是要将一个大合数分解成两个素数的乘积，在计算机上很难实现。 由于RSA算法采用的幂模运算耗时太多，大量的数据处理时速度很慢，所以提高RSA的运算效率便成为非常重要的研究内容[4]。

2.基本定义与定理

定义1：若a,b,c都是整数，且a|b，a|c，那么a就是b和c的公因数。在所有公因数中最大一个，称为最大公因数，并记为gcd(b,c)[3]。

定义2：若a和b的最大公因数是1，即gcd(b,c)=1，则称a和b互素[2]。

定义3：设a，b∈Z,n≠0如果n|(a-b)，则称a和b模n同余，记为ab(modn)，整数n称为模数[3]。

定义4：元素x∈Zn有乘法逆元x-1，当且仅当x和n的最大公因子是1，即gcd(x,n=1)，即x和n互质。如果x的逆元存在，必定满足x×x-1modn=1[3]。

定理1：若a和n互素，则aφ(n)=1modn，称为欧拉定理（简称Euler定理）。

证明：设Zn={a1,a2,...aφ(n)}是模n的一个群集，由于gcd(a,n)=1，根据同余性质ab=a1b1(modn)，故aZn={aa1,aa2,...aaφ(n)}也是模n的一个群集，即■a1■(aa1)(modn)。因此aφ(n)1modn。

定理2：若是p素数，a是正整数且gcd(a,p)=1则ap-11modp，称为费尔玛定理。（简称Fermat定理）[1]。

定理3：设n是一正整数，小于n且与n互质的正整数的个数称为n的欧拉函数，记为φ(n)，若n是素数，则显然有φ(n)=n-1[1]。

推论1：若n是两个素数p和q的乘积，则φ(n)=φ(p)×φ(q)=(p-1)×(q-1)

推论2：对任意非负整数a和正整数b有gcd(a,b)=gcd(b,amodb)。

证明：因为b是正整数，所以可将a表示为a=kb+rrmodb，amodb=r，其中为k一整数，所以amodb=a-kb，设d是a，b的公因子，即d|a，d|b，所以d|kb，由d|a和d|kb得d|(amodb)，因此a是b和amodb的公因子。所以得出a，b的公因子集合与b，amodb的公因子集合相等，两个集合的最大值也相等。

3.RSA公钥算法描述

3.1密钥选择

RSA加密算法的密钥选择方法是该算法的核心，RSA密钥的选择和生成方法保证了RSA公钥加密算法的安全性。先选择两个素数p和q。这两个素数的乘积就是RSA密钥中的正整数n，即n=p×q，如果p和q足够大，那么乘积n也就足够大，如再分解p和q困难性极大，这样就可以满足了公钥密码系统的要求，根据欧拉函数计算出φ(n)=(p-1)(q-1)。然后，随机选取整数e，满足1＜e＜φ(n)，并且gcd(e,φ(n))=1，作为加密密钥。最后求出d=e-1modφ(n)，作为解密密钥。则(e,n)为公钥，d为私钥，p和q为秘密参数，需要做保密处理。

3.2加密运算

加密消息时，先将它分成比n小的数据分组，采用二进制数，选取小于n的2的最大次幂，也就是说，如果p和q为200位素数，那么n将400有位，每个消息分组mi小于400位长,加密后的密文将由相同长度的分组组成ci， 加密公式为c=memodn 如果需要对密文c进行解密，则只需要c对进行d次乘法运算，然后再对乘积取n的模，得到明文m。

3.3解密运算

解密公式为m=cdmodn，因为d=e-1modφ(n)，等式两边同乘以e将等式转化为d×e=1modφ(n)。根据模运算性质可知d×e=kφ(n)+1，其中k是一个大于等于的整数。根据加密公式和模运算性质可知cdmodn=(me)dmodn=mkφ(n)+1modn，利用指数运算性质m×mkφ(n)modn=m×1modn=m。

3.4 计算问题

通过分析RSA算法的求解过程，可知RSA通过乘法与除法加以实现的。可想而知，RSA算法将执行大量的乘除法运算，从而导致RSA算法的加密与解密速度十分慢[6]。因此，大整数的乘除法成为影响RSA算法速度的重要因素。利用模运算的性质：(a×b)modn+[(amodn)×(bmodn)]modn可以大大减少中间运算环节，提高运算速度。例如求am，其中a和m是正整数， m表示为二进制形式bk,bk-1,bk-2，…b0即m=bk2k+bk-12k-1+…+b12+b0。

4.RSA算法的安全性分析

4.1欧几里得(Euclid)算法[2]

欧几里得算法是基于推论2作为求两个正整数的最大公因子的简化过程，是数论中的一个基本算法理论。当两个正整数互素时，可以求出其中一个数关于另一个数的乘法逆元。设输入两个正整数为b，a并设a＞b. ①xb；ya；②ifY=0then returnX=gcd(b,a)；③R=XmodY；④X=Y；⑤Y=R；⑥goto

4.2由n破译p和q

RSA算法安全性是建立在大数的因数分解基础上，下面解决大数的分解。若n=p×q被因子分解，则RSA便被攻破，因为在p和q已知的情况下，则利用欧拉函数可以解出φ(n)=(p-1)×(q-1），再利用欧几里得算法求出以φ(n)为模的公钥的e乘逆元d，就可以破译出RSA的秘密私钥。

若n无法分解时，如果破译者知道φ(n)的值也能够进行破译。已知n=p×q，φ(n)=(p-1)(q-1）=n-p-q+1，p+q=n-φ(n)+1，利用配方法得(p+q)2-4n=(p+q)2-4p×q=(p-q)2，即p-q=■联立方程组(p+q)和(p-q)可得p=■，q=■ ,d也可以很容易地得到。也就是说，如果能够以一种可行的方法直接得到φ(n)，破译者就可以对其进行破译。

4.3 合理选定参数

在设计RSA算法时，应使分解n=p×q的上不可行，对p和q的主要限制是：第一，p和q足够大，这样可以基本保证不会在有效时间内被破译者破译。 第二：差值|p-q|不宜太小，最好与p，q数位接近，如果p和q的数值相当接近，则(p+q)≈2■，并且■(p-q)是一个相当小的数，因此等式■■-n=■■等式右边为平方数，因此可进行因子分解。第三：d=gcd(p-1,q-1)应尽量小，这样可以减小将n因数分解的可能性。第四：p-1与q-1都应该至少含有一个大素数因子，p+1与q-1也至少含有一个大素数因子，否则就可能利用重复加密攻击的方法求出n的真因数。

4.4参数e和d选择原则

在选好p和q后，要选取满足gcd(e,φ(n))的e值是很容易的，因为两个随机数互素的概率为0.6，若采用小的e，可加快加密的速度，但e太小时易遭加密指数的攻击。 这是因为第一：当e过小时，对小的m，可能出现的me＜n情况，此时c=memodn=me即未取模，由c直接开e次方就可求出明文m。 第二：加密指数的攻击，令网中有3个用户为加快速度，均选用e=3，而有不同的模n1,n2,n3，一般情况下其模n1,n2,n3是互素，否则可求出构成n1,n2,n3的两个因子p和q中的1个，进而导致解密密钥被破解。 若有1用户要将明文n传给这3个用户，其密文分别为：c1=m3modn1，c2=m3modn2,c3=modn3 ，令设c=m3mod(n1×n2×n3)利用中国剩余定理可以求出c，故c=m3,m=■即失密。

5.结语

RSA公钥密码算法是迄今为止在求解密码问题中最为成熟理论之一，RSA的基础是数论的欧拉定理，它的安全性依赖于大数的因数分解困难性。RSA算法不仅可用于加密/解密,还可以运于数字签名，密钥交换等方面。本文通过对RSA公钥密码算法分析，在RSA公钥密码算法安全性上做出具体的分析并给出较为合理参数体系结构，对进行密钥设计与求解私钥具有一定的借鉴作用[7]。

参考文献:

[1]陈波,于泠,肖军模.计算机系统安全原理与技术[M]. 北京:机械工业出版社2006. 1

[2]凌捷,谢赞福.信息安全概论[M].广州:华南理工大学出版社2005. 8

[3]杨波.现代密码学[M].北京:清华大学出版社2003. 7

[4]殷彬,陶安等. RSA算法的一种高效软件实现方法[J]. 微计算机信息. 2006(33):258-259

[5]鄢喜爱,杨金民等.RSA公钥密码算法的分析[J].长春工业大学学报. 2006(27):142-144

[6]滕济凯. 基于RSA的公钥叛逆追踪方案[J].计算机工程. 2008(13):152-153

[7]宋晓莉,李敬兆等.RSA算法及其一种简单实现方法的设计[J].电子工程师.2004(30):35-37