Xmas Spirit

Contents

We get given challenge.py and encrypted.bin. Analysing challenge.py:

import random
from math import gcd

def encrypt(dt):
	mod = 256
	while True:
		a = random.randint(1, mod)
		if gcd(a, mod) == 1:
			break
	b = random.randint(1, mod)

	res = b''
	for byte in dt:
		enc = (a * byte + b) % mod
		res += bytes([enc])
	return res


dt = open('letter.pdf', 'rb').read()

res = encrypt(dt)

f = open('encrypted.bin', 'wb')
f.write(res)
f.close()

It calculates two random values, aa and bb. For every byte kk in the plaintext file, it then calculates

ak+bmod256ak + b \mod 256

And appends the result of that as the encrypted character in encrypted.bin.

Analysis

The plaintext file appears to be letter.pdf, and using this we can work out the values of aa and bb because we know the first 4 bytes of every PDF file are %PDF. We can extract the first two bytes of encrypted.bin and compare to the expected two bytes:

with open('encrypted.bin', 'rb') as f:
    res = f.read()

print(res[0])
print(res[1])
print(ord('%'))
print(ord('P'))

Gives us

13
112
37
80

So we can form two equations here using this information:

a37+b13mod256a80+b112mod256a \cdot 37 + b \equiv 13 \mod 256 \\ a \cdot 80 + b \equiv 112 \mod 256

We subtract (2) from (1) to get that

43a99mod25643a \equiv 99 \mod 256

And we can multiply both sides by the modular multiplicative inverse of 43, i.e. 431mod25643^{-1} \mod 256, which is 131131, to get that

a99131169mod256a \equiv 99 \cdot 131 \equiv 169 \mod 256

And then we can calculate bb:

b1316937160mod256b \equiv 13 - 169 * 37 \equiv 160 \mod 256

Solution

So now we have the values for aa and bb, it's simply a matter of going byte-by-byte and reversing it. I created a simple Sage script to do this with me, and it took a bit of time to run but eventually got the flag.

with open('encrypted.bin', 'rb') as f:
    res = f.read()


final = b''


R = IntegerModRing(256)

for char in res:
    b = bytes([ (R(char) - R(160)) / R(169) ])
    print(b.decode('latin-1'), end='')
    final += b

with open('answer.pdf', 'wb') as f:
    f.write(final)

And the resulting PDF has the flag HTB{4ff1n3_c1ph3r_15_51mpl3_m47h5} within.

Last updated