Rating:
# ugractf-powerful
Задание:
В powerful.key лежит что-то в base64
Разбейзим:
В decrypt.py привлекает эта строка:
```python
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
Итого улучшим код:
```python
# Функция эйлера
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_...
