Uncommon Factor Ⅰ

problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from multiprocessing import Pool

size = 2^22

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')<<48) + (randint(0,2^24)<<(128+48)) # 200 bit
ub = seed + 2^48
lb = seed

threads = 64

def f(i):
    p = random_prime(ub, lbound=lb, proof=False)
    q = random_prime(2**312, 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"))

参数的大小变了, AGCD不管用了, 等爷爷wp了,

Uncommon Factor Ⅱ

problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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"))

尝试$AGCD$做出来了, 看看整个流程, 可以知道$n$的式子
$$
n_i = (2^{232} \cdot r_i + 2^{104} \cdot flag + R_i)q_i
$$
两边整除$2^{104}$再把$flag$拆出来就有
$$
{n_i \over 2^{104}} = flag \cdot q_i + (2^{128} \cdot r_i \cdot q_i + {R_iq_i \over 2^{104}})\
也就是
{n_i \over 2^{104}} = flag \cdot q_i + (2^{128} \cdot r_i \cdot q_i + \hat R_i)
$$
把括号里的看成一个整体, 求$flag$就可以看成是一个$AGCD$问题了, 题目也给了很多个$n$, 构造常规的格子就行了
$$
\begin{pmatrix}
2^a & n_1 & n_2 & \cdots & n_i \
0 & -n_0 & 0 & \cdots & 0 \
0 & 0 & -n_0 & \cdots & 0 \
\vdots&\vdots&\vdots&\ddots&\vdots \
0 &0&0&\cdots&-n_0
\end{pmatrix}
$$
调整参数$a$规约格子就能得到$q_0$了, 有了$q_0$求$flag$就简单了

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from sage.all import *
from Crypto.Util.number import bytes_to_long,long_to_bytes
with open('lN.bin','rb') as f:
    file = f.read()

lN = []
for i in range(0,len(file),64):
    lN.append(bytes_to_long(file[i:i+64]))
    

N = []
for n in lN:
    a = n // 2**104
    if a not in N:
        N.append(a)
LEN = len(N)
B = LEN
print(LEN)
M = [[0 for _ in range(B)] for _ in range(B)]
for i in range(500):
    M[0][0] = 2 ** i
    for j in range(1,B):
        M[0][j] = N[j]
        M[j][j] = -N[0]
    RES = Matrix(M).LLL()[0]
    if RES[0] % 2 ** i == 0:
        q = abs(RES[0] // 2 ** i)
        if q != 0 :
            R = N[0] % q
            m = ((N[0] - R) // q) % 2 ** 128
            print(long_to_bytes(m))