**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

```

Original writeup (https://github.com/pberba/ctf-solutions/tree/master/20181223_xmasctf/crypto-328-santas_list_(2.0)).