CryptoCTF 2023 hard分类团队解题writeup 之一

这次 hard 分类也有 5 题，虽然思维方面肯定比 medium 要难些，但也还中规中矩。

Big

题目描述

$p$ 是一个 512 位的 $4k+3$ 型素数，$q$ 是把 $p$ 的十进制表示进行逆序之后的数，也是素数。$N=pq$。

然后 $a$ 是一个模 $N$ 的二次剩余。

首先得到 flag 的二进制为 $\{m_1, m_2, \ldots, m_l\}$，其中 $m_i \in \{0, 1\}$ 对于 $i = 1, 2, \ldots, l$。

然后生成一个随机的 $t_i$，使得 $t_i$ 在 $m_i = 0$ 时不为模 $N$ 的二次剩余，在 $m_i$ 为 1 时为模 $N$ 的二次剩余。

然后记 $c_i = (t_i - a t_i^{-1}) \bmod N$。

已知 $N, a, c_1, c_2, \ldots, c_l$，求 flag。

我的解答

首先是找到 $N=pq$ 的分解。

由于 $q$ 是把 $p$ 的十进制表示进行逆序之后的数，所以可以用估界的手法：逐步猜测 $p$ 和 $q$ 的高位值，通过模 $10^k$ 的验证，以及根据已有猜测对 $N$ 进行估界，得到范围限制，来得到分解。不过由于 $2^{511} < 10^{154} < 2^{512}$，所以 $p$ 的十进制长度有可能是 154，也有可能是 155，需要分别进行尝试。估界代码如下：

import itertools

N = 72271787633166084700895603235291055045699965307538401174867474485084272711938364003794151073975875159886045553516299177522950407802715116792937858353646755246888532333536918663888208381012106370000886903776721867958523682675624556576505534100750339626081218194389244007622749982917071344697799413034317147013

pdigits = 154

cur_sol = [(0, 0)]

for i in range((pdigits + 1) // 2):
    nxt_sol = []
    cur_modulus = (10 ** (i+1))
    for cur_p, cur_q in cur_sol:
        if (pdigits % 2 == 1) and (i == (pdigits - 1) // 2):
            for ph in itertools.product(range(10)):
                nxt_p_add = ph * 10 ** i
                nxt_q_add = ph * 10 ** i
                nxt_p = cur_p + nxt_p_add
                nxt_q = cur_q + nxt_q_add
                if (nxt_p * nxt_q == N):
                    nxt_sol.append((nxt_p, nxt_q))
        else:
            for ph, qh in itertools.product(range(10), repeat=2):
                nxt_p_add = ph * 10 ** (pdigits - 1 - i) + qh * 10 ** i
                nxt_q_add = qh * 10 ** (pdigits - 1 - i) + ph * 10 ** i
                nxt_p = cur_p + nxt_p_add
                nxt_q = cur_q + nxt_q_add
                nxt_min_p, nxt_max_p = nxt_p, nxt_p + 10 ** (pdigits - 1 - i) - 10 ** (i+1)
                nxt_min_q, nxt_max_q = nxt_q, nxt_q + 10 ** (pdigits - 1 - i) - 10 ** (i+1)
                nxt_min_N, nxt_max_N = nxt_min_p * nxt_min_q, nxt_max_p * nxt_max_q
                if ((nxt_p * nxt_q % cur_modulus == N % cur_modulus) and (nxt_min_N <= N <= nxt_max_N)):
                    nxt_sol.append((nxt_p, nxt_q))
    cur_sol = nxt_sol
    print(f'{i = }')
    print(f'{len(cur_sol) = }')

print(cur_sol)

得到 $N=pq$ 的分解。

然后方程就可以分别在在模 $p$ 和模 $q$ 下考虑，然后好巧不巧，$q$ 也是 $4k+3$ 型素数。就可以解模 $p$ 的二次同余方程。得到 $t_i$，然后根据 $t_i$ 是否为模 $N$ 的二次剩余来得到 $m_i$。然后这里非常巧的是，$a$ 是模 $p$ 的非二次剩余。因为 $a$ 是模 $N$ 的二次剩余，所以 $a$ 是模 $q$ 的非二次剩余。解得 $t_i$ 会得到两个解，但是随便用一个就行了，因为他们模 $p$ 要么均为二次剩余，要么均不为二次剩余，这是因为考虑方程：

$-x^2 + c_i x + a = 0$

由韦达定理，$x_1 x_2 = -a$，所以

$x_1^{\frac{p-1}{2}} x_2^{\frac{p-1}{2}} \equiv (-a)^{\frac{p-1}{2}} \equiv (-1)^{2k+1} a^{\frac{p-1}{2}} \equiv 1 \pmod{p}$

逐一求解，就能得到 flag。代码如下：

N = 72271787633166084700895603235291055045699965307538401174867474485084272711938364003794151073975875159886045553516299177522950407802715116792937858353646755246888532333536918663888208381012106370000886903776721867958523682675624556576505534100750339626081218194389244007622749982917071344697799413034317147013

p = 7690745050590286968025665448815927548186441771518218204702842288098845344789340509868897149374937793107491606741591691437711395848517107039674900831427939
q = 9397241380094769307017158485931177341961951476061947013977394739417988689050439874435488908822482074028128151771446818457295188445665208696820950505470967

E = 

a, c_list = E

PR.<x> = PolynomialRing(Zmod(p))

m_list = []
for ci in c_list:
    f = ci * x - x^2 + a
    xi = f.roots()
    if (kronecker(xi[0], p) == 1):
        m_list.append(1)
    else:
        m_list.append(0)

m = ''.join(str(x) for x in m_list)
m = int(m, 2)
from Crypto.Util.number import *
print(long_to_bytes(m))

得到 flag 为：

1	CCTF{_Cocks_18e_5chEm3}

Marjan

题目描述

题目基于椭圆曲线上的数字签名。

给定 256 位素数 $p$，在 $\mathbb{Z}_p$ 上定义椭圆曲线

$E: y^2 = x^3 + a x + b$

其中 $a, b$ 已知。记椭圆曲线 $E$ 的阶为 $n$。

在 $E$ 上选取一个生成元 $G$，然后生成倍点 $P = d G$，其中 $G, P$ 已知。远程有如下选项可以互动：

签名算法

生成 231 位随机数 $k_0, k_1$
计算椭圆曲线上的倍点 $R = k_0 G, S = k_1 G$
令 $r$ 和 $s$ 分别为 $R$ 和 $S$ 的横坐标，保证 $r$ 和 $s$ 均不为 0
计算消息 $m$ 的哈希值 $h = H(m)$
计算 $t = k_0^{-1} (h r - d s) \bmod n$
返回签名 $(r, s, t)$

验签算法

计算消息 $m$ 的哈希值 $h = H(m)$
计算 $u = h r t ^{-1} \bmod n$
计算 $v = s t ^{-1} \bmod n$
计算椭圆曲线上的倍点 $R = u G - v P$
验证点 $R$ 的横坐标是否为 $r$

对指定消息的加密算法（没啥卵用）

将 flag 字符串拆成两部分，并分别转换成整数 $m_1, m_2$
生成随机数 $e$，并计算倍点 $Q = e P$
记点 $Q$ 的横坐标和纵坐标分别为 $e_1$ 和 $e_2$
记 $c_1 = e_1 m_1, c2 = e_2 m_2$，返回 $c_1, c_2, e G$

我们的目标是对于一个给定的消息，给出其签名。如果我们给出的签名能通过上面的验签算法，就能得到 flag。

我的解答

要对消息进行签名的话，如果能知道倍数 $d$ 就行了。

而题目中签名所用的随机数 $k_0$ 仅有 231 位，区别于阶 $n$ 的 255 位，那么自然想到把变成 HNP 问题，高位为 0 的情形：

[HNP] 一类基于各种 DSA 的 HNP 问题求解 - ZM.J 的文章 - 知乎
https://zhuanlan.zhihu.com/p/581146119

直接参考高位为 0 的情况就行了。令

$(k', h', d', r', s') = (k, hr, d, s, t)$

即可套用格求解。

但是当时做的时候，重新推了一下公式：因为一开始他那个代码写得似乎像是每组 $k$ 的低 24 位相等且未知，所以先要把固定的低位消掉，再去做低位为 0 的情况……写着写着才发现这 TMD 不对劲。然后构造格，就也可以求出倍数 $d$ 来。然后根据他的签名步骤弄出已知消息的签名出来即可。中间可能因为 $n$ 不是素数而导致的模逆不存在报错等需要重新运行代码若干次以赌人品。

然后这题还有一个搞心态的地方：在我们输入任意消息，服务器去求消息的哈希的时候，他奶奶的，会拿输入消息加上一个回车的值丢进去算哈希，那是真的牛批！我当时做的时候，说在调试的时候怎么调都调不通，原来是服务器上他妈的要加一个回车……无力吐槽……

代码如下：

from pwn import *
from Crypto.Util.number import *
from hashlib import sha256
from sage.all import *

class Gao:
    def __init__(self) -> None:
        # self.conn = process(['sage', 'another_2.sage'])
        self.conn = remote('06.cr.yp.toc.tf', 13337)
        self.p = 114863632180633827211184132915225798242263961691870412740605315763112513729991
        self.A = -3
        self.B = 105675527217961035404524512435875047840495516468907806313576241823653895562912
        self.E = EllipticCurve(GF(self.p), [self.A, self.B])
        self.order = self.E.order()
    
    def gao_pubkey(self):
        self.conn.sendline('P')
        self.conn.recvuntil('| pkey = ')
        s = self.conn.recvline().strip().decode()[1:-1]
        x, y, z = map(int, s.split(':'))
        self.P = self.E(x, y)

        self.conn.recvuntil('| G = ')
        s = self.conn.recvline().strip().decode()[1:-1]
        x, y, z = map(int, s.split(':'))
        self.G = self.E(x, y)

    
    def gao_recv(self):
        msg = b'1'
        self.conn.sendline('S')
        self.conn.sendline(msg)
        self.conn.recvuntil('| sgn = ')
        r, s, t = eval(self.conn.recvline())
        h = bytes_to_long(sha256(msg+b'\n').digest())
        return h, r, s, t
    
    def get_abc(self, params0, paramsi):
        h0, r0, s0, t0 = params0
        hi, ri, si, ti = paramsi
        A = (s0 * inverse_mod(t0, self.order) - si * inverse_mod(ti, self.order)) % self.order
        B = 1
        C = (h0 * r0 * inverse_mod(t0, self.order) - hi * ri * inverse_mod(ti, self.order)) % self.order
        return A, B, C

    def get_alphabetagamma(self, ABC1, ABCi):
        A1, B1, C1 = ABC1
        Ai, Bi, Ci = ABCi
        alphai = Bi * inverse_mod(Ai, self.order) % self.order
        betai = -B1 * inverse_mod(A1, self.order) % self.order
        gammai = (Ci * inverse_mod(Ai, self.order) - C1 * inverse_mod(A1, self.order)) % self.order
        return alphai, betai, gammai

    def get_uv(self, abg):
        alpha, beta, gamma = abg
        u = (-beta * inverse_mod(alpha, self.order)) % self.order
        v = gamma * inverse_mod(alpha, self.order) % self.order
        return u, v

    def gao_sign(self):
        original_msg = b'I love all cryptographers!!!'
        def sign(msg, skey):
            _tail = bytes_to_long(sha256(str(skey).encode('utf-8')).digest()) % (1 << 24)
            while True:
                K = [randint(1, 2**255) // (1 << 24) + _tail for _ in '__']
                r, s = int((K[0] * self.G).xy()[0]), int((K[1] * self.G).xy()[1])
                if r * s != 0:
                    break
            h = bytes_to_long(sha256(msg).digest())
            print(f'{h = }')
            t = inverse(K[0], self.order) * (h * r - s * skey) % self.order
            assert (K[0] * t - (h * r - s * skey)) == 0
            return (r, s, t)

        def verify(msg, pkey, _sign):
            r, s, t = [int(_) % self.order for _ in _sign]
            h = bytes_to_long(sha256(msg).digest())
            u = int(h * r * inverse(t, self.order) % self.order)
            v = int(s * inverse(t, self.order) % self.order)
            _R = (u * self.G - v * pkey).xy()[0]
            print(f'{_R = }')
            print(f'{r = }')
            return _R == r
        r, s, t = sign(original_msg, self.sk_)
        print('Local verify:', verify(original_msg, self.P, (r, s, t)))
        self.conn.sendline('G')
        self.conn.sendline(f'{r},{s},{t}')

    def gao_sk(self):
        
        n = 32
        param_list = []
        for i in range(n):
            print(f'{i = }')
            h, r, s, t = self.gao_recv()
            param_list.append((h, r, s, t))
        
        ABC1 = self.get_abc(param_list[0], param_list[1])
        A1, B1, C1 = ABC1

        M = [[0 for i in range(n)] for j in range(n)]
        M[0][0] = 1
        M[1][1] = 1
        for i in range(2, n):
            ABCi = self.get_abc(param_list[0], param_list[i])
            alphai, betai, gammai = self.get_alphabetagamma(ABC1, ABCi)
            u, v = self.get_uv((alphai, betai, gammai))
            M[0][i] = v
            M[1][i] = u
            M[i][i] = self.order
        
        weights = [2**(255-24)] + [1] * (n-1)
        M = matrix(ZZ, M) * diagonal_matrix(weights)
        v = M.BKZ(block_size=12)[0]
        if (v[0] < 0):
            v = -v
        deltak1_ = v[1]
        
        self.sk_ = (C1 - B1 * deltak1_) * inverse_mod(A1, self.order) % self.order

    def gao(self):
        self.gao_pubkey()
        self.gao_sk()
        self.gao_sign()
        self.conn.interactive()


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

获取 flag 为：

1	CCTF{L4T71c3_atTAck5_a9A!nS7_ECDSA!}

然而，这道题还有一个比较鬼畜的地方：该题只有在 签名算法 检查了 $r$ 和 $s$ 的非平凡性，没有在 验签算法 中检查！！当时在做这道题的时候，都通过 HNP 求出倍数 $d$ 了，再回过头来去看它的签名和验签算法才发现的这个猫腻，然后当时就觉得这里面肯定不对劲，不过当时想着都到那一步了，就没必要再去折腾了……

所以说，我们回顾验签算法，说白了就是检查：

$R = u G - v P = (h r t ^{-1} - s t^{-1} d) G$

的横坐标是否为 $r$

先假设 $R=O$，那么可以得到一组 $(0, 0, 1)$ 满足上式，但是实际交互的时候会产生一个问题：因为无穷远点的齐次坐标形式是 $(0 : 1 : 0)$，是不能对它应用 xy() 方法的，因为这会导致除以零异常。

那我们退一步，假设 $R=G$，那么此时 $r$ 已知，令 $s = 0$ 以消除未知量 $d$ 对签名式的影响，然后令 $hrt^{-1} = 1$，即 $t = hr$ 即可。结果您猜怎么着？这样还就真行了！而且不需要写交互代码，只需要从远程得到生成元 $G$，然后手搓构造交上去就行了！那真是盖了帽儿了我的老卑鄙！构造代码如下：

from Crypto.Util.number import *
from hashlib import sha256

p = 114863632180633827211184132915225798242263961691870412740605315763112513729991
A = -3
B = 105675527217961035404524512435875047840495516468907806313576241823653895562912
E = EllipticCurve(GF(p), [A, B])

n = E.order()

original_msg = 'I love all cryptographers!!!'
msg = original_msg.encode()
h = bytes_to_long(sha256(msg).digest())

Gx = 28071498537525775917654662519370445472757062171881667597321861083632963432687
# Gy = 2246985053428078910721122714095306631783741268269376734366735762893909876497

r = Gx
s = 0
t = (h * r) % n

print(f'{r},{s},{t}')

Byeween

题目描述

需要在 $\mathbb{Q}$ 上定义的一个随机椭圆曲线上，给定 $Q$，找到所有 $P$ 使得 $2P = Q$

我的解答

应该就是把二倍点的公式往里面一套得到方程，然后求解就行了。

不过坑爹的是，输入格式没有任何的指明。经过尝试，是要输入 x,y 的形式，譬如 504047401/36,11310647101325/216，然后提交的结果如下：

提交的点不符合格式或不在给定椭圆曲线上：无效，退出！
提交的点在给定椭圆曲线上，但是两倍不是 $Q$：没有任何的回显
提交的点在给定椭圆曲线上，而且两倍是 $Q$：回显当前已提交的点的个数

求解代码如下（懒得写交互代码了）：

a = - 198166535281
b = 0

Px = 1278302329349797852690249/364089267083610000
Py = 1433610390621693549402395951257392443/219690771988642815141000000


x, y = var('x, y')

s = (3 * x^2 + a) / (2 * y)

xr = s^2 - 2 * x
yr = - y + s * (x - xr)

sol = solve([xr == Px, yr == Py], x, y, solution_dict=True)
for s in sol:
    print(f'{s[x]},{s[y]}')

得到 flag 为：

1	CCTF{H4lVin9_pO!ntS_0n_3lLipT1C_cuRve5!}