之間的關係ññN和φ(N)φ(ñ)phi(N)在 RSA 算法中
最近我開始學習 RSA 算法的工作原理，其中有一個計算部分真的讓我感到困惑並且無法克服它。
假設我選擇了 2 個素數，
即
$ P = 3 $ 和 $ Q = 11 $
$ N = 3 \times 11 = 33 $
$ \phi(N) = (P-1)\times(Q-1) = 20 $
現在，我必鬚根據一些標準（根據 RSA）選擇 e，讓 $ e = 7 $ 現在，我必須確定 $ d $ 通過使用， $ e^{-1} \equiv1 (\bmod \phi(N)) $ 當我加密和解密時，
a) 密碼 = $ m ^ e \bmod N $
b) 消息 = $ c ^ d \bmod N $
在上述情況下，而不是 $ \bmod N $ ，對於同一個例子，我嘗試了不同的 $ N $ 比實際的 $ N $ ( $ 33 $ )，它不適用於除 $ 33 $ . 為什麼會這樣？我能感覺到自從找到 $ d $ 是基於逆下 $ \bmod \phi(N) $ , 之間存在某種關係 $ N $ 和 $ \phi(N) $ ，但無法理解。
之間有什麼關係嗎 $ N $ 和 $ \phi(N) $ ，如果是這樣，我怎樣才能詳細了解它？
RSA 基於一些數學定理。您需要學習的第一個定理是歐拉定理；如果 $ n $ 和 $ a $ 是互質的正整數，那麼
$$ a^{{\varphi (n)}}\equiv 1\bmod n. $$什麼時候 $ n $ 是一個素數，它是小費馬定理。
這個定理告訴我們，在冪中我們使用模 $ \varphi(n) $ ， IE，$$ a^{x} \equiv a^{x \bmod\varphi(n)} \bmod n $$
當執行教科書 RSA 加密時，計算$$ c = m^e \bmod n $$和解密執行為$$ m = c^d \bmod n $$
現在，明確地；
$$ c^d = (m^{e})^d = m^{ed} $$既然我們選擇 $ d $ 作為的倒數 $ e $ 模組 $ \varphi(n) $ , $ e\cdot d = 1 \bmod \varphi(n), $ 然後
$$ m^{ed \bmod \varphi(n)} = m^1 = m \bmod n $$
我嘗試了與實際 N (33) 不同的 N，但它不適用於 33 以外的任何其他數字。為什麼會這樣？
因為您執行的計算使用未定義的模數。 $ m^e $ 將是不同模數中的不同數字。
**請注意：**您使用 $ \varphi(n) = (p-1)(q-1) $ 什麼時候 $ n=pq $ . 通常Chamchael lambda $ \lambda(n) $ 用來 $ \lambda(n)=\operatorname{lcm}(p-1,q-1) $ 和$$ \varphi(n)=\lambda(n)\cdot\gcd(p-1,q-1). $$這給出了最小的 $ d $ 操作。
**注意 2：**在上面的教科書中使用了 RSA，如果沒有適當的填充，千萬不要使用它。對於加密，應該使用M. Bellare, P. Rogaway 介紹的RSA-OAEP 。最佳非對稱加密——如何使用 RSA和 PKCS#1 v1.5 填充進行加密。前者更可取，因為它具有安全證明，而且 PKCS#1 v1.5 PKCS1v1.5 加密本質上難以安全使用，不應使用。
實際上，我們不使用 RSA 進行加密，我們更喜歡混合加密。RSA 主要用於簽名和簽名 RSA 與機率簽名方案 (PSS) 一起使用。這也是由 M. Bellare、P. Rogaway 介紹的；PSS：可證明安全的數字簽名編碼方法
請記住，RSA 簽名不是 RSA 解密