连分数攻击
连分数
每个数都可以分解成连分数的形式,对一个分数做连分数展开就是在对分子和分母做辗转相除,例如
$${72 \over 28} = 2 + {16 \over 28}$$
$${28 \over 16} = 1 + {12 \over 16}$$
$${16 \over 12} = 1 + {4 \over 12}$$
$${12 \over 4} = 3 + 0$$
所以$72 \over 28$展开为连分数为
$${72 \over 28} = 2 + {1 \over {1 + {1 \over {1 + {1 \over 3+0}}}}}$$
连分数定理
连分数定理:当a和b满足$|{g \over d} - {a \over b}| < {1 \over 2b^{2}}$时,则${a \over b}$是${g \over d}$的一个连分数近似
也就是说如果我们有两个数之比$a \over b$与另一个已知值相近(准确来说一个分值代数式与另一个已知值相近)时,我们可以利用连分数定理去试图找到$a \over b$
维纳攻击
在RSA中,$\phi(N)=(p-1)(q-1)=N-(p+q)+1$
又因为$p*q$远大于$p+q$,所以有$\phi(N) \approx N$
因为
$$ed-1=k*\phi(N)$$
对上述式子两边同时除以$d*\phi(N)$有
$${e \over {\phi(N)}} - {k \over {d}} = {1 \over {d*\phi(N)}}$$
因为$\phi(N) \approx N$,所以用$\phi(N)$替换N,则有:
$${e \over {N}} - {k \over {d}} = {1 \over {d*N}}$$
因为d*N很大,所以$1 \over {d*N}$接近于0,所以上式可以变为:
$${e \over {N}} \approx {k \over {d}}$$
所以我们用连分数形式展开$e \over N$,其近似解中就可能会出现$k \over d$
从而可以求出$\phi(N)={{e*d-1} \over k}$,从而求出m
维纳攻击生效条件:
$$q<p<2q\ and\ d<{{1} \over {3}}N^{1 \over 4}$$
总结
连分数攻击不仅是适用于维纳,我们在遇到有值相似时都可以试图用连分数展开去求,所以我们不要被限制了思想,要开阔我们的眼界
兄弟写的非常好 https://www.cscnn.com/