0%

摸鱼Writeup-3

ByteCTF2021 Final

acyclic group

另外几道题没什么说的,这道题比赛的时候折磨了我很久。。。最后几分钟差一点想出来但还是没出。

代码如下:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#!/usr/bin/env python3
from hashlib import sha256
from random import choices, getrandbits, randint
import signal
import string

from flag import FLAG


def proof_of_work() -> bool:
alphabet = string.ascii_letters + string.digits
nonce = "".join(choices(alphabet, k=8))
print(f'SHA256("{nonce}" + ?) starts with "000000"')
message = (nonce + input().strip()).encode()
return sha256(message).digest().hex().startswith("000000")


def gen_modulus():
primes = [
2, 3, 5, 7, 11, 13, 17, 19,
23, 29, 31, 37, 41, 43, 47, 53,
59, 61, 67, 71, 73, 79, 83, 89,
97, 101, 103, 107, 109, 113, 127, 131,
]
n = 1
t = []
for p in primes:
tmp_t = randint(1, 16)
n *= p ** tmp_t
t.append(tmp_t)
return n, t


def test() -> bool:
n, _ = gen_modulus()
e = randint(1, n)
for i in range(3):
try:
num = input().strip()
except EOFError:
return False
if not str.isnumeric(num):
return False
num = int(num)
if num == n:
return True
res = pow(num, e, n)
print(res)
return False


def main():
signal.alarm(60)
if not proof_of_work():
return
print("Listen...I have some acyclic groups for you..."
"No noise this time...God bless you get them...")
passed = 0
T = 256
signal.alarm(T)
for i in range(T):
print("Round", i)
if test():
passed += 1
print("GOOD SHOT, MY FRIEND")
else:
print("CALM DOWN, MY FRIEND")
if passed > T * 0.8:
print("CONGRATULATIONS", FLAG)


main()

可以看到是一个类似oracle的猜数题,可以传两次消息\(m_0, m_1\),然后得到\(m_0^e\mod n, m_1^e \mod n\)。而 \(n\) 是由一个指定素数集构成的,指数随机生成,于是我最早考虑计算primes所有素数的积\(N\),那么必然有\(N | n, n | N^{16}\),这样传入\(k_1N^{k_0}, k_2N^{k_0}\),得到\(c_0, c_1\)\(k_2*c_0 - k_1*c_1\) 必然是n的倍数,再通过一些简单的过滤则有可能得到\(n\),但这样的理论概率极限也就是\(0.5\),而题目需要大于\(0.8\),实验中最多也就到\(0.55\)左右。

于是考虑别的想法,找到\(N^{16}\) 上的\(k_1\) 次根\(x_1\)\(k_2\)次根 \(x_2\),然后传入\(x_1, x_2\),得到\(c_0, c_1\), 有\(c_0^{k_1} - 1 \equiv 0 \mod n, c_1^{k_2} - 1 \equiv 0 \mod n\), 则可以计算\(GCD(c_0^{k_1} - 1, c_1^{k_2} - 1 )\) 来得到n的倍数。当\(k_1, k_2\) 取到较大的两个素数时(测试中53,41为最佳),\(GCD(c_0^{k_1} - 1, c_1^{k_2} - 1 )\) 中的多余小因子很少,这样结合一些过滤可以稳定到 $ 0.6$ 左右的概率,实验中最高得到182/256次,距离要求仍然相差甚远。

赛后和Hermes聊这题,他用了先验奇数的思想,即先传一个\(x_0, x_0 \equiv 2 \mod 3\),如果返回的\(c_0 \equiv 2 \mod 3\) ,那么e为奇数,反之为偶数,如果是奇数,第二个直接传\(-x_0 \mod N^{16}\) 即可,这样天然是\(0.5+\) 的概率,只需要考虑e为偶数的情况即可。

于是我将这个先验思想与之前的想法结合,由于只有2次根模3上为2,故考虑第一个数传2次根与一个53次根的积,然后根据返回的\(c_0\)判断e的奇偶性,如果为奇数则直接得到n,反之使用之前的方法,传入41次根,计算GCD并过滤,这里使用的过滤也很简单,用了一个简单的check函数:

1
2
3
4
5
def ez_check(x, tmp_n, tmp_c, index):
for j in range(1, index):
if pow(x, j, tmp_n) == tmp_c:
return True
return False

判断现有的n和c是否匹配,虽然不能完全判别正确性,但可以过滤掉一部分n,不加过滤的话,是无法到达0.8的要求的。

于是得到完整的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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
from Crypto.Util.number import *
from tqdm import tqdm
from random import randint


primes = [2, 3, 5, 7, 11, 13, 17, 19,
23, 29, 31, 37, 41, 43, 47, 53,
59, 61, 67, 71, 73, 79, 83, 89,
97, 101, 103, 107, 109, 113, 127, 131]
N = 525896479052627740771371797072411912900610967452630


def ez_check(x, tmp_n, tmp_c, index):
for j in range(1, index):
if pow(x, j, tmp_n) == tmp_c:
return True
return False


def gen_modulus():
n = 1
t = []
for p in primes:
tmp_t = randint(1, 16)
n *= p ** tmp_t
t.append(tmp_t)
return n, t


X53 = 16146763596179907622493109012827107483432127255282437968769511754257220353461373199051318700354563705501798111116975423559551919422360373620077135733152834339753566421633318551588422901547881579218520776006792486613397971515271604855586579740039260074131940980987975405945266243817124527776349845008796650597901430324561617712539448004335786983097258035189240029672607297470279777590671871429356611345024068708210664204032378937951457734824660588211295536984531224843323388692707230473974167062051827530633678063778393771712605759122050047549153324446713490868711015327552083786926047655742819801159119820050854801807132456468704631166477801370570144842420484203774449336692121369166894459616914719270555761434836110634387526761779763136974433072352065708061222706777945829022683408311193928882620000000000000001
X41 = 14433742236573688560360048613517053763200707683208778120848086283299329941013908083365456158136248365405808895787635075734246983533602171353983415139484130546490622760668175853268336625517248976893430593633591158403560983700284581913439756565424800771408850504240484768112546298539809747045454017191685052792871835571611728801542959691013910881345442147407305419751546631888734401332725798315194326822778940702909396121047842327694640911259501609831936278582897452598156308636522732156722313669233126732015453396069197186228360843076869905501365431573710803270781244583676572897758932558706108800668583084492823482604125931433024709087840253930862552870791179735998515105708049484833368876195836038931796305023286562526358223498002848846916276239224031232879423197037204854042451328998802974875960000000000000001
X2 = 15845692616563450127497208839410301344402316795683874456673644728074297254230460786999608268999620577402794405164458414337023127673742026008021414589602557158573546834697406978953669032292544682264032538283813482564370439284759728142958678735148370476425664417360562433032379231110074243013706826953064966499154160963062921354644984286660194677706265414862607876360639364289269590679134724946975491236100718964941807053660511056670515549359602825507165267329870326738546498444951189947310784787069656189398361340810771090331973605773043378424416612980873234071900022982273879970686574341215845470279225478293269284360469028535434817147966175875953360972917337632136468352618104434531745056493725241600130859431706675615178872943525346567519727470007647885832252355970578673569499720213721708193542519836425781249
length = 90
M = N**16
test_length = 2049
times = 0
not_times = 0
pass_times = 0
t0 = 53 * 2
t1 = 41
x0 = (X2 * X53) % M
x1 = X41
for i in tqdm(range(256)):
n, t = gen_modulus()
e = randint(1, n-1)
c0 = pow(x0, e, n)
if c0 % 3 == 2:
c1 = pow(-x0 % M, e, n)
my_n = c1+c0
assert my_n == n
times += 1
continue

c1 = pow(x1, e, n)
tmp0 = pow(c0, t0, M) - 1
tmp1 = pow(c1, t1, M) - 1
if tmp0 == 0:
tmp0 = x0 - 1
if tmp1 == 0:
tmp1 = x1 - 1

sn = GCD(tmp0, tmp1)
my_n = 1
for prime in primes:
i = 1
while sn % prime ** i == 0 and i <= 16:
i += 1
my_n *= prime ** (i - 1)

if not (ez_check(x0, my_n, c0, t0) and ez_check(x1, my_n, c1, t1)):
for l in range(2, test_length):
if my_n % l != 0:
continue
tmp = my_n // l
if ez_check(x0, tmp, c0, t0) and ez_check(x1, tmp, c1, t1):
my_n = tmp
break

if my_n == n:
times += 1
if ez_check(x0, my_n, c0, t0) and ez_check(x1, my_n, c1, t1) and my_n != n:
pass_times += 1
if tmp0 < n or tmp1 < n:
not_times += 1
print('times: %d' % times)

运行后发现通过率可以满足题目要求:

总体来说这题还是比较有意思的,但是对于为什么两个较大素数根做GCD的小因子很小尚未探究,也期待官方WP有比较好的解释。