服务器辅助RSA协议的安全性分析

# 服务器辅助RSA协议的安全性分析及攻击方法研究 在服务器辅助RSA协议的安全性研究中，许多攻击方法被提出并分析。其中，Merkle的多轮攻击和针对低指数RSA - S1的一轮新攻击具有重要意义。下面将详细介绍这些攻击方法及其理论结果和实验情况。 ## 1. 最短向量问题与实验必要性 在研究格相关问题时，当格维度不是太大时，一些算法常常能返回最短格向量，其表现优于理论预期。因此，若有解决最短向量问题（SVP）的算法（SVP - oracle），预测其能高效达成的结果是很有意义的，例如在子集和问题中就有这样的应用。然而，除非格维度极小，否则很难提前预测一个SVP实例在实际中是否可解，所以实验在这种情况下总是必要的。 ## 2. Merkle的多轮攻击分析 ### 2.1 Merkle攻击原理 Merkle的攻击基于如下观察：对于特定向量 \(f = (f_1, \ldots, f_m) \in B_{k,\ell,m}\) 和 \(d = (d_1, \ldots, d_m) \in [\varphi(N)]^m\)，有 \(0 < \sum_{i = 1}^{m} f_id_i < k2^{\ell}\varphi(N)\)，且 \(\sum_{i = 1}^{m} f_id_i \equiv d + j\varphi(N)\)，其中 \(j \in \lfloor k2^{\ell} \rfloor\)，即 \(j\) 的取值不会太多。 研究表明，无论向量 \(f \in B_{k,\ell,m}\) 的分布如何，对于上述协议产生的两对向量 \(f_1 = (f_1, \ldots, f_m)\)，\(d_1 = (d_1, \ldots, d_m)\) 和 \(f_2 = (f_{m + 1}, \ldots, f_{2m})\)，\(d_2 = (d_{m + 1}, \ldots, d_{2m})\)，至少以 \(1/k2^{\ell}\) 的概率满足等式 \(\sum_{i = 1}^{m} f_id_i = \sum_{i = m + 1}^{2m} f_id_i\)。实际上，任何选择这些向量的规则在协议执行至多 \(k2^{\ell}\) 次后都会产生碰撞，且根据“生日悖论”，协议执行约 \(k^{1/2}2^{\ell/2}\) 次后就可能发生碰撞。 这个线性方程比较特殊，因为每个 \(f_i\) 相对 \(d_i\) 较小，可从格的角度进行解释。有研究认为 \((f_1, f_2)\) 是与齐次方程 \(\sum_{i = 1}^{m} f_id_i = \sum_{i = m + 1}^{2m} f_id_i\) 以及同余式 \(\sum_{i = 1}^{m} f_id_i \equiv \sum_{i = m + 1}^{2m} f_id_i \equiv d \pmod{\varphi(N)}\) 相关的特定格中的最短向量。 不过，Merkle的分析并不充分，因为其假设的参数分布与协议实际的分布不同，且在没有SVP - oracle的情况下没有给出相关结果。所以，即使在有SVP - oracle的假设下，Merkle的攻击也未得到严格证明，但其实验结果显示该攻击在许多参数选择下在实际中是成功的。 ### 2.2 Merkle攻击的变体 直接考虑与等式 \(\sum_{i = 1}^{m} z_id_i = \sum_{i = m + 1}^{2m} z_id_i\) 对应的 \((2m - 1)\) 维格 \(L(d_1, d_2)\)，它是正交格的最简单情况，可在多项式时间内计算其基。该格的体积为 \(vol(L(d_1, d_2)) = \sqrt{d_1^2 + \ldots + d_{2m}^2} / \gcd(d_1, \ldots, d_{2m})\)，其最短非零向量的范数预计约为 \((2m - 1)^{1/2}\varphi(N)^{1/(2m - 1)}\)。 向量 \(f = (f_1, \ldots, f_{2m})\) 属于这个格，且其范数至多为 \(k^{1/2}2^{\ell}\)。若 \(k^{1/2}2^{\ell}\) 远小于 \((2m - 1)^{1/2}\varphi(N)^{1/(2m - 1)}\)，则 \(f\) 很可能是 \(L(d_1, d_2)\) 的最短向量，若小到一定程度，相关算法就能找到它。找到 \(f\) 后，可推导出 \(\sum_{i = 1}^{m} f_id_i\)，它与RSA私钥指数模 \(\varphi(N)\) 同余，从而可以对任何消息进行签名，还能在随机多项式时间内恢复 \(N\) 的因式分解。 与原始Merkle攻击相比，原始攻击使用了 \(L(d_1, d_2)\) 的一个轻微变体，利用了 \(f_i \in \lfloor 2^{\ell} \rfloor\) 而非 \(f_i \in \lfloor 2^{\ell} \rfloor_{\pm}\) 的特点，但由于分布不同，这种技巧在此处的作用不大，变体与原始攻击的效率差异很小。 ### 2.3 理论结果 #### 定理1 存在一个确定性算法 \(A\)，给定RSA模数 \(N\)、公钥指数 \(e\) 以及 \(k2^{\ell}\) 个向量 \(d \in [\varphi(N)]^m\)（对应由 \(k2^{\ell}\) 次独立执行RSA - S1生成的向量 \(f \in B_{k,\ell,m}\) 的集合 \(F\)），该算法能在 \(k\)、\(2^{\ell}\)、\(m\)、\(\log N\)