参与了Round18的出题工作，出了三道Ring，在这里记录一下这三个题目的做法。
出题的本意也是想详细介绍一下RLWE的攻击原理。
New Year Ring1
题目描述：
1 | 新年用个新环！ |
题目：
1 | from Crypto.Util.number import * |
题目就是一个RLWE，只是改变了其环R为：
具体来说，题目将长度不到64的flag串编码成R上的多项式S，然后生成随机多项式A，并且随机生成一个小噪声多项式E，计算出：
给出A、B，要求还原S。
实际上攻击的点就在于多项式S的系数都是ASCII码值，所以在模p下显得很小，从而可以用格攻击。
如果本身就了解RLWE造格的具体原理的话这题目就很简单，只需要略微改一改格就很快能做出。但如果一直以来造RLWE的格都是直接找别人的脚本跑、而不知道具体原理的话，可能就不太清楚如何改起。这里简单阐述一下其造格的思路，先从多项式乘法的矩阵表示讲起。
多项式乘法的矩阵表示
首先，对于一个多项式，我们可以用一个由其系数组成的向量来表示这个多项式，而不同幂次就仅仅代表着系数在多项式中的位置。那么现在把眼光放回这个题目里，由于环R的模多项式度是64，所以其中的多项式次数最高为63，因此对于这题目中的多项式S，我们可以把它写作如下向量：
它对应的多项式就是：
同理多项式B、E也就可以写成是：
接下来的问题是，我们如何把多项式的乘法，也就是AS这个计算过程写成矩阵表示。这一部分详细一点可以参考：
其实核心思路并不复杂，比如对于上文中的环R，其模多项式是：
这其实也就说明一个事情，在环R中总有：
这也就是说：
那么我们假设对于两个环R中的多项式a、b相乘，其得到的结果是c。我们知道a、b、c的最高次项的次数都小于n。所以如果我们仅仅计算ab乘积而不模x^n-1的话，他最多就有0到2n-2次项。又由上面的x^(n+i)=x^i，我们就可以推得下面这个重要性质：
- 乘积c中的i次项系数，其实就是ab乘积中的i次项系数与n+i次项系数之和
那么我们就可以根据这个性质写出多项式乘法的矩阵表示了。我们设a、b、c分别为：
比如对于c0，其代表的含义是ab乘积的0次项的系数，对应的我们就需要找ab乘积中的所有0次项以及n次项的系数并求和就得到c0；同理c1就找ab中的1次项以及n+1次项系数求和，以此类推。
这就得到了多项式乘法的矩阵表示形式：
需要注意的是，刚才我们讨论的环是模x^n-1下的，所以才会有x^(n+i)=x^i这一事实。而在本题目中环R是在模x^64+2024下的，上面的式子不成立，那么又该怎么办？
做法也很简单，相似的道理有：
所以其实也就略微变了点样子，这个环中具有的性质是：
所以对于该环中的多项式ab相乘得到c的过程，可以写作如下矩阵：
到这里我们就完成了该环下多项式的矩阵构建。
格攻击
其实只要能把矩阵造出来，那么在网上找一个RLWE的脚本并把矩阵换成上面这个，那么已经可以做出题目了。不过为了wp完整性还是简单说一下构造格的思路。我们知道对于题目中128bit的模素数p而言，E和S都是系数相当小的多项式，因此我们构造格的目的是在目标向量中找到他们。
为此我们可以把多项式乘法写成下面这样：
然后就是用刚才的矩阵来造格：
这个格具有的线性关系是：
前面的ki是因为我们的环还需要对多项式的所有系数模p，所以所有系数求和模p后展开的等式中都含有一个kip。
然后对这个格做LLL就能在第一行找到我们的目标向量了，取中间的64个数字，也就得到flag的全部字符。
exp：
1 | from Crypto.Util.number import * |
题目本身如果了解RLWE的话就很基础，主要是想通过wp帮助一些不太了解多项式乘法的cryptoer找找构建成矩阵的思路，从而不再只是调脚本跑。
New Year Ring2
题目描述：
1 | 新年换个新新环！ |
题目：
1 | from Crypto.Util.number import * |
这一题是上一题的加强，相对于上一题来说，本题又把商环更换为了：
但是目标是不变的，仍然是要利用s和e系数较小这一点，去设法构造格进行规约。
要构造出格就要先构造出商环中多项式乘积的矩阵表示。本题的难点也就在于，商环中现在不仅存在64次项和常数项，还存在一次项和三次项，那么该怎么去构造这个矩阵呢？
我们仍然是利用如下一点：
所以有：
那么对于之前举的多项式a乘b得到c的例子，我们假设ab乘完后先不模x^64+2x^3+2x+4，记这个乘积为d，那么d就有0到2x63次项。而由于上面推得的这个商环下多项式的同余关系，对于c中的各项系数来说，其0次项的系数应该有d中的0次项以及64次项的参与，其1次项应该有d中的1次项、64次项以及65次项参与，其2次项应该有d中的2次项、65次项以及66次项参与，其3次项应该有d中的3次项、64次项、66次项、67次项参与，……以此类推。
但是有一个需要注意的问题是，右边由于存在3+i和1+i项，所以有些项可能需要多次模，比如对于i=61就有：
右边的x^64就又需要展开，得到的最终式子是：
可以注意到，因为最高次项也只会有126次，所以只有i=61、62的时候需要进行二次模运算，不妨把i=61、62的情况一并列出：
所以次数为0到4的项的系数还需要额外调整一下。那么对于这道题中的S乘A的过程，就可以构造出这一次的多项式乘积矩阵如下：
造的格子就和上一道题目是一样的了，把矩阵换成上面这个就行。
exp：
1 | from Crypto.Util.number import * |
New Year Ring3
题目描述：
1 | 新年用个新新新新环！ |
题目：
1 | from Crypto.Util.number import * |
本题仍然基于RLWE，只是又将商环变换成：
似乎还是可以用刚才构造矩阵的思路去解，但是想一想就会发现，这里由于模多项式又多了非常多项，所以会变得极其麻烦。
因此，这一个题是想将商环下多项式乘法的矩阵表示推广到一个更一般的形式，也就是说，如果能找到一个方法，使得对任何商环中的多项式乘法都可以用一个统一的算法来表示矩阵的话，那么其实三个题目都能一步到位。
所以接下来就是阐述怎么构造出这样的矩阵。
首先，仍然接续前文的思路。对于一个商环的模多项式，设其最高次项次数为n，那么商环中的所有多项式就都可以用一个长度为n的向量表示，向量中的每一个值分别表示多项式0到n-1次项的系数。由于我们想得到的是一般形式的商环下的多项式乘法矩阵，因此我们下面将都用一个抽象出的例子来说明。我们就假设，我们要计算的是多项式a和多项式b在模多项式v下的乘积c，其中v是n次，那么就可以把这四个多项式记为：
而接下来的核心思路是，将商环下的多项式乘法拆分成两步，并分别用矩阵乘法表示：
- a和b相乘，得到多项式d
- d模v，得到c
然后将两步矩阵相乘，就得到我们需要的最终矩阵——商环下多项式乘法的表示矩阵。其中d是一个最高次项可以达到2n-2次的一个多项式，因此可以用向量写作：
那么接下来就分步阐述怎么构造矩阵。
a和b相乘，得到多项式d
由于不需要进行模多项式运算，所以这一步其实非常简单，对于目标向量d中每个值对应的次数，我们只需要将所有能得到这个次数的系数乘积求和即可。也就是说矩阵乘法可以表示成：
为了更方便说明，把向量和矩阵的大小都标识出来会更好：
那么接下来我们的目标是，将得到的d向量：
进行模v，从而得到最终的多项式c，将这个过程也表示成矩阵乘法。
d模v，得到c
首先对于d中前n项来说(也就是0到n-1次项)，表示到最终的向量c是很轻松的，由于次数低，不需要模多项式，所以只需要将对应数值加到c中对应项中就可以，也就是造一个单位矩阵即可。
而较难处理的是d中超过了n-1次的项，因为他们要进行模v的操作。而对于这里我们处理的手段仍然是构造模多项式中的同余方程：
也就有：
而又因为d中最高也就只有2n-2次项，所以其中i的范围是：
可以预见的是，由于高次项会存在多次使用同余方程降次，因此我们需要从i=0开始，逐步将x^(n+i)均转化成一个次数在0到n-1的多项式并求出系数，加到最终多项式c的对应项的系数中。
i=0时，显然直接利用刚才的同余方程就可以得到每个次数的项前需要加的系数：
而i=1时，右侧的同余方程又会出现需要降次的x^n次方项，如下：
好像不太好处理，但其实想一想，不就是把刚才求过的n次项降次后得到的系数代入这里不就好了吗？也就是：
然后展开运算出各项系数即可。
而继续看i=2的形式，右侧会得到：
可以发现红色项我们均计算过了，我们只需要继续刚才的过程：代入已经算出的式子并展开计算。这也就是一个迭代的过程，一直到：
计算就彻底结束了。
而要构造矩阵，只需要将d中的大于等于n次方的每一项系数乘以刚才对应展开形式中的对应项系数，就可以得到矩阵中对应的行，然后接在刚才的单位矩阵下即可。也就是说这一步的矩阵应该长下面这个样子：
其中r、s、t几行是我们计算出的值，这里只是随便用个符号记录，没有特别的意义。
这一步的矩阵也表示完了，然后对这一步的矩阵有：
综合表示
我们只需要将两个矩阵乘起来就得到我们需要的一般意义下的多项式乘法卷积矩阵了：
此时就有：
对于这个题目来说，之后就只需要将矩阵代入到RLWE的攻击格中，就可以规约得到需要的向量了。
exp：
1 | from Crypto.Util.number import * |
而这样的通解自然对前面的两题也适用。