2024 XYCTF 部分题解

和同学keyboard,furina一起组了个xing战队打了这场XYCTF.说是新生赛但题目不算很容易,所以姑且记录一下.

标*的是赛后复盘的题目.

Crypto-happy_to_solve1

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


def get_happy_prime():
    p = getPrime(512)
    q = sympy.nextprime(p ^ ((1 << 512) - 1))
    return p, q


m = bytes_to_long(flag)
p, q = get_happy_prime()
n = p * q
e = 65537
print(n)
print(pow(m, e, n))
# 24852206647750545040640868093921252282805229864862413863025873203291042799096787789288461426555716785288286492530194901130042940279109598071958012303179823645151637759103558737126271435636657767272703908384802528366090871653024192321398785017073393201385586868836278447340624427705360349350604325533927890879
# 14767985399473111932544176852718061186100743117407141435994374261886396781040934632110608219482140465671269958180849886097491653105939368395716596413352563005027867546585191103214650790884720729601171517615620202183534021987618146862260558624458833387692782722514796407503120297235224234298891794056695442287

从题目条件可以推出 \(p+q=2^{512}+k\) ，其中k的大小不会很大。因此构造方程 \(x^2-(2^{512}+k)x+n=0\) ，利用该方程暴力搜索p+q即可。

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import long_to_bytes

n = 24852206647750545040640868093921252282805229864862413863025873203291042799096787789288461426555716785288286492530194901130042940279109598071958012303179823645151637759103558737126271435636657767272703908384802528366090871653024192321398785017073393201385586868836278447340624427705360349350604325533927890879
c = 14767985399473111932544176852718061186100743117407141435994374261886396781040934632110608219482140465671269958180849886097491653105939368395716596413352563005027867546585191103214650790884720729601171517615620202183534021987618146862260558624458833387692782722514796407503120297235224234298891794056695442287

P.<x> = ZZ[]

t = 1 << 512
while True:
    f = x ^ 2 - t * x + n
    rs = f.roots()
    if len(rs) > 0:
        p = rs[0][0]
        q = n // p
        assert p * q == n
        break
    t += 1
d = inverse_mod(65537, (p - 1) * (q - 1))
m = power_mod(c, d, n)
print(long_to_bytes(m).decode())
# XYCTF{3f22f4efe3bbbc71bbcc999a0a622a1a23303cdc}

Crypto-x0y

题目如下

Python
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
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os

flag = open("flag.txt", "rb").read()
key = os.urandom(16)
iv = os.urandom(16)
flag = pad(flag, 16)


def aes_encrypt(key, plaintext):
    cipher = AES.new(key, AES.MODE_ECB)
    return cipher.encrypt(plaintext)


def encrypt(key, plaintext, iv):
    ciphertext = b""
    for i in range(0, len(plaintext), AES.block_size):
        key_block = aes_encrypt(key, iv)
        ciphertext_block = bytes(
            [plaintext[i + j] ^ key_block[j] for j in range(AES.block_size)]
        )
        ciphertext += ciphertext_block
        iv = key_block
    return ciphertext


while 1:
    try:
        print("1.print\n2.input\n3.exit")
        a = input("> ")
        if a == "1":
            print((iv + encrypt(key, flag, iv)).hex())
        elif a == "2":
            ivs = bytes.fromhex(input("iv: "))
            inputs = bytes.fromhex(input("message: "))
            print(encrypt(key, inputs, ivs).hex())
        elif a == "3":
            exit(0)
        else:
            print("You need input 1,2,3")
    except:exit(0)
# b8bade451e6cc96d6f1b1f3a9e0c76cddc21942c4adf94561b4003c7473df446caf7d88b8911ebde71c0716a67cba57460ffe68b84ccea0906dddfb19d9a7223

已知iv，且key是选定之后一直不变的，所以key_block其实也是一直不变的。构造一个与密文等长的'0'序列输入即可获取到key_block的值，随后与密文xor即得。

exp:

Python
1
2
3
4
5
6
cipher=[0xdc,0x21,0x94,0x2c,0x4a,0xdf,0x94,0x56,0x1b,0x40,0x03,0xc7,0x47,0x3d,0xf4,0x46,0xca,0xf7,0xd8,0x8b,0x89,0x11,0xeb,0xde,0x71,0xc0,0x71,0x6a,0x67,0xcb,0xa5,0x74,0x60,0xff,0xe6,0x8b,0x84,0xcc,0xea,0x09,0x06,0xdd,0xdf,0xb1,0x9d,0x9a,0x72,0x23]
key=[0x84,0x78,0xd7,0x78,0x0c,0xa4,0xf5,0x6e,0x7a,0x24,0x37,0xa4,0x24,0x58,0xd9,0x7f,0xab,0xc4,0xed,0xa6,0xbd,0x20,0xdd,0xe9,0x5c,0xf9,0x14,0x5e,0x56,0xe6,0x95,0x43,0x56,0xca,0xd5,0xe9,0xb1,0xaa,0x8e,0x3e,0x36,0xbb,0xa2,0xbb,0x99,0x9e,0x76,0x27]
plain=""
for i in range(len(cipher)):
    plain+=chr(cipher[i]^key[i])
print(plain)

Crypto-babyRSAMAX

Python
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
from Crypto.Util.number import *
from gmpy2 import *
from random import choice

flag = b'XYCTF{******}'
e = '?'
def getBabyPrime(nbits):
    while True:
        p = 1
        while p.bit_length() <= nbits:
            p *= choice(sieve_base)
        
        if isPrime(p+1):
            return p+1

p = getBabyPrime(512)
q = getBabyPrime(512)
n = p*q
gift1 = (pow(p,e,n)-pow(q,e,n)) % n
gift2 = pow(p+q,e,n)

t = 65537
x = bytes_to_long(e)
y = pow(x, t, n)

m = bytes_to_long(flag)
c = powmod(m, e, n)

print(f'n = {n}')
print(f'gift1 = {gift1}')
print(f'gift2 = {gift2}')
print(f'c = {c}')
print(f'y = {y}')

'''
n = 39332423872740210783246069030855946244104982381157166843977599780233911183158560901377359925435092326653303964261550158658551518626014048783435245471536959844874036516931542444719549997971482644905523459407775392702211086149279473784796202020281909706723380472571862792003687423791576530085747716706475220532321
gift1 = 4549402444746338327349007235818187793950285105091726167573552412678416759694660166956782755631447271662108564084382098562999950228708300902201571583419116299932264478381197034402338481872937576172197202519770782458343606060544694608852844228400457232100904217062914047342663534138668490328400022651816597367310
gift2 = 111061215998959709920736448050860427855012026815376672067601244053580566359594802604251992986382187891022583247997994146019970445247509119719411310760491983876636264003942870756402328634092146799825005835867245563420135253048223898334460067523975023732153230791136870324302259127159852763634051238811969161011462
c = 16938927825234407267026017561045490265698491840814929432152839745035946118743714566623315033802681009017695526374397370343984360997903165842591414203197184946588470355728984912522040744691974819630118163976259246941579063687857994193309554129816268931672391946592680578681270693589911021465752454315629283033043
y = 1813650001270967709841306491297716908969425248888510985109381881270362755031385564927869313112540534780853966341044526856705589020295048473305762088786992446350060024881117741041260391405962817182674421715239197211274668450947666394594121764333794138308442124114744892164155894256326961605137479286082964520217

'''

gift1和gift2相加后与n进行gcd即可得到p，由此分解出p,q，迎刃而解。

Python
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
from Crypto.Util.number import *

import gmpy2

  

t = 65537

n = 39332423872740210783246069030855946244104982381157166843977599780233911183158560901377359925435092326653303964261550158658551518626014048783435245471536959844874036516931542444719549997971482644905523459407775392702211086149279473784796202020281909706723380472571862792003687423791576530085747716706475220532321

gift1 = 4549402444746338327349007235818187793950285105091726167573552412678416759694660166956782755631447271662108564084382098562999950228708300902201571583419116299932264478381197034402338481872937576172197202519770782458343606060544694608852844228400457232100904217062914047342663534138668490328400022651816597367310

gift2 = 111061215998959709920736448050860427855012026815376672067601244053580566359594802604251992986382187891022583247997994146019970445247509119719411310760491983876636264003942870756402328634092146799825005835867245563420135253048223898334460067523975023732153230791136870324302259127159852763634051238811969161011462

c = 16938927825234407267026017561045490265698491840814929432152839745035946118743714566623315033802681009017695526374397370343984360997903165842591414203197184946588470355728984912522040744691974819630118163976259246941579063687857994193309554129816268931672391946592680578681270693589911021465752454315629283033043

y = 1813650001270967709841306491297716908969425248888510985109381881270362755031385564927869313112540534780853966341044526856705589020295048473305762088786992446350060024881117741041260391405962817182674421715239197211274668450947666394594121764333794138308442124114744892164155894256326961605137479286082964520217

gift3 = gift1+gift2
p = gcd(gift3,n)
q = n//p
phi = (p - 1)*(q - 1)

  

#解e

d1 = gmpy2.invert(t,phi)
e=pow(y,d1,n)
print(long_to_bytes(e)) #因为逆天的出题人把e套了一层bytes所以转一下

# XYCTF{e==4096}

# e和phin不互素，CRT启动！

  

'''Sage

c = 16938927825234407267026017561045490265698491840814929432152839745035946118743714566623315033802681009017695526374397370343984360997903165842591414203197184946588470355728984912522040744691974819630118163976259246941579063687857994193309554129816268931672391946592680578681270693589911021465752454315629283033043

p=166353789373057352195268575168397750362643822201253508941052835945420624983216456266478176579651490080696973849607356408696043718492499993062863415424578199

q=236438400477521597922950445153796265199072404577183190953114805170522875904551780358338769440558816351105253794964040981919231484098097671084895302287425479

e = 4096

  

for mp in GF(p)(c).nth_root(e, all=True):
    for mq in GF(q)(c).nth_root(e, all=True):
        m = crt([ZZ(mp), ZZ(mq)], [p, q])
        try:
            res = bytes.fromhex(hex(m)[2:])
            if res.isascii():
                print(res)
        except:
            pass

'''

# b'XYCTF{Rabin_is_so_biggggg!}'

Crypto-factor1

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import gmpy2

import hashlib

from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)
d = getPrime(512)
e = gmpy2.invert(d, (p**3 - 1) * (q**3 - 1))
flag = "XYCTF{" + hashlib.md5(str(p + q).encode()).hexdigest() + "}"
print(e)
print(p * q)
# 172005065945326769176157335849432320425605083524943730546805772515111751580759726759492349719668775270727323745284785341119685198468883978645793770975366048506237371435027612758232099414404389043740306443065413069994232238075194102578269859784981454218948784071599231415554297361219709787507633404217550013282713899284609273532223781487419770338416653260109238572639243087280632577902857385265070736208291583497988891353312351322545840742380550393294960815728021248513046077985900158814037534487146730483099151396746751774427787635287611736111679074330407715700153025952858666841328055071403960165321273972935204988906850585454805923440635864200149694398767776539993952528995717480620593326867245714074205285828967234591508039849777840636255379730281105670496110061909219669860172557450779495125345533232776767292561378244884362014224844319802810586344516400297830227894063759083198761120293919537342405893653545157892446163

# 99075185389443078008327214328328747792385153883836599753096971412377366865826254033534293886034828804219037466246175526347014045811852531994537520303063113985486063022444972761276531422538694915030159420989401280012025249129111871649831185047820236417385693285461420040134313833571949090757635806658958193793

e过大，一眼Wiener Attack。需要注意的是，虽然从题目中的条件可以推知 \(ed\equiv 1 \bmod(\phi(N))\) ，但是因为d的范围，使用 \(N\) 去攻击并不能成功，而是要根据题目中的形式需要使用 \(N^3\) ，使得d落在可攻击范围之内。

Python
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
def factor_rsa_wiener(N, e):
    N = Integer(N)
    e = Integer(e)
    cf = (e / N).continued_fraction().convergents()
    for f in cf:
        k = f.numer()
        d = f.denom()
        if k == 0:
            continue
        phi_N = ((e * d) - 1) / k
        b = -(N - phi_N + 1)
        dis = b ^ 2 - 4 * N
        if dis.sign() == 1:
            dis_sqrt = sqrt(dis)
            p = (-b + dis_sqrt) / 2
            q = (-b - dis_sqrt) / 2
            if p.is_integer() and q.is_integer() and (p * q) % N == 0:
                p = p % N
                q = q % N
                if p > q:
                    return (p, q)
                else:
                    return (q, p)
e=172005065945326769176157335849432320425605083524943730546805772515111751580759726759492349719668775270727323745284785341119685198468883978645793770975366048506237371435027612758232099414404389043740306443065413069994232238075194102578269859784981454218948784071599231415554297361219709787507633404217550013282713899284609273532223781487419770338416653260109238572639243087280632577902857385265070736208291583497988891353312351322545840742380550393294960815728021248513046077985900158814037534487146730483099151396746751774427787635287611736111679074330407715700153025952858666841328055071403960165321273972935204988906850585454805923440635864200149694398767776539993952528995717480620593326867245714074205285828967234591508039849777840636255379730281105670496110061909219669860172557450779495125345533232776767292561378244884362014224844319802810586344516400297830227894063759083198761120293919537342405893653545157892446163
n=99075185389443078008327214328328747792385153883836599753096971412377366865826254033534293886034828804219037466246175526347014045811852531994537520303063113985486063022444972761276531422538694915030159420989401280012025249129111871649831185047820236417385693285461420040134313833571949090757635806658958193793
print(factor_rsa_wiener(n**3,e))    
# p**3 = 1244017062789857764422667689197770411561706061389715742852841131131435478039738844788314076541516819766126607314172841730975726749473298781835130842627454629568985724966925735905579282826322467200321805458818184179125514763621834851652092846169460275768772863952106838841006859603856275880383937805904493971997262155516186649395940112478889012377196708598220178020268381188803264308066063878770942584129304104857476445838035070537472243418121420612877337721035139
# q**3 = 781750817102250814081402150839349648838094352331200646064329593739249658509293014822407869754909590964961253627998562104967609046600602463761387625281775226114093766468854130062539304801906723482222402079346881907551622221610829587775870117982981382377420719340275829723435212262439715988059683115133464900926751096727854874698447640032293397116617936988359535830766353635342613807991926780460233344065075367609934736815239097217192394502104370100558611689435563

这里解出的是 \(p^{3}, q^{3}\) ，开根后即得p,q。

Crypto-反方向的密码 相思

Python
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
from Crypto.Util.number import *
import hashlib
from secrets import flag

def hash(x):
	return hashlib.sha256(x.encode()).digest()

  
  

def pad(message):
	return message + hash(str(len(message)))


m = bytes_to_long(pad(flag))
p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
e = 3
print(pow(m, e, n))
print(n)

# 120440199294949712392334113337541924034371176306546446428347114627162894108760435789068328282135879182130546564535108930827440004987170619301799710272329673259390065147556073101312748104743572369383346039000998822862286001416166288971531241789864076857299162050026949096919395896174243383291126202796610039053

# 143413213355903851638663645270518081058249439863120739973910994223793329606595495141951165221740599158773181585002460087410975579141155680671886930801733174300593785562287068287654547100320094291092508723488470015821072834947151827362715749438612812148855627557719115676595686347541785037035334177162406305243

拿到题目后可以发现padding是很容易爆破的,因此相当于m的低位已知，考虑使用一元CopperSmith攻击如下等式: \[(low_m+x)^{3}-c\equiv{0}\bmod {n}\] 我们要求x的低256bits都是0，因此实际上可以化归为

\[(low_m+x<<256)^{3}-c\equiv{0}\bmod{n}\]

然后使用monic方法化为首一多项式，即可套用CopperSmith攻击并缩小x的攻击范围。

事实上题目中还给出了flag的高位XYCTF{，因此构造最终exp如下：

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import hashlib
from Crypto.Util.number import *

def Copper(low_m, n, c, LEN):
	R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
	f = (x*2^256 + low_m + 97140404930171*2^(256+8*(LEN-6)))^3 - c
	f = f.monic()
	root = f.small_roots(X=2^(8*(LEN-6)),beta=0.5,epsilon=0.015)
	if(root):
		print('root =',long_to_bytes(int(root[0])))

def hash(x):
	return bytes_to_long(hashlib.sha256(x.encode()).digest())

  

n = 143413213355903851638663645270518081058249439863120739973910994223793329606595495141951165221740599158773181585002460087410975579141155680671886930801733174300593785562287068287654547100320094291092508723488470015821072834947151827362715749438612812148855627557719115676595686347541785037035334177162406305243

c = 120440199294949712392334113337541924034371176306546446428347114627162894108760435789068328282135879182130546564535108930827440004987170619301799710272329673259390065147556073101312748104743572369383346039000998822862286001416166288971531241789864076857299162050026949096919395896174243383291126202796610039053

for LEN in range(20,40):
	low_m = hash(str(LEN))
	Copper(low_m, n, c, LEN)
# root = b'!__d3ng__hu0__1@n__3h@n__Chu__!}'

（比赛中这一题踩了相当严重的坑...Sagemath的small_roots方法默认情况下 \(\varepsilon=\frac{\beta}{8}\) ，如果不调小的话是无法攻击成功的😓GPT给出的建议反而是调大 \(\varepsilon\) 导致白白浪费了两天的时间，所以只能说有疑问还是得看文档）

Crypto-happy_to_solve2

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import random
from Crypto.Util.number import *
from secrets import flag


def get_happy_prime():
    while 1:
        p = int("".join([random.choice("123") for _ in range(512)]))
        q = int("".join([random.choice("567") for _ in range(512)]))
        if isPrime(p) and isPrime(q):
            return (p,q)

m = bytes_to_long(flag)
p ,q= get_happy_prime()
n = p * q
e = 65537
print(n)
print(pow(m, e, n))
# 697906506747097082736076931509594586899561519277373830451275402914416296858960649459482027106166486723487162428522597262774248272216088755005277069446993003521270487750989061229071167729138628583207229945902389632065500739730301375338674342457656803764567184544685006193130563116558641331897204457729877920989968662546183628637193220770495938729301979912328865798266631957128761871326655572836258178871966196973138373358029531478246243442559418904559585334351259080578222274926069834941166567112522869638854253933559832822899069320370733424453856240903784235604251466010104012061821038897933884352804297256364409157501116832788696434711523621632436970698827611375698724661553712549209133526623456888111161142213830821361143023186927163314212097199831985368310770663850851571934739809387798422381702174820982531508641022827776262236373967579266271031713520262606203067411268482553539580686495739014567368858613520107678565628269250835478345171330669316220473129104495659093134763261751546990704365966783697780787341963138501
# 153383826085102296581238539677668696644156148059026868813759015106139131297135097831661048493079405226972222492151356105759235749502324303047037349410709021152255315429280760639113724345836532087970918453353723090554450581657930847674930226113840172368662838756446364482977092478979838209396761279326533419699056209983721842484996150025403009644653678928025861445324715419893797015875541525590135843027312322236085581571452084477262582966972702577136904385741443870527205640874446616413917231260133364227248928492574610248881137364204914001412269740461851747883355414968499272944590071623223603501698004227753335552646715567802825755799597955409228004284739743749531270833084850113574712041224896044525292591264637452797151098802604186311724597450780520140413704697374209653369969451501627583467893160412780732575085846467289134920886789952338174193202234175299652687560232593212131693456966318670843605238958724126368185289703563591477049105538528244632434869965333722691837462591128379816582723367039674028619947057144546

题目原型是osu!gaming CTF 2024的wysi-prime。p,q的十进制数位分别只能是1,2,3和5,6,7，直接构造p，q后dfs即可。

Python
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
from itertools import product
from Crypto.Util.number import long_to_bytes

n = 697906506747097082736076931509594586899561519277373830451275402914416296858960649459482027106166486723487162428522597262774248272216088755005277069446993003521270487750989061229071167729138628583207229945902389632065500739730301375338674342457656803764567184544685006193130563116558641331897204457729877920989968662546183628637193220770495938729301979912328865798266631957128761871326655572836258178871966196973138373358029531478246243442559418904559585334351259080578222274926069834941166567112522869638854253933559832822899069320370733424453856240903784235604251466010104012061821038897933884352804297256364409157501116832788696434711523621632436970698827611375698724661553712549209133526623456888111161142213830821361143023186927163314212097199831985368310770663850851571934739809387798422381702174820982531508641022827776262236373967579266271031713520262606203067411268482553539580686495739014567368858613520107678565628269250835478345171330669316220473129104495659093134763261751546990704365966783697780787341963138501
e = 65537
ciphertext = 153383826085102296581238539677668696644156148059026868813759015106139131297135097831661048493079405226972222492151356105759235749502324303047037349410709021152255315429280760639113724345836532087970918453353723090554450581657930847674930226113840172368662838756446364482977092478979838209396761279326533419699056209983721842484996150025403009644653678928025861445324715419893797015875541525590135843027312322236085581571452084477262582966972702577136904385741443870527205640874446616413917231260133364227248928492574610248881137364204914001412269740461851747883355414968499272944590071623223603501698004227753335552646715567802825755799597955409228004284739743749531270833084850113574712041224896044525292591264637452797151098802604186311724597450780520140413704697374209653369969451501627583467893160412780732575085846467289134920886789952338174193202234175299652687560232593212131693456966318670843605238958724126368185289703563591477049105538528244632434869965333722691837462591128379816582723367039674028619947057144546

def base10(ss):
    r = 0
    for x in ss[::-1]:
        r = r * 10 + x
    return r

def dfs(ps, qs, mod):
    if base10(ps) * base10(qs) == n:
        yield base10(ps), base10(qs)
        return
    for pp, qq in product((1,2,3), (5,6,7)):
        p = base10(ps + [pp])
        q = base10(qs + [qq])
        if p * q % mod == n % mod:
            yield from dfs(ps + [pp], qs + [qq], mod * 10)

p, q = next(dfs([], [], 1))
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(ciphertext, d, n)
print(long_to_bytes(m))
# XYCTF{7f4b2241951976ce5ef6df44503209059997e5085d1bc21f6bef4d9effb29fd0}

Crypto-factor3

Python
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
from Crypto.Util.number import *
import random

flag = b'XYCTF{*****}'
m = bytes_to_long(flag)
def gainPrime():
	while True:
		x = random.getrandbits(256)
		y = random.getrandbits(256)
	if y % 2 == 0:
		continue
	p = x ** 3 + 3 * y ** 3
	if p.bit_length() == 768 and p % 2 == 1 and isPrime(p):
		return p

p, q = gainPrime(), gainPrime()
N = p * q
phi = (p ** 2 + p + 1) * (q ** 2 + q + 1)
d = getPrime(320)
e = inverse(d, phi)
c = d**2^m

print(f"N: {N}")
print(f"e: {e}")
print(f"c: {c}")

  

N: 913125842482770239379848062277162627509794409924607555622246822717218133091223291889541294440266178282194506242444509803611492259403578922020590849630191477864719052980160940803309686069818208833547621252544423652489179493083138385424424384165228024273745733240109761707533778691158938848158094054261174692601673435971526522219273943464877956131040249169850420336023942653021547841666224446678539579529590840999008107782784268926145671962239929431694391039559247

e: 494518390582436635999115147756676313570637682518235195828939117782099618734167908630788943568232122157772909140885391963441876427590731524706959546524212914108888799081844320513851526790475333924396837458796755678072486028072639014677580265244176441153444956871730684233063789931539669072735599696830757690822185323538738397827461580678488181113667710378657058297572328491762536595872579603698945272140918157163640403488075948987156585480146162739943419183496337465468187233821931312507662218106713861638334075899266373256620752680354704533272722692596941861606161634082613228896420520465402725359166156632884432690715903666803067996854084671477445131853993177110154928274312496230096270510089973592664248613332000290545537840595645944390047611474888693558676781309912289044962293014118087259307560444929227407113819165713213046898243995956550944640168932947118400215917515277554126694376415569909534496134700668701465649939

c: 4450931337369461482106945992542133557585962894030505065110870389112565329875502952762182372926117037373210509516570958483606566274369840551132381128665744266165792377925899683228751870742727716

依然是e很大，考虑使用Wiener Attack——因为勒让德定理，我们知道只要保证对于 \(\phi(N)\) 的近似足够精确，连分数就可以覆盖到 \(\frac{k}{d}\) ，所以这里我们参照代码中 \(\phi(N)\) 的结构，构造exp如下：

Python
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
from Crypto.Util.number import *
from gmpy2 import *

e=494518390582436635999115147756676313570637682518235195828939117782099618734167908630788943568232122157772909140885391963441876427590731524706959546524212914108888799081844320513851526790475333924396837458796755678072486028072639014677580265244176441153444956871730684233063789931539669072735599696830757690822185323538738397827461580678488181113667710378657058297572328491762536595872579603698945272140918157163640403488075948987156585480146162739943419183496337465468187233821931312507662218106713861638334075899266373256620752680354704533272722692596941861606161634082613228896420520465402725359166156632884432690715903666803067996854084671477445131853993177110154928274312496230096270510089973592664248613332000290545537840595645944390047611474888693558676781309912289044962293014118087259307560444929227407113819165713213046898243995956550944640168932947118400215917515277554126694376415569909534496134700668701465649939
n=913125842482770239379848062277162627509794409924607555622246822717218133091223291889541294440266178282194506242444509803611492259403578922020590849630191477864719052980160940803309686069818208833547621252544423652489179493083138385424424384165228024273745733240109761707533778691158938848158094054261174692601673435971526522219273943464877956131040249169850420336023942653021547841666224446678539579529590840999008107782784268926145671962239929431694391039559247

class ContinuedFraction():
    def __init__(self, numerator, denumerator):
        self.numberlist = []  # number in continued fraction
        self.fractionlist = []  # the near fraction list
        self.GenerateNumberList(numerator, denumerator)
        self.GenerateFractionList()

    def GenerateNumberList(self, numerator, denumerator):
        while numerator != 1:
            quotient = numerator // denumerator
            remainder = numerator % denumerator
            self.numberlist.append(quotient)
            numerator = denumerator
            denumerator = remainder

    def GenerateFractionList(self):
        self.fractionlist.append([self.numberlist[0], 1])
        for i in range(1, len(self.numberlist)):
            numerator = self.numberlist[i]
            denumerator = 1
            for j in range(i):
                temp = numerator
                numerator = denumerator + numerator * self.numberlist[i - j - 1]
                denumerator = temp
            self.fractionlist.append([numerator, denumerator])

a = ContinuedFraction(e, n**2+2*n*iroot(n,2)[0]+n+iroot(n,2)[0]+1)
for k, d in a.fractionlist:
    if(isPrime(d) and d.bit_length()==320):
        print(d)

# d = 2109723047551375043305134722302342646596769444055829710618826161103186815230448177424794300667429

Crypto-Complex_dlp

Python
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
from Crypto.Util.number import *
from secrets import flag
class Complex:
    def __init__(self, re, im):
        self.re = re
        self.im = im

    def __mul__(self, c):
        re_ = self.re * c.re - self.im * c.im
        im_ = self.re * c.im + self.im * c.re
        return Complex(re_, im_)

    def __str__(self):
        if self.im == 0:
            return str(self.re)
        elif self.re == 0:
            if abs(self.im) == 1:
                return f"{'-' if self.im < 0 else ''}i"
            else:
                return f"{self.im}i"
        else:
            return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"


def complex_pow(c, exp, n):
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            result = result * c
            result.re = result.re % n
            result.im = result.im % n
        c = c * c
        c.re = c.re % n
        c.im = c.im % n
        exp >>= 1
    return result

flag = flag.strip(b"XYCTF{").strip(b"}")
p = 1127236854942215744482170859284245684922507818478439319428888584898927520579579027
g = Complex(3, 7)
x = bytes_to_long(flag)
print(complex_pow(g, x, p))
# 5699996596230726507553778181714315375600519769517892864468100565238657988087817 + 198037503897625840198829901785272602849546728822078622977599179234202360717671908i

复数域上的DLP。看到题目我的第一反应是把复数看作二维矩阵，这样就可以转化到实数域上的矩阵DLP，然后将矩阵变换为Jordan标准型就可以愉快地一维DLP了——但是实操后发现题目的复数对应的矩阵特征值有0，导致Jordan标准型并不容易求得。 其实在题目要求的离散对数的同余模等式两边取模长就可以很轻松地处理为实数域上的DLP，但是我一时没想到模N的完全剩余系对加法和乘法封闭，反而一直在考虑如何在扩域上继续尝试求解Jordan标准型。直到我开始考虑另一道Complex_RSA的时候我才想到取模长的方法——想到这里就迎刃而解,而此时距离我第一次尝试本题已经过去3天了。 exp如下：

Python
1
2
3
4
5
6
from Crypto.Util.number import *
g = 3^2+7^2
c = 5699996596230726507553778181714315375600519769517892864468100565238657988087817^2 + 198037503897625840198829901785272602849546728822078622977599179234202360717671908^2
p = 1127236854942215744482170859284245684922507818478439319428888584898927520579579027
print(long_to_bytes(discrete_log(mod(c,p),mod(g,p))))
# b'___c0mp13x_d1p_15_3@5y_f0r_y0u___'

Crypto-LCG_and_HNP

Python
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
from Crypto.Util.number import *
import random
from secrets import flag


class LCG:
    def __init__(self, seed, a, b, p):
        self.seed = seed
        self.a = a
        self.b = b
        self.p = p

    def next(self):
        self.seed = (self.seed * self.a + self.b) % self.p
        return self.seed >> (self.p.bit_length() - 8)


m = bytes_to_long(flag)
p = getPrime(128)
a = random.randint(1, p)
b = random.randint(1, p)
seed = random.randint(1, p)
out = []
lcg = LCG(seed, a, b, p)
for i in range(30):
    out.append(lcg.next())
key = ""
while 1:
    key += str(lcg.next())
    if int(key) >= m:
        break

with open("out.txt", "w") as f:
    f.write(f"p={p}\n")
    f.write(f"a={a}\n")
    f.write(f"b={b}\n")
    f.write(f"out={out}\n")
    f.write(f"c={int(key)^m}")

泄露了30轮的seed的高位。泄露的高位非常少，直觉告诉我是用不了CopperSmith的，遂研究了下格攻击。 罗列一下我们知道的信息。记每一轮中已知的高位为 \(h_i\) ，未知的低位为 \(l_i\) ，我们有 \[(h_i+l_i)\equiv (a*(h_{i-1}+l_{i-1})+b)\bmod p\] 然后递推一下： \[\begin{aligned} & \left(h_2+l_2\right) \equiv a *\left(h_1+l_1\right)+b(\bmod m) \\ & l_2 \equiv a * l_1+a * h_1+b-h_2(\bmod m) \\ & l_2 \equiv A_1 * l_1+B_1(\bmod m) \text { 【设 } A_1=a ; B_1=a * h_1+b-h_2 \text { 】 } \\ & l_3 \equiv a * l_2+a * h_2+b-h_3(\bmod m) \\ & l_3 \equiv a * A_1 * l_1+a * B_1+a * h_2+b-h_3(\bmod m) \\ & l_3 \equiv A_2 * l_1+B_2(\bmod m) \text { 【设 } A_2=a * A_1 ; B_2=a * B_1+a * h_2+b-h_3 \text { 】 }\end{aligned}\] 想恢复seed可以先考虑恢复 \(l_1\) ，我们需要一个线性组合后能组合出 \(l_1\) 的格基。 那么构造格M如下 \[M=\left[\begin{array}{cccccc}m & & & & & \\ & m & & & & \\ & & \ddots & & & \\ & & & m & & \\ A_1 & A_2 & \ldots & A_{29} & 1 & \\ B_1 & B_2 & \ldots & B_{29} & 0 & 2^{128}\end{array}\right]\] 对M进行LLL攻击，就有可能覆盖到一个形如 \([l_2,l_3,\dots,l_30,l_1,2^{128}]\) 的向量v（容易看出v在M的行向量构成的格内且v的长度并不很大）

取得 \(l_1\) 之后就可以恢复seed：

Python
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
p=183640370379099520304414468793633666661
a=36108041497607074474855679331694767924
b=65925932211985158779695144876342622462

h = [0, 34, 95, 100, 114, 16, 23, 17, 118, 115, 29, 73, 47, 12, 133, 78, 30, 30, 73, 87, 15, 85, 47, 20, 136, 6, 106, 74, 27, 116, 8]
for i in range(len(h)):
    h[i] <<= 120
A = [1]
B = [0]
for i in range(1, len(h)-1):
    A.append(a*A[i-1] % p)
    B.append((a*B[i-1]+a*h[i]+b-h[i+1]) % p)
A = A[1:]
B = B[1:]


M = matrix(ZZ, 31, 31)

for i in range(29):
    M[i, i] = p
    M[29, i] = A[i]
    M[30, i] = B[i]
    M[i, 29] = M[i, 30] = 0
M[29, 29] =  1
M[30, 30] = 2^128
M[29, 30]= 0


# print(M.LLL())
# 2^128 = 340282366920938463463374607431768211456
l1 = 624231359211481698145444691346758315
h1 = h[1]
s1 = l1+h1
#s1 = a*seed+b %p
seed = ((s1 - b)*inverse_mod(a,p))%p
print(seed)
# seed=98265113854859913689289076942864611315

Crypto-fakeRSA

Python
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
from Crypto.Util.number import *

flag = b'XYCTF{******}'
n = ZZ(bytes_to_long(flag))
p = getPrime(int(320))
print(p)

G = Zmod(p)

def function(X, Y, Z):
    def part(a, b, c):
        return vector([9 * a - 36 * c, 6 * a - 27 * c, b])
    def parts(n):
        Gx.<a, b, c> = G[]
        if n == 0: return vector([a, b, c])
        mid = parts(n // 2)
        result = mid(*mid)
        if n % 2 == 0: return result
        else: return part(*result)
    return parts(n)(X, Y, Z)

print(function(69, 48, 52))


#1849790472911267366045392456893126092698743308291512220657006129900961168811898822553602045875909
#(1431995965813617415860695748430644570118959991271395110995534704629241309597572003500157255135707, 1011565891130611736600822618382801465506651972373410962205810570075870804325974377971089090196019, 784497518859893244278116222363814433595961164446277297084989532659832474887622082585456138030246)

将矩阵处理成Jordan标准型即可。思路不难，主要是不了解题目中的代码写法技巧，最终通过几次实验推测出了题目要求。 实际上题目要求的是满足 \(A^{flag}\times\beta=\gamma\) 的flag值。

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
p = 1849790472911267366045392456893126092698743308291512220657006129900961168811898822553602045875909
A = [[9,0,-36],[6,0,-27],[0,1,0]]
n = 3
G = matrix(GF(p), n, n, A)
G_Jor, P = G.jordan_form(transformation=True)
print(G_Jor)
X=[69,48,52]
Y=[1431995965813617415860695748430644570118959991271395110995534704629241309597572003500157255135707,1011565891130611736600822618382801465506651972373410962205810570075870804325974377971089090196019,784497518859893244278116222363814433595961164446277297084989532659832474887622082585456138030246]
G_2=(~P*matrix(GF(p),3,1,X))
G_3=(~P*matrix(GF(p),3,1,Y))

x_2=GF(p)(G_2[1][0])
x_3=GF(p)(G_2[2][0])
y_2=GF(p)(G_3[1][0])
y_3=GF(p)(G_3[2][0])
a_1=y_3/x_3
a_2=a_1/GF(p)(3)
flag=(y_2-a_1*x_2)/(a_2*x_3) 
print(long_to_bytes(int(flag)))
# b'XYCTF{y0u_finally_f0und_t3h_s3cr3ts!!}'

Crypto-Random_rr

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *

from random import randint
flag=b'XYCTF{uuid}'
flag = bytes_to_long(flag)
n = 472993274721871037103726599805149366727531552333249750035977291933239067588481589544777397613192273114354221827196579379954069925604091911249655707080927769808587176515295614018992848517984372306879552247519117116110554431341268358177159108949791969262793325836353834899335531293329721598226413212541536002401507477776699642647348576111445702197483449777741566350285229621935507081895389023444249054515395783080003733803406382744631528246608154546123270319561514117323480441428953306734274538511770278887429407127143049023747710881993279361892937905382946820141513009017756811296722630617325141162244806884220212939955235410280899112731530527048274396186038160728562551536558223235783656985493518204710943916486379681906506757757594165379493317173050550893487151879681122510523721157284728808336110950008840684602353984682117748018347433177541603140491131603068512706893984834735290809952944273565203183330739252949245209529232254867201402656024997949207918675051941911990640248052951780195402390132237903538546705181463959793972284823588987652138458328270662652334799233015314673544813649692428544375538627858921763941533600553536579901589575693816746953261108022490849251974419402753031545629158199093099096735356165044275617408697
rr = 11898141078345200236264081467585899457224809417108457314508072413792599039332439547789237898270544336909458761754683941320649771736625000667170176071314483
def generate():
    fw = open("random", "w")
    for i in range(648):
        fw.write(str(random.getrandbits(32))+"\n")
    fw.close()
generate()
key = str(random.getrandbits(32))
key1= int(str(key)[0])
ks = [randint(0, rr**(i+key1-1)) for i in range(16)]
c1 = pow(sum(k*flag**i for i, k in enumerate(ks)), 127, n)
c2 = pow(flag, 65537, n)
ks = [pow(69, k+key, rr**(i+key1)) for i, k in enumerate(ks)]
print(f"{ks = }")
print(f"{c1 = }")
print(f"{c2 = }")
# key = 3168111950

Python内置的随机数发生器是MT19937，因此获取输出的624个32bit随机数就可以探明随机数发生器的内部状态从而预测随后所有的随机数序列。

此时拿到了key，接下来只要恢复中间使用的ks，再对前面两个式子做gcd就可以了。我不确定能否直接用randcrack预测ks去恢复，所以选择从最后一个式子里恢复ks，需要处理dlp。

最后一个式子的模数形式比较特别，可以用p-adic的discrete_log去求解dlp。感谢maple佬的blog，又学到了新的数学处理手法。

Python
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
from Crypto.Util.number import *
from random import randint
from tqdm import *

n = 472993274721871037103726599805149366727531552333249750035977291933239067588481589544777397613192273114354221827196579379954069925604091911249655707080927769808587176515295614018992848517984372306879552247519117116110554431341268358177159108949791969262793325836353834899335531293329721598226413212541536002401507477776699642647348576111445702197483449777741566350285229621935507081895389023444249054515395783080003733803406382744631528246608154546123270319561514117323480441428953306734274538511770278887429407127143049023747710881993279361892937905382946820141513009017756811296722630617325141162244806884220212939955235410280899112731530527048274396186038160728562551536558223235783656985493518204710943916486379681906506757757594165379493317173050550893487151879681122510523721157284728808336110950008840684602353984682117748018347433177541603140491131603068512706893984834735290809952944273565203183330739252949245209529232254867201402656024997949207918675051941911990640248052951780195402390132237903538546705181463959793972284823588987652138458328270662652334799233015314673544813649692428544375538627858921763941533600553536579901589575693816746953261108022490849251974419402753031545629158199093099096735356165044275617408697
rr = 11898141078345200236264081467585899457224809417108457314508072413792599039332439547789237898270544336909458761754683941320649771736625000667170176071314483
ks = [1462227062794249126369859823370329795444295554631867449122519463903085153603985900680740216206168716423777588580245877886440288748604020630699018542826979566965387039050150069523167528973701117587082189067128448763762233651697690088165126309640643249893980922783446939093480513501423929380273397400708296781344423099729594996935151205635124630966978346265570102760841188859706856157965455490428917432012469015925570881840242441646984344205989934223312311722527845, 17436088264981004997841810232705191434707487036117316568031039310756229463817709762330626096875057666532776781413031682988478368320631200639484646124749334955850093397553177978996330881043557698983399584498223222105144624884205328876488334329130830465297477669138121963831402080876078357077714205039964108868193841782271495425644463200232523492344001660692840819160127541347575190224749912289543698786833926857916729347030739521501971908837887266088602825603179428932500122868635833564921115729380769315969449959847532694279060981180556955413680421245680949817931938812637093078177255366095925596232172597647804659446, 169559415577702492912881115171844374594897133030580223300760597578879930554761809414648409965790290108683744070236827542547112767931390381215817208191241194452401715396697138137182840759511035487717013487364495797652031544286820278750675326239062595892448739046788242584477837603604028584783800711126256213550041835365566067529075264741159242623075137208552904103323636912832758118607742414554050834861661347524996361121876885982545956793412777613516967651789645670837406737788560923095674100190720996844931263803247711890541497769408802573382496173181275896304033554412089516486158308042512557770316390458745235174270820619821158359708588836275104941171089532593072639298996037834372691067497283819036389853616602440038642702961597540965107104661813887585271108258467582, 353291124480685802122760873619558181197925748758526501461956322344713145481696018545548833112663130052221102526199589136442461136617134139228771440873303781403752812631064169836368616974931324935659661616432397250323791027357698736360780111349622044193849460721756463896782586060025792712427344165223388631274105033257953386232975622550466772244070538660725769821337872161112606157590652531598571409049763994992112562965984307203582687185746063109802744989804265169651236595150092278455325980064053498109201539606445526852506504951020231421164201055246981085535835484260199043182412639045612970769228962343363308833437852540654614315024696428638587640053405690902605225272716392141318356689485996722112797193445203157167283359129296847476836010747322296658815494204920904679373943240361056289263055689989853602794079068762252790541020355479732830748629340531275553956346072236216251442369981439899969148055895199797337493316, 15179303239962972288090709923258186951958171456436855682777477692171617505348532247047242658368307257431505429176030938743052282481669819891838891541215477308429612423006023438195430836574000543742809228546430000091179899316856488547218901706415026288318088205302049807334703045024896255849147262301854988225565498235577522563864689394270282449494777293613090615435735306391538191861818216934248371120219493426168505800995544058108910908179783162033445093246274431640068273309491502382851514221655427718436104350319852529981208352415296770552441024164515192550794244703092453886081781025084452892498434750021938722777929757172650087934502975720197724550995892550276217204632074271485875928952811717435969392225184804651569530492559664256153442664382496786312755369567453642365570522203867667064702855064117777248996452839510530112258447365219153330364325480082364302480271013963043808407808026617207478317657335771085499907980998058580300198585325142615450209133083897393551483195987009899057506802305527262738968147264513649676062280043385168050292062437784343481003416836360329, 104314025112423274137233712089887942843544143270638359212971052274128269239471444157192816218808079846611202214084249469627150795706839411653429768726632207799788014550224322493762432406192490957609286668132611092680358220234900446241372261756133560546933898911405464919838498505955386741631220042481687693247513434548162014035705016381807652211578605534090062861927303094187322830394428003720849259122728764020582018050036758593860110512593538102856625101436236685192028585785277359733026956010177985114124809725271266235518425292300207754430093643901348424098723963444965623388363705031341005891153453971749807676104809873756494951980451522602316873491452723525098105304097227244362803315664527459814806074055296007282695273078439762481309737546526713550861490435485841202437290236273820499123268038887900937637888673263245804550050225236201356152470642062093953920448272200600863673489805148880500648543349624355627609552339313652249538084845763001317045938369921466480729660920730443079784782692236767617383867121962635468379178835807692901877341892412552450901873955386866840632105626000662355131829735238309392134598804443268332424263236647235664725585301289855948091012922650578186399459695913486992557308313400835129903295472, 4343840077241661846268935044680587301922553038527003445558194299629246437770144538620877381238906692028249854972040151877119476048349008469539245051594012783879085195059417005760769680951795800991838280644405366143799108863486512837967757384337716585187068737628553329955797218927948991807398217726158890043209786493155396314350961622153611660511283644242391666275370968989005241503828383899735010790229677725184129352599961733027673035747501574385230757945287667652891580150423322079486963198642876365246595747082980621374167798723795545482544349625906607527172146616536749758514128592808962495027958181278487153055495228539745094046329616245517171769643273537017191271548980274132500153620316208900769372928143878394476769232210760910446165114726727346459588121745157883051053172477968719246421056145184230282266693069367823549866560055702512612897427682313787206166585448900167833527105055197710187205451619052189815465364328045147326853372540758120163941655690535948810941959546749120505801600233689886118090477238999842117697450804442045413189286597419777550661497797676126492038567180797469427287581550651480006192621101368344597554817693129617367587265330631435038864934907358392135820575836786357021588185619258824320681971817694708190104082162236078675439624893099574428154391060852816948575281188326664739692492957173855447270784701674993602965772572705572236661284175838750276, 33232188464261655563179500532261332740673268011927651630320348613939386668276216461522230721806580297413734568274970935459682942632905228878109266134442095157849521426423087852309281434787500339731212538950209119002423508188676963099974651225610558899243654721531277558550493327350452829753190227897808568073543678269898207509403265336445740620238191925668387207191570780928973245140015529624527394339504110166219539275461482559378890285009329265175900569903390034280071197123026951890243045598372762777194271518734277493717862068019851753397533687634966545727487904367806612431117675184708993348444665119927999157611733751268566184403876833185469516137451908620375918418813671459671015165252098516843945558856771686910403711604755349007547521956309000907909321344073563215005461926587582952949359614987174889724241132421264477252674765866525922832869625858802619129860030857164098812287559445509108640318149480136605636205337149260208047286736509632239281682602528730811378780178290081953095940304361016309200367801327179710042344212586894803008913891990437132132154254944818304511848018157641226316486358816741537666493766664969385708412966038685156129617636758707978377511764106375364810771789547724915964400747168477073598611228354770053945278770974453529085850122110633659583211141893829685722257824029598188511772787791704436267726687275674340238387313917520001746093685584958790950657401396602667943161883455431709467342749040393470692558305012064228847045344065542300917341497880086951027085764240682050347639183710265265174608568581, 444779920211605528457399163778798302264962864500581879449061229089239557061028178632115126869104894859226622560444516783454331855728643653865605416497057611218192216553619406318123596530221714071025603907837449777716507496519968322248412164964314856154515711925650355367893348523307966596574094376371033024957143232394835676102505384939927310874548633276763683911796494980021115548783946752097475837673376331732397502955289357489918575906500096508563791334858578196054364575510262549227364768636710590870090347574179185730720326430135005745433229085504757196383182089273767249820043995239845148428050144582143617569531992315827635029452027206779513658792594533984308575410806115812027902735755703109725290139038156207495514857551309765646867686889984088386887429907974093388131425361751082756577755914020028802552784669428525627343682049455098817841762010840270014859394810253384211716918791183946657609375093285440242734069437770190190813413589772304378568548089845839766313942144795085022405996403115650259032402819679689834193687730312737088900035185810701229565183457677574983602078058685068344436316207621825755389502057132478973466812474466361405511892936227130460055637816125221120263639554189413490859455156262013094121152711225170530206766029467454109467305401401846460468093777715624211347060013862325763649394914935407437210178038317290293919361423759769343159231891689139655490453425886071219512994202371899835337440763173124439640514220811318874946924703189200447691715469272243497270647235873464259786562267062001636730421451659510209634262617060501219332722128011149714434675517928550498574212874429311999930642838137400894349532393752915440919307741932816838690395606129263401130, 7602657349299010857087412189053904610014835470031847851883656349200899897074907434799227128793882909815738193292999732731888978083302895341590290406257165745016960805038897127665671830799203429105439046544232550057709873279272509500788880966204623301536523568757142788616714342396835348896652095993273120352216558215593487864297089604696564960677302089801831232789103069985778444311388865194583877243016764859298874263207514989622286824950955134805871171552294553075628653085978727480483509447782713038101591216015129434695340034230885326874585545666722007375755217543974918948104058213162198622707539613172458718150254646150294432030411829433714905174414616923009739539225989262351006787760054622647363592552091025438151580366414103445836645659713990402360169403016672502089016488614454624878982485618028646781661937237681350359808210590576468884385972827124881157769458685969004277110291444619196405001534224888721294643753150729204059438079951844348808565383170513314781032113884141668626087014977362543472261224194658720773278314480331562064521903562028929772245246023044918780612944818960063465178711539798601604042918647125400052489298307932451350609822767956789584605169244797260390089496546479886501231620453426723358141585623383732719446553408376039010770786422589076208046136110959032740167791347231308499822725649244370210435390174503003095419480360405606956944343844737311175070859345840892142099028930344584283138344997292575870767828146422997758547138227712103360348602516685557024226449188853398358276132193649977284120887692434143592539192811494203655959855535383027295793357853938962196086241223840647731695273486642076372427955673144634441281545597498351950046381851656586528708237353884336502685431879297832928729212632646314921058694911651155140211366665485536218812420299903213130769617228499207211355651173115373832276702819917, 84264285782731568162877315100957489042921709978064128681351268312087746569277269486245900009777400169887830271723552358655565447593550146955011831050100818215000508691318113595184405583164046098487595114378660143656870174865126611342542042359190092909153954755450866325242940723529598062222899187359928557844177883049590925651498994463750219753412624841866695746278533280094878847475236701017015819139013181859456526369446971330754812310385508018904191327621492159168820784532796330689921699298448074204812463376397381282323119448865011664447416851175564248969000702694318145335362835482058897168517488161967391334177372697703315388808719141005307789457461912851355132825731054246686755461163054191160703614564317990818604434605413936738139726767800963911739280012496306857434637923374480459728565199969705867209254398601345461449150134011614149873500167983320745189254670021733091744167981087834156449345560645456017335407633688885028006913440590401180339340613693275890333649989994343631183579024732181147263210054753733928915807504572214832934722959416211618552311628264441740006263506928574652072303741962304773970001278403931114817733924209744938397932123215729579525983133592585604481836441256004482294972680139829929612014077833332681473454850703790455910234390018139844986977475904490461864701830158535403553678623812164036013559496102371103327886019446045373299153105962515417300141416878319759519389540938146354852993808369804508844242989928184577744636058484630309125804687764207122455205953467056765480238519667329086954915863584834116160428194118255018588109352554311335461224660821734294806261011545470878130619510996578906865491369421849868743287382195889612248362671647411387033198694140556943015854769888065336118318462104334038850907108272666824691321243254155599118711741561988645703051401242347980726593263524750481061186510425684386819376145632247818469939222055128225225680599982324030716227856712465076900465158037591919290264095582887285060549164180202017670962738795868581166749, 86875322477430958180737121081750310417552562568937472111462285494068077044224883282734365519155742412567742579384640688864318774506290688726649362821127869025823526558190891391368772700819437828837459806248988365684079824273784568628472269256575474035185709547347651993828702097549741334374364807937523943589572886556418546138161477442285095981598112603569341799645993286627117775387075506854483018231019196901947857611575841702330988975450215180893407629689116208362182111134678579611569697431926172879405158644545853375597102146456828749129737059398592090470207221930164907529449914731078780527501106015075222892079609819142004929517650214077829963858911041047626149998836986070729125260139028680402532903187215589441565748744974914634384575746331436503499349361029226889115930910170650991829637232214683931349631413139076186550993209917767820494311457665926894684877305970805039969582722809409057884485422798810134923124618610122219627418825157655548696504402394251875250216209088386596839289090205455355830326463145513637140192806838161127837601889645337809125003492037067870634529636104813436961659217629590299188696646907180990318511335172435862882285594729483438730028804396906143686407113299921602779063868388165847291926366314379673487291861917979020712234162374569910970226596823115360201748087179946804305525598669650976080327154187180758461602309422875784085236535569730334773176739598656049048170461638432200220436248431274572686422522379720157015816524948018313551155878299198696729645812418550240418562460968434597425565276688472550697127256796390159826046074365566403255645195972270118195562599397495009632518911353576570958767630794735474661250425256764192128158589944999335063602995713281667673220224066976800182326927451684095263096450327503087613798593569273550869670074927576509772147487168451681956168877773772760560498198909642263656809675890678191288443016329637625633073593034921242604872479828009991046383160941673220022936977188891725330716968754725864852252393788824966035242075304806536640145214252474418277831012513594308952183851343958969850677298051187040013011759593833806518361877966381266531975488250988830914527197364101, 12512746540434506671622137154487272479684301796741804852784466276118318939301642459078381853231258719083628458347218300308117654564963998239910113998177176145693597297093613404613373790353962391872079537076763899617842035568892498763955045462691124784114867824842208398619557012590225397311703746359043524766454656517843775988786861851276648768563329960194176509861369794873055457605566481169738163028805838726245153501259733517437071411250664053003146288253452678594410757071147688309902950173685554263072263315677468119998237322488014934897657616287531839226555887811741614460852594517274931125186552830901907056814814364537922270306184144816527619368461860735029130410855453249885989873125086119053183377748071520492963343904276809950936122217011456932719335145019854799217844683275916251254411759723367406995497382110560047670724344385060716483035502136838796674166618447372318994376720742190789098253575402714952812659933854943786548064525033834188130429821475033759906784746466100360319090217901641302494652036828536156345999295944207311903908579168517843644212223034389569172093947663228241575508427027088548956357607118349234005954956185598117597472201788146015733232957686350215358611056864787006128071212201859644019363381882103578216957110324101802774053325622415064181605199128828290427210592657379567354577480538732546950307498243047731412124485919082022649710227773753299708907420377570860905912772090222116049362619789689065827376289781835174416236170541192824551498867290178284835242340226614885213085297034699023207334693204443834177633980478287732765627349487390651101805889417613406850491982522373652059294595205056982377527663490663856624298132703619405155068989422975395069609806200717991260670611916599446743505075260280455301127997860556855773088502432536965641419712974469765402344889497455850368646912720700712406187148014080534412935202873400913358906387215078903911309526903672652336133008199048483053203616435313691633319058270312626100467991257715266040851461069620411861732977165671779365665772314236597023035647614424138241559672376552675319414807273488451981119673616629216737966281726964723616994609707694019677386869057732381647985259361201436431774138127924914503212637589804812882400769493547225221791707699401249315407469433861394473469478007958068015775562155959407640271035, 8708772086314275150137563047822324600135662221530061604490923488781196834561031216119766508710300439592586098337033648172158478037428422016638015261006654452028325941079516640378163094114359263904509663697697446450829644183714138570138053299079111099978730162273301464139950471846002885912898793623780911069208262571511170830772519224286142285588233365329150597172851602037056835267890472296625561911616145092230018104567552026345101742597268103327522556484095066615892886223565058357363680363535631942614863586767642475310674520180258183502370763782154430809207907408245635540513317210636762204031484268471851140728225200408406477879491421034411771595550287534644492458168126531514396470443302572852034873709549055869547530655956369042654261333529517571359153739442787262860093740661118519451621018435524810049086927689546375333874177211297659402716374232772574921960004351227056283357373573456626553641214672035447396850649297539465342595024155246359918811294045883925114447310675847751632815638598802360958589640694941216735143869543493813631906641446867757344570346832228628926669569641235390679032157550781745139542693343976899951858605641387961226781860479580622706408871423958897669045935376111333791269969907893321496309204776813332733513920276388085041994007557204267637656364577970814757016037506402807507663275686948184629913418881333357288030576799576733495401166943446587740185387874828772125373722620767643073868513719861621143440955960613060364895903611801265463530162601221089578458698304546551933625165213065587195349408747310822367615685148092899114446129224352042234315865770543693346677200293484242331181710417082363209828386909100998998888639900536186820795298321286714108461675397032864388542110213210827364423163325349547591341479159200210127489502278231430650721377665744894470461939053982524090875574789651853588962397719426413835176058841208314719781852021952695059793831541054574871680705012400864629090745303863048197498118155019461006670125137061405464976922277176269488571398394629261276128473896794210626729855368774199524936087915252643083350806653978162434973122894687105799198912067140963567030871513363285565713597188757003358857092315759659368775879258759880919191003344516366609757523241375325301693755640462733509474415702644254270875174073203609818099246161951619877073996976627155333499346477458629618081495288947853190429723736471113704267980053978389993182103772852202476116179106939188158462552458652108321980165243577989, 600670032931697501164308145888014197492570434182237560158362504047400318743985557099146474331125213856150404793770533457208418057346330441677143608228832189090853249915025345091440471977572520377721353552421230209210878714408072035504562082229497678931477951277415656323261513473676851714174232119110952631892409156281805902829840067360861715042158260954202580085062540987292060373485291126788640037325353253582263912429148264582730931166497761524857603024286533377786733733569503217095911870554634981195459051734711257551318783862993538532061516918229242512785148483203666879172553287417202171558010581931339490420944579378230441427075256586289381172933294401587550551868745979621899498946185449116142910195187754784531077545817750030440559239594200572501795505647816820925940699189807911408560014741609936565474163109147615538288077368434085501495660339791023107653834631734799739401195331082524762689829404043854362928974818455326969933539941993127168162613893714556812406931262398133232164550840686759286879519200522303631666340760585955445333243578595829239195345013932609791828394260147075352440178009791316103080071026057431465935054583990885807722362958473601534263884483797804520563080119843829936517581710475224995487406412704094626227661853966476374689727423649602092208013642493973696165953898208578723428386172214500367650457610332358123936218429284291631085293746168516063238704669713654100448973473107547290896972051178145687724778934856166935295480879225802399479077346027327314330339492654814903821691676533513420126315351413897998334933276481425781316933061160336396245725800475529909180155168951048807842776329370733724945778641650510054608686950632422179126803289332576361096595524712081770649946303450447653874189205658344800236157548893404541684986435295108661952487239009695950009496079506381196591935645314690427759872790821975631216132209928929354223296595481820239561580620161078572691513920025180731146443551810374070796784563832569069540610771634802811283644303060748631402280436293606074124845116433560780371614622560694771710506136314406382632695962443912413902134325317328060708301892967007571381754948796760722223816096248930178117187568894324829422197591098693433015570587292619159140504205675563120383480457405492676888099039922054652604691220210221980510833810667665873272200431377635693722100801416566512889633584494029920362450447581541351127279435858414431885445382278645820452301854483001535497815948240428726604118517960146521827602352741617814422650606656703172306618878677224079000419335204662784233051630328692085443396990051814696765167700904476881356841198817297213897315038, 16802200282185468546709956092597774740677661549186109526956115242473121883967931163131646187704424819015848998645400207990914089013740921040117435052153841770979793783160919446710908856026577921822303736856837341534046856200378566367573847587481842033197417244157615430123019293064402352517730950287717412467467865654183120580805017956735624709774788608215096623799957840473617022005811932787883583498153009349216019520591315741115282954188920266939008472763372248700697866120997747281838993436471646694877967037584713292557154069090849429661358360669249141411401563354311865086301325223201338603660585063135197133579821848197298915130533944228373462645556131332664180638837298172981687095294316288287474397100963640912775346092923086826604630609655904543259441330900502644107449819662176812660489691326329405408557397950478553867742426469439899689820127149948041436799921133103166748621889384866646157787616184868217116001323368301878471584588973680319019047080248726830275150507574175166679909676797693790108124055103246880427997452475987304179562314626608037471679968401792562140826537740199515244895441348559877458197387323837253170889409923432265627983693113613925422770696270052261532295092167140744798998616784973950454662490861686686088097664631333759768155114942862532519746034900590201459240562835926241941887144381202153705241903628166984657567323072355632922438685555213721062141830979317585407175747781177680148572415131107678588710821046069788978524572240303124373546329950302755883009871688891897763945611072996185025629828607383345003927868697847599452468428107980542821610672736393669832455756995387290606284835293616942665638848969022879828703775592928644725559259945529304050112289143946763124018433851771902626785481385869955110673938215223622863613678412315324306153440766902206001688838913230436350171971289551619865068519200736270652193304810653015371888594169504114520468603987418351580463962583790787745908309177358777801427510313483309516938585851407176405272323275406264541269998648558076115710572739949113174179063104037408892800012305672645293826133157192205750448664938758484140537975600112928783731131731160554472918720908169457539285420601699964488745103603485765360051670848460168635009550254451173622724686795853530317243637913985666214527422655976232855531815124677038149005239212580323707459514903671850604938595975480625971419288321333482646971954799306704972896590507695031753549266109898497496991269990475759448688581247659517684220339086012734812415537965920455360852739093844076811759759173303373454199660054006117215442176739570999154607921395801738324345694513716171731402600767074759488172948500119306978382635362273371756452203795420879806823382694171689272398990752964743539328906992588078386684970091097095002524822271111900103]
c1 = 363788646363430038957594782766177313516930410013028761096125449525352900311987342432332707389678725464245570305442656091083147693929633253905472222223119105496597576680892700795690978029583841539541374381306488238546636925041645743837795052980068923686651284191050257037214462852085566417008362992641640639862428112228493556483476170926590723955399664612288121797929235261679990399185352352544286959163976884867676390120340127790862048627561021372508575978346406322179713972665443056495181281314029605259955375166316993493231524529034376084736285226932730392410446057610167031627686895389188357267336304140707750661551754532703726810046229782522509583068679068266026330534604220136448779670239303044844594369863033342562614954908580980797071779438702134548396966154384817728024762723793272143181635940946334888845065820620182286804643281323447179363272699368386379953273502775010659085362938622805062632668642982294663858335244396163857338508227323801751681995976156487970781553331051080424612021398707159108830544940316009623664909356175231889874464365926612039289520439021685692867423908585449824825323639525381296026274686349117857285659369998795553471936274903352010099265109629071229881541531543477669574187083631324785284254322
c2 = 408184822131518156560324293475775283916865330287271026174896526350123511666895281956297307670862799857291692050125369779347444868678108319280695068081984027607535529170555137883873801205238074937937942433229726545428621408643537931796698659949811571615439710035675674461716185346635792745790874541046465708604310892716226150611709100803537856333225160587696062166931121471905405372834167788843039506170303362597157739646424300148724721973787617390725217064863182798206515059995025139870581046657455818390197378360718268577414540468313327849155326977072599665355467818781585456624519602844435476444300792593181233725708809256956289242348798772583396011536497809799519543692707372931861510836406771810916160714625641110048105945905698555148489134800297890071585166636593108936219686471652288476546797128397632673886639590166634763861905600305344338904568157848336645918449260801970498973364463883003344546391045331665345600454985730993059182020185438557159428617482719829271986950641093353253897984198499501965120625507862855814501340943227107501804839977088104677785444986972836309787440401273632064782837200999263612507784233705263545942160822597103292282242714942650302979883274746718391358487897324158260429570732440514025523470979
final = []

#part1 dlog by p-adic
for i in trange(16):
    R = Zp(rr, prec=i+3)
    x = (R(ks[i]).log() / R(69).log()).lift()
    final.append(x-3168111950)



#part2 HGCD
def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x^m)
    b_top, b_bot = b.quo_rem(x^m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x^(m // 2))
    e_top, e_bot = e.quo_rem(x^(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11
    
def GCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)

PR.<x> = PolynomialRing(Zmod(n))
f1 = sum(k*x**i for i, k in enumerate(final))^((1<<7)-1) - c1
f2 = x^((1<<16)+1) - c2
f2 = f2 % f1
res = GCD(f1,f2)

m = -res.monic().coefficients()[0]
flag = long_to_bytes(int(m))
print(flag)

Re-砸核桃

本题纯纯的非预期。

首先查壳发现是北斗壳，上传VT发现首次上传时间是2019年。考虑到这还是个在CTF比赛里出现的crackme，所以很可能是之前某次比赛的题目。以"北斗+crackme"为关键词检索得到这篇文章

好了，这下就不用手动脱壳了，很容易吧（

Re-今夕是何年

不知道是什么架构的可执行文件，扔VT上看一看发现是Loongarch. 其实直接查看链接的库也能发现是Loongarch。

参照这篇文章配置QEMU环境，运行后获得flag。

Misc-TCPL

同样的手法，识别出是RISC-V架构的可执行文件，配置QEMU环境运行即得。

环境配置方法

Misc-ZIP神之套

经典明文攻击，没什么可说的。

Misc-美妙的歌声

频谱图里藏有密码，拿去DeepSound解密即可。

*Crypto-反方向的密码 情难

啥比题目，flag长度足足有73字节，爆破的范围没覆盖到导致赛场上没解出来。本身是很显然的二元CopperSmith。

python
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
N = 26278624299187148406559772770865336226934633734285979741424867540828670397865189685966828527168795621543490979182417570078991930822041468539855006585233692884235331084907340302530060261742100702658312435180527335101284800616106884692498603300926488358017928867672861988448488439356448543527810620591324774111321619391264173779312033252573140028630441135269056099074531502841259940379636699304810677716177080486265721322966814104627525953974143476452058638927511594884002185219080847495835727300670028011001853179659250270200020884333850083063514830095064730932997593930711871108436386821290545084229347398808220810263
c = 3335299537518434350008670067273514020883265809787658909900831303201069228111667477512288715627313377374377192065531931991830331266940281529429758933125645068623703704431432931062515459304407129764836169638068667723468109909932687335727824459807903558617156661138991973933280805156893120951135488168923425258119689993859896540097318197048436676318334502053269738046279338047497258783747007084564814994803144049365117574904704816542523015746396519693505167963245600047742456478545640334467678554748227823020862550712083249012329745708139070338928730226897923885785783461594034339595106377701306570280371612953393097739

import itertools
import hashlib
from Crypto.Util.number import *
def small_roots(f, bounds, m, d=None):
    if not d:
        d = f.degree()
 
    R = f.base_ring()
    N = R.cardinality()
    
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
 
    G = Sequence([], f.parent())
    for i in range(m+1):
        base = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
 
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
 
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
 
    B = B.dense_matrix().LLL()
 
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)
 
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B*monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

def hash(x):
    return bytes_to_long(hashlib.sha512(x.encode()).digest() * 2)

def boneh_durfee():
    print('Boneh Durfee')
    P.<x,y> = PolynomialRing(Zmod(N))
    for LEN in range(65,80):
        pad_len = hash(str(LEN)).bit_length()
        f=(y + hash(str(LEN)) * 2^(8 * (LEN-LEN//2)) + x*(2^(pad_len + 8 * (LEN//2))))^2-c
        print(small_roots(f, bounds = (2^(8*(LEN//2)),2^(8*(LEN-LEN//2))), m=1, d=4))
    


if __name__ == '__main__':
    boneh_durfee()

Writeups
#CTF #Crypto
2024 XYCTF 部分题解
https://eupho.me/66c38848.html
作者
Lambert Swizzer
发布于
2024年5月2日
许可协议