Rsa
加密 M 與 N 不互質時的 RSA 漏洞
我已經用幾個測試案例進行了測試，它看起來像密文 $ M^e $ 當 e=3 時，RSA 的值總是與 N 互質。有什麼原因嗎？如果密文會發生什麼 $ M^e $ 當 e=3 時與 M 不互質？
什麼時候 $ N = pq $ 是兩個素數的乘積，唯一不互質的數 $ N $ 是那些包含 $ p $ 或者 $ q $ 作為一個因素。當然有可能 $ M^3 $ 可被任何一個整除 $ p $ 或者 $ q $ 所以你的觀察一般來說是不正確的。一個例子：
$$ M = 42\ N = 7*13 = 91\ M^3 \equiv 14 \pmod{91} $$ 顯然 14 和 91 不是互質的——它們都共享 $ 7 $ 作為一個因素。計算 GCD $ c = M^3 $ 和 $ N $ 因此洩漏 $ 7 $ 作為一個因素 $ N $ , 破壞 RSA。