[WP] cryptohack mathematics brainteasers-part-2

脑筋急转弯II，题目难度上来了

目录传送门：cryptohack 练习学习汇总(writeup index)

Ellipse Curve Unencryptable

考虑到 529=232529 = 23^2 那么很容易就可以发现，若 M∗N=PM*N=P 那么 (M.x+23⋅M.y)⋅(N.x+23⋅N.y)=(P.x+23⋅P.y)(M.x + 23\cdot M.y)\cdot(N.x + 23\cdot N.y)=(P.x + 23\cdot P.y)
有了这个性质我们可以很方便地利用 sage 的 discrete_log 函数求出 n_a（A.x+23⋅A.yA.x + 23\cdot A.y 对 G.x+23⋅G.yG.x + 23\cdot G.y 求离散对数）

求出 n_a 之后易得 shared_secret 之后略

代码: cryptohack/mathematics brainteasers-part-2 Ellipse-Curve-Unencryptable.py

Roll your Own

我们考虑离散对数的安全性可以从什么地方突破。离散对数安全性的一个关键点在于：nn 是质数，而恰好这题没有这个限制，考虑从这个角度入手
同时，回忆 brainteasers-part-2 的 Modular Binomials。众所周知，离散对数令人不爽的地方就在于不能简化为多项式，但是本题 nn 不是质数

不妨设 g=a+bg=a+b, 那么有 gx=∑i=0xCxiaibn−ig^x=\sum\limits_{i=0}^{x}C_x^ia^ib^{n-i}。受到 Modular Binomials 的启发，我们不妨设 a2=na^2=n，那么有 gx=xab+b2g^x=xab+b^2，这是一个非常优美的形式。只要 b≠0b\not=0 且已知即可由 gxg^x 推得 xx。
不妨取 b=1b=1，那么 gx=xa+1g^x=xa+1。考虑到 gp=pa+1g^p=pa+1，要让 gp mod n=1g^p\bmod n=1，那么有 n∣pan|pa 即 a∣pa|p，取 a=pa=p 即可
综上，取 g=a+b=p+1,n=p2g=a+b=p+1,n=p^2，那么 gp mod n=1g^p\bmod n=1 满足，且容易由 gx mod ng^x\bmod n 求得 xx

代码: cryptohack/mathematics brainteasers-part-2 Roll-your-Own.py

Unencryptable

记 x=bytes_to_long(DATA)
注意到题目中有 RSA broken!? 故有 xe≡x(modN)x^e\equiv x\pmod N
因此有 N∣x(xe−1−1)N|x(x^{e-1}-1)，即 x65536−1x^{65536}-1 含有 p 或 q
对 x65536−1x^{65536}-1 因式分解，得到的式子中可能分别含有 p 或 q。故依次与 NN 求 GCD 即可得到 NN 的其中一个因子

代码: cryptohack/mathematics brainteasers-part-2 Unencryptable.py

Cofactor Cofantasy

在数字特征上，pow(g, randint(2, phi - 1), N) 和 randint(1, N - 1) 并没有明显区别，唯一的区别在于计算量。又注意到题目特意强调 Calculating the solution should take less than 15 minutes.，所以猜测可能需要时间盲注。

经过测试，某 bit 为 1 或 0 之间有明显的计算时间区别；但是如果仅执行一次，可以发现效果不是很好（有浮动误差），最终选择执行 5 次计算用时之和。
考虑到已知第一位是 c 故 index=0 对应 bit=1，index=7 对应 bit=0，故可以一开始先测量 index=0,7 并取平均值作为比较标准

实际编写脚本的时候，我取得不是平均值，而略偏下一点，这是因为 bit=1 的情况下时间波动的远远比 bit=0 剧烈
另外在程序运行期间，不要访问其他网页，以避免网络波动造成的可能影响

代码: cryptohack/mathematics brainteasers-part-2 Cofactor-Cofantasy.py

Real Eisenstein

遇事不决就 lattice！
形如 ∑i=1nxiai≈S\sum\limits_{i=1}^{n}x_ia_i\approx S 这样形式的方程第一个就应当想到 lattice（附加要求：xix_i 较小，≈\approx 较严格）
构造格很简单。最后一列是根号的结果，最后一行的最后一列是算出来的结果。除了最后一行最后一列的对角线都是 1

(100⋯0SP1010⋯0SP2001⋯0SP3⋮⋮⋮⋱⋮⋮000⋯1SPn000⋯0cipher)\left( \begin{matrix} 1&0&0&\cdots&0&SP_1\\ 0&1&0&\cdots&0&SP_2\\ 0&0&1&\cdots&0&SP_3\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&1&SP_n\\ 0&0&0&\cdots&0&cipher\\ \end{matrix} \right)

其中 SPn=⌊Pn⋅1664⌋SP_n=\lfloor\sqrt{P_n}\cdot 16^{64}\rfloor, ciphercipher 为程序输出
另外，最后结果有可能是反过来的，所以需要取绝对值再用 chr() 转回来

代码: cryptohack/mathematics brainteasers-part-2 Real-Eisenstein.py