格密码

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

1
2
3
4
5
6
7
8
9
10
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

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:]))
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
#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()))
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
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)
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
# 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)$。

加密

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

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

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
# 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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 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后的第二行。

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

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
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 的方程解法笔记