邓从政

(凯里学院理学院，贵州凯里 556000)

0 引言

一般地，RSA密码体制是利用Zn［1，2］的计算，设n=pq，其中，p，q为素数，ab=1(mod＞ (n)).对此，定义如下的加密函数，ek(x)=xbmodn，和解密函数，dk(y)=yamodn，其中，x，y∈Zn.这样n，b组成了公钥，p，q，a组成了私钥，x是要加密的明文，y =ek(x)是密文，b是加密指数，a是解密指数.假如知道了解密密钥a，那么可以按照以下流程来破译出被加密的明文x.

由于，

有，

假定，x∈Z*N，则有，

式(3)正是我们所期望的解密出来的明文［1］.

从以上的解密流程可以看出，攻击RSA密码体制就是攻击者能够拿到私钥，也就是能够计算出它的解密指数a.如果能做到这一点，那么就可以有效地破解对方发来的密文.事实上，目前有很多种计算私钥a的方法［3，4］，在此基础上，本文介绍一种利用有限简单连分数最佳有理逼近原理计算解密指数的方法来实现对RSA密码体制的有效攻击.

1 有限简单连分数最佳有理逼近原理

事实上，任何一个有理数都可以写成一个有限连分数的形式，

式中，a，b，q1，q2，q3，…，qm，都是非负整数.把［q1，q2，…，qk］，1≤k≤m，称为a/b的第k个渐近分数或者收敛子，容易看出，a/b=［q1，q2，…，qk］，称［q1，q2，…，qk］为连分数a/b的展式.若记，Ek为［q1，q2，…，qk］的第k个收敛子，则每一个Ek可以写成有理数ck/dk的形式，而其中的ck和dk满足如下的递推关系［2］，

且，c0=1，d0=0.

通常，一个有理数的连分数展式有很多有用的性质，基于本研究的目的，最重要的是如下有理数的最佳逼近原理，限于篇幅，这里不作证明.

2 利用逼近原理对RSA密码体制进行有效低解密指数的攻击与实现

假定 n = pq，p和 q为素数，ab≡1(mod＞ (n))，3a＜n1/4，且q＜p＜2q.也就是说，如果n的二进制表示长为x比特，那么当a的二进制表示的位……