GACTF2020密码学部分详解
前言
比赛网址：GACTF2020
writeup参考链接
ezAES
题目信息
附件是一个Python脚本，Gitee备份的challeng.py。
分析
整体浏览Python脚本后，可得此题考察CBC分组加密工作模式；总结一下脚本给出的信息：
- key给出前14位(key长16位，即最后2位未知)
- message的长度为86字节，因此明文最后一组填充10个’\n’
- 密文最后一组给出后10个字节
因此，可穷举key的最后2位，每一位考虑所有可打印字符，有100种可能，因此穷举key的最后2位有$10^{4}$种可能，处于合理范围；对每一个key，解密最后一组密文，将解密出的明文后10位与上一组密文后10位异或，若异或后均为’\n’，则说明穷举出正确的key；
解出正确的key之后，可按照同样的方式计算出SECRET，从而获取整个明文；
已知所有明文之后，由CBC工作模式：$m_{i}=D(c_{i};key)\oplus c_{i-1},i=n,\cdots,1$，其中$c_{0}=IV$，那么已知最后一组密文，就可以递推出IV：$c_{i-1}=D(c_{i};key)\oplus m_{i},i=n,\cdots,1$
解题
上述链接中的solve.py为解题的Python脚本；
程序运行结果如下：
1 | $ python solve.py |
what_r_the_noise
题目信息
噪音太大，听不见，China:124.71.145.165:9999(现在应该已经失效了)。
分析
大致意思是服务器返回的数据是加入了噪声的，让你去掉噪声，解出正确的明文；有点概率论知识应该想到获取多次数据取平均值。
解题
解题的Python脚本在Gitee备份中；
解出的flag可能不完全正确，但是你基本可以猜出是什么单词了！
最后得到flag为gactf{you_know_much_about_differential_privacy}
da Vinci after rsa
题目信息
附件中包含两个文本文件encryption与output；encryption中是一列数，output给出“RSA公钥”与密文；Gitee备份
分析
da Vinci翻译了一下(英语不好)是达芬奇，这既然是密码学题目，自然去查了一下达芬奇密码，发现这是一本书，在网上不停地查这本书，找到一个片段，“打乱的数字”一下引起我的注意，后面马上提到“斐波那契数列”，回去一看，encryption中的那一列数确实是打乱的斐波那契数列，到此encryption的作用弄明白了；
接下来将公钥的模数N放到yafu中分解，得到三个因子；但是我想，不怕，和RSA问题一样求解$d\equiv e^{-1}\ \textrm{mod}\ \phi(N)$即可解出$m\equiv c^{d}\ \textrm{mod}\ N$，编好程序运行时发现$e$在$\phi(N)$下没有逆，这一下子就不知道怎么办了，其实这样的方程也是有办法求解的，求解思路链接在此
解出的$m$虽然有多个，但是flag每个字符都是可见字符，这样最后只剩下一个$m$，这还不是flag；花括号内正好25个字符，encryption中正好25个数，按照一样的规则打乱花括号内的25个字符即得到真正的flag；
解题
上述GitHub备份链接中的solve.sage脚本为解题的sage脚本；
程序运行结果如下：
1 | $ sage solve.sage |
elgamal_rsa
题目信息
附件是一个Python脚本，Gitee备份
分析
$g^{q}\equiv 1\ \textrm{mod}\ p,h\equiv g^{d}\ \textrm{mod}\ p$
$c_{1}\equiv g^{r_{1}}\ \textrm{mod}\ p,c_{2}\equiv m\cdot h^{r_{1}}\ \textrm{mod}\ p$
$c_{11}\equiv g^{r_{2}}\ \textrm{mod}\ p,c_{22}\equiv m\cdot h^{r_{2}}\ \textrm{mod}\ p$
其中，$r_{2}\equiv (B\cdot r_{1}+A)\ \textrm{mod}\ q$
这里的$m$就是$secret$，$secret$是下面“RSA”加密的模数，因此首先要解出$secret$，这也是很好解的；
$c_{2}^{B}\cdot h^{A}\equiv (m\cdot h^{r_{1}})^{B}\cdot h^{A}\equiv m^{B}\cdot h^{B\cdot r_{1}+A}\equiv m^{B-1}\cdot c_{22}\ \textrm{mod}\ p$
$m^{B-1}\equiv c_{2}^{B}\cdot h^{A}\cdot c_{22}^{-1}\ \textrm{mod}\ p$，计算$t\equiv (B-1)^{-1}\ \textrm{mod}\ (p-1)$
那么$(c_{2}^{B}\cdot h^{A}\cdot c_{22}^{-1})^{t}\equiv m\ \textrm{mod}\ p$
解出$secret$后，放到yafu里面分解(因子是真的多，一度怀疑自己解错了)，求解flag的思路链接
解题
上述GitHub备份链接中的solve文件夹中为解题的脚本，解题分两步；第一步，解出secret；第二步，求解方程$c\equiv m^{e}\ \textrm{mod}\ N$($m
程序运行结果如下：
1 | $ python step1.py |
1 | $ sage step2.sage |
babycrypto
题目信息
附件是一个Python脚本，Gitee备份
分析
在GF(p)上定义的点集$\{(x,y)|x,y\in GF(p)\}$上定义加法”+”：$(x_{1},y_{1})+(x_{2},y_{2})=(x_{1}x_{2}-y_{1}y_{2},x_{1}y_{2}+x_{2}y_{1})$，定义乘法”$\cdot$”：$k\cdot (x,y)=(x,y)+\cdots +(x,y)$
给出基点g，$A=a\cdot g,B=b\cdot g$，给出A,B；
$shared=b\cdot A$，再利用shared生成AES密钥进行加密；
p未知！！！先介绍Edwards曲线E：$x^{2}+y^{2}\equiv 1+dx^{2}y^{2}\ \textrm{mod}\ p$，曲线上的加法定义为$(x_{1},y_{1})+(x_{2},y_{2})=((x_{1}y_{2}+x_{2}y_{1})/(1+dx_{1}x_{2}y_{1}y_{2}),(x_{1}x_{2}-y_{1}y_{2})/(1-dx_{1}x_{2}y_{1}y_{2}))$
令d=0，则E：$x^{2}+y^{2}\equiv 1\ \textrm{mod}\ p$，则加法重写为$(x_{1},y_{1})+(x_{2},y_{2})=(x_{1}y_{2}+x_{2}y_{1},x_{1}x_{2}-y_{1}y_{2})$
若我们设定d=0，那么$A(x_{1},y_{1}),B(x_{2},y_{2})$满足方程$x^{2}+y^{2}\equiv 1\ \textrm{mod}\ p$，求$x_{1}^{2}+y_{1}^{2}-1$与$x_{2}^{2}+y_{2}^{2}-1$的公约数，则p是其最大素因子；
下面考虑如何解出b，这是一个离散对数问题，难点是sage并未实现Edwards曲线及其运算；
给出一个有用的结论：$\{(x,y)|x,y\in GF(p),x^{2}+y^{2}\equiv 1\ \textrm{mod}\ p\}$与$H=F_{p}(w)/(w^{2}+1)$(有限域$F_{p}$上的多项式在模$w^{2}+1$下的剩余环)同构，同构映射$\sigma :E\rightarrow H$，$\sigma((x,y))=x+yw$
在sage中通过extend函数就可以生成H，从而可以求解此离散对数问题；
解题
上述GitHub备份链接中的solve文件夹中为解题的脚本，解题分两步；第一步，解出p；第二步，解出b然后以同样的方式生成AES密钥再对消息进行解密；
程序运行结果如下：
1 | $ python step1.py |
使用yafu分解，可得到p(在solve.sage中有给出)
1 | $ sage solve.sage |