陕西理工学院毕业论文（设计）
选取原则如下：
① e不可过小。经验上e 选16位的素数，这样既可以有效地防止攻击，又有较快的加、解密速度。
② 最好选e 为mod?(n)的阶数，即存在i ,使得ei?1(mod?(n))，i 达到，可以有效地抗击攻击。
③ d 要大于n3.3.3 安全性分析
如果说RSA体制的安全性等价于因子分解，那就是说，作为公钥选择的（e,n）参数，n是不能轻易被因子分解的，否则构造单向函数的T=Φ（n）=(p-1)(q-1)就没有秘密可言了。原因很简单，RSA的安全性依赖于因子分解的困难性，目前因子分解速度最快方法的时间复杂度为：T=O(exp(sqrt(ln(n)ln ln(n))))=O(eln(n).lnln(n)0.3。选定e 后可使用欧几里德算法在多项式时间内计算出d。
)，且n因子被分解，就意味着RSA系统被攻破。
反过来，能攻破RSA系统，表明可以分解n的因子，不过这不是绝对的。所以出于安全性考虑，在设计RSA系统时，对n的选择是很重要的。
在RSA算法中,若n =p*q 被因数分解,则RSA便被攻破。因为若p,q 已知,则Φ(n)=(p- 1)*(q - 1)便可以计算出,解密密钥d 便可利用欧几里得算法求出。因此RSA的安全性是依赖于因数分解的困难性。在上一节的参数分析中我们重点讲了对各参数选取原则，这里不再重复。在许多实际应用中，人们总希望使用位数较短的密钥d，一是可降低解出或签名的时间，二是能够满足计算能力低于主机的硬件芯片的需求，比如IC卡中的CPU处理。
现在我们就分析几个RSA体制的安全性问题。 （1）弱密钥情形
类似其他密码体制一样，RSA体制也存在弱密钥现象。若已知明文组
m1=123,m2=183,m3=72,m4=30,假定n=pq=17X11=187，取e=7时，可以发现，明文m经过RSA连续
变换后，就能恢复原文。比如:根据Ck=RSA（mk?1）=mk?1（mod n），则有： C1=123=183（mod187） C2=183=72（mod187） C3=72=30（mod187） C4=30=123（mod187） 这时C4=m1，对加密系统来说是不可靠的，必须加以克服。 （2）同模攻击的可能性
假定两个用户B1，B2共享一个模为n的RSA算法，加密密钥分别为me11e7777e1，e2，并且gcd(e1，
e2)=1，如果用户A想加密同一个明文m，分别从e1，e2加密得到密文：C1=me1 mod n和C2=me1mod n，分别将C1送给B1，C2送给B2。而攻击者截获两个密文后，可以通过使用扩展
第12页 共41页
陕西理工学院毕业论文（设计）
欧几里得算法得到r,s,使得r. e1+s. e2=1.然后按下列计算： C1.C2 mod n=(m1rse1)(m2e2)mod n= m
其中，m1=m2=m为同一明文，表明即使RSA密码系统很安全，但攻击者破获A发送的明文也是可能的。所以实际中建议不同用户不可使用公共的模n。除此之外，不同用户选用的素数也是不能相同的。否则，任何人都可以用欧几里得算法获得（n1，n2）= p，结果容易得到n1，n2的分解式。
（3）由密文泄露明文相关的部分信息量
与其他一些密码弱点一样，RSA体制同样存在将明文的部分信息由密文泄露出去的可能。比如给定密文：C=mmod n，由gcd(e,?(n))?1可知，其中e必为 奇数情形。根据Jcaobi符号容易推出.
因此，只要给定一个密文C，不用通过解密密文就能有效的计算出结果，即反映了在RSA密码系统中，通过加密密文也会泄露一些有关的明文信息。
3.4 公钥密码体制中安全大素数的生成
构造RSA公钥密码体制,关键就在于选取大素数p ，q 。产生素数的方法可分为以下两类:确定性素数的产生方法和概率性素数的产生方法。确定性素数产生方法的优点在于产生的数一定是素数,缺点是产生的素数带有一定的限制;而概率性素数产生方法的缺点在于它不能证明该数是素数,也就是说,产生的数只能是伪素数,为合数的可能性很小。但这种可能依然存在。优点在于使用概率性素数产生方法,产生的伪素数速度很快,构造的伪素数无规律性。于是在构造RSA体制中的大素数时,首先利用概率性素数测试产生伪素数,然后再利用确定性素数测试法进行检验,这样可以发挥二者的优越性。所以文中的算法基于这个原理,预先对密钥素数进行筛选,采用Montgomery模乘算法优化的概率性素数产生方法Miller-Rabin算法进行检测,最后用确定性素数产生方法Pocklington定理进行验证。
3.4.1 素数筛选
对于产生的大数,在进行后面的素数判别时会比较耗时,所以,在把大数送入到素数判别程序前,将一些容易判别出的合数过滤掉。这里采用大数除以小素数过滤掉一部分合数,选取53个小素数进行对大数的过滤。
算法的步骤如下:
(1) 随机产生一个大整数n ;
(2) 选取从2 开始的一组个数约为53个的素数,记为a[i] ; (3) i ←0;
(4) 当i< 53时,计算y ←n (mod a[i]);
第13页 共41页
e 陕西理工学院毕业论文（设计）
(5) 若y = 0,表示没有余数,则数n 不为素数,结束;否则,i ←i+ 1,转(4); (6) 若i= 52,返回n 为素数。 3.4.2 素数检测
素性检测就是判断一个整数是否为素数的准则。最简单的素性检测就是“试除法”,对于给定的数n ,用p 进行试除(0 Miller-Rabin算法是Fermat算法的一个变形改进,它的理论基础是由Fermat定理引申而来。Fermat定理:n是一个奇素数,a是任何整数(1?a?n-1) ,则a n?1= 1(mod n)。 rMiller-Rabin算法的理论基础:如果n是一个奇素数,将n-1= 2m ,r是非负整数,m是正奇数, a 是和n互素的任何整数,那么a≡1(mod n)或者对某个h(0?h?r-1),等式a ≡1(mod n)成立,其中w =2m 。 这个理论是通过一个事实经由Fermat定理推导而来:n是一个奇素数,则方程x=1mod n有±1两个解。 Miller-Rabin算法的步骤如下: ① 将n-1表示成2m(其中r 是非负整数, m 是正奇数) ; ② 随机产生一个整数a(1 ④ 若x=1或x=n-1,则n 通过测试,转(7); ⑤ 若i=1,则n为非素数,结束;否则转(6); ⑥ 当i Miller-Rabin算法并不是一个确定算法。若n 是奇合数,则n通过以a 为基的Miller-Rabin算法测试的数目最多为(n-1)/4,1?a?n - 1。若n 是正整数,选k个小于n 的正整数,以这k 个数作为基用Miller-Rabin算法进行测试,若n 是合数,k 次测试全部通过的概率为(1/4)。比如: k = 100, n 是合数, 但测试全部通过的概率为(1/4)(2). 采用Montgomery 算法进行优化 Miller-Rabin算法最耗时的步骤是(3)和(6)的模幂运算。Montgomery算法将部分积对任意的N 取模转化为对基数R 取模,简化了计算过程, 提高了模幂运算的速度. Montgomery算法的理论基础是:设N 和R是互素的两个整数,且RR ?1100k2m2hmwr, 这是很小的数,说明这样的事情几乎不可能发生。 - NN’=1(N’=-N ?1?1mod R) , 则对于任意整数T,当M = TN’mod R 时,( T+ MN)/R 为整数,且满足(T+MN) / R =TRmod N 。 第14页 共41页 陕西理工学院毕业论文（设计） ?1上述理论中,T+MN =T+(TN’- kR)N =T(1+ N’N)-kRN = TRR - kRN ,为R的倍数,所以(T+MN)/R ?1为整数。又因为T+ MN =T modN , 所以可以很容易推导出(T+ MN)/R= TR在算法中选取0< T ?1modN 。可以看出,Montgomery mod N 也就至多相差一个N ,只需一次 ?1额外的大数减法。这样就给出了满足0 ?1mod N的快速算法, 那么就可以类 mod N的计算步骤如下: ① 计算A’←AR mod N ,B’←B R mod N ,T←A’×B’; ② 选择与N互素的基数R ,并选取R且满足条件R×N > T; ③ 计算S ←{ T+[(Tmod R )×N’mod R]×N}/R ; ④ 若S?N , S=S-N ; ⑤ 返回S 。 然而,这样计算出的结果S 并不是严格意义上的模乘ABmod N ,而是多了一个因子RABmod N 可以通过两次Montgomery算法得到,即:ABmod N =(A*B *R*R ?1?1?1?1和N’,满足0 ?1 ?1-NN’=1 ,那么模乘 mod N)*R ?1mod N =Mon(A,B,N) mod N = S*1*R ?1mmod N =Mon(Mon(A ,B,N),1,N)。 所以模幂运算Z=a(mod n) 的计算步骤如下: ① i←m -1; ② 计算Z←Mon(a,1,n); ③ 计算Z←Mon(Z,1,n); ④ i←i- 1,若i> 0,转(3),否则转(5); ⑤ 返回Z。 可以看出, 如果仅仅是求模乘运算,Montgomery算法需要用到一般的模运算和模逆运算进行预处理,Montgomery算法并不能有任何速度上的提高,但对于模幂运算,模幂运算中约有(3log e)/2次的模乘运算,这样预处理时,只要处理一次就可以进行多次的没有除法的Montgomery模乘运算,这样将大大提高模幂运算的速度,进而提高Miller-Rabin算法的速度。 (3). 素数验证 采用Pocklington定理对素数进行验证,基于Pocklington定理的确定性素数产生方法,它需要已知n - 1的部分素因子。 Pocklington定理:设n = R *F + 1, 这里F=n?1满足:a r?1?qj?1r?jj,其中q1,q2,?,qr是不同的素数,若存在a ≡1(mod n)且gcd(a qj- 1,n) = 1,其中j =1,?, r 。那么n 的每一个素因子p 都有p=F *m + 1的形式(m ?1)。于是若F >n,则n 为素数。 则此算法的步骤如下:, ① 分解n - 1,使n - 1= R ·F ,其中F > n; 第15页 共41页 陕西理工学院毕业论文（设计） ② 分解F ,使F = ③ a ←1; ④ a ←a + 1; ⑤ 若a n?1?qj?j?1rj,其中qj( j = 1,2,?,r)为不同的素数; (mod n) = 1,则转(7); ⑥ 转(4) ,否则n 可能不是素数,转(8); ⑦ 若对于任意的j(j =1,2,?,r),gcd(a⑧ 退出。 3.5 RSA的Matlab实现 3.5.1算法原理 RSA算法的理论基础是数论中的欧拉函数，他的安全性基于大数分解的困难性，在理论上要计算两个大素数的乘积是容易的，但反过来要把一个大数分解成两个素数因子相乘的形式是很困难的，正是由于这个原因保证了此算法的安全性。 RSA的安全性依赖于大数分解。公钥和私钥都是两个大素数 （ 大于 100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。 密钥对的产生:选择两个大素数，p 和q 。计算：n = p * q 。然后随机选择加密密钥e，要求 e 和 ( p - 1 ) * ( q - 1 ) 互质。最后，利用Euclid 算法计算解密密钥d, 满足 e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) ) 其中n和d也要互质。数e和 n是公钥，d是私钥。两个素数p和q不再需要，应该丢弃，不要让任何人知道。 加密信息 m（二进制表示）时，首先把m分成等长数据块 m1 ,m2,..., mi ，块长s，其中 2^s <= n, s 尽可能的大。对应的密文是：ci = mi^e ( mod n ) ( a ) 解密时作如下计算： mi = ci^d ( mod n ) ( b ) 算法流程 （1）. 产生密钥 ① 任意选取两个不同的大质数p和q，计算乘积n=p*q； ② 任意选取一个大整数e，e与(p-1)*(q-1)互素，整数e用做加密密钥。注意：e的选取是很容易的，例如，所有大于p和q的素数都可用。 ③ 确定解密密钥d： d * e = 1 mod（p - 1）*（q - 1） 根据e、p和q可以容易地计算出d。 ④ 公开整数n和e，但是不公开d； 第16页 共41页 n?1qj- 1,n)= 1,则n 是素数,否则转(4);