格密码

格密码

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

构造示例

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

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)

参考:

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

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)

参考

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

祥云杯 2020 - easy matrix

Aero CTF 2020 - Magic II

XNUCA2020 - diamond

2022 DASCTF 7月赋能赛 - LWE?

隐藏数问题(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 实现。

参考:

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 的方程解法笔记