一种基于连分数逼近Legendre定理的RSA攻击算法

江宝安

(重庆移通学院 重庆 401520)

(重庆邮电大学 重庆 400065)(1487663252@qq.com)

本文提出一种基于Wiener算法的改进型连分数RSA攻击算法，本文算法弱化小解密指数d的Wiener限制条件，扩大d的选择范围.

1 Wiener算法

证明.由RSA算法知，存在正整数k，满足

ed=kφ+1，

其中φ=φ(n)为欧拉函数.

上式2边同除dφ，得

而

则

证毕.

不妨设p>q，由以下公式验证k,d的正确性.

令

则

p=u+v,
q=u-v，

p,q为素数,

若n=pq, 则p,q,k,d即为所求值.

2 连分数RSA攻击算法

设p,q为素数，n=pq是RSA模，给定n和加密指数e.存在正整数k，满足RSA方程ed=kφ+1，其中φ=φ(n)为欧拉函数,由

φ=(p-1)(q-1)=pq+1-(p+q)=

3 计算实例(matlab源程序)

%**********************************

n=28562942440499; % n=p*q;

e=7502876735617; % 公钥(n,e)

%实二次无理数是循环连分数算法

e/(sqrt(n)-1)^2

D=4*n*e^2;

c1=-(n+1)*e; q1=-e^2;

a1=floor((sqrt(D)+c1)/q1);

c2=a1*q1-c1; q2=(D-c2^2)/q1;

a2=floor((sqrt(D)+c2)/q2);

c(1)=c1;c(2)=c2;

q(1)=q1;q(2)=q2;

a(1)=a1;a(2)=a2;

for j=2:12

c(j+1)=a(j)*q(j)-c(j);

q(j+1)=q(j-1)+(c(j)-c(j+1))*a(j);

a(j+1)=floor((sqrt(D)+c(j+1))/

q(j+1));

end

x=a;

%**********************************

%连分数a/b算法

Po=0;P(1)=1;

Qo=1;Q(1)=x(1);

P(2)=P(1)*x(2)+Po;

Q(2)=Q(1)*x(2)+Qo;

for j=3:12

P(j)=P(j-1)*x(j)+P(j-2);

Q(j)=Q(j-1)*x(j)+Q(j-2);

end

%**********************************

%验证k，d

for i=1:12

u=0.5*((n+1)-(e*Q(i)-1)/P(i));

v=sqrt(u^2-n);

q1=round(abs(u+v));

p1=round(abs(u-v));

if (p1*q1==n)

k=P(i),d= Q(i),p=p1,q=q1,

break

end

end

f=(p-1)*(q-1); f1=(sqrt(n)-1)^2;

df=(f1-f);

d1=f1/(2*e*df) *(1+sqrt(1+2*e*f*

df/f1)) , %d

%**********************************

其他计算实例：

公钥(n,e)=(15 770 708 441,3 414 331 633)⟹(p,q,d)=(135 979,115 979,97)；

公钥(n,e)=(6 394 628 164 909,8 854 840 583)⟹(p,q,d)=(2 658 899,2 404 991,22 387).

由于matlab数值精度问题，没有进行更多位数RSA攻击算法的计算.

由上证明，只要满足

总能找到解密指数d，即能分解n，攻击成功.

4 结 论

RSA密码算法是现代广泛应用的一种公钥密码体制，对其攻击算法研究受到人们极大的关注，虽然存在多种RSA攻击算法[7-10]，但是使用连分数逼近定理的Wiener算法相对来说是一种有效的算法，本文在Wiener算法的基础上进行改进，提出的新算法相对Wiener算法性能更好，解码指数范围远大于Wiener算法，具有适用范围广、成立条件宽松、解密指数d的选择范围大等优点.