可以在不使用 XOR 的情況下建構 OTP 嗎？
一次性鍵盤(OTP)的典型版本使用 XOR 來組合鍵盤和消息。( $ c=m\oplus k $ )
現在讓我們假設其他一些具有致盲實際應用的場景。以下“OTP”結構是否提供完美的保密性？
- 鑰匙 $ r\in (0;n) $ 是隨機均勻選擇的，使得 $ r^{-1}\bmod n $ 在雙方之間存在和共享。此外，雙方共享一些共同的模數 $ n $ 這可能是 RSA 模數或素數。留言 $ m\in (0;n) $ , 是構造 $ c=m\cdot r \bmod n $ 絕對安全？
- $ r\in (0;n) $ 是隨機統一選擇的，由雙方共享。此外，雙方共享一些共同的模數 $ n $ 這可能是 RSA 模數或素數。留言 $ m\in (0;n) $ , 是構造 $ c=m + r \bmod n $ 絕對安全？（我強烈懷疑這裡的答案是“是”，因為這是通過無線電傳輸秘密消息的“常見”引用方法，其中 $ n=10^4 $ )
兩種結構都不是完全安全的！
為了更數學地表達事物，我想說你可以實現一個帶有消息的一次性填充 $ m $ 和一把鑰匙 $ r $ ， 什麼時候
- $ m $ 和 $ r $ 是元素 $ \mathbb{Z}/n\mathbb{Z} $ ，整數模 n 的加法群，或者當
- $ m $ 和 $ r $ 是一個組的元素 $ G $ 同構於 $ \mathbb{Z}/n\mathbb{Z} $ .
這樣的組將是實施 OTP 的自然選擇。
然而，還有其他可能性。例如，人們可以很容易地想像一個完全安全的 OTP 結構，其中密鑰 $ r $ 是組的一個元素 $ G $ 和消息 $ m $ 是子群的一個元素 $ G $ . （然後密鑰大於消息）。
現在，讓我們回到你的構造。在這兩種結構中，您都假設 $ r,m\in {1,…,n-1} $ 使用非正常符號 $ r,m\in(0;n) $ .
- 構造 1：您計算 $ c=r\cdot m $ 反對 $ n $ . 如果 $ n $ 是一個素數，那麼你有一個素數域的乘法群，它會起作用。正如您已經發現的那樣，當 $ n $ 是複合的。
- 構造 2：您計算 $ c=r+ m $ 反對 $ n $ . 如果你有這將是非常安全的 $ \mathbb{Z}/n\mathbb{Z} $ . 但是，由於您排除了 0 元素，您知道您總是有 $ m\ne c $ ，因此它不是完全安全的。:)
在雨披和yyyyyyy的這些非常有用的提示之後，答案現在很明顯，我將簡要說明為什麼每個結構都非常安全。
關於構造1：
它不可能是完全安全的，因為已經證明完美的保密性（=完美的安全性）需要密鑰空間 $ \mathcal K $ 與消息空間一樣大 $ \mathcal M $ 這顯然不是任意模量的情況，因為約束 $ r $ 必須是可逆的 $ \bmod n $ 這需要 $ gcd(n,r)=1 $ . 對於任何復合模量，顯然存在至少兩個 $ r $ 這樣 $ gcd(n,r)\neq 1 $ （即它的因素）。這意味著密鑰空間小於消息空間，這意味著它不能完全安全。如果 $ n $ 是素數，而不是模與所有的互素數 $ r $ 和 $ 0<r<n $ 這意味著兩個空間都一樣大。這也意味著對於任何消息 $ m’ $ 有一個 $ r’ $ 這樣 $ m’=r’^{-1}\times c \bmod n $ 這意味著每條消息都同樣可能意味著完全保密。
關於構造2：
經典的基於 XOR 的 OTP 是這種結構 $ n=2 $ . 這種概括（與 $ 0 $ 被允許 $ m,r $ ) 是安全的，因為消息和密鑰空間都一樣大，並且可以找到 $ r’ $ 對於任何消息 $ m’ $ 這樣 $ m’=c-r’\bmod n $ 是可構造的。因為攻擊者無法決定哪個 $ r’ $ 當他找到正確的密鑰時，他不知道是“正確的”，因此這個方案是完全安全的。然而，問題中給出的結構並不完全安全（正如克里斯的回答
所指出的那樣），因為 $ 0 $ 不是有效值 $ r $ 因此不可能 $ m=c $ 這會產生一些關於 $ m $ 從而打破了完美的秘密。