DLP、Knapsack、和2022春秋杯的notKnapsack

2022春秋杯的notKnapsack，然后由一个非预期解引出的背包问题另类解法，和Cado数域筛解DLP.

notKnapsack·

题目：task.py（ https://paste.ubuntu.com/p/ZxPHWxcSsm/ ）

输出：output.txt

题目给了286组Modular Subset Product Problem（MSPP），每组有286个$r_{ki}$，记flag的每一位是$x_i$，有：

$$s_k \equiv \prod_{i=1}^{286} x_i r_{ki} \pmod q$$

其中$q = 2*331*p + 1$，$p$是一个128 bits的素数。现有$q$与每组MSPP的$r_{ki}$和$s_k$，求每个$x_i$。

先说（我认为的）正解。首先如果可以解DLP的话，Subset Product Problem是可以转化为Subset Sum Problem（即背包问题Knapsack Problem）的，即设一个生成元$g$，解DLP出所有的$\alpha_{ki}$使得$g^{\alpha_{ki}} \equiv r_{ki} \pmod q$和$g^{\beta_k} \equiv s_k \pmod q$，就会有：

$$g^{\beta_k} \equiv g^{\sum_{i=1}^{286} x_i \alpha_{ki} \pmod {\varphi(q)}} \pmod q$$

其中的$\beta_k \equiv \sum_{i=1}^{286} x_i \alpha_{ki} \pmod {\varphi(q)}$就是转化后的Knapsack Problem。但有两个问题，一是要解287个128 bits的DLP需要很多时间（用Sage的discrete_log开多线程也要好几个小时，前提还要电脑足够好），二是286维的Knapsack Problem并不好解。

所以得换个思路，观察一下会发现MSPP的组数和$r_{ki}$的个数是一样的（都是286），意味着如果DLP可以解的话就会有286组$\beta_k \equiv \sum_{i=1}^{286} x_i \alpha_{ki} \pmod {\varphi(q)}$，组成线性方程：

$$\begin{bmatrix} \alpha_{1,1} & \alpha_{1,2} & \cdots & \alpha_{1,286} \\ \alpha_{2,1} & \alpha_{2,2} & \cdots & \alpha_{2,286} \\ \vdots & \vdots & \ddots & \vdots \\ \alpha_{286,1} & \alpha_{286,2} & \cdots & \alpha_{286,286} \end{bmatrix} \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_{286} \end{pmatrix} = \begin{pmatrix} \beta_1 \\ \beta_2 \\ \vdots \\ \beta_{286} \end{pmatrix} \pmod {\varphi(q)}$$

左边矩阵是个方阵，即线性方程可解。但是DLP难解的问题依然还在，这时可以借助一下Pohlig Hellman（一个解DLP的算法）的分治思路，即我其实不需要解出$\alpha_{ki}$模$\varphi(q)$，只需要解出模$\varphi(q)$的一个较小的因子的结果就好了，而$\varphi(q) = 2*331*p$，其中的$2$和$331$都是很小的因子。

为了方便我取$2$好了（331也可以，但是没必要，因为其中有一步要枚举，只会更花时间），记$q_2 = \frac{\varphi(q)}{2}$，首先由于$g$是生成元，所以肯定有$g^{q_2} \not\equiv 1 \pmod q$且$(g^{q_2})^2 \equiv 1 \pmod q$（费马小定理），由此可推：

$$\begin{cases} (g^{q_2})^\gamma \equiv 1 \pmod q, & \text{if $\gamma$ is even} \\ (g^{q_2})^\gamma \not\equiv 1 \pmod q, & \text{if $\gamma$ is odd} \end{cases}$$

于是算一下所有的$r_{ki}^{q_2} \pmod q$即可算出所有的$\alpha_{ki}$，$\beta_k$同理。然后就是普通的解线性方程：

# sage
q = 210767327475911131359308665806489575328083
#phiqi = [2, 331, 318379648755152766403789525387446488411]

with open('./output.txt', 'r') as f:
  data = f.read()
  data = eval(data)

q2 = (q-1) // 2
g2 = pow(2, q2, q)

A = zero_matrix(GF(2), len(data))
s = vector(GF(2), [0 for _ in range(len(data))])

for i in range(len(data)):
  for j in range(len(data[i][0])):
    r2 = pow(data[i][0][j], q2, q)
    if r2 == 1:
      A[i, j] = 0
    elif r2 == g2:
      A[i, j] = 1
    else:
      print('???')
      exit(-1)
  
  s2 = pow(data[i][1], q2, q)
  if s2 == 1:
    s[i] = 0
  elif s2 == g2:
    s[i] = 1
  else:
    print('????')

x = A.solve_right(s)
print(x)

import libnum
m = int(''.join([str(xi) for xi in x]), 2)
flag = libnum.n2s(int(m))
flag = 'flag{%s}' % flag.decode()
print(flag)

Cado-nfs与DLP·

Cado-nfs是一个基于数域筛法（Number Field Sieve ，NFS）的整数分解工具，但是可以用来解较小数的DLP，而且速度意外的快（拿我的渣机作例子，解上面说的一组MSPP的287个DLP需要大概半小时），Cado解DLP的用法在这里有介绍。代码可以在官方的GitLab下载，下载完make一下就好了（文档有说，略）。

拿这一题作例子，即$q=210767327475911131359308665806489575328083$，$q-1=2*331*318379648755152766403789525387446488411$，首先需要做初始化：

./cado-nfs.py -dlp -ell=318379648755152766403789525387446488411 210767327475911131359308665806489575328083

-dlp就是用Cado解DLP而不是分解的意思，-ell后面接$q-1$最大的因子（所以首先得分解$q-1$），最后的是模数$q$。初始化完后，log的最后一条会说中间文件的位置和接下来需要用到的命令：

接下来如果我想解$37126728850884067628485342834808743961711$和$75931802900470864125815280257447903586619$（$r_{11}$和$r_{12}$）的DLP的话，就是执行：

./cado-nfs.py /tmp/cado.zoml9prk/p40.parameters_snapshot.0 target=37126728850884067628485342834808743961711,75931802900470864125815280257447903586619

很好理解，就是target后面接要解的值，多个值用逗号隔开。这里要提一下的是，Cado似乎是不能指定基底（生成元$g$）的，所以命令也不用输入基底，如果实在想要指定基底的指数的话可以通过换底公式转换（文档也有说，略）：

运行完后会给出结果和使用的基底logbase = 60836434940362636378310692831698552327736。（PS：解这两个用了14秒）

上面说的是在命令行运行的，但是如果用Cado来解notKnapsack的话，一大堆target在命令行跑不太实际，然后Cado好像没给API调用？所以粗略写了个脚本（懒得逆了，逃）：

import os

CADO_PATH = 'path/to/cado-nfs/'
CADO_CMD = './cado-nfs.py --screenlog=INFO /tmp/cado.xxxxxxxx/p40.parameters_snapshot.0 target=%s'

with open('output.txt', 'r') as f:
  data = f.read()
  data = eval(data)

os.chdir(CADO_PATH)

for i in range(len(data))[0:N]:  # solve N groups
    print('Doing - %d' % i)
    target = ''
    for ri in data[i][0]:
        target += str(ri) + ','
    s = data[i][1]
    target += str(s)

    cmd = CADO_CMD % target
    print(cmd)

    os.system(cmd)

Cado跑的每一条结果都会以下面格式储存在/tmp/cado.xxxxxxxx/pxx.logquery中（就是刚才说的中间文件的文件夹），所以可以选择运行完后直接读logquery获取结果。

with open('/tmp/cado.xxxxxxxx/pxx.logquery', 'r') as f:
  query = f.read().split('\n')[:-1]
  query = [[int(qi) for qi in q.split(' ')] for q in query]

logs = {}
for q in query:
  logs[q[0]] = q[1]

（关于NFS的理论先留个坑，有空补，逃）

关于Knapsack·

在很久以前我有提到过带模的背包问题的解法，当时说的是推出有$\|wD\| ≤ \sigma(MD)$所以可解，但其实说的并不全面，实际操作中会发现当问题规模增大时，格的维度会跟着增大，当维度大到一定程度后，使用当时说的解法就解不出正确的结果。

这其中有两个原因，一个是LLL算法其实并不能解SVP问题，它解的是apprSVP，即设格的最短向量长度是$\lambda_1$、LLL算法解出来的第一个向量是$b_1$的话，LLL只会保证$\|b_1\| \le (\delta-\frac{1}{4})^{2/(n-1)} · \lambda_1$（其中$\delta$是LLL参数，Sage中默认0.99；$n$是维度），即解出的$b_1$和最短向量的在长度上可能会存在$(\delta-\frac{1}{4})^{2/(n-1)}$的误差，当维度$n$变大时，这个误差也会（以指数）变大，即$b_1$是最短向量的可能性变小。这个问题可以通过调用BKZ然后设置一个较大的block_size缓解，但是block_size越大运行时间越长（原文是“running time increases double exponentially with block_size”，可参考这里）；而且我调Sage的BKZ维度过大的话会what(): infinite loop in babai- -

第二个原因是，当维度增大时，解背包问题用到的格的$\lambda_2\rm{-Gap}$会变小，即最短向量的长度$\lambda_1$和第二短的向量长度$\lambda_2$（甚至第i短的向量长度$\lambda_i$）相差不大，结合上面说的LLL的误差，有可能第2短、第3短、第i短的向量也会落在$(\delta-\frac{1}{4})^{2/(n-1)} · \lambda_1$中，然后成为LLL规约后的基的第一个向量（即假的最短向量）。这个问题的解决方法是，构造新的格，使得高维度时$\lambda_2\rm{-Gap}$仍然足够大。（PS：目前我也不知道Gap是怎么算出来的，所以还是靠实验测，留坑）

但是，这样子摁构造一个新的格是挺难的，所以接下来我会引入一个新的假设，即假设我知道同一个明文对应多组不同公钥的背包加密的结果，观察会发现notKnapsack的$\beta_k \equiv \sum_{i=1}^{n} x_i \alpha_{ki} \pmod {\varphi(q)}$恰好符合我的假设。

假设我用Cado解了$n_r$组DLP，且$\beta_k = \sum_{i=1}^{n} x_i \alpha_{ki} - t_k\varphi(q)$， $k=1, 2, ..., n_r$；根据$\beta_k$、$\alpha_{ki}$和$\varphi(q)$可以构造以下格$L(B)$：

$$\begin{align} B = \begin{bmatrix} 2 & & & & \alpha_{1, 1} & \alpha_{2, 1} & \cdots & \alpha_{n_r, 1} & \\ & 2 & & & \alpha_{1, 2} & \alpha_{2, 2} & \cdots & \alpha_{n_r, 2} & \\ & & \ddots & & \vdots & \vdots & \ddots & \vdots \\ & & & 2 & \alpha_{1, n} & \alpha_{2, n} & \cdots & \alpha_{n_r, n} & \\ & & & & \varphi(q) & & & & \\ & & & & & \varphi(q) & & & \\ & & & & & & \ddots & & \\ & & & & & & & \varphi(q) & \\ 1 & 1 & \cdots & 1 & \beta_1 & \beta_2 & \cdots & \beta_{n_r} & -1 \end{bmatrix}_{(n+n_r+1)*(n+n_r+1)} \\ \end{align}$$

使得

$$vB = (x_1, x_2, ..., x_n, t_1, t_2, ..., t_{n_r}, -1)·B \\ = (2x_1-1, 2x_2-1, ..., 2x_n-1, 0, 0, ..., 0, 1) = w$$

首先$\|w\|=\sqrt{n+1}$，$\|w\| ≤ \sigma(L(B))$是肯定没问题的。然后是Gap，因为我也不知道Gap怎么算，所以只有给出实验值，以下是在模数128 bits，$n=32$情况下的实验数据，给出LLL解出的第一个向量和第二个向量的长度（由于高维LLL误差较大，所以拿了比较小的$n$）:

$n_r$	$\lambda_1$	$\lambda_2$
1	5.74456265	50.0499750
2	5.74456265	675.983728
3	5.74456265	9461.71512
4	5.74456265	99343.2373
5	5.74456265	871867.823

明显$n_r$越大的话$\lambda_2\rm{-Gap}$越大（但是显然解DLP用的时间增多）。最后notKnapsack我用了$n_r=24$搞出来了（也就是等半天而已，吧）：

# sage
q = 210767327475911131359308665806489575328083
phiq = 318379648755152766403789525387446488411

with open('/tmp/cado.xul9ujy8/p40.logquery', 'r') as f:
  query = f.read().split('\n')[:-1]
  query = [[int(qi) for qi in q.split(' ')] for q in query]

logs = {}
for q in query:
  logs[q[0]] = q[1]

with open('./../../output.txt', 'r') as f:
  data = f.read()
  data = eval(data)

rs = []
ss = []
for i in range(1, 25):
  tmp = []
  for r in data[i][0]:
    tmp.append(logs[r])
  rs.append(tmp)
  ss.append(logs[data[i][1]])

# hack
C = 131
kk = 2
n = len(data[0][0])
nr = len(rs)
Mt = zero_matrix(n + nr + 1)
for i in range(n):
  Mt[i, i] = kk
  Mt[-1, i] = kk // 2
for i in range(nr):
  Mt[i+n, i+n] = phiq
  for j in range(n):
    Mt[j, i+n] = rs[i][j]
  Mt[-1, i+n] = ss[i]
Mt[-1, -1] = kk // 2

for i in range(nr):
  for j in range(len(Mt[0])):
    Mt[j, i+n] *= C
  #Mt[-1, i+n] -= kk // 2

L = Mt.LLL()

print(L[0])
xs = Mt.solve_left(L[0])
print(xs)

import libnum
x = [abs(x) for x in xs[:n]]
m = int(''.join([str(xi) for xi in x]), 2)
flag = libnum.n2s(int(m))
flag = 'flag{%s}' % flag.decode()
print(flag)