具有可逆順序的雙密鑰密碼系統
在閱讀 Shamir、Rivest 和 Adleman 關於“心理撲克”的論文時，我遇到了一個提到系統的問題： $ E_a(E_b(x)) = E_b(E_a(x)) $ ，但沒有透露有關它的細節，與 $ E_a(x) $ 是“加密明文 $ x $ 帶鑰匙 $ a $ ”.
任何現有的安全現代密碼系統是否具有此屬性，以及如何呼叫它以供以後參考？
首先，請注意所需的交換性與選擇明文攻擊下的安全性不兼容，選擇明文攻擊（以IND-CPA為名）被認為是現代加密系統的要求。證明，根據tylo的評論擴展，使用對稱加密的 IND-CPA 遊戲（參見Katz 和 Lindell 的現代密碼學簡介的第 3.5 節中的CPA 不可區分性實驗，也在第 4 頁）：
我們假設一個密碼 $ E $ :
- 可交換的問題，即： $ \forall a,\forall b,\forall x, E_a(E_b(x))=E_b(E_a(x)) $ ;
- 內射： $ \forall a,\forall x,\forall y, E_a(x)=E_a(y)\implies x=y $ （可靠解密的必要性）；
- $ E $ 可以是確定性的或機率性的；在後一種情況下 $ E $ 有一些隨機源作為除了鍵（下標）和數據（顯式參數）之外的隱藏輸入，並且上述屬性適用於每個實例中隨機輸入的所有值 $ E $ ;
- 密碼有一個公共定義（除了它的隨機性，如果有的話）允許對手實際實施（一種算法，在參數大小上具有時間和空間複雜度多項式）；
比賽開始時裁判選擇並宣布參數的大小；
裁判秘密選擇一個隨機密鑰 $ k $ ;
對手選擇一個隨機密鑰 $ r $ , 一個隨機明文 $ X $ , 併計算 $ M_0=E_r(X) $ 使用密碼的定義，直到 $ M_0\ne X $ （對於任何安全密碼都具有很高的可能性）；
在訓練階段，對手送出 $ X $ 用於加密並獲得 $ Y=E_k(X) $ ;
在挑戰階段
- 對手送出 $ M_0 $ , 和任何 $ M_1 $ 那既不是 $ M_0 $ 也不 $ X $ （送出 $ M_1=M_0 $ 將是糟糕的策略；送出 $ M_0 $ 或者 $ M_1 $ 在訓練階段送出的內容將違反確定性加密的遊戲規則）；
- 裁判暗中選擇 $ i $ 隨機進入 $ {0,1} $ 通過公平的拋硬幣，然後返回 $ C=E_k(M_b) $ ;
（這裡的遊戲規則允許對手在密鑰下進行其他加密查詢 $ k $ , 一定是針對不同的消息 $ M_0 $ 和 $ M_1 $ 在為確定性加密而玩的遊戲中）；
對手返回 $ i’=0 $ 如果 $ C=E_r(Y) $ ，可以使用密碼的定義計算，或者 $ i’=1 $ 除此以外;
如果對手獲勝 $ i’=i $ （我們想要這樣的機率，這應該比 $ 1/2 $ 由一些 $ \epsilon>0 $ 與參數的大小無關）；
- 如果裁判選擇 $ i=0 $ : $ C=E_k(M_0)=E_k(E_r(X)) $ ，並應用我們得到的密碼的交換性 $ C=E_r(E_k(X))=E_r(Y) $ ， 因此 $ i’=0 $ ;
- 如果裁判選擇 $ i=1 $ ： 自從 $ M_1\ne M_0 $ ，並且因為密碼是單射的， $ C=E_k(M_1) $ 必須不同於任何東西 $ E_k(M_0) $ 本來是，其中（如上所示）必然匹配 $ E_r(Y) $ 由對手計算並用於查找 $ i’ $ ， 因此 $ i’=1 $ （注意：在機率算法的情況下，人們可能認為可能有幾個 $ E_k(M_0) $ , 但交換性使得它們都必須匹配 $ E_r(Y) $ 由對手計算：為了可交換，密碼必然是確定性的輸入 $ M_0 $ 和 $ Y $ 考慮到這些是如何產生的）；
- 因此可以肯定， $ i’=i $ （這是一個完美的區分）。
正如figlesquidge所說，在某種意義上，具有One Time Pad的XOR 具有所需的交換性。對於任何具有帶外同步方法的流密碼也是如此（包括分組密碼，例如OFB或CTR模式下的AES，帶有帶外IV）；帶外我的意思是：不是考慮交換性的密文的一部分。
然而，OTP 或其他帶外數據通常是不切實際的（特別是在幾個密文被洗牌但帶外數據沒有洗牌的案例中，這就是心理撲克中的情況），並且與密碼的定義不匹配（需要可重複使用的密鑰並且沒有帶外數據）。
我們研究了密碼學民間傳說中最簡單的交換密碼，有時用於心理撲克：
Pohlig -Hellman 求冪密碼
對於給定的公共奇素數 $ p $ ， 讓 $ K $ 是一組 $ k\in\mathbb N $ 和 $ 0<k<p $ 與_ _ $ p-1 $ ， 和 $ * $ 乘法模 $ p-1 $ ， 以便 $ (K,*) $ 是一個交換群 $ k=1 $ 中性元素。
Pohlig-Hellman 求冪密碼 $ \mathbb Z_p $ 用鑰匙輸入 $ k $ 是
$$ \begin{align} E:K\times\mathbb Z_p&\mapsto \mathbb Z_p\ (k,x)&\mapsto E(k,x)=x^k\bmod p=E_k(x) \end{align} $$ 用密鑰加密 $ k $ 是 $ E_k: x\mapsto E_k(x) $ 並且是一個排列 $ \mathbb Z_p $ . 在函式組合下從一個群獲得的排列集（注 $ \circ $ )，同構於 $ (K,*) $ :
$$ \forall a\in K,\forall b\in K,\forall x\in \mathbb Z_p,E_b(E_a(x))=(E_b\circ E_a)(x)=E_{ba}(x) $$ 因此，解密是 $ D_k=E_\overline k $ ， 和 $ \overline k=k^{-1}\bmod(p-1) $ 的倒數 $ k $ 在小組中 $ (K,) $ ; 並且所需的交換性屬性成立： $$ \forall a\in K,\forall b\in K,\forall x\in \mathbb Z_p, E_a(E_b(x))=E_b(E_a(x)) $$ 對於適當的 $ p $ （使離散對數問題變得困難），密碼對於與同一隨機密鑰相關的多個隨機明文被推測是安全的
$$ that’s stated before (15) in the original article, linked to the title of this section; and justified by an argument I do not get $$. 但是，它具有許多其他隨機交換密碼顯然不具有的屬性，包括乘法屬性 $ \pmod p $ : $$ \forall k\in K,\forall x\in \mathbb Z_p,\forall y\in \mathbb Z_p, E_k(x\cdot y\bmod p)=E_k(x)\cdot E_k(y)\bmod p $$ 還有許多其他不受歡迎的屬性：
- 三個固定點： $ \forall x\in{0,1,p-1},\forall k\in K,E_k(x)=x $
- 消息空間的對稱性： $ \forall x\in \mathbb Z_p,\forall k\in K,E_k(p-x\bmod p)=\big(p-E_k(x)\big)\bmod p $
- 同構與 $ (K,*) $ 允許一些相關密鑰攻擊，並暗示弱密鑰 ( $ k=1 $ ).
- 鍵空間不是 $ \mathbb N $ ，這很不方便。
變種
我們可以解決這 4 個問題。讓 $ p $ 成為一個大的公共素數 $ (p-1)/2 $ 素數，例如 $ p=\lfloor\pi\cdot2^{2046}\rfloor+3,617,739 $ . 讓 $ P $ 是一組 $ (p-3)/2 $ 整數 $ {2,3\dots,(p-3)/2,(p-1)/2} $ . 鑰匙 $ k $ 256 位和數據 $ x\in P $ ， 定義
$$ \begin{align} k_E&=2^{320}\cdot\small\text{SHA-256}(k)+2^{64}\cdot k+1\ k_D&=\overline{k_E}={k_E}^{-1}\bmod (p-1)\ \mathbf E_k(x)&=\min\big(x^{k_E}\bmod p,p-(x^{k_E}\bmod p)\big)\ \mathbf D_k(x)&=\min\big(x^{k_D}\bmod p,p-(x^{k_D}\bmod p)\big) \end{align} $$ 固定點和對稱性被定義刪除 $ P $ 和使用 $ \min $ . 指數的構造 $ k_E $ 使它與 $ p-1 $ （自從 $ k_E $ 是奇數且太小而不能除的單個奇數除數 $ p-1 $ )，確保任何 256 位 $ k $ 製作精細的密鑰，並提供公平的保護以防止相關密鑰攻擊。的建設 $ k_D $ 確保 $ \forall k,\forall x,\mathbf D_k(\mathbf E_k(x))=x $ . 所需的交換性屬性以及乘法屬性（無論是否需要）仍然成立。我們可以通過插入偽隨機排列人為地擺脫乘法性質 $ M $ 集合的 $ P $ 加密之前，之後反過來： $ x\mapsto (M^{-1}\circ\mathbf E_k\circ M)(x) $ 仍然具有交換性，但不具有乘性；然而對手知道 $ M $ 仍然可以潛在地利用乘法屬性。
使用 RSA 加密填充
如果 $ \small\text{OAEP}(x) $ 指定用於RSA-OAEP的填充，其模數為 $ \lceil\log_2(p)\rceil $ 位，然後 $ x\mapsto E(\small\text{OAEP}(x)) $ 似乎是 IND-CPA 安全且可破譯的（失去了所需的交換性屬性：該填充必須在協議的任何步驟需要交換性的外部）。正如Ricky Demer所指出的，OAEP+優於 OAEP。
兩種填充都隱藏了乘法屬性，包括使密碼機率化。