格密码专题学习

最近发现每次做格的题都一知半解格不出来，因此决定从零开始系统学习一下格。

一、定义

• 基： 在n维空间中给定的n个线性无关向量：$\vec{b_1},\vec{b_2},…,\vec{b_n}$。

• 格： 对于n维空间中的基，存在线性组合$x_1\vec{b_1}+x_2\vec{b_2}+…+x_n\vec{b_n}$,其中整系数的线性组合构成的集合成为格，即$x_i\in \mathbb{Z}$，记为

$$ \mathcal{L}(B)=\{x_1\vec{b_1}+x_2\vec{b_2}+...+x_n\vec{b_n},x_i\in\mathbb{Z}\} $$

不同的基可能产生同样的格

二、理论知识点

格的等价交换

• 向量交换： 即$\vec{b_i}\longleftrightarrow\vec{b_j}$

• 向量取反： 即$\vec{b_i}\longleftrightarrow-\vec{b_i}$

• 整系数线性组合： 即$\vec{b_i}\longleftrightarrow\vec{b_i}+k\vec{b_j}$

  不同格基产生相同格的条件： 两个格基矩阵$B_1,B_2$ ,若$B_2=B_1U$，（U是幺模矩阵，即行列式的值为±1的矩阵），则两组格基产生的格相同。

格的基本区域

• 定义： 格基组成的最小重复单元。

行列式

• 再次认识不同格基产生相同格的条件： 行列式的值相同。

• 行列式越小，格点密度越大。

延展空间

• 定义： 格$\mathcal{L}(B)$中基的所有线性组合所形成的集合为这组基向量所张成的延展空间。

  即$span(\mathcal{L}(B))=span(B)={a_1\vec{b_1}+a_2\vec{b_2}+…+a_n\vec{b_n}|a_i\in\mathbb{R}}$

范数

• $l_1$范数：

$\|x\|_1=\sum^n_{i=1}|x_i|$

• $l_2$范数：

$\|x\|_2=\sqrt{ \sum^n_{i=1}x_i^2}$（欧几里得范数）

• $l_{\infty}$范数：
  $|x|_{\infty}=max|x_i|$

Successive Minima（连续极小）

• 定义： 在$秩为n的格\mathcal{L}中，第i个连续极小值（i=1,2,…,n），$

$$ \lambda_i=inf\{r|dim(span(\mathcal{L}\cap\mathcal{B}(0,r)))\ge i\} $$

其中$\lambda_1$是最短非零向量。$inf$指下界。$\mathcal{B}(0,r)$是在零点，半径为$r$的超球体。

• 重点： $\lambda _1$是格$\mathcal{L}$中的最短非零向量的长度

施密特正交化

正交化过程：

• 给定一组线性无关向量$b_1,b_2,…,b_n$

• 目标计算得到一组正交基$\tilde b_1,\tilde b_2,…,\tilde b_n$

• $<b_i,b_j>$表示$b_i$和$b_j$的内积

• 令$\mu_{i,j}=\frac{<b_i,b_j>}{<b_j,b_j>}$

• 正交化后的向量表示为

$$ \begin{cases} \tilde b_1=b_1 \\ \tilde b_2=\mu_{2,1}\tilde b_1 \\ \vdots \\ \tilde b_i=\sum^{i-1}_{j=1}\mu_{i,j}\tilde b_{j} \end{cases} $$

注意： 施密特正交化没有限制系数为整数，因此正交化的结果不能直接应用于格基。

QR分解

• 定义： 将一个矩阵分解为一个正交矩阵Q和一个上三角矩阵R的乘积，即 A=QR。

• 引入： 对施密特正交化之后的向量进行取整，得到近似正交基$\tilde b_1,\tilde b_2,…,\tilde b_n$

• 矩阵形式表示：

$$ \begin{bmatrix} \|\tilde b_1\| & \mu_{2,1}\|\tilde b_1 \| & \cdots & \mu_{n,1}\|\tilde b_1\| \\ 0 & \|\tilde b_2\| & \cdots & \mu_{n,2}\| b_2\| \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \|\tilde b_n\| \end{bmatrix} $$

• 结论：

  • $det(B)=\Pi^n_{i=1}|\tilde b_i|$

  • 可以得到$\lambda_1$的下界，即$\lambda_1 \ge min(|\tilde b_i)|$

• 不懂，留坑

Hermite定理（赫米特定理）

• 目的： 求$\lambda_1$的上界

• 内容： 对于$n$维格$\mathcal{L}$，都有一个非零向量$\vec{v}\in \mathcal{L}$，满足$|\vec{v}|\le\sqrt{n}det(\mathcal{L})^{\frac{1}{n}}$

高斯启发式

• 引入： 对Hermite定理的进一步缩小。

• 内容： 对于$n$维格$\mathcal{L}$，高斯期望的长度为

$$ \sigma(\mathcal{L})=\sqrt{\frac{n}{2\pi e}}det(\mathcal{L})^{\frac{1}{n}} $$

• 结论： 在”随机选择的格“中最短向量满足$|\vec{v}|\approx\sigma(\mathcal{L})$

三、三大问题

SVP问题（最短向量问题）

• 寻找一个随机格$L$中的最短非零向量，即寻找一个$v\in L$满足$|v|$最小。

CVP问题（最近向量问题）

• 在格$L$中，已知一个不在格点上的向量$w$，寻找一个向量$v\in L$，使得$|w-v|$最小。

SIVP问题（最短独立向量问题）

• 在格$L$中，寻找$n$个线性独立的向量$Bx_1,Bx_2,…,Bx_n$，并且这些向量的长度都小于等于最长的最短向量$\lambda_n$

$$ max\|Bx_i\| \le \lambda_n $$

四、格攻击应用

格基规约算法（LLL,BKZ）

高斯算法

• 简介： 一种原始的二维格基规约算法。

• 概念

  • 最小基： 设$x,y$是二维格$L$中的一组基。若$x,y$满足$|x|=\lambda_1$(后文均用$|x|$表示向量长度)，且$y$ 与$x$线性无关，则$x,y$为最小基（也称Minkowski约化基） 。

  • 取整： 记$[\mu]为距\mu最近的整数$。$规定对于整数n，[n+\frac{1}{2}]的值取n。$

• 算法步骤：

  • 输入： $二维格L的一组基x,y，其中|x|<|y|$

  • 输出： $格L中的一组最小基v_1,v_2$

  • 代码：

    #sage
    def Gauss(x,y):
        v1,v2=x,y
        finished = False
        while not finished:
            m=round((v2.dot_product(v1)/v1.dot_product(v1)))
            v2 = v2 - m*v1
            if v1.norm() <= v2.norm():
                finished = True
            else
                v1,v2 = v2,v1
        return v1,v2

LLL算法

• 简介： LLL算法可视为高斯算法在高维格中的推广。

• 效果： 使施密特正交化的程度最大化，以求解最短向量问题

• 算法步骤：

  • 输入： $n维格的任意一组基$。

  • 输出： 以多项式时间输出一组LLL约化基。

  • 代码：

    #sage
    max(a, b):
        return a if a > b else b
    
    def LLL_v0(M, delta=0.75):
        B = deepcopy(M)
        Q, mu = B.gram_schmidt()
        n, k = B.nrows(), 1
    
        while k < n:
    
            # size reduction step
            for j in reversed(range(k)):
                if abs( mu[k][j] ) > 0.5:
                    B[k] = B[k] - round( mu[k][j] ) * B[j]
                    Q, mu = B.gram_schmidt()
    
            # swap step 
            if Q[k].dot_product(Q[k]) >= (delta - mu[k][k-1]^2) * Q[k-1].dot_product(Q[k-1]):
                k = k + 1
            else:
                B[k], B[k-1] = B[k-1], B[k]
                Q, mu = B.gram_schmidt()
                k = max(k-1,1)
    
        return B

BKZ算法

• 简介： 约化能力比LLL算法更强，使用了KZ约化和深插法。

$L^2$ 算法

• 简介： 浮点型LLL算法，采用浮点数和大数运算算法优化运行时间，并使用deepinsertion提升约化能力。

BKZ 2.0

• 简介： BKZ的优化版本

五、配平

• 为什么要配平： 因为利用格基规约解决的其实是最短向量问题，而一些情况下直接构造的格不满足$|v|\le\sqrt n der(L)^{\frac1 n}$ ，也就是说想要求的向量在构造的格中不是最短向量。因此需要通过配平来使其达到最短。

• 例子：

  • 已知$h=f^{-1}g \mod p$,其中给出$(h,p)$，求$(f,g)$ ,$f$为128bits$g$为64bits,$p$为250bits。

  • 构造格

$$ \begin{bmatrix} f & k \end{bmatrix} \begin{bmatrix} 1 & h \\ 0 & p \end{bmatrix} = \begin{bmatrix} f & g \end{bmatrix} $$

• 即$vB=w$，其中$w$就是我们想要求的向量，要保证它满足是最短向量，而实际

$$ \|w\|\approx2^{128} \\ \sqrt{2p}\approx2^{125} $$

而上边显然不满足，因此需要调整。令$D=2^{10}$

$$ \begin{bmatrix} f & k \end{bmatrix} \begin{bmatrix} 1 & Dh \\ 0 & Dp \end{bmatrix} = \begin{bmatrix} f & Dg \end{bmatrix} $$

• 此时

$$ \|w'\|\approx2^{128}\le\sqrt{2Dp}\approx2^{130} $$

• 此时便能解出$w’$，求g时还需再除以D。

六、典型题型

1.Wiener攻击

• 代码：

  D = 2^(n.nbits()//2)
  m = matrix(ZZ, [
    [D, n+1],
    [0, -e]
  ])
  L = m.LLL()
  w = L[0]
  v = m.solve_left(w)
  k = abs(v[0])
  d = abs(v[1])
  phi = (e*d-1) // k
  p_plus_q = n + 1 - phi
  p_min_q = (p_plus_q^2 - 4*n)^(1/2)
  p = (p_plus_q + p_min_q) // 2
  q = n // p
  assert p*q == n
  
  print('p = %s' % p)
  print('q = %s' % q)
  print('d = %s' % d)

• 攻击条件：$d<\frac13N^{\frac14}$

2.01背包密码(Knapsack)

• 构造：

$$ (x_0,x_1,...,x_{n-1},-1) \begin{bmatrix} 2 & 0 & 0 & \cdots & 0 & M_0 \\ 0 & 2 & 0 & \cdots & 0 & M_1 \\ 0 & 0 & 2 & \cdots & 0 & M_2 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 2 & M_{n-1} \\ 1 & 1 & 1 & \cdots & 1 & S \end{bmatrix} \\ =(2x_0-1,2x_1-1,...2x_{n-1}-1,0) $$

PS：需要配平时在最后一列加上系数。

• 代码：

  from secret import flag
  from random import getrandbits
  import libnum
  BITS = 1024
  fb = bin(libnum.s2n(flag))[2:].zfill(8*len(flag))
  fb = [int(i) for i in fb]
  
  M = [getrandbits(BITS) for i in range(len(fb))]
  S = sum([fb[i]*M[i] for i in range(len(fb))])
  
  print('M = %s' % M)
  print('S = %s' % S)

  with open('./out', 'r') as f:
    exec(f.read())
  n = len(M)
  
  B = zero_matrix(ZZ, n+1)
  for i in range(n):
    B[i, i] = 2
    B[-1, i] = 1
    B[i, -1] = M[i]
  B[-1, -1] = S
  L =B.LLL()
  print(L[0]) # 理论上只含(-1, 0, 1)且只有最后一位是0，否则是没解出
  
  import libnum
  fb = ''.join([str((li+1)//2) for li in L[0][:-1]])
  flag = libnum.n2s(int(fb, 2))
  print(flag) # 若解出 2 xi - 1
  
  fb = ''.join([str((li+1)//2) for li in -L[0][:-1]])
  flag = libnum.n2s(int(fb, 2))
  print(flag) # 若解出 1 - 2 xi

• 见另一篇文章

3.HSSP(隐子集和问题)

• 概述： $w=vG,其中w,v均为GF(p)上的向量，G是01矩阵，已知w，恢复矩阵G$

• 代码：

  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 andnv 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)

• 详细见另一篇文章

4.LWE（容错学习问题）

• 概述： $Ax+e=b\mod q$，已知$A,b,q$，未知$e$（很小），求$x$。

其中$A$是$m*n$矩阵，$x$是$n$维向量。

• 分析：

$$ Ax+e=b+kqI_m \\ Ax+kqI_m=b-e \\ (A|qI_m) \begin{pmatrix} x \\ k \end{pmatrix} =b-e \\ 转置一下：(x|k) \begin{pmatrix} A^T \\ qI_m \end{pmatrix} =(b-e)^T\\ 另一种组合：(qI_m|A) \begin{pmatrix} k \\ x \end{pmatrix} =b-e \\ 转置一下：(k|x) \begin{pmatrix} qI_m \\ A^T \end{pmatrix} =(b-e)^T\\ $$

• 代码：

  #脚本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):
          fori 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)

5.NTRU

• 概述： 公开密钥加密系统，使用基于格的加密算法来加密，包括加密算法和签名算法。
• 简化问题： $g\equiv hf \mod p$，已知$(h,p)$，求$(f,g)$
• 构造格： 变换得到$g=hf+kp$

$$ (f,k) \begin{pmatrix} 1 & h \\ 0 & p \end{pmatrix} = (f,g) $$

• 脚本求解

6.Ring-LWE问题

• 概述： LWE在环上的版本，$A$和$x$是多项式环

7.HNP问题（隐藏数问题）

• 概述： 以基于DSA为例

• 代码：

  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)

8.GGH加密

• 概述： $c=m*B’+e,B’=UB$，已知$c,B$，求$m$

• 代码：（Nguyen’s Attack算法）

  # 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))

9.HLCP(隐线性组合问题)

• 概述： $w=vG$，其中$w,v$为$GF(p)$上的向量，$G$是$0$至$B$之间整数值矩阵。已知$w$，恢复矩阵$G$。

10.$a_iX_i \equiv b_i \mod (P+S)$

$$ (k_1k_2,a_1k_2,a_2k_1,a_1a_2) \\ \begin{pmatrix} 1 & P & 0 & P^2 \\ 0 & X_1 & X_1 & X_1P \\ 0 & 0 & -X_2 & X_2P \\ 0 & 0 & 0 & X_1X_2\\ \end{pmatrix}\\ =(k_1k_2,k_2(b_1-sk_1),b_1k_2-b_2k_1,(b_1-k_1s)(b_2-k_2s) $$ $$ B \approx (P^{2\alpha},P^{2\alpha+\gamma},P^{\alpha+\beta},P^{2\alpha+2\gamma})\\ \begin{pmatrix} P^{2\gamma} & 0 & 0 & 0\\ 0 & P^{\gamma} & 0 & 0 \\ 0 & 0 & P^{\alpha-\beta+2\gamma} & 0 \\ 0 & 0 & 0 & 1\\ \end{pmatrix} $$

参考：

初识格 | DexterJie’Blog

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

格基规约算法概览-CSDN博客

格密码 | Lazzaro (lazzzaro.github.io)