最近在复现Crypto CTF 2024的时候碰到一道题考察了HNP-2H（Hidden Number Problem with 2 Holes，双洞隐藏数问题），在做题的时候，找到了一篇论文：Extended Hidden Number Problem and Its Cryptanalytic Applications，并通过这篇论文了解到可以通过狄利克雷近似定理来将HNP-2H约化为我们熟悉的HNP来解决。

HNP-2H的定义

这里直接引用论文中的定义：

设\(N\)是一个质数，并设\(x\in \mathbb{Z}_n\)是一个部分未知的整数满足以下\(d\)条同余式： \[ \alpha_ix+\rho_{i,1}k_{i,1}+\rho_{i,2}k_{i,2}\equiv \beta_i\pmod{N},\ 1\le i\le d \] 其中\(\alpha_i\)满足\(\alpha_i\mod{N}\neq0\)，\(\alpha_i,\rho_{i,1},\rho_{i,2}\)以及\(\beta_i\)（\(1\le i\le d\)）为已知量，未知量\(k_{i,1}\)与\(k_{i,2}\)满足\(0\le k_{i,1}\le2^{\mu_1}\)及\(0\le k_{i,2}\le2^{\mu_2}\)（\(1\le i\le d\)），其中\(\mu_1,\mu_2\)为已知有理常量，则双洞隐藏数问题（Hidden Number Problem with 2 Holes）就是通过以上条件求出\(x\)。

使用狄利克雷近似解决HNP-2H

在使用狄利克雷近似解决HNP-2H之前，我们需要先了解何谓狄利克雷近似，其阐述如下

狄利克雷近似（Dirichlet's approximation）定理以及其推论

狄利克雷近似定理：设\(\alpha\in\mathbb{R}\)以及\(0<\varepsilon\le1\)为两已知量，那么存在\(p,q\in\mathbb{Z}\)使得\(1\le q\le\frac{1}{\varepsilon}\)以及\(|\alpha-\frac{p}{q}|<\frac{\varepsilon}{q}\)成立。

通过这个定理，我们可以得到如下推论：

假定我们已知\(A,N\in\mathbb{Z}\)与\(B\in\mathbb{R}\)满足\(B\ge1\)且\(N>0\)那么存在\(\lambda\in\mathbb{Z}\)满足\(1\le\lambda\le B\)且\(|\lambda A|_N<\frac{N}{B}\).（\(|a|_N\)表示\(min_{k\in\mathbb{Z}}|a-kN|\)）

通过狄利克雷近似定理以及其推论，我们可以知道，在已知\(B\)的情况下，我们可以通过连分数在多项式时间内通过\(|\lambda A|_N<\frac{N}{B}\)求解出\(\lambda\)

借助狄利克雷近似解决HNP-2H

本部分摘自论文第三部分的 Theorem 3 的证明

令\(A_i=(\rho_{i,1})^{-1}\rho_{i,2}\mod{N}\)，\(\gamma_i=k_{i,1}+A_ik_{i,2}\)，\(\alpha_i'=(\rho_{i,1})^{-1}\alpha_i\mod{N}\)以及\(\beta_i'=(\rho_{i,1})^{-1}\beta_i\mod{N}\)（\(1\le i\le d\)），则同余式\(\alpha_ix+\rho_{i,1}k_{i,1}+\rho_{i,2}k_{i,2}\equiv \beta_i\pmod{N}\)可以转化为： \[ \alpha_i'x+\gamma_i\equiv\beta'_i\pmod{N} \] 我们选定一个大于1的实数\(B\)，由狄利克雷近似的推论，我们可以通过连分数找到一个非零整数\(\lambda_{i,B}\)满足\(|\lambda_{i,B}A_i|<\frac{N}{B}\)，且有\(1\le\lambda_{i,B}\le B\)（\(1\le i\le d\)），使得下面的关系成立： \[ \begin{aligned} |\lambda_{i,B}\gamma_i|_N &=|\lambda_{i,B}k_{i,1}+\lambda_{i,B}A_ik_{i,2}|_N\\ &\le|\lambda_{i,B}|_Nk_{i,1}+|\lambda_{i,B}A_i|_Nk_{i,2}\\ &<B2^{\mu_1}+\frac{N}{B}2^{\mu_2} \end{aligned} \] 选择\(B_{min}=N^{\frac{1}{2}}2^{\frac{\mu_2-\mu_1}{2}}\)可以最大限度地减少\(B2^{\mu_1}+\frac{N}{B}2^{\mu_2}\)的上界（此时\(B_{min}2^{\mu_1}+\frac{N}{B_{min}}2^{\mu_2}=N^{\frac{1}{2}}2^{\frac{\mu_1+\mu_2+2}{2}}\)）.

在此之后，我们设\(k_i'=\left(\lambda_{i,B_{min}}\gamma_i+\lfloor N^{\frac{1}{2}}2^{\frac{\mu_1+\mu_2+2}{2}}\rfloor\right)\mod{N}\)，可以知道：\(k_i'<N^{\frac{1}{2}}2^{\frac{\mu_1+\mu_2+4}{2}}\)，那么通过下述步骤，我们就可以将HNP-2H转化为HNP，从而通过一般HNP的解决方法来解决HNP-2H了： \[ \begin{aligned} \alpha_i'x+\gamma_i&\equiv\beta'_i\pmod{N}\\ (\lambda_{i,B_{min}}\alpha_i')x+\lambda_{i,B_{min}}\gamma_i&\equiv\lambda_{i,B_{min}}\beta'_i\pmod{N}\\ (\lambda_{i,B_{min}}\alpha_i')x+k_i'&\equiv\lambda_{i,B_{min}}\beta'_i+\lfloor N^{\frac{1}{2}}2^{\frac{\mu_1+\mu_2+2}{2}}\rfloor\pmod{N}\\ \alpha_i''x+k_i'&\equiv\beta_i''\pmod{N},\ (1\le i\le d) \end{aligned} \]

例：[Crypto CTF 2024] Honey

加密代码：

#!/usr/bin/env python3  
  
from Crypto.Util.number import *  
from math import sqrt  
from flag import 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  
    assert m < p  
    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  
  
  
nbit = 512  
params = gen_params(512)  
m = bytes_to_long(flag)  
C = encrypt(m, params)  
f = open('params_enc.txt', 'w')  
f.write(f'p = {params[0]}\n')  
f.write(f'Q = {params[1]}\n')  
f.write(f'R = {params[2]}\n')  
f.write(f'S = {params[3]}\n')  
f.write(f'C = {C}')  
f.close()

整理可得方程组： \[ C_i\equiv Q_im+R_ir_i+S_is_i\pmod{p} \] 其中\(i=1,2,\cdots,d\)，而\(C_i,Q_i,R_i,S_i\)以及\(p\)均已知，而且知道\(0\le r_i,s_i\le2^d=2^{32}\)，要求\(m\)，显然，这是HNP-2H，那么我们可以通过上面讲的方法来将其约化为HNP来求解，有\(A_i=R_i^{-1}S_i\mod{p}\)，\(\gamma_{i}=r_i+A_is_i\)，\(\alpha_i'= R_i^{-1}Q_i\mod{p}\)，\(\beta_i'=R_i^{-1}C_i\mod{p}\)（\(1\le i\le d\)），可以将方程\(C_i\equiv Q_im+R_ir_i+S_is_i\pmod{p}\)变为： \[ \alpha_i'm+\gamma_i\equiv \beta_i'\pmod{p} \] 由于\(0\le r_i,s_i\le2^d=2^{32}\)，那么我们可以取\(\mu_1=\mu_2=32\)，那么我们取\(B_{min}=p^{\frac{1}{2}}2^{\frac{\mu_2-\mu_i}{2}}=p^{\frac{1}{2}}\)，则可以利用连分数计算出满足条件的\(\lambda_{i,B_{min}}\)，算法如下：

def getLambda(A):
    B = p.isqrt()
    cf = (A/p).continued_fraction()
    for i in range(len(cf)):
        if cf.denominator(i) < B and cf.denominator(i+1) > B:
            return cf.denominator(i)
    return None

在求出\(\lambda_{i,B_{min}}\)之后，我们可以得到： \[ k_i'=\left(\lambda_{i,B_{min}}\gamma_i+\lfloor p^{\frac{1}{2}}2^{\frac{\mu_1+\mu_2+2}{2}}\rfloor\right)\mod{p}=\left(\lambda_{i,B_{min}}\gamma_i+\lfloor p^{\frac{1}{2}}2^{33}\rfloor\right)\mod{p} \] 可以得到\(\{k_1,k_2,\cdots,k_d\}\)的上界\(K=p^{\frac{1}{2}}2^{\frac{\mu_1+\mu_2+4}{2}}=p^{\frac{1}{2}}2^{34}\).这样我们就可以将这个问题约化为一般的HNP进行求解，代码如下：

#sage
from Crypto.Util.number import*

p = ...
Q = [...]
R = [...]
S = [...]
C = [...]

def getLambda(A):
    B = p.isqrt()
    cf = (A/p).continued_fraction()
    for i in range(len(cf)):
        if cf.denominator(i) < B and cf.denominator(i+1) > B:
            return cf.denominator(i)
    return None

d = len(Q)
A = []
B = p.isqrt()

for i in range(d):
    a = inverse(R[i], p) * S[i] % p
    A.append(a)

alpha = []
beta = []

for i in range(d):
    lambda_i = getLambda(A[i])
    a = inverse(R[i], p) * Q[i] * lambda_i % p
    b = (inverse(R[i], p) * C[i] * lambda_i + floor(B * 2^33)) % p
    alpha.append(a)
    beta.append(b)

K = p.isqrt() * 2^34

L = matrix(QQ, d+2)

for i in range(d):
    L[i, i] = p
    L[-2, i] = alpha[i]
    L[-1, i] = beta[i]

L[-2, -2] = K / p
L[-1, -1] = K

res = L.LLL()

v = res[1]
m = int(abs(v[-2] * p / K))
print(long_to_bytes(m))

运行可得flag：CCTF{3X7eNdED_H!dD3n_nNm8eR_pR0Bl3m_iN_CCTF!!}