# Magic 1 (crypto, 205p, 44 solved)
In the challenge we get [source code](https://raw.githubusercontent.com/TFNS/writeups/master/2020-03-01-AeroCTF/magic/task.py) and [data](https://raw.githubusercontent.com/TFNS/writeups/master/2020-03-01-AeroCTF/magic/output.txt).
The code is a quite simple stream cipher.The interesting part is:
```python    def create(cls, source: np.ndarray) -> 'Cipher':        assert len(set(source.shape)) == 1        line = source.reshape(-1)        assert len(line) == len(set(line) & set(range(len(line))))        keys = set(map(sum, chain.from_iterable((*s, np.diag(s)) for s in [source, source.T])))        assert len(keys) == 1        key = int(keys.pop())        return cls(key, key % len(line))```
This basically creates the `key` value which turned into bytes provides the keystream.It might seem a bit complex, but in reality this function simply checks if provided `source` numpy array is a `magic square`.
`line = source.reshape(-1)` flattens the matrix into a single list and `assert len(line) == len(set(line) & set(range(len(line))))` checks if this list contains all numbers `0..n`.Then `set(map(sum, chain.from_iterable((*s, np.diag(s)) for s in [source, source.T])))` makes a set of sums along all vertical, horizontal and diagonals of the matrix, and then it's checked if set contains only a single element.
The `key` value from which the keystream is derived is the magic number of the square, so the sum.
What we know in the task is encrypted flag and also `c = key % len(line) = key % n**2`.
The magic sum of such magic square (which starts from 0 and not clasically from 1) is:
```M = (n * (n**2 + 1)) / 2 - n = (n/2)*(n**2+1-2) = (n/2)*(n**2-1)```
Since we know `c = M%n**2` we can do:
```pythonc == M mod n**2 c == (n/2)*(n**2-1) mod n**22*c == n*(-1) mod n**2 # x-1 mod x == -1 mod x 2*c == (-n) mod n**22*c == (n**2-n) # -k mod x == x-k mod xn**2 -n -2c mod n**2 == 0```
Now we can solve this quadratic equation `n**2 -n -2c = 0` for `n`:
```pythona = 1b = -1c = -2 * canarydelta = b ** 2 - 4 * a * cx1 = -b - gmpy2.isqrt(delta) / 2 * ax2 = -b + gmpy2.isqrt(delta) / 2 * ax = x1 if x1 > 0 else x2```
With this we can recover the magic sum of the square `key = x * (x ** 2 - 1) / 2`.Finally we can decrypt the flag `print(long_to_bytes(ct ^ key))` and we get `Aero{m4g1c_squ4r3_1s_just_4n_4nc13nt_puzzl3}`