HNP问题（隐数问题）

为了证明Diffie-Hellman密钥交换协议而引入的HNP问题，用于解决在给定其线性关系的部分知识的情况下恢复秘密的“隐藏”数字

HNP问题

设p为素数，α ∈ [1, p − 1]中的任意整数并且需要恢复，给定的m个整数在{(t_i, a_i)}_i = 1^m​中满足式子形如 β_i − t_iα + a_i = 0 (mod  p) 其中β_i是未知的，并且满足任意|β_i| < K < P（K表示上界）

为了解决这一类问题，我们可以将式子重写为β_i + a_i = t_iα + k_ip 构造格 此时我们就有一个完整的短向量求解

但这个向量的结果并不是最优解，此时我们可以定义 t = (a₁, …, a_m, 0), u = (β₁, …, β_m, α/p)​我们就可以得到 vB − t = u 其中满足的条件为 此时我们就可以将这个问题转换为一个CVP问题 在条件 并且 B ≤ p/2^k下，我们可以用Kannan嵌入法进行一个SVP解决这个CVP问题，构造如下格 此时我们就可以得到一个目标向量u′ = (β₁, …, β_m, Kα/p, −K)，并且这个向量满足，det (B′) = p^m − 1 ⋅ k² 所以我们此时可以通过LLL算法拿到这个短向量u′,但此时该格上仍有一个更短向量(0, …, 0, K, 0),所以u′为第二短的向量。

实例

from Crypto.Util.number import *

t = 30
p = getPrime(512)
x = getPrime(512)
while x > p:
    x = getPrime(512)
rs = []
cs = []
ss = []
for i in range(t):
    r = getPrime(512)
    s = getPrime(400)
    c = (r * x + s) % p
    rs.append(r)
    cs.append(c)
    ss.append(s)

print(f'p = {p}')
print(f'rs = {rs}')
print(f'cs = {cs}')

exp

p = p
rs = rs
cs = cs
t = len(rs)
kbits = 400
K = 2 ** kbits

P = identity_matrix(t) * p
RC = matrix([[-1, 0], [0, 1]]) * matrix([rs, cs])
KP = matrix([[K / p, 0], [0, K]])
M = block_matrix([[P, 0], [RC, KP]], subdivide=False)
shortest_vector = M.LLL()
x = shortest_vector[1, -2] / K * p % p
print(x)

扩展隐藏数问题

扩展隐数问题将HNP问题扩展到存在关于秘密整数的线性关系的多个信息块，并且可以同时处理多个密码整数块的问题

设p为素数，设α ∈ [1, p − 1],则有式子 其中π_j和x̄都是已知的，并且对于未知的x_j满足对于一个已知的整数v_j，0 ≤ x_j < 2^ν_j给出d条方程 其中对于 1 ≤ i ≤ d, α_i ≢ 0 (mod  p), ρ_i, j 以及 β_i 均为已知的整数，未知正整数 k_i, j 的上界为 2^μ_i, j 已知，则扩展隐藏数问题 (EHNP) 则是通过上述条件恢复 α。为解决 EHNP, 我们可以构造格: 其中具体的各个函数（diag表示对角矩阵）

计算：

通过 κ_D, 我们可以得到满足 0 < δκ_D < 1

我们需要根据上述的构造格 ℒ(B, δ), 在格 ℒ 中找到向量 u 使得:

通过 LLL 算法对我们构造的格进行规约可以得到:

然后令

最后计算：