格密码

2020-11-07 crypto 格密码 ∞ 评论

格密码

线性独立空间上有集合 $v_1,\cdots,v_n \in \mathbb{R}^n$ ，格（Lattices）就是这些向量的线性组合，用公式表示为：

$L=\{a_1v_1+a_2v_2+\cdots+a_nv_n \mid a_1,a_2,\cdots,a_n \in \mathbb{Z}\}$ 。

格 $L$ 的维数等于格中向量的个数。

假定 $v_1,v_2,\cdots,v_n$ 是格 $L$ 的基， $w_1,w_2,\cdots,w_n \in L$ ，则必然存在整系数 $a_{ij}$ 使得：

$\begin{cases} w_1=a_{11}v_1+a_{12}v_2+\cdots+a_{1n}v_n \\ w_2=a_{21}v_1+a_{22}v_2+\cdots+a_{2n}v_n \\ \vdots \\ w_n=a_{n1}v_1+a_{n2}v_2+\cdots+a_{nn}v_n \end{cases}$

这样，格的问题就是矩阵运算了。

最短向量问题（SVP，The Shortest Vector Problem）：

寻找一个格 $L$ 中最短的非零向量。即，寻找一个 $v \in L$ 满足其欧几里德范数 $\mid\mid v \mid\mid$ 最小。

最接近向量问题（CVP，The Closest Vector Problem）：

对于一个非格 $L$ 中的向量 $w$ ，在格中寻找一个向量 $v$ ，使得 $\mid\mid w-v \mid\mid$ 最小。

CVP和SVP都是NP完备问题，因此求解起来十分困难，因此这两个问题都是可以作为密钥体制的基础的。

Hermite定理

这个定理揭示了格中最短向量的大概长度。
定理本体：对 $n$ 维的格 $L$ ，都包含一个非零向量 $v \in L$ ，满足： $|v|\leq \sqrt n \det (L) ^ {1/n}$ 。
$v$ 的长度是可以构造的，而上界是固定的，越接近上界，值越精确，故可以通过系数调整 $|v|$ 的值（配平）从而使得和上界更接近；但是存在问题，如果系数过大，使得长度超过了上界，则无法求解。

构造示例

$bm-kn-c=-r \Longrightarrow \begin{bmatrix} m & -1 & -k \end{bmatrix}\begin{bmatrix} 1 & 0 & b \newline 0 & 2^{400} & c \newline 0 & 0 & n \end{bmatrix}=\begin{bmatrix} m & -2^{400} & -r \end{bmatrix}$

使目标向量中的值数量级相近会更利于规约，对格进行配平（乘大系数T）后规约，有机会得到目标向量。

LLL加速：flatter

from subprocess import check_output
from re import findall

def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

L = flatter(M)

参考：

格攻击之小未知数方程求解入门——原理与例子

格基规约算法：算法详解

【CTF-Crypto】格密码基础

NRTU

NTRU是一个带有专利保护的开源公开密钥加密系统，使用基于格的加密算法来加密数据。它包括两部分算法：NTRUEncrypt用来加密，NTRUSign用来进行数字签名。与其他流行的公钥加密系统不同，它可以防止被Shor算法破解，并显著提升了性能。

在同等加密强度下，NTRU执行大开销的私钥操作比RSA算法快得多。RSA算法的私钥操作耗时与密钥长度呈三次方关系，而NTRU相应操作为二次方关系。

NTRU密码体制，需要三个整数参数 $(N,p,q)$ 和四个次数为 $N-1$ 的整系数多项式集合 $L_f,L_g,L_{\varphi},L_m$ ，在这里 $N$ 为一素数， $p,q$ 可以不必为素数，但为安全，要求 $\gcd(p,q)=1$ ，且 $q$ 远大于 $p$ 。

NTRU工作于多项式整数环 $\mathbb{R}=\mathbb{Z}[x]/(x^N-1)$ ，当 $F \in \mathbb{R}$ ，可以把 $F$ 表示为多项式或向量形式， $F=\sum\limits_{i=0}^{N-1}F_ix^i=[F_0,F_1,\cdots,F_{N-1}]$ 。

在这里记 $L(d_1,d_2)=\{F \in \mathbb{R}:F$ 有 $d_1$ 个系数为 $1$ ， $d_2$ 个系数为 $-1$ ，其余为 $0\}$ ，选取三个确定的整数 $d_f,d_g,d_{\varphi}$ ，多项式集合 $L_f=L(d_f,d_{f-1}),L_g=L(d_g,d_g),L_{\varphi}=L(d_{\varphi},d_{\varphi})$ ，而 $L_m=\{m \in \mathbb{R}:m$ 的系数位于区间 $[-\cfrac{p-1}{2},\cfrac{p-1}{2}]$ ，其中 $p$ 为素数 $\}$ 。

密钥生成

B随机选择两个多项式 $f$ 和 $g$ ， $f\in L_f,g\in L_g$ ，要求 $f$ 关于模 $p$ 和模 $q$ 的逆 $F_p,F_q$ 都存在，也即 $F_q \star f \equiv 1 \pmod q$ 和 $F_p \star f \equiv 1 \pmod p$ ，这里可以用扩展欧几里得算法计算出 $F_p$ 和 $F_q$ 。为此， $f$ 首先应满足 $\gcd(f(1),pq)=1$ ，如果有一个逆不存在，需重新选择 $f$ 。

然后，B计算 $h \equiv F_q \star g \pmod q$ ，则公钥为 $h$ ，私钥为 $f$ ，但在实际中，还将存储 $F_p$ ，因而一般认为私钥为 $(f,F_p)$ 。

加密

假设A想发送信息 $m \in L_m$ 给B，他将根据参数 $d_{\varphi}$ 随机选择一个 $\varphi \in L_{\varphi}$ ，然后，他利用B的公钥 $h$ 计算

$e \equiv \varphi \star h+m \pmod q$

A把密文 $e$ 发送给B。

解密

当B收到密文 $e$ 后，他首先利用私钥 $f$ 计算

$a \equiv f \star e \pmod q$

选择 $a$ 的系数位于 $[-\cfrac{p-1}{2},\cfrac{p-1}{2}]$ 之间，然后计算

$b \equiv a \pmod p$

$c \equiv F_p \star b \pmod p$

则多项式 $c$ 就是明文 $m$ 。

构造矩阵

$B^{NT}= \left(\begin {array}{c} I & H \newline 0 & q \end{array} \right) =\left(\begin {array}{cccc|cccc} \lambda & 0 & \cdots & 0 & h_0 & h_1 & \cdots & h_{N-1} \newline 0 & \lambda & \cdots & 0 & h_{N-1} & h_0 & \cdots & h_{N-2}\newline \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \newline 0 & 0 & \cdots & \lambda & h_1 & h_2 & \cdots & h_0 \newline \hline 0 & 0 & \cdots & 0 & q & 0 & \cdots & 0 \newline 0 & 0 & \cdots & 0 & 0 & q & \cdots & 0 \newline \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \newline 0 & 0 & \cdots & 0 & 0 & 0 & \cdots & q \end{array} \right)$

其中 $H$ 是根据公钥多项式的系数生成的循环矩阵。

构建一个这样的矩阵，然后进行LLL算法得到解密密钥。

参考

NTRU学习笔记

从一道CTF题初探NTRU格密码

Practical lattice-based cryptography: NTRUEncrypt and NTRUSign

#Sage
h = 
p = 
c = 

v1 = vector(ZZ, [1, h])
v2 = vector(ZZ, [0, p])
m = matrix([v1,v2]);
f, g = m.LLL()[0]
print(f, g)

a = f*c % p % g
m = a * inverse_mod(f, g) % g
print(bytes.fromhex(hex(m)[2:]))

#Sage 
#多项式1
N =
p =
q =
Q.<x> = Zmod(q)[]
P.<y> = Zmod(p)[]

ex = 
hx = 

print('-------decrypt------')
qq = x^N-1
pp = y^N-1
hn = [int(x) for x in hx.coefficients()]
n = len(hn)
A1 = matrix.identity(n)
A0 = matrix.zero(n)
Aq = matrix.identity(n) * q
Ah = matrix(ZZ, [hn[-i:] + hn[:-i] for i in range(n)])
M = block_matrix([A1,Ah,A0,Aq],nrows=2)
L = M.LLL()
v = L[0]
f = list(v)[:n]
g = list(v)[n:]
fx = Q(f)
fy = P(f)
gx = Q(g)
Fqx = fx.inverse_mod(qq)
Fpy = fy.inverse_mod(pp)

#hxx = (Fqx*gx).mod(x^N-1)
#print(hxx==hx)

ax = (fx*ex).mod(qq)
an = [int(x) for x in ax.coefficients()]
#中心提升(centerlift)，使域范围从[0,q)变换到(-q/2,q/2)
for i in range(len(an)):
	if an[i] > q//2:
		an[i] -= q
ax = P(an)
print(ax)
out = (Fpy * ax).mod(pp)
print(out)

print(bytes(out.coefficients()))

p = 
q = 
n = 
Zx.<x> = ZZ[]

e = 
h = 

def inv_mod_prime(f,p):
    T = Zx.change_ring(Integers(p)).quotient(x^n-1)
    return Zx(lift(1 / T(f)))

def mul(f,g):
    return (f * g) % (x^n-1)

def bal_mod(f,q):
    g = list(((f[i] + q//2) % q) - q//2 for i in range(n))
    return Zx(g)

def decrypt(e,pri_key):
    f,fp = pri_key
    a = bal_mod(mul(e,f),q)
    d = bal_mod(mul(a,fp),p)
    return d

def get_key():
    for j in range(2 * n):
        try:
            f = Zx(list(M[j][:n]))
            fp = inv_mod_prime(f,p)
            return (f,fp)
        except:
            pass
    return (f,f)

M = matrix(ZZ, 2*n, 2*n)
hh = h.list()
for i in range(n): M[i,i] = 1
for i in range(n,2*n): M[i,i] = q
for i in range(n):
    for j in range(n):
        M[i,j+n] = hh[(n-i+j) % n]
M = M.LLL()
key = get_key()

l = decrypt(e, key).list()
flag = bytes(l)
print(flag)

# Sage
# Ref: https://www.osgeo.cn/sagemath/constructions/rings.html
class NTRU:
  def __init__(self, N, p, q, d):
    self.debug = False

    assert q > (6*d+1)*p
    assert is_prime(N)
    assert gcd(N, q) == 1 and gcd(p, q) == 1
    self.N = N
    self.p = p
    self.q = q
    self.d = d
  
    self.R_  = PolynomialRing(ZZ,'x')
    self.Rp_ = PolynomialRing(Zmod(p),'xp')
    self.Rq_ = PolynomialRing(Zmod(q),'xq')
    x = self.R_.gen()
    xp = self.Rp_.gen()
    xq = self.Rq_.gen()
    self.R  = self.R_.quotient(x^N - 1, 'y')
    self.Rp = self.Rp_.quotient(xp^N - 1, 'yp')
    self.Rq = self.Rq_.quotient(xq^N - 1, 'yq')

    # order check in keyGen
    #self.RpOrder = self.p^self.N - self.p
    #self.RqOrder = self.q^self.N - self.q
    self.RpOrder = self.p^(self.N - 1) - 1
    self.RqOrder = (self.q^self.N - self.q) // (self.q-1)


    self.sk, self.pk = self.keyGen()

  def test(self):
    assert self.debug == True
    pass

  def T(self, d1, d2):
    assert self.N >= d1+d2
    t = [1]*d1 + [-1]*d2 + [0]*(self.N-d1-d2)
    shuffle(t)
    return self.R(t)

  # center lift
  def lift(self, fx):
    mod = Integer(fx.base_ring()(-1)) + 1  # emmm
    return self.R([Integer(x)-mod if x > mod//2 else x for x in list(fx)])

  def keyGen(self):
    fx = self.T(self.d+1, self.d)
    gx = self.T(self.d, self.d)

    Fp = self.Rp(list(fx)) ^ (-1)                           # list emmm
    assert pow(self.Rp(list(fx)), self.RpOrder-1) == Fp     # order checked
    assert self.Rp(list(fx)) * Fp == 1                
    
    # Fq = self.Rq(fx) ^ (-1)   # wasted
    Fq = pow(self.Rq(list(fx)), self.RqOrder - 1)     # invert
    assert self.Rq(list(fx)) * Fq == 1                # order checked
    
    hx = Fq * self.Rq(list(gx))

    sk = (fx, gx, Fp, Fq, hx)
    pk = hx
    return sk, pk

  def setKey(self, fx, gx):
    assert type(fx) == type('x^2 + 1')  # e.g.
    assert type(gx) == type('x^2 - 1')  # emmm

    try:
      fx = self.R(fx)
      gx = self.R(gx)

      Fp = self.Rp(list(fx)) ^ (-1)
      Fq = pow(self.Rq(list(fx)), self.RqOrder - 1)
      hx = Fq * self.Rq(list(gx))

      self.sk = (fx, gx, Fp, Fq, hx)
      self.pk = hx
      return True
    except:
      return False
  
  def getKey(self):
    ssk = (
          str(self.R_(list(self.sk[0]))),   # fx
          str(self.R_(list(self.sk[1])))    # gx
        )
    spk = str(self.Rq_(list(self.pk)))      # hx
    return ssk, spk
   
  def encrypt(self, m):
    assert type(m) == type('x^2 + 1') # e.g.
    assert self.pk != None
    hx = self.pk
    mx = self.R(m)
    mx = self.Rp(list(mx))              # change m to Rp, TODO: assert m in Rp
    mx = self.Rq(list(mx))              # change m to Rq

    rx = self.T(self.d, self.d)
    rx = self.Rq(list(rx))
    

    e = self.p * rx * hx + mx
    #return e
    return str(self.Rq_(list(e)))

  def decrypt(self, e):
    assert type(e) == type('xq^2 - 1')  # e.g.
    assert self.sk != None
    fx, gx, Fp, Fq, hx = self.sk

    e = self.Rq(e)
    ax = self.Rq(list(fx)) * e
    a = self.lift(ax)                   # center lift
    bx = Fp * self.Rp(list(a))
    b = self.lift(bx)
    
    #return bx
    return str(self.R_(list(b)))
    
if __name__ == '__main__':
  mm = '-x^2 + x + 1'
  ntru = NTRU(N=11, p=3, q=512, d=3)
  #ntru.setKey('xp^2+1', 'xq^2-1')
  
  print('keyGen check:')
  sk, pk = ntru.getKey()
  print("fx = '%s'" % sk[0])
  print("gx = '%s'" % sk[1])
  print("hx = '%s'" % pk)
  
  print('\nencrypt/decrypt check:')
  e = ntru.encrypt(mm)
  print("e = '%s'" % e)
  m = ntru.decrypt(e)
  print(m)
  assert m == mm
  print(m)

  print('\ncheck setKey:')
  fx = ''
  gx = ''
  hx = ''
  e = ''
  ntru.setKey(fx, gx)
  m = ntru.decrypt(e)
  assert m == mm
  print(m)

参考：

SCTF-XCTF 2020 - Lattice

MAR DASCTF - threshold

GGH加密

1997年，Goldreich、Goldwasser、Halevi三人受Ajtai在格难题上的研究所启发，提出了一个基于格中最近向量难题的非对称密码学算法：GGH Cryptosystem。

1999年，Nguyen发现在这个密码学算法设计中，有一个很大的缺陷，可以使攻击者从密文中获取到明文的部分信息，且可以将原来的最近向量难题转化为一个较为简单的最近向量难题。基于这个观察，Nguyen解出了设计者放在网上的5个challenge中的4个（其中有2个被设计者认为是不可能攻破的），足以证明该密码算法是broken的。

定义

GGH包含一个私钥和一个公钥，选取格 $L$ 的一组好基 $B$ 和一个幺模矩阵 $U$ 作为私钥，计算 $L$ 的另一组基 $B’=UB$ 作为公钥。

选定 $M$ 值，明文向量 $(m_1,m_2,\cdots,m_n), \quad m_i \in(-M,M)$ 。

加密

给定明文 $m=(m_1,m_2,\cdots,m_n)$ ，误差向量 $e$ ，和公钥 $B’$ ，计算 $v=m \cdot B’=\displaystyle\sum m_ib_i’$ ；
密文 $c=v+e=m \cdot B’+e$ 。

解密

计算 $c \cdot B^{-1}=(m \cdot B’+e)B^{-1}=m \cdot U \cdot B \cdot B^{-1}+e \cdot B^{-1}=m \cdot U+e \cdot B^{-1}$ ；
如果 $e \cdot B^{-1}$ 足够小，可利用Babai最近平面算法的变种Babai rounding technique去除；
最后计算 $m=m \cdot U \cdot U^{-1}$ 得到明文。

GGH中的误差向量的选取是3或者-3。

求解

利用Nguyen’s Attack算法。

# Sage 
# Read ciphertext and public key.
c = []
c = vector(ZZ, c)

B = []
B = matrix(ZZ, B)

# Nguyen's Attack.
n = 150
delta = 3
s = vector(ZZ, [delta]*n)
B6 = B.change_ring(Zmod(2*delta))
left = (c + s).change_ring(Zmod(2*delta))
m6 = (B6.solve_left(left)).change_ring(ZZ)
new_c = (c - m6*B) * 2 / (2*delta)

# embedded technique
new_B = (B*2).stack(new_c).augment(vector(ZZ, [0]*n + [1]))
new_B = new_B.change_ring(ZZ)

new_B_BKZ = new_B.BKZ()
shortest_vector = new_B_BKZ[0]
mbar = (B*2).solve_left(new_c - shortest_vector[:-1])
m = mbar * (2*delta) + m6

print(bytes.fromhex(hex(m)[2:]))

# Sage
# e=mW+r
from sage.modules.free_module_integer import IntegerLattice

W = 
e = 

B = W.stack(e).augment(vector([0] * W.ncols() + [1]))
r = IntegerLattice(B).shortest_vector()
print('r = {}'.format(r))

m = W.solve_left(e - r[:-1])
print('m = {}'.format(m))

参考

GGH encryption scheme

GYCTF 2020 - GGH

LWE问题

容错学习问题（LWE问题， Learning With Errors）是一个机器学习领域中的怀疑难解问题，由Oded Regev 在2005年提出，他因此赢得2018年哥德尔奖。这是一个极性学习问题的一般形式。

定义

随机选取一个矩阵 $\mathbf{A} \in \mathbb{Z}_q^{m \times n}$ ，一个随机向量 $\mathbf{s} \in \mathbb{Z}_q^n$ ，和一个随机的噪音 $\mathbf{e} \in \varepsilon^m$ 。

一个LWE系统的输出 $g_\mathbf{A}(\mathbf{s, e}) = \mathbf{As + e} \pmod q$ 。

一个LWE问题是，给定一个矩阵 $\mathbf{A}$ ，和LWE系统的输出 $g_\mathbf{A}(\mathbf{s, e})$ ，还原 $\mathbf{s}$ 。

LWE的误差向量是一个满足正态分布的小向量。

因为加入了一些误差，如果使用高斯消元法的话，这些误差会聚集起来，使得解出来的东西跟实际值差很多。

求解

构造矩阵：

$L = \begin{bmatrix} I & A \newline 0 & b \end{bmatrix}$

利用LLL算法和Babai最近平面算法，可以在多项式时间内找到SVP近似解。

#脚本1-小规模
#Sage
from sage.modules.free_module_integer import IntegerLattice

row = 
column = 
prime = 

ma = 
res = 

W = matrix(ZZ, ma)
cc = vector(ZZ, res)

# Babai's Nearest Plane algorithm
def Babai_closest_vector(M, G, target):
    small = target
    for _ in range(5):
        for i in reversed(range(M.nrows())):
            c = ((small * G[i]) / (G[i] * G[i])).round()
            small -=  M[i] * c
    return target - small

A1 = matrix.identity(column)
Ap = matrix.identity(row) * prime
B = block_matrix([[Ap], [W]])  
lattice = IntegerLattice(B, lll_reduce=True)
print("LLL done")
gram = lattice.reduced_basis.gram_schmidt()[0]
target = vector(ZZ, res)
re = Babai_closest_vector(lattice.reduced_basis, gram, target)
print("Closest Vector: {}".format(re))

R = IntegerModRing(prime)
M = Matrix(R, ma)
M = M.transpose()

ingredients = M.solve_right(re)
print("Ingredients: {}".format(ingredients))

m = ''
for i in range(len(ingredients)):
    m += chr(ingredients[i])
print(m)

#脚本2-大规模
#Sage
from sage.modules.free_module_integer import IntegerLattice
from random import randint
import sys
from itertools import starmap
from operator import mul

# Babai's Nearest Plane algorithm
# from: http://mslc.ctf.su/wp/plaidctf-2016-sexec-crypto-300/
def Babai_closest_vector(M, G, target):
    small = target
    for _ in range(1):
        for i in reversed(range(M.nrows())):
            c = ((small * G[i]) / (G[i] * G[i])).round()
            small -= M[i] * c
    return target - small

m = 
n = 
q = 

A_values = 
b_values = 

A = matrix(ZZ, m + n, m)
for i in range(m):
    A[i, i] = q
for x in range(m):
    for y in range(n):
        A[m + y, x] = A_values[x][y]
lattice = IntegerLattice(A, lll_reduce=True)
print("LLL done")
gram = lattice.reduced_basis.gram_schmidt()[0]
target = vector(ZZ, b_values)
res = Babai_closest_vector(lattice.reduced_basis, gram, target)
print("Closest Vector: {}".format(res))

R = IntegerModRing(q)
M = Matrix(R, A_values)
ingredients = M.solve_right(res)

print("Ingredients: {}".format(ingredients))

for row, b in zip(A_values, b_values):
    effect = sum(starmap(mul, zip(map(int, ingredients), row))) % q
    assert(abs(b - effect) < 2 ** 37)

print("ok")

利用Embedding Technique构造一个Embedding Lattice，也可以解SVP。

# Sage
DEBUG = False
m = 44
n = 55
p = 2^5
q = 2^10

def errorV():
  return vector(ZZ, [1 - randrange(3) for _ in range(n)])

def vecM():
  return vector(ZZ, [p//2 - randrange(p) for _ in range(m)])

def vecN():
  return vector(ZZ, [p//2 - randrange(p) for _ in range(n)])

def matrixMn():
  mt = matrix(ZZ, [[q//2 - randrange(q) for _ in range(n)] for _ in range(m)])
  return mt

A = matrixMn()
e = errorV()
x = vecM()
b = x*A+e

if DEBUG:
  print('A = \n%s' % A)
  print('x = %s' % x)
  print('b = %s' % b)
print('e = %s' % e)

z = matrix(ZZ, [0 for _ in range(m)]).transpose()
beta = matrix(ZZ, [1])
T = block_matrix([[A, z], [matrix(b), beta]])
if DEBUG:
  print('T = \n%s' % T)

print('-----')
L = T.LLL()
print(L[0])
print(L[0][:n] == e)

# Sage
import re
s2n=lambda x: [int(x) for x in re.findall(r"\-?\d+\.?\d*",x)]
f=open("./enc.out","r").readlines()
m = 66
n = 200
p = 5
q = 2^20
B = [s2n(f[i]) for i in range(m)]
A = [s2n(f[i+66]) for i in range(m)]
C = [s2n(f[i+132]) for i in range(m)]
b= list(matrix(ZZ,s2n(f[-1])))
m=A+B+C+b
M = matrix(ZZ,m)
L = M.LLL()
print(L[0])
res=M.solve_left(L[0])
for i in res[:-1]:
    print(chr(abs(i)),end="")

参考

初探全同态加密之二：格密码学与LWE问题

祥云杯 2020 - easy matrix

Aero CTF 2020 - Magic II

XNUCA2020 - diamond

2022 DASCTF 7月赋能赛 - LWE?

环LWE（RLWE）

环LWE问题是LWE问题在环上的版本，不同的是 $A$ 和 $s$ 的选取是在多项式环。

多项式环 $R_q = \mathbb{Z_q}[x]/f(x)$ ，表示每次计算后都要对多项式系数模 $q$ ，对多项式模 $f(x)$ 。它其中的每个元素都是一个多项式，每一次操作都相当于对多个元素进行操作，也就是能够一次加密多个比特的明文，对比LWE每次仅能对一个比特操作来说能够大大提高效率满足实际需要。

对于 $B=AS+E$ ，给出 $A,B$ ， $E$ 是随机生成一个小噪声多项式， $S$ 的系数在模 $p$ 下很小，要求还原 $S$ 。

假设多项式 $a$ 和多项式 $b$ 模多项式 $v$ ，要计算得到的多项式 $c$ ，其中 $v$ 是 $n$ 次。

记多项式为：

$a = (a_0,a_1,a_2,a_3,…a_{n-1})$

$b = (b_0,b_1,b_2,b_3,…b_{n-1})$

$v = (v_0,v_1,v_2,v_3,…v_{n-1},1)$ （默认首一多项式）

$c = (c_0,c_1,c_2,c_3,…c_{n-1})$

将将商环下的多项式乘法拆分成两步，并分别用矩阵乘法表示：

$a$ 和 $b$ 相乘，得到 $d$
$d$ 模 $v$ ，得到 $c$

然后将两步矩阵相乘，就得到最终矩阵——商环下多项式乘法的表示矩阵。

其中 $d$ 是一个最高次项可以达到 $2n-2$ 次的一个多项式，因此可以写作：

$d = (d_0,d_1,d_2,d_3,…d_{n-1},d_n,…,d_{2n-2})$

$a$ 和 $b$ 相乘，得到 $d$ 

将所有能得到这个次数的系数乘积求和即可。

$(a_0,a_1,a_2,…a_{n-1})_{1\times n} \left( \begin{matrix} b_0 &b_1 &b_2 &\cdots &b_{n-1}&&\\ &b_0 &b_1 &\cdots &b_{n-2}&b_{n-1}&\\ &&b_0 &\cdots &b_{n-3}&b_{n-2}&b_{n-1}\\ &&&\ddots &\vdots&\vdots&\vdots&\ddots\\ &&&&b_0&b_1&b_2&\cdots&b_{n-1}\\ \end{matrix} \right) _{n\times (2n-1)} = (d_0,d_1,d_2,d_3,…d_{n-1},d_n,…,d_{2n-2})_{1\times (2n-1)}$

$d$ 模 $v$ ，得到 $c$

首先对于 $d$ 中前 $n$ 项来说（ $0$ 到 $n-1$ 次项），很容易表示最终的向量 $c$ ，由于次数低，不需要模多项式，所以只需要将对应数值加到 $c$ 中对应项中就可以，也就是造一个单位矩阵即可。而较难处理的是 $d$ 中超过了 $n-1$ 次的项，因为要进行模 $v$ 的操作。

构造模多项式中的同余方程：

$x^{n} = -(v_{n-1}x^{n-1}+v_{n-2}x^{n-2}+…+v_{2}x^{2}+v_{1}x^{1}+v_0) \bmod v$

也就有：

$x^{n+i} = -(v_{n-1}x^{n-1+i}+v_{n-2}x^{n-2+i}+…+v_{2}x^{2+i}+v_{1}x^{1+i}+v_0x^i) \bmod v$

而又因为 $d$ 中最高也就只有 $2n-2$ 次项，所以 $i \in \{0,1,2,…,n-3,n-2\}$ 。

由于高次项会存在多次使用同余方程降次，因此需要从 $i=0$ 开始，逐步将 $x^{n+i}$ 均转化成一个次数在 $0$ 到 $n-1$ 的多项式并求出系数，加到最终多项式 $c$ 的对应项的系数中。

$i=0$ 时，直接利用前面的同余方程就可以得到每个次数的项前需要加的系数：

$x^{n} = -(v_{n-1}x^{n-1}+v_{n-2}x^{n-2}+…+v_{2}x^{2}+v_{1}x^{1}+v_0) \bmod v$

而 $i=1$ 时，右侧的同余方程又会出现需要降次的 $x^n$ 次方项，如下：

$x^{n+1} = -(v_{n-1}{\color{red}{x^{n}}}+v_{n-2}x^{n-1}+…+v_{2}x^{3}+v_{1}x^{2}+v_0x) \bmod v$

把刚才求过的 $n$ 次项降次后得到的系数代入，有：

$x^{n+1} = -(v_{n-1}{\color{red}{(-(v_{n-1}x^{n-1}+v_{n-2}x^{n-2}+…+v_{2}x^{2}+v_{1}x^{1}+v_0)}}+v_{n-2}x^{n-1}+…+v_{2}x^{3}+v_{1}x^{2}+v_0x) \bmod v$

然后展开运算出各项系数即可。

以此类推，代入已经算出的式子并展开计算，一直迭代到：

$x^{n+n-2} = -(v_{n-1}{\color{red}{x^{n+n-3}}}+v_{n-2}{\color{red}{x^{n+n-4}}}+…+v_{2}{\color{red}{x^{n}}}+v_{1}x^{n-1}+v_0x^{n-2}) \bmod v$

而要构造矩阵，只需要将 $d$ 中的大于等于 $n$ 次方的每一项系数乘以刚才对应展开形式中的对应项系数，就可以得到矩阵中对应的行，然后接在单位矩阵下即可。这一步的矩阵为：

$\left( \begin{matrix} 1\\ &1\\ &&1\\ &&&\ddots\\ &&&&1\\ r_0&r_1&r_2&\cdots&r_{n-1}\\ s_0&s_1&s_2&\cdots&s_{n-1}\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ t_0&t_1&t_2&\cdots&t_{n-1}\\ \end{matrix} \right) _{(2n-1)\times n}$

对这一步的矩阵有：

$(d_0,d_1,d_2,d_3,…d_{n-1},d_n,…,d_{2n-2})_{1\times (2n-1)} \left( \begin{matrix} 1\\ &1\\ &&1\\ &&&\ddots\\ &&&&1\\ r_0&r_1&r_2&\cdots&r_{n-1}\\ s_0&s_1&s_2&\cdots&s_{n-1}\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ t_0&t_1&t_2&\cdots&t_{n-1}\\ \end{matrix} \right) _{(2n-1)\times n} = (c_0,c_1,c_2,c_3,…c_{n-1})_{1\times n}$

综合表示

将两个矩阵相乘，得到一般意义下的多项式乘法卷积矩阵：

$L = \left( \begin{matrix} b_0 &b_1 &b_2 &\cdots &b_{n-1}&&\\ &b_0 &b_1 &\cdots &b_{n-2}&b_{n-1}&\\ &&b_0 &\cdots &b_{n-3}&b_{n-2}&b_{n-1}\\ &&&\ddots &\vdots&\vdots&\vdots&\ddots\\ &&&&b_0&b_1&b_2&\cdots&b_{n-1}\\ \end{matrix} \right) _{n\times (2n-1)} \left( \begin{matrix} 1\\ &1\\ &&1\\ &&&\ddots\\ &&&&1\\ r_0&r_1&r_2&\cdots&r_{n-1}\\ s_0&s_1&s_2&\cdots&s_{n-1}\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ t_0&t_1&t_2&\cdots&t_{n-1}\\ \end{matrix} \right) _{(2n-1)\times n}$

此时有：

$(a_0,a_1,a_2,…a_{n-1})L= (c_0,c_1,c_2,c_3,…c_{n-1})$

对 $L$ 规约即可得到需要的向量。

参考：

NSSRound#18 - New Year Ring1/2/3

隐藏数问题（HNP / Hidden Number Problem）

由DSA签名中各参数的关系：

$r \equiv g^k \pmod q$

$s \equiv k^{-1}(H(m)+xr) \equiv q$

可得每轮临时密钥与签名、明文的关系：

$k_i \equiv s_i^{-1}r_i \cdot x+s_i^{-1}H(m) \pmod q$

$k_i \equiv A_ix+B_i \pmod q$

$k_i = A_ix+B_i+l_iq$

其中 $k_i$ 就是每次使用的临时密钥， $A_i = s_i^{-1}r,B_i = s_i^{-1}H(m)$ 。

构建格：

$M = \begin{bmatrix} q & & & & & & \newline & q & & & & & \newline & &\ddots& & & & \newline & & & q & & & \newline A_1&A_2&\dots & A_t&K/q& & \newline B_1&B_2&\dots & B_t& & K & \newline \end{bmatrix}$

（其中 $K$ 是 $k$ 的上界，例如 $k$ 的位数小于等于121时，那么 $K=2^{122}$ ）

不难发现，存在一个 $M$ 的整系数线性组合 $v$ ，可以得到我们想要的 $v_k$ 。

$vM = \begin{bmatrix} l_1 & l_2 & \cdots & l_t & x & 1 \end{bmatrix} \begin{bmatrix} q & & & & & & \newline & q & & & & & \newline & &\ddots& & & & \newline & & & q & & & \newline A_1&A_2&\dots & A_t&K/q& & \newline B_1&B_2&\dots & B_t& & K & \newline \end{bmatrix} = \begin{bmatrix} k_1 & k_2 & \cdots & k_t & Kx/q & K \end{bmatrix} = v_k$

因此 $v_k$ 即为 $M$ 上的一个格点，且长度很短，可以用LLL算法求出。

注：有另一个短向量 $v=(0,0,⋯,K,0)$ 也在格上，且这个短向量比 $(k_1, k_2, \cdots, k_t, Kx/n, K)$ 还要短。此外，多次测试发现， $v_k$ 总会出现在LLL后的第二行。

import json

t = 40

# Load data
f = open("data", "r")
(q, Hm_s, r_s, s_s) = json.load(f)

# Calculate A & B
A = []
B = []
for r, s, Hm in zip(r_s, s_s, Hm_s):
    A.append( ZZ( (inverse_mod(s, q)*r) % q ) )
    B.append( ZZ( (inverse_mod(s, q)*Hm) % q ) )

# Construct Lattice
K = 2^122   # ki < 2^122
X = q * identity_matrix(QQ, t) # t * t
Z = matrix(QQ, [0] * t + [K/q] + [0]).transpose() # t+1 column
Z2 = matrix(QQ, [0] * (t+1) + [K]).transpose()    # t+2 column

Y = block_matrix([[X],[matrix(QQ, A)], [matrix(QQ, B)]]) # (t+2) * t
Y = block_matrix([[Y, Z, Z2]])

# Find short vector
Y = Y.LLL()

# check
k0 = ZZ(Y[1, 0] % q)
x = ZZ(Y[1, -2] / (K/q) % q)
assert(k0 == (A[0]*x + B[0]) % q)
print(x)

参考

The Dark Side of the Hidden Number Problem: Lattice Attacks on DSA

[HNP] 一类基于各种DSA的HNP问题求解

NPUCTF 2020 - babyLCG

RCTF 2022 - IS_THIS_LCG

隐子集和问题（HSSP / Hidden Subset Sum Problem）

$w=vG$ ，其中 $w,v$ 为 $\text{GF}(p)$ 上的向量， $G$ 为01矩阵（ $g_{ij} \in \{ 0,1 \}$ ），已知 $w$ ，恢复矩阵 $G$ 。

求解算法 Nguyen-Stern Algorithm，使用 orthogonal lattice 实现。

参考：

HSSP与正交格学习笔记

格密码分析：正交格攻击

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

AIS3 EOF CTF Quals 2021 - notPRNG

Zer0pts CTF 2022 - Karen

solving_hssp

from Crypto.Util.number import *

n = 60
m = 330
p = ...
w = ...
MM = ...

e = 0x10001
MM = matrix(GF(2), MM)

def allpmones(v):
    return len([vj for vj in v if vj in [-1, 0, 1]]) == len(v)

# We generate the lattice of vectors orthogonal to b modulo x0
def orthoLattice(b, x0):
    m = b.length()
    M = Matrix(ZZ, m, m)

    for i in range(1, m):
        M[i, i] = 1
    M[1:m, 0] = -b[1:m] * inverse_mod(b[0], x0)
    M[0, 0] = x0

    for i in range(1, m):
        M[i, 0] = mod(M[i, 0], x0)

    return M

def allones(v):
    if len([vj for vj in v if vj in [0, 1]]) == len(v):
        return v
    if len([vj for vj in v if vj in [0, -1]]) == len(v):
        return -v
    return None

def recoverBinary(M5):
    lv = [allones(vi) for vi in M5 if allones(vi)]
    n = M5.nrows()
    for v in lv:
        for i in range(n):
            nv = allones(M5[i] - v)
            if nv and nv not in lv:
                lv.append(nv)
            nv = allones(M5[i] + v)
            if nv and nv not in lv:
                lv.append(nv)
    return Matrix(lv)

def kernelLLL(M):
    n = M.nrows()
    m = M.ncols()
    if m < 2 * n:
        return M.right_kernel().matrix()
    K = 2 ^ (m // 2) * M.height()

    MB = Matrix(ZZ, m + n, m)
    MB[:n] = K * M
    MB[n:] = identity_matrix(m)

    MB2 = MB.T.LLL().T

    assert MB2[:n, : m - n] == 0
    Ke = MB2[n:, : m - n].T

    return Ke

def attack(m, n, p, h):
    # This is the Nguyen-Stern attack, based on BKZ in the second step
    print("n =", n, "m =", m)

    iota = 0.035
    nx0 = int(2 * iota * n ^ 2 + n * log(n, 2))
    print("nx0 =", nx0)

    x0 = p
    b = vector(h)

    # only information we get
    M = orthoLattice(b, x0)

    t = cputime()
    M2 = M.LLL()
    print("LLL step1: %.1f" % cputime(t))

    # assert sum([vi == 0 and 1 or 0 for vi in M2 * X]) == m - n
    MOrtho = M2[: m - n]

    print("  log(Height, 2) = ", int(log(MOrtho.height(), 2)))

    t2 = cputime()
    ke = kernelLLL(MOrtho)

    print("  Kernel: %.1f" % cputime(t2))
    print("  Total step1: %.1f" % cputime(t))

    if n > 170:
        return

    beta = 2
    tbk = cputime()
    while beta < n:
        if beta == 2:
            M5 = ke.LLL()
        else:
            M5 = M5.BKZ(block_size=beta)

        # we break when we only get vectors with {-1,0,1} components
        if len([True for v in M5 if allpmones(v)]) == n:
            break

        if beta == 2:
            beta = 10
        else:
            beta += 10

    print("BKZ beta=%d: %.1f" % (beta, cputime(tbk)))
    t2 = cputime()
    MB = recoverBinary(M5)
    print("  Recovery: %.1f" % cputime(t2))
    print("  Number of recovered vector = ", MB.nrows())
    print("  Number of recovered vector.T = ", MB.ncols())
    return MB

res = attack(m, n, p, w)

隐线性组合问题（HLCP / Hidden Linear Combination Problem）

$w=vG$ ，其中 $w,v$ 为 $\text{GF}(p)$ 上的向量， $G$ 为 $0$ 至 $B$ 之间整数值矩阵（ $g_{ij} \in [0,B] \cap\mathbb{Z}$ ），已知 $w$ ，恢复矩阵 $G$ 。

参考：

Provably Solving the Hidden Subset Sum Problem via Statistical Learning

2022强网杯 - Lattice

solving_hssp

方程问题

$aX \equiv b \pmod p$
$X$ 是大的数， $a$ 和 $b$ 是小的数，可写成 $aX+kp=b$ 或 $aX-kp=b$ ，已知 $X$ 和 $p$ ，求 $a$ 和 $b$ 。
Wiener’s
$\Big\vert \cfrac{X}{p}-\cfrac{k}{a} \Big\vert \le \cfrac{1}{2a^2}$
用连分数方法，用 $\cfrac{X}{p}$ 求出 $k$ 和 $a$ ，进而解出 $b$ 。
Lattices
构造 $(a,k) \begin{bmatrix} 1 & X \newline 0 & p\end{bmatrix} = (a,b)$ ，记为 $A\cdot M=B$ 。
$B$ 有很大概率为 $M$ 里的最短向量，使用LLL算法reduce后可求出最短向量，即解出 $B=(a, b)$ 。
$a_iX_i \equiv B \pmod p$
$B$ 是未知大数， $X$ 是大的数， $a$ 是小的数，已知 $X$ 和 $p$ ，求 $a$ 和 $B$ 。如果有多组这样的式子，可以转化成 $aX \equiv b \pmod p$ 的情况。
转化为 $a_iB^{-1} \equiv X_i^{-1} \pmod p$ ，消去未知数 $B$ ，有：
$a’=X_1B^{-1} \bmod p = a_1 \bmod p$
$b’=X_2B^{-1} \bmod p = a_2 \bmod p$
$X’=X_1^{-1}X_2 \bmod p = a_1^{-1}a_2 \bmod p$
即 $a’X’ \equiv b’ \pmod p$ ，对应 $a_iB^{-1} \equiv X_i^{-1} \pmod p$ 求解。
$\sum\limits_{i=1}^n a_iX_i \equiv b \pmod p$
构造 $(a_1,a_2,\cdots,a_n,k)\begin{pmatrix} 1 & 0 & \cdots & 0 & X_1 \newline 0 & 1 & \cdots & 0 & X_2 \newline \vdots & \vdots & \ddots & \vdots & \vdots \newline 0 & 0 & \cdots & 1 & X_n \newline 0 & 0 & \cdots & 0 & p \end{pmatrix}=(a_1,a_2,\cdots,a_n,b)$ ，记为 $A\cdot M=B$ 。
只要有 $a=\max(a_i) \le O(p^{\frac{1}{n+1}})$ 就可解 $a_i$ 。
$\sum\limits_{i=1}^n a_iX_i \equiv Y \pmod p$
$Y$ 是已知大数，背包密码解法。
构造 $(a_1,a_2,\cdots,a_n,k,-1)\begin{pmatrix} 1 & 0 & 0 & \cdots & 0 & 0 & X_1 \newline 0 & 1 & 0 & \cdots & 0 & 0 & X_2 \newline \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \newline 0 & 0 & 0 & \cdots & 1 & 0 & X_n \newline 0 & 0 & 0 & \cdots & 0 & 1& p \newline 1 & 1 & 1 & \cdots & 1 & 1& Y\end{pmatrix}=(a_1-1,a_2-1,\cdots,a_n-1,k-1,0)$ ，记为 $A\cdot M=B$ 。
注意到 $B$ 的最后一个元素是0，所以如果 $M$ 的最后一列和 $B$ 的最后一个元素同乘一个超大的 $C$ 的话（即 $M$ 和 $B$ 同乘一个对角阵 $D$ ， $D$ 的对角线上的最右下一个是 $C$ ，其他是1）， $\det(M)$ 会变大，而 $B$ 则不变。所以如果 $C$ 足够大的话，即可解 $a_i$ 。
$a_iX_i \equiv b_i \pmod {P+s}$
假设原来的 $p$ 可以拆成 $P+s$ ， $P$ 已知， $s$ 未知但一定会存在。如RSA中， $\varphi(N)$ 并不知道，但会知道 $N=\varphi(N)+[1-(p+q)]$ ，用类似扩展维纳攻击的方法可以用 $P+s$ 代替 $P$ ，然后用格的方法做，但需要的 $a$ 和 $b$ 要更小。
对于两组情况：
$\begin{cases} a_1X_1 \equiv b_1 \pmod {P+s} \newline a_2X_2 \equiv b_2 \pmod {P+s}\end{cases}$
构造 $(k_1k_2,a_1k_2,a_2k_1,a_1a_2)\begin{pmatrix} 1 & P & 0 & P^2 \newline 0 & X_1 & X_1 & X_1P \newline 0 & 0 & -X_2 & X_2P \newline 0 & 0 & 0 & X_1X_2 \end{pmatrix}=(k_1k_2,k_2(b_1-sk_2),b_1k_2-b_2k_1,(b_1-k_1s)(b_2-k_2s))$ ，记为 $A\cdot M=B$ 。
$x_i=q_ip+r_i$
$x_i$ 已知， $p$ 为 $\alpha$ 位， $q_i$ 为 $\beta$ 位， $r_i$ 为 $\rho$ 位（ $\rho \lt\lt \alpha$ ），求 $p$ 。
ACD问题（Approximate Common Divisior Problem）。
构造 $(q_0,q_1,\cdots,q_t)\begin{pmatrix} 2^{\rho} & x_1 & x_2 & \cdots & x_t \newline 0 & -x_0 & 0 & \cdots & 0 \newline 0 & 0 & -x_0 & \cdots & 0 \newline \vdots & \vdots & \vdots & \ddots & \vdots \newline 0 & 0 & 0 & \cdots & -x_0\end{pmatrix}=(q_02^{\rho},q_0x_1-q_1x_0,\cdots,q_0x_t-q_tx_0)=(q_02^{\rho},q_0r_1-q_1r_0,\cdots,q_0r_t-q_tr_0)$ ，记为 $A\cdot M=B$ 。
使用LLL算法reduce后得到 $q_02^{\rho}$ 。
参考：
WMCTF 2021 - easylsb

参考：Wiener’s v.s Lattices —— aX=b%p 的方程解法笔记

Lazzaro

CTF弱鸡自进阶

格密码

格密码