2023 N1CTF密码部分题解

其实就做了两题，题目质量还挺好的。

其他题目先留个坑，以后搞出来了再补

PS：所有题目和WP可以在官方仓库中找到

e2W@rmup·

题目：e2W@rmup.zip

算是密码签到题？

题目是一个ECDSA签名，搜一下就可以知道ECDSA的签名大概为（令$G$为生成元，曲线的群阶为$q$）：

$$Sk = d \\ Pk = d * G \\ R = k * G \\ r = R.x \\ s \equiv k^{-1} (H(m) + rd) \pmod q$$

题目除了$k$是用nonce_gen(msg_hash, d)生成，其余运算都跟标准的ECDSA一致，所以基本可以确定是nonce_gen的问题

来看看nonce_gen，如果令其输入为$m$和$d$，然后令

$$m = 2^{128} m_h + m_l \\ d = 2^{128} d_h + d_l$$

的话，其输出就是

$$k = 2^{128} m_h + d_h$$

然后把这些套进$s$的话，就是

$$\begin{aligned} s &\equiv k^{-1} (m + rd) \pmod q \\ s (2^{128} m_h + d_h) &\equiv m + r (2^{128} d_h + d_l) \pmod q \\ 2^{128} s m_h + s d_h &\equiv m + 2^{128} r d_h + r d_l \pmod q \\ 0 &\equiv (m - 2^{128} s m_h) + (2^{128} r - s) d_h + r d_l \pmod q \\ \end{aligned}$$

其中的未知数只有128 bits的$d_h$和$d_l$，而$q$是256 bits，所以可以Coppersmith以下，但实际测试$d_h$和$d_l$还是不够小

再来看看$d$生成的时候有d.bit_length() == 256，所以知道$d$的最高bit是$1$，令$d_h = 2^{127} + d_h'$，再扔进去Coppersmith，就解出来了

PS：如果还解不出来，可以考虑枚举$d_h$和$d_l$的部分比特，根据这个界应该不用枚举多少的比特

参考代码

# Sage

import hashlib
import ecdsa
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import *


g = ecdsa.NIST256p.generator
order = g.order()

E = g.curve()
p = Integer(E.p())
F = GF(p)
E = EllipticCurve(F, [E.a(), E.b()])
G = E([g.x(), g.y()])
q = Integer(order)

s = 98064531907276862129345013436610988187051831712632166876574510656675679745081
r = 9821122129422509893435671316433203251343263825232865092134497361752993786340
cipher = b'\xf3#\xff\x17\xdf\xbb\xc0\xc6v\x1bg\xc7\x8a6\xf2\xdf~\x12\xd8]\xc5\x02Ot\x99\x9f\xf7\xf3\x98\xbc\x045\x08\xfb\xce1@e\xbcg[I\xd1\xbf\xf8\xea\n-'

msg = b'welcome to n1ctf2023!'
hm = bytes_to_long(hashlib.sha256(msg).digest())
R = E.lift_x(r)
Pk = r.inverse_mod(q) * (s * R - hm * G)

load('./copper.sage')
A = (hm - 2^128 * s * (hm>>128))
B = 2^128 * r - s
C = r
R_ = Integers(q)
P.<dh, dl> = PolynomialRing(R_)
f = A + B * (2^127+dh) + C * dl   # 2^127 -> d is 256 bits (if not work, guess more bits of d...)
res = small_roots(f, [2^127, 2^128], m=5, d=3)
print(res)
dh = Integer(res[0][0])
if dh.nbits() > 127:
  dh = -dh % q
dl = Integer(res[0][1])
if dl.nbits() > 128:
  dl = -dl % q
print(dh, dl)
d = 2^128 * (2^127+dh) + dl
k = 2^128 * (hm>>128) + (2^127+dh)
assert d * G == Pk
assert k * G == R

aes = AES.new(long_to_bytes(d), mode=AES.MODE_ECB)
flag = aes.decrypt(cipher)
print(flag)

'''
[(52519103347694788037353536001474492988, 109657576978117277727118025094273115603), (115792089210356248762697446949407573529912350735155231256607165619890030234162, 115792089210356248762697446949407573529716411746844863233472397944476717552534)]
52519103347694788037353536001474492988 109657576978117277727118025094273115603
b'n1ctf{Wow!__You_bre4k_my_s1gn_chal1enge!!___}\x03\x03\x03'
'''

e20k·

题目：e20k.zip

如题，是个ZK（零知识证明，Zero-Knowledge Proof），但是前面套了个椭圆曲线做随机数种子

首先需要输入一个椭圆曲线的点作为ECPrng的state，但E的模数是N，不为素数，而我们不能在$\mathbb{Z}_N$上开平方或者解二次方程，即很难在模数$N$的椭圆曲线上找到一个点

所以需要先分解$N$，根据keygen，$N$由三个素数组成，不妨令$N = pqr$，其中$r = 2q-1$，也即$2q = r + 1$，所以$2N = p(2q)r$是一个$(r+1)$的倍数，于是就很自然（？）地想到William’s p+1攻击

根据Wiki上的介绍，只需要找到$M$，满足$M$是$(p+1)$的倍数，就可以通过计算$\text{gcd}(N, V_M - 2)$计算出$p$，其中$V_M$是Lucas sequence的第$M$个元素

由于这里的$2N$是个大整数，所以其实还需要一种快速计算Lucas sequence元素的算法，先来看看Lucas sequence，

这不就类似Fibonacci数列吗，于是怼个矩阵运算

$$\begin{bmatrix} A & -1 \\ 1 & 0 \end{bmatrix}^k \begin{bmatrix} V_1 \\ V_0 \end{bmatrix} \equiv \begin{bmatrix} V_{k+1} \\ V_{k} \end{bmatrix} \pmod N$$

把$2N$代入$k$就可以得到$V_{2N}$，然后

$$r = \text{gcd}(N, V_{2N} - 2) \\ q = \frac{r+1}{2} \\ p = \frac{N}{qr}$$

即可分解$N$

然后找$E_N$上的群元的话，只要先分别在$E_p$、$E_q$和$E_r$上找到对应的群元，然后把他们的x、y坐标分别与$(p, q, r)$做CRT，就可得到$E_N$上对应群元的x、y坐标

但是需要用怎么样的群元呢，所以先接着往下分析，可以看到prng主要被用在Sample中，如果signal被设为1的话，就会执行random.seed(prng.next())重置Sample的随机数种子

到这里的第一个想法是，我知道了种子就可以知道Sample后面使用的随机数了，但是ECPrng.next的输出中还加了个self.bias，是个未知数，所以并没有这么简单

继续分析，可以看到，Sample的signal被设为1的地方只有

self.y = vector(Rq, [Sample(0.3, N, 1) for _ in range(m)])

注意这里是m个Sample都重置了随机种子，所以如果有办法使得prng.next()每次都输出一样的值的话，则每次Sample都重置为相同的随机种子，于是可以使得向量$\mathbf{y}$的每个元素都一样

PS：当时这个地方没有发现，所以花了很多时间在分析后面的代码，但是要不构造的格太大，要不因为$q$太小导致界不够，都不能攻击成功，最后结论是，后面的ZK应该没有漏洞

再来分析prng.next()，令state为点$S$的话，prng.next()做的就是

$$S_{i} = 4 * S_{i-1} \\ \text{return } S_{i}.x + b_{ias}$$

这里的$S_0$就是前面输进去的椭圆曲线点，所以有两个方法可以构造出每次prng.next()输出相同的值：构造$S$的阶为$4$使得每次输出单位元，或阶为$3$使得每次输出$S$,试了一下，构造$4$阶的话远端的self.state.xy()[0]会报错，所以只能选择$3$阶

构造$3$阶元素还是需要用CRT，而且需要一个前提条件是$E_p$、$E_q$和$E_r$的阶都是$3$的倍数，然后分别找出里面的$3$阶群元做CRT就好了

如果要找$E_p$中的$3$阶群元，只需要先随机找一个群元$P$，然后计算$P' = \frac{|E_p|}{3} * P$即可，$E_q$和$E_r$的类似

一顿操作后，就可以在远端的ZK协议中注入一个每个元素都相同的向量$\mathbf{y}$（当然是未知的）

参考代码：

# Sage

from pwn import *
from pow import solve_challenge

def V(k, N, A=5):
  M = matrix(Zmod(N), [
    [A, -1],
    [1, 0]
  ])
  v = vector(Zmod(N), [A, 2])
  vk = M^k * v
  return Integer(vk[1])

def factorN(N):
  A = 5
  while True:
    v2n = V(2*N, N, A)
    g = gcd(v2n-2, N)
    print('[Log] %d - %d' % (A, g))
    if g.nbits() >= 256 and is_prime(g):
      r = g
      q = (r+1) // 2
      p = N // (q * r)
      if p * q * r == N:
        return p, q, r
    A = next_prime(A)

def check_order_k(fN, k):
  p, q, r = fN
  Ep = EllipticCurve(GF(p), [3, 7])
  Eq = EllipticCurve(GF(q), [3, 7])
  Er = EllipticCurve(GF(r), [3, 7])
  for Ex in (Ep, Eq, Er):
    if Ex.order() % k != 0:
      return False
  return True

def EN_random_element_k(fN, k):
  p, q, r = fN
  Ep = EllipticCurve(GF(p), [3, 7])
  Eq = EllipticCurve(GF(q), [3, 7])
  Er = EllipticCurve(GF(r), [3, 7])
  Ps = [(Ex.order() // k) * Ex.random_element() for Ex in (Ep, Eq, Er)]
  x = crt([Integer(Px.xy()[0]) for Px in Ps], [p, q, r])
  y = crt([Integer(Px.xy()[1]) for Px in Ps], [p, q, r])
  return x, y


while True:
  #context.log_level = 'debug'
  rm = remote('121.41.9.20', 6665)

  rm.recvuntil(b') solve ')
  p = rm.recvline()[:-1]
  print('p = %s' % p.decode())
  s = solve_challenge(p.decode()).encode()
  print('s = %s' % s.decode())
  rm.sendline(s)
  rm.recvuntil(b'Correct')

  rm.recvuntil(b'N = ')
  N = Integer(rm.recvline()[:-1].decode())
  print('N = %d' % N)
  fN = factorN(N)
  print('fN = %s' % str(fN))

  if not check_order_k(fN, 3):
    rm.close()
    print('\n'*4)
    continue

  x, y = EN_random_element_k(fN, 3)
  print('x, y = %d, %d' % (x, y))
  rm.sendline(str(x).encode() + b', ' + str(y).encode())

  rm.interactive()
  rm.close()

然后来分析下ZK协议

$$\begin{array}{|l|} \hline t = \mathbf{A} \mathbf{s} \\ \hline \begin{array}{lcl} \mathrm{P} & \ \ \ \ \ \ \ \ \ \ \ \ \ & \mathrm{V} \\ \begin{array}{l} \mathbf{y} \leftarrow \text{Sample}(0.3)^m \\ w = \mathbf{A} \mathbf{y} \end{array} & & \\ & \overset{w}{\longrightarrow} & \\ & & \begin{array}{l} c \leftarrow \text{Sample}(0.3) \\ \end{array}\\ & \overset{c}{\longleftarrow} & \\ \begin{array}{l} \mathbf{z} = \mathbf{s} c + \mathbf{y} \end{array} & & \\ & \overset{\mathbf{z}}{\longrightarrow} & \\ & & \begin{array}{l} \mathbf{A} \mathbf{z} \overset{?}{=} t c + w \\ \end{array}\\ \end{array} \\ \hline \end{array}$$

知道公开的$t$和协议的Transcript $(w, c, \mathbf{z})$，然后主要关注$\mathbf{z} = \mathbf{s} c + \mathbf{y}$，由于$\mathbf{z}$、$\mathbf{s}$和$\mathbf{y}$都是向量，所以展开就有

$$z_i = s_i c + y$$

注意，上面一顿操作后，$\mathbf{y}$中元素都一样，令其为$y$

令$\mathbf{z}$最后一个元素为$z_m$的话，就有

$$z_i - z_m = (s_i - s_m) c \\ s_i - s_m = (z_i - z_m) c^{-1}$$

如果再知道$s_m$就可以恢复所有的$s_i$然后恢复$\mathbf{s}$了

再来找找和$\mathbf{s}$有关的变量，就是$t = \mathbf{A} \mathbf{s}$，展开一下有

$$t = \mathbf{A} \begin{bmatrix} s_1 \\ s_2 \\ \vdots \\ s_m \end{bmatrix} = \mathbf{A} ( \begin{bmatrix} s_1 - s_m \\ \vdots \\ s_{m-1} - s_m \\ 0 \end{bmatrix} + \begin{bmatrix} s_m \\ \vdots \\ s_m \\ s_m \end{bmatrix}) = \mathbf{A} \mathbf{s_{im}} + s_m \sum_{i=1}^m A_i$$

即有

$$s_m = (t - \mathbf{A} \mathbf{s_{im}}) (\sum_{i=1}^m A_i)^{-1}$$

最后恢复$\mathbf{s}$然后求出AES密钥解密即可

参考代码：

# Sage
from Crypto.Cipher import AES
from hashlib import md5

with open('./out', 'r') as f:
  exec(f.read())
N, q, m = (256, 4197821, 15)
PRq.<a> = PolynomialRing(Zmod(q))
Rq = PRq.quotient(a^N + 1, 'x')
A = vector(Rq, [Rq(Ai) for Ai in A])
t = Rq(t)
w = Rq(w)
c = Rq(c)
z = vector(Rq, [Rq(zi) for zi in z])
ct = bytes.fromhex(ct)

zm = z[-1]
sim = []
for i in range(m-1):
  sim += [(z[i] - zm) * c^(-1)]
vsim = vector(Rq, sim + [Rq(0)])
sa = sum(list(A))
sm = (t - A * vsim) * sa^(-1)

s = [x + sm for x in sim] + [sm]
s = vector(Rq, s)

aes = AES.new(md5(str(s).encode()).digest(), mode=AES.MODE_ECB)
flag = aes.decrypt(ct)
print(flag)

# b'n1ctf{A_Weak_RSIS_pr0bl3m_H373!!}\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f'

总结·

菜