Tags: polynomial png factor 


# 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:

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
enc = hex(C)[2:].rstrip('L').decode('hex')
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).