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 定理，存在整数 和 ，使得 。因此，存在矩阵 ，对于某个尚未知晓的值 。

另请注意

所以

因此，

这允许确定 ，从而确定 。矩阵 可以在解密步骤中代替 使用。