Official Solution to the "lowExponent" Problem in NepCTF2021
这题使用的加密算法是 Demytko，属于一种类似 RSA 的在椭圆曲线上的加密算法，这题的攻击思路也是可以完全类比 RSA Hastad 广播攻击。 加密后的结果是椭圆曲线上的点， Division Polynomials 使我们可以用仅含一个未知数的多项式来表示这个点的 $x$ 坐标： $$ \begin{aligned} \psi_{-1} &=-1 \\ \psi_{0} &=0 \\ \psi_{1} &=1 \\ \psi_{2} &=2 y \\ \psi_{3} &=3 x^{4}+6 a x^{2}+12 b x-a^{2} \\ \psi_{4} &=4 y\left(x^{6}+5 a x^{4}+20 b x^{3}-5 a^{2} x^{2}-4 a b x-8 b^{2}-a^{3}\right) \\ \psi_{2 i+1} &=\psi_{i}\left(\psi_{i+2} \psi_{i-1}^{2}-\psi_{i-2} \psi_{i+1}^{2}\right) / 2 y, i \geq 2 \\ \psi_{2 i} &=\psi_{i+2} \psi_{i}^{3}-\psi_{i+1}^{3} \psi_{i-1}, i \geq 3 \end{aligned} $$...