HNP问题（隐数问题）

(Updated: )

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

HNP问题

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

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

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

实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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)