一種基于連分數(shù)逼近Legendre定理的RSA攻擊算法

江寶安

(重慶移通學(xué)院 重慶 401520)

(重慶郵電大學(xué) 重慶 400065)(1487663252@qq.com)

本文提出一種基于Wiener算法的改進型連分數(shù)RSA攻擊算法，本文算法弱化小解密指數(shù)d的Wiener限制條件，擴大d的選擇范圍.

1 Wiener算法

證明.由RSA算法知，存在正整數(shù)k，滿足

ed=kφ+1，

其中φ=φ(n)為歐拉函數(shù).

上式2邊同除dφ，得

而

則

證畢.

不妨設(shè)p>q，由以下公式驗證k,d的正確性.

令

則

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

p,q為素數(shù),

若n=pq, 則p,q,k,d即為所求值.

2 連分數(shù)RSA攻擊算法

設(shè)p,q為素數(shù)，n=pq是RSA模，給定n和加密指數(shù)e.存在正整數(shù)k，滿足RSA方程ed=kφ+1，其中φ=φ(n)為歐拉函數(shù),由

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

3 計算實例(matlab源程序)

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

n=28562942440499; % n=p*q;

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

%實二次無理數(shù)是循環(huán)連分數(shù)算法

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;

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

%連分數(shù)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數(shù)值精度問題，沒有進行更多位數(shù)RSA攻擊算法的計算.

由上證明，只要滿足

總能找到解密指數(shù)d，即能分解n，攻擊成功.

4 結(jié) 論

RSA密碼算法是現(xiàn)代廣泛應(yīng)用的一種公鑰密碼體制，對其攻擊算法研究受到人們極大的關(guān)注，雖然存在多種RSA攻擊算法[7-10]，但是使用連分數(shù)逼近定理的Wiener算法相對來說是一種有效的算法，本文在Wiener算法的基礎(chǔ)上進行改進，提出的新算法相對Wiener算法性能更好，解碼指數(shù)范圍遠大于Wiener算法，具有適用范圍廣、成立條件寬松、解密指數(shù)d的選擇范圍大等優(yōu)點.