发表于 2023-04-07 更新于 2023-11-12 本文字数： 24k 阅读时长 ≈ 22 分钟

有关隐藏数问题的简要笔记

HNP 问题

HNP 问题，the Hidden Number Problem。

LHNP(线性隐藏数问题)

原理

LHNP，即 The Linear Hidden Number Problem，线性隐藏数问题。

定义是从形如 \[ c_i=r_i\cdot x+e_i\pmod{p} \] 的一组方程组恢复 \(s\)。

即 \[ \begin{cases} c_1=r_1\cdot x+e_1\\ c_2=r_2\cdot x+e_2\\ \ \ \ \ \ \ \vdots\\ c_n=r_t\cdot x+e_t\\ \end{cases}\pmod{p} \] 将单个方程可以转化为 \[ e_i=c_i-r_i\cdot x+k_ip \] 我们可以构造出矩阵 \[ M=\begin{bmatrix} p\\ & p\\ & & \ddots\\ & & & p\\ -r_1 & -r_2 & \cdots & -r_n & K/p &\\ c_1 & c_2 & \cdots & c_n & & K \end{bmatrix} \] 其中 \(K\) 为 \(e_i\) 的上界，\(k_i\) 为常系数，用于占位便于格出最短向量，该矩阵满足 \[ (k_1,k_2,\cdots,k_t,x,1)M=(e_1,e_2,\cdots,e_t,Kx/p,K) \] 其中 \((e_1,e_2,\cdots,e_t,Kx/p,K)\) 可证在格中，那么我们进行 LLL 算法即可得到该向量，并且可以从中还原 \(x\)。

实例

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}')

从上面代码我们可以获取三十个方程满足 \[ c_i=r_i\cdot x+s_i\pmod{p} \] 构造格后 LLL 算法即可得到 \(x\)。

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)

MIHNP(模反隐藏数问题)

原理

MIHNP，即 The Modular Inversion Hidden Number Problem，模反隐藏数问题。

针对的是形如 \[ h_i=(s+t_i)^{-1}-e_i\pmod{p} \] 其中，\(e\) 是误差（error），满足 \(|e|\leq \frac{p}{2^{k+1}}\)，从 \(d\) 个 \((h_i,t_i)\) 对中恢复 \(s\) 即模反隐藏数问题。

考虑其中一个方程，有 \[ (h_0+e_0)(s+t_0)\equiv 1\pmod{p} \] 那么可以改写成 \(s\) 的表达式 \[ s\equiv \frac{1-(h_0+e_0)t_0}{h_0+e_0}\equiv\frac{1}{h_0+e_0}-t_0\pmod{p} \] 如果我们有另外一个对 \((h_1,t_1)\)，那么可以写作 \[ (h_1+e_1)(s+t_1)\equiv 1\pmod{p} \] 将 \(s\) 改写为用 \((h_0,t_0)\) 对表示 \[ 1\equiv (h_1+e_1)(\frac{1}{h_0+e_0}-t_0+t_1)\pmod{p} \] 展开可写成方程 \[ (h_0+e_0)(h_1+e_1)(t_0-t_1)+(e_0-e_1)+(h_0-h_1)\equiv 0\pmod{p} \] 那么其中只有 \((e_0,e_1)\) 对未知，我们仅需构造方程后进行二元 Coppersmith 还原这两个小根即可。

实例

from Crypto.Util.number import *
import random, os
from gmpy2 import *
flag = 'flag{th1s_1s_fl4g}'

p = random.getrandbits(1024)

print('> mod =', p)
secret = random.randint(1, p-1)

def XennyOracle():
    r = getPrime(512)
    d = invert(secret+r, p) - getPrime(246)
    print('> r =', r)
    print('> d =', d)

def task():
    for _ in range(3):
        op = int(input())
        if op == 1:
            XennyOracle()
        elif op == 2:
            ss = int(input())

            if ss == secret:
                print('flag: ', flag)

try:
    task()
except Exception:
    print("Error. try again.")

根据如上代码，可以得到关系式 \[ d=\frac{1}{\mathrm{secret}+r}-e\pmod{p} \] 其中我们需要两对 \((d,r)\)。

mod = 103749960487318496535753127992597646596574197997346604494391500263407540367515232654243412375033616945349248057185120615722859917113041268644784351010497818179758334399774566693302975715253680868349322945783661543444012109390796753316368646224473385493551959776211868508124173853146220498072369988662598365737

r = 7554447571265160138826769036234163274945140724778979915009852024745364483862510066425251491305987868229626094117437547971483604358422085703908125935180533

d = 101985344200009891162621238301457902327130889519486305921303529965809795092552155000675574294868973653091733390024027051635945224775240336861956431150596823874553394527629780608016246850565741640968516986406244424459268316383289944793625444505084150632372055950924768521047738331629715715251235824065754062421

r = 13090253437847914840731392679465737677743543688720968701737801038380918192995977693627043510294249352189923663339210839369051093420312059888494671044789773

d = 67171614284124458946714888283433754454833311156850027624019964385885510153022868877446836813353331293804301964862035632895563688487758460098403813402145815716073796080437726175478667720783792797395845065060542295820029322704256388851730482630855413455182090758448749461531342234199684253932837821327563402710

构造二元方程

mod = 103749960487318496535753127992597646596574197997346604494391500263407540367515232654243412375033616945349248057185120615722859917113041268644784351010497818179758334399774566693302975715253680868349322945783661543444012109390796753316368646224473385493551959776211868508124173853146220498072369988662598365737
r1 = 7554447571265160138826769036234163274945140724778979915009852024745364483862510066425251491305987868229626094117437547971483604358422085703908125935180533
d1 = 101985344200009891162621238301457902327130889519486305921303529965809795092552155000675574294868973653091733390024027051635945224775240336861956431150596823874553394527629780608016246850565741640968516986406244424459268316383289944793625444505084150632372055950924768521047738331629715715251235824065754062421
r2 = 13090253437847914840731392679465737677743543688720968701737801038380918192995977693627043510294249352189923663339210839369051093420312059888494671044789773
d2 = 67171614284124458946714888283433754454833311156850027624019964385885510153022868877446836813353331293804301964862035632895563688487758460098403813402145815716073796080437726175478667720783792797395845065060542295820029322704256388851730482630855413455182090758448749461531342234199684253932837821327563402710

import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    
    print("LLL done")

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []

Fp.<e1, e2> = Zmod(mod)[]
f = (d1 + e1) * (d2 + e2) * (r1 - r2) + e1 - e2 + d1 - d2
roots = small_roots(f, (2 ** 246, 2 ** 246))
print(roots)
e1, e2 = roots[0]
s1 = inverse_mod(ZZ(d1 + e1), mod) - r1
s2 = inverse_mod(ZZ(d2 + e2), mod) - r2
print(s1 == s2)
print(s1)

输出如下

LLL done

[(110376508622719622460215737752126153337071479266224099409237079274751233023, 105599366105793964194530868572953367123126433936636879204012605915941896157)]

True

53379746320881385658533052144390270941298506554594791554301088574708911821601622941503571564466589181259916168325928415646767240609719266256878030902014359933013735963354498961369838802171449182939387573660896489128177385885182722953047765671114102309583476608373333611398704410882862602499435963602566386559

扩展

我们由上述方程 \[ (h_0+e_0)(h_1+e_1)(t_0-t_1)+(e_0-e_1)+(h_0-h_1)\equiv 0\pmod{p} \] 可以变形为 \[ (t_0-t_1)e_0e_1+(h_1(t_0-t_1)+1)e_0+(h_0(t_0-t_1)-1)e_1+h_0h_1(t_0-t_1)+h_0-h_1=0\pmod{p} \] 即可以改写成一个关于 \(e_0,e_1\) 的方程 \[ F_i(X,Y)=A_iXY+B_iX+C_iY+D_j \] 满足 \(F_i(e_0, e_i)=0\pmod{p}\)

其中系数一一对应为 \[ A_i=t_0-t_i\\ B_i=h_i(t_0-t_i)+1\\ C_i=h_0(t_0-t_i)-1\\ D_i=h_0h_i(t_0-t_i)+h_0-h_i \]

这里是，对于任意 \((e_0,e_i)\) 对均成立此方程。

自然地，对于 \(d\) 个 \((e_0,e_i)\) 对，我们可以列出方程组 \[ \boldsymbol{v}=(1,e_1,\cdots,e_d,e_0,e_0e_1,\cdots,e_0e_d,k_1,\cdots,k_d)\\ R=\begin{bmatrix} D_1&D_2&\cdots&D_d\\ C_1&0&\cdots&0\\ 0&C_2&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&C_d\\ B_1&B_2&\cdots&B_d\\ A_1&0&\cdots&0\\ 0&A_2&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&A_d\\ \end{bmatrix} ,P=\begin{bmatrix} p&0&\cdots&0\\ 0&p&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&p \end{bmatrix}\\ \boldsymbol{v}\begin{bmatrix}R\\P\end{bmatrix}=\boldsymbol{0} \] 为了解出方程中的 \((e_0,\cdots,e_d)\)，不妨构造格 \[ M=\begin{bmatrix} E&R\\ 0&P \end{bmatrix} \] 其中 \[ E=\begin{bmatrix} 1&0&\cdots&0&0&\cdots&0\\ 0&2^{-k}&\cdots&0&0&\cdots&0\\ \vdots&\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&2^{-k}&0&\cdots&0\\ 0&0&\cdots&0&2^{-2k}&\cdots&0\\ \vdots&\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&0&0&\cdots&2^{-2k} \end{bmatrix} \] 其中，\(k\) 是 \(e_i\) 的位数

使得 \[ \boldsymbol{v}M=(1,\frac{e_1}{2^{k}},\cdots,\frac{e_d}{2^{k}},\frac{e_0}{2^{k}},\frac{e_0e_1}{2^{2k}},\cdots,\frac{e_0e_d}{2^{2k}},0,\cdots,0) \] 这个解向量很小，可以证明在格内。

实例

from Crypto.Util.number import *
import random, os
from gmpy2 import *
flag = 'flag{th1s_1s_fl4g}'

p = random.getrandbits(1024)

print('> mod =', p)
secret = random.randint(1, p-1)

def XennyOracle():
    r = getPrime(512)
    d = invert(secret+r, p) - getPrime(328)
    print('> r =', r)
    print('> d =', d)

def task():
    for _ in range(16):
        op = int(input())
        if op == 1:
            XennyOracle()
        elif op == 2:
            ss = int(input())

            if ss == secret:
                print('flag: ', flag)

try:
    task()
except Exception:
    print("Error. try again.")

我们迭代十五次获取到 ds 和 rs。

还原 \(secret\) 的代码如下

p = mod
hs = ds
ts = rs
k = 328
d = len(hs) - 1
Ai = []
Bi = []
Ci = []
Di = []
for i in range(1, d + 1):
    Ai.append(ts[0] - ts[i])
    Bi.append(hs[i] * Ai[-1] + 1)
    Ci.append(hs[0] * Ai[-1] - 1)
    Di.append(hs[0] * hs[i] * Ai[-1] + hs[0] - hs[i])
R = block_matrix([matrix(Di), diagonal_matrix(Ci), matrix(Bi), diagonal_matrix(Ai)], ncols=1)
P = diagonal_matrix(ZZ, [p] * d)
E = block_diagonal_matrix([matrix([1]), diagonal_matrix([2^(-k)] * (d + 1)), diagonal_matrix([4^(-k)] * d)])
M = block_matrix([[E, R], [0, P]])
shortest_vector = M.LLL()[0]
es = shortest_vector[1:d+2] * 2 ^ k
es = list(es[-1:]) + list(es[:-1])
s = inverse_mod(ZZ(hs[0] + es[0]), p) - ts[0]
print(s)

ECHNP(椭圆曲线隐藏数问题)

原理

ECC 加密中，公开对通常是 \((tG,P+tG)\)，其中 \(tG\) 是公钥，\(P+tG\) 是密文。

如果说我们拥有一个预言机，我们可以选择公钥生成密文，即使密文出现一定的错误，我们也可以还原出明文 \(P_x\)。

我们知道对任意的 \(t\) 可以成立 \[ O_{P,G}(t)=(P+tG)_x=\left(\frac{y_P-y_Q}{x_P-x_Q}\right)^2-x_P-x_Q-e_t\pmod{p} \] 其中，\(Q=tG\)。

不妨令 \[ h_t=(P+tG)_x \] 那么有 \[ (h_t+e_t+x_P+x_Q)(x_P-x_Q)^2=(y_P-y_Q)^2=x_P^3+ax_P+b-2y_Py_Q+y_Q^2\pmod{p} \] 优先选择 \(t=0\)，那么我们有 \[ h_0=x_P-e_0 \] 考虑 \(y_P\) 是我们不需要的数据，将其化简得到 \[ y_P=\frac{x_P^3+ax_P+b+y_Q^2-(h_0+e_0+x_P+x_Q)(x_P-x_Q)}{2y_Q} \] 不妨考虑共轭对 \((P+Q)_x,(P-Q)_x\)

令 \[ s_{P+Q}=\frac{y_P-y_Q}{x_P-x_Q},s_{P-Q}=\frac{y_P-y_{-Q}}{x_P-x_{-Q}} \] 我们尝试消去 \(y_P\)，有 \[ \begin{align} (P+Q)_x+(P-Q)_x&=s_{P+Q}^2-x_P-x_Q+s_{P-Q}^2-x_P-x_Q\\ &=2\left(\frac{x_Qx_P^2+(a+x_Q^2)x_P+ax_Q+2b}{(x_P-x_Q)^2}\right) \end{align} \] 那么 \(h_i=(P+Q)_x-e_i\) 和其共轭 \(h_{-i}=(P-Q)_x-e_{-i}\) 可以构造 \(\tilde{h}_i=h_i+h_{-i}\)，\(\tilde{e}_i=e_i+e_{-i}\)，再加上 \(x_P=h_0+e_0\)，我们可以得到 \[ \tilde{h}_i+\tilde{e}_i=2\left(\frac{x_Q(h_0+e_0)^2+(a+x_Q^2)(h_0+e_0)+ax_Q+2b}{(h_0+e_0-x_Q)^2}\right) \] 我们再把分母上的 \((h_0+e_0-x_Q)^2\) 左乘，化简，我们可以改写为一个关于 \(e_0,\tilde{e}_t\) 的方程 \[ \begin{align} F_i(X,Y)&=X^2Y+(\tilde{h}_i-2x_Q)X^2+2(h_0-x_Q)XY+2[\tilde{h}_i(h_0-x_Q)-2h_0x_Q-a-x_Q^2]X+(h_0-x_Q)^2Y+[\tilde{h}_i(h_0-x_Q)^2-2h_0^2x_Q-2(a+x_Q^2)h_0-2ax_Q-4b]\\ &=X^2Y+A_iX^2+A_{0,i}XY+B_iX+B_{0,i}Y+C_i \end{align} \] 满足 \(F_i(e_0, \tilde{e}_i)=0\pmod{p},Q=iG\)

其中系数一一对应为 \[ A_i=\tilde{h}_i-2x_Q\\ A_{0,i}=2(h_0-x_Q)\\ B_i=2[\tilde{h}_i(h_0-x_Q)-2h_0x_Q-a-x_Q^2]\\ B_{0,i}=(h_0-x_Q)^2\\ C_i=\tilde{h}_i(h_0-x_Q)^2-2h_0^2x_Q-2(a+x_Q^2)h_0-2ax_Q-4b \] 自然地，对于 \(d\) 个 \((e_0,\tilde{e}_i)\) 对，我们可以列出方程组 \[ \boldsymbol{v}=(1,e_0,\tilde{e}_1,\cdots,\tilde{e}_d,e_0^2,e_0\tilde{e}_1,\cdots,e_0\tilde{e}_d,k_1,\cdots,k_d)\\ R=\begin{bmatrix} -C_1&-C_2&\cdots&-C_d\\ -B_1&-B_2&\cdots&-B_d\\ -B_{0,1}&0&\cdots&0\\ 0&-B_{0,2}&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&-B_{0,d}\\ -A_1&-A_2&\cdots&-A_d\\ -A_{0,1}&0&\cdots&0\\ 0&-A_{0,2}&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&-A_{0,d}\\ \end{bmatrix} ,P=\begin{bmatrix} p&0&\cdots&0\\ 0&p&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&p \end{bmatrix}\\ \boldsymbol{v}\begin{bmatrix}R\\P\end{bmatrix}=\begin{bmatrix}e_0^2\tilde{e}_1,\cdots,e_0^2\tilde{e}_d\end{bmatrix} \] 为了解出方程中的 \((e_0,\cdots,e_d)\)，不妨构造格 \[ M=\begin{bmatrix} E&R\\ 0&P \end{bmatrix} \] 其中 \[ E=\begin{bmatrix} 2^{3k}&0&\cdots&0&0&\cdots&0\\ 0&2^{2k}&\cdots&0&0&\cdots&0\\ \vdots&\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&2^{2k}&0&\cdots&0\\ 0&0&\cdots&0&2^{k}&\cdots&0\\ \vdots&\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&0&0&\cdots&2^{k} \end{bmatrix} \] 其中，\(k\) 是 \(e_i\) 的位数

使得 \[ \boldsymbol{v}M=(2^{3k},e_02^{2k},\tilde{e}_12^{2k},\cdots,\tilde{e}_d2^{2k},e_0^22^{k},e_0\tilde{e}_12^{k},\cdots,e_0\tilde{e}_d2^k,e_0^2\tilde{e}_1,\cdots,e_0^2\tilde{e}_d) \] 这个解向量可以证明在格内。

实例

from Crypto.Util.number import *
import os

p = getPrime(1024)
a = getPrime(200)
b = getPrime(200)
E = EllipticCurve(GF(p), [a, b])
R = E.random_element()
P = E.random_element()

print('> mod =', p)
print('> a =', a)
print('> b =', b)
print(f'> R = ({R[0]}, {R[1]})', )

def XennyOracle(t):
    O = P + t*R
    return int(O[0]) - getPrime(163)

def task():
    for _ in range(30):
        op = int(input())
        if op == 1:
            XennyOracle(int(input()))
        elif op == 2:
            ss = int(input())

            if ss == P[0]:
                print('flag: ', flag)

try:
    task()
except Exception:
    print("Error. try again.")

我们可以从中获取椭圆曲线的参数，点 \(G\) 和 14 对 \((e_0,\tilde{e}_i)\)，还原脚本如下：

p = p
a = a
b = b
E = EllipticCurve(GF(p), [a, b])
G = E((x, y))
hs = hs
k = 163
d = len(hs) - 1
Ai = []
A0i = []
Bi = []
B0i = []
Ci = []
for i in range(1, d + 1):
    Q = i * G
    xQ = ZZ(Q[0])
    Ai.append(hs[i] - 2 * xQ)
    A0i.append(2 * (hs[0] - xQ))
    Bi.append(2 * (hs[i] * (hs[0] - xQ) - 2 * hs[0] * xQ - a - xQ ^ 2))
    B0i.append((hs[0] - xQ) ^ 2)
    Ci.append(hs[i] * (hs[0] - xQ) ^ 2 - 2 * ((hs[0] ^ 2 +a) * xQ + (a + xQ ^ 2) * hs[0] + 2 * b))
R = block_matrix(ZZ, [-matrix(Ci), -matrix(Bi), -diagonal_matrix(B0i), -matrix(Ai), -diagonal_matrix(A0i)], ncols=1)
P = diagonal_matrix(ZZ, [p] * d)
E = block_diagonal_matrix([matrix([8^k]), diagonal_matrix([4^k] * (d + 1)), diagonal_matrix([2^k] * (d + 1))])
M = block_matrix([[E, R], [0, P]])
shortest_vector = M.LLL()[0]
es = shortest_vector[1:d+1] / 4 ^ k
xP = ZZ(hs[0] + es[0])
print(xP)

HSSP(隐子集和问题)

The Hardness of the Hidden Subset Sum Problem and Its Cryptographic Implications

A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem

原理

HSSP，即 Hidden Subset Sum Problem，隐子集和问题。

使用 Nguyen-Stern Algorithm 求解，内部使用正交格实现。

在 HSSP 中，主要针对的是给予一个模数 \(M\) 和结果向量 \(\bold{h}=(h_1,\cdots,h_m)\)，满足 \[ \bold{h}=\alpha_1\bold{x}_1+\alpha_2\bold{x}_2+\cdots+\alpha_n\bold{x}_n\pmod{M} \] 其中我们需要还原向量 \(\bold{\alpha}=(\alpha_1,\cdots,\alpha_n)\) 和向量 \(\bold{x}_i\in\{0,1\}^m\)。

Nguyen-Stern 算法主要分两步：

从样本 \(\bold{h}\) 中，计算得到正交格 \(\bar{\mathcal{L}}_\bold{x}\)，其中 \(\mathcal{L}_\bold{x}\) 从 \(\bold{x}_i\) 生成。
从正交格 \(\bar{\mathcal{L}}_\bold{x}\) 中，恢复隐向量 \(\bold{x}_i\)。从 \(\bold{h},\bold{x}_i,M\) 中恢复权重向量 \(\alpha_i\)。

算法

第一步：正交格攻击

首先计算格 \(\mathcal{L}_0\)，需要满足条件 \(\gcd(h_1,M)=1\)，其次将向量改写为 \(\bold{h}=(h_1,\bold{h}'),\bold{u}=(u_1,\bold{u}')\)，那么可以从 \(\bold{u}\in \mathcal{L}_0\) 得到 \[ u_1\cdot h_1+\bold{u}'\cdot \bold{h}'\equiv 0\pmod{M} \] 即 \[ u_1+\bold{u}'\cdot \bold{h}'\cdot h_1^{-1}\equiv 0\pmod{M} \] 此时化为 SVP 问题，改写成 \[ (k,\bold{u}')\mathcal{L}_0=\bold{u}\newline \mathcal{L}_0=\begin{bmatrix} M&\newline -\bold{h}'\cdot h_1^{-1}&\bold{I}_{m-1} \end{bmatrix} \] 其中，\(m\) 是 \(\bold{h}\) 的维度。

那么我们对 \(\mathcal{L}_0\) 进行格规约，即可得到 \(\bold{u}_1,\cdots,\bold{u}_m\)，其中前 \(m-n\) 个向量 \(\bold{u}_1,\cdots,\bold{u}_{m-n}\) 组成格 \(\mathcal{L}_{\bold{x}}^{\perp}\)。

随后我们进行正交格规约，计算 \(\bar{\mathcal{L}}_\bold{x}=(\mathcal{L}_{\bold{x}}^{\perp})^{\perp}\)，这是由一组向量 \((\bold{c}_1,\cdots,\bold{c}_n)\) 生成的。

第二步：恢复 \(\bold{x}_i,\bold{\alpha}\)

由于 LLL 算法本身的限制，我们得到的基向量 \((\bold{c}_1,\cdots,\bold{c}_n)\) 可能要比 \((\bold{x}_1,\cdots,\bold{x}_n)\) 大，而原始向量组一定是 \(L_\bold{x}\) 中最短的向量之一。

因此这里需要选择用 BKZ 算法以获得更好的基，但此时改变了格的形式，因为 \(\bold{x}_i\pm \bold{x}_j,i\neq j\) 也可能很短，所以还需要额外的一步去还原原始向量。

这样我们得到 \((\bold{x}_1,\cdots,\bold{x}_n)\)，再通过解方程的方式求解 \(\bold{\alpha}=(\alpha_1,\cdots,\alpha_n)\)。

代码

def ortholattice(h, M):
    """
    生成一个在模M下与h正交的格L0，满足`L0*h%M==0`

    参数：
        h - 一个向量(vector)
        M - 模数

    返回值：
        一个在ZZ域内的，在模M下与h正交的矩阵
    """
    m = len(h)
    L0 = identity_matrix(Zmod(M), m)
    L0[1:, 0] = -h[1:] * inverse_mod(h[0], M)
    L0 = L0.change_ring(ZZ)
    L0[0, 0] = M

    return L0

def kernelLLL(L_perp):
    """
    求解$(L^\perp)^\perp$以找到$L$，同时使用LLL化简格
    """
    n = L_perp.nrows()
    m = L_perp.ncols()
    if m < 2 * n:
        # 不满足NS正交格攻击的条件
        # 需要注意的是在multivariate攻击中条件有变
        return L_perp.right_kernel_matrix()
    # 乘以K是为了满足LLL算法的条件
    K = 2 ** (m // 2) * L_perp.height()
    L_l = block_matrix(2, 1, [K * L_perp, identity_matrix(ZZ, m)])
    L = L_l.T.LLL().T

    assert L[:n, :m-n] == 0, "理论上会压缩这部分向量"
    Ke = L[n:, :m-n].T

    return Ke

def allones(v):
    """
    将合解的向量取绝对值，不合理的向量返回None

    参数：
        v - 解向量
    
    返回值：
        合解的向量或None
    """
    if all(vi in [0, 1] for vi in v):
        return v
    elif all(vi in [0, -1] for vi in v):
        return -v
    return None

def recovery(Lx):
    """
    恢复原始解向量组，顺序不一定

    参数：
        Lx - 通过BKZ算法恢复的基

    返回值：
        原始解向量组
    """
    # 正确的解
    Lv = [allones(v) for v in Lx if allones(v)]
    for vi in Lv:
        for vj in Lx:
            # 如果vj-vi是解
            v = allones(vj - vi)
            if v and v not in Lv:
                Lv.append(v)
            # 如果vj+vi是解
            v = allones(vj + vi)
            if v and v not in Lv:
                Lv.append(v)
    return matrix(ZZ, Lv)

def NSAttack(n, h, p):
    """
    NS攻击，`m=len(h)`

    参数：
        n - 向量组大小（权重维度）
        h - 结果向量
        p - 模数
    
    返回值：
        乱序的原始向量组
    """
    h = vector(h)
    m = len(h)
    L0 = ortholattice(h, p)
    # 格出向量u，向量u满足u*h%M==0
    L1 = L0.LLL()
    print('[+] LLL done.')
    # 向量u组成新格Lx_perp
    Lx_perp = L1[:m-n]
    # 求解$(Lx^\perp)^\perp$
    Lx = kernelLLL(Lx_perp)
    print('[+] Lx solved.')
    # 格规约Lx，化简格，便于运行BKZ算法
    Lx_bar = Lx.LLL()
    # 使用BKZ算法，获得更好的基
    for beta in range(10, n, 10):
        # 如果基都落在-1,0,1中，那么说明可以提前退出BKZ算法
        if all(all(i in [-1, 0, 1] for i in vec) for vec in Lx_bar):
            break
        Lx_bar = Lx_bar.BKZ(block_size=beta)
    print('[+] BKZ done.')

    # 求解$(\bold{x}1,\cdots,\bold{x}_n)$
    print('[+] recovery X.')
    X = recovery(Lx_bar)

    return X

LLBP(线性位泄露问题)

定义

LLBP，即 The Linear Bits Leakage Problem，线性位泄露问题。

指的是形如 \[ a_ix=b_i\pmod{N} \] 的线性方程，但我们仅有 \(N\) 与 \(b_i\) 的部分位，需要还原出 \(x\)。

MSB

MSB，Most Significant Bits，即最高位泄露。

假定 \(N\) 的位数为 \(\eta\)，泄露最高位位数为 \(\rho\)。

此时我们考虑将 \(b_i\) 表示为 \[ b_i=h_i+s_i \] 其中，\(h_i\) 是泄露出来的最高位，而 \(s_i\) 为未知的低位（秘密）。

那么变形可得新方程为 \[ x=a_i^{-1}(h_i+s_i)\pmod{N} \]

那么选取两对 \(x\) 相关方程 \((b_0,b_i)\)，有 \[ a_i^{-1}(h_i+s_i)=a_0^{-1}(h_0+s_0)\pmod{N} \] 展开可得 \[ s_i=a_ia_0^{-1}s_0+a_ia_0^{-1}h_0-h_i \] 那么可以构建方程， \[ A_i=a_ia_0^{-1}\newline B_i=a_ia_0^{-1}h_0-h_i\newline s_i=A_is_0+B_i \] 即改写成 \[ (k_1,\cdots,k_n,s_0,1)\begin{bmatrix} N&\newline &\ddots\newline &&N\newline A_1&\cdots&A_n&1\newline B_1&\cdots&B_n&&K \end{bmatrix}=(s_1,\cdots,s_n,s_0,K) \] 其中，\(K\) 为平衡系数，\(K=2^{\eta-\rho}\)。

需要满足条件 \[ \rho(n+1)\geq \eta \]

生成代码如下

from Crypto.Util.number import getPrime, getRandomRange

def gen(k: int, eta: int, rho: int):
    assert rho * (k + 1) >= eta
    hs = []
    A = []
    B = []
    N = getPrime(eta)
    x = getRandomRange(1, N)
    for _ in range(k):
        a = getRandomRange(1, N)
        b = a * x % N
        A.append(a)
        B.append(b)
        gamma = eta - rho
        hs.append(b >> gamma << gamma)
    return x, N, A, B, hs

k = 5
eta = 768
rho = 256
x, N, A, B, hs = gen(k, eta, rho)
print(f'{x = }')
print(f'{N = }')
print(f'{A = }')
print(f'{B = }')
print(f'{hs = }')

格代码如下

k = 5
eta = 768
rho = 256
A = ...
hs = ...
N = ...

Ai = []
Bi = []
for ai, hi in zip(A[1:], hs[1:]):
    Ai.append(ai * pow(A[0], -1, N) % N)
    Bi.append((Ai[-1] * hs[0] - hi) % N)

Ai = matrix(Ai)
Bi = matrix(Bi)
MA = matrix.identity(k - 1) * N
K = ZZ(pow(2, eta - rho))
M = matrix.block([[MA, ZZ(0), ZZ(0)], [Ai, ZZ(1), ZZ(0)], [Bi, ZZ(0), K]])
L = M.LLL()
ss = list(L[0])
assert ss[-1] == K
ss = ss[-2:-1] + ss[:-2]
B = [ZZ(hi + si) for hi, si in zip(hs, ss)]

LSB

LSB，Lowest Significant Bits，即最低位泄露。

假定 \(N\) 的位数为 \(\eta\)，泄露最低位位数为 \(\rho\)。

此时我们考虑将 \(b_i\) 表示为 \[ b_i=2^{\rho}s_i+l_i \] 其中，\(l_i\) 是泄露出来的最低位，而 \(s_i\) 为未知的高位（秘密）。

那么变形可得新方程为 \[ x=a_i^{-1}(2^{\rho}s_i+l_i)\pmod{N} \]

那么选取两对 \(x\) 相关方程 \((b_0,b_i)\)，有 \[ a_i^{-1}(2^{\rho}s_i+l_i)=a_0^{-1}(2^{\rho}s_0+l_0)\pmod{N} \] 展开可得 \[ 2^{\rho}s_i=a_ia_0^{-1}2^{\rho}s_0+a_ia_0^{-1}l_0-l_i \] 那么可以构建方程， \[ A_i=a_ia_0^{-1}\newline B_i=\frac{a_ia_0^{-1}l_0-l_i}{2^{\rho}}\newline s_i=A_is_0+B_i \] 即改写成 \[ (k_1,\cdots,k_n,s_0,1)\begin{bmatrix} N&\newline &\ddots\newline &&N\newline A_1&\cdots&A_n&1\newline B_1&\cdots&B_n&&K \end{bmatrix}=(s_1,\cdots,s_n,s_0,K) \] 其中，\(K\) 为平衡系数，\(K=2^{\eta-\rho}\)。

生成代码如下

from Crypto.Util.number import getPrime, getRandomRange

def gen(k: int, eta: int, rho: int):
    assert rho * (k + 1) >= eta
    ls = []
    A = []
    B = []
    N = getPrime(eta)
    x = getRandomRange(1, N)
    for _ in range(k):
        a = getRandomRange(1, N)
        b = a * x % N
        A.append(a)
        B.append(b)
        ls.append(b % pow(2, rho))
    return x, N, A, B, ls

k = 5
eta = 768
rho = 256
x, N, A, B, ls = gen(k, eta, rho)
print(f'{x = }')
print(f'{N = }')
print(f'{A = }')
print(f'{B = }')
print(f'{ls = }')

格攻击代码如下

k = 5
eta = 768
rho = 256
# A = ...
# ls = ...
# N = ...

Ai = []
Bi = []
for ai, li in zip(A[1:], ls[1:]):
    alpha = ai * pow(A[0], -1, N) % N
    Ai.append(alpha)
    Bi.append((alpha * ls[0] - li) * pow(2, -rho, N) % N)

Ai = matrix(Ai)
Bi = matrix(Bi)
MA = matrix.identity(k - 1) * N
K = ZZ(pow(2, eta - rho))
M = matrix.block([[MA, ZZ(0), ZZ(0)], [Ai, ZZ(1), ZZ(0)], [Bi, ZZ(0), K]])
L = M.LLL()
ss = list(L[0])
assert ss[-1] == K
ss = ss[-2:-1] + ss[:-2]
B = [ZZ(hi + si * pow(2, rho)) for hi, si in zip(ls, ss)]
B

随机位泄露

分析

同理，假定 \(N\) 的位数为 \(\eta\)，其中随机位泄露用数对 \((\gamma_i,\gamma_i+\rho_i)\) 表示，这代表着从 \(\gamma_i\) 位开始泄露，泄露其中 \(\rho_i\) 位。

此时我们考虑将 \(b_i\) 表示为 \[ b_i=m_{i,0}+2^{\rho_0}s_{i,0}+2^{\gamma_1}m_{i,1}+2^{\gamma_1+\rho_1}s_{i,1}+\cdots+2^{\gamma_l}m_{i,l}+2^{\gamma_l+\rho_l}s_{i,l} \] 其中，\(m_i\) 是泄露出来的位，而 \(s_i\) 为未知的位（秘密）。

这里将 \(b_i\) 分离成多块，每一块以 [泄露位，未知位] 组成，\(\gamma_0\) 默认为 \(0\)。

那么变形可得新方程为 \[ x=a_i^{-1}(m_{i,0}+2^{\rho_0}s_{i,0}+2^{\gamma_1}m_{i,1}+2^{\gamma_1+\rho_1}s_{i,1}+\cdots+2^{\gamma_l}m_{i,l}+2^{\gamma_l+\rho_l}s_{i,l})\pmod{N} \]

那么选取两对 \(x\) 相关方程 \((b_0,b_i)\)，有 \[ \begin{align} &a_i^{-1}(m_{i,0}+2^{\rho_0}s_{i,0}+2^{\gamma_1}m_{i,1}+2^{\gamma_1+\rho_1}s_{i,1}+\cdots+2^{\gamma_l}m_{i,l}+2^{\gamma_l+\rho_l}s_{i,l})\\ =&a_0^{-1}(m_{0,0}+2^{\rho_0}s_{0,0}+2^{\gamma_1}m_{0,1}+2^{\gamma_1+\rho_1}s_{0,1}+\cdots+2^{\gamma_l}m_{0,l}+2^{\gamma_l+\rho_l}s_{0,l})\pmod{N} \end{align} \] 左乘可得 \[ \begin{align} &m_{i,0}+2^{\rho_0}s_{i,0}+2^{\gamma_1}m_{i,1}+2^{\gamma_1+\rho_1}s_{i,1}+\cdots+2^{\gamma_l}m_{i,l}+2^{\gamma_l+\rho_l}s_{i,l}\\ =&a_ia_0^{-1}(m_{0,0}+2^{\rho_0}s_{0,0}+2^{\gamma_1}m_{0,1}+2^{\gamma_1+\rho_1}s_{0,1}+\cdots+2^{\gamma_l}m_{0,l}+2^{\gamma_l+\rho_l}s_{0,l})\pmod{N} \end{align} \] 变形为 \(s_{i,j}\) 的方程，由于方程太复杂这里不写出过程，以系数形式表示 \[ \begin{align} \alpha_i&=a_ia_0^{-1}\\ A_{i,0}&=\alpha_i2^{\rho_0}\\ A_{i,1}&=\alpha_i2^{\gamma_1+\rho_1}\\ \vdots\\ A_{i,l}&=\alpha_i2^{\gamma_l+\rho_l}\\ B_i&=\sum_{j=0}^{l}2^{\gamma_j}(\alpha_im_{0,j}-m_{i,j})\\ 2^{\rho_0}s_{i,0}+\cdots+2^{\gamma_l+\rho_l}s_{i,l}&=A_{i,0}s_{0,0}+\cdots+A_{i,l}s_{0,l}+B_i\\ \sum^{l}_{j=0}2^{\gamma_j+\rho_j}s_{i,j}&=\sum^{l}_{j=0}A_{i,j}s_{0,j}+B_i \end{align} \]

MSB

MSB 情况下是 \(l=1\) 的情况，即

\[ b_i=s_{i,0}+2^{\gamma_1}m_{i,1} \] 其中，\(\rho_0=0\) 代表第零块无泄露位，没有 \(\gamma_2\) 代表第一块无未知位。

其中方程为 \[ \begin{align} \alpha_i&=a_ia_0^{-1}\\ A_{i,0}&=\alpha_i\\ B_i&=2^{\gamma_1}(\alpha_im_{0,0}-m_{i,0})\\ s_{i,0}&=A_{i,0}s_{0,0}+B_i \end{align} \]

LSB

而 LSB 情况下同样是 \(l=1\) 的情况，即 \[ b_i=m_{i,0}+2^{\rho_0}s_{i,0} \] 其中方程为 \[ \begin{align} \alpha_i&=a_ia_0^{-1}\\ A_{i,0}&=\alpha_i2^{\rho_0}\\ B_i&=\alpha_im_{0,j}-m_{i,j}\\ 2^{\rho_0}s_{i,0}&=A_{i,0}s_{0,0}+B_i \end{align} \]

格

\[ \mathcal{L}=\begin{bmatrix} \mathrm{diag}(N)&\\ \mathrm{diag}(-2^{\gamma_0+\rho_0})&\mathrm{diag}(2^{\eta+(\gamma_0+\rho_0)-\gamma_1})\\ \vdots&&\ddots\\ \mathrm{diag}(-2^{\gamma_{l-1}+\rho_{l-1}})&&&\mathrm{diag}(2^{\eta+(\gamma_{l-1}+\rho_{l-1})-\gamma_l})\\ A_{i,0}&&&&1\\ \vdots&&&&&\ddots\\ A_{i,l}&&&&&&1\\ B_i&&&&&&&K \end{bmatrix}\\ (k_0,\cdots,k_{l-1},s_{i,0},\cdots,s_{i,l-1},s_{0,0},\cdots,s_{0,l},1)\mathcal{L}\\ =(2^{\gamma_l+\rho_l}s_{1,l},\cdots,2^{\gamma_l+\rho_l}s_{i,l},\sigma_s s_{1,l-1},\cdots,\sigma_s s_{i,0},\sigma_s s_{0,0},\cdots,\sigma_s s_{0,l},K) \]

其中，\(\sigma_s\) 补足位数使得每个方向上的位数为 \(\eta\)，且 \(K=2^\eta\)，实际计算中格整体除以 \(2^{\gamma_l+\rho_l}\) 便于计算。