HNP问题的数学背景

Hidden Number Problem是格密码学中的核心问题之一,其标准形式为:给定模数p和一组数对(t_i, a_i),寻找x使得t_i x ≡ a_i (mod p)对所有或大多数i成立,其中误差e_i = t_i x - a_i是有界的小量。这个问题最早出现在Boneh和Venkatesan关于DSA签名侧信道攻击的工作中:如果攻击者能获得DSA签名nonce的部分比特泄露,就可以构造HNP来恢复私钥。

HNP-2H是HNP的推广形式,每个方程包含两个小未知量而非一个。这使得问题的复杂度显著增加:标准HNP中每个方程只贡献一个约束维度,而HNP-2H中每个方程贡献两个维度。如果直接构造格,维度会是方程数量的两倍以上,使得LLL算法难以处理。因此需要特殊的技巧来降维,连分数逼近就是其中最经典的方法。

理解HNP-2H的关键在于认识到:虽然有两个小未知量,但它们都是以线性组合的形式出现在方程中。如果我们能找到一个线性变换,把这个二维向量投影到一条精心选择的直线上,使得投影后的量依然可界定,那么问题就约化回了标准HNP。这条直线的方向必须精心选择,使得变换后两个分量的系数都足够小。连分数逼近恰好提供了这样一种机制。

连分数理论的基础

在深入Honey的解法之前,有必要回顾连分数的基本性质。实数α的连分数展开为α = [a0; a1, a2, ...],其中a0是整数部分,ai都是正整数。第k个渐近分数p_k/q_k是通过截断连分数展开得到的,它满足重要的最佳逼近性质:在所有分母不超过q_k的有理数中,p_k/q_k是对α最好的逼近。

更精确地说,渐近分数满足不等式|α - p_k/q_k| < 1/(q_k · q_{k+1})。这个界告诉我们:如果两个连续的分母q_k和q_{k+1}差距很大,那么p_k/q_k对α的逼近就非常好。当q_{k+1}远大于q_k时,逼近误差主要由1/q_{k+1}控制。

在HNP-2H的应用中,我们利用的是这个性质:给定A和p,我们想找一个有理数u/λ使得λA非常接近up的倍数。这等价于要求A/p ≈ u/λ,即u/λ是A/p的好的有理逼近。连分数展开恰好能找到这样的逼近。

具体实现中,我们设定一个分母上界B,然后在A/p的连分数展开中找到第一个分母超过B的渐近分数,取前一项作为我们的逼近。这样保证λ < B,同时由于下一个分母q_{k+1} > B,逼近误差|A/p - u/λ| < 1/(λ·B)。乘以pλ后得到|λA - up| < p/B。

这个推导展示了参数B的选择逻辑:我们希望p/B尽可能小,使得Δ = λA - up很小,但同时也希望B不要太小使得λ本身变得很大。取B ≈ √p是一个平衡点,使得λ和Δ都在√p量级。

题目分析

题目给出了一个基于同余加密的系统,我们需要从密文中恢复出flag。加密脚本的核心逻辑如下:

def gen_params(nbit):
    p, Q, R, S = getPrime(nbit), [], [], []
    d = int(sqrt(nbit << 1))
    for _ in range(d):
        Q.append(getRandomRange(1, p - 1))
        R.append(getRandomRange(0, p - 1))
        S.append(getRandomRange(0, p - 1))
    return p, Q, R, S

def encrypt(m, params):
    p, Q, R, S = params
    d = int(sqrt(p.bit_length() << 1))
    C = []
    for _ in range(d):
        r, s = [getRandomNBitInteger(d) for _ in '01']
        c = Q[_] * m + r * R[_] + s * S[_]
        C.append(c % p)
    return C

params_enc.txt包含p, Q, R, S, C。其中p是512-bit素数,数组长度d = 32,每条密文满足:

C_i ≡ Q_i m + R_i r_i + S_i s_i (mod p)

核心未知量是m = bytes_to_long(flag)且m < p,噪声r_i, s_i是32-bit。

问题归类

把方程右移到同一侧:

C_i - Q_i m ≡ R_i r_i + S_i s_i (mod p)

这是Hidden Number Problem的一个变体。标准HNP的形式是t_i · x + e_i (mod p),其中e_i是小量。这类问题源于DSA签名的侧信道攻击:如果知道部分nonce的低位比特,可以用HNP恢复私钥。

而这里每个方程有两个小未知量r_i和s_i,文献中称之为HNP with Two Holes(HNP-2H)或HNP-2D。Hole指的是小未知量的维度,标准HNP是1-hole,这里是2-hole。

从几何角度看,每个方程在Z_p上定义了一个二维的小平面:{(r_i, s_i) | |r_i|, |s_i| < 2^32}。我们需要找一个点m,使得所有t_i m - a_i都落在对应小平面的投影附近。

这类题型的核心考点在于:如何通过数学变换把两个小未知量压缩成一个可界定的短量,然后构造格来求解。如果直接处理,维度会过高(需要同时恢复m和所有r_i, s_i),但通过连分数技巧,我们可以把问题降维。

第一步:消元

首先消去R_i,简化方程结构。令:

C̄_i ≡ R_i^(-1) C_i (mod p)
Q̄_i ≡ R_i^(-1) Q_i (mod p)
A_i ≡ R_i^(-1) S_i (mod p)

于是每条式子变为:

C̄_i - Q̄_i m ≡ r_i + A_i s_i (mod p)

现在右侧是两个小量的线性组合,但A_i是模p的随机元素,A_i s_i看起来把结构打散了。关键技巧是用连分数来恢复结构。

第二步:连分数逼近

对于分数A_i/p,我们需要找一个有理数逼近来控制A_i s_i的大小。这里的关键观察是:如果能找到u_i/λ_i使得λ_i A_i接近u_i p,那么:

λ_i A_i s_i = (u_i p + Δ_i)s_i ≡ Δ_i s_i (mod p)

其中Δ_i = λ_i A_i - u_i p是一个很小的量。

这里连分数展开给出了一个分数的最佳逼近序列。对于分数α = A_i/p,其连分数展开为[a0; a1, a2, ...],第k个渐近分数为p_k/q_k。这些渐近分数满足:

|α - p_k/q_k| < 1/(q_k · q_{k+1})

这意味着分母越大,逼近越好。但我们需要在分母大小和逼近精度之间取得平衡。

具体策略是:取B ≈ √p作为分母上界,在连分数展开中找到第一个分母超过B的项,取前一项作为我们的逼近。这样保证λ_i < B,同时由于q_{k+1} > B,有:

|A_i/p - u_i/λ_i| < 1/(λ_i · B)

两边乘以pλ_i得到:

|λ_i A_i - u_i p| < p/B ≈ √p

因此|Δ_i|在√p量级。这是整个技巧的核心:通过控制连分数分母的界,我们同时控制了λ_i和Δ_i的大小。

把原式两边乘以λ_i:

λ_i(C̄_i - Q̄_i m) ≡ λ_i r_i + λ_i A_i s_i (mod p)

将λ_i A_i替换成u_i p + Δ_i,由于u_i p s_i ≡ 0 (mod p):

λ_i(C̄_i - Q̄_i m) ≡ λ_i r_i + Δ_i s_i (mod p)

定义短量:

k_i = λ_i r_i + Δ_i s_i

现在|r_i|, |s_i| < 2^32,λ_i和Δ_i都在√p量级(约2^16),因此|k_i|的界约为√p · 2^32 ≈ 2^48。这里取一个宽松的上界B = √p · 2^34 ≈ 2^50。

HNP-2H被约化为一元secret加小误差的标准HNP形式。从几何角度看,我们把一个二维的小向量(r_i, s_i)通过线性变换(λ_i, Δ_i)投影到了一条线上,得到了一个可控的一维短量。

def lambda_from_cf(A, B, p):
    cf = (QQ(A) / QQ(p)).continued_fraction()
    for i in range(cf.length() - 1):
        di = Integer(cf.denominator(i))
        dj = Integer(cf.denominator(i + 1))
        if di < B and B <= dj:
            ui = Integer(cf.numerator(i))
            return di, ui
    return Integer(cf.denominator(cf.length() - 1)), Integer(cf.numerator(cf.length() - 1))

第三步:Kannan Embedding

现在有t_i m - a_i ≡ -k_i (mod p),其中t_i = λ_i Q̄_i,a_i = λ_i C̄_i,且|k_i| < B。

这是典型的Closest Vector Problem:在格L中找向量v使得v尽可能接近目标t = (a_0, ..., a_{n-1}, 0, M)。直接求解CVP很难,但Kannan embedding技巧可以把CVP转化为SVP。

核心思想是在高一维的空间中构造一个新格,使得新格中的短向量对应原问题的CVP解。构造(n+2)维格基如下:

def build_embedding_matrix(p, t, a, B):
    n = len(t)
    M = B
    Mtx = Matrix(ZZ, n + 2, n + 2)

    for i in range(n):
        Mtx[i, i] = Integer(p)

    for j in range(n):
        Mtx[n, j] = Integer(t[j])
    Mtx[n, n] = Integer(B)

    for j in range(n):
        Mtx[n + 1, j] = Integer(a[j])
    Mtx[n + 1, n + 1] = Integer(M)

    return Mtx

格基的几何直观:前n行对角线上是p,这允许我们在第i个坐标上自由加减p的倍数。这正是模运算需要的:对于任何整数q_i,q_i · p对应模p下的零,不会改变同余类。

第n行装t_i和误差界B。第n+1行装a_i和尺度M。这个设计的巧妙之处在于:当我们用整数向量(q_0, ..., q_{n-1}, x, -1)与这个基做线性组合时,得到:

(q_0 p + x t_0 - a_0, ..., q_{n-1} p + x t_{n-1} - a_{n-1}, xB, -M)

如果取x = m,并且选择q_i使得q_i p ≡ - (t_i m - a_i) (mod p),那么前n个坐标恰好是-(t_i m - a_i)在对称区间内的代表,也就是-k_i。

由于|k_i| < B,这些坐标都很小。整个向量的范数约为:

√(n · B² + (mB)² + M²)

当m < p ≈ 2^512且B ≈ 2^50时,最后一项mB占主导。但关键在于:随机向量的每个坐标预期在[0, p)范围内,其范数约为√n · p/2,远大于我们构造的这个特殊向量。

LLL算法能找到格中的最短非零向量(或接近最短的向量)。由于我们构造的特殊向量确实很短,LLL有很大概率把它找出来。

从另一个角度看,Kannan embedding本质上是在降维打击:CVP需要在n维空间中找最近点,而SVP只需要在n+2维空间中找最短向量。虽然维度增加了,但SVP有成熟的算法(LLL/BKZ),而CVP求解相对困难。

LLL算法原理补充

理解Kannan embedding为什么有效,需要了解LLL算法的基本原理。LLL(Lenstra-Lenstra-Lovász)算法是一种格基约化算法,输入是一个整数格的基,输出是一个"近似正交"的基,其中第一个向量相对较短。

算法的核心思想是迭代执行所谓的"size reduction"和"Lovász condition"检查。Size reduction确保每个基向量相对于它前面的向量尽可能短,而Lovász condition确保相邻基向量之间保持一定的角度关系。这两个条件共同作用使得约化后的基中前面的向量确实比原始基中的向量短得多。

对于Kannan embedding构造的格,如果我们正确设置了参数,那么对应正确secret的向量确实会比随机向量短很多。因此LLL输出的第一个或前几个向量很可能就是我们要找的解。这就是为什么从LLL的约化基中提取候选值是有效的。

第四步:候选提取与验证

LLL返回约化基后,从短向量中提取候选m。检查向量的最后两个坐标:如果倒数第二个是±M,或者能被B整除,则提取候选值。

def extract_candidates(red, B, M, p):
    cands = set()
    n = len(red[0]) - 2

    for r in red.rows():
        if abs(Integer(r[n + 1])) == M:
            x = Integer(r[n]) // Integer(B)
            if 0 <= x < p:
                cands.add(x)
        if Integer(r[n]) % Integer(B) == 0:
            x = abs(Integer(r[n]) // Integer(B))
            if 0 <= x < p:
                cands.add(x)

    return cands

拿到候选后必须验证。验证回到原始约束:计算残差u_i = λ_i(C̄_i - Q̄_i m) mod p,映射到对称区间(-p/2, p/2),检查是否满足|u_i| < B。

def centered(x, p):
    x = Integer(x) % p
    if x > p // 2:
        x -= p
    return x

def verify_candidate(m, p, Q, R, S, C, lam, B):
    n = len(Q)
    for i in range(n):
        invR = inverse_mod(Integer(R[i]), Integer(p))
        u = (Integer(lam[i]) * (invR * (Integer(C[i]) - Integer(Q[i]) * Integer(m)))) % p
        u = centered(u, p)
        if abs(u) >= B:
            return False
    return True

通过约束验证后,将m转为字节串,检查flag格式。

完整求解脚本

# SageMath
import ast

def read_params(path):
    s = open(path, "r").read()
    d = {}
    for line in s.strip().splitlines():
        k, v = line.split("=", 1)
        d[k.strip()] = ast.literal_eval(v.strip())
    return d["p"], d["Q"], d["R"], d["S"], d["C"]

def centered(x, p):
    x = Integer(x) % p
    if x > p // 2:
        x -= p
    return x

def lambda_from_cf(A, B, p):
    cf = (QQ(A) / QQ(p)).continued_fraction()
    for i in range(cf.length() - 1):
        di = Integer(cf.denominator(i))
        dj = Integer(cf.denominator(i + 1))
        if di < B and B <= dj:
            ui = Integer(cf.numerator(i))
            return di, ui
    return Integer(cf.denominator(cf.length() - 1)), Integer(cf.numerator(cf.length() - 1))

def solve_honey(params_path="params_enc.txt"):
    p, Q, R, S, C = read_params(params_path)
    n = len(Q)
    Bmin = isqrt(p)
    lam = []
    t = []
    a = []

    for i in range(n):
        invR = inverse_mod(Integer(R[i]), Integer(p))
        A = (invR * Integer(S[i])) % p
        li, ui = lambda_from_cf(A, Bmin, p)
        lam.append(li)
        t.append((Integer(li) * invR * Integer(Q[i])) % p)
        a.append((Integer(li) * invR * Integer(C[i])) % p)

    B = Integer(Bmin) * (Integer(2) ** Integer(34))
    M = B
    Mtx = Matrix(ZZ, n + 2, n + 2)

    for i in range(n):
        Mtx[i, i] = Integer(p)

    for j in range(n):
        Mtx[n, j] = Integer(t[j])
    Mtx[n, n] = Integer(B)

    for j in range(n):
        Mtx[n + 1, j] = Integer(a[j])
    Mtx[n + 1, n + 1] = Integer(M)

    red = Mtx.LLL()
    cands = set()

    for r in red.rows():
        if abs(Integer(r[n + 1])) == M:
            x = Integer(r[n]) // Integer(B)
            if 0 <= x < p:
                cands.add(x)
        if Integer(r[n]) % Integer(B) == 0:
            x = abs(Integer(r[n]) // Integer(B))
            if 0 <= x < p:
                cands.add(x)

    for x in list(cands):
        ok = True
        for i in range(n):
            invR = inverse_mod(Integer(R[i]), Integer(p))
            u = (Integer(lam[i]) * (invR * (Integer(C[i]) - Integer(Q[i]) * Integer(x)))) % p
            u = centered(u, p)
            if abs(u) >= B:
                ok = False
                break
        if ok:
            b = Integer(x).to_bytes((Integer(x).nbits() + 7) // 8, "big")
            if b"CCTF{" in b and b.endswith(b"}"):
                return b.decode(errors="ignore")

    return None

flag = solve_honey("params_enc.txt")
print(flag)

HNP-2H题型的本质与推广

Honey代表了一类典型的lattice题目:HNP with Two Holes。理解这类题型的本质,需要从代数结构和几何意义两个层面来把握。

从代数结构看,HNP-2H的核心困难在于两个小未知量的耦合。每个方程C_i ≡ Q_i m + R_i r_i + S_i s_i (mod p)包含三个未知量m, r_i, s_i,其中r_i, s_i是有界的小量。如果直接处理,我们需要在Z_p中同时恢复m和所有r_i, s_i,这是一个高维搜索问题。消元和连分数技巧的本质是降维:通过引入中间变量λ_i, Δ_i,把(r_i, s_i)这个二维小向量压缩成一维短量k_i = λ_i r_i + Δ_i s_i。这个压缩不是随意的,而是利用了A_i/p的连分数逼近性质,确保压缩后的量依然可界定。

从几何意义看,每个方程定义了Z_p中的一个约束:t_i m应该落在a_i的B邻域内。多个这样的约束在m的空间中产生了很多候选区间,这些区间的交集就是真正的解。Kannan embedding的巧妙之处在于:它把这些软约束编码成了格的几何结构。格中的短向量恰好对应满足所有约束的m值。LLL算法之所以能找到这个向量,是因为约束的一致性使得对应的格向量确实比随机向量短得多。

这类题目的识别特征比较明显。首先,方程形式通常包含模运算和多个小未知量,小未知量的界是明确的(如|r|, |s| < 2^32)。其次,目标secret通常模一个大素数,且方程数量足够多来保证唯一解。最重要的是,题面中会给出两个或更多系数数组,这些系数的引入往往就是为了构造两个hole。

解题的核心流程可以概括为六个阶段,但真正决定成败的是前三个阶段。消元阶段通过模逆运算把方程标准化,这一步看似简单但容易出现符号错误。连分数逼近是整个解题的灵魂:需要选择合适的分母界,界太大会导致Δ_i过大而破坏短量性质,界太小会压缩不够充分使得λ_i本身成为负担。Embedding构造则需要权衡维度和尺度,维度过高会增加LLL的计算时间,尺度选择不当会影响短向量的显著性。

参数选择有章可循。连分数的分母界通常取√p,这个选择的依据是:我们希望λ_i和Δ_i都在同一量级,这样它们的线性组合不会出现单方面主导。误差界B = Bmin · 2^(noise_bit + slack)中的slack通常取2到4位,给算法留出容错空间。尺度参数M取B是一种常见做法,但有时也可以取B的某个倍数来调整最后一行的权重。

这类题目有多种变形。最常见的是噪声界的变化,可能不是2^32而是其他值,需要相应调整B的倍数。方程数量也可能不同,少于20个可能需要用BKZ而非LLL,多于50个可能需要筛选方程。还有一种更难的变体是三个或更多小未知量,这时连分数技巧可能不够用,需要用多变量lattice方法。

​