# ugractf-powerful   Задание:  
![image](https://user-images.githubusercontent.com/73061822/109431632-8f7bef80-7a18-11eb-9fc5-9b105683297b.png)
В powerful.key лежит что-то в base64  Разбейзим:  
![image](https://user-images.githubusercontent.com/73061822/109431735-0e712800-7a19-11eb-88b4-8508966c030f.png)
В 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 = "")```  
Получаем флаг:  
![image](https://user-images.githubusercontent.com/73061822/109432121-ce12a980-7a1a-11eb-9017-eafc6fa659f4.png)  
Флаг:  ugra_it_is_too_powerful_rsa_right_...