脑筋急转弯II,题目难度上来了
目录传送门:cryptohack 练习学习汇总(writeup index)
Ellipse Curve Unencryptable
考虑到 $529 = 23^2$ 那么很容易就可以发现,若 $M*N=P$ 那么 $(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\cdot A.y$ 对 $G.x + 23\cdot G.y$ 求离散对数)
求出 n_a
之后易得 shared_secret
之后略
代码: cryptohack/mathematics brainteasers-part-2 Ellipse-Curve-Unencryptable.py
Roll your Own
我们考虑离散对数的安全性可以从什么地方突破。离散对数安全性的一个关键点在于:$n$ 是质数,而恰好这题没有这个限制,考虑从这个角度入手
同时,回忆 brainteasers-part-2 的 Modular Binomials。众所周知,离散对数令人不爽的地方就在于不能简化为多项式,但是本题 $n$ 不是质数
不妨设 $g=a+b$, 那么有 $g^x=\sum\limits_{i=0}^{x}C_x^ia^ib^{n-i}$。受到 Modular Binomials 的启发,我们不妨设 $a^2=n$,那么有 $g^x=xab+b^2$,这是一个非常优美的形式。只要 $b\not=0$ 且已知即可由 $g^x$ 推得 $x$。
不妨取 $b=1$,那么 $g^x=xa+1$。考虑到 $g^p=pa+1$,要让 $g^p\bmod n=1$,那么有 $n|pa$ 即 $a|p$,取 $a=p$ 即可
综上,取 $g=a+b=p+1,n=p^2$,那么 $g^p\bmod n=1$ 满足,且容易由 $g^x\bmod n$ 求得 $x$
代码: cryptohack/mathematics brainteasers-part-2 Roll-your-Own.py
Unencryptable
记 x=bytes_to_long(DATA)
注意到题目中有 RSA broken!?
故有 $x^e\equiv x\pmod N$
因此有 $N|x(x^{e-1}-1)$,即 $x^{65536}-1$ 含有 p 或 q
对 $x^{65536}-1$ 因式分解,得到的式子中可能分别含有 p 或 q。故依次与 $N$ 求 GCD 即可得到 $N$ 的其中一个因子
代码: 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!
形如 $\sum\limits_{i=1}^{n}x_ia_i\approx S$ 这样形式的方程第一个就应当想到 lattice(附加要求:$x_i$ 较小,$\approx$ 较严格)
构造格很简单。最后一列是根号的结果,最后一行的最后一列是算出来的结果。除了最后一行最后一列的对角线都是 1
其中 $SP_n=\lfloor\sqrt{P_n}\cdot 16^{64}\rfloor$, $cipher$ 为程序输出
另外,最后结果有可能是反过来的,所以需要取绝对值再用 chr()
转回来
代码: cryptohack/mathematics brainteasers-part-2 Real-Eisenstein.py