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, $a$ and $b$. For every byte $k$ in the plaintext file, it then calculates

$$ak + 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 $a$ and $b$ 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:

$$a \cdot 37 + b \equiv 13 \mod 256 \\ a \cdot 80 + b \equiv 112 \mod 256$$

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

$$43a \equiv 99 \mod 256$$

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

$$a \equiv 99 \cdot 131 \equiv 169 \mod 256$$

And then we can calculate $b$:

$$b \equiv 13 - 169 * 37 \equiv 160 \mod 256$$

Solution

So now we have the values for $a$ and $b$, 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.