Crypto2: writeup

Ссылка на задачу http://f8tasks.ru/challenges#Crypto2-6

Crypto2


Category	Crypto / Math
Difficulty	Easy
Technique	Linear Transformation — sum invariant
Flag	`flag{its_not_magic}`

Recon

Два артефакта задачи: task.py (генератор) и output.txt (матрица после преобразования).

Условие подсказывает: «Люди не верят в магию…». Намёк прямой: магии нет, есть математика.

task.py — ключевые наблюдения:

s = 0
for i in range(4):
    for j in range(4):
        square[i][j] = randint(0, flag // 16)
        s += square[i][j]

square[3][3] += flag - s

Первые 15 клеток заполняются случайно, последняя подгоняется так, чтобы сумма всей матрицы равнялась flag:

$$\text{flag} = \sum_{i,j} \text{square}[i][j]$$

Функция magic() применяет к матрице только операции += — никакого XOR, умножения, перестановок. Это линейное преобразование.

Linear Transformation

Каждый выходной элемент magic_square[i][j] — сумма нескольких входных клеток. Например, из magic():

magic_square[0][0] += square[1][0]          # из цикла
magic_square[0][0] += square[3][0] + square[0][1]  # ниже

Итого: $\text{out}_{00} = x_0 + x_4 + x_{12} + x_1$, где $x_k$ — клетки исходной матрицы, пронумерованные построчно.

Всё преобразование записывается как:

$$Ax = b$$

где $x$ — вектор из 16 входных значений, $b$ — 16 чисел из output.txt, $A$ — матрица коэффициентов из нулей и единиц.

Построение столбца $A$ вручную (для $x_0$):

Подаём на вход единичный вектор: square[0][0] = 1, все остальные = 0.

Выходная клетка	Откуда берётся 1	Позиция в $b$
`magic_square[0][0]`	`square[0][0]` + цикл строки 0	0
`magic_square[0][1]`	`+= square[0][0] + ...`	1
`magic_square[1][0]`	`+= square[0][0]` из цикла	4
`magic_square[3][0]`	`+= square[0][0] + ...`	12

Столбец 0 матрицы $A$: единицы на позициях 0, 1, 4, 12 — всё остальное нули.

Повторяя для всех 16 базисных векторов, получаем полную матрицу $A$ автоматически. Это реализует build_matrix() из solve.py.

Ранг системы: 14 при 16 неизвестных. Решений бесконечно много, но это не проблема — нам нужна только сумма. Для любого вектора ядра $v$ (где $Av = 0$) выполняется $\sum v_i = 0$, поэтому все решения дают одинаковую сумму, и flag восстанавливается однозначно.

Decryption

Шаг	Действие	Результат
1	Построить матрицу $A$ через `build_matrix()`	Матрица $16 \times 16$
2	Решить $Ax = b$ методом Гаусса (точная арифметика, `Fraction`)	Одно из решений $x$
3	Вычислить $\sum x_i$	`2284117282071619956732933978357702666471695229`
4	Перевести integer → hex	`666c61677b6974735f6e6f745f6d616769637d`
5	Декодировать hex → ASCII	`flag{its_not_magic}`

Шаг 4–5 подробнее — flag кодировался как int.from_bytes(flag_bytes, 'big'). Обратный шаг:

hex_value = f"{flag_number:x}"
if len(hex_value) % 2:
    hex_value = "0" + hex_value
flag = bytes.fromhex(hex_value).decode("ascii")

Automation

#!/usr/bin/env python3

from fractions import Fraction


OUTPUT = [
    [295662573273290623900407320667244440561913074, 398969263312250142846591713944233406242755402, 348748750178596858287457463436167770367743486, 1364037545534325541882463501082729953690961051],
    [575026186132965057911584617811112536209642264, 475019143092003929835430859115351077234156392, 306730089063421029803201145877510554629647601, 506049720455827979279301584495901051137471499],
    [84266604156989810704049456000281640732504848, 489861776717561426112183190426399395504819586, 343168692956493452627232161939238347545174591, 1300450584581165319714233483811149638923359733],
    [247265750644178124958450035605722570774151739, 316655879927503657733383936311500619683899343, 1294831694146552023902991223917286568358963480, 1191862843017346876917142321386548275775314968],
]


def magic(square: list[list[int]]) -> list[list[int]]:
    magic_square = [row[:] for row in square]

    for i in range(4):
        magic_square[0][i] += square[1][i]
        magic_square[1][i] += square[0][i]
        magic_square[2][i] += square[3][i]
        magic_square[3][i] += square[2][i]

    magic_square[0][0] += square[3][0] + square[0][1]
    magic_square[0][1] += square[0][0] + square[0][2]
    magic_square[0][2] += square[0][1] + square[0][3]
    magic_square[0][3] += square[0][2] + square[3][3]

    magic_square[1][0] += square[1][1] + square[1][3] + square[2][2]
    magic_square[1][1] += square[1][0] + square[2][3] + square[2][1]
    magic_square[1][2] += square[2][0] + square[2][2]
    magic_square[1][3] += square[1][0] + square[2][1]

    magic_square[2][0] += square[1][2] + square[2][3]
    magic_square[2][1] += square[1][1] + square[1][3]
    magic_square[2][2] += square[1][0] + square[1][2] + square[2][3]
    magic_square[2][3] += square[1][1] + square[2][0] + square[2][2]

    magic_square[3][0] += square[0][0] + square[3][1]
    magic_square[3][1] += square[3][0] + square[3][2]
    magic_square[3][2] += square[3][1] + square[3][3]
    magic_square[3][3] += square[3][2] + square[0][3]

    return magic_square


def build_matrix() -> list[list[Fraction]]:
    columns = []
    for index in range(16):
        square = [[0] * 4 for _ in range(4)]
        square[index // 4][index % 4] = 1
        transformed = magic(square)
        columns.append([Fraction(value) for row in transformed for value in row])
    return [list(row) for row in zip(*columns)]


def solve_linear_system(matrix: list[list[Fraction]], vector: list[Fraction]) -> list[Fraction]:
    augmented = [row[:] + [value] for row, value in zip(matrix, vector)]
    size = len(augmented)
    pivot_cols = []
    pivot_row = 0

    for col in range(size):
        swap_row = None
        for row in range(pivot_row, size):
            if augmented[row][col] != 0:
                swap_row = row
                break
        if swap_row is None:
            continue

        augmented[pivot_row], augmented[swap_row] = augmented[swap_row], augmented[pivot_row]
        pivot = augmented[pivot_row][col]
        augmented[pivot_row] = [value / pivot for value in augmented[pivot_row]]

        for row in range(size):
            if row == pivot_row or augmented[row][col] == 0:
                continue
            factor = augmented[row][col]
            augmented[row] = [
                augmented[row][idx] - factor * augmented[pivot_row][idx]
                for idx in range(size + 1)
            ]

        pivot_cols.append(col)
        pivot_row += 1

    solution = [Fraction(0) for _ in range(size)]
    for row, col in enumerate(pivot_cols):
        solution[col] = augmented[row][-1]
    return solution


def decode_integer(value: int) -> str:
    hex_value = f"{value:x}"
    if len(hex_value) % 2:
        hex_value = "0" + hex_value
    return bytes.fromhex(hex_value).decode("ascii")


def main() -> None:
    matrix = build_matrix()
    vector = [Fraction(value) for row in OUTPUT for value in row]
    solution = solve_linear_system(matrix, vector)

    flag_number = sum(solution)
    if flag_number.denominator != 1:
        raise ValueError("flag is not an integer")

    flag = decode_integer(int(flag_number))
    print(flag)


if __name__ == "__main__":
    main()

python3 solve.py
# flag{its_not_magic}

Key Takeaways

Чтение генератора как вектор атаки. Одна строка square[3][3] += flag - s раскрывает, что flag — это сумма всей матрицы. Читать task.py внимательно — первый шаг в любой задаче с генератором.
Линейные операции → система уравнений. Если код содержит только +=, всё преобразование записывается как $Ax = b$. Ранг меньше числа неизвестных не блокирует задачу: нужно искать инвариант — характеристику, одинаковую у всех решений.
Integer → hex → ASCII — стандартный путь к флагу. Большое целое число в CTF почти всегда оказывается текстом, закодированным через int.from_bytes(..., 'big'). Проверять этот шаг — обязательная привычка.