同样 dφ(n) 是一个很大的数,所以 e /N 略大于 k /d, e 和 N 是我们是知道的,公钥中给我们的,所以我们计算出来 e /N后,比它略小的 k / d 用计算 e /N 的连分数展开,依次算出这个分数每一个渐进分数,由于 e /N 略大于k/ d,wiener 证明了,该攻击能精确的覆盖 k/d。
import gmpy2 deftransform(x,y): #使用辗转相处将分数 x/y 转为连分数的形式 res=[] while y: res.append(x//y) x,y=y,x%y return res defcontinued_fraction(sub_res): numerator,denominator=1,0 for i in sub_res[::-1]: #从sublist的后面往前循环 denominator,numerator=numerator,i*numerator+denominator return denominator,numerator #得到渐进分数的分母和分子,并返回
#求解每个渐进分数 defsub_fraction(x,y): res=transform(x,y) res=list(map(continued_fraction,(res[0:i] for i inrange(1,len(res))))) #将连分数的结果逐一截取以求渐进分数 return res
defwienerAttack(e,n): for (d,k) in sub_fraction(e,n): #用一个for循环来注意试探e/n的连续函数的渐进分数,直到找到一个满足条件的渐进分数 if k==0: #可能会出现连分数的第一个为0的情况,排除 continue if (e*d-1)%k!=0: #ed=1 (mod φ(n)) 因此如果找到了d的话,(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n) continue phi=(e*d-1)//k #这个结果就是 φ(n) px,qy=get_pq(1,n-phi+1,n) if px*qy==n: p,q=abs(int(px)),abs(int(qy)) #可能会得到两个负数,负负得正未尝不会出现 d=gmpy2.invert(e,(p-1)*(q-1)) #求ed=1 (mod φ(n))的结果,也就是e关于 φ(n)的乘法逆元d return d print("该方法不适用") e = n = d=wienerAttack(e,n) print("d=",d)`
当然,python中有winner attack库,可以直接使用:
1 2 3 4 5 6 7 8
import RSAwienerHacker
N = e =
d = RSAwienerHacker.hack_RSA(e,N) if d: print(d)
3.扩展 Wiener’s Attack:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
from Crypto.Util.number import * from gmpy2 import invert c = e2 = e1 = N = a = 0.356#731./2049 M1=N**0.5 M2= N **(a+1) D = diagonal_matrix(ZZ,[N,M1,M2,1]) M=matrix(ZZ,[[1,-N,0,N**2],[0,e1,-e1,-e1*N],[0,0,e2,-e2*N],[0,0,0,e1*e2]])*D L=M.LLL() t=vector(ZZ,L[0]) x=t*M**(-1) phi = int(x[1]/x[0]*e1) d = invert(0x10001,phi) m=pow(c,d,N) print long_to_bytes(m)