Tags: crypto rsa
Rating:
## Solution
Notice that the flag is encrypted using _textbook-rsa_, which means that the plaintext is malleable. To illustrate the general idea, let us first solve a simpler version of this problem.
### Simpler version of the problem
If the problem given was the following,
```python
for i in range(5):
if choice == '1':
m = bytes_to_long(input('\nPlaintext > ').strip().encode())
print('\nEncrypted: ' + str(encrypt(m)))
elif choice == '2':
c = int(input('\nCiphertext > ').strip())
if c == flag_encrypted:
print('Ho, ho, no...')
else:
print('\nDecrypted: ' + str(m))
```
Since the ciphertext is malleable, then we can mutate the ciphertext in a way that is predictable to us.
```
ct_flag = encrypt(flag) = flag^e mod n
ct_two = encrypt(2) = 2^e mod n
ct_not_flag = ct_flag*ct_two = (flag*2)^e mod n
```
Therefore, `decrypted(ct_not_flag) = flag*2`
But this problem _does not allow_ this. So we have to look for a way to manipulate the ciphertext.
### Solving the current version
Let's say we have the public key `(n, e)`, then we can bypass the `Ho, ho, no...`
```
ct_flag = encrypt(flag) = flag^e mod n
ct_neg = encrypt(-1) = -1^e mod n = -1 mod n
ct_not_flag = ct_flag*ct_neg = (flag*-1)^e mod n
```
Which means that `decrypted(ct_not_flag) = flag*-1 mod n`, and we can easily recover the flag from that.
```python
e = 65537
n = get_n()
m = flag*(n-1) % n
pt = decrypt(m)
print(long_to_bytes((pt*(n-1))%n))
```
But this requires us to be able to get `n` and `e`.
### Getting the public key
Getting `e` is easy because the default value is `e = 65537` and we are left to find `n`.
It's easy to show that for some `m`, then `m**65537 - encrypt(m)` is a multiple of `n`, and for some cases,
```
n = gcd(m1**65537 - encrypt(m1), m2**65537 - encrypt(m2))
```
You can get the GCD of several residuals to make it more likely that you have gotten `n`.
We implement this using,
```python
e = 65537
def get_resid(i):
return i**e - encrypt(i)
def get_n():
curr = get_resid(bytes_to_long('a'))
for i in [bytes_to_long('b'), bytes_to_long('c')]:
curr = GCD(curr, get_resid(i))
return curr
```
