Some Nearly Write Ups - writeup | De3B4t0 = Great-Station = Come on!Let us do it!

好久没更了水一下...

# 2021 年陕西省大学生网络安全技能大赛

# Give me num

无附件，只有打题目，连上之后是看到 LCG，
然后随机输数字都没有其他变化只有什么什么 Num 的东西，但是你可以弄到 n 次猜测他是给你数字然后去预测他的接下去的数
用一个脚本去爆破发现成立并且给了个 it's true 还是啥的接近这个意思，然后去反复尝试发现会断掉那就是收到了不同的东西开 debug 模式 30 层之后发现是 related message attack 直接就上脚本就出了。

from Crypto.Util.number import *
from pwn import *
from functools import reduce

if __name__ == "__main__":
    p = remote("129.226.4.186",7000)
    context.log_level = 'debug'
    data = []
    for i in range(6):
        p.recvuntil("num:")
        p.sendline("1")
        data.append(int(p.recvuntil("\n")[:-1]))

    delta = [d1 - d0 for (d0, d1) in zip(data, data[1:])]
    m_mul = [d0 * d2 - d1 * d1 for (d0, d1, d2) in zip(delta, delta[1:], delta[2:])]
    m = reduce(GCD, m_mul)


    m0,m1,m2,m3 = data[:4]
    a = (m2 - m1) * inverse(m1 - m0 , m) % m
    b = (m1 - a * m0) % m
    for i in range(30):
        p.recvuntil("num:")
        data.append((a*data[-1]+b)%m)
        p.sendline(str(data[-1]))
    p.interactive()

拿到：

it is true
30
cipher1=pow(m,e,n):
0x10652cdfaa84742a301254ad38685682db0723ead4a9696a391186333d2e18f1b1205385f3658c27818bcfb0bdb8b84f17b26ef267f93d08b9eef9791a7ce8ad98d4d0393b0df6696d9568caa712e5a2645ed74f758b378fd7f6f37e70248e46cd814d8b03da3287cea21a3f42a371adb565L
cipher2=pow(m+1,e,n):
0x10652cdfaa84742a301254ad38685682db0723ead4a9696a391186333d2e18f1b1205385f3660717240e2fd0a5b4a66b71329cab62c2cf4d5f3a706aeefd13c05993ce41f119bff6039327bd36bee9a01181bd366d4118ce3d8ce118dc84a3eb7e5497fa611a2c7c4811fa835faf4c1925f8L
N:
86556158206673268412999351099391537818771292689555971866425305353742222745803154706209551717854578357455003375422313884956087927511235887012764481212450066610311227919903117972157504258058310749942009463761100652057157343578534551749795505001379235681472026344861535746921918227188061252683055822118537612609
E:
3

接下去用 sagemath 就可以跑出来 m 了

def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]


if __name__ == '__main__':
    n = 86556158206673268412999351099391537818771292689555971866425305353742222745803154706209551717854578357455003375422313884956087927511235887012764481212450066610311227919903117972157504258058310749942009463761100652057157343578534551749795505001379235681472026344861535746921918227188061252683055822118537612609
    e = 3

    c1 =0x10652cdfaa84742a301254ad38685682db0723ead4a9696a391186333d2e18f1b1205385f3658c27818bcfb0bdb8b84f17b26ef267f93d08b9eef9791a7ce8ad98d4d0393b0df6696d9568caa712e5a2645ed74f758b378fd7f6f37e70248e46cd814d8b03da3287cea21a3f42a371adb565
    c2 = 0x10652cdfaa84742a301254ad38685682db0723ead4a9696a391186333d2e18f1b1205385f3660717240e2fd0a5b4a66b71329cab62c2cf4d5f3a706aeefd13c05993ce41f119bff6039327bd36bee9a01181bd366d4118ce3d8ce118dc84a3eb7e5497fa611a2c7c4811fa835faf4c1925f8
    diff = 1
    m1 = related_message_attack(c1, c2, diff, e, n)
    print("m1:", m1)

m1: 13040004482825757166149747768424026334639325666603913967492907164094589547731068248503236733
long_to_bytes 之后就拿到了 flag
flag{ffa5eaae11394fc8044a21fa920c19f8}

# 2021CISCN

# Move

根据题目可以看出是一个 copper 的...（bushi! 上次虎符也卡在这里了，不过写过一次 wp，我做了一会才发现这样子的。那就直接开始造格子

$\left[\begin{matrix} 2^{512}&e\\ 0&-n \end{matrix}\right]$

我们可以直接通过这个格基规约就得到了 x,y 剩下的看之前的 wp，就能解出来了，用的也是一种费马小定理的思想

[HFCTF2021Crypto Wp - d33b4t0's blog](https://d33b4t0.com/2021/04/09/HFCTF 2021 Crypto WP/)

	from Crypto.Util.number import*

	def add(p1, p2):
	if p1 == (0, 0):
	return p2
	if p2 == (0, 0):
	return p1
	if p1[0] == p2[0] and (p1[1] != p2[1] or p1[1] == 0):
	return (0, 0)
	if p1[0] == p2[0]:
	tmp = (3 * p1[0] * p1[0]) * inverse(2 * p1[1], n) % n
	else:
	tmp = (p2[1] - p1[1]) * inverse(p2[0] - p1[0], n) % n
	x = (tmp * tmp - p1[0] - p2[0]) % n
	y = (tmp * (p1[0] - x) - p1[1]) % n
	return (int(x), int(y))
	def mul(n, p):
	r = (0, 0)
	tmp = p
	while 0 < n:
	if n & 1 == 1:
	r = add(r, tmp)
	n, tmp = n >> 1, add(tmp, tmp)
	return r
	def factor(K,N):
	l = 0
	r = K
	for i in range(518):
	s = (l+r)//2
	v = ss - (9ss(K-1-s)(K-1-s)//(round(N0.25)round(N**0.25)))
	if v < 4*N:
	l = s
	else :
	r = s
	return r
	def gets():
	return [352349739892292322999330613117511489276791137416050590322561272098135764509812116210543232353192946492907441641899508311181782397967869533800138447935440769558784357373166666205853969428654899524304252899588626355058283586558885888,406850608655407486298019095013146348847805975120061760929682791882948049742096195978800022454159691659865169100330308708576847735609146508679126419372034710027124703842712262177437006326228856546452636094881051757653949488135598409]

	'''
	M = Matrix(ZZ,[[2**512,e],[0,-n]])
	M.LLL()[0]

	'''

	def getK():
	x = (-s[0])//(2**512)
	y = (e*x+s[1])//n
	K = (ex-ny)//y
	return K

	if __name__ == "__main__":
	n = 80263253261445006152401958351371889864136455346002795891511487600252909606767728751977033280031100015044527491214958035106007038983560835618126173948587479951247946411421106848023637323702085026892674032294882180449860010755423988302942811352582243198025232225481839705626921264432951916313817802968185697281
	e = 67595664083683668964629173652731210158790440033379175857028564313854014366016864587830963691802591775486321717360190604997584315420339351524880699113147436604350832401671422613906522464334532396034178284918058690365507263856479304019153987101884697932619200538492228093521576834081916538860988787322736613809
	c = (6785035174838834841914183175930647480879288136014127270387869708755060512201304812721289604897359441373759673837533885681257952731178067761309151636485456082277426056629351492198510336245951408977207910307892423796711701271285060489337800033465030600312615976587155922834617686938658973507383512257481837605, 38233052047321946362283579951524857528047793820071079629483638995357740390030253046483152584725740787856777849310333417930989050087087487329435299064039690255526263003473139694460808679743076963542716855777569123353687450350073011620347635639646034793626760244748027610309830233139635078417444771674354527028)
	s = gets()
	K = getK()
	S = factor(K,n)
	d = inverse(e,n+1+S)
	c = mul(d,c)
	print(long_to_bytes(c[0])+long_to_bytes(c[1]))

# ImageEncrypt

观察题目，我们可以得知

$enc1 \oplus enc2 = test \oplus plain$

那么接下去，我们就可以根据这个得到 plain 的前 256 位，之后就可以推得 ch 的大概和 key 的大概取值，一共出现了四个我们发现其中两个互为补数，那么就可以得到对应的 key1,key2, 去爆破一下很小的范围的 r, 于是我们可以爆破八次来排列组合，得到 key1 = 169,key2 = 78 , 于是得到了 r = 1.2 , 之后可以得知，random.random 函数出来的是 (0,1) 的六位小数，爆破一下也很快，出来 x = 0.840264 , 那么就直接可以发现 encrypt 函数其实是和 decrypt 函数一模一样，直接拿来用，就能得到 flag

	import hashlib
	test = [205, 237, 6, 158, 24, 119, 213, 32, 74, 151, 142, 186, 57, 28, 113, 62, 165, 20, 190, 37, 159, 137, 196, 44, 97, 37, 7, 222, 220, 95, 4, 66, 0, 28, 199, 142, 95, 105, 119, 232, 250, 215, 60, 162, 91, 211, 63, 30, 91, 108, 217, 206, 80, 193, 230, 42, 221, 71, 136, 115, 22, 176, 91, 57, 61, 3, 87, 73, 250, 121, 51, 72, 83, 120, 77, 199, 236, 190, 249, 116, 45, 6, 134, 110, 149, 94, 214, 232, 153, 213, 119, 98, 81, 203, 240, 114, 240, 29, 122, 188, 156, 53, 128, 185, 40, 147, 245, 204, 47, 101, 80, 229, 41, 150, 28, 195, 25, 235, 119, 6, 192, 8, 73, 255, 159, 172, 77, 94, 254, 104, 236, 219, 141, 91, 195, 162, 97, 56, 252, 173, 163, 43, 167, 214, 50, 73, 115, 190, 254, 53, 61, 77, 138, 192, 15, 4, 190, 27, 37, 108, 101, 135, 90, 215, 106, 243, 112, 111, 106, 89, 143, 150, 185, 142, 192, 176, 48, 138, 164, 185, 61, 77, 72, 0, 17, 203, 210, 71, 186, 49, 162, 250, 218, 219, 195, 63, 248, 220, 155, 180, 219, 132, 219, 94, 144, 247, 211, 95, 70, 227, 222, 31, 69, 24, 13, 216, 185, 108, 137, 57, 186, 211, 55, 27, 158, 241, 223, 21, 134, 106, 152, 127, 187, 245, 246, 131, 176, 177, 228, 100, 112, 11, 84, 61, 193, 42, 41, 69, 229, 145, 254, 138, 3, 153, 123, 31]
	enc1 = [131, 92, 72, 47, 177, 57, 131, 118, 4, 38, 192, 19, 119, 82, 63, 143, 235, 165, 15, 140, 209, 223, 117, 133, 47, 148, 81, 144, 138, 246, 173, 235, 177, 181, 110, 39, 9, 192, 57, 166, 180, 153, 141, 19, 234, 157, 142, 80, 234, 197, 151, 152, 249, 143, 176, 155, 147, 17, 57, 194, 191, 254, 13, 144, 140, 85, 25, 248, 172, 208, 154, 249, 5, 201, 27, 137, 69, 23, 175, 34, 156, 72, 208, 32, 195, 16, 127, 65, 207, 131, 57, 203, 7, 98, 89, 36, 65, 75, 211, 21, 45, 132, 214, 239, 102, 58, 68, 130, 97, 204, 225, 76, 152, 216, 74, 149, 79, 165, 198, 72, 150, 94, 7, 177, 46, 226, 252, 247, 79, 62, 69, 106, 60, 21, 106, 236, 47, 145, 170, 28, 18, 101, 14, 152, 131, 7, 37, 15, 168, 99, 115, 27, 220, 150, 89, 82, 232, 170, 107, 221, 212, 46, 235, 129, 36, 66, 217, 222, 36, 15, 217, 192, 247, 192, 113, 230, 129, 196, 13, 247, 148, 228, 225, 86, 71, 133, 132, 238, 236, 127, 11, 83, 107, 141, 114, 150, 182, 146, 213, 250, 141, 53, 114, 16, 198, 70, 133, 17, 247, 173, 136, 73, 236, 78, 188, 150, 239, 58, 199, 136, 11, 122, 134, 77, 47, 167, 137, 188, 55, 195, 41, 49, 245, 92, 160, 213, 254, 0, 85, 205, 193, 69, 2, 140, 143, 155, 127, 236, 179, 199, 168, 35, 85, 40, 45, 174]
	enc2 = [198, 143, 247, 3, 152, 139, 131, 84, 181, 180, 252, 177, 192, 25, 217, 179, 136, 107, 190, 62, 4, 6, 90, 53, 105, 238, 117, 44, 5, 116, 132, 195, 214, 171, 113, 209, 18, 31, 194, 174, 228, 212, 196, 14, 27, 41, 211, 56, 139, 135, 225, 214, 89, 122, 178, 212, 185, 231, 204, 150, 204, 212, 160, 142, 213, 173, 186, 166, 65, 238, 5, 32, 45, 31, 25, 189, 148, 38, 78, 79, 33, 56, 227, 48, 103, 163, 31, 189, 37, 124, 106, 249, 86, 188, 86, 233, 41, 250, 89, 7, 212, 234, 111, 104, 245, 102, 227, 96, 160, 67, 181, 13, 26, 192, 214, 210, 188, 84, 216, 215, 243, 72, 233, 2, 122, 166, 107, 251, 70, 128, 94, 190, 185, 210, 34, 85, 77, 29, 182, 77, 115, 208, 228, 252, 73, 198, 151, 70, 10, 97, 138, 235, 21, 117, 239, 102, 129, 2, 253, 80, 53, 61, 184, 220, 41, 82, 37, 140, 23, 143, 179, 53, 153, 113, 213, 211, 111, 197, 248, 65, 60, 69, 1, 81, 48, 254, 251, 89, 195, 8, 93, 190, 66, 174, 97, 175, 210, 191, 66, 112, 123, 128, 33, 230, 237, 104, 16, 192, 239, 173, 44, 10, 120, 231, 114, 151, 140, 63, 103, 44, 243, 222, 242, 73, 51, 46, 98, 137, 163, 152, 147, 95, 223, 3, 15, 112, 85, 215, 133, 131, 240, 239, 224, 195, 140, 124, 70, 156, 221, 241, 37, 245, 1, 99, 9, 157, 99, 150, 47, 118, 225, 16, 13, 141, 135, 99, 18, 119, 63, 160, 6, 247, 27, 68, 45, 199, 86, 193, 252, 21, 135, 32, 42, 103, 114, 241, 49, 249, 182, 52, 18, 155, 157, 61, 4, 246, 158, 52, 118, 242, 195, 54, 139, 232, 100, 31, 11, 233, 58, 100, 101, 137, 83, 145, 209, 7, 241, 96, 57, 148, 207, 29, 237, 124, 177, 166, 161, 20, 116, 122, 61, 71, 46, 82, 18, 157, 253, 130, 112, 66, 94, 57, 221, 243, 222, 192, 147, 5, 130, 201, 174, 26, 160, 16, 188, 103, 187, 11, 238, 182, 144, 4, 137, 33, 84, 100, 7, 239, 219, 83, 112, 189, 166, 58, 93, 141, 30, 198, 220, 196, 118, 172, 5, 45]
	s = []
	for i in range(16*16):
	s.append(test[i]^enc1[i]^enc2[i])
	keys = []
	for i in range(256):
	keys.append(((enc2[i]^s[i])&0xff))
	key1 = 169#78#177
	key2 = 78#86#169
	ch = ''
	for i in range(256):
	if keys[i] == key1:
	ch = ch + '00'
	elif keys[i] == (~key1)&0xff:
	ch = ch + '01'
	elif keys[i] == key2:
	ch = ch + '10'
	elif keys[i] == (~key2)&0xff:
	ch = ch + '11'
	bin_x = []
	for i in range(16):
	bin_x.append(int(ch[i16:i16+16],2))
	print(bin_x)
	def generate(x):
	return round(rx(3-x),6)
	tmp1 = bin_x[0]
	tmp2 = bin_x[1]
	'''
	for i in range(0,20):
	r = i/10
	x0 = str(tmp1 / 22000)[:8]
	for j in range(-10,10):
	tmpx = float(x0)+j/1000000
	tmpx = float(str(tmpx)[:8])
	x2 = generate(tmpx)
	if int(x2*22000) == tmp2:
	print(i)
	print(tmpx)
	'''
	r = 1.2

	def encrypt(pixel,key1,key2,x0,m,n):
	num = m*n//8
	seqs = []
	x = x0
	bins = ''
	tmp = []
	for i in range(num):
	x = generate(x)
	tmp.append(x)
	seqs.append(int(x*22000))
	for x in seqs:
	bin_x = bin(x)[2:]
	if len(bin_x) < 16:
	bin_x = '0'*(16-len(bin_x))+bin_x
	bins += bin_x
	assert(len(pixel) == m*n)
	cipher = [ 0 for i in range(m) for j in range(n)]
	for i in range(m):
	for j in range(n):
	index = n*i+j
	ch = int(bins[2index:2index+2],2)
	pix = pixel[index]
	if ch == 0:
	pix = (pix^key1)&0xff
	if ch == 1:
	pix = (~pix^key1)&0xff
	if ch == 2:
	pix = (pix^key2)&0xff
	if ch == 3:
	pix = (~pix^key2)&0xff
	cipher[index] = pix
	return cipher
	'''
	for i in range(10**6):
	s = encrypt(test,key1,key2,i/1000000,16,16)
	if enc1== s:
	print(i)
	'''
	x0 = 840264/1000000

	image = encrypt(enc2,key1,key2,x0,24,16)
	print(image)
	data = ''.join(map(chr,image))
	print(data)

	# 用 py2 的 md5 计算 data

# HOMO

观察题目，第一步就是过随机数，猜测后一位是啥，他给了 512 次机会，但是得 200 次才能过，同时 getrandbits (64) 得到的是两组随机数，并且先出现的在后面后来出现的在前面，那么我们就可以通过这个去 Crack 过掉这个。

	import math
	from pwn import*
	from randcrack import RandCrack
	from Crypto.Util.number import*

	q = 2**54
	n = 1024
	t = 83
	T = 100
	l = math.floor(math.log(q,t))
	delta = math.floor(q/t)
	mu = 0
	sigma = 1

	def get_homo_data():
	pk0 = io.recvline()[:-1]
	pk0 = [int(item) for item in pk0.strip(b'[]').split(b',')]
	pk1 = io.recvline()[:-1]
	pk1 = [int(item) for item in pk1.strip(b'[]').split(b',')]
	ct0 = io.recvline()[:-1]
	ct0 = [int(item) for item in ct0.strip(b'[]').split(b',')]
	ct1 = io.recvline()[:-1]
	ct1 = [int(item) for item in ct1.strip(b'[]').split(b',')]
	return pk0,pk1,ct0,ct1

	def pass_random():
	io.recv()
	io.sendline("1")
	data = []
	io.recv()
	for i in range(312):
	io.sendline('0')
	io.recvuntil("is ")
	data.append(int(io.recvuntil("\n")[:-1]))
	io.recv()
	data2 = []
	rc = RandCrack()
	for i in range(312):
	r = bin(data[i])[2:].zfill(64)
	rc.submit(int(r[32:],2))
	rc.submit(int(r[:32],2))
	for i in range(200):
	dataa = (rc.predict_getrandbits(64))
	io.sendline(str(dataa))
	io.recv()

接下去，就要去过掉这个 Homo 同态加密的东西... 看了看我们可以构造 ct0 和 ct1 使得他 decry 出来就是 flag，那就可以使得 ct0+q,ct1 也 + q，那么想法成立

	def pass_homo():
	io.sendline("2")
	ct00 = ''
	ct10 = ''
	for i in range(len(ct0)):
	ct00 = ct00 + str(ct0[i]+q) + ','
	for i in range(len(ct1)):
	ct10 = ct10 + str(ct1[i]+q) + ','
	ct00 = ct00[:-1]
	ct10 = ct10[:-1]

	io.recv()
	io.sendline(ct00)

	io.recv()
	io.sendline(ct10)
	flag = io.recvline()[:-1]
	flag = [int(item) for item in flag.strip(b'[]').split(b',')]
	return flag


	if __name__ == "__main__":
	io = remote("124.71.224.99",21556)
	pk0,pk1,ct0,ct1 = get_homo_data()
	ssas = 47250135711800236243968330988950393827359446311214202975868194501939952447572268820856256117222966332956624906884328096423030618437170852480308637038075184731534034015103327181044504218075090965826320006738450109936180577663749111150190257135657273887365560219600637489061420461374674626281886506172665209012
	print(long_to_bytes(ssas))
	'''
	pass_random()
	flag = pass_homo()
	print(flag)
	s = ''
	for i in range(len(flag)):
	s =s +str(flag[i])
	'''

# XCTF Final 2021:

# GSA

$e = d^{-1}\mod (p^2-1)(q^2-1)\\\\ lower = n*(n-5)//\sqrt{\frac{ne(k-1)^2}{k} + 2}\\\\ y = 75(2^{i+1})n^3-(2^{i+1}(925+9*2^{i+2})-2^j*625)n^2\\\\ x = 625e\\\\ upper = [\sqrt{\frac{y}{x}}]\\\\ \\\\ (p^2-1)*(q^2-1) = n^2+1-(p^2+q^2)\\\\ = (p-1)*(q-1)*(p+1)*(q+1) \\\\ = (n+1 -p-q)(n+1 +p+q)\\\\ = (n+1)^2-(p+q)^2\\\\ = n^2+1-(p^2+q^2)$

lower 是 d 的下界， upper 是 d 的上界 d 是随机生成 514 位.

$y = n^2((75n-925)*2^{i+1}-9*2^{2i+3}-625*2^j)$

已知 n ,e 求 d 设 p²+q² = x*n x 从 2 开始遍历到 7 q=6p 时候差最大为 n=6p² q²+p²=37p² ≈6n 所以大概上界为 7n

$de = k(n^2-p^2-q^2+1) +1\\\\ \frac{e}{n^2-xn}=\frac{k}{d}\\\\$

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

	table = string.ascii_letters + string.digits

	def lianfenshu(n,e):#连分数
	s=[]
	while n >0:
	k=e//n
	s.append(k)
	e1=e
	n1=n
	n=e1-k*n
	e=n1
	return s

	def convergents(e):##e 为连分数的 []
	d = []
	n = []
	for i in range(len(e)):
	if i == 0:
	di = e[i]
	ni = 1
	elif i == 1:
	di = e[i]*e[i-1] + 1
	ni = e[i]
	else: # i > 1
	di = e[i]*d[i-1] + d[i-2]
	ni = e[i]*n[i-1] + n[i-2]
	n.append(ni)
	d.append(di)
	return n,d

	def pow(st,sha):
	for i in table:
	for j in table:
	for k in table:
	s = i+j+k
	sing = s+st
	shasha = sha256(sing.encode()).hexdigest()
	if shasha == sha:
	io.sendline(s)
	return

	if __name__ == "__main__":
	io = remote("",)
	io.recvuntil('XXX+')
	st = io.recvuntil(")")[:-1].decode()
	io.recvuntil("== ")
	sha = io.recvuntil("\n")[:-1].decode()
	io.recv()
	pow(st,sha)
	io.recvuntil(b'n = ')

	n = int(io.recvline()[:-1])
	io.recvuntil(b'e = ')
	e = int(io.recvline()[:-1])
	k = 6
	print(n)
	print(e)

	x = 2
	dd=[]
	while x<=8:
	N = nn - xn
	nn=convergents(lianfenshu(N,e))[0]
	ee=convergents(lianfenshu(N,e))[1]

	for i in range(len(nn)):
	if i==0:
	i=1
	d=nn[i]
	k=ee[i]
	if (de-1)%k==0 and (de-1)>0:
	phi=(d*e-1)//k
	if phi%2==0:
	if len(bin(d))>513 and len(bin(d))<517:
	dd.append(d)
	x = x+1

	d = dd[0]
	s = (de-1)//(nn) +1
	a = -((de-1 )//s - (nn) -1 )#p^2+q^2
	pp_qq = gmpy2.iroot(a*2-4(n*n),2)[0]#p^2-q^2
	p = gmpy2.iroot((pp_qq+a)//2,2)[0]
	q = gmpy2.iroot((a-pp_qq)//2,2)[0]

	if p>q:
	p = q
	print(sha1(long_to_bytes(p)).hexdigest())
	io.recv()
	io.sendline("2")
	io.recv()
	io.sendline(sha1(long_to_bytes(p)).hexdigest())
	io.interactive()

WriteUp