Rsa
在 RSA 中求逆
我已經在 RSA 上閱讀了一段時間，但有些東西我仍然無法理解。生成密鑰時：一旦你找到 n = pq 和 φ(n)，你選擇一個數字 d 與 φ(n) 互質，然後你需要找到 e d mod φ(n) 的倒數。
你不需要這樣做來知道 φ(φ(n)) 然後使用費馬小定理嗎？如果是這樣，您將需要找到 φ(n) = (p-1)(q-1) 的因式分解，因此對 (p-1)/2 和 (q-1)/2 進行因式分解。這可能不是很長嗎？
提前致謝
加布里埃爾
一旦你發現 $ n = pq $ 和 $ \phi(n) $ , 你選擇一個數字 $ d $ 與 $ \phi(n) $ 然後你需要找到 $ e $ 的倒數 $ d \bmod \phi(n) $
其實，我們通常做的是：選擇 $ e $ ; 然後找到素數 $ p $ 和 $ q $ 和 $ p-1, q-1 $ 與 $ e $ ，然後找到 $ d $ 這是倒數 $ e \bmod \text{lcm}(p-1,q-1) $ . 但這並不能回答你的問題。
難道你不需要這樣做才能知道 $ \phi(\phi(n)) $ 然後使用費馬小定理？
我想我們可以選擇素數 $ p $ 和 $ q $ 以某種方式讓我們知道因式分解 $ p-1, q-1 $ .
但是，我們（通常）不會。相反，我們使用擴展歐幾里得方法來找到所需的逆；這不需要我們知道因式分解 $ \phi(n) $ （或者 $ \text{lcm}(p-1, q-1) $ )