A good challenge about SSP(Subset Sum Problem,a kind of knapsack) in Ant x D^3 CTF 2022.

Chanllenge

Initial：

encrypt：

decrypt：

Analysis

发现该题是一个Knapsack [1] 问题，但不能用普通的的背包出来。

Q1 : Why can’t use regularly method of knapsack to attack it?

A1 :

如果直接在encrypt上面进行背包的话，会发现他没法背包出来。方案设计者表明了该方案针对于常规攻击是相对安全的。

为了避免弱密钥，推荐 。

为了抵抗低密度的攻击，选择 去满足 d > 1，防止了我们常规攻击背包问题的方式。

这道题目是Yasuyuki Murakami等人的设计knapsack公钥密码系统 [3] ，有一篇paper:《Equivalent key attack against a public-key cryptosystem based on subset sum problem》[2] 讲解针对该题的攻击内容的。

其中说明如果想要恢复 子集和问题(Subset Sum Problem) 的等价密钥 ，需要让keys满足以下条件

2. P 是一个素数（或者用 gcd(P,e) = 1），且满足

3. 是一个正奇数序列

可知

存在一个 比较短的向量t 满足

如果该向量是足够短的话，需要满足

因此 向量s和向量k 属于 一个 orthogonal lattice 的 子格。接着可以找到满足上述的最后两个条件的等价私钥。(ps:事实上，P并不是严格意义需要去满足他是一个素数，只需要与e互素即可)

orthogonal lattice（正交格）[4]:

给出一个格 . 格 的所有基能够张成 的相同子空间 。 作为内积的正交向量子空间。我们定义orthogonal lattice为

引理：对于任意的格 ，

Details of Attack

定义一个格

Theorem :定义格 ，那么存在一 个 的向量 ，满足 。

使用 Algorithm 1，可以计算 LLL以后的格基为 ，并且根据他们长度的升序重新排序这 n-1 个向量 。根据Theorem可知，只有一个向量是满足 。将第 n-1 个作为该满足条件的向量。

假设每个 的分布都很均匀，可以得到 ，同时 。所以当 时， 。那么 时，满足Thorem的条件。并且 n-1 个向量 是按照长度升序排序的，我们可以知道这里的 就是此处会产生的最长的 。

再用一次 Algorithm 1，就可以计算得到 $\mathscr{L}1^\perp\mathscr{L}(\bold{u_1},\bold{u_2})\bold{t{n-1}}\bold{t_0}\lang\bold{s},\bold{t_i}\rang=0 ,i\in[1,n-2]\lang\bold{a},\bold{t}\rang = e \lang\bold{s},\bold{t}\rang + P \lang\bold{k},\bold{t}\rang = 0\lang\bold{k},\bold{t_i}\rang=0{\bold{s},\bold{k}} \in \mathscr{L}_1^{\perp}$ 。

接着去枚举搜寻等价私钥

在寻找的过程中需要满足 Analysis 中的最后两条，可以以一个比较高的概率去得到一组等价私钥。

Q2 : How to enumerate the xi,yi ?

A1 :

根据官方的wp，我们可以得知

并且根据 的奇偶性，可以判断出 的奇偶性，接着随机生成一组 ，满足生成的 全是正数即可。

我们可以得知 P > e >> |a| >> zi，接着就可以得知 比较小。

那么就可以用连分数的办法得到y1,y2。

A2 :

也可以直接爆破x1,y1,x2,y2，但运气不好就可能比较难跑出来吧？

完整的算法过程在Attach中描述

Attach

Algorithm 1. Find out the orthogonal lattice [4]:

INPUT- 格 的一个 格基

OUTPUT - 格 的 格基

1. 挑选一个 .

2. 生成一个 完整格 ​
   

3. 对 LLL格基规约后张成 基

4. 输出向量 ，其中 .

Algorithm 2. Recover the equivalent private key [2]

INPUT- 公钥 .

OUTPUT - 私钥

1. 计算 的正交格，定义 。

2. 取 $\mathscr{L}1 = \mathscr{L}(t_1,t_2,\dots,t{n-2})\mathscr{L}_1^\perp = \mathscr{L}(\bold{u_1},\bold{u_2})$ .

3. 令

   枚举空间

4. 对每个集合 ，用 计算P和e

5. 用下面两条情况筛选 每个序列

   2. 是正奇数序列

6. 剩下来的每一组 都是等价私钥

Reference

[1] : Knapsack Problem : https://en.wikipedia.org/wiki/Knapsack_problem#Subset-sum_problem

[2] : Jiayang Liu, Jingguo Bi:《Equivalent key attack against a public-key cryptosystem based on subset sum problem》

[3] : Murakami, Y., Hamasho, S., Kasahara, M.: 《A public-key cryptosystem based on decision version of subset sum problem》. Information Theory and its Applications (ISITA), Honolulu, HI, USA, 2012, pp. 735–739

[4] : Nguyen, P.Q., Stern, J.: 《Merkle-Hellman revisited: a cryptanalysis of the QuVanstone cryptosystem based on group factorizations》 CRYPTO, Santa Barbara, CA, USA, 1997, pp. 198–212