[SECCON CTF 2022] this_is_not_lsb

prob.py

 

from Crypto.Util.number import *
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
e = 65537
n = p * q
phi = (p - 1) * (q - 1)

d = pow(e, -1, phi)

print(f"n = {n}")
print(f"e = {e}")
print(f"flag_length = {flag.bit_length()}")

# Oops! encrypt without padding!
c = pow(flag, e, n)
print(f"c = {c}")

# padding format: 0b0011111111........
def check_padding(c):
    padding_pos = n.bit_length() - 2
    m = pow(c, d, n)

    return (m >> (padding_pos - 8)) == 0xFF


while True:
    c = int(input("c = "))
    print(check_padding(c))

 

In textbook RSA, when ciphertext $E(P) = P^e$ is given, ciphertext for $E(P' = mP) = P^e \cdot m^e$  can be easily calculated without knowing $P$.

 

When we send $c \cdot M^e$, we can check whether $2^{1022} - 2^{1024} \leq flag \cdot M \leq 2^{1022} -1$ or not.

 

Once we find appropriate $M$ satisfies 2^{1022} - 2^{1024} \leq flag \cdot a$, then set $a$ as lower bound and possible to recover maximum $M$ such that $flag \cdot M \leq 2^{1022} -1$ using binary search.

 

solver.py

 

from pwn import *
from Crypto.Util.number import *
r = remote("this-is-not-lsb.seccon.games", 8080)


r.recvuntil(" = ")
n = int(r.recvline())
r.recvuntil(" = ")
e = int(r.recvline())
r.recvuntil(" = ")
flag_len = int(r.recvline())
r.recvuntil(" = ")
c = int(r.recvline())


def query(factor):
  r.recvuntil(" = ")
  val = c * pow(factor, e, n) % n
  r.sendline(str(val).encode())
  z = r.recvline()
  return z == b'True\n'

st = 2**438
en = 2**439 - 1

factor = 2**576 * 196

for i in range(584,-1,-1):
  adder = 2**i
  while query(factor + adder):
    factor += adder
    print("!! add",i)


#factor = 48663794436922351897392835332645276106957960444910813902095379757782525882180340752407585793044725993977469588294850480616647015758190038588490706033703755590689470468363797990
  
flag = (2**1022 - 1)//factor


print(long_to_bytes(flag))