MTCTF 2021 Writeup（复现练习）

NSSCTF Crypto继续刷题中，本文章用来记录，有问题欢迎交流＼(●´ϖ’●)／

Symbol

题目

分析

看格式像是flag，猜测前四个字母就是flag，仔细观察对比之后，发现希腊字母$\lambda ,\alpha ,\gamma$的latex语法标注分别为：

1
\lambda,\alpha,\gamma

发现首字母分别对应$l,a,g$，那么第一个应该是$f$，看起来像是音乐符号，搜索之后发现是降号（flat）$\flat$对应$f$，证明我们的思路是正确的，就是要找到对应符号的英文语法的首字母，那么接下来便挨个寻找即可
找到一个参考博客：Latex符号大全 - 高峰OUC - 博客园

1
\forall \uplus \nu _ \Lambda \alpha T \epsilon \Xi _ T \approx \triangleleft \hbar

即$\forall \uplus \nu _ \Lambda \alpha T \epsilon \Xi _ M \approx \triangleleft \hbar$
对应的字符为fun_LaTeX_Math，计算得到32为md5为e1b217dc3b5e90b237b45e0a636e5a86

Strange_rsa1

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from sage.all import RealField
from secret import flag1


Bits = 512
p = getPrime(Bits)
q = getPrime(Bits)
n = p * q

gift = RealField(prec=Bits*2)(p) / RealField(prec=Bits*2)(q)
e = 0x10001
m = bytes_to_long(flag1)
c = pow(m, e, n)

output = open('output.txt', 'w')
output.write('n = ' + str(n) + '\n')
output.write('c = ' + str(c) + '\n')
output.write('gift = ' + str(gift) + '\n')

分析

$gift = \frac{p}{q},n=p\cdot q$
即$p = \sqrt {gift\cdot n}=\sqrt{p^2}$
这里使用sagemath中的sqrt进行高精度开方，之后正常RSA解密即可

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#sage
import gmpy2
from Crypto.Util.number import *

n = 108525167048069618588175976867846563247592681279699764935868571805537995466244621039138584734968186962015154069834228913223982840558626369903697856981515674800664445719963249384904839446749699482532818680540192673814671582032905573381188420997231842144989027400106624744146739238687818312012920530048166672413
c = 23970397560482326418544500895982564794681055333385186829686707802322923345863102521635786012870368948010933275558746273559080917607938457905967618777124428711098087525967347923209347190956512520350806766416108324895660243364661936801627882577951784569589707943966009295758316967368650512558923594173887431924
gift = 0.9878713210057139023298389025767652308503013961919282440169053652488565206963320721234736480911437918373201299590078678742136736290349578719187645145615363088975706222696090029443619975380433122746296316430693294386663490221891787292112964989501856435389725149610724585156154688515007983846599924478524442938
e = 0x10001
p = int(sqrt(n*gift))
#print(p)
q = n // p
phi = (p-1)*(q-1)
d = inverse(e, phi)
m = pow(c, d, n)
ans = long_to_bytes(m)
print(ans)

Remeo

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
from Crypto.Util.number import*
from Crypto.Cipher import AES
from secret import msg,password,flag
import socketserver
import signal
assert len(msg) == 32
assert len(password) == 8

def padding(msg):
    return msg + bytes([0 for i in range((16 - len(msg))%16)])

class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)       
        except:
            pass

    def recv(self):
        return self._recvall()

    def login(self):
        right_num = 0
        while 1:
            self.send(b'[~]Please input your password:')
            str1 = self.recv().strip()[:8]
            true_num = 0
            for i in range(len(password)):
                if str1[i] != password[i]:
                    login = False
                    self.send(b'False!')
                    break
                else:
                    true_num = i + 1 

                if right_num > true_num:
                    continue
                else:
                    right_num = true_num

                if true_num == len(password):
                    login = True
                check = b''
                for i in range(0x2000):
                    check = self.aes.encrypt(padding(check[:-1] + str1[:i+1]))

            if login == True:
                self.send(b"Login Success")
                return True,check[:16]
            
        return False

    def handle(self):
        signal.alarm(100)
        self.aes = AES.new(padding(password),AES.MODE_ECB)
        _,final_check = self.login()
        if _ == 1:
            assert msg.decode() == final_check.hex()
            self.send(b'Good Morning Master!')
            self.send(flag)
            
class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 9999
    print("HOST:POST " + HOST+":" + str(PORT))
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

分析

分析题目，发现当password的某一位正确时都会进行0x2000次AES加密，因此很明显暗示我们是Time Attack，我们可以通过爆破时检验与前一次爆破时所需要时间差的大小来判断当前字符是否正确。
具体可参考：20211211-美团CTF | 4XWi11’s Blog

ezRSA

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *

flag = open('flag.txt', 'rb').read()
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
e = 65537
n = p * q
c = pow(m, e, n)

s = getPrime(256)
M = getPrime(5048)
hint = (p - 297498275426) * inverse(s, M) % M
t = open("message.txt", "w")
t.write(f"e = {e}\nc = {c}\nn = {n}\nM = {M}\nhint = {hint}\n")
t.close()

分析

$hint \equiv (p-297498275426)\cdot s^{-1} \mod M$
令$p’=p-297498275426$，则有$hint\equiv p’\cdot s^{-1}\mod M$
因此$p’= hint\cdot s - kM$
构造格
$$
(s,-k)
\begin{pmatrix}
1 & hint \newline
0 & M
\end{pmatrix}
=(s,p’)
$$

之后求出$p’$也就求出了$p$，后续简单RSA解密即可

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#sage10.6
from Crypto.Util.number import *
e = 65537
c = 11223534598141520071392544441952727165225232358333005778273904279807651365082135278999006409297342081157139972503703772556228315654837441044781410960887536342197257046095815516053582104516752168718754752274252871063410625756822861003235434929734796245933907621657696650609132419469456238860601166224944487116
n = 99499509473364452726944770421623721217675378717234178828554602484867641740497277374806036356486848621495917213623425604565104435195783450029879177770305417469850119739921527698744700219067563802483159458398895082044997907953256062342593605652927874232404778144112740505724215742062859322375891810785229735653
M = 28858066896535909755146975040720031655813099454455588895434479778600245612915775220883088811806723015938061791264869678085304248608125313205719043320256733514389739252845381708094678596099621503299764646358765107958130065721737938646850422959290465490270263553423913213684958592738500488797707239673645370968467090153285601432966586133693641854092761919184904521240074718850103356119966387029699913571443658384564840234765103070736676067458391659605655580766436276719610283460962533141261830775028138998594269732067550977245136631815804641115446066102981044849495663224005844657686979516481904043008222498344271373989609634617315702887646444506965035406154183377067490922195507071571055579654138590566650703038341939225657159668601565182939447340585110418258653618384852356058444795156595720943362884361136229430356254095673818462046182310826133487611183265532844700265640889105864909560170846171486510513240630480729194415061752698286990999064594811803482429976978688266632277914610443963726561921790718480343488391563503774868490108659902216386976683532579945706490286814310031310144410303859633785939399012605326754445715302492704458881700872467560968264583996658711892595658439058034434031646411995511168849724976850557976639662545139917517675296224197763447929417263845949813741362574641118781293171167041592771305352186419565096347024619027397784780864922205105185970180629777320680707022011697404359388540366320053501502698747763307336114482530784826238326983596966436776918503653153420281803168537703048371580451
hint = 24302462761412867722556483860201357169283131384498485449193507018526006760633350601593235386242712333885826513399701577522498685938541691414316724804357523659514319083860507720945068584985970098437482386854188516742033184163273293005356970701527614010961471490166306765208284126815267752826036846338185010168551115391901008731195800723630612524215610302192763771954146943262822909368086155537366851998954401585888789660061750804720858175620022924944428882337005545535959410243692854073069775794945154943244522898330286785483043492678802461244624116832548150221211726044545331789932659966539042635768789637635754297830131948383991027466194455817875377950516103513735000718642093769229006510961952865719649517629939801014585849419818774317178973918720330390674833583065434312010539617630210110724391629534996688713945139529416075521015600392479980677759342058040778532467875961508475990300178277703011765698425360329342396347848373844031930655143343217447877587074485794273364964346235973542157189093330870952677683308479410235841331914353677363106473914986073397716367455628483060709281215783434084559550690248426391913205234184130354155776334292729262232484610747771114078013979494659835579574006801652858265173309736540235377076956677464263798132149783780830729103485354096234062135454873557941791812722418582207577124971978987895472250326100927372068822672582017222521124179752698654114839303426099426224351872025466618402675104161895600513776962289703455252021742990686505176582638132300246212598903123706906104217087


G = Matrix(ZZ,[[1,hint],[0,M]])
L = G.LLL()[0]
s , p1 = L
s = abs(s)
p1 = abs(p1)
print(s,p1)
p = p1 + 297498275426
q = n//p
assert n == p*q
print(p*q)
d = inverse(e , (p-1)*(q-1))
m = pow(c , d , n)
ans = long_to_bytes(m)
print(ans)

hamburgerRSA

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *

flag = open('flag.txt').read()
nbit = 64

while True:
    p, q = getPrime(nbit), getPrime(nbit)
    PP = int(str(p) + str(p) + str(q) + str(q))
    QQ = int(str(q) + str(q) + str(p) + str(p))
    if isPrime(PP) and isPrime(QQ):
        break

n = PP * QQ
m = bytes_to_long(flag.encode())
c = pow(m, 65537, n)
print('n =', n)
print('c =', c)

分析

题目中的PP，QQ的生成方式十分特别，是由64bit的素数$p,q$拼接而成的
我们设$x= len(str(p)),y=len(str(q))$，则有：
$PP = 10^{x+2y} p+10^{2y} p+10^y q+q$
$QQ = 10^{2x+y} q+10^{2x} q+10^x p+p$
$n = 10^{3x+3y}pq + …+pq$
因此我们可以发现$n$的高位和低位都暴露了$pq$的高位和低位
由于$p,q$的位数可能为$19,20$，因此$pq$的位数大概在$38,39,40$附近，而考虑到进位等情况，高低泄露的位数大概都在$18,19$附近。
中间剩下的位数数据我们可以直接爆破。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#sage10.6
from gmpy2 import *
from Crypto.Util.number import *
from itertools import product
from string import digits

n = 177269125756508652546242326065138402971542751112423326033880862868822164234452280738170245589798474033047460920552550018968571267978283756742722231922451193
c = 47718022601324543399078395957095083753201631332808949406927091589044837556469300807728484035581447960954603540348152501053100067139486887367207461593404096


high = str(n)[:18]
low = str(n)[-18:]

for i in range(1000):
    pq = high + str(i) + low
    pq_temp = [i for i,_ in factor(int(pq))]
    if len(pq_temp) == 2 and pq_temp[0].nbits() == 64:
        p, q = pq_temp
        print(i)
        break
PP = int(str(p) + str(p) + str(q) + str(q))
QQ = int(str(q) + str(q) + str(p) + str(p))

d = inverse(65537, (PP-1)*(QQ-1))
m = pow(c, d, n)
ans = long_to_bytes(m)
print(ans)

RomeoAndJuliet

Study > WriteUp
#CTF
MTCTF 2021 Writeup（复现练习）
http://ramoor.github.io/2025/08/14/MTCTF 2021 Writeup（复现练习）/
作者
Ramoor
发布于
2025年8月14日
许可协议