證明單字母密碼是有效的對稱密碼
我應該在數學上證明：
$ D_k(E_k(p))=p $
我知道
$ E_k(p)=c=(p+k)\bmod26 $
和
$ D_k(c)=p=(c-k)\bmod26 $
將這兩個公式替換為我的初始斷言
$ ((p+k)\bmod26-k)\bmod26=p $
並應用 $ \bmod $ 我有兩次財產
$ ((p \bmod26+k \bmod26)\bmod26)-k)\bmod26=p $
$ ((p\bmod26+k\bmod26)\bmod26)\bmod26-k\bmod26)\bmod26=p $
但從這裡？我怎樣才能擺脫所有這些 $ \bmod $ 具有 $ p $ ?
你需要的引理是$$ ((a \bmod m) + b) \bmod m = (a + b) \bmod m \tag{1} $$對於所有整數 $ a $ , $ b $ 並且對於所有正整數 $ m $ . 換句話說，這個引理說，如果你要將一堆數字加（或減）在一起，然後減少和模 $ m $ ，無論你是否減少任何（或全部）加數模 $ m $ 第一的。
證明上述引理 (1) 的最簡單（也是最有用的泛化）方法是通過模同餘的概念。基本上，我們定義 $ a $ 和 $ b $ 模數一致 $ m $ ，寫為 $ a \equiv b \pmod m $ ， 如果 $ a = b + km $ 對於某個整數 $ k $ . 從這個定義中，立即得出$$ (a \bmod m) \equiv a \pmod m $$而且，事實上，$$ (a \bmod m) = (b \bmod m) \iff a \equiv b \pmod m. $$
我們還可以證明模同餘關係 $ \equiv $ 遵循許多與正規等式相同的代數定律。特別是，我們可以證明它是傳遞的，即$$ a \equiv b \text{ and } b \equiv c \implies a \equiv c \pmod m, $$並且在這個意義上它與加法兼容$$ a \equiv b \iff a + c \equiv b + c \pmod m. $$
應用模同餘的這些性質，我們可以看到 $ (a \bmod m) \equiv a \pmod m $ 暗示 $ (a \bmod m) + b \equiv a + b \pmod m $ ，這意味著引理（1）。
額外練習：還表明模同餘與乘法兼容，因為 $$ a \equiv b \implies ac \equiv bc \pmod m. $$
現在我們已經證明了引理 (1)，剩下的就很簡單了：$$ \begin{aligned} D_k(E_k(p)) &= ((p + k) \bmod 26) - k) \bmod 26 \ &= (p + k - k) \bmod 26 \ &= p \bmod 26. \end{aligned} $$ 如果 $ 0 \le p < 26 $ ， 然後 $ p \bmod 26 = p $ ，我們完成了。（我們確實需要做這個額外的假設，以使加密是可逆的，因為如果 $ p $ 可以取其他值！）
當然，我們也可以完全跳過引理 (1)，直接求助於模同餘，特別是$$ E_k(p) = (p + k) \bmod 26 \equiv p + k \pmod{26},, $$和$$ D_k(c) = (c - k) \bmod 26 \equiv c - k \pmod{26}, $$由此得出$$ D_k(E_k(p)) \equiv p + k - k = p \pmod{26}. $$
我嘗試用更多細節來解釋它。假設我們有以下模方程。 $$ a \equiv b \mod(c) $$ 那麼對於一個整數 $ k $ 我們有， $$ a=b+k \cdot c $$ 例如，在 $ \mod(26) $ 提醒 $ 28 $ 等於 $ 2 $ 這也是對所有人的同樣提醒 $ 2+k \cdot 26 $ 包含 $ {2,28,44,80,…} $ . 此時我們需要弄清楚加法和乘法是什麼情況。所以我聲稱， $$ a_1 \mod(c)+ a_2 \mod(c)\equiv (a_1+a_2) \mod(c) $$ $$ a_1 \mod(c)\cdot a_2 \mod(c)\equiv (a_1 \cdot a_2) \mod(c) $$ **證明：**讓我們在左邊有， $$ a_1 \equiv b_1 \mod(c) , : a_2 \equiv b_2 \mod(c) $$ 我們可以寫， $$ a_1+a_2=b_1+b_2+(k_1+k_2)\cdot c $$ 認為 $ k_3=k_1+k_2 $ 作為一個新的整數， $$ a_1+a_2=b_1+b_2+k_3\cdot c \to a_1+a_2\equiv b_1+b_2 \mod(c) $$ 何處， $$ a_1 \mod(c)+ a_2 \mod(c)\equiv (a_1+a_2) \mod(c) $$ 更簡單地說，整數標量是加法的，您可以執行一次模運算。對於乘法，我們有相同的證明方法。您可以將 c 的新標量取為多個 1 的乘積。
讓我們按照簡單的例子。 $ 28\equiv 2 \mod(26) $ 並且 $ 32 \equiv 6 \mod(26) $ . 然後我們有 $ 28+32=60 \equiv 8 \mod(26) $ 當您首先計算模數然後將它們相加時，它具有相同的結果。
我要求 $ 28 \cdot 32 \equiv (2\cdot 6=12) \mod(26) $ 而您可以通過提前將它們相乘來檢查它，然後找到餘數。因為 $ 28\cdot 32= 896=34\cdot 26+12 $ .
總而言之，你不需要關心多個mod，只需先進行操作，然後再取結果的mod。
此外，有關更多詳細資訊，請查看此連結， https://brilliant.org/wiki/modular-arithmetic/