这次 medium 分类题量是最多的，内容方面是最丰富的，两极分化比较严重。

有脑筋急转弯的，有考察 SageMath API 使用的，有 MISC 题目混进来的……

总之 medium 分类最难的比 tough 还要更难……

TPSD

题目描述

题目基于一个不定方程：

其中解 $p, q, r$ 至少要有一个素数。每次提交结果，都要求最小值的比特数在限定范围内。

我的解答

自己瞎几把想+乱试了好久没想出个所以然来，所以直接抄答案：

https://www.ams.org/journals/mcom/2007-76-259/S0025-5718-07-01947-3/S0025-5718-07-01947-3.pdf

In 1936, Mahler discovered a parametric solution for $k = 1$:

他丫是真的牛逼，这种东西靠自己想是完全他妈的想不出来的，只能说人与人之间智商的差距是最令人绝望的……

所以就直接抄就行了，至于要满足素数的条件，就是撞大运。另外经过测试，发现负数也能被算成素数，也就是说远程 check 是否为素数是拿绝对值去 check 的。那就无脑撞 $9t^3-1$ 为素数就行。

顺便吐槽一下远程：代码不可见，提示模糊，所以导致大家都不知道输入的格式到底是啥，而且也不知道要交多少组答案才到头……

代码如下：

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
from pwn import *
import random
from Crypto.Util.number import *

context.log_level = 'debug'

class Gao:
    def __init__(self) -> None:
        self.conn = remote('05.cr.yp.toc.tf', 11137)
    
    def gao_one(self):
        self.conn.recvuntil('+ almost')
        s = self.conn.recvline()
        l, r = eval(s.split(b'-')[0])
        while True:
            t = random.getrandbits((l + r) // 6)
            A, B, C = 9 * t**4, 3*t - 9*t**4, 1 - 9*t ** 3
            if (isPrime(-C)):
                if (l <= min(x.bit_length() for x in (A, B, C)) <= r):
                    break
        
        assert A**3 + B**3 + C**3 == 1
        self.conn.sendline(f'{A},{B},{C}')
    
    def gao(self):
        for i in range(20):
            self.gao_one()
        self.conn.interactive()

if __name__ == '__main__':
    g = Gao()
    g.gao()

得到 flag 为：

1
CCTF{pr1m3S_in_7ErnArY_Cu8!c_3qu4tI0nS!}

Trex

题目描述

题目基于一个不定方程：

其中 $a$ 为一个随机数。对于每个 $a$，都需要求出一组解 $(x, y, z)$ 保证这三个数两两不相等，且均不为 0.

我的解答

既然要求 $x \ne y$，那么直接令 $y=x + t$，后面的构造中别让 $t = 0$ 就行。

那么 $x^2 + y^2 - xy = (x - y)^2 + xy = t^2 + x^2 + xt$

然后就是 $x^2 + xt + t^2 = a z^3$。

为了简化方程形式，直接令 $x = t$，那么就是 $3t^2 = a z^3$

直接令 $t = 3 a^2, z = 3a$ 即可。

所以得到一组解：$(x, y, z) = (3a^2, 6a^2, 3a)$。

然后代进去交答案就行。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from pwn import *

context.log_level = 'debug'

class Gao:
    def __init__(self) -> None:
        # self.conn = process(['python3', 'another.py'])
        self.conn = remote('03.cr.yp.toc.tf', 31317)
    
    def gao_one(self):
        self.conn.recvuntil('Level ')
        s = self.conn.recvline().decode()
        a = int(s.split('=')[1].split('*')[0])
        x, y, z = 3 * a**2, 6 * a**2, 3 * a
        self.conn.sendline(f'{x},{y},{z}')
    
    def gao(self):
        for i in range(19):
            self.gao_one()
        self.conn.interactive()

if __name__ == '__main__':
    g = Gao()
    g.gao()

得到 flag 为：

1
CCTF{T3rn3ry_Tr3x_3Qu4t!0n}

Keymoted

题目描述

首先 $N=pq$，其中 $p$ 为 256 位素数，$s = p \oplus 2^{255} \oplus 2^{128}$，$q$ 为不小于 $2s+1$ 的最小素数。$N$ 已知。

然后是在 $\mathbb{Z}_n$ 下定义椭圆曲线 $E_n: y^2 = x^3 + ax + b$，其中 $a, b$ 已知。

然后还生成了 $e$，并记 $\mathbb{Z}_p$ 下的椭圆曲线的阶为 $n_p$，$\mathbb{Z}_q$ 下的椭圆曲线的阶为 $n_q$。记 $t_p = p + 1 - n_p$，$t_q = q + 1 - n_q$，题目保证给出的 $e$ 满足

然后题目在 $E_n$ 上，用 flag 转成整数之后作为横坐标 $m$，如果 $m^3 + a m + b$ 不为模 $N$ 的二次剩余那就将 $m$ 加 1，加到为二次剩余为止。此时就可以对应一个点 $P$，然后计算 $Q = e P$，已知 $Q$，试求 $m$。

我的解答

这应该是一个经典的椭圆曲线问题，只需要注意到 $E_n = E_p \oplus E_q$ 就可以了（事实上这道题的椭圆曲线上随机生成点也是基于此来做的，首先生成一个横坐标 $x$ 满足 $x^3 + ax + b$ 同时为模 $p$ 和模 $q$ 的二次剩余，然后在 $\mathbb{Z}_p$ 和 $\mathbb{Z}_q$ 下分别开根，最后用中国剩余定理组合出 $y$）。求出 $e$ 在分别模 $n_p$ 和模 $n_q$ 下的逆 $d_p$ 和 $d_q$，并求出 $P_p = d_p Q$ 以及 $P_q = d_q Q$，最后用中国剩余定理组合出 $P$ 的横坐标即可。

所以实际上问题主要还是在得到 $N=pq$ 的分解上。

因为 $p$ 为 256 位素数，所以在 $p$ 的二进制表示

中，$p_{255}$ 必为 1。然后 $p_{128}$ 不确定是啥，所以有等式

或

实际是哪个还需要试。

然后有 $q = 2 s + 1 + t$，根据 $N = pq$ 就可以建立一个关于 $p$ 与 $t$ 的等式。因为 $t$ 较小，可以忽略，所以可以先大概看成是关于 $p$ 的二次方程，套公式解得一个大概的 $p’$，这个解出的 $p’$ 应该和真实的 $p$ 接近。然后用 Coppersmith 方法试求真正的 $p$。如果求得出来，那就说明之前等式假设正确了。代码如下：

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
pkey = (6660938713055850877314255610895820875305739186102790477966786501810416821294442374977193379731704125177528590285016474818841859956990486067573436301232301, 65537, 5539256645640498184116966196249666621079506508209770360679460869295427007578, 20151017657582479433586370393795140515103572865771721775868586710594524816458)
enc = (6641320679869421443758875467781930795132746694454926965779628505713445486895274490835545942727970688359873955019634877304270220728625521646208912044469433, 2856872654927815636828860866843721158889474116106462420201092148493803550131351543372740950198853438539317164093538508795630146854596724019329887894933972)


nbit = 256

def find_phigh(n):
    a, b, c = -2, (2^nbit - 2^(nbit//2+1) - 1), n
    delta = b^2 - 4 * a * c
    sd = floor(sqrt(delta))
    x1 = floor((- b + sd) / (2 * a))
    x2 = floor((- b - sd) / (2 * a))
    results = []
    for x in [x1, x2]:
        if (x > 2^255) and (x < 2^256):
            results.append(x)
    return results[0]

print('---')
n, e, a, b = pkey
res = find_phigh(n)
print(res)

PR.<x> = PolynomialRing(Zmod(n))
f = x + res
sol = f.small_roots(X=2^50, beta=0.42)
if (len(sol) == 0):
    print('GG')
else:
    print(gcd(ZZ(f(sol[0])), n))

然后就得到了 N 的分解。之后分别在模 $p$ 和模 $q$ 的椭圆曲线中求离散对数，再通过中国剩余定理组合起来就行了。代码如下：

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
pkey = (6660938713055850877314255610895820875305739186102790477966786501810416821294442374977193379731704125177528590285016474818841859956990486067573436301232301, 65537, 5539256645640498184116966196249666621079506508209770360679460869295427007578, 20151017657582479433586370393795140515103572865771721775868586710594524816458)
enc = (6641320679869421443758875467781930795132746694454926965779628505713445486895274490835545942727970688359873955019634877304270220728625521646208912044469433, 2856872654927815636828860866843721158889474116106462420201092148493803550131351543372740950198853438539317164093538508795630146854596724019329887894933972)

n, e, a, b = pkey

p = 93511613846272978051774379195449772332692693333173612296021789501865098047641
q = n // p
assert n % p == 0

m_list, n_list = [], []
for some_prime in [p, q]:
    EC = EllipticCurve(Zmod(some_prime), [a, b])
    P = EC(enc)
    o = P.order()

    e = 65537
    d = inverse_mod(e, o)
    m = d * P
    m_list.append(ZZ(m.xy()[0]))
    n_list.append(ZZ(some_prime))

mm = crt(m_list, n_list)

from Crypto.Util.number import *
print(long_to_bytes(mm))

最后一个字节因为 $m$ 是 flag 加上某个偏移量以是 $m^3 + a m + b$ 为模 $N$ 的二次剩余，所以被破坏，恢复成花括号即可。flag 为：

1
CCTF{a_n3W_4t7aCk_0n_RSA_a9ain!?}