writeup-for-2021-RCTF

Posted on Edited on In Word count in article: 2.7k Reading time ≈ 2 mins.

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"))

尝试做出来了, 看看整个流程, 可以知道的式子

两边整除再把拆出来就有
也就是
把括号里的看成一个整体, 求就可以看成是一个问题了, 题目也给了很多个, 构造常规的格子就行了

调整参数规约格子就能得到了, 有了求就简单了

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))