Tags: crypto
Rating:
We are given a slow [decryption code](https://github.com/CTF-STeam/ctf-writeups/tree/master/2021/UgraCTF/decrypt.py), which we have to improve to make it decrypt the ciphertext.
Here's the most important part:
```python
for a, (b, n), (c, d) in zip(
encrypted_data,
key["common_key"],
key["private_key"]
):
x = (a ** b) ** (c ** d)
c1 = chr((x % n) % 256)
c2 = chr((x % n) // 256 % 256)
c3 = chr((x % n) // 65536)
```
So powerful. This code can be improved using some modular arithmetic properties:
- `x^a = (x % n)^a (mod n)`
- `x^phi(n) = 1 (mod n)`
So the above code can be improved as below:
```python
for a, (b, n), (c, d) in zip(
encrypted_data,
key["common_key"],
key["private_key"]
):
ab = pow(a, b, n)
cd = pow(c, d, phi(n))
x = pow(ab, cd, n)
c1 = chr((x % n) % 256)
c2 = chr((x % n) // 256 % 256)
c3 = chr((x % n) // 65536)
```
(Full code: [decrypt_solve.py](https://github.com/CTF-STeam/ctf-writeups/tree/master/2021/UgraCTF/decrypt_solve.py))
Flag: `ugra_it_is_too_powerful_rsa_right_d412d60205d`
