Cayley-Purser 演算法

Cayley-Purser 演算法是一種 公鑰密碼學 演算法，它依賴於 矩陣乘法 不滿足交換律這一事實。它由 Sarah Flannery（當時 16 歲）受到 Michael Purser 的想法啟發而設計，用於 1998 年的青年科學家競賽。Flannery 以 Purser 和 Arthur Cayley（矩陣 的發明者）的名字命名了該演算法。

Cayley-Purser 演算法僅使用模矩陣乘法，而不是模冪運算，並且對於大模數而言，速度比其他公鑰演算法快得多（例如，對於 200 位模數，速度比 RSA 加密 快約 20 倍）。雖然該演算法起初看起來與 RSA 一樣安全，但隨後表明，僅通過了解公共資料即可輕鬆解密使用該演算法加密的訊息。

Cayley-Purser 演算法的設定過程如下。

1. 選擇兩個大素數 和 ，並令 。素數 和 都應為 的形式，其中 也是素數。

2. 從 （ 可逆矩陣的一般線性群，其條目是模 的整數）中隨機選擇矩陣 和 ，使得 。

3. 選擇 並令 。

4. 令 。

5. 釋出 、、 和 。保密矩陣 ，解密時需要用到它。

要加密，請使用以下步驟。

1. 將訊息表示為 矩陣 ，其條目在 中。

2. 隨機選擇 。

3. 令 。

4. 令 。

5. 將 加密為 。

6. 傳輸對 。

解密按如下步驟執行。

1. 令 。

2. 那麼 。由於 和 可交換，我們有

由於 是兩個大的、未知的素數的乘積，因此透過 計算確定原始矩陣 是非常困難的。此外，求解

對於 也是棘手的，因為由於選擇 和 的方式， 在 中心的階數將至少為 ，機率為 。

然而，沒有必要知道 即可解密訊息；知道 的倍數就足夠了，因為如果 ，則有

如果矩陣 是降秩的（也就是說，如果 約簡模 或模 ，結果是單位矩陣的標量倍數），那麼 可以分解為 。有了 的因式分解，確定 在 中的解並不困難。

如果 是非降秩的，那麼可以按如下方式確定 為 的倍數。由於 ，那麼根據 Cayley-Hamilton 定理，存在整數 和 ，使得 。因此，存在矩陣 ，對於某個尚未知曉的值 。

另請注意

所以

因此，

這允許確定 ，從而確定 。矩陣 可以在解密步驟中代替 使用。