So easy: writeup

ссылка на задачу http://f8tasks.ru/challenges#So%20easy-15

So easy


Category	Crypto
Difficulty	Easy
Vulnerability	Linear modular arithmetic — small plaintext
Flag	`flag{ololo}`

Recon

Легенда задачи: «В стране лилипутов и криптосервисы соответствующие. Ну давай, давай, Гуливер, расшифровывай!»

Два артефакта: task.py (генератор, доступен участнику) и output.txt (шифротекст).

task.py — ключевые строки:

pri = getPrime(40)
pub = 1867939819429

m = [ord(i) for i in flag]
c = [hex(i*pub % pri)[2:] for i in m]

pub — константа, известна участнику. pri — случайное 40-битное простое число, не публикуется. Каждый символ флага шифруется независимо.

output.txt:

614e797687|82955cdf44|1e8ad93f69|3fd1bca826|60aced459b|1e1f267421|82955cdf44|1e1f267421|82955cdf44|1e1f267421|1db373a8d9

11 hex-блоков через | — по одному на символ флага.

Немедленные наблюдения:

82955cdf44 встречается три раза → три одинаковых символа
1e1f267421 встречается три раза → ещё три одинаковых символа
Схема детерминирована и посимвольна: никакой случайности, одинаковый символ всегда даёт одинаковый блок

Вектор атаки: символы ASCII малы (32–126), pub известен, все $c_i$ известны. Из уравнения $m_i \cdot pub - c_i = k_i \cdot pri$ при ограниченном диапазоне $m_i$ и $k_i$ — восстановление pri перебором кандидатов.

Modulus Recovery: восстановление скрытого модуля

Формула шифрования:

$$c_i \equiv m_i \cdot pub \pmod{pri}$$

Эквивалентное точное равенство для целых чисел:

$$m_i \cdot pub - c_i = k_i \cdot pri$$

Кандидат на модуль:

$$pri = \frac{m_i \cdot pub - c_i}{k_i}$$

Ручной расчёт для минимального шифроблока:

Минимальное значение в шифротексте: 0x1db373a8d9 = 127 564 753 113. Пробуем m = 125 (символ }, ord(}) = 125) и k = 232:

delta = 125 × 1 867 939 819 429 − 127 564 753 113
      = 233 492 477 428 625 − 127 564 753 113
      = 233 364 912 675 512

delta % 232 == 0  →  pri_candidate = 233 364 912 675 512 / 232 = 1 005 883 244 291

Проверки кандидата:

Условие	Результат
$2^{39} \le pri < 2^{41}$	✓ (1 005 883 244 291 ≈ 40 бит)
Тест простоты (Miller–Rabin)	✓
`pub % pri ≠ 0`	✓
Все 11 символов после расшифровки — печатные ASCII	✓

Правильный модуль — единственный, при котором весь шифротекст декодируется в читаемый текст. Перебор: m ∈ 32..126, k ∈ 1..299 — всего не более 28 175 итераций.

Decryption

Шаг	Действие	Формула / код
1	Разобрать шифротекст	`int(x, 16)` для каждого блока
2	Восстановить `pri`	перебор (m, k), проверка двух условий + валидация
3	Вычислить обратный элемент	`inv = pow(pub, -1, pri)`
4	Расшифровать каждый символ	`chr((c * inv) % pri)`
5	Собрать флаг	`''.join(...)`

Результат:

pri = 1005883244291
flag{ololo}

Automation

pub = 1867939819429
ciphertext = "614e797687|82955cdf44|1e8ad93f69|3fd1bca826|60aced459b|1e1f267421|82955cdf44|1e1f267421|82955cdf44|1e1f267421|1db373a8d9"


def is_prime(n: int) -> bool:
    if n < 2:
        return False
    small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for prime in small_primes:
        if n % prime == 0:
            return n == prime

    d = n - 1
    s = 0
    while d % 2 == 0:
        s += 1
        d //= 2

    for base in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
        if base % n == 0:
            continue
        x = pow(base, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = (x * x) % n
            if x == n - 1:
                break
        else:
            return False
    return True


def find_prime(cs: list[int], pub: int) -> int:
    printable = range(32, 127)
    first = min(set(cs))

    for candidate_char in printable:
        delta = candidate_char * pub - first
        if delta <= 0:
            continue
        for quotient in range(1, 300):
            if delta % quotient != 0:
                continue
            prime = delta // quotient
            if not ((1 << 39) <= prime < (1 << 41)):
                continue
            if not is_prime(prime) or pub % prime == 0:
                continue

            inverse = pow(pub, -1, prime)
            plaintext = [(value * inverse) % prime for value in cs]
            if all(char in printable for char in plaintext):
                return prime

    raise RuntimeError("prime modulus not found")


def main() -> None:
    cs = [int(part, 16) for part in ciphertext.split("|")]
    prime = find_prime(cs, pub)
    inverse = pow(pub, -1, prime)
    flag = "".join(chr((value * inverse) % prime) for value in cs)
    print(f"pri = {prime}")
    print(flag)


if __name__ == "__main__":
    main()

python3 solve.py
# pri = 1005883244291
# flag{ololo}

Key Takeaways

Посимвольное шифрование без случайности раскрывает структуру. Одинаковые символы дают одинаковые блоки шифротекста. Три совпадающих блока в output.txt — прямая утечка: авторское шифрование не использует ни IV, ни соль, ни паддинг.
Малый plaintext ломает модульную арифметику. ASCII-символы укладываются в 7 бит. Из равенства $m \cdot pub - c = k \cdot pri$ при ограниченных $m \in [32, 126]$ и $k < 300$ перебор кандидатов на pri занимает менее 30 тысяч итераций вместо полного перебора 40-битных простых ($\approx 3 \times 10^{10}$).
Восстановление скрытого параметра — стандартная техника. Если схема линейна и один из параметров мал — всегда проверять, можно ли восстановить модуль или ключ через уравнение $a \cdot m - c = k \cdot n$. Это работает для любого c = m * a mod n с малым m.