Crypto1: writeup

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

Crypto1


Category	Crypto
Difficulty	Easy
Vulnerability	RSA Perfect Power — $n = p^5$
Flag	`flag{tw0_plu5_tw0_15_f0ur}`

Recon

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

output.txt содержит три числа в стандартном RSA-формате:

n   — модуль (5120-битное число)
e   — открытая экспонента (65537)
c   — шифротекст

task.py — генератор, доступный участнику. Ключевое наблюдение:

p = getPrime(1024)
n = p*p*p*p*p      # <-- аномалия
e = 65537
c = powmod(m, e, n)

В стандартном RSA модуль строится как $n = p \cdot q$, где $p$ и $q$ — два разных больших простых. Здесь модуль — это одно простое число, возведённое в пятую степень. Это уязвимость.

Vulnerability: RSA Perfect Power

Безопасность RSA держится на вычислительной сложности факторизации $n = p \cdot q$.

Если $n = p^5$, факторизация тривиальна — достаточно найти точный целый корень пятой степени:

$$p = \sqrt[5]{n}$$

Почему нельзя использовать float? Числа 1024-битные (~310 знаков). Вещественная арифметика потеряет точность. Решение — бинарный поиск по целым числам:

def integer_nth_root(value: int, degree: int) -> int:
    low, high = 0, 1
    while high**degree <= value:
        high <<= 1
    while low + 1 < high:
        mid = (low + high) // 2
        if mid**degree <= value:
            low = mid
        else:
            high = mid
    return low

После нахождения кандидата — обязательная проверка точности: p**5 == n.

Exploitation

Полная цепочка от $n$ до флага:

Шаг	Действие	Формула
1	Восстановить $p$	$p = \sqrt[5]{n}$, целочисленно
2	Вычислить функцию Эйлера	$\varphi(p^5) = p^5 - p^4$
3	Найти секретную экспоненту	$d \equiv e^{-1} \pmod{\varphi(n)}$
4	Расшифровать	$m = c^d \bmod n$
5	Декодировать в ASCII	`m.to_bytes(...).decode('ascii')`

Шаг 2 подробнее: почему $\varphi(p^5) = p^5 - p^4$

Для степени простого числа функция Эйлера считается по формуле:

$$\varphi(p^k) = p^k - p^{k-1}$$

Смысл: из $p^k$ чисел от $1$ до $p^k$ не взаимно просты с $p^k$ ровно те, что делятся на $p$. Их $p^{k-1}$ штук. Остальные — взаимно просты.

Для нашего случая $k = 5$:

$$\varphi(p^5) = p^5 - p^4 = p^4(p - 1)$$

Шаг 3: проверка перед инверсией

Обратный элемент $d = e^{-1} \bmod \varphi(n)$ существует только если $\gcd(e,\, \varphi(n)) = 1$. В Python:

from math import gcd
assert gcd(e, phi) == 1
d = pow(e, -1, phi)

Шаг 5: байты → строка

Флаг шифровался целиком как одно большое целое число (big-endian):

m = int.from_bytes(flag.encode('ascii'), 'big')

Обратное преобразование:

data = m.to_bytes((m.bit_length() + 7) // 8, 'big')
flag = data.decode('ascii')

Automation

from math import gcd


N = <значение из output.txt, строка 1>
E = 65537
C = <значение из output.txt, строка 3>


def integer_nth_root(value: int, degree: int) -> int:
    low = 0
    high = 1
    while high**degree <= value:
        high <<= 1

    while low + 1 < high:
        mid = (low + high) // 2
        if mid**degree <= value:
            low = mid
        else:
            high = mid
    return low


def main() -> None:
    p = integer_nth_root(N, 5)
    if p**5 != N:
        raise ValueError("N is not an exact fifth power")

    phi = p**5 - p**4
    if gcd(E, phi) != 1:
        raise ValueError("E is not invertible modulo phi(N)")

    d = pow(E, -1, phi)
    message = pow(C, d, N)
    data = message.to_bytes((message.bit_length() + 7) // 8, "big")
    print(data.decode("ascii"))


if __name__ == "__main__":
    main()

python3 solve.py
# flag{tw0_plu5_tw0_15_f0ur}

Key Takeaways

Чтение кода как вектор атаки. Уязвимость не в слабых числах, а в неправильной конструкции модуля. Одна строка n = p*p*p*p*p в генераторе делает весь RSA тривиальным для взлома. Читать код задачи — часть технического анализа.
Функция Эйлера для степеней простых. $\varphi(p^k) = p^k - p^{k-1}$ — это не магия, а следствие определения. Умение применять эту формулу напрямую закрывает целый класс учебных RSA-задач.
Целочисленная арифметика в криптографии. Вещественные числа теряют точность на 1024-битных значениях. Бинарный поиск по целым — стандартный инструмент всякий раз, когда нужен точный корень большого числа.