技术摘要：一种基于广义卢卡斯矩阵的新型公钥密码体制

问题陈述

本文旨在解决增强公钥密码体制的需求，这些体制需要更大的密钥空间、更低的传输复杂度，以及基于数论和线性代数的鲁棒安全性。虽然矩阵理论和递归序列（如斐波那契序列和卢卡斯序列）已被应用于密码学（例如 Hill 密码、ElGamal），但现有方法通常涉及交换大型密钥矩阵或依赖于标准的序列属性。作者提出了一种系统，通过使用广义递归矩阵，在最小化密钥协商期间数据交换的同时，最大化加密密钥空间的复杂度。

方法论

1. 数学基础

所提方案的核心依赖于从广义斐波那契矩阵 (GFM) 构建的广义卢卡斯矩阵 (GLM)。

• 广义斐波那契矩阵 (GFM)： 作者利用了 $k$ 阶广义斐波那契序列 $\{f_{k,n}\}$ 及其对应的矩阵表示 $Q^k_n$。这些矩阵满足标准性质，如 $Q^n_k Q^l_k = Q^{n+l}_k$，以及基于阶数 $k$ 的特定行列式规则。
• 广义卢卡斯序列： 定义了一个新的序列 $\{l_{k,n}\}$，其初始值源自前 $k$ 个 GFM 矩阵的迹（$\text{trace}(Q^r_k)$）。其递推关系与广义斐波那契序列一致：$l_{k,k+n} = \sum_{i=0}^{k-1} l_{k,k+n-1-i}$。
• 广义卢卡斯矩阵 (GLM)： 使用广义卢卡斯序列项的线性组合构建一个递归矩阵 $L^{(n)}_k$。作者建立了 GLM 与 GFM 之间的基本关系：
  $$L^{(n)}_k = Q^n_k L^{(0)}_k = L^{(0)}_k Q^n_k$$
  其中 $L^{(0)}_k$ 是初始卢卡斯矩阵。

2. 密码方案

该方案将这些矩阵集成到改进的仿射-Hill 密码 (Affine-Hill Cipher) 与 ElGamal 公钥基础设施中。

• 密钥交换（基于 ElGamal）：

  • 接收方 (Bob)： 选择一个素数 $p$、一个原根 $\alpha$ 以及一个秘密整数 $D$。他发布 $E_1 = \alpha$ 和 $E_2 = \alpha^D \pmod p$。
  • 发送方 (Alice)： 选择一个随机整数 $e$。她计算签名 $s = E_1^e \pmod p$ 和共享密钥 $\lambda = E_2^e \pmod p$。
  • 传输： Alice 将密文和签名 $s$ 发送给 Bob。她并不发送完整的密钥矩阵或秘密 $\lambda$。

• 加密（带 GLM 的仿射-Hill 密码）：

  • 利用共享密钥 $\lambda$（矩阵阶数）和签名 $s$（指数），Alice 构建加密密钥矩阵 $K = L^{(s)}_\lambda \pmod p$。
  • 使用来自卢卡斯序列的项生成偏移向量 $B$：$B = [l_{\lambda,\lambda}, l_{\lambda,\lambda+1}, \dots, l_{\lambda,2\lambda-1}]$。
  • 明文块 $P$ 被加密为 $C = (P \cdot K + B) \pmod p$。

• 解密：

  • Bob 使用他的私钥恢复 $\lambda$：$\lambda = s^D \pmod p$。
  • 他构造逆矩阵 $K^* = L^{(-s)}_\lambda H^{-1} \pmod p$，其中 $H = (L^{(0)}_\lambda)^2$。论文证明了 $L^{(s)}_\lambda L^{(-s)}_\lambda = H$，确保了逆矩阵的存在性。
  • 解密过程为 $P = (C - B) \cdot K^* \pmod p$。

主要贡献

1. 定义广义卢卡斯矩阵： 论文正式定义了 $k$ 阶 GLM，并确立了它们的代数性质，包括行列式公式、乘积规则（$L^{(m)}_k L^{(n)}_k = L^{(m+n)}_k L^{(0)}_k$）以及其逆矩阵的显式构造。
2. 基于参数的密钥生成： 不同于传统的基于矩阵的密码（其中整个矩阵必须被共享或由大型种子生成），该方案允许双方仅通过两个参数重建密钥矩阵：$\lambda$（源自离散对数问题）和 $s$（签名）。
3. 与仿射-Hill 及 ElGamal 的集成： 作者提出了一个混合方案，利用仿射-Hill 密码的效率（带有偏移向量的分块加密），并通过 ElGamal 设置中固有的离散对数问题的难度来保障安全性。
4. 逆矩阵构造： 论文提供了一种计算 GLM 逆矩阵的具体方法，而不依赖于标准的高斯消元法，而是利用关系式 $Inv(L^{(n)}_k) = L^{(-n)}_k H^{-1}$。

结果与分析

• 实现示例： 作者通过 $p=37$，$k=3$，以及特定的整数值 $D$ 和 $e$ 展示了该方案。他们成功地将明文 "NOBLE2022" 加密为密文块，并恢复了原始消息，验证了矩阵运算和模运算的数学正确性。
• 复杂度降低： 该方案声称降低了密钥传输的时间和空间复杂度。通过不传输 $n \times n$ 矩阵，仅需交换一对数字 $(\lambda, s)$。
• 安全性分析：
  • 离散对数： 从 $s$ 恢复 $\lambda$ 需要解决离散对数问题，这对于大素数而言在计算上是不可行的。
  • 密钥空间： 针对暴力破解攻击的安全性取决于一般线性群 $|GL(\lambda)|$ 的大小。作者计算得出，对于 $p=37$ 且 $\lambda=50$，密钥空间约为 $3.105 \times 10^{3920}$，规模呈指数级增长。
  • 签名独立性： 分析表明，即使已知签名 $s$，也不会破坏安全性，因为安全性主要取决于确定 $\lambda$ 的难度以及由 $\lambda$ 定义的庞大矩阵空间。

意义与主张

论文得出结论，该方法为授权方提供了一个数学简单且强大的密码框架，同时为入侵者设置了显著的障碍。其意义在于：

• 扩大的密钥空间： 与标准实现相比，使用广义卢卡斯矩阵显著扩大了可用的密钥空间。
• 高效性： 通过将密钥传输简化为一对数字，该方案提高了带宽和存储方面的效率。
• 鲁棒性： 将离散对数问题（用于密钥协商）与矩阵结构的复杂性（用于加密）相结合，构建了多层防御。

作者断言，该方法对于“授权方而言在数学上是简单的，而对于入侵者而言则是繁琐的”，这依赖于已建立的离散对数问题的难度以及广义卢卡斯矩阵巨大的组合空间。