1. RSA算法原理及内在特性

1.1 RSA算法描述

在该箅法中，公钥和私钥是两个大素数的函数，从其中一个密钥和密文恢复明文等价于将两个素数的乘积因子分解．为生成这两个密钥，选择两个大素数P和q，计算其乘积n=pq，再随机选取加密密钥e(一般e取3，17，65，537)，使得e与(p-1)(q-1)互素，*后用欧几里德算解密密钥d，使得d=e的-1次方mod((p—1)x(q—1))．在这种算法中e和d也是互素的，e和n为公钥，d为私钥，两个素数P和q和不再用到，但不能泄露．加密报文时，首先将m分成若干以数字表示的块，使得每块都有一个模n表示，即如果P和q均为100位的十进制素数，则n有近200位，并且每一报文块m，也近似200位．密义c由类似报文块大小的ci构成．加密公式Ci=Mi的e次方(mod(n))，解密时取一块Ci并计算：Mi=ci的d次方(mod(n))．

1.2 RSA算法的内在特性

1.2.1 存在不动点

当n是不含平方因子的整数且为k个素数因子之积时，对于任何奇数e，本算法的加密操作至少有3000个不动点．所以密钥对(e,n)的取值对于整个算法的安全性非常重要．

1.2.2 具有周期性

若x为整数，n为模数，并满足X的a+b次方与X的a次方modn为同一个等价类，则b为X的a次方modn的周期，记为per(x，n)．根据周期判定充要条件可知，若n由若干素数之积组成，则&(n)由一些小因子构成．只需知道&(n)的所有因子，私钥d马上可以通过公式ed=1mod&(n)求出(e与&(n)互质)。

1.2.3 对明文的要求

1的e次方=1modP，1的e次方=1modq．而e为奇数，所以(p-1)的e次方=p的-1次方modP成立，(q—1)的e次方=q的-1次方modq也成立．根据孙子定理，x=amodp=bmodq成立．当a与b分别取+1与-1时，对应的4个解是满足m的e次方=mmodn与(m,n)=1的解．至少4个明文组同时满足m的e次方=mmodn与(m,n)=1．所以，对于一些特殊明文，明文组会被加密成自己。

1.2.4 RSA算法的保密性

RSA算法的保密性在于对大数进行因数分解，这个时间比破译DES算法耗时长得多，但从长远考虑，笔者认为选择大于1024位长的模数n较为安全．

2. 常见的RSA算法破解方法

除因子分解法外，常见的黑客攻击方法有以下4种．

2.1 小指数攻击法

由DES与RSA的差异分析可知，RSA算法主要基于软件与硬件的结合实现，其加密速度远不如DES快．所以一些使用RSA算法进行加密的机构采用一种提升RSA速度并且能使加密易于实现的解决方案——令公钥e取较小的值．但这样做会使该算法的强度降低．若解密指数d的值为n值的114并且e<n时，使用小指数攻击法能解密d．

2.2选择密文攻击

这是一种绕开RSA基本算法直接攻击协议的方式．贸然签名的一方容易被黑客进行选择密文攻击．攻击者E只需将某信息作一下伪装(Blind)，让拥有私钥的实体A签名，再经计算就可得到E所想要的信息．例：E窃听A的通讯，并设法收集用A的私钥进行RSA算法加密的密文c，E希望将c解密得到明文p(p=c的d次方modnn)。

E首先选择一个小于n的随机数r，并根据x=r的e次方modn，y=x的e次方modn，t=r的-1次方modn得到A的公钥e．由上式可推出t=x的d次方modn．E再设法让A用其私钥签名y，由此对Y解密，A发消息给E(利用u=y的d次方modn),通过以上公式，E可以计算出它本不应该得到的P．

2.3公共模数攻击

如果网络中都使用同样的n，容易被黑客进行公共模数攻击。

例：p为明文，e1和e2为加密密钥，公共模数为n,则两个密文为C1=p的e1次方modn，C2=p的e2次方modn，由于e1，e2，c1，C2，n都已知，又e1和e2互索，由欧几里德算法可以求得r和s，满足rxel+s×e2=1．设r为负数，再用欧几里德算法可算出(C一1)与c2的乘积等于Pmodn，可见无需解密密钥即可还原出原始明文。

2.4计时攻击

类似于通过观察转动盘转出每个数字所用时间的方法猜测出密码数字组合。

若攻击者监视解密过程并精确计时，可以计算出d．例：攻击者根据所得到的时间t估计某个临时明文m1，计算ml加密的时间，与t进行比较．如果比t大，则再取个较小的临时明文m，将m作为m1，再计算加密时间井与t比较，算法的终止条件是直至比t小．设此时的明文为m，对ml与m：进行取中运算，计算新生成的m的加密时间．若比t大，则取中后的m作为m1；若比t小，取中后的m作为m2再进行循环，直至越来越靠近的ml与m2*终收敛成真正的密文m．