We are given the following script.

#!/usr/bin/env python3

from Crypto.PublicKey import RSA
from Crypto.Util import number
from Crypto.Util.number import bytes_to_long, long_to_bytes
import sys
from secret import flag

key = RSA.generate(2048, e = 3)

def encrypt(msg : bytes, key) -> int:
    m = bytes_to_long(msg)
    if m.bit_length() + 128 > key.n.bit_length():
        return 'Need at least 128 Bit randomness in padding'
    shift = key.n.bit_length() - m.bit_length() - 1
    return pow(m << shift | number.getRandomInteger(shift), key.e, key.n)

def loop():
    print('My public modulus is:\n%d' % key.n)
    print('Here is your secret message:')
    print(encrypt(flag, key))

    while True:
        print('You can also append a word on your own:')
        sys.stdout.flush()
        PS = sys.stdin.buffer.readline().strip()
        print('With these personal words the cipher is:')
        print(encrypt(flag + PS, key))

if __name__ == '__main__':
    try:
        loop()
    except Exception as err:
        print(repr(err))

The service encrypts the flag + our input + a random padding, we can minimize the padding by sending the longest input allowed, so the random padding will be around 128 bits, since the e = 3, we can do a coppersmith short pad attack to recover the flag.

The script originated from here.

# sage
from Crypto.Util.number import *

def short_pad_attack(c1, c2, e, n):
    PRxy.<x,y> = PolynomialRing(Zmod(n))
    PRx.<xn> = PolynomialRing(Zmod(n))
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))

    g1 = x^e - c1
    g2 = (x+y)^e - c2

    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)

    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()

    kbits = 130
    diff = h.small_roots(X=2^kbits, beta=0.5, epsilon=1/30)[0]  # find root < 2^kbits with factor >= n^0.5

    return diff

def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]

from pwn import *
ps = b"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
e = 3
r = remote("52.59.124.14",int(10009))
r.recvuntil("My public modulus is:\n")
n = int(r.recvline().strip())
r.recvline()
r.sendlineafter("You can also append a word on your own:\n", ps)
r.recvline()
C1 = int(r.recvline().strip())
r.sendlineafter("You can also append a word on your own:\n", ps)
r.recvline()
C2 = int(r.recvline().strip())
print(n, C1, C2)
assert C1 != C2

diff = short_pad_attack(C1, C2, e, n)
m = related_message_attack(C1, C2, diff, e, n)
print(long_to_bytes(int(m)))