# Timisoara-CTF-Finals-2018-Crypto-Write-up## Write-up for tasks Recap(250p) and Recess(400p)
This was a 2 in one problem. We were given a copy of the code that was running on a server in which the flags were in some files flag1, respectively flag2:```pythonimport signalimport sysimport osimport binasciiimport random
os.chdir(os.path.dirname(os.path.abspath(__file__)))
MAGIC_NUMBER = 11MSG_LENGTH = 119CERT_CNT = MAGIC_NUMBERcoeffs = [random.randint(0, MAGIC_NUMBER**128) for i in range(MAGIC_NUMBER)]
def enc_func(msg):    global coeffs    msg = msg * 0x100 + 0xFF    acc = 0    cur = 1    for coeff in coeffs:        acc = (acc + coeff * cur) % (MAGIC_NUMBER**128)        cur = (cur * msg) % (MAGIC_NUMBER**128)    return acc % (MAGIC_NUMBER**128)
def get_hex_msg():    try:        msg = raw_input()        msg = int(msg,16)        return msg % (MAGIC_NUMBER ** (128) )    except:        print "Bad input"        exit()
def encryption():    print 'Input your message:'    msg = get_hex_msg()    ct = enc_func( msg )    print "Encryption >>>> %#x" %  ct
def challenge1():    for i in range(CERT_CNT):        msg = random.randint(0, MAGIC_NUMBER**(MSG_LENGTH) )        ct = enc_func( msg )        print 'Encrypt this: %#x' % msg        ct2 = get_hex_msg()        if ct != ct2:            print "Your input %#x should have been %#x" % (ct2, ct)            exit()    print "You win challenge 1"    print open("flag1").read()
def challenge2():    for i in range(CERT_CNT):        msg = random.randint(0, MAGIC_NUMBER**(MSG_LENGTH))        ct = enc_func( msg )        print 'Decrypt this: %#x' % (ct)        msg2 = get_hex_msg()        if enc_func(msg) != enc_func(msg2):            print "Your input %#x should have been %#x" % (msg2, msg)            exit()    print "You win challenge 2"    print open("flag2").read()
def input_int(prompt):    sys.stdout.write(prompt)    try:        n = int(raw_input())        return n    except ValueError:        return 0    except:        exit()
def menu():    while True:        print "Horrible Crypto"        print "1. Arbitrary Encryption"        print "2. Encryption Challenge"        print "3. Decryption Challenge"        print "4. Exit"        choice = input_int("Command: ")        {                1: encryption,                2: challenge1,                3: challenge2,                4: exit,        }.get(choice, lambda *args:1)()
if __name__ == "__main__":    signal.alarm(15)   a menu()```Ok, so let's analyse what we are given and what we have to do:Running the code we can see a menu:> Horrible Crypto> 1. Arbitrary Encryption> 2. Encryption Challenge> 3. Decryption Challenge> 4. Exit
So, we are given an encryption oracle and two challanges, encryption (**task recap**) and decryption (**task recess**)### Understanding the encryptionLet's start with the encryption:```pythondef enc_func(msg):    global coeffs    msg = msg * 0x100 + 0xFF    acc = 0    cur = 1    for coeff in coeffs:        acc = (acc + coeff * cur) % (MAGIC_NUMBER**128)        cur = (cur * msg) % (MAGIC_NUMBER**128)    return acc % (MAGIC_NUMBER**128)
def get_hex_msg():    try:        msg = raw_input()        msg = int(msg,16)        return msg % (MAGIC_NUMBER ** (128) )    except:        print "Bad input"        exit()
def encryption():    print 'Input your message:'    msg = get_hex_msg()    ct = enc_func( msg )    print "Encryption >>>> %#x" %  ct```Inside `encryption()` the input is a hex number which gets decoded to an int and then actually encrypted in `enc_func(msg)`.Now, let's focus on how the encryption works:It takes the message, it multiplies it by 256, adds 255 `msg = msg * 0x100 + 0xFF` and then computes the polynomial `coeffs(msg)` modulo 11^128 (`MAGIC_NUMBER = 11` is a constant), and that's our ciphertext.### Task RecapRecap was the first challenge. The adversary is given 11 messages to encrypt. By successfully encrypting the messages, the flag is given to the adversary.```pythondef challenge1():    for i in range(CERT_CNT):        msg = random.randint(0, MAGIC_NUMBER**(MSG_LENGTH) )        ct = enc_func( msg )        print 'Encrypt this: %#x' % msg        ct2 = get_hex_msg()        if ct != ct2:            print "Your input %#x should have been %#x" % (ct2, ct)            exit()    print "You win challenge 1"    print open("flag1").read()```So basically we need to find the coefficients of the polynomial **coeffs** in order to be able to encrypt. Note that we have an encryption oracle so practically we can find any coefficient of the polynomial **coeffs** right? Well, that's great because we can recreate the original polynomial by creating a **Lagrange polynomial** of degree equal to the degree of the polynomial **coeffs**.You can read more about it on [Wikipedia](https://en.wikipedia.org/wiki/Lagrange_polynomial), the math is pretty simple, and there's an image that visually describes very well the algorithm.**NOTE**: since the contest's servers don't work anymore you will have to run the challange code locally.
### Task Recess
Now, the second task was the **real deal**. The adversary has to decrypt 11 messages. I didn't solve this task during the contest (I solved it about 4 hours after the contest ended, but I still got goosebumbs when I got the flag). About 3 hours before the end of the contest a hint was added (sadly, i don't remember the exact form of the hint), and eventually I found an article on [Wikipedia](https://en.wikipedia.org/wiki/Hensel%27s_lemma) and a bit of code on [GitHub](https://github.com/gmossessian/Hensel/blob/master/Hensel.py). After a good 30 minutes of reading I implemented the solution, practically for a message **msg** we had to find a root of the polynomial `f(x)=coeffs(x)-msg`. The mistake I made was that I didn't realize what this line of code was doing:```pythonmsg = msg * 0x100 + 0xFF```This makes it so that the encription is a bit more complicated, encription isn't just **coeffs(msg)**, it's **coeffs(g(msg))**, where **g** is another ploynomial: `g(x) = 256*x+255`. That means that Hensel's lemma had to be applied to the polynomial **coeffs(g(x))**. So I wrote a funtion that composes two polynomials.### The codeHere's my solution to both problems:```pythonfrom pwn import *from Crypto.Util.number import inverse
MOD=11**128
def transform(x):	return (x*256+255)%MOD
#Polynomial partclass Polynomial(list):
	def __init__(self,coeffs):		self.coeffs = coeffs
	def evaluate(self,x,mod):		val = 0		for i in range(len(self.coeffs)):			val = (val + x**i * self.coeffs[i]) % mod		return val
	def raise_degree(self,x):		coeffs=[]
		for i in range(x):			coeffs.append(0)
		for i in range(len(self.coeffs)):			coeffs.append(self.coeffs[i]) 		self.coeffs=coeffs 	def add_to_degree(self,x,y):		while(len(self.coeffs)<=x):			self.coeffs.append(0) 		self.coeffs[x]=(self.coeffs[x]+y)%MOD
	def add_poly(self,x):		while(len(self.coeffs)