1. decompile the challenge binary file, easy to understand, nothing to say
 
1.  In file backdoor.py found that:
```ctxt = (pow(g, int.from_bytes(ptxt, 'big'), n_sq) * pow(r, n, n_sq)) % n_sq```
because of :  
```ctxt == (g ^ ptxt) * (r ^ n)   mod  n_sq=>  ctxt^a == ((g ^ ptxt) * (r ^ n))^a   mod  n_sq=>  ctxt^a == (g ^ ptxt)^a  * (r ^ n)^a   mod  n_sq=>  ctxt^a == (g ^ (ptxt*a))  * ((r ^a)^ n)  mod  n_sq```
lookat backdoor.py :
```    while True:        r = random.randrange(1, n)        if gcd(r, n) == 1:            break```
when execute backdoor.py without arguments, it will print the cipher result of 'ls' (ptxt)
So we need to find a payload instead of 'ls', and the payload :   int(palyload)  == int('ls') * n
because of:
```def run(msg: dict):    ptxt = dec(msg['hash'], msg['ctxt'])    subprocess.run(ptxt.split())```
we use the follow script to find out payload and n:
```from Crypto.Util.number import long_to_bytes, bytes_to_long
ls = bytes_to_long(b'ls')
# char in bytes.split() is seperatorTAB = b' \x09\x0a\x0b\x0c\x0d'
sh_b = b'sh'for i0 in TAB:    for i1 in TAB:        for i2 in TAB:            for i3 in TAB:                for i4 in TAB:                    for i5 in TAB:                        b = sh_b + bytes([i0, i1, i2, i3, i4, i5])                        a = bytes_to_long(b)%ls                        if a==0:                            n = bytes_to_long(b)//ls                            print(n, b)                            break
# b = ls * n```
 After run it, we got  payload: b'sh\t \x0c\t\r ', and n = 299531993847392
Finally, write the full exploit:
```#!/usr/bin/env python3import json
from pwn import *
HOST = os.environ.get('HOST', 'localhost')PORT = 31337
io = remote(HOST, int(PORT))
# GET THE 'ls' cipher resultio.recvuntil(b'> ')io.sendline(b'5')ret = io.recvuntil(b'Welcome to Shiny Shell Hut!')idx = ret.index(b'{"hash":')end = ret.index(b'}', idx + 1)msg = ret[idx:end+1]msg = json.loads(msg)
ctxt = msg["ctxt"]n = msg["n"]
# MAKE new payloadpayload = b'sh\t \x0c\t\r 'h = int(hashlib.sha256(payload).hexdigest(), 16)ctxt = pow(ctxt, 299531993847392, n*n)msg = {'hash': h, 'ctxt': ctxt, 'n': n}io.sendline(b'4'+json.dumps(msg).encode())io.interactive()```
