README.md

ugractf-powerful

Задание:

В powerful.key лежит что-то в base64
Разбейзим:

В decrypt.py привлекает эта строка:

x = ((a ** b) ** (c ** d)) % n
    c1 = chr((x % n) % 256)
    c2 = chr((x % n) // 256 % 256)
    c3 = chr((x % n) // 65536)

Получается, что мы можем улучшить алгоритм - перед каждым возведением в степень брать остаток a от n.
Однако этого недостаточно, ведь надо избавиться от (c ** d)
С этим нам помогает теорема Эйлера (https://ru.wikipedia.org/wiki/Теорема_Эйлера_(теория_чисел))
a и n - взаимно просты (НОД(a, n) == 1)
Следовательно, можно сколько угодно раз сокращать степень a на phi(n) (функция Эйлера),
т.к a^phi(n) - все равно, что единица, если в итоге мы возьмем все по модулю n

Итого улучшим код:

# Функция эйлера
def euler(n):
    r = n
    i = 2
    while i*i <= n:
        if n % i == 0:
            while n % i == 0:
                n //= i
            r -= r//i
        else:
            i += 1
    if n > 1:
        r -= r//n
    return r

encrypted_data = [7694194, 12679249, 22673605, 26642998, 10281324, 2484993, 3301680, 26131280, 6865248, 19303891, 46900148, 19716783, 10473459, 42921375, 1869927]

common_key = [[1, 50041451], [17045939, 22409533], [38326205, 43588471], [13285757, 29508329], [16605031, 25857479],
              [19973635, 22035437], [28748477, 33483613], [19772147, 29395493], [14750489, 37890373],
              [22009967, 31043153], [8630093, 46977407], [7037449, 25618013], [19066073, 21727201],
              [17161541, 55059869], [4231027, 27977503]]

private_key = [[1, 1], [6857117, 22088735], [11002793, 41094781], [25733503, 20761384], [24639809, 9722971],
               [6568487, 14240680], [22286801, 21248597], [13389587, 16288757], [21388063, 35415551],
               [9747529, 10052210], [33093259, 31613673], [20074495, 9292667],
               [10015109, 19952694], [27543217, 36139021], [27039463, 11090510]]

for a, (b, n), (c, d) in zip(encrypted_data, common_key, private_key):
    p = c
    t = euler(n)
    for i in range (1, d):
        c *= p
        c = c % t #Каждый раз берем остаток
    p = a
    for i in range (1, b):
        a *= p
        a = a % n #Каждый раз берем остаток
    p = a
    for i in range (1, c):
        a *= p
        a = a % n #Каждый раз берем остаток
    c1 = chr(a % 256)
    c2 = chr(x // 256 % 256)
    c3 = chr(x // 65536)
    print(c3 + c2 + c1, end = "")

Получаем флаг:

Флаг:
ugra_it_is_too_powerful_rsa_right_...