BUUCTF 每日打卡 2021-4-5

引言

出人意料的得到消息要被拉去打国赛(第十四届全国大学生dpd mod (p1)联想到
φ = ( p − 1 ) ∗ ( q − 1 ) varphi = (p-1) * (q-1) φ=(p1)(q1)
那肯定就有人问了,你在 dp,dq 泄露中字母就没联想到 φ 呢?
对比 dp,dq 泄露和 dp(dq) 泄露的已知条件:前者已知 p , q , ( n ) , ( φ ) , d p , d q , c p, q, (n), (φ), dp, dq, c p,q,(n),(φ),dp,dq,c ;而后者已知 e , n , d p ( d q ) , c e, n, dp(dq), c e,n,dp(dq),c
我们的目的是解出私钥 d d d ,或者 直接解出 c d c^{d} cd ,通过 m ≡ c d   m o d   n m equiv c^{d} space mod space n mcd mod n 来解出密文 m m m
而 RSA 加密算法中有很重要的一步
e ∗ d ≡ 1   m o d   φ e * d equiv 1 space mod space varphi ed1 mod φdp(dq) 泄露问题中已知 e e e ,所以可以根据此式解出私钥 d d d
而 dp,dq 泄露问题中 e e e 未知,于是采取解出 c d c^{d} cd 整体的策略

回到 dp,dq 泄露问题
因为
d p ≡ d   m o d   ( p − 1 ) dp equiv dspace mod space (p-1) dpd mod (p1)所以 ∃   k 1 ∈ Z ,   s . t . existsspace k_{1} inmathbb{Z}, space s.t.  k1Z, s.t.
d p = d + k 1 ∗ ( p − 1 ) dp = d + k_{1} * (p-1) dp=d+k1(p1)等式两边同时乘 e e e
e ∗ d p = e ∗ d + k 1 ∗ e ∗ ( p − 1 ) ( ∗ ) e * dp = e * d + k_{1} * e * (p-1) qquad qquad (*) edp=ed+k1e(p1)()因为
e ∗ d ≡ 1   m o d   φ e * d equiv 1 space mod space varphi ed1 mod φ所以 ∃   k 2 ∈ Z ,   s . t . existsspace k_{2} inmathbb{Z}, space s.t.  k2Z, s.t.
e ∗ d = 1 + k 2 ∗ φ = 1 + k 2 ∗ ( p − 1 ) ∗ ( q − 1 ) e * d = 1 + k_{2} * varphi = 1 + k_{2} * (p-1) * (q-1) ed=1+k2φ=1+k2(p1)(q1)将此式中的 e ∗ d e * d ed 代入 ∗ * 式,得
e ∗ d p = 1 + k ∗ ( p − 1 ) e * dp = 1+k * (p-1) edp=1+k(p1)其中 k = ( p − 1 ) ∗ ( k 1 ∗ e + k 2 ∗ ( q − 1 ) )   ∈ Z k = (p-1) * (k_{1} * e + k_{2} * (q - 1)) space inmathbb{Z} k=(p1)(k1e+k2(q1)) Z

d p ≡ d   m o d   ( p − 1 ) dp equiv dspace mod space (p-1) dpd mod (p1) 可知,
d p < ( p − 1 ) < p dp < (p-1) < p dp<(p1)<p
e > k e > k e>k所以,只要我们使 k k k 遍历 e e e 的取值就能求出 p p p ,进而求出 φ varphi φ ,再对 e e e 求关于 φ varphi φ 的逆元,就能求出私钥 d d 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 证书格式
BUUCTF 每日打卡 2021-4-5
用解密网站:http://ctf.ssleye.com/pub_asys.htmlBUUCTF 每日打卡 2021-4-5
得到 n 和 e
尝试用 http://factordb.com/ 网站爆破:
BUUCTF 每日打卡 2021-4-5
没有结果
emmm…
再用 sagemath 爆破:
BUUCTF 每日打卡 2021-4-5
花了一点时间
这样,我们得出了 p, q, n, e,然后就可以开始解密。。。
嗯???
密文呢?
解压之后的文件里面还有一个 flag.enc 文件,密文应该就在里面
但是打开文件
BUUCTF 每日打卡 2021-4-5

BUUCTF 每日打卡 2021-4-5
一堆乱码是什么鬼?
用 python 读取文件:

with open(r"D:BUUCTFCryptoRSA(1)eaf8d6c-3fe5-4549-9e81-94ac42535e7bflag.enc", "rb") as f:     f = f.read() print(f) 

得到一串 bytes :b’Ax96xc0YJ^x00nx96xb8xxb6|xd7$y[x13xa8xf2xcaTxdax06xd0xf1x9c(xbehx9bb’
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:BUUCTFCryptoRSA(1)eaf8d6c-3fe5-4549-9e81-94ac42535e7bflag.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)) 

这是我参考了大佬的建议自己写的版本
结果如下:
BUUCTF 每日打卡 2021-4-5
高亮处即为 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:BUUCTFCryptoRSA(1)eaf8d6c-3fe5-4549-9e81-94ac42535e7bflag.enc", "rb") as f:     f = f.read()     print(rsa.decrypt(f, key)) 

结果如下:
BUUCTF 每日打卡 2021-4-5
属实恶心人

结语

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

版权声明:玥玥 发表于 2021-04-07 2:30:34。
转载请注明:BUUCTF 每日打卡 2021-4-5 | 女黑客导航