LakeCTF 2023 - Invalid curve attack

lake23_invalid_curve.sage

from time import time

def get_invalid_point(p, a, known_factors = [], check_point = False):
	"""
	Input: the prime p, the fixed curve parameter a, and the already know factors
		that we do not want to repeat. Optionally we can check how much does it take
		to solve the dlp for a point before returning it with check_point=True.
	Output: an invalid point Q, the parameter b defining its curve, and the factors
		of its order.
	"""
	while True:
		b = randint(1, p)
		E_1 = EllipticCurve(GF(p), [a, b])
		order = E_1.order()
		factors = prime_factors(order)
		
		# Compute the best order we can get from a point
		good_factors = []
		for f in factors:
			if f.nbits() <= 40 and not f in known_factors:
				good_factors.append(f)

		cof = prod(good_factors)
		if cof.nbits() >= 50:
			print(f'Found curve')
			break
	
	# Now that we have a good curve, we need to find the point
	G = E_1.gen(0) * (order // cof)
	assert G.order() == cof

	if check_point:
		# Sanity check that we can actually solve the invalid dlp
		r = randint(1, cof)
		Q = G*r

		print(f'Solving dlog for {cof.nbits()} bits order')
		tic = time()
		dlog = G.discrete_log(Q)
		assert dlog == r, (r, dlog)
		print(f'Done in {round(time() - tic, 2)} s')

	return G, b, good_factors



if __name__ == '__main__':
	p = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
	a = 0xfffffffffffffffffffffffffffffffefffffffffffffffc
	b = 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1

	E = EllipticCurve(GF(p), [a, b])
	order = E.order()
	assert is_prime(order) # should we trust NSA? 

	known_factors = []
	Gs = []
	Bs = []
	for i in range(4):
		G, b, new_factors = get_invalid_point(p, a, known_factors)
		known_factors.extend(new_factors)
		print(f'{G = }\n{b = }')
		print(f'Got {prod(known_factors).nbits()} total bits')

	# Some computed values
	p = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
	a = 0xfffffffffffffffffffffffffffffffefffffffffffffffc
	b = 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1

	Bs = [83741891083651463213018945835494413320520449989597215648,3556206473404317281093691979083778944572588872003627559970,132627736693468008571263914981090018160610438249416432561,4353766386870675869823517562355728918310218671450488829638]
	Gs = [EllipticCurve(GF(p), [a, Bs[0]])(1428777260646132976198331917216550410517338377336849911092, 3658983833028448009741994042652306163657412286434111440479),EllipticCurve(GF(p), [a, Bs[1]])(3189235510701084020240251273172260904256567493190538416973, 3147050744360070584444363752093634124297717789231789390963),EllipticCurve(GF(p), [a, Bs[2]])(1836055837552433451429707649431552069210777860779533915323, 4080888809128014080938902461081426574934912634479355715692),EllipticCurve(GF(p), [a, Bs[3]])(567148773685333711499991584170987837091585548967120385444, 2945834156539179266918934145900085216962713232769658612995)]

	# Server values
	pub = EllipticCurve(GF(p), [a, b])(275956366273838645914286744108317970424389601350215013292,1715484665561054570396524612468150066010506001507851259697)
	out = [
		EllipticCurve(GF(p), [a, Bs[0]])(2520009623362543945986336259874602290571366143015497579774,918209543266182540574220472175145773512397388546557928127),
		EllipticCurve(GF(p), [a, Bs[1]])(6114283288101947049456189131219162763629412798424257598888,3337781419281746480460476732287507319887104334435838499559),
		EllipticCurve(GF(p), [a, Bs[2]])(4375469479810874253079345013985635396946981387269636176579,3039983122916367530269883045392843677915744087945892387770),
		EllipticCurve(GF(p), [a, Bs[3]])(5006251221813189712869553605012565305195873815585805823417,1916349364515225922801955454929707154738727920670355042345)
	]
	
	orders = [Gs[i].order() for i in range(4)]
	dlogs = []
	for i in range(4):
		print(f'Solving dlog {i}')
		dlog = Gs[i].discrete_log(out[i])
		print(f'{dlog = }')
		dlogs.append(dlog)
	
	PK = CRT_list(dlogs, orders)
	d = inverse_mod(PK, E.order())
	G = d*pub

	flag = int(G[0]).to_bytes((int(G[0]).bit_length() + 7)//8, 'big')
	print(f'{flag = }')