Above#

随着LLM逐渐强大 CTF的解题变的越来越快 但是过一道题留在脑子里的东西越来越少

Basic#

简单来说 格可以看成一系列元素组成的离散子集 具备线性性

在CTF中 比较常用来表述格的方式为Basis 也就是几组线性无关的向量

$$B = \{b_1, b_2, \dots, b_n\}$$

其中格中的任何元素$v_i$都可以视为格中基的线性组合

$$v = a_1b_1 + a_2b_2 + \dots + a_nb_n\;\;\;a_1, a_2, \dots, a_n \in \mathbb{Z}$$

因此可以用一个矩阵$M$ 也就是一个线性系统来描述一个格空间 我们先在$\mathbf{Z_n}$上进行讨论

不难得知有无数组基都可以表示$M$中的向量 但是满足加密系统的量往往具备代数规模上的优越性 会是一组小基

---

基于格的常见难题为 CVP与SVP

• SVP描述为在格 $L$ 中，找到一个非零向量 $v$，使得其欧几里得范数 $\|v\|$ 最小（记为 $\lambda_1(L)$）格是已知的 但是在高维格中找到系数的线性组合在多项式时间下不可解

• CVP描述为给定一个格 $L$ 和一个不在格上的目标向量 $t \in \mathbb{R}^n$，找到格中离 $t$ 最近的格中向量 $v \in L$ 使得$\|v-t\|$最小

  由此衍生出SIS和LWE问题 作为常见的题目构造

  • SIS 描述为 给定一个随机矩阵 $A \in \mathbb{Z}_q^{n \times m}$ 找到一个非零的短向量 $z \in \mathbb{Z}^m$，使得：$A \cdot z \equiv 0 \pmod q$ 并且 $\|z\| < \beta$
  • LWE描述为 从一系列方程 $b = A \cdot s + e \pmod q$中恢复秘密$s \in \mathbb{Z}_q^n$

由这两大问题可以给出很多的相关构造

---

不难看出 在这些线性系统中 所求的往往是满足条件的向量 也就是格点 为了能够分辨哪些向量是我们找到的 可能是预期需要的向量 而非空间中随机分布的结果 我们引入一个工具 高斯启发式 (Gaussian Heuristic)

与随机采样的向量相比 符合加密系统的向量往往在数量级上会非常小 在较理想情况下视为格中最小向量 而由统计学规律

在 $n$ 维格 $L$中 $\lambda_1(L)$ 的期望值约为

$\lambda_1(L) \approx \sigma(L) = \sqrt{\frac{n}{2\pi e}} \cdot \det(L)^{\frac{1}{n}}$

可见 它主要取决于格的维度和行列式

---

我们了解了如何估计出格中的最短向量 接下来分析如何评判格中某个基的好坏

1. Hadamard比率

   主要描述基向量之间有多正交

   $\mathcal{H}(B) = \frac{\det(L)}{\prod_{i=1}^n \|b_i\|}$

   $0 < \mathcal{H} \le 1$

   一般来说$\mathcal{H}$越接近1 就说明这组基越发正交 往往在赛题中直接给出数据拼凑基的比率会很小 需要通过LLL等算法优化

2. Hermite Factor

   主要描述格中的第一个短向量到底要有多短

   $\|b_1\| = \delta^n \cdot \det(L)^{\frac{1}{n}}$

   对应也有描述在使用规约算法下 能得到的预期最短向量

   $\|v\|\le \sqrt{n}\text{det}(L)^{\frac{1}n}$

   二者是具备一定类似性的

---

我们已经能够知道什么样的格基是好的了 接下来该如何得到一组好的基呢？

1. LLL

   • LLL的处理是每两个每两个向量进行的 类似冒泡的结构
   • 对于向量$b_i$和$b_j$ 定义$\mu_{i,j} = \frac{\langle b_i , b_j^* \rangle}{\langle b_j^*, b_j^* \rangle}$ 后续简写为$\mu$ 也就是参考Schmidt正交化的思路 做投影然后转换

   先对于两个向量进行约简 如果 $b_i$ 比 $b_{i-1}$ 长，就尝试 $b_i = b_i - \mu b_{i-1}$ 让 $b_i$ 变短

   分析如果约简后交换 $b_i$ 和 $b_{i-1}$ 能优化正交性 那就进行交换 依据的是Lovasz条件 也就是

   $|b_k^*|^2 \ge (\delta - \mu_{k,k-1}^2)|b_{k-1}^*|^2$ 其中$\delta \in(\frac{1}{4},1)$ 我们由此得到两个向量之间的大小关系

   直到没有向量需要处理 LLL退出

2. BKZ

   LLL针对的是2组向量间前后的关系 BKZ提供了一个更大的窗口 由block_size参数决定 在该窗口内做全量搜索

---

基本知识梳理完毕 先从一些常见的情景分析如何把一个线性系统嵌入到格中

首先对于齐次的SIS类

对于$Ax=b\mod p$ 其中$(A \in \mathbb{Z}^{m \times n})\;(x \in \mathbb{Z}^n)$

先分析特解如果想求的是

$Ax=0\mod p$ 可以直接做

$$(x,k)\begin{pmatrix}I&A^T\\O&pI\end{pmatrix}=(x,0)$$

求最短的$(x,0)$

回到这里

$Ax=b\mod p$

$$(x,k)\begin{pmatrix}I&A^T\\O&pI\end{pmatrix}=(x,b^T)$$

也就是求距离$t=(0,b^T)$的最近向量$v=(x,b^T)$

这里引入Kannan embedding的手法

设格基$D=\begin{pmatrix}I&A^T\\O&pI\end{pmatrix}$ 那么原本就有 $(x,k)D=v$

可以做新格

$$D_0=\begin{pmatrix}D&O\\t&T\end{pmatrix}=\begin{pmatrix} I & A^T & 0 \\ 0 & pI & 0 \\ 0 & b^T & T\ \end{pmatrix}$$

$T$是用来控制存放这多出来的一维的 有

$$(x,k,-1)\begin{pmatrix} I & A^T & 0 \\ 0 & pI & 0 \\ 0 & b^T & T\ \end{pmatrix}=(x,0,-T)$$

消去$b$后会是显然的最短

然后是针对LWE类的规约 给出$As+e\equiv b\mod q$ 可以发现如果令$c\equiv b-e$ 那么LWE和非齐次SIS是类似的

对于普通的LWE中 $e$往往比较小 而$s$随机 这就带来了一定的代数结构差异 我们对LWE构造的CVP为

已知目标$t=(b,0)$ 寻找$v=(b,s)$ 使得在

$$(k,s)\begin{pmatrix}qI&0\\A^T&I\end{pmatrix}=(b-e,s)$$

中有最小 那么考虑一样的嵌入 就可以做格子

$$D_0=\begin{pmatrix}D&O\\t&T\end{pmatrix}=\begin{pmatrix} qI & 0 & 0 \\ A^T & I & 0 \\ b^T & 0 & T\ \end{pmatrix}$$

在用分块矩阵的构造下 对于格就基本上能够确定构造的思路 即

把参与线性系统的量放在一角

准备单位阵来接住所欲求小量

格的构造基本上基本非常规则的对称美

注意比例的匀称 考虑范数 一般来说是绝对值的小比较好

Cipher#

接下来对于常见的基于格的加密系统 分析造格的思路 以供化归

NTRU#

---

基于多项式环的公钥加密 小素数$p$ 大素数$q$

在多项式环$R = \mathbb{Z}[x]/(x^N - 1)$上

抽样小多项式$f, g \in R$ 计算 $f$ 在模 $q$ 和模 $p$ 下的逆$f_q, f_p$

也就是$f\cdot f_q\equiv 1 \mod q$ ; $f\cdot f_p\equiv 1 \mod p$

公钥$h = f_q \cdot g \pmod q$ 同时 $h\cdot f\equiv g\mod q$

私钥$(f, f_p)$

---

加密

在$R$上抽样$m\in[-p/2, p/2]$ 抽样小多项式$r\in R$ 计算

$$c=r\cdot h + m \mod q$$

解密

先计算

$$a\equiv f\cdot c \equiv f\;(r\cdot h + m)\equiv g\cdot r +m\cdot f\mod q$$

此时可以得到

$$m\equiv a\times f_p - r\cdot f_p\cdot g\mod p$$

因为$p$是小素数 便于在生成公钥的时候 设计 $p\;|\;g$ 此时就有 $m\equiv f_p\cdot a\mod p$ 解密完毕

---

攻击面主要在公钥中 由于

$$h\cdot f\equiv g\mod q$$

也就是

$$h\cdot f+kq=g$$

$f\;g$都相对小 可以考虑对于$x \cdot p(x) \pmod{x^N - 1}$中多项式乘法的循环移位矩阵表达方式

$$\text{rot}(p) = \begin{pmatrix} p_0 & p_{N-1} & \cdots & p_1 \\ p_1 & p_0 & \cdots & p_2 \\ \vdots & \vdots & \ddots & \vdots \\ p_{N-1} & p_{N-2} & \cdots & p_0 \end{pmatrix}$$

RLWE也是类似的处理思路 下面默认先把多项式矩阵化 那么有

$$(f,k)\begin{pmatrix}I&rot(h)\\O&qI\end{pmatrix}=(f,g)$$

右边相当短 可以看成SVP问题 考虑规约出来 稍微估算一下界

$$\text{det}=q^N$$

如果$f\;g$系数都在$\delta$内 可以估计最小向量的范数 $\|v\|\approx d\cdot \sqrt{2N}$

计算一下Hermite的定理 可以有

$$d\cdot \sqrt{2N}\lt \sqrt{N}\cdot q^{\frac{1}{2}}$$

在$N$比较大的时候 直接做SVP格效果会变差

HNP#

---

基本构造如下

对于线性系统

$$A_ix_0\equiv B_i+b_i\mod q$$

已知$A_i$ $B_i$是泄露的高位 $b_i$是未知比特 要求恢复密钥$x_0$

设有$n$组数据 每次泄露的比特位数为$m$ 密钥$x$比特数为$X$ 先给出一个直观的结论 当泄露的数据大于未知的数据 可以考虑做格 在线性系统中规约求解 也就是当

$$(n+1)\times m>X$$

可解

---

把模式变为整数方程 有

$$A_ix_0= B_i+b_i-k_iq$$

已知的是$A_i\;B_i$ 未知的是$b_i\;k_i\;x_0$

这里的核心思路在于$x_0$未必是小的 如何避免常量的影响呢？ 在一次系统下 优先考虑代数消元