[SWPU 2020]happy | NSSCTF
1
2
3
4
| ('c=', '0x7a7e031f14f6b6c3292d11a41161d2491ce8bcdc67ef1baa9eL')
('e=', '0x872a335')
#q + q*p^3 =1285367317452089980789441829580397855321901891350429414413655782431779727560841427444135440068248152908241981758331600586
#qp + q *p^2 = 1109691832903289208389283296592510864729403914873734836011311325874120780079555500202475594
|
给了c和e
还有p，q之间的关系
p和q可以通过z3暴力求
根据公式
m=c^d(mod p*q)
d为e关于mod((p-1)*(q-1))的逆元
exp:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| from z3 import*
from Crypto.Util.number import*
import gmpy2
c=0x7a7e031f14f6b6c3292d11a41161d2491ce8bcdc67ef1baa9e
e=0x872a335
f=Solver()
p,q=Int('p'),Int('q')
f.add(q + q*pow(p,3) ==1285367317452089980789441829580397855321901891350429414413655782431779727560841427444135440068248152908241981758331600586,
q*p + q *pow(p,2) == 1109691832903289208389283296592510864729403914873734836011311325874120780079555500202475594)
while f.check()==sat:
m=f.model()
print(m[p])
print(m[q])
np=int(str(m[p]))
nq=int(str(m[q]))
f.add(p!=np,q!=nq)
m=pow(c,gmpy2.invert(e,(np-1)*(nq-1)),np*nq)
try:
print(long_to_bytes(m).decode())
except Exception as e:
print('error')
print(long_to_bytes(m))
|
