# 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

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:

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:

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

f.write(final)
And the resulting PDF has the flag HTB{4ff1n3_c1ph3r_15_51mpl3_m47h5} within.