在哪裡φ(n)披(n)varphi(n)RSA的一部分從何而來？
$ e d \equiv 1 \pmod{\varphi(n)} $
在哪裡 $ \varphi(n) $ 部分來自？RSA 的發明者是如何得出結論的 $ \varphi(n) $ ?
$ \phi(n) $ 是數字的乘法群的階 $ \mathbb{Z}_n $ . $ \phi $ 稱為歐拉函式。拉格朗日定理的一個結果是一個群的任何元素，提升到群的階等於單位元素。
所以，使用 $ \phi(n) $ 確保解密有效。自從 $ ed\equiv 1\bmod{\phi(n)} $ ，我們可以說 $ ed-1\equiv\phi(n) $ 或者 $ ed\equiv\phi(n)+1 $ .
所以如果我們看 $ m^{ed}\bmod{n} $ 好吧，這和 $ m^{\phi(n)+1}\bmod{n} $ 這與 $ m^{\phi(n)}m^1\bmod{n} $ . 但由於 $ \phi(n) $ 是組的順序，我們知道 $ m^{\phi(n)}\equiv 1 $ 所以我們有 $ m^{\phi(n)}m^1\equiv 1m^1\equiv m\bmod{n} $ . 這證明了解密是有效的，我們只能證明它，因為我們選擇了 $ d $ 因此。
如果我們不使用 $ \phi(n) $ 數學不一定*工作，解密也不能保證工作。因此，RSA 的設計者使用 $ \phi(n) $ 出於需要。
*參見 fgrieu 的評論。任意倍數 $ LCM(p-1,q-1) $ 會工作。
在哪裡 $ \phi(n) $ 部分來自？
那麼，實際的要求是，如果 $ n = pq $ 和兩者 $ p $ 和 $ q $ 是素數，我們有：
$ de \equiv 1 \mod p-1 $
$ de \equiv 1 \mod q-1 $
第一個確保 RSA 加密，然後是 RSA 解密，將獲得原始值取模 $ p $ .
第二個確保 RSA 加密，然後是 RSA 解密，將獲得原始值取模 $ q $ .
當兩者都為真時，則 RSA 加密，然後再進行 RSA 加密，將取模得到原始值 $ lcm(p,q) = n $
而如果 $ de \equiv 1 \mod \phi(n) $ ，這將確保上述兩個都是正確的。
RSA 的發明者是如何得出結論的 $ \phi(n) $ ?
也許他們知道數論？
它不能是任何正整數互質嗎 $ e $ ?
不， $ d $ 和 $ e $ 必須滿足以上兩個條件；一種 $ d $ 用任意正整數互質選擇 $ e $ 不太可能。