非常基本的模組化範例
這是一個非常基本的問題，但我無法正確回答。我正在研究一個基本的非對稱加密範例。
所以 $ (m^e)^d \equiv m \pmod n $ （至少在 m < n 的前提下，我想）
如果我選擇：
- m = 14（我的消息）
- n = 19
- e = 3
- d = 13 – 因為 $ 3 \cdot 13 ≡ 1 \pmod{19} $
然後我加密 $ 14^3 ≡ 8 \pmod {19} $
但我解密 $ 8 ^ {13} ≡ 8 \pmod {19} $
我究竟做錯了什麼？
編輯我這背後的邏輯是：
$ m^e ≡ m’ \pmod n $
如果 $ e \cdot d≡1 \pmod n $ 然後
$ m’^d ≡ m \pmod n $
因為 $ (m^e)^d = m^{e \cdot d} ≡ m^1 \pmod n $
嘗試遵循 Burt Kaliski 的RSA Public-Key Cryptosystem 的數學作為參考，該問題存在以下問題：
- 問題選擇 $ n=19 $ 作為素數，而不是作為兩個不同素數的因數 $ p $ 和 $ q $ ( $ p=5 $ , $ q=11 $ , $ n=55 $ 在參考中）；然而，這並不是災難性的，我們將通過採用 $ n=p $ 並忽略 $ q $ .
- 問題使用 $ d $ 這樣 $ e,d\equiv1\pmod n $ ，當參考文獻中沒有任何暗示時；參考用途 $ e,d\equiv1\pmod L $ 和 $ L=\operatorname{lcm(p-1,q-1)} $ ，並且隨著我們的適應變成 $ L=n-1 $ ，因此之間的關係 $ e $ 和 $ d $ 應該 $$ e,d\equiv1\pmod{(n-1)} $$
- 該問題忽略了規定的要求 $ e $ 相對質數 $ p-1 $ 和 $ q-1 $ （意義： $ e $ 與任何一個都不共享主要因素 $ p-1 $ 或者 $ q-1 $ ); 隨著我們的適應，這變成了 $ e $ 相對質數 $ n-1 $ . 它遵循 $ e=3 $ 是一個無效的選擇 $ n=19 $ ， 自從 $ 3 $ 將兩者分開 $ e=3 $ 和 $ n-1=18 $ .
如果我們保持 $ n=19 $ ， 我們可以用 $ e=5 $ ， 尋找 $ d $ 這樣 $ e,d\equiv1\pmod{18} $ ，例如 $ d=11 $ . 然後 $ c=m^e\bmod p=14^5\bmod19=10 $ ， 和 $ m’=c^d\bmod n=10^{11}\bmod19=14=m $ ，正如預期的那樣。
注意：我使用 $ c $ 對於參考文獻中的密文，以及 $ m’ $ 為解密結果。
這是費馬小定理的一個應用，它指出如果 $ p $ 是素數，那麼對於所有 $ m $ 不能被 $ p $ , 它認為 $ m^{p-1}\equiv1\bmod p $ .
請注意，既然我們選擇了 $ d $ 和 $ e,d\equiv1\pmod{(n-1)} $ , 它認為 $ e,d=k(n-1)+1 $ 對於某個整數 $ k $ .
現在，我們計算的方式 $ m’ $ , 它認為
$$ \begin{align}m’&\equiv c^d&\pmod n&&\text{ using }m’=c^d\bmod n\ &\equiv{(m^e)}^d&\pmod n&&\text{ using }c=m^e\bmod n\ &\equiv m^{e,d}&\pmod n\ &\equiv m^{k(n-1)+1}&\pmod n&&\text{ using }e,d=k(n-1)+1\ &\equiv {(m^{n-1})}^k,m&\pmod n\ &\equiv 1^k,m&\pmod n&&\text{ using FLT}\ &\equiv m&\pmod n\ \end{align} $$ 注意：使用 FLT 時，我們依賴 $ n $ 素數，和 $ m $ 不能被 $ n $ , 成立。 自從 $ m’=c^d\bmod n $ 它認為 $ 0\le m’<n $ . 我們有 $ 0<m<n $ 和 $ m’\equiv m\pmod n $ ， 因此 $ m’=m $ 量子點
在問題的推理中做出的一個不正確的假設是它會認為 $ m^i\bmod n=m^{(i\bmod n)}\bmod n $ ; 這通常是錯誤的，並且問題中的計算給出了證明。
真正成立的是 $ m^i\bmod n=m^{(i\bmod\lambda(n))}\bmod n $ 在哪裡 $ \lambda $ 是Carmichael 函式，並且 $ m $ 與 $ n $ 或者 $ n $ 是無平方的。後者在 RSA 中成立。在參考 $ n=p,q $ 和 $ p $ 和 $ q $ 不同的素數，和 $ \lambda(n)=L=\operatorname{lcm}(p-1,q-1) $ .
此答案中使用的標準表示法（但不是參考，它在第一個表示法中省略了括號）：for $ w>0 $
- $ u\equiv v\pmod w $ 意思是 $ w $ 劃分 $ u-v $
- $ u=v\bmod w $ 意思是 $ w $ 劃分 $ u-v $ 和 $ 0\le u<w $ .