Coppersmith

前言

不知不觉学密码有半年了，从最开始的 RSA 到格再到奇奇怪怪的东西，不禁感慨数学确实有趣。 之前的 MRCTF 的题有道三元 Coppersmith ，可惜当时水平太过低微，既做不出来也看不懂 exp ，如今再回来补这个坑，就差不多可以往生 pwn 了。

后记

这篇文章搁了很久，pwn 由于一些原因也没怎么做，还是在密码里打点小工。刚好天枢的 CTF 有一道 Coppersmith，吃了没基础的亏，论文都看不懂。

Coppersmith 的大致思想

可以参考 Tover 爷的这篇文章。

模根与整根

RSA 的许多攻击都可以化成解模根的问题，而所谓解模根就是方程在模数 下的解。这时候直接解是不现实的，就需要用到 Coppersmith 方法。 解模根的关键就是 Howgrave-Graham 定理： 令 为一个至多含 个单项式的整数多项式，若满足

则 在整数域上成立。

不难看出，这个定理实际是将模方程转化成我们所常见的整数方程，这样，我们就可以用一些常见的方法（如牛顿迭代法）来求解了。

如 GF(323) 上的方程

由韦达定理就能看出，这个方程在整数域下是解不出来实根的，但是我们稍微变换一下，变为如下形式， 记

注意， 仍是成立的。 但是这个时候，肉眼分解 就能得到根 ，而这个根代入原始方程也是成立的。

Coppersmith 就是利用这个思想，往方程加入一些模 为零的项，使得方程满足 Howgrave-Graham 定理的条件，然后再用整数域的方法求解。

单变量 Coppersmith 的实现

一个比较基础是方法是构造一个简单的矩阵跑 LLL。直接上例子：

我们可以构造矩阵

可以理解成 LLL 的过程中用前面三行对最后一行进行了一些加减操作，使得最后一行的系数变得很小，而实际上系数变小就是为了满足 Howgrave-Graham 定理的界。

LLL 后我们得到向量 ，对应的多项式为 ，这个多项式在整数域上的根 即为原方程的根。

然而以上的方法需要满足 ，更精确来说是 （证明不难，即 LLL 得到的最短向量小于 HG 定理的界），可以看出 越小这个条件越容易满足，但是我们的研究通常是把 的界往上扩的，这时我们就可以加一些 x-shift 的多项式(关于这个词，总感觉翻译成 x 的移位多项式比较怪，本文就保留原英文称谓了)。

如果你细心去算了，就会发现上面的例子其实是不符合条件的，因为 LLL 给出的是最坏的界，我们算条件也是用这个最坏的界，上面恰好得到了一个更好（即更短）的向量。

感觉这篇文又要鸽了，没看懂他例子的格是怎么造出来的。

二元 Coppersmith

结式

三元 Coppersmith

参数解释

论文里 和 不难理解是三个变量对应的界，但除此之外还有 和 的选取，这也是我当前很迷糊的点，下面简单探讨一下。

首先是最简单的 ，论文明确给出 ，而 的意思就是多项式的最大系数，所以 就是多项式对各 进行 代入后的最大系数。如 ， ，则 ，显然最大系数在 那，即 。 然后 和 目前我也不知道咋算（）

杂谈

直到现在才反应过来 paper 的引用名中后面的数字是年份（）

参考

• 知乎 -「:=」和「=:」的区别是什么？
• Santanu Sarkar and Subhamoy Maitra. Some Applications of Lattice Based Root Finding Techniques
• [[ELL06] E. Jochemsz and A. May. A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants, Asiacrypt 2006, LNCS 4284, pp. 267–282, 2006.](https://www.cs.umd.edu/~gasarch/TOPICS/attackingRSA.pdf)
• Coppersmith’s Method and Related Applications
• lord. Way to CopperSmith