Tags: crypto rsa 


## 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,

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...')
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.

e = 65537
n = get_n()
m = flag*(n-1) % n
pt = decrypt(m)

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,

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)).