引言
出人意料的得到訊息要被拉去打國賽（第十四屆全國大學生資訊安全競賽-創新實踐能力賽）了（一臉懵逼）
我還什么都沒學呢（摸魚）
嘛，不過被分到第二梯隊大概也沒抱什么希望吧（繼續摸魚）
害，說喪氣話也改變不了什么，還是腳踏實地地慢慢進步吧
畢竟 Crypto手 在隊里也是稀缺人才
我也是加把勁騎士！(doge)
RSA2
dp(dq) 泄露的題沒做過，不過跟 dp, dq 泄露相比容易許多
首先，根據
d
p
≡
d
m
o
d
(
p
?
1
)
dp \equiv d\space mod \space (p-1)
dp≡d mod (p?1)聯想到
φ
=
(
p
?
1
)
?
(
q
?
1
)
\varphi = (p-1) * (q-1)
φ=(p?1)?(q?1)
那肯定就有人問了，你在 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
m≡cd mod n 來解出密文
m
m
m
而 RSA 加密演算法中有很重要的一步
e
?
d
≡
1
m
o
d
φ
e * d \equiv 1 \space mod \space \varphi
e?d≡1 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 d\space mod \space (p-1)
dp≡d mod (p?1)所以
?
k
1
∈
Z
,
s
.
t
.
\exists\space k_{1} \in\mathbb{Z}, \space s.t.
? k1?∈Z, s.t.
d
p
=
d
+
k
1
?
(
p
?
1
)
dp = d + k_{1} * (p-1)
dp=d+k1??(p?1)等式兩邊同時乘
e
e
e 得
e
?
d
p
=
e
?
d
+
k
1
?
e
?
(
p
?
1
)
(
?
)
e * dp = e * d + k_{1} * e * (p-1) \qquad \qquad (*)
e?dp=e?d+k1??e?(p?1)(?)因為
e
?
d
≡
1
m
o
d
φ
e * d \equiv 1 \space mod \space \varphi
e?d≡1 mod φ所以
?
k
2
∈
Z
,
s
.
t
.
\exists\space k_{2} \in\mathbb{Z}, \space s.t.
? k2?∈Z, 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)
e?d=1+k2??φ=1+k2??(p?1)?(q?1)將此式中的
e
?
d
e * d
e?d 代入
?
*
? 式，得
e
?
d
p
=
1
+
k
?
(
p
?
1
)
e * dp = 1+k * (p-1)
e?dp=1+k?(p?1)其中
k
=
(
p
?
1
)
?
(
k
1
?
e
+
k
2
?
(
q
?
1
)
)
∈
Z
k = (p-1) * (k_{1} * e + k_{2} * (q - 1)) \space \in\mathbb{Z}
k=(p?1)?(k1??e+k2??(q?1)) ∈Z
由
d
p
≡
d
m
o
d
(
p
?
1
)
dp \equiv d\space mod \space (p-1)
dp≡d mod (p?1) 可知，
d
p
<
(
p
?
1
)
<
p
dp < (p-1) < p
dp<(p?1)<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 證書格式
用解密網站：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’A\x96\xc0YJ^\x00\n\x96\xb8x\xb6|\xd7$y[\x13\xa8\xf2\xcaT\xda\x06\xd0\xf1\x9c(\xbeh\x9bb’
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))
結果如下：
屬實惡心人
結語
作業肝完了，假期也結束了
感覺什么都沒干啊啊啊啊啊啊啊啊
希望能堅持
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/273331.html
標籤：其他
上一篇：shiro權限安全框架
下一篇：介面冪等性是什么？如何設計？