2023-极客大挑战-wp-crypto

赛题记录

Week 1

SignIn

题目描述：

Bibo...Hello! 你好! こんにちは! Привет!
5359437b48656c6c6f5f576f726c645f43727970746f5f6269626f6269626f7d…  Hmm... Something goes wrong with my grettings bot.

十六进制解码即可。

proof_of_work

题目描述：

nc 59.110.20.54:5526 Build your own function to solve proof_of_work!

确实是过个proof就送。

exp：

from Crypto.Util.number import *
from pwn import *
from tqdm import *
from hashlib import sha256
from base64 import b64decode,b64encode

#context.log_level = 'debug'

def proof_of_work():
	table = string.digits + string.ascii_letters
	temp = r.recvuntil(b"sha256(XXXX+")
	temp = r.recvline()
	suffix = temp[:16].decode()
	hex1 = temp[20:].strip().decode()
	for i in tqdm(table):
		for j in table:
			for k in table:
				for m in table:
					temp1 = i+j+k+m
					if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
						r.sendline(temp1.encode())
						return

r = remote("59.110.20.54", 5526)
proof_of_work()
r.recvline()
print(r.recvline())

#SYC{st3p_1nt0_1nter4ctive_Crypt0graphy}

SimpleRSA

题目描述：

So simple RSA! Wait... Are you kidding me? https://en.wikipedia.org/wiki/RSA_(cryptosystem) 
hint: flag<p

题目：

import gmpy2
from Crypto.Util.number import * 
flag = b"SYC{Al3XEI_FAKE_FLAG}"
assert len(flag) == 35
p,q = [getPrime(2048) for _ in "__"] 
n = p*q 
e = 65537 
c = gmpy2.powmod(bytes_to_long(flag),e,n) 
print(p) 
print(c)
#24724324630507415330944861660078769085865178656494256140070836181271808964994457686409910764936630391300708451701526900994412268365698217113884698394658886249353179639767806926527103624836198494439742123128823109527320850165486500517304731554371680236789357527395416607541627295126502440202040826686102479225702795427693781581584928770373613126894936500089282093366117940069743670997994742595407158340397268147325612840109162997306902492023078425623839297511182053658542877738887677835528624045235391227122453939459585542485427063193993069301141720316104612551340923656979591045138487394366671477460626997125944456537
#510345661718450375632304764819724223824018609359964259503762283253350010161515190912152623604019093266967095847334388281390406831587663253164256543905694021952211220652820225527413861208452760215767828927039893435528572148282529198773772864255061213208279999011194952146362748485103032149806538140693537361755210176698895104708379400806511907719904867068865970241208806615061055047254026118016836750283966478103987375361826198930529462261013324904522014804502582865716441828895047550041401172127129749969507853355531197814919603963664646220505672302543085959372679395717892060245461464861507164276442140407308832537707450729432224150754603518526288767105682399190438680085925078051459448618725871249563011864525585870188123725554411655044152994826056900502298772802133526591794328224932405680583757307064395792317383571866619582974377344736930271554160701478385763426091091686496788999588340419226785217028504684542197970387916262126278955278523452903043316452825738030645100271595942652498852506660789605846309602343932245435421425673058238785509280366229754404949219663043627431437755087855502139890639468481922788973821783957766433857773771229298328019250652625289700950165414584983487319078090573179470893450632419467111117341472

用p解密就好。

exp：

from Crypto.Util.number import * 

p = 24724324630507415330944861660078769085865178656494256140070836181271808964994457686409910764936630391300708451701526900994412268365698217113884698394658886249353179639767806926527103624836198494439742123128823109527320850165486500517304731554371680236789357527395416607541627295126502440202040826686102479225702795427693781581584928770373613126894936500089282093366117940069743670997994742595407158340397268147325612840109162997306902492023078425623839297511182053658542877738887677835528624045235391227122453939459585542485427063193993069301141720316104612551340923656979591045138487394366671477460626997125944456537
c = 510345661718450375632304764819724223824018609359964259503762283253350010161515190912152623604019093266967095847334388281390406831587663253164256543905694021952211220652820225527413861208452760215767828927039893435528572148282529198773772864255061213208279999011194952146362748485103032149806538140693537361755210176698895104708379400806511907719904867068865970241208806615061055047254026118016836750283966478103987375361826198930529462261013324904522014804502582865716441828895047550041401172127129749969507853355531197814919603963664646220505672302543085959372679395717892060245461464861507164276442140407308832537707450729432224150754603518526288767105682399190438680085925078051459448618725871249563011864525585870188123725554411655044152994826056900502298772802133526591794328224932405680583757307064395792317383571866619582974377344736930271554160701478385763426091091686496788999588340419226785217028504684542197970387916262126278955278523452903043316452825738030645100271595942652498852506660789605846309602343932245435421425673058238785509280366229754404949219663043627431437755087855502139890639468481922788973821783957766433857773771229298328019250652625289700950165414584983487319078090573179470893450632419467111117341472
e = 65537
d = inverse(e,p-1)
print(long_to_bytes(pow(c,d,p)))

#SYC{Just_a_s1mple_modular_equation}

OTPTwice

题目描述：

I invented a new symmetric cryptosystem, and I believe you will never break it!

题目：

from pwn import xor 
from os import urandom 
flag = b"SYC{Al3XEI_FAKE_FLAG}" 

# step0: key generation & distribution
def s0(msg): 
    k1,k2 = [urandom(len(msg)) for _ in "__"] 
    return k1,k2 

#  

# step1: Alice encrypt M, and send it to Bob
def s1(msg,k1):
    c1 = xor(msg,k1)
    return c1 

# step2: Bob encrypt c1, and send it to Alice 
def s2(msg,k2):
    c2 = xor(msg,k2) 
    return c2 

# step3: Alice decrypt c2, and send it to Bob.
def s3(msg,k1):
    c3 = xor(msg,k1)
    return c3 

# step4: Bob decrypt c3, get M.
def s4(msg,k2):
    m_ = xor(msg,k2) 
    return m_ 


def encrypt(msg,k1,k2): 
    c1 = s1(msg,k1) 
    c2 = s2(c1,k2) 
    c3 = s3(c2,k1)
    m_ = s4(c3,k2) 
    assert msg == m_

# Here's what hacker Eve got:
def encrypt_(msg,k1,k2):
    c1 = s1(msg,k1) 
    c2 = s2(c1,k2) 
    c3 = s3(c2,k1)
    m_ = s4(c3,k2) 
    if HACK == True:
        print(c1) 
        print(c2) 
        print(c3) 


k1,k2 = s0(flag) 
encrypt_(flag,k1,k2) 

'''
b'\xdbi\xab\x8d\xfb0\xd3\xfe!\xf8Xpy\x80w\x8c\x87\xb9'
b'o\xb0%\xfb\xdb\x0e\r\x04\xde\xd1\x9a\x08w\xda4\x0f\x0cR'
b'\xe7\x80\xcd\ria\xb2\xca\x89\x1a\x9d;|#3\xf7\xbb\x96'
'''

题目看着比较长，但是其实几个函数功能都是重复的，均为异或操作。提取一下其实也就有：

$$c_1 = flag \oplus k_1$$ $$c_2 = c_1 \oplus k_2 =flag \oplus k_1 \oplus k_2$$ $$c_3 = c_2 \oplus k_1 = flag \oplus k_1 \oplus k_2 \oplus k_1 = flag \oplus k_2$$

那么就有：

$$c_2 \oplus c_1 = k_2$$ $$c_2 \oplus c_3 = k_1$$ $$flag = c_1 \oplus c_2 \oplus c_3$$

exp：

from pwn import xor 

c1 = b'\xdbi\xab\x8d\xfb0\xd3\xfe!\xf8Xpy\x80w\x8c\x87\xb9'
c2 = b'o\xb0%\xfb\xdb\x0e\r\x04\xde\xd1\x9a\x08w\xda4\x0f\x0cR'
c3 = b'\xe7\x80\xcd\ria\xb2\xca\x89\x1a\x9d;|#3\xf7\xbb\x96'

flag = xor(c1,xor(c2,c3))
print(flag)

#SYC{I_l0v3_Crypt0}

OldAlgorithm

题目描述：

An old algorithm but widely used nowadays.

题目：

from Crypto.Util.number import * 
import os 
flag = b"SYC{Al3XEI_FAKE_FLAG}"

pad = lambda msg,padlen: msg+os.urandom(padlen-len(msg))


flag = pad(flag,32)
print(len(flag))
p = [getPrime(16) for _ in range(32)] 
c = [bytes_to_long(flag)%i for i in p] 


print('p=',p)
print('c=',c)

'''
p= [58657, 47093, 47963, 41213, 57653, 56923, 41809, 49639, 44417, 38639, 39857, 53609, 55621, 41729, 60497, 44647, 39703, 55117, 44111, 57131, 37747, 63419, 63703, 64007, 46349, 39241, 39313, 44909, 40763, 46727, 34057, 56333]
c= [36086, 4005, 3350, 23179, 34246, 5145, 32490, 16348, 13001, 13628, 7742, 46317, 50824, 23718, 32995, 7640, 10590, 46897, 39245, 16633, 31488, 36547, 42136, 52782, 31929, 34747, 29026, 18748, 6634, 9700, 8126, 5197]
'''

标题指的就是CRT。

exp：

from sympy.ntheory.modular import crt
from Crypto.Util.number import * 

p= [58657, 47093, 47963, 41213, 57653, 56923, 41809, 49639, 44417, 38639, 39857, 53609, 55621, 41729, 60497, 44647, 39703, 55117, 44111, 57131, 37747, 63419, 63703, 64007, 46349, 39241, 39313, 44909, 40763, 46727, 34057, 56333]
c= [36086, 4005, 3350, 23179, 34246, 5145, 32490, 16348, 13001, 13628, 7742, 46317, 50824, 23718, 32995, 7640, 10590, 46897, 39245, 16633, 31488, 36547, 42136, 52782, 31929, 34747, 29026, 18748, 6634, 9700, 8126, 5197]

m = crt(p,c)[0]
print(long_to_bytes(m))

#SYC{CRT_1s_s0_ju1cy!}

easy_classic

题目描述：

非常好套娃，使我的古典旋转

几层密码及对应解密分别如下

1

udzeojxuwqcu

2

ialhhooavtepcyr

一眼就看出来是ilovecryptohaha，估计是个W型栅栏之类，反正是个置换密码。

3

5a6H5a6Z5LiH5rOV55qE6YKj5Liq5rqQ5aS0

base64

4

熊曰：呋食食食取噗山笨笨破嗄咯哈動嗡雜類嗒嘿啽沒歡破吖咬我啽寶盜噔咯沒

开始以为是兽音，搜了才知道居然还有与熊论道加密，在线解密网址如下：

与熊论道/熊曰加密 - PcMoe!

5

password: adltlfltqrcy
key: 👝👘👠👩👞👘👤👜

key用emoji解密得到：fairgame

显然是个提示，用playfair密码解。

最终得到flag：

SYC{classical_1s_fun}

Week 2

PolyRSA

题目描述：

Harder RSA. Check it out!

题目：

import gmpy2
from Crypto.Util.number import *  
flag = b"SYC{Al3XEI_FAKE_FLAG}"
p,q = [getPrime(2048) for _ in "__"] 
e1,e2 = [getPrime(17) for _ in "__"] 
e = 65537
n = p*q 
c1 = gmpy2.powmod(2*p + 3*q,e1,n)
c2 = gmpy2.powmod(5*p + 7*q,e2,n) 
c = gmpy2.powmod(bytes_to_long(flag),e,n) 
print("e1=",e1)
print("e2=",e2) 
print("c1=",c1) 
print("c2=",c2) 
print("c=",c)
print("n=",n)

#e1= 113717
#e2= 80737
#c1= 97528398828294138945371018405777243725957112272614466238005409057342884425132214761228537249844134865481148636534134025535106624840957740753950100180978607132333109806554009969378392835952544552269685553539656827070349532458156758965322477969141073720173165958341043159560928836304172136610929023123638981560836183245954461041167802574206323129671965436040047358250847178930436773249800969192016749684095882580749559014647942135761757750292281205876241566597813517452803933496218995755905344070203047797893640399372627351254542342772576533524820435965479881620338366838326652599102311019884528903481310690767832417584600334987458835108576322111553947045733143836419313427495888019352323209000292825566986863770366023326755116931788018138432898323148059980463407567431417724940484236335082696026821105627826117901730695680967455710434307270501190258033004471156993017301443803372029004817834317756597444195146024630164820841200575179112295902020141040090350486764038633257871003899386340004440642516190842086462237559715130631205046041819931656962904630367121414263911179041905140516402771368603623318492074423223885367923228718341206283572152570049573607906130786276734660847733952210105659707746969830132429975090175091281363770357
#c2= 353128571201645377052005694809874806643786163076931670184196149901625274899734977100920488129375537186771931435883114557320913415191396857882995726660784707377672210953334914418470453787964899846194872721616628198368241044602144880543115393715025896206210152190007408112767478800650578941849344868081146624444817544806046188600685873402369145450593575618922226415069043442295774369567389939040265656574664538667552522329712111984168798829635080641332045614585247317991581514218486004191829362787750803153463482021229058714990823658655863245025037102127138472397462755776598314247771125981017814912049441827643898478473451005083533693951329544115861795587564408860828213753948427321483082041546722974666875065831843384005041800692983406353922680299538080900818930589336142421748023025830846906503542594380663429947801329079870530727382679634952272644949425079242992486832995962516376820051495641486546631849426876810933393153871774796182078367277299340503872124124714036499367887886486264658590613431293656417255355575602576047502506125375605713228912611320198066713358654181533335650785578352716562937038768171269136647529849805172492594142026261051266577821582011917001752590659862613307646536049830151262848916867223615064832279222
#c= 375617816311787295279632219241669262704366237192565344884527300748210925539528834207344757670998995567820735715933908541800125317082581328287816628816752542104514363629022246620070560324071543077301256917337165566677142545053272381990573611757629429857842709092285442319141751484248315990593292618113678910350875156232952525787082482638460259354559904243062546518553607882194808191571131590524874275187750985821420412987586148770397073003186510357920710387377990379862185266175190503647626248057084923516190642292152259727446111686043531725993433395002330208067534104745851308178560234372373476331387737629284961288204368572750848248186692623500372605736825205759172773503283282321274793846281079650686871355211691681512637459986684769598186821524093789286661348936784712071312135814683041839882338235290487868969391040389837253093468883093296547473466050960563347060307256735803099039921213839491129726807647623542881247210251994139130146519265086673883077644185971830004165931626986486648581644383717994174627681147696341976767364316172091139507445131410662391699728189797082878876950386933926807186382619331901457205957462337191923354433435013338037399565519987793880572723211669459895193009710035003369626116024630678400746946356
#n= 728002565949733279371529990942440022467681592757835980552797682116929657292509059813629423038094227544032071413317330087468458736175902373398210691802243764786251764982802000867437756347830992118278032311046807282193498960587170291978547754942295932606784354258945168927044376692224049202979158068158842475322825884209352566494900083765571037783472505580851500043517614314755340168507097558967372661966013776090657685241689631615245294004694287660685274079979318342939473469143729494106686592347327776078649315612768988028622890242005700892937828732613800620455225438339852445425046832904615827786856105112781009995862999853122308496903885748394541643702103368974605177097553007573113536089894913967154637055293769061726082740854619536748297829779639633209710676774371525146758917646731487495135734759201537358734170552231657257498090553682791418003138924472103077035355223367678622115314235119493397080290540006942708439607767313672671274857069053688258983103863067394473084183472609906612056828326916114024662795812611685559034285371151973580240723680736227737324052391721149957542711415812665358477474058103338801398214688403784213100455466705770532894531602252798634923125974783427678469124261634518543957766622712661056594132089

题目给了密文以及如下两个信息。要求分解n还原明文：

$$c_1 = (2p+3q)^{e_1} \quad(mod\;n)$$ $$c_2 = (5p+7q)^{e_2} \quad(mod\;n)$$

思路肯定是消p、q其中一个元，然后与n求gcd得到分解。

先统一指数：

$$c_1^{e_2} = (2p+3q)^{e_1e_2} \quad(mod\;n)$$ $$c_2^{e_1} = (5p+7q)^{e_1e_2} \quad(mod\;n)$$

由二项式定理展开得到：

$$c_1^{e_2} = (2p)^{e_1e_2}+(3q)^{e_1e_2} \quad(mod\;n)$$ $$c_2^{e_1} = (5p)^{e_1e_2}+(7q)^{e_1e_2} \quad(mod\;n)$$

然后配系数作差就能消掉其中一个，比如这里我们消去p：

$$5^{e_1e_2}c_1^{e_2} = 5^{e_1e_2}(2p)^{e_1e_2}+5^{e_1e_2}(3q)^{e_1e_2} \quad(mod\;n)$$ $$2^{e_1e_2}c_2^{e_1} = 2^{e_1e_2}(5p)^{e_1e_2}+2^{e_1e_2}(7q)^{e_1e_2} \quad(mod\;n)$$

作差得到：

$$5^{e_1e_2}c_1^{e_2}- 2^{e_1e_2}c_2^{e_1} = 5^{e_1e_2}(3q)^{e_1e_2} - 2^{e_1e_2}(7q)^{e_1e_2} \quad(mod\;n)$$

求解与n的gcd即可得到q，从而分解n还原明文。

exp：

from Crypto.Util.number import *  

e = 65537
e1= 113717
e2= 80737
c1= 97528398828294138945371018405777243725957112272614466238005409057342884425132214761228537249844134865481148636534134025535106624840957740753950100180978607132333109806554009969378392835952544552269685553539656827070349532458156758965322477969141073720173165958341043159560928836304172136610929023123638981560836183245954461041167802574206323129671965436040047358250847178930436773249800969192016749684095882580749559014647942135761757750292281205876241566597813517452803933496218995755905344070203047797893640399372627351254542342772576533524820435965479881620338366838326652599102311019884528903481310690767832417584600334987458835108576322111553947045733143836419313427495888019352323209000292825566986863770366023326755116931788018138432898323148059980463407567431417724940484236335082696026821105627826117901730695680967455710434307270501190258033004471156993017301443803372029004817834317756597444195146024630164820841200575179112295902020141040090350486764038633257871003899386340004440642516190842086462237559715130631205046041819931656962904630367121414263911179041905140516402771368603623318492074423223885367923228718341206283572152570049573607906130786276734660847733952210105659707746969830132429975090175091281363770357
c2= 353128571201645377052005694809874806643786163076931670184196149901625274899734977100920488129375537186771931435883114557320913415191396857882995726660784707377672210953334914418470453787964899846194872721616628198368241044602144880543115393715025896206210152190007408112767478800650578941849344868081146624444817544806046188600685873402369145450593575618922226415069043442295774369567389939040265656574664538667552522329712111984168798829635080641332045614585247317991581514218486004191829362787750803153463482021229058714990823658655863245025037102127138472397462755776598314247771125981017814912049441827643898478473451005083533693951329544115861795587564408860828213753948427321483082041546722974666875065831843384005041800692983406353922680299538080900818930589336142421748023025830846906503542594380663429947801329079870530727382679634952272644949425079242992486832995962516376820051495641486546631849426876810933393153871774796182078367277299340503872124124714036499367887886486264658590613431293656417255355575602576047502506125375605713228912611320198066713358654181533335650785578352716562937038768171269136647529849805172492594142026261051266577821582011917001752590659862613307646536049830151262848916867223615064832279222
c= 375617816311787295279632219241669262704366237192565344884527300748210925539528834207344757670998995567820735715933908541800125317082581328287816628816752542104514363629022246620070560324071543077301256917337165566677142545053272381990573611757629429857842709092285442319141751484248315990593292618113678910350875156232952525787082482638460259354559904243062546518553607882194808191571131590524874275187750985821420412987586148770397073003186510357920710387377990379862185266175190503647626248057084923516190642292152259727446111686043531725993433395002330208067534104745851308178560234372373476331387737629284961288204368572750848248186692623500372605736825205759172773503283282321274793846281079650686871355211691681512637459986684769598186821524093789286661348936784712071312135814683041839882338235290487868969391040389837253093468883093296547473466050960563347060307256735803099039921213839491129726807647623542881247210251994139130146519265086673883077644185971830004165931626986486648581644383717994174627681147696341976767364316172091139507445131410662391699728189797082878876950386933926807186382619331901457205957462337191923354433435013338037399565519987793880572723211669459895193009710035003369626116024630678400746946356
n= 728002565949733279371529990942440022467681592757835980552797682116929657292509059813629423038094227544032071413317330087468458736175902373398210691802243764786251764982802000867437756347830992118278032311046807282193498960587170291978547754942295932606784354258945168927044376692224049202979158068158842475322825884209352566494900083765571037783472505580851500043517614314755340168507097558967372661966013776090657685241689631615245294004694287660685274079979318342939473469143729494106686592347327776078649315612768988028622890242005700892937828732613800620455225438339852445425046832904615827786856105112781009995862999853122308496903885748394541643702103368974605177097553007573113536089894913967154637055293769061726082740854619536748297829779639633209710676774371525146758917646731487495135734759201537358734170552231657257498090553682791418003138924472103077035355223367678622115314235119493397080290540006942708439607767313672671274857069053688258983103863067394473084183472609906612056828326916114024662795812611685559034285371151973580240723680736227737324052391721149957542711415812665358477474058103338801398214688403784213100455466705770532894531602252798634923125974783427678469124261634518543957766622712661056594132089

t1 = pow(3,(e1*e2),n)
t2 = pow(7,(e1*e2),n)
temp1 = t2*pow(c1,e2,n)
temp2 = t1*pow(c2,e1,n)

p = GCD(temp1-temp2,n)
q = n // p
d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))

#SYC{poly_rsa_Just_need5_s1mple_gcd}

Simple3DES

题目描述：

题目链接：nc 59.110.20.54:23333 https://blog.csdn.net/Mr_wzc/article/details/121713518

题目：

from Crypto.Cipher import DES3
from Crypto.Util.number import *
import os
import random
import string
import hashlib

xor = lambda a,b: bytes([a[i % len(a)] ^ b[i % len(b)] for i in range(max(len(a), len(b)))])
pad = lambda msg,padlen: msg+chr((padlen-(len(msg)%padlen))).encode()*(padlen-(len(msg)%padlen))

flag = os.environ.get("FLAG", "SYC{Al3XEI_FAKE_FLAG}").encode()
sec = os.urandom(8)

banner = '|'*70

DEBUG = False 
def proof_of_work():
    if DEBUG:
        return True
    proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
    digest = hashlib.sha256(proof.encode()).hexdigest()
    print("sha256(XXXX+%s) == %s" % (proof[4:], digest))
    x = input("Give me XXXX: ")
    if len(x)!=4 or hashlib.sha256((x+proof[4:]).encode()).hexdigest() != digest:
        return False
    print("Right!")
    return True



def enc(msg,key):
    try:
        key = long_to_bytes(key)
        msg = xor(long_to_bytes(msg),sec)
        des = DES3.new(key,DES3.MODE_ECB)
        ct = xor(des.encrypt(pad(msg,8)),sec)
        return bytes_to_long(ct)
    except Exception as e:
        print(e)
        return Exception

def service():
    cnt = 0
    if not proof_of_work():
        exit()
    print(banner)
    print('Simple DES Encryption Service')
    print(banner)
    while cnt<2:
        print('1. Encrypt\n2. Get encrypted flag.')
        choice = int(input('> '))
        if choice == 1:
            print('Input msg:')
            msg = int(input('> ').strip())
            print('Input key:')
            key = int(input('> ').strip())
            print(enc(msg,key))
        elif choice == 2:
            print('Input key:')
            key = int(input('> ').strip())
            print(enc(bytes_to_long(flag),key))
        else:
            exit()
        cnt+=1
    print(banner)
    print('Bye!')
    exit()

try:
    service()
except Exception:
    print("Something goes wrong...\n")
    print(banner+'\n')
    exit()

题目基于3DES，其加密流程如下：

我们可以做的是：

• 输入1，可以指定3DES密钥与一段明文，获得他的加密结果
• 输入2，可以指定密钥，获得flag的加密结果

并且一共只有两次交互机会，所以可以知道预期应该是每个选项用一次。

然后需要注意，这里的enc函数并不是简单的3DES加密，而是有临时密钥sec的参与：

sec = os.urandom(8)

def enc(msg,key):
    try:
        key = long_to_bytes(key)
        msg = xor(long_to_bytes(msg),sec)
        des = DES3.new(key,DES3.MODE_ECB)
        ct = xor(des.encrypt(pad(msg,8)),sec)
        return bytes_to_long(ct)
    except Exception as e:
        print(e)
        return Exception

也就是说，enc的执行流程如下：

• 将msg与sec异或，并进行填充
• 进行3DES加密
• 将得到的密文再与sec异或，得到最终密文值

接下来阐述两种思路。

弱密钥

这一部分我是看2022年的hackergame中，不可加密的异世界的wp了解到的：

HackerGame 2022 出题记 | tl2cents blog

还有一些参考如下：

DES 弱密钥 - lightless blog

这就是说，DES加密中，存在一些密钥为弱密钥，如果使用弱密钥加密，会导致一个惨重结果：轮密钥全部相同。

这也就是说，使用弱密钥的话：

• 对明文连续加密两次，仍然是明文
• 对密文连续解密两次，仍然是密文

而3DES的密钥分为三个部分k1，k2，k3，加密流程是：

• 用k1进行加密
• 用k2进行解密
• 用k3进行加密

那么可以取巧的一个方式就是，我们选择两个弱密钥，按如下方式拼起来当作3DES的密钥：

key = b"\x01\x01\x01\x01\x01\x01\x01\x01"+b"\xFE\xFE\xFE\xFE\xFE\xFE\xFE\xFE"+b"\x01\x01\x01\x01\x01\x01\x01\x01"

那么我们第一次输入2，得到flag的加密值。第二次再把flag加密值发送回去让他加密即可，这样正好还抵消了sec的影响(可以自己推一下)，因此就能得到flag。

exp：

from Crypto.Util.number import *
from Crypto.Cipher import DES3
from pwn import *
from tqdm import *
from hashlib import sha256

#context.log_level = 'debug'

def proof_of_work():
	table = string.digits + string.ascii_letters
	temp = r.recvuntil(b"sha256(XXXX+")
	temp = r.recvline()
	suffix = temp[:16].decode()
	hex1 = temp[20:].strip().decode()
	for i in tqdm(table):
		for j in table:
			for k in table:
				for m in table:
					temp1 = i+j+k+m
					if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
						r.sendline(temp1.encode())
						return

r = remote("59.110.20.54", 23333)
proof_of_work()

xor = lambda a,b: bytes([a[i % len(a)] ^ b[i % len(b)] for i in range(max(len(a), len(b)))])
#2
r.recvuntil(b"Get encrypted flag.")
r.recvuntil(b"> ")
r.sendline(b"2")
r.recvuntil(b"> ")
key = b"\x01\x01\x01\x01\x01\x01\x01\x01"+b"\xFE\xFE\xFE\xFE\xFE\xFE\xFE\xFE"+b"\x01\x01\x01\x01\x01\x01\x01\x01"
r.sendline(str(bytes_to_long(key)).encode())
enc = long_to_bytes(int(r.recvline().strip().decode()))

#1
r.recvuntil(b"Get encrypted flag.")
r.recvuntil(b"> ")
r.sendline(b"1")
r.recvuntil(b"> ")
r.sendline(str(bytes_to_long(enc)).encode())
r.recvuntil(b"> ")
r.sendline(str(bytes_to_long(key)).encode())
flag = long_to_bytes(int(r.recvline().strip().decode()))
print(flag)


#SYC{DES_1s_0ut_0f_t1me}

pad

但是第二种估计才是预期解，注意到enc中加密流程中有个漏洞：

• 将msg与sec异或，并进行填充
• 进行3DES加密
• 将得到的密文再与sec异或，得到最终密文值

他将msg与sec异或后，再进行填充。而填充的方式如下：

pad = lambda msg,padlen: msg+chr((padlen-(len(msg)%padlen))).encode()*(padlen-(len(msg)%padlen))

DES以8字节为一组进行分组加密。而这个pad是在msg恰好为8字节的整数倍时，仍然会进行8字节b”\x08”的填充。也就是说，如果我们发送一个空的字节串，对应的数字也就是0，那么靶机端加密的流程应该是：

• sec + b”\x08”*8
• 进行3DES加密
• 得到的密文再与sec异或，得到最终密文值

而由于8字节为一组加密，所以第二组的密文值是：

$$3DES(padding) \oplus sec$$

而我们拥有密钥，自然也就能获得3DES(padding)的值，与密文异或就能得到sec的值。

有了sec后，输入2申请flag的密文，相信解密不是难事。

exp：

from Crypto.Util.number import *
from Crypto.Cipher import DES3
from pwn import *
from tqdm import *
from hashlib import sha256

#context.log_level = 'debug'

def proof_of_work():
	table = string.digits + string.ascii_letters
	temp = r.recvuntil(b"sha256(XXXX+")
	temp = r.recvline()
	suffix = temp[:16].decode()
	hex1 = temp[20:].strip().decode()
	for i in tqdm(table):
		for j in table:
			for k in table:
				for m in table:
					temp1 = i+j+k+m
					if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
						r.sendline(temp1.encode())
						return

r = remote("59.110.20.54", 23333)
proof_of_work()

xor = lambda a,b: bytes([a[i % len(a)] ^ b[i % len(b)] for i in range(max(len(a), len(b)))])
#2
r.recvuntil(b"Get encrypted flag.")
r.recvuntil(b"> ")
r.sendline(b"2")
r.recvuntil(b"> ")
key = b"1234567887654321"
des = DES3.new(key,DES3.MODE_ECB)
r.sendline(str(bytes_to_long(key)).encode())
enc = long_to_bytes(int(r.recvline().strip().decode()))

#1
r.recvuntil(b"Get encrypted flag.")
r.recvuntil(b"> ")
r.sendline(b"1")
r.recvuntil(b"> ")
r.sendline(b"0")
r.recvuntil(b"> ")
r.sendline(str(bytes_to_long(key)).encode())
enc1 = long_to_bytes(int(r.recvline().strip().decode()))


#dec
padding = b"\x08"*8
enc_pad1 = des.encrypt(padding)
sec = xor(enc_pad1,enc1)[-8:]
temp = xor(des.decrypt(xor(sec,enc)),sec)
print(temp)


#SYC{DES_1s_0ut_0f_t1me}

JPGDiff

题目描述：

图片中的字符串即为flag

题目给了两张图片，一张是经过某种加密后的图片，一张是hint。hint图片如下：

可以看到他分别给了2x2，4x4，8x8的几个图片的一种一次性走完所有点的走法，而由于加密后的图片是一个一维的点序列，因此可以知道：加密的图片就是按照这种走法得到的点的序列。

而由于加密图片共有65536=256x256个点，所以目标就是：

• 找到这种走法的普遍函数形式，推广到256x256的正方形中
• 然后生成256x256的点的序列，然后用序列对应还原加密图片即可

然后其实之前瞎翻，翻到春哥博客里看到过这个走法的加密函数：

[CryptoCTF] CryptoCTF 2023 medium分类 团队解题writeup 之二 - 知乎 (zhihu.com)

就直接去NSS上下载这个题目附件，用里面的函数直接跑一遍就能生成对应序列，然后对着还原即可。

exp：

from PIL import Image
from tqdm import *

def sox(n, d):
	x, y, t = 0, 0, d
	for s in range(n - 1):
		u = 1 & t // 2
		v = 1 & t ^ u
		x, y = spin(2**s, x, y, u, v)
		x += 2**s * u
		y += 2**s * v
		t = t // 4
	return x, y

def spin(n, x, y, u, v):
	if v == 0:
		if u == 1:
			x = n - 1 - x
			y = n - 1 - y
		x, y = y, x
	return x, y

n = 256
pix = []
for d in trange(n**2):
    x, y = sox(n, d)
    pix.append((x,y))

image = Image.open(r"E:\题\极客大挑战 2023\week2\jpgdiff\ct.png")
width, height = image.size
pixel_data = []

for y in range(height):
    for x in range(width):
        pixel = image.getpixel((x, y))
        pixel_data.append(pixel)

image = Image.new("RGB", (256, 256))
pixels = image.load()

for i in trange(65536):
      x,y = pix[i]
      pixels[y, x] = pixel_data[i]

image.save("flag.png")

#SYC{H1LB5RT_C1pher}

然后对着flag进行搜索，可以找到对应的走法其实是叫做Hilbert曲线：

希尔伯特曲线（Hilbert曲线含解析）-腾讯云开发者社区-腾讯云 (tencent.com)

Energetic_Carcano

题目来源：

题目链接：nc 59.110.20.54:8763 https://en.wikipedia.org/wiki/Elliptic-curve_cryptography

题目：

# from sage.all import *
import os 
import random 
import string 
import hashlib 
from Crypto.Util.number import * 

DEBUG = True

banner = '|'*70 
flag = os.environ.get("FLAG", b"SYC{Al3XEI_FAKE_FLAG}").encode()
pbits = 120
abp = "abp" 


def proof_of_work(): 
    if DEBUG:
        return True
    proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
    digest = hashlib.sha256(proof.encode()).hexdigest()
    print("sha256(XXXX+%s) == %s" % (proof[4:], digest))
    x = input("Give me XXXX: ")
    if len(x)!=4 or hashlib.sha256((x+proof[4:]).encode()).hexdigest() != digest: 
        return False
    print("Right!")
    return True

def check(a,b,p,turn,ans):
    if DEBUG:
        return True 
    try:
        if turn == "a":
            return int(a) == ans 
        if turn == "b":
            return int(b) == ans
        if turn == "p":
            return int(p) == ans  
    except Exception:
        exit()


try: 
    if not proof_of_work():
        exit() 
    print(banner) 
    print('\nHi Crypto-ers! AL3XEI here. I know you are excellent at math, so I prepared a game for u.') 
    print('In the equation y^2 = x^3+ a*x + b (mod p), 4 points are given. Plz give me the right a, b or p to contine the game.') 
    print('Good Luck!\n') 
    print(banner+'\n') 

    for i in range(10):
        turn = random.choice(abp) 
        p = getPrime(pbits) 
        a,b = [next_prime(random.randint(2,p)) for _ in "ab"] 
        curve = EllipticCurve(GF(p),[a,b]) 
        pts = [curve.random_point() for _ in range(4)]
        pts = [(_[0], _[1]) for _ in pts] 
        for _ in pts:
            print(_,end=" ") 
        print('\nGive me '+turn+" :") 
        ans = int(input('> ')) 
        if check(a,b,p,turn,ans):
            print("Good! Next challenge->\n") 
            print(banner+'\n')
            pbits+=5  
            continue 
        else:
            print("Something goes wrong...\n") 
            print(banner+'\n') 
            exit() 

    print('Congrats! Your flag is:',flag)

except Exception:
    print("Something goes wrong...\n") 
    print(banner+'\n') 
    exit() 

题意很简单，完成十轮挑战就能获得flag，每轮挑战内容为：

• 生成一条随机椭圆曲线，给出其上四个点的坐标
• 要求提供给定参数p、a、b其中一个的值，提供正确则进行下一轮挑战

我们知道椭圆曲线的点满足方程：

$$y^2 = x^3+ax+b \quad(mod\;p)$$

而我们有四个点的坐标，就有四组方程：

$$y_1^2 = x_1^3+ax_1+b \quad(mod\;p)$$ $$y_2^2 = x_2^3+ax_2+b \quad(mod\;p)$$ $$y_3^2 = x_3^3+ax_3+b \quad(mod\;p)$$ $$y_4^2 = x_4^3+ax_4+b \quad(mod\;p)$$

要求从四组方程中还原a、b、p，其实跟无参数的LCG很像，主要目的就是消元，求gcd得到p，然后再回到模方程中求解a、b。

消元过程如下，我们取前两组方程：

$$y_1^2 - x_1^3 =ax_1+b \quad(mod\;p)$$ $$y_2^2 - x_2^3= ax_2+b \quad(mod\;p)$$

作差消掉b：

$$y_1^2 - x_1^3 - y_2^2 + x_2^3=ax_1 - ax_2 \quad(mod\;p)$$

把a单独提出来：

$$(y_1^2 - x_1^3 - y_2^2 + x_2^3)(x_1-x_2)^{-1} = a \quad(mod\;p)$$

同理，我们取第二三组方程也能得到：

$$(y_2^2 - x_2^3 - y_3^2 + x_3^3)(x_2-x_3)^{-1} = a \quad(mod\;p)$$

那么作差就有：

$$(y_1^2 - x_1^3 - y_2^2 + x_2^3)(x_1-x_2)^{-1} - (y_2^2 - x_2^3 - y_3^2 + x_3^3)(x_2-x_3)^{-1} = 0 \quad(mod\;p)$$

那么同样再取一组求gcd，并消去小因子就能得到p，得到p过后还原ab就很轻松。

exp：

from Crypto.Util.number import *
from pwn import *
from tqdm import *
from hashlib import sha256

#context.log_level = 'debug'

def proof_of_work():
	table = string.digits + string.ascii_letters
	temp = r.recvuntil(b"sha256(XXXX+")
	temp = r.recvline()
	suffix = temp[:16].decode()
	hex1 = temp[20:].strip().decode()
	for i in tqdm(table):
		for j in table:
			for k in table:
				for m in table:
					temp1 = i+j+k+m
					if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
						r.sendline(temp1.encode())
						return

def calc(points):
    (x1,y1),(x2,y2),(x3,y3),(x4,y4) = points
    t1 = (y2**2-y1**2-x2**3+x1**3)
    t2 = (y3**2-y2**2-x3**3+x2**3)
    t3 = (y4**2-y3**2-x4**3+x3**3)
    k1p = t1*(x3-x2) - t2*(x2-x1)
    k2p = t2*(x4-x3) - t3*(x3-x2)
    k3p = t1*(x4-x3) - t3*(x2-x1)
    p = GCD(k1p,k2p)
    p = GCD(p,k3p)

    for i in range(2,1000):
        while(p % i == 0):
            p //= i
    a = inverse(x2-x1,p)*t1 % p
    b = (y1**2-x1**3-a*x1) % p

    return a,b,p
	
r = remote("59.110.20.54",8763)
proof_of_work()
r.recvuntil(b"Good Luck!")

for i in range(10):
    r.recvuntil(b"|"*70)
    r.recvline()
    r.recvline()
    points = r.recvline().strip().decode().split(" ")
    point_list = [[0,0] for k in range(4)]
    for j in range(8):
        if(j % 2 == 0):
            point_list[j//2][0] = int(points[j][1:-1])
        else:
            point_list[j//2][1] = int(points[j][:-1])

    a,b,p = calc(point_list)

    r.recvuntil(b"me ")
    turn = r.recvline()
    if(b"a" in turn):
        r.sendline(str(a).encode())
    if(b"b" in turn):
        r.sendline(str(b).encode())
    if(b"p" in turn):
        r.sendline(str(p).encode())

r.recvuntil(b"Congrats! Your flag is:")
print(r.recvline())	


#SYC{ECC_M4ster}

事实上，这题居然可以直接定义在ZZ域上，然后Groebner解。我开始认为必须在Zp域上才行，所以没有考虑过，涨知识了。

Just need One

题目描述：

题目链接：nc 59.110.20.54:2613 One bullet to kill all Outlaws.

题目：

import os 
import random 
import string 
import hashlib 

flag = os.environ.get("FLAG", b"SYC{Al3XEI_FAKE_FLAG}")
DEBUG = False
banner = '|'*70
if DEBUG:
    print("==DEBUG MODE==") 

def proof_of_work(): 
    if DEBUG:
        return True
    proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
    digest = hashlib.sha256(proof.encode()).hexdigest()
    print("sha256(XXXX+%s) == %s" % (proof[4:], digest))
    x = input("Give me XXXX: ")
    if len(x)!=4 or hashlib.sha256((x+proof[4:]).encode()).hexdigest() != digest: 
        return False
    print("Right!")
    return True  

try:
    if not proof_of_work():
        exit() 
    print(banner) 
    parms = [random.getrandbits(32) for _ in range(128)] 
    res = res = int(input('Give me x calculating f(x) :\n> '))  
    if res >= 2**32:
        print("Give me something smaller.\n")  
        print(banner+'\n') 
        exit() 

    cnt = 0  
    for _ in range(128): 
        cnt += pow(res,_)*parms[_]  
    print(cnt) 
    ans = input('Give me Coefficients :\n> ') 
    ans = [int(_) for _ in ans.split(",")] 
    
    if ans == parms:
        print('Congrats! Your flag is:',flag)  
    else:
        exit()

except Exception:
    print("Something goes wrong...\n") 
    print(banner+'\n') 
    exit() 

这题题意如下：

• 通过proof
• 生成长度为128的序列，序列中每个值是随机的32比特
• 可以输入一个小于2^32的res，当作多项式的x，并计算如下累加和cnt：

$$cnt = \sum_{i=0}^{127}parms_i * res^i$$

• 给出cnt，要求还原parms并输入给靶机，就能获得flag

解决方式也很简单，注意到他其实只限制了res小于2^32，那么我们传入负数的话，绝对值大小是不会检查的。所以直接传-2^32或更小的2的幂次，然后将累加和逐次移位并处理对应的减法借位就有parms了。

exp：

from Crypto.Util.number import *
from pwn import *
from tqdm import *
from hashlib import sha256

#context.log_level = 'debug'

def proof_of_work():
	table = string.digits + string.ascii_letters
	temp = r.recvuntil(b"sha256(XXXX+")
	temp = r.recvline()
	suffix = temp[:16].decode()
	hex1 = temp[20:].strip().decode()
	for i in tqdm(table):
		for j in table:
			for k in table:
				for m in table:
					temp1 = i+j+k+m
					if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
						r.sendline(temp1.encode())
						return

r = remote("59.110.20.54", 2613)
proof_of_work()
r.recvuntil(b"> ")
res = -2**64
r.sendline(str(res).encode())
cnt = int(r.recvline().strip().decode())
tt = cnt
r.recvuntil(b"> ")

parms = [0 for i in range(128)]
for i in range(128):
	parms[i] = cnt & ((1<<64)-1)
	if(i%2):
		parms[i] = 2**64-parms[i]
	elif(i!=0 and i%2 == 0):
		parms[i] += 1
	cnt >>= 64

r.sendline(str(parms)[1:-1].encode())
print(r.recvline())

#SYC{Alg0r1thm_1s_s0_S1mpl3!}

Fi1nd_th3_x’

题目描述：

听说在那个大陆有位叫jrl777的旅行者......Cryptoer穿越到了提瓦特就要拿出真本事！

题目：

from Crypto.Util.number import *
from libnum import* 
from secret import flag

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
e = getPrime(32)
n = p*q*r
phi = (p-1)*(q-1)*(r-1)
d = inverse(e,phi)
dP = d%((q-1)*(r-1))
dQ = d%((p-1)*(r-1))
dR = d%((p-1)*(q-1))
m = s2n(flag.encode())
c = pow(m,e,n)

print('p=',p)
print('q=',q)
print('r=',r)
print('dP=',dP)
print('dQ=',dQ)
print('dR=',dR)
print('c=',c)

'''
p= 13014610351521460822156239705430709078128228907778181478242620569429327799535062679140131416771915929573454741755415612880788196172134695027201422226050343
q= 12772373441651008681294250861077909144300908972709561019514945881228862913558543752401850710742410181542277593157992764354184262443612041344749961361188667
r= 12128188838358065666687296689425460086282352520167544115899775800918383085863282204525519245937988837403739683061218279585168168892037039644924073220678419
dP= 116715737414908163105708802733763596338775040866822719131764691930369001776551671725363881836568414327815420649861207859100479999650414099346914809923964116101517432576562641857767638396325944526867458624878906968552835814078216316470330511385701105459053294771612727181278955929391807414985165924450505855941
dQ= 44209639124029393930247375993629669338749966042856653556428540234515804939791650065905841618344611216577807325504984178760405516121845853248373571704473449826683120387747977520655432396578361308033763778324817416507993263234206797363191089863381905902638111246229641698709383653501799974217118168526572365797
dR= 60735172709413093730902464873458655487237612458970735840670987186877666190533417038325630420791294593669609785154204677845781980482700493870590706892523016041087206844082222225206703139282240453277802870868459288354322845410191061009582969848870045522383447751431300627611762289800656277924903605593069856921
c= 93063188325241977486352111369210103514669725591157371105152980481620575818945846725056329712195176948376321676112726029400835578531311113991944495646259750817465291340479809938094295621728828133981781064352306623727112813796314947081857025012662546178066873083689559924412320123824601550896063037191589471066773464829226873338699012924080583389032903142107586722373131642720522453842444615499672193051587154108368643495983197891525747653618742702589711752256009
'''

Task.txt：

5Lq65Lus5Y+q6K6w5b6X77yM6L+Z5pys5piv6aOO5ZKM5pel5Li955qE5LiA5aSp77yManJsNzc35q2j5Zyo572R5LiK5a2m5Lmg5a+G56CB5a2m44CC5b+954S25LmL6Ze077yM6buR6Imy5raI6YCA77yM5bGP5bmV55m95YWJ6aqk6LW377yM5omA5pyJ55qE6K665paH6YO95reh5Ye655y85biY44CC5LuW5Yed56We5LiA55yL77yM5Y205Y+q5pyJ5rex6YKD5aaC5aKo55qE4oCc5Y6f56We4oCd5LqM5a2X5Zyo5Zue5bqU552A44CC5pyq5Y+K5oCd6ICD77yManJsNzc36ISR6KKL5LiA6Zi15pmV55yp44CC6ICM5q2k5Yi777yM5o+Q55Om54m55aSn6ZmG5LiK56m65pyJ6YeR5YWJ6Zeq54OB77yM56m66Ze05Lmx5rWB5LmL5YaF77yM5LiD56eN5YWD57Sg5Yqb5pKV5byA5LqG5pe256m66KOC57yd77yM6aOO5bim5p2l5LqG5pWF5LqL55qE56eN5a2Q44CC5Y+v5YaN5Z2a5Zu655qE5bKp55+z5Lmf6Zq+6YCD56Oo5o2f55qE5ZG96L+Q44CC4oCc5LiW55WM77yM6YGX5b+Y5oiR44CC4oCd5LuW57uI56m25b+Y6K6w5LqG6Ieq5bexQ3J5cHRvZXLnmoTouqvku73jgILigJzmj5Dnk6bnibnlpKfpmYbnmoTml4XkurrvvIzkvaDog73mib7liLDmiJHpgZflpLHnmoTotKblj7flkJfvvJ/igJ0=

先解task得到：

人们只记得，这本是风和日丽的一天，jrl777正在网上学习密码学。忽然之间，黑色消退，屏幕白光骤起，所有的论文都淡出眼帘。他凝神一看，却只有深邃如墨的“原神”二字在回应着。未及思考，jrl777脑袋一阵晕眩。而此刻，提瓦特大陆上空有金光闪烁，空间乱流之内，七种元素力撕开了时空裂缝，风带来了故事的种子。可再坚固的岩石也难逃磨损的命运。“世界，遗忘我。”他终究忘记了自己Cryptoer的身份。“提瓦特大陆的旅人，你能找到我遗失的账号吗？”

还是直接看题吧，题目给出以下几个值：

dP = d%((q-1)*(r-1))
dQ = d%((p-1)*(r-1))
dR = d%((p-1)*(q-1))

然后也直接给了n的分解p、q、r以及密文，要求还原明文。

主要问题就在于，没有加密指数e，且加密指数e的比特是32，不太容易爆破，因此我们无法直接求得解密指数，只能用给的几个dP、dQ、dR来解题。(其实翻maple的博客翻到过有一个工具，可以非常快速的给出所有32比特的素数，但是这题肯定不是考这个哈哈。有兴趣的师傅也可以自己去找一找)

然后对dP熟悉一点的话，应该能知道，我们能获得以下几个解密值：

$$c^{dP} \equiv m \quad(mod\;qr)$$ $$c^{dQ} \equiv m \quad(mod\;pr)$$ $$c^{dR} \equiv m \quad(mod\;pq)$$

那么其实就是一个不互素的CRT，不清楚的师傅可以自己搜一搜原理，这里推荐一手Xenny师傅的密码工坊。

但是只追求出结果的话，用这个库里的函数可以一步到位，不管互不互素：

from sympy.ntheory.modular import crt

当然我是建议了解清楚原理。

exp：

from Crypto.Util.number import *
from sympy.ntheory.modular import crt

p= 13014610351521460822156239705430709078128228907778181478242620569429327799535062679140131416771915929573454741755415612880788196172134695027201422226050343
q= 12772373441651008681294250861077909144300908972709561019514945881228862913558543752401850710742410181542277593157992764354184262443612041344749961361188667
r= 12128188838358065666687296689425460086282352520167544115899775800918383085863282204525519245937988837403739683061218279585168168892037039644924073220678419
dP= 116715737414908163105708802733763596338775040866822719131764691930369001776551671725363881836568414327815420649861207859100479999650414099346914809923964116101517432576562641857767638396325944526867458624878906968552835814078216316470330511385701105459053294771612727181278955929391807414985165924450505855941
dQ= 44209639124029393930247375993629669338749966042856653556428540234515804939791650065905841618344611216577807325504984178760405516121845853248373571704473449826683120387747977520655432396578361308033763778324817416507993263234206797363191089863381905902638111246229641698709383653501799974217118168526572365797
dR= 60735172709413093730902464873458655487237612458970735840670987186877666190533417038325630420791294593669609785154204677845781980482700493870590706892523016041087206844082222225206703139282240453277802870868459288354322845410191061009582969848870045522383447751431300627611762289800656277924903605593069856921
c= 93063188325241977486352111369210103514669725591157371105152980481620575818945846725056329712195176948376321676112726029400835578531311113991944495646259750817465291340479809938094295621728828133981781064352306623727112813796314947081857025012662546178066873083689559924412320123824601550896063037191589471066773464829226873338699012924080583389032903142107586722373131642720522453842444615499672193051587154108368643495983197891525747653618742702589711752256009

cp = pow(c,dP,q*r)
cq = pow(c,dQ,p*r)
cr = pow(c,dR,p*q)

N = [q*r,p*r,p*q]
C = [cp,cq,cr]
M = crt(N,C)[0]
print(long_to_bytes(M))

#SYC{CRT_1s_f3n_but_Gen3hi_im9act_is_a_balabalaba}

然后就发现，这明文并不长，所以随便用一个模下的m都可以直接出结果，并不需要CRT。

Week 3

Quick_Robert

题目描述：

nc 59.110.20.54:3042 https://en.wikipedia.org/wiki/Quadratic_residue

题目没有给源码，nc上去后发现有proof_of_work，那么把proof过掉后靶机会发送题目任务如下：

||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Hi Crypto-ers! AL3XEI Here. In number theory, if there exists an integer q satisfying x^2=q(mod n), q is so called a quadratic residue.
We write this calculation as L(a,p), which its value shows a is or is not quadratic residue modulo p.
Below, you need to give me the answer of the sum of L(a*l**2+b*l+1,p), where a,b are integers, p is a prime, and l rise from 0 to p-1.
For example, given a = 2, b = 3, c = 1, p = 5, the answer will be
L(1, 5) + L(6, 5) + L(15, 5) + L(28, 5) + L(45, 5) = 1.      
Hope you success!

||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

1809 * l**2 + 204 * l + 1
p = 191 (8 bits)

> Type your answer:

大致描述一下题目任务：

• L(a,p)是一个函数，根据a是模p下的二次剩余还是二次非剩余有不同的取值。按照例子的话，我认为应该是：

$$\begin{equation} L(a,p)=\left\{ \begin{aligned} 0 \quad a是模p下的二次剩余\\ 1 \quad a是模p下二次非剩余\\ \end{aligned} \right . \end{equation}$$

• 然后，题目要求计算如下累加式并返回答案，答案正确即可进入下一轮：

$$\sum_{l=0}^{p-1}{L(al^2+bl+1,p)}$$

没什么其他思路，不过第一轮p只有8bit所以可以先用欧拉判别式暴力计算一遍，然后会发现一个很巧的事实：

对于所有的 $ l \in [0,p-1]$，都有al^2+bl+1是模p下的二次剩余。多切几组数字也是这样的。

那这难道是个什么结论吗？并不是。因为如果自己生成一组a、b、p的话，基本上是满足不了这个结论的。说明这个a、b、p肯定是取的满足某个性质的特殊值。经过测试发现：给的a、b均满足a是二次剩余，且满足下面的完全平方式：

$$t^2 = a$$ $$ax^2+bx+1 = (tx+1)^2 \quad(mod\;p)$$

测试脚本如下：

from Crypto.Util.number import *

a,b,c,p = 1809,204,1,191
PR.<x> = PolynomialRing(Zmod(p))
f = x^2 - a
t = f.roots()

#ax^2+bx+1 -> (tx+1)^2
print(b%p)
for i in t:
    print(int(i[0])*2%p)

所以才有为什么全部都是二次剩余。那么照这样来说我们每次传0给靶机就好。

但是实际上并不是这样的，测试出来需要每次传p-1给靶机，不知道是例子给错了还是什么情况，反正题目肯定是有点小问题。

exp：

from Crypto.Util.number import *
from pwn import *
from tqdm import *
from hashlib import sha256
import re

#context.log_level = 'debug'

#part1 proof		
def proof_of_work():
	table = string.digits + string.ascii_letters
	temp = r.recvuntil(b"sha256(XXXX+")
	temp = r.recvline()
	suffix = temp[:16].decode()
	hex1 = temp[20:].strip().decode()
	for i in tqdm(table):
		for j in table:
			for k in table:
				for m in table:
					temp1 = i+j+k+m
					if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
						r.sendline(temp1.encode())
						return

r = remote("59.110.20.54",3042)
proof_of_work()


#part2 calculate
def find_coeffcients(expression):
	# 定义匹配系数的正则表达式
    pattern = re.compile(r'(-?\d+)\s*\*\s*l\*\*2|(-?\d+)\s*\*\s*l|(-?\d+)')
    # 使用findall方法找到匹配的所有项
    matches = pattern.findall(expression)
    # 将匹配结果转换为整数并存储在列表中
    coefficients = [int(match[0] or match[1] or match[2]) for match in matches]
    return coefficients

def find_p(equation):
    pattern = re.compile(r'\b\d+\b')
    # 使用search方法找到匹配的第一个数字
    match = pattern.search(equation)
    p_value = int(match.group())
    return p_value

r.recvuntil(b"|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||")
for i in range(7):	
	r.recvuntil(b"|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||")
	r.recvline()
	r.recvline()	
	temp = r.recvline().strip().decode()		
	a,b,c = find_coeffcients(temp)
	p = find_p(r.recvline().strip().decode())
	#print("a,b,c,p = "+str(a)+","+str(b)+","+str(c)+","+str(p))
	r.recvuntil(b"> Type your answer:")
	r.sendline(str(p-1).encode())

r.recvline()
r.recvline()
r.recvline()
r.recvline()
print(r.recvline())


#SYC{G00d!_u_4r3_Qu33n_0f_Quadratic}

更新

题目之后进行了update，对L函数作了详细说明，也就是勒让德符号：

$$\begin{equation} L(a,p)=\left\{ \begin{aligned} 0 \quad a是模p下的某个因子\\ 1 \quad a是模p下的二次剩余\\ -1 \quad a是模p下二次非剩余\\ \end{aligned} \right . \end{equation}$$

那么再看之前题目的例子就没问题了，回传p-1也是正确的。然后题目更新后还做了如下修改：

• 每一轮的p都取了1000bit以上的大数
• 增加了三轮，现在需要通过十轮才有flag
• a、b、p不再全部是特殊构造

当然这个需要十轮是做出来才知道的。

然后我的做法也很简单，首先自己生成一些小的素数进行测试，找找规律：

from Crypto.Util.number import *
import random
from gmpy2 import *
from tqdm import *

def calcsum(a,b,c,p):
    sum = 0
    for i in range(0,p):
        temp = a*i**2+b*i+1
        if(powmod(temp,(p-1)//2,p) == 1):
            sum += 1
        elif(powmod(temp,(p-1)//2,p) == p-1):
            sum += -1
        else:
            sum += 0
    return sum

for i in range(10):
    p = getPrime(18)
    a = random.randint(1,p-1)
    b = random.randint(1,p-1)
    c = 1
    print(powmod(a,(p-1)//2,p),calcsum(a,b,c,p))

然后就会发现测试出来，L函数的求和结果仅与a是否是模p下的二次剩余有关。如果a是模p下的二次剩余，求和结果为-1；否则为1。

当然还要考虑一种特殊情况，也就是update之前的那种特殊构造(虽然a、b如果是纯随机的话这种情况基本不太可能出现，但是出题人确实在题目中构造了这个情况)，我们用如下方法来核验是否能构成完全平方式：

(b*inverse(2,p))**2 % p == a%p

所以我们每次用以下条件语句，选择发送对应的求和结果给靶机就好：

if((b*inverse(2,p))**2 % p == a%p):
	res = p-1
elif(pow(a,(p-1)//2,p) == 1):
	res = -1
else:
	res = 1

exp：

from Crypto.Util.number import *
from pwn import *
from tqdm import *
from hashlib import sha256
import re

#context.log_level = 'debug'

#part1 proof		
def proof_of_work():
	table = string.digits + string.ascii_letters
	temp = r.recvuntil(b"sha256(XXXX+")
	temp = r.recvline()
	suffix = temp[:16].decode()
	hex1 = temp[20:].strip().decode()
	for i in tqdm(table):
		for j in table:
			for k in table:
				for m in table:
					temp1 = i+j+k+m
					if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
						r.sendline(temp1.encode())
						return



r = remote("59.110.20.54",3042)
proof_of_work()

#part2 calculate
def find_coeffcients(expression):
	# 定义匹配系数的正则表达式
	pattern = re.compile(r'(-?\d+)\s*\*\s*l\*\*2|(-?\d+)\s*\*\s*l|(-?\d+)')
	# 使用findall方法找到匹配的所有项
	matches = pattern.findall(expression)
	# 将匹配结果转换为整数并存储在列表中
	coefficients = [int(match[0] or match[1] or match[2]) for match in matches]
	return coefficients

def find_p(equation):
	pattern = re.compile(r'\b\d+\b')
	# 使用search方法找到匹配的第一个数字
	match = pattern.search(equation)
	p_value = int(match.group())
	return p_value

r.recvuntil(b"|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||")
for i in trange(10):	
	r.recvuntil(b"|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||")
	r.recvline()
	r.recvline()	
	temp = r.recvline().strip().decode()
	
	a,b,c = find_coeffcients(temp)
	p = find_p(r.recvline().strip().decode())
	#print("a,b,c,p = "+str(a)+","+str(b)+","+str(c)+","+str(p))
	r.recvuntil(b"> Type your answer:")
	if((b*inverse(2,p))**2 % p == a%p):
		res = p-1
	elif(pow(a,(p-1)//2,p) == 1):
		res = -1
	else:
		res = 1
	r.sendline(str(res).encode())

r.recvline()
r.recvline()
r.recvline()
r.recvline()
print(r.recvline())


#SYC{G00d!_u_4r3_Qu33n_0f_Quadratic}

当然，题做完了还是要想想，排除掉能构成完全平方式的特殊情况后，为什么这个求和结果只与a是否是模p下的二次剩余有关。这个问题抽象出来其实就是勒让德符号求和，于是搜索关键词可以搜索到下面这篇文章：

https://imomath.com/index.cgi?page=quadraticCongruencesSumsLegendreSymbols

这里阐述一下他的证明思路。

预备知识

首先需要知道一个引理：

去除0，模p的完全剩余系中有(p-1)/2个二次剩余，有(p-1)/2个二次非剩余

这个引理的证明也很简单，首先知道：

$$对于 \forall x \in(0,p),(\frac{x^2}{p}) = 1$$

也就是x^2形式的数均为二次剩余，这样也能求出模p下的全部二次剩余。而由于(p-x)^2和x^2模p下相同，因此可以两两配对，也就是模p的完全剩余系下共有(p-1)/2个二次剩余，剩下的(p-1)/2个数自然也就是二次非剩余。

有了这个引理后，我们先从最简单的情况开始，考虑对如下形式的f(x)求勒让德符号的和：

$$f(x) = ax+b$$ $$sum = \sum_{x=0}^{p-1}(\frac{f(x)}{p})$$

显然，由于ax+b也构成模p下的完全剩余系，所以同样有(p-1)/2个x使得f(x)是二次剩余，(p-1)/2个x使得f(x)是二次非剩余，然后还有一个x使得f(x)为0，因此求和结果是：

$$sum = \sum_{x=0}^{p-1}(\frac{f(x)}{p}) = 1*\frac{p-1}{2}+(-1)*\frac{p-1}{2}+0 = 0$$

回到题目

然后回到我们求勒让德符号和的f(x)形式，也就是：

$$f(x) = ax^2+bx+c$$ $$sum = \sum_{x=0}^{p-1}(\frac{f(x)}{p})$$

那么首先对f(x)进行一点处理，由于：

$$4af(x) = 4ax^2+4abx+4ac = (2ax+b)^2 - (b^2 - 4ac)$$

那么对于f(x)的勒让德符号有：

$$(\frac{4af(x)}{p}) = (\frac{4a}{p})(\frac{f(x)}{p})$$

所以对于我们需要求的和sum，可以写作：

$$\sum_{x=0}^{p-1}(\frac{4af(x)}{p}) = (\frac{4a}{p})\sum_{x=0}^{p-1}(\frac{f(x)}{p})$$

移项就得到(移项基于勒让德符号只有1、-1、0三个取值)：

$$sum = \sum_{x=0}^{p-1}(\frac{f(x)}{p}) = (\frac{4a}{p})\sum_{x=0}^{p-1}(\frac{4af(x)}{p}) = (\frac{4a}{p})\sum_{x=0}^{p-1}(\frac{(2ax+b)^2 - (b^2 - 4ac)}{p})$$

而之所以要把x化成这个形式，是因为这样可以发现：2ax+b也构成了模p下的完全剩余系，所以其实(2ax+b)^2效果和x^2相同，然后我们把b^2-4ac记作D(就像二次函数的判别式)，，并且，由于勒让德符号的完全积性，(4a,p)=(a,p)，因此sum的表达式可以进一步简化为：

$$sum = (\frac{a}{p})\sum_{x=0}^{p-1}(\frac{x^2 - D}{p})$$

那么问题就简化成了求解出下面这个表达式的值：

$$\sum_{x=0}^{p-1}(\frac{x^2 - D}{p})$$

然后要求解这个式子又需要引入一个定理，这里我直接截图：

这个定理对我们现在推导的贡献是，他告诉我们以下式子的值为：

$$\sum_{x=0}^{p-1}(\frac{x^2 - D}{p}) \equiv -1 \quad(mod\;p)$$

而由于勒让德符号只有1、-1、0三个取值，所以就有：

$$\sum_{x=0}^{p-1}(\frac{x^2 - D}{p}) = -1 或p-1$$

那值在什么时候会分别取到-1和p-1呢？可以想到，如果等于p-1，那么对除了x^2-D零点以外的所有x，都有：

$$(\frac{x^2 - D}{p}) = 1$$

这也就是说所有x^-D都是模p下的二次剩余，因此只可能D是p的倍数。而此外的其他情况就有：

$$\sum_{x=0}^{p-1}(\frac{x^2 - D}{p}) = -1$$

然后由之前的推导有：

$$sum = (\frac{a}{p})\sum_{x=0}^{p-1}(\frac{x^2 - D}{p})$$

所以再排除了能构成完全平方式的情况后，我们只需要判断a是否是模p下的二次剩余就可以求解sum了。

Diligent_Liszt

题目描述：

https://en.wikipedia.org/wiki/Discrete_logarithm

题目：

import gmpy2 as gp 
import random 
from Crypto.Util.number import * 

DEBUG = False
 
flag = b"SYC{Al3XEI_FAKE_FLAG}"
assert flag.startswith(b"SYC")
nbits = 512
g = 3 

def gen_p_1(digit):
    primes = []
    pri = 1
    while(len(primes)<100):
        pri = gp.next_prime(pri)
        primes.append(int(pri))
    while True:
        count = 2
        while count < 2**digit:
            count *= random.choice(primes)
        count += 1
        if(gp.is_prime(count)):
            return count
        

p,q,r = [gen_p_1(nbits) for _ in "pqr"] 

n = p*q*r 
x = bytes_to_long(flag) 
y = gp.powmod(g,x,n) 


print("p = {}".format(p))
print("q = {}".format(q))
print("r = {}".format(r))   
print("y = {}".format(y)) 

if DEBUG:
    print("x = {}".format(x)) 

'''
p = 1068910928091265978478887270179608140018534288604159452828300604294675735481804963679672853224192480667904101881092533866322948043654533322038484907159945421
q = 1711302770747802020613711652777299980542669713888988077474955896217408515180094849053961025086865697904731088087532944829046702427480842253022459937172565651
r = 132969813572228739353704467775972551435751558645548804253458782569132362201099158857093676816706297676454547299888531536236748314013888413096371966359860637
y = 5385116324746699759660077007129548063211490907227715474654765255668507958312745677683558789874078477569613259930365612562164095274660123330458355653249805062678976259429733060364358954180439218947514191603330532117142653558803034110759332447742304749985874760435453594107494324797235909651178472904825071375135846093354526936559640383917210702874692725723836865724807664892994298377375580807917514349966834376413176898806591411038129330967050554114677719107335006266

'''

题目中三个数均满足p-1光滑，那么如果不给p、q、r分别的值也能分解出来。既然直接给了，那就分开用pohlig-hellman求DLP后再crt起来就好。

exp：

from Crypto.Util.number import * 
from sympy.ntheory.modular import crt

p = 1068910928091265978478887270179608140018534288604159452828300604294675735481804963679672853224192480667904101881092533866322948043654533322038484907159945421
q = 1711302770747802020613711652777299980542669713888988077474955896217408515180094849053961025086865697904731088087532944829046702427480842253022459937172565651
r = 132969813572228739353704467775972551435751558645548804253458782569132362201099158857093676816706297676454547299888531536236748314013888413096371966359860637
y = 5385116324746699759660077007129548063211490907227715474654765255668507958312745677683558789874078477569613259930365612562164095274660123330458355653249805062678976259429733060364358954180439218947514191603330532117142653558803034110759332447742304749985874760435453594107494324797235909651178472904825071375135846093354526936559640383917210702874692725723836865724807664892994298377375580807917514349966834376413176898806591411038129330967050554114677719107335006266
g = 3

xp = discrete_log(mod(y,p),mod(g,p))
xq = discrete_log(mod(y,q),mod(g,q))
xr = discrete_log(mod(y,r),mod(g,r))

n = [p-1,q-1,r-1]
c = xp,xq,xr
M = crt(n,c)[0]
print(long_to_bytes(int(M)))

#SYC{D1scr3te_L0g_W1th_Mult1pl3_pr1m35}

card_game

题目描述：

AL3XEI送给了你这个游戏的关键数据，你能预测接下来要出的牌吗 nc 59.110.20.54 4953

题目：

from Crypto.Util.number import *
from cards import Heart, Spade, Club, Diamond
from secret import flag

def choose_card(num):
    x = (num>>5)%4
    if x == 0:
        return (Heart[(num>>6)%13]), 'Heart'
    if x%4 == 1:
        return (Spade[(num>>6)%13]), 'Spade'
    if x%4 == 2:
        return (Diamond[(num>>6)%13]), 'Diamond'
    else:
        return (Club[(num>>6)%13]), 'Club'

def GAME():
    banner = ''' 
 ####    ##   #####  #####      ####    ##   #    # ###### 
#    #  #  #  #    # #    #    #    #  #  #  ##  ## #      
#      #    # #    # #    #    #      #    # # ## # #####  
#      ###### #####  #    #    #  ### ###### #    # #      
#    # #    # #   #  #    #    #    # #    # #    # #      
 ####  #    # #    # #####      ####  #    # #    # ######
'''
    print(banner)

    meum = '''option:
    1: start game
    2: get hint
    3: exit
    '''
    print(meum)

    while True:
        print('input your option: ', end='')
        your_input = input()

        if your_input == '1':
            n = getPrime(36)
            m = getPrime(16)
            c = getPrime(16)
            seed = getPrime(36)
            out = seed
            round = 0
            score = 0
            res = []
            while True:
                round += 1
                res = []
                print(f'round:{round}')
                print(f'score:{score}')
                for i in range (3):
                    out = (out*m+c)%n
                    res.append(out)
                if round == 1:
                    for i in res:
                        card, suit = choose_card(i)
                        print(card)
                elif round==2 or round==3:  #gift
                    for i in res:
                        card, suit = choose_card(i)
                        print(card)
                    print(f'gift: {res}')
                else:
                    cards = []
                    suits = []
                    for i in range(len(res)):
                        card, suit = choose_card(res[i])
                        cards.append(card)
                        suits.append(suit)
                    print("Give me your guess: (example: Heart_1 Club_2 Diamond_3)")  
                    try:
                        g_1, g_2, g_3 = input().split()
                        g_1, g_2, g_3 = g_1.split('_'), g_2.split('_'), g_3.split('_')
                    except ValueError:
                        print("Please enter in the correct format.")
                        return
                    if (g_1[0] == suits[0] and g_1[1] == cards[0][15]) and (g_2[0] == suits[1] and g_2[1] == cards[1][15]) and (g_3[0] == suits[2] and g_3[1] == cards[2][15]):
                        for i in cards:
                            print(i)
                        print("Congratulations! You matched the cards!")
                        score += 1
                    else:
                        for i in cards:
                            print(i)
                        print("Try again!")
                if score == 50:
                    print('The flag is your reward!')
                    print(flag)
                    return
                else:
                    continue
        
        if your_input == '2':
            print("Have you ever heard of LCG?")

        if your_input == '3':
            break

if __name__ == '__main__':
    GAME()

card文件是给了很多如下形式的牌面字符串：

'''
┌─────────┐
│ A       │
│         │
│    ♥    │
│         │
│       A │
└─────────┘'''

总的说来，题目代码很长，但是实际上仔细看完过后会发现考的东西真的很简单，我猜可能是有升级版的题目在后面，不然感觉有点浪费。

任务是这样的，题目给我们提供了三个选项，但是其实只有输入1有用。输入1后会发生：

• 随机生成n、m、c、seed四个数，用这四个数实现以下的LCG：

$$x = mx+c \quad(mod\;n)$$

• 然后游戏开始，每一轮，用这个LCG生成三个数，并用这三个数计算牌的数字和花色
• 在第二轮和第三轮，会额外给出这一轮的三个数的值
• 从第四轮开始，要求我们预测这一轮的三张牌的数字和花色，预测正确则加一分，分数达到50就给flag

而根据数字得到牌的计算方式choose_card(num)是题目给了我们的，所以目标就是得到LCG的每一轮的三个数的值。而我们有第二轮和第三轮的共六个LCG的数字序列。那么就可以完全复原LCG的各个参数m、c、n，然后就往后预测就可以了。

然后有一点需要注意，每一次发送的形式应该是如下：

(example: Heart_1 Club_2 Diamond_3)

然后注意到他的牌的数字是这么取的：

cards[0][15]

也就是每张牌的第十五个字符。比如对于A：

'''
┌─────────┐
│ A       │
│         │
│    ♥    │
│         │
│       A │
└─────────┘'''

第十五个字符就恰好是A。然而对于10就不太一样了：

'''
┌─────────┐
│10       │
│         │
│    ♥    │
│         │
│       10│
└─────────┘'''

其第十五个字符应该是0。所以要留意一下这个小细节。不过其实无伤大雅，因为就算猜错了他也不会退出，而还能继续猜，所以只要够50分就可以。

exp：

from Crypto.Util.number import *
from pwn import *
from tqdm import *
from gmpy2 import powmod

#context.log_level = 'debug'

def solve_LCG(sequence):
    c1,c2,c3,c4,c5,c6 = sequence

    t1 = c2-c1
    t2 = c3-c2
    t3 = c4-c3
    t4 = c5-c4
    T1 = t4*t2 - t3*t3
    T2 = t3*t1 - t2*t2
    n = GCD(T1,T2)

    for i in range(2,1000):
        while(n % i == 0):
            n //= i

    m = inverse((c2-c1),n)*(c3-c2) % n
    c = (-m*c2 + c3) % n

    return m,c,n

def getnext(out,m,c,n):
    next_out = [out[-1]]
    for i in range(3):
        next_out.append((m*next_out[-1]+c)%n)
    return next_out[1:]

def gen_card(out):
    table_num = ["A","2","3","4","5","6","7","8","9","0","J","Q","K"]
    table_suits = ['Heart','Spade','Diamond','Club']

    res = ""
    for i in out:
        suits_order = (i >> 5) % 4
        num_order = (i >> 6) % 13
        res += (table_suits[suits_order] + "_" + table_num[num_order] + " ")

    return res
    
sequence = []
r = remote("59.110.20.54",4953)
r.recvuntil(b"input your option:")
r.sendline(b"1")
r.recvuntil(b"gift: ")
sequence += eval(r.recvline().decode().strip())
r.recvuntil(b"gift: ")
sequence += eval(r.recvline().decode().strip())
m,c,n = solve_LCG(sequence)
out = getnext(sequence,m,c,n)
res = gen_card(out)
r.recvuntil(b"(example: Heart_1 Club_2 Diamond_3)")
r.sendline(res.encode())

for i in trange(49):
    out = getnext(out,m,c,n)
    res = gen_card(out)
    r.recvuntil(b"(example: Heart_1 Club_2 Diamond_3)")
    r.sendline(res.encode())
r.recvuntil(b"The flag is your reward!")
r.recvline()
print(r.recvline())

#SYC{lcg_a@@@@@ttack}

Week 4

EzComplex

题目描述：

And u, my friend:  Complex factors! (In a double sense)

题目：

#sage9.3
from Crypto.Util.number import *
flag = b'FAKE{Do_You_know_Complex_numbers}'
p = random_prime(1 << 384)
q = random_prime(1 << 384)
n = p * q
e = 0x10001
N = pow(p, 2) + pow(q, 2)
m = bytes_to_long(flag)
c = pow(m,e,n)


print(c)
print(N)

'''
122977267154486898127643454001467185956864368276013342450998567212966113302012584153291519651365278888605594000436279106907163024162771486315220072170917153855370362692990814276908399943293854077912175867886513964032241638851526276
973990451943921675425625260267293227445098713194663380695161260771362036776671793195525239267004528550439258233703798932349677698127549891815995206853756301593324349871567926792912475619794804691721625860861059975526781239293017498
'''

题目给了一个额外信息N如下，要求给出n的分解：

$$N = p^2 + q^2$$

结合题目名字complex，可以把这个数字放在复数域中分解，这是因为：

$$N = (p+qi)(p-qi)$$

因此在复数域中分解，并遍历所有可能的因子就能得到p和q。

exp：

from Crypto.Util.number import *

c = 122977267154486898127643454001467185956864368276013342450998567212966113302012584153291519651365278888605594000436279106907163024162771486315220072170917153855370362692990814276908399943293854077912175867886513964032241638851526276
N = 973990451943921675425625260267293227445098713194663380695161260771362036776671793195525239267004528550439258233703798932349677698127549891815995206853756301593324349871567926792912475619794804691721625860861059975526781239293017498
e = 65537

zn = ZZ[i](N)
for d in divisors(zn):
    p = int(d[0])
    q = int(d[1])
    if isPrime(p) and isPrime(q) and p.bit_length() > 380:
        break
phi = (p-1)*(q-1)
n  = p*q
d = inverse(e,phi)
print(long_to_bytes(int(pow(c,d,n))))

#SYC{D0_you_like_r41n?_i_pref3r_R1_ng}

ext^7gcd

题目描述：

题目链接：nc 59.110.20.54:1789 （下sagemath! 不下的统统发配到安东星当嘿奴！）

又是一个没有附件的题目，通过proof后我们可以看见题目内容：

||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Hi Crypto-ers! AL3XEI here. Solving extended gcd over 2 primes can be easy, but what about 7 primes?
primes : [938770989594038574883307091377, 731124780451059048515699872973, 705906522337130351303390881793, 1259253321424214851154594220511, 638192849150199238389371476021, 1160157641563492827848830377527, 1225294646722407790694425867847] ( 100 bits )
Give me a0,...a5,a6:

题目意思也很明确，要求我们对7个素数求出扩展欧几里得的结果，也就是找到a0、a1、…a6满足：

$$\sum_{i=0}^{6}{a_ip_i} = d$$

其中d是7个素数的最大公约数，所以也就是1。并且经测试是不能发送0给靶机的。

我的做法也很简单，首先对前六个数两两使用exgcd，使得：

$$a_1p_1 + b_1p_2 = 1$$ $$a_2p_3 + b_2p_4 = 1$$ $$a_3p_5 + b_3p_6 = 1$$

所以就有：

$$(a_1p_1 + b_1p_2) + (a_2p_3 + b_2p_4) + (a_3p_5 + b_3p_6) = 3$$

然后再将3与最后一个素数做exgcd，就有：

$$a_4((a_1p_1 + b_1p_2) + (a_2p_3 + b_2p_4) + (a_3p_5 + b_3p_6)) + b_4p_7 = 1$$

将对应系数发送过去即可。测试后知道共有15轮挑战，并且发送的格式是：

a,b,c,d,e,f,g

也就是列表不带两边括号的形式。

然后如果限制只有不能发送0的话，那么方法太多太多了。比如想个简单一点的先让后六个a为1，然后把后六个素数的和与第一个素数做exgcd即可。再麻烦一点，甚至可以构造一个下面这样的格：

$$L= \left(\begin{matrix} -K & & & & & & & \\ Kp_1 & 1& & & & & & \\ Kp_2 & & 1& & & & & \\ Kp_3 & & & 1& & & & \\ Kp_4 & & & & 1& & & \\ Kp_5 & & & & & 1 & & \\ Kp_6 & & & & & & 1& \\ Kp_7 & & & & & & & 1\\ \end{matrix}\right)$$

这是因为当满足题目需要的exgcd要求 $ \sum_{i=1}^{7}{a_ip_i} = 1 $时，这个格具有下面的线性关系：

$$(1,a_1,a_2,a_3,a_4,a_5,a_6,a_7) \left(\begin{matrix} -K & & & & & & & \\ Kp_1 & 1& & & & & & \\ Kp_2 & & 1& & & & & \\ Kp_3 & & & 1& & & & \\ Kp_4 & & & & 1& & & \\ Kp_5 & & & & & 1 & & \\ Kp_6 & & & & & & 1& \\ Kp_7 & & & & & & & 1\\ \end{matrix}\right) =(0,a_1,a_2,a_3,a_4,a_5,a_6,a_7)$$

所以可以规约出我们需要的ai向量，而之所以第一列乘上大系数K是为了保证第一项规约出0。不过既然有很多简单方法可选，这个方法就没太大必要了。

exp：

from Crypto.Util.number import *
from pwn import *
from tqdm import *
from hashlib import sha256,sha1
import string
from gmpy2 import gcdext

#context.log_level = 'debug'

def proof_of_work():
	table = string.digits + string.ascii_letters
	temp = r.recvuntil(b"sha256(XXXX+")
	temp = r.recvline()
	suffix = temp[:16].decode()
	hex1 = temp[20:].strip().decode()
	for i in tqdm(table):
		for j in table:
			for k in table:
				for m in table:
					temp1 = i+j+k+m
					if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
						r.sendline(temp1.encode())
						return
					
r = remote("59.110.20.54", 1789)
proof_of_work()

for round in range(15):
	r.recvuntil(b'primes :')
	primes = eval(r.recvline().strip().decode().split("(")[0])

	d,a1,b1 = gcdext(primes[0],primes[1])
	d,a2,b2 = gcdext(primes[2],primes[3])
	d,a3,b3 = gcdext(primes[4],primes[5])
	d,a4,b4 = gcdext(3,primes[6])

	t = [int(a1)*int(a4),int(b1)*int(a4),int(a2)*int(a4),int(b2)*int(a4),int(a3)*int(a4),int(b3)*int(a4),int(b4)]
	sum1 = 0
	for i in range(7):
		sum1 += t[i]*primes[i]
	r.sendline(str(t)[1:-1].encode())
r.recvline()
r.recvline()
r.recvline()
r.recvline()
print(r.recvline())

#SYC{N0t_s0_e4sy_3xtgCd}

Algebra

题目描述：

Recently jrl888 has learned something about groebner_basis.But could U plz help him to sovle his linear algebra homework?

题目：

#utf-8
#sage


import os
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from secret import flag,e
from functools import reduce

assert reduce(lambda x,y:x&y,[i^3 - 10*i^2 + 31*i - 30==0 for i in e])

LEN = 32
flag = pad(flag,36)

def LongArray(t:list):
    return [bytes_to_long(t[i]) for i in range(len(t))]

def BytesArray(t:list):
    return [long_to_bytes(t[i]) for i in range(len(t))]

def xor(a, b):
    return bytes([a[i%len(a)] ^^ b[i%len(b)] for i in range(max(len(a), len(b)))])

def ArrayXor(a:list,b:bytes):
    return [xor(a[i],b) for i in range(len(a))]

def scissors(flag:bytes):
    return [flag[i:i+len(flag)//3] for i in range(0, len(flag), len(flag)//3)]

def challenge(m: bytes, bits: int, level: int):
    p = getPrime(bits)
    M = random_matrix(Zmod(p), LEN).matrix_from_rows_and_columns(range(LEN), range(LEN-level))
    c = vector(GF(p), m) * M
    return {"p": p, "M": M.list(), "c": c.list()}

def groebner_challenge(m,e):
    p = getPrime(1024)
    s = sum(m)
    c = [pow(m[i],e[i],p) for i in range(3)]
    c.insert(0,s)
    c.insert(0,p)
    return c

key = os.urandom(LEN)
Get_key = challenge(key,256,0x10)

S_bytes = scissors(flag)
C_bytes = ArrayXor(S_bytes,key)
C_long  = LongArray(C_bytes)

groebner_challenge = groebner_challenge(C_long,e)

with open('keyTask.chall', 'w') as f:
    f.write(f"{Get_key}")

with open('groebnerTask.chall','w') as f:
    f.write(f"{groebner_challenge}")

然后还有两份数据文件，较长就不写出来了，有需要的师傅可以找我要。

简单描述一下题目任务：

• 生成一个长度为32的随机字节串key，并进入challenge
• challenge中，将key按字节拆成1x32的向量m，同时生成一个32x16的随机矩阵M以及随机素数p，并返回M以及模p下mM的计算结果c
• 将flag拆成三等分的字节串，每一部分均与key异或得到C_bytes，并转为列表C_long
• 对C_long进行groebner_challenge并返回结果

所以其实题目主要也就分为两部分，一部分解challenge得到key，一部分解groebner_challenge得到C_long，然后异或就有flag，因此我的wp也分两部分阐述。

challenge

这一部分主要在于key对应的m向量是按字节拆分，也就是说在模p下都是很小的量，所以可以用格规约出key，具体如何构造格可以见我写的这一篇中的Matrix一题的challenge3，是一模一样的：

Crypto趣题-Lattice | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

groebner_challenge

这一部分给了以下几组模等式：

$$m_0^{e_0} \equiv c_0 \quad(mod\;p)$$ $$m_1^{e_1} \equiv c_1 \quad(mod\;p)$$ $$m_2^{e_2} \equiv c_2 \quad(mod\;p)$$

其中mi就是我们需要求出的C_long中的三部分，除此之外还给出了两个信息，一个是mi的和：

$$m_0 + m_1 + m_2 = s$$

另一个是三个e满足的方程：

$$e_i^3 - 10e_i^2 + 3*e_i - 30==0$$

那么求解这个三次方程可以得到三个根5，3，2，那么我们对所有可能的3^3种e的组合分别求groebner，就会发现在分别取2，3，5的时候可以求出mi，然后异或key就能得到flag了。

exp：

from Crypto.Util.number import *

#part1 get key
Get_key = 
p,M,c = Get_key["p"],Get_key["M"],Get_key["c"]

MM = matrix(ZZ,32,16,M)
E = diagonal_matrix([1]*32)
P = diagonal_matrix([p]*16)
C = matrix(ZZ,c)
L = block_matrix(ZZ,[[MM,E],[P,0],[C,0]])
ML = L.LLL()
key = list(ML[1][16:])
for i in range(len(key)):
    key[i] = abs(key[i])
key = bytes(key)

#part2 get e
PR.<i> = PolynomialRing(ZZ)
f = i^3 - 10*i^2 + 31*i - 30
res = f.roots()
e = [i[0] for i in res]


#part3 get C_long
groebner_challenge = [175336555462486363373099551411803174933803940918372428249159666803182759268063415863987676455854054651631174131625763475189413468427467197699058719725221879406119373683175842618465694427132003565774900609456204965408254598477034791500576573579131820364396996254469692964946065509325801687720344376041097328929, 192597139210277682598060185912821582569043452465684540030278464832244948354365, 5415723658972576382153559473862560277755192970021711034483296770242757614573901416501357332661976379693731699836578087114136761491831672836130172409491889, 210713951733721296094981135225517096332793112439184310028590576805069783972692891743044656754643189870169698041576462365740899368554671164493356650858567594970345928936103914826926922045852943068526737627918609421198466329605091625, 93558120697660628972553751937347865465963385519812302371069578286123647411810258547153399045605149278436900736665388355004346922404097196048139360206875149390218160164739477798859206611473675859708579299466581718543909912951088772842957187413726251892347470983848602814387339449340072310561011153714207338630]
p,s,c = groebner_challenge[0],groebner_challenge[1],groebner_challenge[2:]

PR.<x1,x2,x3> = PolynomialRing(Zmod(p))
f1 = x1+x2+x3-s
f2 = x1^e[2]-c[0]
f3 = x2^e[1]-c[1]
f4 = x3^e[0]-c[2]
F = [f1,f2,f3,f4]
res = Ideal(F).groebner_basis()
#print(res)
C_long = [175336555462486363373099551411803174933803940918372428249159666803182759268063415863987676455854054651631174131625763475189413468427467197699058719725221879406119373683175842618465694427132003565774900609456204965408254598477034791426984973114319422168794550068252297864611570239554629678043272534782205132762,175336555462486363373099551411803174933803940918372428249159666803182759268063415863987676455854054651631174131625763475189413468427467197699058719725221879406119373683175842618465694427132003565774900609456204965408254598477034791441070070348726882479628953871755257672217743797421672257560044812378339845544,175336555462486363373099551411803174933803940918372428249159666803182759268063415863987676455854054651631174131625763475189413468427467197699058719725221879406119373683175842618465694427132003565774900609456204965408254598477034791441077538064071473846707298910579940788965430025316563097279250948717798654116]
for i in range(3):
    C_long[i] = p - C_long[i]

#part4 get flag
def xor(a, b):
    return bytes([a[i%len(a)] ^^ b[i%len(b)] for i in range(max(len(a), len(b)))])

def ArrayXor(a:list,b:bytes):
    return [xor(a[i],b) for i in range(len(a))]

for i in range(3):
    C_long[i] = long_to_bytes(C_long[i])
S_bytes = ArrayXor(C_long,key)

flag = b""
for i in S_bytes:
    flag += i[:12]
print(flag)

#SYC{You_are_really_algebra_master}

GoGoCrypto

题目描述：

题目链接：http://47.109.106.62:7842/ 带上你的web队友，拿下这道crypto web 题吧！（允许小范围爆破）

题目文件很多，全部放在wp里有点长，需要的师傅找我要就可以了。解题要用到的主要的两个go文件如下：

publicController.go：

package Controller

import (
	"GoCode/myfunc"
	"github.com/gin-gonic/gin" 
	"net/http"
	"encoding/base64"
	"fmt" 
)

type PubController struct {
}

var sid []byte 
var key []byte 
var iv []byte 
var nonce []byte 
var pwd string  

func SendJsonBack(feedback string, check string, c *gin.Context) {
	messageMap := map[string]interface{}{
		"msg":   feedback,
		"check": check,
	}
	c.JSON(http.StatusOK, messageMap)
}

func (pc PubController) Router(pr *gin.Engine) {
	pr.GET("/", pc.Room)
	pr.POST("/api/dec", pc.MyDec) 
	pr.POST("/api/check", pc.CheckPwd)
}

func (pc PubController) Room(c *gin.Context) {
	sid = Myfunc.GetRandBytes(16) 
	key = Myfunc.GetRandBytes(16) 
	iv = Myfunc.GetRandBytes(16) 
	nonce = Myfunc.GetRandBytes(16) 

	token, _ := Myfunc.AESEnc(sid, key, iv) 
	c.SetCookie("token", base64.StdEncoding.EncodeToString(token), 0, "/", "", true, true) 
	c.SetCookie("nonce",base64.StdEncoding.EncodeToString(nonce) , 0, "/", "", true, true) 
	fmt.Println("token:", base64.StdEncoding.EncodeToString(token))	
	c.HTML(http.StatusOK, "index.html", gin.H{"ping": "pong"}) 

}

func(pc PubController) MyDec(c *gin.Context) {
	var feedback string 
	var check string 


	Rec_err := c.PostForm("Rec") 
	fmt.Println("Rec:", Rec_err) 
	Rec, err := base64.StdEncoding.DecodeString(Rec_err) 
	if err != nil {
		check = "false" 
		feedback = "Try again." 
		SendJsonBack(feedback, check, c) 
		return 
	}

	Pt_err, err := Myfunc.AESDec(Rec, key, iv) 
	//
	if err != nil || base64.StdEncoding.EncodeToString(Pt_err) == base64.StdEncoding.EncodeToString(sid){
		check = "false" 
		feedback = "Don't try to fool me! Try again." 
		SendJsonBack(feedback, check, c) 
		return 
	}
	check = "true" 
	feedback = "Access Accepted."  
	Pt := base64.StdEncoding.EncodeToString(Pt_err) 
	fmt.Println("(DEBUG)Pt: ", Pt) 
	nonce_hash := Myfunc.Hash(nonce) 
	pwd = Pt+nonce_hash
	fmt.Println("pwd: ",pwd)
	SendJsonBack(feedback, check, c) 
	
}

func(pc PubController) CheckPwd(c *gin.Context) {
	var feedback string 
	var check string 

	Rec := c.PostForm("Password")
	if pwd == "" {
		check = "false" 
		feedback = "Give me your token first." 
		SendJsonBack(feedback, check, c) 
		return  
	}
	if Rec == pwd {
		check = "true" 
		feedback = "Your flag is: SYC{AL3XEI_FAKE_FLAG}" 
	} else {
		check =  "false" 
		feedback = "Oops! Please try again." 
		
	}
	SendJsonBack(feedback, check, c) 

}

myfunc.go：

package Myfunc 

import (
    "crypto/aes"
    "crypto/cipher"
    "crypto/rand"
    "bytes"
	"crypto/sha512" 
	"encoding/base64" 
	"fmt"
)

func check(err error) {
    if err != nil {
        panic(err) 
    }
}

func GetRandBytes(n int) []byte {
	res := make([]byte, n) 
	_, e := rand.Read(res) 
	check(e) 
	return res 
}

func Pad(pt []byte) []byte {
	padlen := aes.BlockSize - (len(pt) % aes.BlockSize) 
	padding := bytes.Repeat([]byte{byte(padlen)}, padlen) 
	return append(pt, padding...) 
}

func Unpad(pt []byte) []byte {
	padlen := int(pt[len(pt)-1]) 
	return pt[:len(pt)-padlen] 
}

func AESEnc(pt []byte, key []byte, iv []byte) ([]byte, error) {
	block, e := aes.NewCipher(key) 
	if e != nil {
		return nil, e 
	}
	pt_ := Pad(pt) 
	fmt.Println("(DEBUG) pt_: ", pt_)
	ct := make([]byte, len(pt_)) 
	m := cipher.NewCBCEncrypter(block, iv) 
	m.CryptBlocks(ct, pt_) 
	
	return ct, nil 

}

func AESDec(ct []byte, key []byte, iv []byte) ([]byte, error) {
	block, e := aes.NewCipher(key) 
	if e != nil {
		return nil, e
	}
	m := cipher.NewCBCDecrypter(block, iv) 
	pt_ := make([]byte, len(ct)) 
	m.CryptBlocks(pt_, ct) 
	
	return Unpad(pt_), nil 

}

func Hash(nonce []byte) string{
	h := sha512.New() 
	h.Write(nonce) 
	nonce_hash := base64.StdEncoding.EncodeToString(h.Sum(nil)) 
	return nonce_hash 
}

事实上我一点也不懂web，但是丢给chatgpt+问web队友很轻松就能大概搞清楚每个函数的意思。简单描述一下题目任务，有三个访问接口如下：

func (pc PubController) Router(pr *gin.Engine) {
	pr.GET("/", pc.Room)
	pr.POST("/api/dec", pc.MyDec) 
	pr.POST("/api/check", pc.CheckPwd)
}

• 访问Room方法，我们可以从Cookie中得到token和nonce的值，token是sid经AES加密后的值；

• 访问MyDec方法，我们可以用post方式发送一个base64串让服务器解密，服务器正确解密后会检查解密结果是否等于sid，如果不相等则通过检查，并将解密后的结果连接上nonce的sha512值，作为pwd

• 访问CheckPwd方法，我们可以发送一个base64串，服务器base64解码后检查结果与pwd相等，则可以获得flag

接下来看看怎么解题。首先，pwd的后半部分，也就是nonce的sha512值我们是可以获得的，因此主要要想的办法是如何去得到pwd的前半部分Pt，也就是MyDec中的AES解密结果。

然后我的做法也很简单，注意到AES解密后一定会unpad，而myfunc中的pad和unpad是pkcs#7的标准填充方式，而我们利用的点也主要在于unpad函数：

func Unpad(pt []byte) []byte {
	padlen := int(pt[len(pt)-1]) 
	return pt[:len(pt)-padlen] 
}

可以看到它解填充时，只用最后一个字节的值当作填充长度，这对于标准填充过的密文来说，这样解填充当然是没问题的，但是如果不是标准填充过后的密文就会产生问题，这是因为在MyDec中我们可以发送任何base64串，只要他能正确AES解密，并且解密结果不等于sid(也就是token的解密值)，服务器就会把解密结果Pt当作pwd的前一部分。

方法一

也就是说，我们发送任意16字节密文的base64串，服务器应该都能AES解密出16字节明文并解填充，得到最终的Pt。而如果我们可以使解密出的最后一字节值恰为16，那么根据unpad的方式，Pt最终将会是一个空串，所以pwd其实就是nonce的sha512值，所以我们发送nonce的sha512值过去check就能得到flag。

至于如何使解密出的最后一字节值恰为16，我的方法是直接生日攻击就好，一次有1/256的概率成功，那么爆破256次就有大于50%的概率成功。

exp：

import requests
from urllib.parse import unquote
from base64 import *
from hashlib import sha512
from Crypto.Util.number import *
from tqdm import *

base_url = "http://47.109.106.62:7842/"

#part1 get nonce
response = requests.get(base_url + "/")

if response.status_code == 200:
    cookies = response.cookies
    token_cookie = cookies.get("token")
    nonce_cookie = cookies.get("nonce")

    token = unquote(token_cookie)
    nonce = unquote(nonce_cookie)

    print("Token:", token)
    print("Nonce:", nonce)
nonce_hash = b64encode(sha512(b64decode(nonce)).digest())

#part2 get flag
randombytes = b"0" * 15
for i in trange(256):
    #get pwd
    temp = randombytes + long_to_bytes(i)
    temp = b64encode(temp)
    data = {"Rec": temp}
    response = requests.post(base_url + "api/dec", data=data)

    #get flag
    data = {"Password": nonce_hash}
    response = requests.post(base_url + "api/check", data=data)
    if("Oops!" not in response.text):
        print(response.text)
        break

#SYC{N0t_S0_E45y_Cryp0W3b}

方法二

可以发现刚才的方法是完全没用到token的，而如果用上token，我们则可以完全不爆破。思路就是：sid本身是个16字节的值，所以AES加密前会被填充为下面的形式：

sid + b"\x10"*16

而又因为是CBC模式加密，所以我们用字节翻转攻击，改变第一组明文的最后一字节，从而实现把最后一个解密出的字节从16改成32，这样解填充的Pt也为空串。

exp：

import requests
from urllib.parse import unquote
from base64 import *
from hashlib import sha512
from Crypto.Util.number import *

base_url = "http://47.109.106.62:7842/"

#part1 get token&nonce
response = requests.get(base_url + "/")

if response.status_code == 200:
    cookies = response.cookies
    token_cookie = cookies.get("token")
    nonce_cookie = cookies.get("nonce")

    token = unquote(token_cookie)
    nonce = unquote(nonce_cookie)

    print("Token:", token)
    print("Nonce:", nonce)
nonce_hash = b64encode(sha512(b64decode(nonce)).digest())

#part2 get flag
token1,token2 = b64decode(token)[:16],b64decode(token)[16:]
token1 = token1[:-1] + long_to_bytes((token1[-1] ^ 16 ^ 32))
temp = b64encode(token1+token2)
data = {"Rec": temp}
response = requests.post(base_url + "api/dec", data=data)

#get flag
data = {"Password": nonce_hash}
response = requests.post(base_url + "api/check", data=data)
print(response.text)

#SYC{N0t_S0_E45y_Cryp0W3b}