格密码

格密码

线性独立空间上有集合 $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完备问题,因此求解起来十分困难,因此这两个问题都是可以作为密钥体制的基础的。

  • 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$。

    • 参考

      从一道CTF题初探NTRU格密码

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

  • 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)$。

      • 加密
        1. 给定明文 $m=(m_1,m_2,\cdots,m_n)$,误差向量 $e$,和公钥 $B’$,计算 $v=m \cdot B’=\displaystyle\sum m_ib_i’$;
        2. 密文 $c=v+e=m \cdot B’+e$。
      • 解密
        1. 计算 $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}$;
        2. 如果 $e \cdot B^{-1}$ 足够小,可利用Babai最近平面算法的变种Babai rounding technique去除;
        3. 最后计算 $m=m \cdot U \cdot U^{-1} $ 得到明文。

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

    • 求解

      利用Nguyen’s Attack算法。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      # 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:]))
  • 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的误差向量是一个满足正态分布的小向量。

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

    • 求解

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

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      #脚本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)
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      #脚本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")