**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).