RCTF 2021 | Uncommon Factors 2 - crypto-writeup-public

#RCTF2021

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の合成数 $N_i = p_iq_i$ が $128$ 個与えられる。このとき $p_i = r*2^{232} + x*2^{104} + \alpha_i$ であり、 $x \sim 2^{128}, r \sim 2^{80}, \alpha_i \sim 2^{104}$ である。目的は $x$ を求めること

このとき $N_i = x*2^{104}q_i + (r*2^{232} + \alpha_i)q_i$ とかいて、 $x*2^{104}$ を求める問題はApproximate GCD Problem

https://eprint.iacr.org/2014/548.pdfによればこの問題は次のような格子のLLLで解ける

$\begin{bmatrix} K & N_2 & N_3 & \dots & N_k \ & -N_1 \ & & -N_1 \ & & & \ddots \ & & & & -N_1 \end{bmatrix}$

うーん未だにApproximate GCDがこれでとけるのがよくわかってないが解ける

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)