Hack.lu CTF 2016 Creative Cheating (Crypto 150pt)

solver.py

# Hack.lu CTF 2016 Creative Cheating (Crypto 150pt)

def egcd(a, b):
 if (a == 0):
     return [b, 0, 1]
 else:
     g, y, x = egcd(b % a, a)
     return [g, x - (b // a) * y, y]

def modInv(a, m):
 g, x, y = egcd(a, m)
 if (g != 1):
     raise Exception("[-]No modular multiplicative inverse of %d under modulus %d" % (a, m))
 else:
     return x % m

def decrypt(p, q, e, c):
	n = p * q
	phi = (p - 1) * (q - 1)
	d = modInv(e, phi)
	m = pow(c, d, n)
	return m

def verify(Bm, sig):
	An = 0x53a121a11e36d7a84dde3f5d73cf
	# Ap = 38456719616722997
	# Aq = 44106885765559411
	Ae = 0x10001
	Am = pow(sig, Ae, An)
	return Am == Bm


Bp = 49662237675630289
Bq = 62515288803124247
Be = 0x10001

f = open("dump.txt", "r")

flist = []
for line in f:
	line = line.strip().decode("base64")
	row = line.split(" ")
	seq = int(row[2][:-1])
	data = int(row[5][:-2], 16)
	sig = int(row[8][:-2], 16)
	# print seq, data, sig
	m = decrypt(Bp, Bq, Be, data)
	if verify(m, sig) == True:
		plain = hex(m)[2:-1].zfill(2).decode("hex")
		flist.append([seq, plain])
f.close()

flist.sort(key=lambda x:x[0])

flag = ""
for f in flist:
	flag += f[1]
print flag

# Result
# >python solver.py
# flag{n0th1ng_t0_533_h3r3_m0v3_0n}

Task:
Mr. Miller suspects that some of his students are cheating in an automated computer test. He captured some traffic between crypto nerds Alice and Bob. It looks mostly like garbage but maybe you can figure something out. He knows that Alice's RSA key is (n, e) = (0x53a121a11e36d7a84dde3f5d73cf, 0x10001) (192.168.0.13) and Bob's is (n, e) = (0x99122e61dc7bede74711185598c7, 0x10001) (192.168.0.37)

Flag: flag{n0th1ng_t0_533_h3r3_m0v3_0n}

Alice→Bobの暗号通信(RSA)のpcapデータが渡される（秘密鍵はすぐに特定可能）。通信データは分割されていて、それぞれにシーケンス番号・データ部・シグネチャが含まれている。データ部の復号結果をシグネチャを用いて検証し、シーケンス番号でソートして繋げるとFlagになる。