BUUCTF 每日打卡 2021-4-5

引言

出人意料的得到消息要被拉去打国赛（第十四届全国大学生信息安全竞赛-创新实践能力赛）了（一脸懵逼） 我还什么都没学呢（摸鱼） 嘛，不过被分到第二梯队大概也没抱什么希望吧（继续摸鱼） 害，说丧气话也改变不了什么，还是脚踏实地地慢慢进步吧 毕竟 Crypto手 在队里也是稀缺人才 我也是加把劲骑士！(doge)

RSA2

dp(dq) 泄露的题没做过，不过跟 dp, dq 泄露相比容易许多 首先，根据 \[ dp \equiv d\space mod \space (p-1) \] 联想到 \[ \varphi = (p-1) * (q-1) \] 那肯定就有人问了，你在 dp,dq 泄露中字母就没联想到 φ 呢？ 对比 dp,dq 泄露和 dp(dq) 泄露的已知条件：前者已知 \(p, q, (n), (φ), dp, dq, c\) ；而后者已知 \(e, n, dp(dq), c\) 我们的目的是解出私钥 \(d\) ，或者 直接解出 \(c^{d}\) ，通过 \(m \equiv c^{d} \space mod \space n\) 来解出密文 \(m\) 而 RSA 加密算法中有很重要的一步 \[ e * d \equiv 1 \space mod \space \varphi \] dp(dq) 泄露问题中已知 \(e\) ，所以可以根据此式解出私钥 \(d\) 而 dp,dq 泄露问题中 \(e\) 未知，于是采取解出 \(c^{d}\) 整体的策略

回到 dp,dq 泄露问题 因为 \[ dp \equiv d\space mod \space (p-1) \] 所以 \(\exists\space k_{1} \in\mathbb{Z}, \space s.t.\) \[ dp = d + k_{1} * (p-1) \] 等式两边同时乘 \(e\) 得 \[ e * dp = e * d + k_{1} * e * (p-1) \qquad \qquad (*) \] 因为 \[ e * d \equiv 1 \space mod \space \varphi \] 所以 \(\exists\space k_{2} \in\mathbb{Z}, \space s.t.\) \[ e * d = 1 + k_{2} * \varphi = 1 + k_{2} * (p-1) * (q-1) \] 将此式中的 \(e * d\) 代入 \(*\) 式，得 \[ e * dp = 1+k * (p-1) \] 其中 \(k = (p-1) * (k_{1} * e + k_{2} * (q - 1)) \space \in\mathbb{Z}\)

由 \(dp \equiv d\space mod \space (p-1)\) 可知， \[ dp < (p-1) < p \] 故 \[ e > k \] 所以，只要我们使 \(k\) 遍历 \(e\) 的取值就能求出 \(p\) ，进而求出 \(\varphi\) ，再对 \(e\) 求关于 \(\varphi\) 的逆元，就能求出私钥 \(d\) 进行解密 实现代码如下：

from Crypto.Util.number import *

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

for k in range(1, e):
    p = (e*dp-1) // k +1
    q = n // p
    if (n - p*q) == 0:
        break
print(p, q)
phi = (p-1) * (q-1)
d = inverse(e, phi)
print(d)
m = pow(c, d, n)
print(long_to_bytes(m))

得到 flag{wow_leaking_dp_breaks_rsa?_98924743502}

RSA

打开 pub.key 文件，看到前缀后缀就知道是 SSL 证书格式 用解密网站：http://ctf.ssleye.com/pub_asys.html 得到 n 和 e 尝试用 http://factordb.com/ 网站爆破： 没有结果 emmm...... 再用 sagemath 爆破： 花了一点时间 这样，我们得出了 p, q, n, e，然后就可以开始解密。。。 嗯？？？ 密文呢？ 解压之后的文件里面还有一个 flag.enc 文件，密文应该就在里面 但是打开文件

一堆乱码是什么鬼？ 用 python 读取文件：

with open(r"D:\BUUCTF\Crypto\RSA(1)\0eaf8d6c-3fe5-4549-9e81-94ac42535e7b\flag.enc", "rb") as f:
    f = f.read()
print(f)

得到一串 bytes ：b'A0YJ^8x|$y[9c(9bb' bytes_to_long 之后应该就是密文了 解密代码如下：

from Crypto.Util.number import *

n = 86934482296048119190666062003494800588905656017203025617216654058378322103517
e = 65537
p = 285960468890451637935629440372639283459
q = 304008741604601924494328155975272418463

phi = (p-1) * (q-1)
d = inverse(e, phi)
print(d)

with open(r"D:\BUUCTF\Crypto\RSA(1)\0eaf8d6c-3fe5-4549-9e81-94ac42535e7b\flag.enc", "rb") as f:
    f = f.read()
print(f)
c = bytes_to_long(f)
print(c)

m = pow(c, d, n)
print(long_to_bytes(m))

这是我参考了大佬的建议自己写的版本 结果如下： 高亮处即为 flag ，但是有一堆 padding

然后是另一个参考了 wp 的版本：

from Crypto.Util.number import *
import rsa

n = 86934482296048119190666062003494800588905656017203025617216654058378322103517
e = 65537
p = 285960468890451637935629440372639283459
q = 304008741604601924494328155975272418463

phi = (p-1) * (q-1)
d = inverse(e, phi)
print(d)
key = rsa.PrivateKey(n, e, int(d), p, q)

with open(r"D:\BUUCTF\Crypto\RSA(1)\0eaf8d6c-3fe5-4549-9e81-94ac42535e7b\flag.enc", "rb") as f:
    f = f.read()
    print(rsa.decrypt(f, key))

结果如下： 属实恶心人

结语

作业肝完了，假期也结束了 感觉什么都没干啊啊啊啊啊啊啊啊 希望能坚持