格密码

2021年10月11日22:32:41已关闭评论419 views1字数 6262阅读20分52秒阅读模式

线性独立空间上有集合 $v_{1}, \dots, v_{n} \in R^{n}$

v_{1}, \dots, v_{n} \in R^{n}

，格（Lattices）就是这些向量的线性组合，用公式表示为：

$L = a_{1} v_{1} + a_{2} v_{2} + \dots + a_{n} v_{n} ∣ a_{1}, a_{2}, \dots, a_{n} \in Z$

L = a_{1} v_{1} + a_{2} v_{2} + \dots + a_{n} v_{n} ∣ a_{1}, a_{2}, \dots, a_{n} \in Z

。

格 $L$

L

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

假定 $v_{1}, v_{2}, \dots, v_{n}$

v_{1}, v_{2}, \dots, v_{n}

是格 $L$

L

的基， $w_{1}, w_{2}, \dots, w_{n} \in L$

w_{1}, w_{2}, \dots, w_{n} \in L

，则必然存在整系数 $a_{i j}$

a_{i j}

使得：

${\begin{cases} w_{1} = a_{11} v_{1} + a_{12} v_{2} + \dots + a_{1 n} v_{n} w_{2} = a_{21} v_{1} + a_{22} v_{2} + \dots + a_{2 n} v_{n} ⋮ w_{n} = a_{n 1} v_{1} + a_{n 2} v_{2} + \dots + a_{n n} v_{n} \end{cases}$

{\begin{cases} w_{1} = a_{11} v_{1} + a_{12} v_{2} + \dots + a_{1 n} v_{n} w_{2} = a_{21} v_{1} + a_{22} v_{2} + \dots + a_{2 n} v_{n} ⋮ w_{n} = a_{n 1} v_{1} + a_{n 2} v_{2} + \dots + a_{n n} v_{n} \end{cases}

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

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

寻找一个格 $L$

L

中最短的非零向量。即，寻找一个 $v \in L$

v \in L

满足其欧几里德范数 $∣ ∣ v ∣ ∣$

∣ ∣ v ∣ ∣

最小。

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

对于一个非格 $L$

L

中的向量 $w$

w

，在格中寻找一个向量 $v$

v

，使得 $∣ ∣ w - v ∣ ∣$

∣ ∣ w - v ∣ ∣

最小。

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

构造示例

$b m - k n - c = - r ⟹ [\begin{matrix} m & - 1 & - k \end{matrix}] [\begin{matrix} 1 & 0 & b 0 & 2^{400} & c 0 & 0 & n \end{matrix}] = [\begin{matrix} m & - 2^{400} & - r \end{matrix}]$

b m - k n - c = - r ⟹ [\begin{matrix} m & - 1 & - k \end{matrix}] [\begin{matrix} 1 & 0 & b 0 & 2^{400} & c 0 & 0 & n \end{matrix}] = [\begin{matrix} m & - 2^{400} & - r \end{matrix}]

NRTU格密码

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

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

NTRU密码体制，需要三个整数参数 $(N, p, q)$

(N, p, q)

和四个次数为 $N - 1$

N - 1

的整系数多项式集合 $L_{f}, L_{g}, L_{φ}, L_{m}$

L_{f}, L_{g}, L_{φ}, L_{m}

，在这里 $N$

N

为一素数， $p, q$

p, q

可以不必为素数，但为安全，要求 $gcd (p, q) = 1$

gcd (p, q) = 1

，且 $q$

q

远大于 $p$

p

。

NTRU工作于多项式整数环 $R = Z [x] / (x^{N} - 1)$

R = Z [x] / (x^{N} - 1)

，当 $F \in R$

F \in R

，可以把 $F$

F

表示为多项式或向量形式， $F = \sum_{i = 0}^{N - 1} F_{i} x^{i} = [F_{0}, F_{1}, \dots, F_{N - 1}]$

F = \sum_{i = 0}^{N - 1} F_{i} x^{i} = [F_{0}, F_{1}, \dots, F_{N - 1}]

。

在这里记 $L (d_{1}, d_{2}) = F \in R : F $ 有 $ d_{1} $ 个系数为 $ 1 $ ， $ d_{2} $ 个系数为 $ - 1 $ ，其余为 $ 0$

L (d_{1}, d_{2}) = F \in R : F $ 有 $ d_{1} $ 个 系 数 为 $ 1 $ ， $ d_{2} $ 个 系 数 为 $ - 1 $ ， 其 余 为 $ 0

，选取三个确定的整数 $d_{f}, d_{g}, d_{φ}$

d_{f}, d_{g}, d_{φ}

，多项式集合 $L_{f} = L (d_{f}, d_{f - 1}), L_{g} = L (d_{g}, d_{g}), L_{φ} = L (d_{φ}, d_{φ})$

L_{f} = L (d_{f}, d_{f - 1}), L_{g} = L (d_{g}, d_{g}), L_{φ} = L (d_{φ}, d_{φ})

，而 $L_{m} = m \in R : m $ 的系数位于区间 $ [- \frac{p - 1}{2}, \frac{p - 1}{2}] $ ，其中 $ p $ 为素数 $$

L_{m} = m \in R : m $ 的 系 数 位 于 区 间 $ [- \frac{p - 1}{2}, \frac{p - 1}{2}] $ ， 其 中 $ p $ 为 素 数 $

。

密钥生成

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

然后，B计算 $h \equiv F_{q} ⋆ g (\mod q)$
$h \equiv F_{q} ⋆ g (\mod q)$
，则公钥为 $h$
$h$
，私钥为 $f$
$f$
，但在实际中，还将存储 $F_{p}$
$F_{p}$
，因而一般认为私钥为 $(f, F_{p})$
$(f, F_{p})$
。
加密

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

$e \equiv φ ⋆ h + m (\mod q)$
$e \equiv φ ⋆ h + m (\mod q)$

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

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

$a \equiv f ⋆ e (\mod q)$
$a \equiv f ⋆ e (\mod q)$

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

$b \equiv a (\mod p)$
$b \equiv a (\mod p)$

$c \equiv F_{p} ⋆ b (\mod p)$
$c \equiv F_{p} ⋆ b (\mod p)$

则多项式 $c$
$c$
就是明文 $m$
$m$
。
构造矩阵

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

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

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

从一道CTF题初探NTRU格密码

Practical lattice-based cryptography: NTRUEncrypt and NTRUSign


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:]))



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)




ax = (fx*ex).mod(qq)
an = [int(x) for x in ax.coefficients()]

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

GGH加密

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

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

定义

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

选定 $M$
M
值，明文向量 $(m_{1}, m_{2}, \dots, m_{n}), m_{i} \in (- M, M)$
(m1,m2,⋯,mn),mi∈(−M,M)
。
- 加密
  1. 给定明文 $m = (m_{1}, m_{2}, \dots, m_{n})$
  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}$
  3. 最后计算 $m = m \cdot U \cdot U^{- 1}$
GGH中的误差向量的选取是3或者-3。

求解

利用Nguyen’s Attack算法。



c = []
c = vector(ZZ, c)

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


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)


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:]))

参考

GGH encryption scheme

GYCTF 2020 - GGH

LWE问题

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

定义

随机选取一个矩阵 $A \in Z_{q}^{m \times n}$
$A \in Z_{q}^{m \times n}$
，一个随机向量 $s \in Z_{q}^{n}$
$s \in Z_{q}^{n}$
，和一个随机的噪音 $e \in ε^{m}$
$e \in ε^{m}$
。

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

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

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

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

求解

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



from sage.modules.free_module_integer import IntegerLattice

row = 
column = 
prime = 

ma = 
res = 

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


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)



from sage.modules.free_module_integer import IntegerLattice
from random import randint
import sys
from itertools import starmap
from operator import mul



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

参考

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

祥云杯 2020 - easy matrix

Aero CTF 2020 - Magic II

XNUCA2020 - diamond

相关推荐: OWASP Top 10 2021 全新出炉

OWASP Top 10 2021 是全新的，具有新的图形设计和一页有用的信息图。2021 年前 10 名发生了什么变化有三个新类别，四个类别的命名和范围发生了变化，并且 2021 年的前 10 名中进行了一些合并。A01:2021-Broken Access…

免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉。

左青龙
微信扫一扫

右白虎
微信扫一扫

格密码

格密码

NRTU格密码

密钥生成

加密

解密

构造矩阵

参考

GGH加密

定义

求解

参考

LWE问题

定义

求解

参考

2025御网杯线上初赛WriteUp （Misc、Crypto）

密码学浅入浅出ECIES之椭圆曲线加密算法

【CTFer成长之路】反序列化漏洞

【CTFer成长之路】XSS的魔力

CTF - Pwn题之shellcode&栈迁移

第二届长城杯信息安全铁人三项赛（防护赛）总决赛-逆向题解

ACTF 2025 writeup by Mini-Venom

2025蓝桥杯WP（LRT）

UKFC2024 ACTF WP

ACTF 2025 Writeup by Nepnep

在线咨询

微信