Approximate GCDとして解く問題 - RCTF 2021 Uncommon Factor 2 / Midnightsun CTF 2021 Finals Flåarb.tar.xz writeup

時期が近くて解法が近いので2件writeupです

RCTF 2021 Uncommon Factor 2

from multiprocessing import Pool

size = 2^7

flag = open("flag.txt", "rb").read()
assert len(flag) == 22
assert flag[:5] == b"flag{"
assert flag[-1:] == b"}"
seed = flag[5:-1] # 128 bit
seed = (int.from_bytes(seed,'big')<<104) + (randint(0,2^80)<<(128+104)) # 312 bit
ub = seed + 2^104
lb = seed

threads = 64

def f(i):
    p = random_prime(ub, lbound=lb, proof=False)
    q = random_prime(2**200, proof=False)
    N = p*q
    return N

def reseed(i):
    set_random_seed()

pool = Pool(processes=threads)
pool.map(reseed,range(size))
lN = pool.map(f,range(size))
pool.close()
pool.join()

lN.sort()
with open("lN.bin","wb") as f:
    for n in lN:
        f.write(int(n).to_bytes(512//8,"big"))

512bitの合成数が128個与えられます。それぞれという形式になっています。多少開いていみるととかけます。

が比較的小さければからを求める問題はApproximate GCD Problemとして知られており、簡単なインスタンスは次のような格子のLLLで解けます。確かにこの基底で解かれそうなことはわかるのですが、どうやってこの格子を思いつけば良いのかが未だにわかっていません。

from ptrlib import chunks

with open("lN.bin", "rb") as f:
    data = f.read()

ns = chunks(data, 512 // 8)
ns = [int.from_bytes(n, "big") for n in ns]

ns = list(set(ns))
print("[+] done {}".format(len(ns)))

K = 2^(104 + 128)

M = matrix.identity(len(ns)) * - ns[0]
M[0,0] = K
for i in range(1, len(ns)):
  M[0,i] = ns[i]

t1 = cputime()
print("[+] {}x{} LLL...".format(M.nrows(), M.ncols()))
L = M.LLL()
t2 = cputime()
print("[+] done in {}".format(t2 - t1))

v = Matrix(ZZ, L[0])
v = v * M^(-1)

q = int(v[0,0])
print(ns[0] % q)
print(ns[0] // q)

Midnightsun CTF 2021 Finals Flåarb.tar.xz

なんでこんな問題名なんだろう

次のようなファイルが与えられます（長い数値は省略しています）。どうしてこんな形式にしたんだろう。そういえばMidnightsunのCrypto問題は毎回こういう形式ですね。

sage: p1 = random_prime(2^2048) 
....: p2 = next_prime(0xcafebabe * p1 + randint(0, 2^1024)) 
....:  
....: q1 = random_prime(2^512) 
....: q2 = random_prime(2^512) 
....:  
....: n1 = ZZ(p1 * q1) 
....: n2 = ZZ(p2 * q2)                                                                                                                                                                                                                                                                                                                                             
sage: c1 = pow(int.from_bytes(flag, byteorder='little'), 2^16 + 1, n1) 
....: c2 = pow(int.from_bytes(flag, byteorder='little'), 2^16 + 1, n2)                                                                                                                                                                                                                                                                                             
sage: n1                                                                                                                                                                                                                                                                                                                                                           
...
sage: n2                                                                                                                                                                                                                                                                                                                                                           
...
sage: c1                                                                                                                                                                                                                                                                                                                                                           
...
sage: c2                                                                                                                                                                                                                                                                                                                                                           
...

つまり という形式のRSAで、がかなり小さいです。 と近似できるので、こちらもApproximate GCDとして解くことができます。

n2_ = n2 // 0xcafebabe

for i in range(512):
  K = 2^(1024 + i)

  M = Matrix([
      [K, 0, n1],
      [0, K, -n2_],
  ])
  L = M.LLL()

  for row in L:
      # ys = [abs(x) for x in row]
      zs = [abs(x//K) for x in row]
      for q in zs:
        for n in [n1, n2]:
          g = (gcd(n, q))
          if g != 1:
            print(g, q)

しかしこの問題の想定解は連分数展開らしいです。どうやって思いつくんだろう