置換共軛問題很難嗎？
讓 $ x $ , $ y $ , $ z $ 是排列。那麼公鑰是 $ z=xyx^{−1} $ 和 $ y $ . 置換共軛搜尋問題容易嗎？如果是，如何找到 $ x $ 從 $ z $ 和 $ y $ ? 設 a 是 Alice 的大數密鑰，X,Y,A=XaYX−a 是公鑰。
加密 Bob 選擇隨機數 r,s 和 B=XrYX−r,C=XrAsX−r,並且 c=H(C)+m, (B,c) 是發送給 Alice 的密文。
解密 Alice 計算 C=XaBX-a。由於置換群的離散對數問題較弱，所以Alice可以從B計算C。最終Alice得到明文為m=H(C)+c。
我假設 X 的排列維數是 1988 並且排列表示為數組形式。X 的順序有 256 位整數。
這個密碼系統不安全嗎？
假設排列中的元素數量不是太大，看起來可以使用分支定界過程快速解決。
（符號：我將使用大寫字母來指定排列，小寫字母來指定排列的各個元素）；此外，我將遵循約定 $ XY $ 意思是“應用排列 $ X $ 到元素，然後應用排列 $ Y $ )
該算法是直截了當的；我們知道 $ XY = ZX $ ， 所以：
- 我們選擇排列的任意元素 $ a $ 並假設 $ X(a) = b $ （在哪裡 $ b $ 是以前的輸出 $ X $ ）。然後我們可以推導出值 $ XY(a) = d $ （在哪裡 $ d = Y(b) $ ）。此外，我們有 $ Z(a) = c $ （對於某些元素 $ c $ )，所以我們可以推導出 $ X(c) = d $ .
假如說 $ c, d $ 是以前未知的輸入/輸出 $ X $ ，我們重申相同的邏輯，這將給我們另一對 $ X(e) = f $ .
我們繼續這樣做，直到它給我們一個我們以前見過的對，或者它給出一個不一致的對（也就是說，它分配了相同的 $ X(g) $ 值到兩個不同的輸出，或者它給了我們一個集合 $ g \ne h, i $ 和 $ X(g) = X(h) = i $
如果它給了我們一個不一致的對，我們回到之前的假設 $ X(a) = b $ , 並修改 $ b $ ，然後從那裡重新開始我們的計算。
如果它給了我們一對我們以前見過的，並且仍然有未分配的輸入/輸出到 $ X $ ，我們從頭開始，任意選擇一個以前未分配的輸入/輸出對。
這不會給出一個獨特的價值 $ X $ ; 那是因為有多種解決方案，這將任意選擇一個。
更新：我剛剛寫了一個快速（而且相當次優）的 C 程序來做到這一點；在一秒鐘內給定超過 10,000 個元素的兩個排列，它可以找到一個共軛（存在一個）……