Factors of RSA modulus
In the article A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, the original RSA article, it is mentioned that Miller has shown that n (the modulus) can be factored using any multiple of φ(n).
想像一下，我知道公鑰和私鑰。但我真正想要的是n、p和q的因子，但我不能在大量n中使用任何分解算法。
在米勒的文章中，假設說我如何找到這兩個因素，知道公鑰和私鑰。但我無法理解它是如何完成的。有人知道嗎？或者有一個小例子？
雖然羅伯特展示的方式可以工作，如果[Math Processing Error] $ e $ 很小（如果 $ e \cdot d \equiv 1 \pmod{\phi(n)} $ （這不一定是真的），有一種稍微複雜一點的方法在任何情況下都可以使用。
我們所做的是計算[Math Processing Error] $ \lambda = (e \cdot d - 1)/ 2^k $ 奇數（和[Math Processing Error] $ k $ 是使[Math Processing Error] $ \lambda $ 奇怪的。特殊屬性 $ \lambda $ 有就是這樣[Math Processing Error] $ (m^\lambda)^{2^k} \equiv 1 \pmod{n} $ 對於任何[Math Processing Error] $ m $ 相對於[Math Processing Error] $ n $ .
這是我們如何使用它；我們隨機選擇[數學處理錯誤] $ m $ , 併計算 $ m^\lambda \mod n $ . 如果是 1 或 $ n-1 $ ，我們返回並選擇另一個 $ m $ .
如果不是，我們反復平方值（ $ \mod n $ )，並檢查值是否變為 1 或 $ n-1 $ （並且因為 $ \lambda $ 的屬性，最多變成兩者之一 $ k $ 平方，除非我們碰巧選了一個 $ m $ 這不是相對重要的 $ n $ ); 如果值變成 $ n-1 $ ，我們回去，然後選擇另一個 $ m $ . 但是，如果它變為 1，則意味著前一個值 $ z $ 擁有財產 $ z^2 \bmod n = 1 $ , 這意味著 $ gcd(n,z-1) $ 和 $ gcd(n,z+1) $ 是的因素[數學處理錯誤] $ n $ .
而且，至少有 1/2 的可能[數學處理錯誤] $ m $ 值將導致分解，因此這種方法是實用的。
通常，公共指數很小。那麼如果你知道公鑰和私鑰，那麼你可以計算 $ e.d=1+k.\phi(n) $ . k 小於 e 並且 $ \phi(n) $ 在 n 的範圍內。一種直接的方法允許對除 ed-1 的小 k 進行詳盡的搜尋，使得[數學處理錯誤] $ \frac{e.d-1}{k} $ 是一個整數。
然後 $ \phi(n)= p.q -(p+q)+1 $ 允許找到 $ p+q $ 求解一個二次方程直接給出 p 和 q。
這是最簡單的方法，很容易實現。