RTACTF | Neighbor RSA

#rtactf

import os

# Plaintext (FLAG)
plaintext = os.getenv("FLAG", "FAKE{sample_flag}").encode()
plai  = plaintext[:len(plaintext)//2]
ntext = plaintext[len(plaintext)//2:]
m1 = int.from_bytes(plai  + os.urandom(128), 'big')
m2 = int.from_bytes(ntext + os.urandom(128), 'big')

# Generate key
e = 65537
p = random_prime(1<<2048)
q = random_prime(1<<512)
r = random_prime(1<<512)
n1 = p * q
n2 = next_prime(p) * r
assert m1 < n1 and m2 < n2

# Encryption
c1 = pow(m1, e, n1)
c2 = pow(m2, e, n2)

# Information disclosure
print(f"e = {hex(e)}")
print(f"n1 = {hex(n1)}")
print(f"n2 = {hex(n2)}")
print(f"c1 = {hex(c1)}")
print(f"c2 = {hex(c2)}")

#RSA

• 

• 

が2048bit、が512bitとサイズに大きな差があるので

Approximate GCD ProblemとしてLLL、あるいは連分数展開で解ける

連分数展開ならが十分小さいので解ける、ということ

あるいはunivariate coppersmith methodでも解ける。で、これが2048bitに対して十分に小さいのでで程度

with open("output.txt") as f:
  e = int(f.readline().strip().split(" = ")[1], 16)
  n1 = int(f.readline().strip().split(" = ")[1], 16)
  n2 = int(f.readline().strip().split(" = ")[1], 16)
  c1 = int(f.readline().strip().split(" = ")[1], 16)
  c2 = int(f.readline().strip().split(" = ")[1], 16)



# e = 65537
# p = random_prime(1<<2048)
# q = random_prime(1<<512)
# r = random_prime(1<<512)
# p2 = next_prime(p)
# 
# n1 = p * q
# n2 = p2 * r

K = 2**512
M = matrix(ZZ, [
  [K, 0, n1],
  [0, K, -n2],
])

L = M.LLL()
for row in L:
  zs = [int(abs(x//K)) for x in row]
  for r in zs:
    if r == 0 or r == 1:
      continue
    if n2 % r != 0:
      continue

    p2 = n2 // r
    print(r, p2)
    p = previous_prime(p2)
    q = n1 // p

    print(p, q, r)

    d1 = int(pow(e, -1, (p-1)*(q-1)))
    d2 = int(pow(e, -1, (p2-1)*(r-1)))

    m1 = pow(c1, d1, n1)
    m2 = pow(c2, d2, n2)

    print(hex(m1)[2:] + hex(m2)[2:])