格基规约（LLL）：后量子密码的战场

1982 年，Arjen Lenstra、Hendrik Lenstra 和 Laszlo Lovasz 三人发表了一篇论文，提出了 一种在多项式时间内对格基进行规约的算法。这个算法后来以三人姓氏首字母命名，称为 LLL 算法。在发表的当年，它就被用来在多项式时间内分解有理系数多项式，解决了一个 长期悬而未决的问题。此后四十多年里，LLL 算法成为了计算数论和密码分析中最核心的 工具之一，从破解背包密码系统到攻击 RSA 的弱参数实现，再到如今后量子密码方案的 安全性分析，它始终处于第一线。

本文将从格的基本定义出发，逐步推导 LLL 算法的完整过程，给出一个可编译运行的 C 语言实现，并讨论它在现代密码学中的攻防地位。

一、格的定义与基本性质

什么是格

设 \(b_1, b_2, \ldots, b_d \in \mathbb{R}^n\) 是 \(d\) 个线性无关的向量。由这些向量 生成的格（lattice）定义为它们的所有整系数线性组合：

\[ \mathcal{L}(b_1, \ldots, b_d) = \left\{ \sum_{i=1}^{d} z_i b_i \;\middle|\; z_i \in \mathbb{Z} \right\} \]

这里 \(d\) 称为格的秩（rank），\(n\) 称为格的嵌入维数（embedding dimension）。 当 \(d = n\) 时，称格为满秩格（full-rank lattice）。矩阵 \(B = [b_1, \ldots, b_d]\) 称为格的一组基（basis）。

格与向量空间的本质区别在于：格中只包含离散的点，而向量空间是连续的。如果把二维格 画出来，它看起来就像一个无穷延伸的平行四边形网格。

基的不唯一性

同一个格可以有无穷多组基。两组基 \(B\) 和 \(B'\) 生成同一个格，当且仅当存在一个 整数幺模矩阵 \(U\)（即 \(\det(U) = \pm 1\) 的整数矩阵），使得 \(B' = BU\)。

这一点对密码学至关重要：一个格的「好基」（短且近似正交）可以让许多问题变得容易， 而「坏基」（长且近似平行）则让同样的问题在计算上难以处理。格基规约的目标，就是 把坏基变成好基。

格的行列式

格的行列式（也称为格的体积）定义为：

\[ \det(\mathcal{L}) = \sqrt{\det(B^T B)} \]

当格是满秩格时，\(\det(\mathcal{L}) = |\det(B)|\)。格的行列式不依赖于基的选择， 它是格本身的不变量。直观上，它等于格的基本域（fundamental domain）的体积。

代码：格的基本操作

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define MAX_DIM 64

typedef struct {
    int d;                          /* 格的秩（行数） */
    int n;                          /* 嵌入维数（列数） */
    double B[MAX_DIM][MAX_DIM];     /* 基向量，行优先 */
} Lattice;

/* 内积 */
static double dot(const double *u, const double *v, int n)
{
    double s = 0.0;
    for (int i = 0; i < n; i++)
        s += u[i] * v[i];
    return s;
}

/* 向量范数 */
static double norm2(const double *v, int n)
{
    return dot(v, v, n);
}

/* 打印基向量 */
static void lattice_print(const Lattice *L)
{
    for (int i = 0; i < L->d; i++) {
        printf("  b[%d] = (", i);
        for (int j = 0; j < L->n; j++) {
            if (j > 0) printf(", ");
            printf("%.2f", L->B[i][j]);
        }
        printf(")  |b| = %.4f\n", sqrt(norm2(L->B[i], L->n)));
    }
}

二、最短向量问题与最近向量问题

格上有两个核心计算问题，它们的困难性是现代格密码安全的基石。

最短向量问题（SVP）

给定格 \(\mathcal{L}\) 的一组基 \(B\)，找到格中最短的非零向量：

\[ \text{SVP}: \quad \text{find } v \in \mathcal{L} \setminus \{0\} \text{ such that } \|v\| = \lambda_1(\mathcal{L}) \]

其中 \(\lambda_1(\mathcal{L})\) 是格的第一连续最小值（first successive minimum）， 即格中非零向量的最小范数。

精确求解 SVP 在一般情况下是 NP-hard 的（在随机化规约下）。因此密码学中更关注它 的近似版本：

\(\gamma\)-SVP：找到 \(v \in \mathcal{L} \setminus \{0\}\)，使得 \(\|v\| \leq \gamma \cdot \lambda_1(\mathcal{L})\)。

LLL 算法解决的就是 \(\gamma = 2^{(d-1)/2}\) 的近似 SVP，其中 \(d\) 是格的维数。

最近向量问题（CVP）

给定格 \(\mathcal{L}\) 的一组基 \(B\) 和目标向量 \(t \in \mathbb{R}^n\)，找到格中离 \(t\) 最近的向量：

\[ \text{CVP}: \quad \text{find } v \in \mathcal{L} \text{ such that } \|v - t\| = \min_{w \in \mathcal{L}} \|w - t\| \]

CVP 至少和 SVP 一样难。在实际的密码分析中，很多攻击本质上都可以归结为 CVP 的 某种变体。Babai 在 1986 年证明，利用 LLL 规约后的基，可以通过最近平面算法 （nearest plane algorithm）在多项式时间内近似求解 CVP。

Minkowski 定理

Minkowski 定理给出了 \(\lambda_1\) 的上界：

\[ \lambda_1(\mathcal{L}) \leq \sqrt{d} \cdot \det(\mathcal{L})^{1/d} \]

更精确的界由 Hermite 常数 \(\gamma_d\) 给出：\(\lambda_1(\mathcal{L}) \leq \sqrt{\gamma_d} \cdot \det(\mathcal{L})^{1/d}\)。对于大维数 \(d\)，\(\gamma_d \approx d / (2\pi e)\)。

这个定理告诉我们，在高维格中，最短向量大约长 \(\Theta(\sqrt{d})\)，而随机格点的 平均长度大约是 \(\Theta(\sqrt{d / (2\pi e)}) \cdot \det(\mathcal{L})^{1/d}\)。

SVP 与 CVP 求解算法的谱系

三、Gram-Schmidt 正交化

Gram-Schmidt 正交化是 LLL 算法的计算核心。给定线性无关的向量组 \(b_1, \ldots, b_d\)， Gram-Schmidt 过程产生一组正交向量 \(b_1^*, \ldots, b_d^*\) 和系数 \(\mu_{i,j}\)：

\[ b_i^* = b_i - \sum_{j=1}^{i-1} \mu_{i,j} b_j^*, \quad \mu_{i,j} = \frac{\langle b_i, b_j^* \rangle}{\langle b_j^*, b_j^* \rangle} \]

需要注意一个重要区别：在 LLL 算法中，Gram-Schmidt 正交化只是分析工具，我们 并不把基替换成正交化后的结果（那样会失去格的整数结构）。\(b_i^*\) 和 \(\mu_{i,j}\) 用于指导如何对原始基进行整数变换。

Gram-Schmidt 系数的几何意义

\(\mu_{i,j}\) 表示 \(b_i\) 在 \(b_j^*\) 方向上的投影长度与 \(b_j^*\) 长度的比值。当 \(|\mu_{i,j}| \leq 1/2\) 时，我们说 \(b_i\) 相对于 \(b_j\) 是尺寸规约的 （size-reduced）。直观上，这意味着 \(b_i\) 没有在 \(b_j^*\) 方向上「伸出太多」。

正交性缺陷

Gram-Schmidt 正交化还引出了一个衡量基质量的指标–正交性缺陷 （orthogonality defect）：

\[ \delta(B) = \frac{\prod_{i=1}^{d} \|b_i\|}{\det(\mathcal{L})} \]

由 Hadamard 不等式，\(\delta(B) \geq 1\)，等号成立当且仅当基是正交的。\(\delta(B)\) 越接近 1，基越「好」。LLL 规约保证 \(\delta(B) \leq 2^{d(d-1)/4}\)。

代码：Gram-Schmidt 过程

typedef struct {
    double Bs[MAX_DIM][MAX_DIM];     /* Gram-Schmidt 正交向量 */
    double mu[MAX_DIM][MAX_DIM];     /* Gram-Schmidt 系数 */
    double Bs_norm2[MAX_DIM];        /* |b*_i|^2 */
} GSO;

/* 计算 Gram-Schmidt 正交化 */
static void gram_schmidt(const Lattice *L, GSO *gso)
{
    int d = L->d, n = L->n;
    memset(gso, 0, sizeof(GSO));

    for (int i = 0; i < d; i++) {
        /* 拷贝 b_i 到 b*_i */
        memcpy(gso->Bs[i], L->B[i], sizeof(double) * n);

        /* 减去投影 */
        for (int j = 0; j < i; j++) {
            gso->mu[i][j] = dot(L->B[i], gso->Bs[j], n) / gso->Bs_norm2[j];
            for (int k = 0; k < n; k++)
                gso->Bs[i][k] -= gso->mu[i][j] * gso->Bs[j][k];
        }

        gso->Bs_norm2[i] = norm2(gso->Bs[i], n);
    }
}

四、LLL 算法：完整推导

两个条件

LLL 规约基需要同时满足两个条件：

条件一：尺寸规约条件（Size Reduction Condition）

\[ |\mu_{i,j}| \leq \frac{1}{2}, \quad \text{for all } 1 \leq j < i \leq d \]

这个条件确保每个基向量在之前所有 Gram-Schmidt 向量方向上的投影不超过一半。违反 此条件时，我们用整数倍的 \(b_j\) 来修正 \(b_i\)：令 \(b_i \leftarrow b_i - \lfloor \mu_{i,j} \rceil b_j\)， 其中 \(\lfloor \cdot \rceil\) 表示四舍五入到最近整数。

条件二：Lovasz 条件

\[ \|b_k^*\|^2 \geq \left(\delta - \mu_{k,k-1}^2\right) \|b_{k-1}^*\|^2, \quad \text{for all } 2 \leq k \leq d \]

其中 \(\delta \in (1/4, 1]\) 是算法参数，原始论文取 \(\delta = 3/4\)。这个条件防止 相邻 Gram-Schmidt 向量长度下降太快。违反此条件时，交换 \(b_k\) 和 \(b_{k-1}\)。

为什么 Lovasz 条件有效

Lovasz 条件的核心洞察是：如果 \(\|b_k^*\|^2\) 比 \(\|b_{k-1}^*\|^2\) 小太多，那么 交换 \(b_k\) 和 \(b_{k-1}\) 之后，新的 \(b_{k-1}^*\) 会变短，但它与新的 \(b_k^*\) 的 乘积 \(\|b_{k-1}^*\| \cdot \|b_k^*\|\) 会严格减小。具体来说，可以证明每次交换 后，\(\prod_{i=1}^{d} \|b_i^*\|^{2(d-i)}\) 至少乘以一个因子 \(\delta - 1/4 < 1\)。

由于这个乘积的初始值有上界（由输入基的范数决定），而它严格单调递减且有下界 （由格的行列式决定），所以算法必然终止。

终止性与复杂度

设 \(B\) 为输入基中向量的最大欧氏范数。LLL 算法的迭代次数上界为：

\[ O\left(\frac{d^2 \log B}{\log(1/(\delta - 1/4))}\right) \]

取 \(\delta = 3/4\) 时，总的算术运算次数为 \(O(d^5 n \log^3 B)\)。在实际应用中， 算法的表现通常远好于这个最坏情况估计。

输出质量保证

LLL 规约基具有以下性质：

1. \(\|b_1\| \leq 2^{(d-1)/2} \lambda_1(\mathcal{L})\)：第一个基向量是最短向量的 \(2^{(d-1)/2}\) 近似。

2. \(\|b_1\| \leq 2^{(d-1)/4} \det(\mathcal{L})^{1/d}\)：第一个基向量长度接近 Minkowski 界。

3. \(\prod_{i=1}^{d} \|b_i\| \leq 2^{d(d-1)/4} \det(\mathcal{L})\)：Hadamard 比 有界。

五、完整 C 语言实现

下面是 LLL 算法的完整 C 语言实现，包括尺寸规约、Lovasz 条件检查、基向量交换、 以及 Gram-Schmidt 正交化的增量更新。

/*
 * lll.c -- LLL 格基规约算法的完整实现
 *
 * 编译: gcc -O2 -o lll lll.c -lm
 * 运行: ./lll
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <float.h>

#define MAX_DIM 64

/* ======================== 基本类型 ======================== */

typedef struct {
    int d;
    int n;
    double B[MAX_DIM][MAX_DIM];
} LatticeBase;

/* ======================== 向量运算 ======================== */

static inline double vec_dot(const double *u, const double *v, int n)
{
    double s = 0.0;
    for (int i = 0; i < n; i++)
        s += u[i] * v[i];
    return s;
}

static inline double vec_norm2(const double *v, int n)
{
    return vec_dot(v, v, n);
}

static inline void vec_swap(double *u, double *v, int n)
{
    for (int i = 0; i < n; i++) {
        double t = u[i];
        u[i] = v[i];
        v[i] = t;
    }
}

/* ======================== Gram-Schmidt ======================== */

static void compute_gso(const LatticeBase *L,
                        double mu[MAX_DIM][MAX_DIM],
                        double Bs[MAX_DIM][MAX_DIM],
                        double Bn2[MAX_DIM])
{
    int d = L->d, n = L->n;

    for (int i = 0; i < d; i++) {
        memcpy(Bs[i], L->B[i], sizeof(double) * n);

        for (int j = 0; j < i; j++) {
            if (Bn2[j] < DBL_EPSILON) {
                mu[i][j] = 0.0;
                continue;
            }
            mu[i][j] = vec_dot(L->B[i], Bs[j], n) / Bn2[j];
            for (int k = 0; k < n; k++)
                Bs[i][k] -= mu[i][j] * Bs[j][k];
        }

        Bn2[i] = vec_norm2(Bs[i], n);
    }
}

/* ======================== 尺寸规约 ======================== */

static void size_reduce(LatticeBase *L, int k, int l,
                        double mu[MAX_DIM][MAX_DIM],
                        double Bs[MAX_DIM][MAX_DIM],
                        double Bn2[MAX_DIM])
{
    if (fabs(mu[k][l]) <= 0.5)
        return;

    int r = (int)round(mu[k][l]);
    int n = L->n;

    for (int j = 0; j < n; j++)
        L->B[k][j] -= r * L->B[l][j];

    /* 更新 mu 值 */
    for (int j = 0; j <= l; j++)
        mu[k][j] -= r * mu[l][j];
    /* mu[l][l] 视为 1，所以最后处理 */
    mu[k][l] -= r * 1.0;
    /* 上面的循环已经处理了 j < l 的情况，mu[k][l] 需要单独处理 */
    /* 实际上 mu[l][l] 不存在于数组中（对角线视为 1），重新计算更安全 */
}

/* ======================== LLL 核心 ======================== */

/*
 * 执行 LLL 规约。参数 delta 通常取 0.75。
 * 返回交换次数。
 */
static int lll_reduce(LatticeBase *L, double delta)
{
    int d = L->d, n = L->n;
    double mu[MAX_DIM][MAX_DIM] = {{0}};
    double Bs[MAX_DIM][MAX_DIM] = {{0}};
    double Bn2[MAX_DIM] = {0};
    int swaps = 0;

    /* 初始 Gram-Schmidt */
    compute_gso(L, mu, Bs, Bn2);

    int k = 1;
    while (k < d) {
        /* 对 b_k 做尺寸规约 */
        for (int l = k - 1; l >= 0; l--) {
            if (fabs(mu[k][l]) > 0.5) {
                int r = (int)round(mu[k][l]);
                for (int j = 0; j < n; j++)
                    L->B[k][j] -= r * L->B[l][j];
                /* 重新计算受影响的 mu 值 */
                compute_gso(L, mu, Bs, Bn2);
            }
        }

        /* 检查 Lovasz 条件 */
        double lhs = Bn2[k];
        double rhs = (delta - mu[k][k-1] * mu[k][k-1]) * Bn2[k-1];

        if (lhs >= rhs) {
            k++;
        } else {
            /* 交换 b_k 和 b_{k-1} */
            vec_swap(L->B[k], L->B[k-1], n);
            swaps++;

            /* 重新计算 Gram-Schmidt（简化实现） */
            compute_gso(L, mu, Bs, Bn2);

            k = (k > 1) ? k - 1 : 1;
        }
    }

    return swaps;
}

/* ======================== 优化版 LLL ======================== */

/*
 * 带增量 GSO 更新的 LLL 实现。
 * 交换 b_k 和 b_{k-1} 后，只需要更新第 k-1 和 k 行的 GSO 数据，
 * 而不是重新计算全部。这将实际性能从 O(d^6) 降到 O(d^5)。
 */
static int lll_reduce_fast(LatticeBase *L, double delta)
{
    int d = L->d, n = L->n;
    double mu[MAX_DIM][MAX_DIM] = {{0}};
    double Bs[MAX_DIM][MAX_DIM] = {{0}};
    double Bn2[MAX_DIM] = {0};
    int swaps = 0;

    compute_gso(L, mu, Bs, Bn2);

    int k = 1;
    while (k < d) {
        /* 尺寸规约 b_k */
        for (int l = k - 1; l >= 0; l--) {
            if (fabs(mu[k][l]) > 0.5) {
                int r = (int)round(mu[k][l]);
                for (int j = 0; j < n; j++)
                    L->B[k][j] -= (double)r * L->B[l][j];

                /* 增量更新 mu[k][*] */
                for (int j = 0; j < l; j++)
                    mu[k][j] -= (double)r * mu[l][j];
                mu[k][l] -= (double)r;
            }
        }

        /* Lovasz 条件 */
        double lhs = Bn2[k];
        double rhs = (delta - mu[k][k-1] * mu[k][k-1]) * Bn2[k-1];

        if (lhs >= rhs) {
            k++;
        } else {
            /* 交换 b_k 和 b_{k-1}，然后做增量 GSO 更新 */
            vec_swap(L->B[k], L->B[k-1], n);
            swaps++;

            /* 保存旧值 */
            double mu_kk1 = mu[k][k-1];
            double Bk_old = Bn2[k];
            double Bkm1_old = Bn2[k-1];

            /* 更新 Bn2 */
            double new_Bkm1 = Bk_old + mu_kk1 * mu_kk1 * Bkm1_old;
            if (new_Bkm1 < DBL_EPSILON) {
                compute_gso(L, mu, Bs, Bn2);
                k = (k > 1) ? k - 1 : 1;
                continue;
            }

            double eta = Bkm1_old / new_Bkm1;
            double zeta = mu_kk1 * eta;

            Bn2[k-1] = new_Bkm1;
            Bn2[k] = Bk_old * eta;

            /* 更新 Gram-Schmidt 向量 */
            for (int j = 0; j < n; j++) {
                double bsk = Bs[k][j];
                double bskm1 = Bs[k-1][j];
                Bs[k-1][j] = bsk + mu_kk1 * bskm1;
                Bs[k][j] = -zeta * bsk + (Bk_old / new_Bkm1) * bskm1;
            }

            /* 更新 mu 矩阵 */
            mu[k][k-1] = zeta;

            for (int j = 0; j < k - 1; j++) {
                double tmp = mu[k-1][j];
                mu[k-1][j] = mu[k][j];
                mu[k][j] = tmp;
            }

            for (int i = k + 1; i < d; i++) {
                double mik = mu[i][k];
                double mikm1 = mu[i][k-1];
                mu[i][k-1] = mik + mu_kk1 * mikm1;
                /* 注意这里用的是更新后的 mu[k][k-1] = zeta */
                mu[i][k] = mikm1 * (Bk_old / new_Bkm1) - mik * zeta;
            }

            k = (k > 1) ? k - 1 : 1;
        }
    }

    return swaps;
}

/* ======================== 辅助函数 ======================== */

static void print_basis(const LatticeBase *L, const char *label)
{
    printf("%s:\n", label);
    for (int i = 0; i < L->d; i++) {
        printf("  b[%d] = (", i);
        for (int j = 0; j < L->n; j++) {
            if (j > 0) printf(", ");
            printf("%8.2f", L->B[i][j]);
        }
        printf(")  |b| = %10.4f\n", sqrt(vec_norm2(L->B[i], L->n)));
    }
}

static double orthogonality_defect(const LatticeBase *L)
{
    double prod_norms = 1.0;
    for (int i = 0; i < L->d; i++)
        prod_norms *= sqrt(vec_norm2(L->B[i], L->n));

    /* 计算 det(B^T B)^{1/2}（这里假设 d == n 简化处理） */
    /* 用 Gram-Schmidt 的 |b*_i| 的乘积 */
    double mu[MAX_DIM][MAX_DIM] = {{0}};
    double Bs[MAX_DIM][MAX_DIM] = {{0}};
    double Bn2[MAX_DIM] = {0};
    compute_gso(L, mu, Bs, Bn2);

    double prod_gs = 1.0;
    for (int i = 0; i < L->d; i++)
        prod_gs *= sqrt(Bn2[i]);

    if (prod_gs < DBL_EPSILON)
        return 1e18;

    return prod_norms / prod_gs;
}

/* ======================== 测试用例 ======================== */

static void test_basic(void)
{
    printf("=== 基本测试 ===\n");

    LatticeBase L;
    L.d = 3;
    L.n = 3;

    /* 一个「坏基」 */
    double init[3][3] = {
        {  1,   1,   1 },
        { -1,   0,   2 },
        {  3,   5,   6 }
    };
    memcpy(L.B, init, sizeof(init));

    print_basis(&L, "规约前");
    printf("  正交性缺陷: %.6f\n\n", orthogonality_defect(&L));

    int swaps = lll_reduce_fast(&L, 0.75);

    print_basis(&L, "规约后");
    printf("  正交性缺陷: %.6f\n", orthogonality_defect(&L));
    printf("  交换次数: %d\n\n", swaps);
}

static void test_knapsack_style(void)
{
    printf("=== 背包式格（密码分析相关） ===\n");

    LatticeBase L;
    L.d = 5;
    L.n = 5;

    /* 模拟一个背包密码的格 */
    double init[5][5] = {
        { 1, 0, 0, 0, 47 },
        { 0, 1, 0, 0, 83 },
        { 0, 0, 1, 0, 29 },
        { 0, 0, 0, 1, 61 },
        { 0, 0, 0, 0, 137 }
    };
    memcpy(L.B, init, sizeof(init));

    print_basis(&L, "规约前");

    int swaps = lll_reduce_fast(&L, 0.99);

    print_basis(&L, "规约后");
    printf("  交换次数: %d\n\n", swaps);
}

static void benchmark(void)
{
    printf("=== 性能基准测试 ===\n");
    printf("%-8s %-12s %-12s %-10s %-10s\n",
           "维数", "规约前|b1|", "规约后|b1|", "交换次数", "耗时(ms)");

    for (int dim = 5; dim <= 40; dim += 5) {
        LatticeBase L;
        L.d = dim;
        L.n = dim;

        /* 生成随机格基 */
        srand(42 + dim);
        for (int i = 0; i < dim; i++)
            for (int j = 0; j < dim; j++)
                L.B[i][j] = (rand() % 2001) - 1000;

        double before = sqrt(vec_norm2(L.B[0], dim));

        clock_t start = clock();
        int swaps = lll_reduce_fast(&L, 0.99);
        clock_t end = clock();

        double after = sqrt(vec_norm2(L.B[0], dim));
        double ms = 1000.0 * (end - start) / CLOCKS_PER_SEC;

        printf("%-8d %-12.2f %-12.2f %-10d %-10.2f\n",
               dim, before, after, swaps, ms);
    }
    printf("\n");
}

int main(void)
{
    test_basic();
    test_knapsack_style();
    benchmark();
    return 0;
}

代码结构说明：

• compute_gso：完整的 Gram-Schmidt 计算，\(O(d^2 n)\) 时间。
• lll_reduce：简化版 LLL，每次交换后重新计算全部 GSO。逻辑清晰但较慢。
• lll_reduce_fast：优化版 LLL，交换后做增量 GSO 更新，性能提升一个数量级。
• orthogonality_defect：计算正交性缺陷，用于评估规约质量。

六、LLL 的密码分析应用：背包密码

1978 年，Merkle 和 Hellman 提出了基于子集和问题的背包公钥密码系统。他们的方案 使用超递增序列作为私钥，通过模乘变换得到看起来随机的公钥序列。加密时，消息比特 选择公钥序列的子集求和。

攻击原理

Shamir 在 1984 年首先破解了这个系统。后来 Lagarias 和 Odlyzko 用 LLL 给出了 更优雅的攻击。核心思想是构造如下格：

设公钥为 \((a_1, \ldots, a_n)\)，密文为 \(s = \sum_{i} x_i a_i\)，其中 \(x_i \in \{0, 1\}\)。 构造 \((n+1) \times (n+1)\) 的格基矩阵：

\[ B = \begin{pmatrix} 1 & 0 & \cdots & 0 & a_1 \\ 0 & 1 & \cdots & 0 & a_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & a_n \\ 0 & 0 & \cdots & 0 & -s \end{pmatrix} \]

明文向量 \((x_1, x_2, \ldots, x_n, 0)\) 是这个格中的一个向量（因为 \(\sum x_i a_i - s \cdot 0 = \sum x_i a_i \neq 0\)，但实际上最后一列的值为 \(\sum x_i a_i - 1 \cdot s = 0\)，需要在最后加一行），而且它很短（分量只有 0 和 1）。 对这个格做 LLL 规约，就有很大概率在输出的前几个向量中找到明文。

密度与成功率

攻击的成功率取决于背包的密度 \(d = n / \log_2(\max a_i)\)。当 \(d < 0.9408\) 时（低密度），LLL 攻击几乎总是成功的。这个临界密度来自 Coster、Joux、LaMacchia、 Odlyzko、Schnorr 和 Stern 在 1992 年的分析。

代码：背包攻击的格构造

/*
 * 构造用于攻击子集和问题的格基。
 * 输入：公钥 a[0..n-1]，密文 s
 * 输出：(n+1) x (n+1) 格基
 */
static void build_knapsack_lattice(LatticeBase *L,
                                   const double *a, int n, double s)
{
    L->d = n + 1;
    L->n = n + 1;
    memset(L->B, 0, sizeof(L->B));

    for (int i = 0; i < n; i++) {
        L->B[i][i] = 1.0;          /* 单位矩阵部分 */
        L->B[i][n] = a[i];         /* 公钥值 */
    }
    L->B[n][n] = -s;               /* 密文的负值 */
}

/*
 * 在 LLL 规约后的基中搜索明文。
 * 明文向量的特征：前 n 个分量都是 0 或 1，最后一个分量为 0。
 */
static int find_plaintext(const LatticeBase *L, int n, int *plaintext)
{
    for (int i = 0; i < L->d; i++) {
        int valid = 1;

        /* 检查最后一个分量是否为 0 */
        if (fabs(L->B[i][n]) > 0.5) {
            valid = 0;
            continue;
        }

        /* 检查前 n 个分量是否为 0 或 1（或 0 或 -1） */
        int all_01 = 1, all_0m1 = 1;
        for (int j = 0; j < n; j++) {
            double v = L->B[i][j];
            if (fabs(v) > 0.5 && fabs(v - 1.0) > 0.5)
                all_01 = 0;
            if (fabs(v) > 0.5 && fabs(v + 1.0) > 0.5)
                all_0m1 = 0;
        }

        if (all_01) {
            for (int j = 0; j < n; j++)
                plaintext[j] = (int)round(L->B[i][j]);
            return 1;
        }
        if (all_0m1) {
            for (int j = 0; j < n; j++)
                plaintext[j] = -(int)round(L->B[i][j]);
            return 1;
        }
    }
    return 0;
}

七、Coppersmith 方法：多项式小根

1996 年，Don Coppersmith 基于 LLL 算法提出了一种在模 \(N\) 意义下求多项式小根的 方法。这个方法后来成为 RSA 密码分析中最强大的工具之一。

基本定理

设 \(f(x)\) 是次数为 \(d\) 的首一整系数多项式，\(N\) 是正整数。如果存在 \(x_0\) 满足 \(f(x_0) \equiv 0 \pmod{N}\) 且 \(|x_0| < N^{1/d}\)，那么可以在关于 \(\log N\) 和 \(d\) 的多项式时间内找到 \(x_0\)。

方法概述

Coppersmith 方法的关键步骤是：

1. 构造多个多项式 \(g_1(x), g_2(x), \ldots\)，它们都以 \(x_0\) 为模 \(N^m\) 的根 （\(m\) 是一个参数）。通常取 \(g_{i,j}(x) = x^j N^{m-i} f(x)^i\)。

2. 将这些多项式的系数向量作为格基（每个多项式对应一行，每列对应 \(x\) 的一个幂次， 乘以适当的 \(X^j\) 来平衡各列的大小）。

3. 对这个格做 LLL 规约。

4. 规约后的短向量对应一个具有小系数的多项式 \(h(x)\)，它也以 \(x_0\) 为根。关键 一步：如果 \(h(x)\) 的系数足够小，那么 \(h(x_0) = 0\) 不仅在模 \(N^m\) 意义下 成立，在整数上也成立。

5. 用标准方法（如求根公式、Newton 法）求解 \(h(x) = 0\)。

对 RSA 小公钥指数的攻击

如果 RSA 使用小的公钥指数 \(e\)（例如 \(e = 3\)），并且消息有已知的高位（例如填充 格式已知），那么 Coppersmith 方法可以恢复消息。

具体来说，设 \(c = m^e \bmod N\)，已知 \(m = m_0 + x_0\)，其中 \(m_0\) 是已知部分， \(x_0\) 是未知的小值。则 \((m_0 + x_0)^e - c \equiv 0 \pmod{N}\)。当 \(|x_0| < N^{1/e}\) 时，Coppersmith 方法可以高效地找到 \(x_0\)。

对于 \(e = 3\)，这意味着如果消息的约 \(1/3\) 比特已知，就可以恢复全部消息。

Hastad 广播攻击

如果同一消息 \(m\) 用 \(e\) 个不同的 RSA 公钥 \((N_1, e), (N_2, e), \ldots, (N_e, e)\) 加密（其中 \(e\) 是小公钥指数），得到密文 \(c_i = m^e \bmod N_i\)，那么用中国剩余 定理可以计算 \(m^e \bmod (N_1 N_2 \cdots N_e)\)。由于 \(m < \min(N_i)\)，所以 \(m^e < N_1 N_2 \cdots N_e\)，直接开 \(e\) 次方即可得到 \(m\)。

结合 Coppersmith 方法和线性填充关系，Hastad 攻击可以进一步放松条件。

攻击格构造的 Python 伪代码

为了说明 Coppersmith 方法中格的构造，给出以下伪代码：

def coppersmith_lattice(f, N, m, t, X):
    """
    f: 目标多项式（首一，次数 d）
    N: 模数
    m: 移位参数（控制格的维数）
    t: 额外移位
    X: 根的上界
    """
    d = f.degree()
    # 构造移位多项式
    polys = []
    for i in range(m):
        for j in range(d):
            g = (X**j) * (N**(m-i)) * f(x)**i * x**j
            polys.append(g)
    for i in range(t):
        g = (X**(d*m + i)) * f(x)**m * x**i
        polys.append(g)

    # 提取系数矩阵作为格基
    dim = d * m + t
    B = matrix(ZZ, dim, dim)
    for i, g in enumerate(polys):
        for j in range(dim):
            B[i, j] = g.coefficient(x, j)

    # LLL 规约
    B_reduced = B.LLL()

    # 取最短向量，还原为多项式
    h = sum(B_reduced[0][j] * x**j / X**j for j in range(dim))
    return h.roots()

八、BKZ：更强的规约

LLL 算法的近似因子随维数指数增长，对于高维格来说不够精确。BKZ（Block Korkin-Zolotarev）算法通过在局部块上执行更强的规约来改善这一点。

BKZ-beta 算法

BKZ-\(\beta\) 的核心思想是：在滑动窗口中对每个 \(\beta\) 维的块执行精确 SVP（或 强近似 SVP），然后将结果拼回全局基。

BKZ-beta(B, beta):
    repeat until no change:
        for k = 0 to d - beta:
            pi_k = 投影到 span(b*_k, ..., b*_{k+beta-1})
            v = SVP(pi_k(格的投影))
            if |v| < |b*_k|:
                插入 v，LLL 规约局部块
    return B

关键参数

根 Hermite 因子

衡量规约质量的标准指标是根 Hermite 因子 \(\gamma\)，定义为：

\[ \|b_1\| = \gamma^d \cdot \det(\mathcal{L})^{1/d} \]

不同算法的根 Hermite 因子：

BKZ 2.0

2011 年，Chen 和 Nguyen 提出了 BKZ 2.0，包含以下改进：

1. 极端剪枝（extreme pruning）：在 SVP 枚举中使用随机化剪枝，以接受少量 失败概率换取巨大的加速。

2. 早期终止：当进展停滞时提前终止。

3. 预处理：在 BKZ 巡回之前先做 LLL 和低 \(\beta\) 的 BKZ 预处理。

4. 自动选择参数：基于 GSA（Geometric Series Assumption）预测最优参数。

九、后量子格密码

1994 年 Shor 算法的出现意味着，一旦大规模量子计算机问世，RSA 和椭圆曲线密码 将被彻底攻破。格密码是后量子密码的主要候选方案之一，因为目前没有已知的量子算法 能高效地求解格上的困难问题。

LWE 问题

Learning With Errors（带误差学习问题）是格密码中最核心的困难问题。

定义：给定 \(m\) 个「带噪声」的线性方程：

\[ b_i = \langle a_i, s \rangle + e_i \pmod{q} \]

其中 \(a_i \in \mathbb{Z}_q^n\) 是随机已知向量，\(s \in \mathbb{Z}_q^n\) 是秘密 向量，\(e_i\) 是服从某个「小」分布（通常是离散高斯分布）的误差项。目标是恢复 \(s\)。

LWE 问题的困难性可以规约到最坏情况下的格问题（GapSVP 和 SIVP），这一规约由 Regev 在 2005 年证明。

SIS 问题

Short Integer Solution（短整数解问题）也是格密码的核心困难问题。

定义：给定随机矩阵 \(A \in \mathbb{Z}_q^{n \times m}\)，找到短的非零向量 \(x \in \mathbb{Z}^m\)，使得 \(Ax = 0 \pmod{q}\) 且 \(\|x\| \leq \beta\)。

SIS 是 SVP 的一种推广，它的困难性同样可以规约到最坏情况下的格问题。

NTRU

NTRU 是最早的格密码方案之一（1996 年），工作在截断多项式环 \(R = \mathbb{Z}[x]/(x^N - 1)\) 上。

• 密钥生成：选择两个小多项式 \(f, g \in R\)，公钥为 \(h = g \cdot f^{-1} \bmod q\)。
• 加密：选择随机小多项式 \(r\)，密文 \(c = r \cdot h + m \bmod q\)。
• 解密：计算 \(a = f \cdot c \bmod q\)，然后 \(a \bmod p\) 恢复消息。

对 NTRU 的最佳已知攻击就是在 NTRU 格上做 BKZ 规约。NTRU 格的维数为 \(2N\)， 基的形式为：

\[ \begin{pmatrix} qI_N & 0 \\ H & I_N \end{pmatrix} \]

其中 \(H\) 是由 \(h\) 的系数构成的循环矩阵。

Kyber/ML-KEM

2022 年，NIST 选定 CRYSTALS-Kyber 作为后量子密钥封装机制（KEM）的标准，后更名 为 ML-KEM（Module Lattice-based KEM）。它基于 Module-LWE 问题。

Kyber 的安全参数：

这里 \(n\) 是多项式环的维数，\(k\) 是模块秩，\(q\) 是模数。Module-LWE 的困难性在于： 即使用 BKZ-\(\beta\) 攻击，所需的块大小 \(\beta\) 也远超当前可行的范围。

格密码的攻击与安全估计

格密码的安全性评估本质上就是估计 BKZ-\(\beta\) 需要多大的 \(\beta\) 才能攻破方案， 以及运行 BKZ-\(\beta\) 需要多少时间。

核心安全假设链：

方案安全性
  <-- Module-LWE/SIS 困难性
    <-- 格上 approx-SVP 困难性
      <-- BKZ-beta 求解 approx-SVP 的复杂度
        <-- SVP oracle 在维数 beta 上的复杂度

目前 SVP oracle 的最佳已知复杂度：

LLL 在这里的角色是作为 BKZ 的子程序和初始预处理步骤。

十、实战：用 LLL 攻击小指数 RSA

本节展示一个完整的攻击场景：当 RSA 使用 \(e = 3\) 且消息有部分已知结构（例如 PKCS#1 v1.5 填充中的已知前缀）时，如何用 LLL 恢复消息。

攻击场景

假设 RSA 公钥 \((N, e)\)，其中 \(e = 3\)。已知密文 \(c = m^3 \bmod N\)，且消息 \(m = m_0 + x\) 具有已知高位 \(m_0\)，未知低位 \(x\) 满足 \(|x| < N^{1/3}\)。

目标多项式：\(f(x) = (m_0 + x)^3 - c \bmod N\)。

格的构造

以 Coppersmith 方法的简化版（Howgrave-Graham 方法）为例，取参数 \(m = 2\)：

构造 6 个移位多项式（\(d = 3\), \(m = 2\), \(t = 0\) 时的维数为 \(d \cdot m = 6\)）：

\[ g_0(x) = N^2, \quad g_1(x) = N^2 x, \quad g_2(x) = N^2 x^2 \] \[ g_3(x) = N f(x), \quad g_4(x) = N x f(x), \quad g_5(x) = f(x)^2 \bmod N^2 \]

将每个多项式 \(g_i(xX)\) 的系数作为格基的一行，对这个格做 LLL 规约。

代码：小指数 RSA 攻击（简化演示）

/*
 * 简化的 Coppersmith 攻击演示。
 * 仅用于教学，不处理大整数。
 */
static void demo_small_exponent_attack(void)
{
    printf("=== 小指数 RSA 攻击演示 ===\n");

    /* 简化参数（实际中 N 应该是 1024+ 比特） */
    double N = 1073741827.0;   /* 一个接近 2^30 的素数积 */
    double e = 3.0;

    /* 假设消息 m = m0 + x，其中 m0 已知，x 未知 */
    double m0 = 12345600.0;
    double x_true = 78.0;     /* 真实的未知部分 */
    double m = m0 + x_true;

    /* c = m^3 mod N（简化计算） */
    double c = fmod(m * m * m, N);

    /* 构造用于 Coppersmith 的格
     * 这里做一个极简化的一维版本作为演示 */
    printf("  N = %.0f\n", N);
    printf("  m0 = %.0f (已知)\n", m0);
    printf("  x_true = %.0f (待恢复)\n", x_true);
    printf("  c = %.0f\n", c);

    /* 构造格基：用于线性化近似
     * f(x) = (m0 + x)^3 - c mod N
     * 展开后收集系数，构建格 */
    double X = 1000.0;  /* x 的上界 */

    LatticeBase L;
    L.d = 4;
    L.n = 4;
    memset(L.B, 0, sizeof(L.B));

    /* 第一行：常数项的控制 */
    L.B[0][0] = N * N;
    L.B[0][1] = 0;
    L.B[0][2] = 0;
    L.B[0][3] = 0;

    /* 第二行：x 的系数 */
    L.B[1][0] = 0;
    L.B[1][1] = N * X;
    L.B[1][2] = 0;
    L.B[1][3] = 0;

    /* 第三行：x^2 的系数 */
    L.B[2][0] = 0;
    L.B[2][1] = 0;
    L.B[2][2] = N * X * X;
    L.B[2][3] = 0;

    /* 第四行：f(x) 的系数（乘以 X 的适当幂次） */
    double a0 = fmod(m0 * m0 * m0 - c, N);
    double a1 = 3.0 * m0 * m0;
    double a2 = 3.0 * m0;
    double a3 = 1.0;

    L.B[3][0] = a0;
    L.B[3][1] = a1 * X;
    L.B[3][2] = a2 * X * X;
    L.B[3][3] = a3 * X * X * X;

    printf("  规约前基向量范数:");
    for (int i = 0; i < L.d; i++)
        printf(" %.2e", sqrt(vec_norm2(L.B[i], L.n)));
    printf("\n");

    lll_reduce_fast(&L, 0.99);

    printf("  规约后基向量范数:");
    for (int i = 0; i < L.d; i++)
        printf(" %.2e", sqrt(vec_norm2(L.B[i], L.n)));
    printf("\n");

    /* 检查规约后的短向量 */
    for (int i = 0; i < L.d; i++) {
        double v3 = L.B[i][3];
        if (fabs(v3) > 0.5) {
            double x_cand = L.B[i][3] / (X * X * X);
            printf("  候选 x = %.2f (行 %d)\n", x_cand, i);
        }
    }

    printf("\n");
}

在实际的密码分析中，上述过程需要使用大整数库（如 GMP 或 fplll）。这里的代码仅 用于展示思路。

十一、工程实践与常见陷阱

数值稳定性

LLL 算法对浮点精度非常敏感。以下是实践中最常见的问题和解决方案：

整数 LLL 与浮点 LLL

在密码分析中，通常需要精确结果，因此实际库都使用整数 LLL（也称为 de Weger 变体）或多精度浮点 LLL。fplll 库支持多种模式：

编译与运行

# 编译上面的完整 C 代码
gcc -O2 -Wall -Wextra -o lll lll.c -lm

# 运行
./lll

fplll 库的使用

fplll 是目前最广泛使用的格规约库。安装和使用示例：

# 安装 fplll
sudo apt-get install libfplll-dev

# 或从源码编译
git clone https://github.com/fplll/fplll.git
cd fplll && autoreconf -i && ./configure && make && sudo make install

使用 fplll 命令行工具：

# 输入格式：每行一个基向量，数字间用空格分隔
echo "[[1 0 47][0 1 83][0 0 137]]" | fplll

# 指定 delta 参数
echo "[[1 0 47][0 1 83][0 0 137]]" | fplll -a lll -d 0.99

# 使用 BKZ
echo "[[1 0 47][0 1 83][0 0 137]]" | fplll -a bkz -b 20

十二、基准测试与个人思考

规约质量对比

以下是不同参数和算法在随机格上的典型表现（维数 \(d = 50\)，范数上界 \(B = 10^6\)）：

Bleichenbacher 式攻击

Daniel Bleichenbacher 在 1998 年提出了对 PKCS#1 v1.5 的自适应选择密文攻击。 虽然原始攻击不直接使用 LLL，但后续的改进版本利用格规约来减少所需的 oracle 查询 次数。

核心思想：每次 oracle 查询给出关于明文的一个线性不等式约束。收集足够多的约束后， 将问题转化为在一个格中找短向量。

这类攻击在 TLS 1.2 的 RSA 密钥交换中仍然是实际威胁（ROBOT 攻击，2017 年）。 即使在 TLS 1.3 已经移除了 RSA 密钥交换的今天，旧版协议的兼容性仍然让这类攻击 有存活空间。

我的思考

LLL 算法让我深刻体会到理论与实践之间的距离。在理论上，它的近似因子 \(2^{(d-1)/2}\) 在高维度下看起来很差。但在实践中，它几乎总是能给出远好于理论保证的结果。这种 「实际表现远超理论分析」的现象在算法研究中并不罕见，但 LLL 是最引人注目的例子 之一。

从密码学的角度看，LLL 的存在定义了一条安全边界。任何密码方案如果其安全性可以 规约到 \(2^{O(d)}\) 近似 SVP，那么它在多项式时间内就是不安全的。这直接导致了 格密码参数的选择必须让 BKZ 在更高的块大小下运行，而不仅仅是抵抗 LLL。

后量子密码的竞争中，格密码方案（以 Kyber/ML-KEM 和 Dilithium/ML-DSA 为代表） 最终胜出，部分原因是它们的安全假设被研究得最为透彻–而 LLL 及其后继算法正是 这种透彻研究的工具。密码学的安全不来自于隐藏弱点，而来自于在公开的攻击工具面前 仍然屹立不倒。

一个有趣的观察是：格问题在经典计算和量子计算下的困难性差距远小于因式分解或 离散对数。这既是格密码被选为后量子标准的原因（量子计算机带来的额外优势有限）， 也是它让人不太放心的地方（也许未来会有更好的量子算法）。

最后，从工程角度说一句：如果你在实际项目中需要格规约，请使用 fplll 而不是自己 写。数值稳定性问题会让你的实现在某些输入上静默地给出错误结果，而你可能永远 不会注意到。本文的 C 代码仅用于理解算法原理，不应用于生产环境。

进一步阅读

• Lenstra, Lenstra, Lovasz (1982). Factoring Polynomials with Rational Coefficients.
• Coppersmith (1996). Finding a Small Root of a Univariate Modular Equation.
• Nguyen, Vallee (2010). The LLL Algorithm: Survey and Applications. Springer.
• NIST (2024). FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard.
• Albrecht et al. (2021). The Lattice Estimator. https://github.com/malb/lattice-estimator

上一篇: 扩展欧几里得与模逆元

下一篇: 有限域算术

相关阅读: - 椭圆曲线算术 - 素性测试