RSA : M 和 n 之間的公因數

假設我們有一個經典的 RSA 加密，n = p*q。對於給定的 C，我在 Internet 上看到，如果我們知道明文 M 和 n 具有共同因子，則 RSA 可能很弱。但是，我無法找到證據。

我們知道 $ M=C^e \space mod;n $ ，其中 e 是公鑰。我試著這麼說 $ M = a + k*n $ ，其中 a 和 k 為正整數，並重做算法。所以 ：

$ C = M^e;mod;n = (a + k*n)^e;mod;n = a^e;mod;n $

和

$ M = C^d;mod;n = a^{d*e};mod;n $

然而，這聽起來毫無用處，因為我們不知道 a（即使使用殘酷的力量，如果 $ n $ 很大）和 $ d $ ，顯然因為它是私鑰。有人可以幫我解決這個問題嗎？

對於給定的 C，我在 Internet 上看到，如果我們知道明文 M 和 n 具有共同因子，則 RSA 可能很弱。但是，我無法找到證據。

這很簡單；我們都知道 $ C $ 和 $ n $ ; 如果 $ M $ 有一個共同的因素 $ n $ , 也是 $ C $ . 所以，我們可以計算 $ \gcd(C, n) $ . 既然我們知道 $ M $ 和 $ n $ 有一個公因數，那麼這不是1；我們假設 $ C < n $ ，所以不是 $ n $ . 因此，這必須是一個適當的因素 $ n $ ; 如果 $ n $ 是兩個素數的乘積，這將是其中之一，因此兩個素數因數 $ n $ 然後是 $ \gcd(C, n) $ 和 $ n / \gcd(C, n) $ .

一旦我們有了因式分解 $ n $ 然後（假設我們知道值 $ e $ ), 計算 $ d $ 是直截了當的。

引用自：https://crypto.stackexchange.com/questions/99220