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
