Skip to main content

Day 2: XMAS Spirit

challenge description
Now that elves have taken over Santa has lost so many letters from kids all over the world. 
However, there is one kid who managed to locate Santa and sent him a letter. It seems like the XMAS
spirit is so strong within this kid. He was so smart that thought of encrypting the letter in case
elves captured it. Unfortunately, Santa has no idea about cryptography. Can you help him read the letter?


This kid was so kind to send an encrypted letter to Santa! If santa can read it, so can any adversary. Please do not do this kid!

(Luckily I work for Santa, not the Grinch or the elves)

Let's take a look at the encryption mechanism. It seems simple and reminds me of the Linear congruential generator.

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')

Seems like it tries to mimick an Affine Cipher. With knowledge into the first few bytes of a PDF file (magic bytes), we can reverse the values of a, b and create the PDF back.
f = open("encrypted.bin", "rb")
flag = open("flag.pdf", "wb")

data = f.readlines()
data = b"".join(data)

from math import gcd
from Crypto.Util.number import bytes_to_long

PDF_MAGIC = [0x25, 0x50, 0x44, 0x46, 0x2D]
mod = 256

def check(a, b):
for i in range(1, 5):
if (PDF_MAGIC[i] * a + b) % mod != data[i]:
return False
return True

def create_pdf(a, b):
result = b""
for index, c in enumerate(data):
for i in range(0, 256):
if (i * a + b) % mod == c:
result += bytes([i])
if i == 255:
print("Not found", index)

for a in range(256):
if gcd(a, mod) != 1:
for b in range(256):
if (PDF_MAGIC[0] * a + b) % mod == data[0]:
if check(a, b):
print(f'Found a: {a}, b: {b}')
create_pdf(a, b)

PDF File

pdf preview