2025 n1junior crypto

出了三道 Easy xxx problem，都是比较纯粹考知识点的题目。

CheckIn

考虑 。

简单估计可以得到 ，也就是说 实际上是一个跟 差不多规模的量。

所以枚举这个 ，解方程可以得到 的估计值，然后使用 coppersmith 求出 。

exp 大概需要跑十几分钟。

MyRandom

熟悉 mt19937 可以立即发现这个就是改了一下 mt19937 的一些系数。

有一个网站 https://stackered.com/blog/python-random-prediction/ 对 mt19937 的各个原理讲的很详细了，本来是准备做 hint 放这个网站的，但是有的选手很快过了这题所以没放。

上面这个网站里也有现成的代码，可以直接拿来改改用。

然后做这个题，首先是 CFB mode 的加密方式可以拿到一半的数据，并且按照 mt19937 的状态计算就是连续 8 个拿到后 4 个。

这个题的 seed size 为 288 bit 实际上是很特殊的，因为如果是 256 bit 应该是没有办法还原这个 seed——mt19937 使用 seed 的过程从 9 个为一循环变成 8 个一循环，导致我们知道的这些连续数据实际上的效果重复了。

当然 288bit 太小了，可以 z3 直接解出来，预期是注意到 9 个一循环所以我们恰好可以用连续四个恢复一个 seed 的状态，跑 9 次就行了。

StrangeCurve

一个较简化的 csidh fault attack，论文是 https://eprint.iacr.org/2020/1006.pdf。

可以先去 cryptohack 上了解 isogeny 相关的知识，然后结合这个论文就很简单了。

我们令 ，。

问题点在于我们会在第 轮时， 有 的概率不在 上，而在 的 quadratic twist 上，导致 isogeny 方向变化。

我们令 比较大，那么就会得到正确的 ，然后第 轮的影响会大概率得到 ，满足 。

因此我们可以直接对 和各个 分别 mitm，就能还原 privkey。

是为了在 sage 上跑的比较快，我的 exp 10min 以内能出。

这个题实际上还有可以优化的点，比如我们可以先从 与 之间 mitm，并且注意到 是随机的，所以 的不可能很多，这样可以减少 mitm 的枚举量，并且知道哪些 的也可以减少求 和 的路径的复杂度，这样就可以让 更大一些。