歐拉定理與 RSA 有什麼關係？
在 RSA 中，我們計算 e（加密密鑰）和 d（解密密鑰） $ \bmod phi(n) $ 並不是 $ \bmod n $ ，那麼當我們得到密鑰並加密和解密我們使用的 $ \bmod n $ 不是 $ \bmod phi(n) $ 使用以下規則：
加密： $ C =(m^e) \bmod n $
解密： $ m = C^d = (m^e)^d \bmod n = m^{e.d} \bmod n = m^1 \bmod n = m \bmod n $
我不明白怎麼來 $ e \cdot d=1 $ 即使它 $ \bmod n $ 不是 $ \bmod phi(n) $ ? 因為實際上它不等於 $ 1 $ . 我不明白是怎麼回事；如果不等於 $ 1 $ 它仍然會成功破譯。
例子：
給定 $ p = 11 $ , $ q = 3 $ 和 $ n = 33 $ , $ phi(n) = (p-1)(q-1) = 20 $ , $ e = 3 $ 所以 $ d = 7 $ 自從 $ e \cdot d = 1 \bmod phi(n) $
讓我們加密數字 $ 15 $
$$ C = 15^3 \bmod n= 9 $$
$$ m = 9^{7} \bmod n=15 $$
但
$$ 9^7 = (15^{3})^7 = 15^{7 \cdot 3}=15^{21} =15 \mod n $$
我們怎麼可能只使用成功破譯它 $ \bmod n $ 並不是 $ \bmod phi(n) $ ? 所以 $ e \cdot d =21 $ 並不是 $ 1 $ 仍然得到 $ m $ ? 我有一種感覺，歐拉定理（ $ m^{phi(n)}=1 \bmod n $ ）與此有關，但我不知道怎麼做！
對於給定的 $ n>1 $ , 讓整數 $ f>0 $ 對所有人 $ m $ 在 $ [0,n) $ 和 $ \gcd(m,n)\ne1 $ 它持有 $ m^f\bmod n=1 $ . 一個這樣的整數 $ f $ 是歐拉方程 $ n $ , $ \operatorname{phi}(n) $ 又名 $ \varphi(n) $ , $ \Phi(n) $ 或者 $ \phi(n) $ . 在這麼多的歐拉定理中，問題中的一個可能是關於歐拉全能的那個性質。最小的這樣 $ f $ 是 $ \lambda(n) $ ， 在哪裡 $ \lambda $ 是卡邁克爾函式。
認為 $ e $ 和 $ d $ 已被選擇為 $ e\cdot d\bmod f=1 $ . 根據運營商的定義¹ $ \bmod $ 是當它左邊沒有左括號時，這意味著：存在整數 $ k $ 這樣 $ e\cdot d=k\cdot f+1 $ （和 $ 0\le1<f $ , 代表)。
現在，假設 $ \gcd(m,n)=1 $ , $$ \begin{align} \left(m^e\right)^d\bmod n&=m^{e\cdot d}&\bmod n\ &=m^{k\cdot f+1}&\bmod n\ &=m^{k\cdot f}\cdot m^1&\bmod n\ &=m^{f\cdot k}\cdot m&\bmod n\ &=\left(m^f\right)^k\cdot m&\bmod n\ &=1^k\cdot m&\bmod n\ &=1\cdot m&\bmod n\ &=m&\bmod n\ \end{align} $$ 我們已經在條件下證明了這一點 $ \gcd(m,n)=1 $ ，這是原始 RSA 論文所做的，以及對 RSA 的許多介紹。但在不涉及的條件下，這恰好是真的 $ m $ ： 那 $ n $ 是無方的，看這個。
這種“無方 $ n $ “條件比 $ \gcd(m,n)=1 $ 在任意消息加密的情況下 $ m $ ，尤其是當我們使用人為的小 $ n $ , 此後我們不能一概而論地排除 $ \gcd(m,n)\ne1 $ 不太可能。在問題中 $ n=33 $ ， 因此 $ \gcd(m,n)\ne1 $ 發生在 $ m $ 之一 $ 0 $ , $ 3 $ , $ 6 $ , $ 9 $ , $ 11 $ , $ 12 $ , $ 15 $ , $ 18 $ , $ 21 $ , $ 22 $ , $ 24 $ , $ 27 $ , $ 30 $ ，因此包括 $ m=15 $ 經過考慮的！
¹ 對於整數 $ s $ 和整數 $ t>0 $ , 什麼運算符的等效定義 $ \bmod $ 是當它左邊沒有左括號時
$ s\bmod t $ 是唯一定義的整數 $ r $ 和 $ 0\le r<t $ 和 $ s-r $ 的倍數 $ t $
$ s\bmod t $ 是唯一定義的整數 $ r $ 和 $ 0\le r<t $ 使得存在整數 $ k $ 和 $ s=k\cdot t+r $
取決於標誌 $ s $ , $ s\bmod t $ 是
如果 $ s\ge0 $ ，歐幾里得除法的餘數 $ s $ 經過 $ t $
如果 $ s<0 $ ， 任何一個
- $ t-((-s)\bmod t) $ 如果那不是 $ t $
- $ 0 $ ， 否則
不要與符號混淆² $ r\equiv s\pmod t $ 左邊有左括號 $ \bmod $ ，其等效定義包括：
- $ s-r $ 是的倍數 $ t $
- 存在整數 $ k $ 和 $ s=k\cdot t+r $
² $ r\equiv s\pmod t $ 最好與可能的幾個中的任何一個一起閱讀 $ \equiv $ 在…的左邊 $ \pmod t $ 讀作congruent或等價而不是equal，並且在左括號所在的地方有一個停頓。那個停頓是為了標記 $ \pmod t $ 限定所說的話。使用很常見 $ = $ 代替 $ \equiv $ , 省略 $ \pmod t $ , 或省略前面的左括號 $ \bmod $ . 當兩者之間的差異時，這也是造成混淆的常見原因 $ \bmod t $ 和 $ \pmod t $ 很重要，其中包括在 RSA 中計算密文。