Tags: polynomial png factor

Rating:

# Made by baby (for, 141p, 29 solved)

This was a very nice, and not so trivial crypto challenge.
In the end it turned out very simple, but nothing really suggested that, so we did a bit of an overkill here.

In the challenge we get [encryption code](babymade.py) and [encrypted flag](flag.enc) to work with.
We can see that the flag is supposed to be a PNG file.

The encryption code is rather simple:

python
from secret import exp, key

def encrypt(exp, num, key):
assert key >> 512 <= 1
num = num + key
msg = bin(num)[2:][::-1]
C, i = 0, 1
for b in msg:
C += int(b) * (exp**i + (-1)**i)
i += 1
try:
enc = hex(C)[2:].rstrip('L').decode('hex')
except:
enc = ('0' + hex(C)[2:].rstrip('L')).decode('hex')
return enc


We can see that secret key parameter is at most 512 bits long, so it will modify only the lowest 128 bytes of the PNG.
This shouldn't be an issue - we can replace the broken PNG trailer, and the picture should be still fine.

The encryption itself is performed bit by bit, in reverse bit order.
If i-th bit is lighted, then we add exp**i to the accumulator and we also add (-1)**i.

The second part with -1 shouldn't be much of an issue, because assuming a nice random bits distribution in the data, we should get roughly the same number of 1 and -1 and they should more-or-less even out in the end.

The final encrypted payload is, therefore, a polynomial exp**i + exp**j + exp**k +.... -+C where C is some small number and `i

Original writeup (https://github.com/p4-team/ctf/tree/master/2018-11-24-asis-finals/crypto_baby).