hitcon-2017-quals-secret-fs.py

#!/usr/bin/python

def exgcd(a,b):
	u,  v,  s,  t = 1, 0, 0, 1
	while b !=0:
		q, r = divmod(a,b)
		a, b = b, r
		u, s = s, u - q*s
		v, t = t, v - q*t
	return (u, v, a)

def mod_inverse(a,b):
	x,y,z = exgcd(a,b) 
	assert(z==1)
	return x

n = 104176920808444707134363566789644103637046138703732812593856489450966164422700871083271001476798525601830292237723021138499045286505397665962198734248957208942814238767855960753797521549548788530151996440657784060736603682776712677518537991291065233449586393186516770855075158900503486179189610821817031409223
e1 = 3
m1 = 80026450605919212347157319516655228661982088106956311148514121800139890113377161068043879513015347037232410178041918490832353137735848626795271143817272105057902549455690557715462777567966903851646207028020678373050285949287173514737755698953051536123368646144531895984034141177000138932645546381541544731963
e2 = 0x7478
m2 = 24789836942239403722795930341732835678691656750347230627416434227665247940527361150396455511246644544283832637661545664078814615114240744561273489461844843182114793772702713013603371781739673411384862756987736726406966123858749513205304608394157412210509128405578588422322912351914650629099969071449156118527

a,b,g = exgcd(e1, e2)
print a,b,g
print a * e1 + b * e2

print mod_inverse(m2, n)
r = (pow(m1, a) * mod_inverse(m2, n)) % n

print hex(r).decode('hex')