為什麼e>n3/2和>n3/2e>n^{3/2}阻止維納的攻擊
據我了解，這是維納的攻擊。
認為 $ n=pq $ 和 $ q < p < 2q $ ， 和 $ d < n^{1/4}/3 $ 在哪裡 $ ed=k\phi(n)+1 $ 和 $ e < \phi(n) $ .
$$ \begin{align*} n-\phi(n) &=n-(p-1)(q-1)\ &= n-(n-p-q+1) \ &= p+q-1 \ &< 2q+q-1\ &=3q-1 \ &< 3\sqrt{n} \end{align*} $$ 和 $ e<\phi(n)\implies ke < k\phi(n) =ed -1 < ed \implies k<d<n^{1/4}/3 $ .
所以，
$$ \begin{align*} \left|\frac{e}{n}-\frac{k}{d}\right| &= \left|\frac{ed-kn}{nd}\right|\ &=\left|\frac{de-k\phi(n)-(kn+k\phi(n))}{nd}\right|\ &= \left|\frac{1-k(n-\phi(n))}{nd}\right|\ &\le \frac{3k\sqrt{n}}{nd} \ &\le \frac{3(n^{1/4}/3)\sqrt{n}}{nd} = \frac{1}{dn^{1/4}}\ &< \frac{1}{2d^2}. \end{align*} $$ 最後一個不等式（通過一些關於連分數的定理）和 $ gcd(d,k)=1 $ 暗示 $ \frac{k}{d} $ 是簡單連分數的收斂 $ \frac{e}{n} $ .
為什麼 $ e>n^{3/2} $ 暗示 $ k/d $ 不是簡單連分數的收斂 $ e/n $ ? 或者為什麼這樣 $ e $ 阻止維納的進攻？
足以證明 $ |e/n-k/d| > 1/d^2 $ .
謝謝！
在維納的進攻中 $ k $ 是一個小數（ $ k<d $ ）。如果我們設置 $ e^{’}=e+t\phi(n) $ 對於一些大 $ t $ 然後 $ e^{’} $ 可以用來代替 $ e $ 用於消息加密。此外，k 變成了一個很大的數字，我們不能使用 Wiener 的攻擊。有關更多詳細資訊，您可以查看“RSA 密碼系統的二十年攻擊”。