WMCTF2021Crypto WriteUp. - writeup | De3B4t0 = Great-Station = Come on!Let us do it!

一次没什么人在打的WMCTF不过题目质量nb,不过我还是只有一个血其他都是第四第五个解出来的qwq...总体是第二个ak crypto的.还行...

# checkin

Backpack..
就试试看二进制下的 backpack 然后对应做发现就其实 0b 下对应位相差是 0 和 1 相差的话就是相同的值，就应该是 state. 然后差不多就传 100 的时候让你传 flag 然后发现差不多直接做吧。

	from os import stat
	import requests
	from bs4 import BeautifulSoup
	import random
	url = "http://47.104.243.99:10000/show.php"

	def getdata(msg):
	data = {
	"rp": msg
	}
	r = requests.post(url, data=data)
	Soup = BeautifulSoup(r.text, 'lxml')
	all_p = Soup.find_all('p')
	return (all_p)

	flag = int(str(getdata("flag")[1]).split(":")[1].strip('</p>'))
	print(flag)#1620418829165478
	'''

	print(bin(101))
	print(bin(102))
	print(bin(103))
	s = state[2] - state[1]
	print(s)
	print(state[2] - state[0])
	news = []
	news.append(state[2] - state[0])
	news.append(state[2] - state[1])
	print(state[0b1101100-101]-state[0b1101000-101])
	print(state[0b1101101-101]-state[0b1101001-101])

	'''

	flag = int(str(getdata("flag")[1]).split(":")[1].strip('</p>'))
	base = 0b10000000000000000000000000000000000000000000000
	base_num = (int(str(getdata(base)[1]).split(":")[1].strip('</p>')))
	new_state = []
	for i in range(32):
	tmp = 1<<i
	new_state.append(int(str(getdata(base\|tmp)[1]).split(":")[1].strip('</p>')) - base_num)
	print(new_state)
	'''
	new_state =[97005071980911, 32652300906411, 73356817713575, 108707065719744, 103728503304990, 49534310783118, 53330718889073, 2121345207564, 46184783396167, 115771983454147, 64261597617025, 2311575715655, 56368973049223, 84737125416797, 24316288533033, 82963866264519, 101019837363048, 25996629336722, 41785472478854, 68598110798404, 40392871001665, 94404798756171, 54290928637774, 112742212150946, 91051110026378, 124542182410773, 40388473698647, 22059564851978, 57353373067776, 80692115733908, 84559172686971, 28186390895657, 97005071980911, 32652300906411, 73356817713575, 108707065719744, 103728503304990, 49534310783118, 53330718889073, 2121345207564, 46184783396167, 115771983454147, 64261597617025, 2311575715655, 56368973049223, 84737125416797, 24316288533033, 82963866264519, 101019837363048, 25996629336722, 0, 68598110798404, 40392871001665, 94404798756171, 54290928637774, 112742212150946, 91051110026378, 124542182410773, 40388473698647, 22059564851978, 57353373067776, 80692115733908, 84559172686971, 125191462876568]
	'''
	from sage.all import*
	nbit = len(new_state)
	A = Matrix(ZZ, nbit + 1, nbit + 1)
	for i in range(nbit):
	A[i, i] = 1
	# replace the bottom row with your public key
	for i in range(nbit):
	A[i, nbit] = new_state[i]
	# last element is the encoded message
	A[nbit, nbit] = -int(flag)

	res = A.LLL()
	for i in range(0, nbit + 1):
	# print solution
	M = res.row(i).list()
	nnn = True
	for m in M:
	if m != 0 and m != 1:
	nnn = False
	break
	if nnn:
	print(i, M)
	M = ''.join(str(j) for j in M)
	M = (int(M[::-1], 2))
	print(M)
	print(getdata(M))

# baby_ocb

构造 tag 任意解密吧，emmm 就拿之前的脚本我发现就可以直接日（
其实就可以直接看到是 tag 和 header 异或了，那么我们可以通过之前的 my_pmac 计算出来我们的对应的 from admin 和 from baby 是啥。
直接异或就可以了

exp

	from pwn import *
	from Crypto.Util.number import *
	from hashlib import sha256
	import string
	from pwnlib.util.iters import mbruteforce
	import base64
	#context.log_level = 'debug'

	xor = lambda s1 , s2 : bytes([x1^x2 for x1,x2 in zip(s1,s2)])
	table = string.ascii_letters+string.digits

	def times2(input_data,blocksize = 16):
	assert len(input_data) == blocksize
	output = bytearray(blocksize)
	carry = input_data[0] >> 7
	for i in range(len(input_data) - 1):
	output[i] = ((input_data[i] << 1) \| (input_data[i + 1] >> 7)) % 256
	output[-1] = ((input_data[-1] << 1) ^ (carry * 0x87)) % 256
	assert len(output) == blocksize
	return output

	def times3(input_data):
	assert len(input_data) == 16
	output = times2(input_data)
	output = xor_block(output, input_data)
	assert len(output) == 16
	return output

	def back_times2(output_data,blocksize = 16):
	assert len(output_data) == blocksize
	input_data = bytearray(blocksize)
	carry = output_data[-1] & 1
	for i in range(len(output_data) - 1,0,-1):
	input_data[i] = (output_data[i] >> 1) \| ((output_data[i-1] % 2) << 7)
	input_data[0] = (carry << 7) \| (output_data[0] >> 1)
	# print(carry)
	if(carry):
	input_data[-1] = ((output_data[-1] ^ (carry * 0x87)) >> 1) \| ((output_data[-2] % 2) << 7)
	assert len(input_data) == blocksize
	return input_data

	def xor_block(input1, input2):
	assert len(input1) == len(input2)
	output = bytearray()
	for i in range(len(input1)):
	output.append(input1[i] ^ input2[i])
	return output

	def hex_to_bytes(input):
	return bytearray(long_to_bytes(int(input,16)))

	def pow():
	io.recvuntil(b"XXXX+")
	suffix = io.recv(16).decode("utf8")
	io.recvuntil(b"== ")
	cipher = io.recvline().strip().decode("utf8")
	proof = mbruteforce(lambda x: sha256((x + suffix).encode()).hexdigest() ==
	cipher, table, length=4, method='fixed')
	io.sendline(proof.encode())

	def get_FLAG_data():
	io.recv()
	io.sendline(b'3')
	io.recvuntil(b'ciphertext: ')
	ciphertext = base64.b64decode(io.recvline()[:-1])
	io.recvuntil(b'tag: ')
	tag = base64.b64decode(io.recvline()[:-1])
	nonce = b'\x00'*16
	associate_data = b'from admin'
	return ciphertext,tag,nonce,associate_data

	def Server_Enc(msg,nonce):
	io.recv()
	io.sendline(b'1')
	io.recv()
	io.sendline(base64.b64encode(nonce))
	io.recv()
	io.sendline(base64.b64encode(msg))

	associate_data = b'from baby'
	io.recvuntil(b'ciphertext: ')
	ciphertext = base64.b64decode(io.recvline()[:-1])
	io.recvuntil(b'tag: ')
	tag = base64.b64decode(io.recvline()[:-1])

	return ciphertext,tag

	def Server_Dec(nonce,cip,tag,associate_data):
	io.recv()
	io.sendline(b'2')
	io.recv()
	io.sendline(base64.b64encode(nonce))
	io.recv()
	io.sendline(base64.b64encode(cip))
	io.recv()
	io.sendline(base64.b64encode(tag))
	io.recv()
	io.sendline(base64.b64encode(associate_data))
	io.recvuntil(b'plaintext: ')
	plaintext = base64.b64decode(io.recvline()[:-1])
	return plaintext

	def get_my_enc(msg):
	nonce = bytearray(os.urandom(16))
	fake_m = bytearray(b'\x00'15+b'\x80'+b'\x00'16)
	cip,tag = Server_Enc(fake_m,nonce)
	m0 = bytearray(b'\x00'*15+b'\x80')
	m1 = bytearray(b'\x00'*16)

	c0 = cip[:16]
	c1 = cip[16:]

	enc = xor_block(Server_Dec(nonce,xor_block(c0,m0),c1,b""),m0)
	A = back_times2(enc)
	B = enc
	C = xor_block(B,c0)

	msg = msg
	new_nonce = xor_block(B,m0)
	new_msg = xor_block(msg,times2(C)) + m1
	new_msg = (bytes(new_msg))
	ENC,TAG = Server_Enc(new_msg,new_nonce)

	#io.interactive()
	return xor_block(ENC[:16],times2(C))

	def my_pmac(header, blocksize = 16):
	assert len(header)
	m = int(max(1, math.ceil(len(header) / float(blocksize))))
	offset = get_my_enc(bytearray([0] * blocksize))
	offset = times3(offset)
	offset = times3(offset)
	checksum = bytearray(blocksize)
	for i in range(m - 1):
	offset = times2(offset)
	H_i = header[(i * blocksize):(i * blocksize) + blocksize]
	assert len(H_i) == blocksize
	xoffset = xor_block(H_i, offset)
	encrypted = get_my_enc(xoffset)
	checksum = xor_block(checksum, encrypted)
	offset = times2(offset)
	H_m = header[((m - 1) * blocksize):]
	print(H_m)
	assert len(H_m) <= blocksize
	if len(H_m) == blocksize:
	offset = times3(offset)
	checksum = xor_block(checksum, H_m)
	else:
	H_m = H_m + b'\x80'
	while len(H_m) < blocksize:
	H_m += b'\x00'
	assert len(H_m) == blocksize
	checksum = xor_block(checksum, H_m)
	offset = times3(offset)
	offset = times3(offset)
	final_xor = xor_block(offset, checksum)
	auth = get_my_enc(final_xor)
	return auth

	if __name__ == "__main__":
	io = remote("47.104.243.99",10001)
	pow()
	F_ciphertext,F_tag,F_nonce,F_associate_data = get_FLAG_data()

	print(len(F_ciphertext))
	FROMADMIN = my_pmac(b'from admin')
	print(FROMADMIN)
	FROMBABY = my_pmac(b'from baby')
	print(FROMBABY)
	F_associate_data = b'from baby'
	F_tag = xor_block(xor_block(F_tag, FROMADMIN),FROMBABY)

	print(Server_Dec(F_nonce,F_ciphertext,F_tag,F_associate_data))
	io.interactive()

# ezlsb

$isPrime(a+2)$

get_Prime :

$suffix(2^{368})\\ isPrime(a^2+siffix+1+2k)$

generate:

$q = key^2+sx_1+1+2k_1\\ p = r^{2}+sx_2+1+2k_2\\ n = pq = r^2key^2+(sx_1+1+2k_1)r^2+(sx_2+1+2k_2)key^2 + (1+2k_1+sx_1)(1+2k_2+sx_2)$

Airdrop:

$q = a^2+sx_1+1+2k_1\\ p = r^2+sx_2+1+2k_2\\ gift = pq =r^2a^2+(sx_1+1+2k_1)r^2+(sx_2+1+2k_2)a^2 + (1+2k_1+sx_1)(1+2k_2+sx_2)$

Hint：给你 n,e,c

Leak:
给你 p,e,c 可以尝试让他是实现一个 p%4==3 然后去每个按下面这条平方根分解

$m = c^{(p+1)//4}\mod p$

Backdoor:
就拿到 password 就可以了。

Main：

$a=getPrime(512)\\ p =a^2+sx_1+2k_1+1\\ q = b^2 + sx_2+2k_2+1\\ n=pq\\ e=0x10001\\ pass = pass^e\mod n\\$

4 次 Airdrop 的机会分解 n

$gift_1 =q_1a^2+q_1r_1\\ gift_2 =q_2a^2+q_2r_2\\ gift_3 =q_3a^2+q_3r_3\\ gift_4 =q_4a^2+q_4r_4$

$n=qa^2+qr$

r 和 b 是 512 位素数 sx 是 368 位素数 https://martinralbrecht.wordpress.com/2020/03/21/the-approximate-gcd-problem/
感觉是 agcd 的加强版

拿一组数据去得到 password
对所有的 n 和 gift 进行开方之后发现其实就是上面这个 agcd 的东西了（ lambda 就是 384, 可以直接拿 a
拿到 a 之后就能用 coppper 去分解 n 了
发现后面拿到的 p 的 phi 和 4096gcd 一下只有 2，就可以 inverse 之后再有限域开平方。直接是不行的然后就用 p - 拿到的值。

	from Crypto.Util.number import *

	n = 47935439323457127833037357083983237496878689261127081988649381912739468031720632155196797632254382181519984640185516509133478757768213513987941266551218952702606511178276633908546681835137035411034761316782876147359960487121213984853077540707588650724919247893999205747065241005931759522778403309142776013266993947909627871209547322186129461944966954255478452004126991923307040855781751576009560486080068518925411003611155913186594087392942825850544717133800805624006483035224985413873703244911627183839595554490748948155205230203576672211733145725061218786720271669259766573150046403742640731305478008090581342450251
	c = 3919344937892382453030977567508693676032303846339768189327551099374946365060960690768609451174592443590215485748150561581950399880588830921746078740240411900651523182948715415984890388869890625266181130509341855855926592096861408547012789662424413990132921065901887989126066338526922430576216968899218768929718135909294604392991675565238263427980279809833873727879908414057057251514599614783087363407160259495649433827508201133578753184878878951808963235285802411560617758684149245785926009513999665737813112781227632184408328506347530201548662504337685327938279816153782173263392272482010848912768570644687383402740
	e = 0x10001
	import gmpy2
	gift = [n,44990368188010733918858560274483758890181415269493297111432503547349003225605998615045785893226033910128870030617267155471810954946701223520640922021975809987807505611903409246795611631098996240773157768116757200113829094343552868816290020352831816362796203792491207823175523672191727528508633850619433949770456610363882692306556232795718586073455551690290817146381615597057233415356702398751201147360489923331479498200944380380485186742204102241268627281885440725091810845139220728878887230186802227055200861696153582625239928130166788950797548542788617056657074111819043054568673588056230147076007178129781162831611, 78683096763326373669536693596249569085095290247102968419967840631586829732977219369969300751984289814402998022338838702200385790818392667580904195251832143834204909181557079203022588554330880322720341355019524178584242950915453525665150758590809948785874945747350388081180350115247240154475291948408741761648481087095447887536869026145459137082976669264740463624475908502268200243221926503732189641142315206390638626198685135408561463549566690400552904111413732721731304453362155831880117750312809828284867777234323889613356325170410656020466019958496069321445323099847122674429896323552643458809760407340317926830901, 155378045723411522600696035951116955917841229585849918356678240504530602921920566960136486129553454017727749961462685165377347755302826839915112915642536853507763599097574159709699129520153090998679336513853206496584404340204651266745291554668873684828162763771988162464321539837322058407795741726134977433737336303715635638805865795180826546489644742166424956313290523391862752963123672824271036686045932898668866001588000885565313392223064341062105415322004215058987783863547389257154167383707353247208122517429835580960973747381235079792989510459208038145580319784674535377716228024727145018179341727746440515438603, 145996826337300053358889785500361366816465399568166384938579711772423913668332754495063912415488340254571832698805395656780786821255846897561093531075917438583833034671829076937376980928330090827535202591154261056743308762095398623323354628401868490174767786058940272278982366625466222310654778128867887749716594188776848527274133080300896292575037380431855075174589507467705421620952488239054607980417485378752030675364661643727200369011640293898438494036260460375174641137939853447480714174584002881316581265441151705735968822426191526020807499157273552559963397713746419094028547071420597530907758157846952075538021]
	G = []
	for i in gift:
	G.append(gmpy2.iroot(i,2)[0])
	from sage.all import *

	M = Matrix(ZZ,4+1,4+1)
	for i in range(4):
	M[i+1,i+1] = -G[0]
	for i in range(4):
	M[0,i+1] = G[i+1]

	M[0,0] = 2** (368)
	P=M.LLL()[0]
	P0 = (abs(P[0])//M[0,0])
	Q = [P0]
	#print((bin(P0)))

	for i in range(1,5):
	tmp = ((P[i]-P0*G[i])//G[0])
	Q.append(tmp)
	import gmpy2
	a = abs(G[0]//Q[0])
	print(a)
	'''
	N = 47935439323457127833037357083983237496878689261127081988649381912739468031720632155196797632254382181519984640185516509133478757768213513987941266551218952702606511178276633908546681835137035411034761316782876147359960487121213984853077540707588650724919247893999205747065241005931759522778403309142776013266993947909627871209547322186129461944966954255478452004126991923307040855781751576009560486080068518925411003611155913186594087392942825850544717133800805624006483035224985413873703244911627183839595554490748948155205230203576672211733145725061218786720271669259766573150046403742640731305478008090581342450251
	pbar = 15606058170269190953682935674386408585241503399431015536676436247560293934016890029594865561178385431706188686337043777633715364517948170845087640826845217
	ZmodN = Zmod(N)
	P.<x> = PolynomialRing(ZmodN)
	f = pbar**2 + x
	x0 = f.small_roots(X=2^368, beta=0.1,epsilon = 0.01)
	p = pbar + x0[0]
	print("p: ", p)
	243549051613825768264099803511229671296850562269513049496935511304072171908221622373325530141385783545202972578556352456412692718100967837804917914686772005951461971082613057233161910519390099300130916541889963526259281974154202935031489884213351283127857066122909931059096582655197258061167540446985751813009
	'''
	p = 243549051613825768264099803511229671296850562269513049496935511304072171908221622373325530141385783545202972578556352456412692718100967837804917914686772005951461971082613057233161910519390099300130916541889963526259281974154202935031489884213351283127857066122909931059096582655197258061167540446985751813009
	q = 47935439323457127833037357083983237496878689261127081988649381912739468031720632155196797632254382181519984640185516509133478757768213513987941266551218952702606511178276633908546681835137035411034761316782876147359960487121213984853077540707588650724919247893999205747065241005931759522778403309142776013266993947909627871209547322186129461944966954255478452004126991923307040855781751576009560486080068518925411003611155913186594087392942825850544717133800805624006483035224985413873703244911627183839595554490748948155205230203576672211733145725061218786720271669259766573150046403742640731305478008090581342450251//p
	phi = (p-1)*(q-1)
	d = inverse(0x10001,phi)
	print(long_to_bytes(pow(c,d,47935439323457127833037357083983237496878689261127081988649381912739468031720632155196797632254382181519984640185516509133478757768213513987941266551218952702606511178276633908546681835137035411034761316782876147359960487121213984853077540707588650724919247893999205747065241005931759522778403309142776013266993947909627871209547322186129461944966954255478452004126991923307040855781751576009560486080068518925411003611155913186594087392942825850544717133800805624006483035224985413873703244911627183839595554490748948155205230203576672211733145725061218786720271669259766573150046403742640731305478008090581342450251)))

	c = 26477776136511814537867182410042935036751631193394882824790793880743251563906439761929648379057880893788211246254847830996292172157860942596330440504204415170090503913269874666809421512135396019520075970999555199447275211351781765139220570319976413703772788491129400862990098026864762589440254742120432827191
	n = 462759013310826480654170350879608056333317185952185294792509715751354925534996431275210016348827150025558626490699228055937593844557693779418456113065581193070896452111537933875515496157080452283253231904539734791991415148758529596162008849892665895353050001859515122987866725231231752910748407229540350263791
	c1 = pow(c,inverse(4096,n-1),n)
	c2 = pow(c1,(n+1)//4,n)
	print(long_to_bytes(n-c2))

打交互

	from pwn import *
	from Crypto.Util.number import *
	from hashlib import sha256
	import string
	from pwnlib.util.iters import mbruteforce
	#context.log_level = 'debug'

	table = string.ascii_letters+string.digits

	def passpow():
	io.recvuntil(b"XXXX+")
	suffix = io.recv(16).decode("utf8")
	io.recvuntil(b"== ")
	cipher = io.recvline().strip().decode("utf8")
	proof = mbruteforce(lambda x: sha256((x + suffix).encode()).hexdigest() ==
	cipher, table, length=4, method='fixed')
	io.sendline(proof.encode())

	def get_gift():
	io.recv()
	io.sendline(b'1')
	io.recvuntil(b'gift: ')
	gift = int(io.recvline()[:-1])
	return gift

	def get_data():
	io.recv()
	io.sendline(b'3')
	io.recvuntil(b'n = ')
	n = int(io.recvline()[:-1])
	io.recvuntil(b'e = ')
	e = int(io.recvline()[:-1])
	io.recvuntil(b'c = ')
	c = int(io.recvline()[:-1])
	return n,e,c

	if __name__ == "__main__":
	io = remote("47.104.243.99",9999)
	passpow()
	n,e,c = get_data()
	print(n,c)
	gift = []
	for i in range(4):
	gift.append(get_gift())

	#print(gift)

	password = b'Cou1d_I_get_Th3_passw03d_then_captu7e_the_fla9?'
	io.sendline(b'2')
	io.recv()
	io.sendline(password)
	io.recvuntil(b'n = ')
	n = int(io.recvline()[:-1])
	e = 4096
	io.recvuntil(b'c = ')
	c = int(io.recvline()[:-1])
	print(c)
	print(n)
	io.interactive()

# ezl1ner

每次传输的值只能是 f0 的倍数

已经能拿到 f0 了.
每次左移一格（然后打过去，发现 key 我们是可以自己知道的拿到 f0 的时候，那么我们只需要去对他进行一次实现，拿个 key, 之后就是解矩阵方程了

https://baike.baidu.com/item/ 希尔密码 / 2250150?fr=aladdin

$secret*Key=C\mod q\\ secret=C*Key^-1\mod q$

	from pwn import *
	from Crypto.Util.number import *
	from hashlib import sha256
	import string
	from pwnlib.util.iters import mbruteforce

	q = 2**24
	tat = string.ascii_letters+string.digits

	def pass_pow():
	io.recvuntil(b"XXXX+")
	suffix = io.recv(16).decode("utf8")
	io.recvuntil(b"== ")
	ciphers = io.recvline().strip().decode("utf8")
	print(ciphers)
	proof = mbruteforce(lambda x: sha256((x + suffix).encode()).hexdigest() ==
	ciphers, tat, length=4, method='fixed')
	io.recv()
	io.sendline(proof)

	def get_init_data():
	n = int(io.recvline()[:-1])
	e = 0x10001
	io.recvuntil(b' only two chances.\n')
	c0 = int(io.recvline()[:-1])
	return n,e,c0

	def give_key(key,num):
	for i in range(15):
	io.recvuntil(b'key'+num+b':')
	io.sendline(str(key[i]).encode())
	io.recvuntil(b'here is your cipher:')
	cipher = eval(io.recvline()[:-1])
	return cipher

	def to_vec(num , length):
	vec = []
	while length > 0:
	vec = [num % q] + vec
	num //= q
	length -= 1
	return vec

	def vec_to_num(vec):
	num = 0
	for i in vec:
	num = num *q
	num = num + i
	return num

	def to_mat(numlist):
	M =[]
	for i in numlist:
	M.append(to_vec(i , 40))
	return M

	from sage.all import*
	if __name__ == "__main__":
	io = remote("47.104.243.99",31923)
	#io.interactive()
	pass_pow()
	#io = remote("192.168.50.123",10006)
	n,e,c0 = get_init_data()
	#1round

	key1 = []
	for i in range(15):
	c1 = (pow((1<<480) + 1 + (1<<(480+24i)) , e , n ) c0 ) % n
	key1.append( c1 )

	cipher1 = give_key( key1 , b'1')

	f0_vec = cipher1[20:]
	f0 = vec_to_num(f0_vec)

	key1_I_GIVE =to_mat([f0]+[(1<<(480+24i))f0 for i in range(15)])
	CC = Matrix(Zmod(q),[cipher1])
	KK = Matrix(Zmod(q),key1_I_GIVE)
	secret = (KK.solve_left(CC))

	print(secret)


	#2round
	cf0 = eval(io.recvline()[:-1])
	key2 = []
	for i in range(15):
	c2 = (pow((1<<480)2 + 1,e,n)cf0)%n
	key2.append(c2)

	cipher2 = give_key(key2,b'2')
	cf0_vec = cipher2[20:]
	cf0 = vec_to_num(cf0_vec)
	key2_I_GIVE =to_mat([(1)cf0]+[(1<<480)cf0 for i in range(15)] )
	#print(key2_I_GIVE)
	#print(cf0)
	CC = Matrix(Zmod(q),[cipher2])
	KK = Matrix(Zmod(q),key2_I_GIVE)
	#print(KK.solve_left(CC))
	sss = (secret[0])
	s = " ".join(str(i) for i in sss)
	print(s)
	io.sendline(s)
	io.interactive()

WriteUp

# checkin

# baby_ocb

# ezlsb

# ezl1ner

祥云杯2021Crypto Wp