RSA算法研究

摘要： RSA算法是密码学中使用最广泛的算法之一，它不仅可以用于加密明文，还可以用作数字签名。本文主要介绍了如何快速地获得一些不为一般人所知的常数，进而判断该数是否为素数，并给出了RSA算法的数学表达式，讨论了该算法中各参数的含义和由来。同时分析了对RSA算法常见的攻击方法：因子分解法，讨论RSA算法中各参数应该如何选取，才不容易分解。

关键词： RSA算法 素数 素勤公式 素性检测

在RSA算法中，将两个大素数求积非常容易，但是要将该乘积分解成两个大素数是非常困难的。判断一个数p是否为素数通常用不超过p 的所有整数去整除p，如果某一次被某一个不为1的整数整除了，则数p是合数；如果p不能被所有不超过p 的所有数去整除，则p为素数。但是对于100多位的大素数，采取这种方法效率极其低下。本文提出了基于概率检测的方法，即在一定的概率范围下认为被检测的数为素数，但这存在把一个合数误判为素数的风险。本文利用泰勒公式去得到一个指定位数的大数，然后用数论的方法来寻求一个较好的检测素性的方法，进而讨论了RSA算法中各参数对算法安全性的影响，以及常用的攻击方法。

1.RSA算法描述

我们对明文进行分组，用M表示，把密文分组用C表示，则RSA算法可以描述为：

加密：C=M mod n

解密：M=c mod n=（M ） mod n=M mod n

发送方和接收方都知道n的值。发送方知道e的值，而接收方知道d的值。所以{e，n}和{d，n}构成一对密钥，通常称{e，n}是公钥，{d，n}是私钥。

参数解释：

①p和q为两个大素数。

②计算n=pq。

③随机选取e，且满足1＜e＜Φ（n），gcd（e，Φ（n））=1。Φ（n）=（p-1）（q-1）。

得到公钥就是e和n。

④通过ed=1 modΦ（n），计算d。那么私钥就是d和n。

2.大数的生成

首先将一个函数用泰勒公式的若干项去近似代替，给参数随机选取一个值，就可以得到一个数，我们选取这个值的整数和小数点后若干位组成一个数，这样我们就得到了一个不为常人所知的大数。

例如：我们取e 这个函数，其n阶麦克劳林展开式为1+x+x /2！+…x /n！，一旦取定x和n的值就可求出它的值，取整数和小数点后若干位就得到了一个大数。如果该大数为奇数直接使用素性检测算法即可，否则将该大数加1或者重新选取参数值重新生成一个大数，然后使用素性检测算法判断是否为素数，如果在符合要求的概率范围内为素数则认为成功找到了一个素数,否则重新生成一个大素数，再次检测。

3.素性检测用到的数学知识

现在已经生成了大数p，要判断它是否为素数，需要以下的准备工作：

（1）若p是任意的正整数，则必有p=6k±h，其中h=0，1，2，3，4，5。

①当h=0，2，4时，p必为偶数。

②当h=3时，p为3的倍数的奇数。

③当h=1，5时，即p=6k±1不是偶数也不是3的倍数的奇数，称这种奇数为素性奇数。

因此，当k=0，2，3，4时，p一定不是素数。素数不是杂乱无章地存在，而是分布在y=6x±1的两条平行斜线上。素性奇数公式p=6k+1中包含了两类奇数，一类是素数，一类是类素奇数（即除了1和本身外，还能被除2，3之外的其它素数所整除，是素数与素数之积或乘方，可以表示为p=（6k ±1）（6k ±1）其中k ，k ∈N）。

p=6k±1，k∈N与p=（6k ±1）（6k ±1），k ，k ∈N这两个公式告诉我们：当k为任意自然数时，通过第一个公式可以计算出任意大的素性奇数，通过第二个公式可以计算出任意大的类素奇数。从素性奇数的集合中去掉类素奇数的集合，剩下的一定是素数。

（2）定理1：n是素数的充分必要条件是Φ（n）=n-1，其中Φ（n）是欧拉函数。

证明：①若n是素数，则{1，2，…，n-1}中的任何一数都与n互质，由欧拉函数的定义知，Φ（n）=n-1条件是必要的。

②若Φ（n）=n-1（n＞1），可用反证法证明n是素数。如果Φ（n）=n-1并且n是合数，则n有标准分解式，可导出Φ（n）＜n-1的矛盾。即条件是充分的。

定理2：若a 1（mod n），且满足1≤x＜n-1的自然数x，适合a ≠1（mod n），则n是素数。

证明：由题给条件知n-1整除Φ（n），又Φ（n）≤n-1，故Φ（n）=n-1。由定理1，知n是素数。

推论：若2 1（mod n），并且1≤x＜n-1时，都有2 ≠1（mod n），则n是素数。

因此，2 1（mod n）是判断n为素数的必要非充分条件。

4.素性检测算法

（1）用泰勒公式产生一个大数p，判断该大数是否为奇数，是奇数则转（2），如果不是奇数则将该大数加1然后转（2）。

（2）计算（p+1）mod6是否为0，为0则转（3），不为0则计算（p-1）mod6是否为0，如果为0则转（3），否则转（6）。

（3）计算2 1（mod n）是否成立，如果成立则转（4），否则转（6）。

（4）用2000以内的小素数去除p看能否除尽，不能除尽转（5）否则转（6），这样可以排除大量的类素奇数。

（5）产生随机数a且a＜p，计算v=a modp，如果v≠1且v≠-1则转（6），否则输出p为素数退出算法。

（6）p=p+2，转（2）。

5.RSA的安全性

攻击RSA算法的方法比较多，主要是因子分解方法。

要解密密文分组C，需要获得密钥d，由于d=e modΦ（n），为了求得d需要求出Φ（n）的值，为了求出Φ（n）的值需要对n进行分解，因此RSA算法的安全程度依赖于对n的分解难度。

为了增大对n的分解难度，对参数的选择需要加以限制，现就RSA算法的参数讨论如下：

（1）p，q选择强素数，否则不能防御某些特殊的因子分解方法。

假设p，q不是强素数。可以假设p-1没有大的素因子，p-1=p…p，其中p 为素数，a 是自然数（1≤i≤m）。可以设p ＜A（1≤i≤m），A为一较小的整数，此时分解n就比较容易。我们可以设a≥ai（1≤i≤m），可以构造B=p…p，此时必有（p-1）|B。由费马定理知道，2 =1modp，又因为有（p-1）|B。我们如下处理x =y mod n，可以把x 看成是p的某整数倍加1。

（2）如果2 =y mod n中，y=1，则把x换成3……，直到y≠1。那么，gcd（y-1，n）=p，因为y应该为p的某整数倍加1。由此可以求出p与q。

（3）p与q之差要比较大，否则n≈（p+q） /4-（p-q） /4。也就是说n 接近（p+q）/2，逐个找比n 略大的自然数N，到使（N -n）是一个完全平方数。可以设x =N -n，则n=N -x =（N+x）（N-x），则p=N-x，q=N+x。

（4）p，q应该足够大，使得在计算上分解n是不可能的。

（5）gcd（（p-1），（q-1））不可过小，否则攻击者可以采用迭代方法对密文C=Memod n反复进行e次幂的运算。c ，c ，…到出现c的e 次幂mod n为c时为止。则c的e 次幂mod n为M，当t不是很大时，这种攻击是有效的。由Eluer定理知e =1modΦ（n），同样由Eluer定理，t的最小值有t=Φ（Φ（n））=Φ（（p-1）（q-1）），如果gcd（（p-1），（q-1））小，Φ（Φ（n））就很大，t就会很大。

（6）e不可选择过小，否则虽然加密速度快但可以采用小指数攻击。在C=Memod n中，如果e选择过小，可能没有模n的运算，可以通过直接开平方得到。一般选择使e =1modΦ（n）中的i尽可能大的e。

（7）密钥d的选取是最为关键的，应使d＞N 且越大越好，这是因为当d的长度小于N的长度的0.25倍时，攻击者可能通过连分数方法在多项式时间内求出d，而当d＞N 时，攻击者只能采用穷举攻击法。若d较小，则显然破译困难远比大因子分解的难度小，系统被直接攻破的可能性较大。另外，d又不能太接近e，否则RSA密钥系统较容易被攻破，因为攻击者最喜欢从比较小的数和e附近进行攻击。

（8）定时攻击方法类似窃贼通过观察别人转动拨号转盘的时间或手势来猜测所拨电话号码。假定加密算法使用了一个取模乘法函数，这个函数在大多情况下都运行较快，但是有些情况下花费时间比平均的一个取模指数运算时间长。这种情况下一次迭代的执行时间会大于整个算法的平均执行时间，以至于这种攻击可以奏效。

不过防范定时攻击的方法也比较多，常见的有以下几种：一是保证所有的取幂操作在返回时，花费同样多的时间，使得攻击者无法通过观察时间来攻击。二是通过对取幂算法增加一个随机延时来迷惑定时攻击者。三是在进行取幂运算之前先用一个随机数与密文相乘，防止攻击者了解计算机正在处理的密文。

6.总结

本文主要论述了RSA算法的数学表达式，并且论述了如何获得RSA算法所需的大素数，在此基础上进一步讨论了RSA算法的安全性问题。

参考文献：

［1］关振胜.公钥基础设施PKI与认证机构CA［M］.北京：电子工业出版社，2002.

［2］王衍波，薛通.应用密码学［M］.北京：机械工业出版社.

注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文