> For the complete documentation index, see [llms.txt](https://ir0nstone.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ir0nstone.gitbook.io/notes/writeups/ctfs/htb-cybersanta-2021/crypto/xmas-spirit.md).

# Xmas Spirit

## Contents

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

```python
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:

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

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

Gives us

```python
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.

```python
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.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://ir0nstone.gitbook.io/notes/writeups/ctfs/htb-cybersanta-2021/crypto/xmas-spirit.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.