Rating:
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)))
```
