本题主要实现了关于多项式运算和向量运算的相关考点，考察选手在逆向过程中对常见抽象代数结构/运算在二进制层面的特征识别和对基于代数构建的密码学场景的分析能力。

题目首先接收一个来自用户的长度为 78 字节的输入，取去掉前缀和后缀之后的中间的 72 字节，将其先按照 16 进制形式转换成一个 288 比特的大整数，然后对该数进行 RSA - 3840 加密，得到一个 3840 比特的加密结果，然后将该加密结果代入 check 函数检查其是否正确。

check 函数首先取 RSA 加密后的前 1920 比特，将其转化为一个 1920 比特的大数后代入某一 verify 函数中进行验证，并根据其返回结果是否为True来判定是否通过验证。

注意到这里存在对同一 verify 函数的两次调用，其中第一次调用所有传参均为硬编码，因此为一个恒成立的调用，该调用主要是为了帮助选手理解该 verify 通过的原因。

通过分析，可以看出这里主要实现了yige Schnorr 签名的验签过程，我们传入的 1920 比特的输入位于 verify 函数 API 中的私钥参数位置，因此这里的本质就是预期用户输入一个私钥，使得程序用该私钥对某一硬编码的消息进行签名，然后用一硬编码的公钥进行验签，若验签通过则返回True，因此选手的任务就是需要根据 Schnorr 签名/验签的流程和已知的硬编码数据恢复出私钥的值。

Schnorr签名的密钥生成/签名/验签过程可以参考：https://en.wikipedia.org/wiki/Schnorr_signature

根据该运算过程，可知存在表达式 (1) 成立：

其中：

根据题目提供的硬编码数据，可知这里我们知道 200 次签名的结果，即我们知道 200 组的，要求我们恢复出私钥x，注意到这里的每个ki并不是一个直接生成的随机数，而是由若干下的随机数累加而成的，那么这里我们可以尝试采用[子集和问题]的思想，通过格基规约的形式恢复出ki相关的信息，继而恢复出私钥x。

*点击可查看大图

此时如果将表达式转移到模下的同余式：

该问题可以通过 Nguyen-Stern 算法求解，即通过构造两次垂直格的形式进行 [LLL 格基规约]，如图 1 所示，详细分析过程可参考[该文献](https://eprint.iacr.org/2020/461.pdf)。

然而该表达式同本题中的场景存在一定差异（本题中还引入了独立的加法运算），注意到上述论文中还提到了关于隐式子集和问题的一个变种场景的讨论，即引入了加法运算后的仿射隐式子集和问题（affine hidden subset sum problem）

如表达式 (4) 所示，论文中在对该问题的讨论中引入了关于 Schnorr 签名场景的 case study，该场景和我们本题中的场景是一致的，根据论文中的分析思路，该问题同样可以通过构造两次垂直格按照 Nguyen-Stern算法的思路求解，如图 2 所示，详细分析过程可参考该文献(https://eprint.iacr.org/2020/461.pdf)

球分享