一些格中常见的知识、问题形式介绍。
基础知识
定义
格 $\Lambda$:给定一组线性无关的基向量 $v_1, v_2, v_3,…, v_n$, 那么这些基向量的所有整系数线性组合 $a_1v_1+a_2v_2+…+a_nv_n, a_i\in Z$ 所形成的集合,就叫作这组基向量所张成的格。
(格就是 $\Z^m$ 上的一个满秩可加子群)
一个点 $a\in \Z^m$ 与格 $\Lambda$ 的距离:$d(a,\Lambda):=min_{\textbf{x}\in \Lambda}\Arrowvert a-\textbf{x}\Arrowvert$;
格中的最短非零向量长度:$\lambda_1(\Lambda):=min_{a\in \Lambda/{0}}\Arrowvert a\Arrowvert$。
矩阵表示:$\textbf{A}\in \Z_q^{m×n},m\ge n$ (使前 $n$ 行构成可逆矩阵),则定义格为:
$\mathcal{L}(A):={\textbf{z}\in \Z^m\mid \exists \textbf{s} \in \Z^n:z=As^T\ mod\ q}$,简单地以 $A,A^T$ 来表示一个格(两种不同的方式)。
也有:
$\mathcal{L}^\perp (A)={z\in \Z^n\mid Az^T=0\ mod\ q}$
注:并不是所有格都能够写成第二种形式。
-
不同的基底或会张成不同的格
-
相同的格会有多种不同的基底
Lemma 1
若 $B,C$ 是两不同基底,使得其张成的格相同的充要条件是:存在单模矩阵 $U$ ( an n x n matrix with integer entries and det(U) = ±1)。
because: $B=CU$ and $C=BU^{-1}$,so $\mathcal{L}(B)\subseteq \mathcal{L}(C)$ and $\mathcal{L}(C)\subseteq \mathcal{L}(B)$ so ok.
而 U 为可逆矩阵,故 det = +-1。
Lemma 2
对于基底 $B$,有 $det(\mathcal{L}(B))=\sqrt{det(B^{\mathcal{T}}B)}$
两大难题
广义上的 NP-hard
SVP (最短向量问题)
给定lattice和基向量,找到lattice中的一个长度最短的非零向量。
CVP (最近向量问题)
给定lattice和基向量,以及一个不在lattice上的目标向量,找到lattice中一个距离目标向量最近的格向量。
Minkowski’s First Theorem
对于任意 n 维的满秩格基,都有 $SVP(L)\le \sqrt n(det(L))^{1\over n}$
二维格中的高斯格基约减算法
有点像 GCD
这个算法用于寻找 SVP。
设 L 为两个基向量 v1, v2 所张成的 2 维lattice,假定 $\arrowvert v_1\arrowvert < \arrowvert v_2\arrowvert$,我们现在通过减去 v1 的某个倍数来使得 v2 变短。$v_2^{\ast} = v_2 - \frac{v_1 \cdot v_2}{ {\Arrowvert v_1\Arrowvert} ^2} v_1$,我们就得到了新向量 v2* 正交于 v1,且使得 v2 变成了目前的最短状态。
但现在在 lattice 中,不能减去任意倍数的 v1,只能减去整数倍的 v1。
所以利用下式来替代:$v_2 -= m v_1, m = \lceil \frac{v_1 \cdot v_2}{ {\Arrowvert v_1\Arrowvert}^2} \rceil$
若 v1 > v2* 则交换之,继续操作;否则结束。
代码如下:
def GaussLatticeReduction(v1, v2):
while True:
if v2.norm() < v1.norm():
v1, v2 = v2, v1
m = round( v1*v2 / v1.norm()^2 ) # round() 四舍五入
if m == 0:
return (v1, v2)
v2 = v2 - m*v1
参考链接:
LLL 算法
在所有基向量经过至少一次规约后,LLL 返回新基,按长度进行大致排序。
规约的主要目的是,将这组任意给定的基转化为一组正交性较好的优质基(格基点在整数点上,故无法直接应用 GS 正交化),并使得这个优质基中的各个向量尽量短。
前置知识
Gram-Schmidt 正交化
给定一组 $m$ 维子空间的基 ${b_i\in \R ^ n}$,定义: \(b_1^*=b_1\\ b_2^*=b_2-\mu_{2,1}b_1^*,\mu_{2,1}={b_2·b_1^*\over b_1^*·b_1^*}\\ \vdots\\ b_m^*=b_m-\sum\limits_{i<m}\mu_{m,i}b_i^*,\mu_{m,i}={b_m·b_i^*\over b_i^*·b_i^*}\) 最后单位化向量 ${b_i^*}$。
LLL 规约基
令一组基为 $\textbf{B}={b_1,…,b_n}$;且 $\textbf{B}^={b_1^,…,b_n^}$,表示相应的 GS 正交基。设 $\mu_{i,j}:={b_j·b_i^\over b_i^·b_i^}$,则 LLL-reduced $B$ 满足:
- (Size Condition)$\forall j < i$,$\mu_{i,j}\le \eta$;
- (Lovász Condition)$\forall i < d$,$\delta\Arrowvert b_i^\Arrowvert ^2 \le \Arrowvert b_{i+1}^ + \mu_{i+1,i}·b_i^*\Arrowvert ^2$;
- 也有用另一等价条件的:$(\delta - \mu_{i+1,i}^2)\Arrowvert b_i^* \Arrowvert^2 \le \Arrowvert b_{i+1}\Arrowvert^2$
其中 $\eta\in [0.5,\sqrt{\delta}),\delta\in (0.25,1.0]$,当且仅当 $\delta<1$,有时间复杂度在多项式时间 $O(n^6log^3B)$ 内。最初取值 $\eta = 0.5, \delta = 0.75$, Sage 中一般取 $\eta = 0.501, \delta = 0.99$。
-
性质1:LLL-reduced B 含有一向量,其范数与真正的 SVP 相差最多在一个指数级别。
$\Arrowvert b_1 \Arrowvert \le 2^{n-1\over 2}\lambda_1(\Lambda)$
-
性质2(Minkowski):$\prod\limits_{i=1}^n\Arrowvert b_i\Arrowvert \le 2^{n(n-1)\over 4}det(\textbf{B})$
-
性质3:$\Arrowvert b_1\Arrowvert \le 2^{ {n-1\over 4} }det(L)^{1\over n}$
简易代码
def LLL(B, delta):
Q = gram_schmidt(B)
def mu(i,j):
v = B[i]
u = Q[j]
return (v*u) / (u*u)
n, k = B.nrows(), 1
while k < n:
# length reduction step
for j in reversed(range(k)):
if abs(mu(k, j)) > .5:
B[k] = B[k] - round(mu(k, j))*B[j]
Q = gram_schmidt(B)
# swap step
if Q[k]*Q[k] >= (delta - mu(k,k-1)**2)*(Q[k-1]*Q[k-1]):
k = k + 1
else:
B[k], B[k-1] = B[k-1], B[k]
Q = gram_schmidt(B)
k = max(k-1, 1)
return B
这里的 def mu() 就是 GS正交化 中的 $\frac{v_i \cdot v_j}{ {\Arrowvert v_i\Arrowvert}^2}$
参考链接: Building Lattice Reduction (LLL) Intuition、
Lemma
对格基 $\mathcal{L}$,LLL 算法输出的规约基满足: \(\Arrowvert \textbf{v}_1\Arrowvert \le \Arrowvert \textbf{v}_2\Arrowvert \le \cdots \le \Arrowvert \textbf{v}_i\Arrowvert \le 2^{n(n-1)\over 4(n+1-i)}det(\mathcal{L})^{1\over n+1-i}\) 也即能推出上面的性质 2、3。
BKZ
定义
以 $\textbf{B}:={b_1,…,b_n}$ 为基的格,而 $\pi_i:\R^m\rightarrow span(b_1,…,b_{i-1})^\perp$ 表示由 B 的各个向量张成空间 的正交空间。($\pi_i$ 为一恒等映射)
而:$\pi_i(b_j)=b_j^-\sum\limits_{i\le k<j}\mu_{k,i}b_k^\ if\ i\le j\ else\ 0$。
(存疑,不知道是个什么,随 i 增加而 norm 减少,直观上是:只考虑了与前 i-1 维正交化后的基)
$\mathcal{L}_{[i,j]}:={a_i\pi_i(b_i)+…+a_j\pi_i(b_j)\mid a_k\in Z}\subset \R^n$
-
$BKZ_\beta$-$reduced$:其中 $\beta$ 是 blocksize,格基 $\textbf{B}$ 被称为 ~ 的,当其满足 LLL-reduced 且 $\forall j\in [1,n],\Arrowvert b_j^* \Arrowvert =\lambda_1(\mathcal{L}{[j,k]})$,其中 $k=min(j+\beta-1,n)$。(也有说是 $\delta \Arrowvert b_j^* \Arrowvert \le \lambda_1(\mathcal{L}{[j,k]}),\delta \in (0,1)$ 的)
- HKZ-reduced:(BKZ-n) 改为 $\forall j\in [1,n],\Arrowvert b_j^* \Arrowvert =\lambda_1(\mathcal{L}_{[j,n]})$
-
在 BKZ 的每轮迭代中,都在寻找这样一个向量 $\textbf{v}\in Z^{k-j+1}$:$\Arrowvert \pi_j(\sum\limits_{i=j}^kv_i\textbf{b}i)\Arrowvert = \lambda_1(\mathcal{L}{[j,k] } )$。(还是没懂,粗浅理解为b_j^*?)
若 $\Arrowvert b_j^* \Arrowvert >\lambda_1(\mathcal{L}{[j,k]})$,则在 $b{j-1},b_j$ 之间插入 $\textbf{b}:=\sum\limits_{i=j}^kv_i\textbf{b}_i$。这之后再用一次 LLL 则可消除如此(若插入)造成的线性相关性,并且更新 $\mu$。
算法过程
如果我们想找到 SVP $\textbf{x}=\sum x_i\textbf{b}_i$,
一种方法是:
枚举所有格点 $\textbf{y}:\Arrowvert \textbf{y}\Arrowvert \le R,R=\Arrowvert \textbf{b}_1\Arrowvert$。既然 SVP 一定满足 $\Arrowvert \pi_i(x)\Arrowvert \le R\ \forall i\in [1,n]$,以 $R\ge \Arrowvert \pi_n(\textbf{x})\Arrowvert=…=\mid x_n\mid·\Arrowvert \textbf{b}_n^*\Arrowvert$ 为例:这说明对 $x_n$ ,我们的选择是有限的。由此可推广到所有系数(存疑,我看这个book不等式符号都反了。。)。
于是如此枚举(Enumeration)(搜索):创建一棵树,对 Xn 所有可能值建立子节点,再到 Xn-1 …,每一层的条件是范数小于等于 R(由于前面的不等式符号反了,故存疑)。但这样太朴素了,故需要剪枝。
(在 blocksize 较小的情况下表现不错)
第二种方法是:筛 (Sieving):
从晶格中的一组向量开始,然后把这些向量组合成更小的向量,使列表中的向量的长度迭代地变小。
大体朴素地,设 $L:{x_n};R:\forall \textbf{x},\Arrowvert \textbf{x}\Arrowvert \le R,\gamma<1$,然后创建 $L’:\forall \textbf{x},\textbf{y}\in L^2,\textbf{x}\ne ±\textbf{y}$,若 $\Arrowvert \textbf{x} ± \textbf{y}\Arrowvert <\gamma R$,则添加进 $L’$。
(渐进式地更快)
- 规约后的格基质量可以用
root Hermite Factor
去衡量。
rHF:$\delta = (\mid \textbf{b}_0\mid /Vol(\textbf{B})^{1\over n})^ {1\over n}$
对 $\beta$ 较小情况下,[GN08b] 中实验性地计算了 rHF,较大时遵循 [Che13] 中的渐进公式 $\delta(\beta)^{2(\beta-1)}=(\beta/(2\pi e))(\beta \pi)^{1\over \beta}$,趋于 1。
高斯启发式(Gaussian Heuristic):
估计 SVP 长度约为 $\lambda_1(\Lambda) \approx \sqrt{n\over 2\pi e}det(\Lambda)^{1\over n}$
几何级数假设(Geometric Series Assumption / GSA):
一个被充分规约的格基,其高斯正交化向量满足:$\Arrowvert \textbf{b}^_{m-i}\Arrowvert \approx \delta_0^{2i} \Arrowvert \textbf{b}_m^\Arrowvert$
对 BKZ-β 来说,即有 $\Arrowvert \textbf{b}^\Arrowvert \approx \delta(\beta)^{-2}\Arrowvert \textbf{b}_{i-1}^\Arrowvert$。
GGH
“Dead cryptosystem”
前提
对于格中的某一格点 p,向其添加一个长度为 $\delta$ 的随机向量 e,就可以产生一个随机点 c = p + e。如果 $\delta$ 较小,那么 p 就是 c 在格中的最近向量。虽然 CVP 是 NP-hard 的,但如果近似因子 (here refer to $\delta $) 比较大,则存在多项式时间的算法解决 app-CVP 问题。而求解之的结果与 $\delta$ 以及输入基的质量密切相关(规约基与非规约基)。
利用这种特性,可以构造单向陷门函数。故 GGH 加密方案诞生了。
基本思想
在 GGH 中,系统产生了同一个格的两个不同基,其中一个作为私钥的规约基 R,从 R 推导出一个普通基 B 作为公钥。
加密者用 B 把消息转化成格中的某个点 p,同时随机产生一个扰动向量 e,形成密文 c = p + e。扰动向量 e 的长度不超过 $\delta $。 由于解密者拥有规约基,因此他有较高的概率找到距离 c 最近的格点 p,从而恢复明文。
方案保证攻击者既无法通过公钥来正确恢复 p,也保证不能从公钥中推导出私钥。
简要来说: $c = mB+e$
- m: 由明文组成的一个 1xn vector
- B: 由公钥组成的一个 nxn matrix,一般由 R 乘上随机的单模矩阵生成。
- e: 一个 1xn vector,其中每项一般都是 random(±sigma) (sigma = 3 normally)
- c: 密文
Nyguen’s Attack
有个叫做 Nyguen 的人在 GGH 提出几年后,就把作者挂在网上的五个挑战日掉了,后来有个作者就宣布了:GGH is “dead”。
接下来我们就介绍这种攻击方法:
首先设一个 all-sigma vector s (sigma, sigma, …, sigma) \(c=mB+e\\ c+s=mB+(e+s)\\ c+s\equiv mB\ (mod\ 2*sigma)\\ since\ we\ know\ c,s\ and\ B,we\ can\ get:m2s\equiv m\ (mod\ 2*sigma)\\\) 那么接下来我们就能拿到: \({ {c-m2s*B}\over{2*sigma} }=({ {m-m2s}\over {2*sigma} })B+{e\over {2*sigma} }\) 这样我们就拿到了一个更简单的 CVP 问题,扰动向量更小,故我们可以用传统方法 embedded technique 将这个 CVP 转化为 SVP 解答并求出明文。
注:这里的分母 2*sigma 可能导致方程两边系数为非整数,在两边同乘上 2 即可。
Embedded technique
hxp 的 wp 中写得非常形象。
在一维中,假定给出如下 CVP 实例:
黑点即为格点,红点为 c = mB + e。
我们将扩展一维,将一维的 CVP 转化为二维的 SVP。
其中灰点为拓展后新增的格点,原目标点移动到了格中。
现在使用 LLL 求出该格的 SVP,如图所示,若代表 SVP 的向量为 $\delta$,则将原目标点在原格中偏移 $-\delta$ 即可求得 CVP。(“-“ stands for: from outer lattice to inside lattice)
具体做法如下:
设原基底矩阵为 B,CVP 目标点为 c = (100, 100, 100)。
将 c 作为基底向量添加进 B,再将原向量添加一维 0,c 的新增维度设为 1 (或其他)。
这样一来既保证了 c 在新格内,也保证了最后求出的 SVP 极大概率就是扰动向量。
那么 CVP = (100, 100, 100) - (0, 1, 0) = (100, 99, 100)。
参考链接:
Cryptanalysis of the Goldreich–Goldwasser–Halevi Cryptosystem from Crypto’97
Algorithms for the Closest and Shortest Vector Problems
NTRU
referred to https://latticehacks.cr.yp.to/ntru.html、https://pdfs.semanticscholar.org/67e7/020ce5649947e2199bc0eb8bd62b9a31ca4e.pdf
由 Hoffstein, Pipher, and Silverman 在 1998 年提出。
-
Zx.<x> = ZZ[]
表示以 x 为自变量、整数为系数的多项式- 如
f = Zx([1, 2, 3])
表示f = 3·x**2 + 2·x + 1
- 如
-
(f * g) % (x**n - 1)
,其中 f, g 为多项式;表示 x 的次数小于 n 的模域也即
R = Zx.quotient(x^n - 1)
然后介绍一下工具代码:
Zx.<x> = ZZ[]
def convolution(f,g): # return f * g in (x^n - 1)
return (f * g) % (x^n - 1)
def balancedmod(f,q): # return f where coef in f \in (-q//2, q//2)
g = list(((f[i] + q//2) % q) - q//2 for i in range(n))
return Zx(g)
def randomdpoly(d): # return a random polynomial which has d non-zero coefs \in {1, -1}
assert d <= n
result = n*[0]
for j in range(d):
while True:
r = randrange(n)
if not result[r]: break
result[r] = 1-2*randrange(2)
return Zx(result)
def invertmodprime(f,p): # invert f^-1 in (x^n - 1) for 'x' and p for coef
# which means that f * invertmodprime(f, p) = 1 + p*u, u is a polynomial
T = Zx.change_ring(Integers(p)).quotient(x^n - 1)
return Zx(lift(1 / T(f)))
def invertmodpowerof2(f,q): # sage cannot deal with non-primes
assert q.is_power_of(2)
g = invertmodprime(f,2) # f * g = 1 + 2 * u
while True:
r = balancedmod(convolution(g,f),q)
if r == 1: return g # yes, f * g = 1 + q*u indeed
g = balancedmod(convolution(g,2 - r),q)
# no, so: g' = g*(2-(1+2*u)) = (1-4*u**2) // f
def randommessage(): # return a polynomial whose coefs are \in {-1, 0, 1}
result = list(randrange(3) - 1 for j in range(n))
return Zx(result)
Parameters
NTRU 常使用 $n\in (250,2500)$ 的多项式。
整数 q,通常是 2 的幂次;p 一般是 3(远远小于 q),因为多项式 $f, g, r$ 的系数为 ${-1,0,1}$,且多为 0($D_f, D_g , D_r$ 较小)。
主体代码
def keypair():
while True:
try:
f = randomdpoly(Df)
f3 = invertmodprime(f,3)
fq = invertmodpowerof2(f,q)
break
except:
pass
g = randomdpoly(Dg)
publickey = balancedmod(3 * convolution(fq,g),q)
secretkey = f, f3
return publickey, secretkey
def encrypt(message,publickey):
r = randomdpoly()
return balancedmod(convolution(publickey,r) + message,q)
def decrypt(ciphertext,secretkey):
f, f3 = secretkey
a = balancedmod(convolution(ciphertext,f),q)
return balancedmod(convolution(a,f3),3)
这里需要注意:最后解密时 $a = fc=r3g+f*m\ mod\ q$
-
如果 $\arrowvert a\arrowvert > q//2$,此称之为越界错误,那么会造成 Decrypt Failure。
当 $d=Dr=Dg=Df$, $a$ 应当保证其理论最大系数 $3d+d =4d<q//2$。
但是为了防止攻击,q 相对于 n, d 应当小一点。我觉得这个 q 就是用来拿逆元的。
Attack
格中,λ 为任意正整数,[h_i] 即为公钥向量。规约出的结果即为 $(\lambda f \parallel g)$ ($\parallel$ 指连接符)
($g_i = \Sigma f_j*H_{n+i-j}$,所以要转置一大波)
Code
def attack(publickey):
recip3 = lift(1/Integers(q)(3))
publickeyover3 = balancedmod(recip3 * publickey,q)
M = matrix(2 * n)
for i in range(n):
M[i,i] = q
for i in range(n):
M[i+n,i+n] = 1
c = convolution(x^i,publickeyover3)
for j in range(n):
M[i+n,j] = c[j]
M = M.LLL()
for j in range(2 * n):
try:
f = Zx(list(M[j][n:]))
f3 = invertmodprime(f,3)
return (f,f3)
except:
pass
return (f,f)
n = 120
q = 2^32
d = 81
publickey,secretkey = keypair()
donald = attack(publickey)
print donald[0]
try:
m = randommessage()
c = encrypt(m,publickey)
assert decrypt(c,donald) == m
print 'attack successfully decrypts'
except:
print 'attack was unsuccessful'
后来 May 发觉 $f,g$ 中有大量的 0,所以他弄了个新格,其中 θ 为某个大整数,这样方便规约。
BDD(Bounded Distance Decoding) Problem
给定格 $\Lambda$、点 $\textbf{a}:d(\textbf{a},\Lambda)<{1\over 2}\lambda_1(\Lambda)$,找到离该点最近的格点 $\textbf{x}$。
- Babai 的最近平面算法
SIS (Short Integer Solution)
找到一非平凡的向量 $0\ne v\in \Z^m:Av=0\ mod\ q;\Arrowvert v\Arrowvert \le \beta < q\in \Z$,其中 $A\in Z_q^{n×m}$。也即找到小向量 $v\in \mathcal{L}^\perp(A)$,一般来说 $v\in {0,1,-1}^m$。
-
基于 SIS 的抗碰撞哈希函数:
有 $A\in \Z^{n×m}_q$,定义信息 $s\in {0,1}^m;h_A:{0,1}^m\rightarrow \Z_q^n$,则有 $h_A(s)=As^T$。(由哈希函数定义,$2^m>q^n$)
假设能找到碰撞使得 $As_0^T=As_1^T$,则 $A(s_0^T-s_1^T)=0;(s_0^T-s_1^T)\in {0,1,-1}^m$,故此基于 SIS 的困难性。
LWE
定义
令 $n,q\in \Z,\mathcal{X}$ 为一(以 0 为中心的)概率分布,给出秘密 $s\in \Z^n_q$,则称 $L_{n,q,\mathcal{X} }$ 表示在 $\Z_q^n × \Z_q$ 上的 LWE-Distribution。
具体地,均匀随机地取一 $a\in \Z^n_q$,$ e$ 遵循 $\mathcal{X}$ 生成,则 LWE 实例为 $(a,a·s+e)\in \Z^n_q×\Z_q$。
- 常见地,也基于参数为 $\alpha$ 的高斯分布去定义 $\mathcal{X}$,高斯分布的标准差为 $\sigma={\alpha q\over 2\sqrt{\pi} }$。
Search LWE-problem
给定 $m$ 组 $LWE$ 实例 $a_i,a_i·s+e_i$,我们建立如下矩阵表示:
寻找秘密向量 $s\in \Z_q^n$,称之为 ~ 问题。
Decision LWE-problem
给定 $m$ 组实例 $(a_i,b_i)\in \Z_q^n×\Z_q$,区分样本是从均匀随机分布 $\mathcal{U}(Z_q^n×Z_q)$ 选取的或是 LWE 实例 $L_{n,q,\mathcal{X}}$,被称之为 ~ 问题。
- 若误差和秘密以相同分布生成,则称之为
(Hermite) normal form LWE
;而从一小集合 ${-1,0,1}$ 中得到秘密的,则称为small secret LWE
。
Ring-LWE
对一个密码系统来说,公钥至少需要 $n$ 个 LWE 实例 $\mathcal{a},b\in \Z^n_q×\Z_q$ 构成,则公钥大小至少为 $n^2$。为减少之,可以在公钥中添加一些结构:如,定义操作 $\sigma:(a_0,…,a_{n-1})\rightarrow (-a_{n-1},a_0,…,a_{n-2})$,则公钥只需要 $a,{b_i}$,剩余的 $a_i=\sigma^i(a)$。这就如同多项式上的操作,于是我们由此引出 RLWE。
令 $f(x)=x^n+1,R_q=\Z_q[x]/<f(x)>;s=s(x)\in R_q,a\in R_q$,则 RLWE 即如此 $(a,a·s+e)$,具体定义待补充。
这里给个例子:
from sage.crypto.lwe import LWE
from sage.stats.distributions.discrete_gaussian_integer \
import DiscreteGaussianDistributionIntegerSampler as DGDIS
import uuid
n = len(secret)
q = random_prime(1<<512, proof=False, lbound=1<<511)
lwe = LWE(n=n, q=q, D=DGDIS(1<<128))
# A: 1xn; q: mod; D: error;
# output: (A, b)
lwe._LWE__s = vector(Zmod(q), secret)
L = [lwe() for _ in range(2*n)]
讲解一下基本用法:
已知一个 mxn 的矩阵 $A$,一个 mx1 的 $b = Ax + e$,其中 $e$ 是一个 m 维的扰动向量,$x$ 是一个 nx1 的向量。
这显然像一个CVP,可以构造一个 Matrix[32 + 64 + 1, 64 + 32 + 1],然后 LLL 拿 CVP。
前 [32, 64] 为 64 个 A,[32, 64:96] 是 1,求系数;[32:96, 64] 是 q 求模; [-1, 64] 是 CVP ($b$),[-1, -1] 来个 1 即可。
Knapsack
比较经典的背包问题:
给定 $M = (M_1,M_2,…,M_n)$,其中 $M_i > 0$。
将明文转换为一系列二进制数 $x=x_1,x_2,…,x_n$,那么 $S = \Sigma_{i=1} ^ n x_iM_i$
给定 $M,S$ 找到满足 $S$ 的序列 $x$。
Attacks
Meet-in-Middle
显然有时空复杂度都为 $O(2^{n\over 2})$ 的暴力算法:
枚举出所有可能的 $n\over 2$ 个 $x$ 组合,对于 $M_{0-{n\over 2} }$ 存下所有的 $Mid = S - S_{0-{n\over 2} }$,然后求出 $S_{ {n\over 2}-n }$ 并一一与 $Mid$ 匹配。
LLL Attack
构造矩阵求解 SVP 即可。以下两个矩阵在某些情况下会有不同效果。
Related
这里一并介绍类似问题及其矩阵构造:
- $a_1, …, a_n\in Z_n,N\in N$ with $gcd(a_i, N )= 1$ for some of them and $a_1x_1+…+a_nx_n=0\ (mod\ N)$, upper bounds $X_i\in Z$ such that $\arrowvert x_i \arrowvert \le X_i$ and $\Pi_{i=1} ^n X_i\le N$
For such prob, we can find $X=(x_1,…,x_n)$ as solution of SVP.
- 也可以这样: $Wlog\ gcd(a_n,N)=1$, $Set\ b_i=-a_i·a_n^{-1}$
将之转化为:$b_1x_1+…+b_{n-1}x_{n-1}=x_n\ (mod\ N)$,减少一维。
然后构造如下即可:
若 $x_1\approx … \approx x_n \approx N^{1\over n}$,那么可以知道 $x$ 是一个 short vector。
则我们可以拿到 $(x_1,…,x_{n-1},y)$
-
Find a solution of $a_1x_1+…+a_nx_n=b\ (mod\ N)$
- Define rank n+1 lattice with vectors $(x_1,…,x_n,y)$, which means that we can use the above matrix (with N replaced by -N).
- Define CVP target vector as (0, …, 0, b)
然后将 CVP 转换为 SVP 就可以了。
-
Find a solution of $a_1x_1+…+a_nx_n=b$
- Define $N = max(a_i, b) $, then use the method above.
- 直接日 knaspack 也行。
-
Find small modular roots of polynomials
- Given: integer N of unknown factorization, monic polynomial:
$f(x)=x^n+a_{n-1}x^{n-1}+…+a_1x+a_0$
- Find: all small roots $x_0$ with $f(x_0) = 0\ (mod\ N)$
We can set $f(x)=x_n+a_{n-1}x_{n-1}+…+a_1x_1+a_0$ with $x_i=x^i$
Size restriction is $ \Pi x_i = \Pi x^i \le \Pi X^i = X^ { {n(n+1)\over 2} }$
- Coppersmith
-
讲一个有趣的 trick:(源于 N1CTF)
-
已知 $x_0,N,N\mid f(x_0)·g(x_0)$ 且多项式系数极小,N 极大。我们现在的问题是要得到多项式的各项系数。
设 $w(x)=f(x)·g(x)$ 考虑到 $kN=w(x_0)$ 中 $k$ 极小,且多项式系数极小,我们能够联想到使用 LLL 规约得到多项式系数。格基如下: \(\begin{bmatrix} b*x_0^0 & 1 & 0 & \ldots & 0\\ b*x_0^1 & 0 & 1 & \ldots & 0\\ \vdots & \vdots & \vdots & \ddots & 0\\ b*N & 0 & \ldots & \ldots & 1 \end{bmatrix}\) 其中 b 为一平衡量,选取适当的参数即可。规约后得到的向量为 $b * (0,w_0,w_1,…,k)$。
-
Hidden Number Problem
refer to Return of the Hidden Number Problem, Keegan Ryan
我们所寻找的 Hidden Number,形如 $\arrowvert t\alpha -u\arrowvert < n $ (限制范围) 中的 $\alpha$,其中 $n$ 是接近 $\arrowvert t\alpha -u\arrowvert$ 的边界。
这里 $u$ 可以有多种含义,而下面讲述的是:已知 (多组) $MSB_{l_i,n}(x)$ 从而拿到 Hidden Number 的方法。
我们所要找到的是满足不等式组:$\arrowvert \lfloor t_i\alpha \rfloor - u_i \arrowvert_q< {q\over 2^{l_i+1} } for\ all\ i\in {1,…,d }$ 的 Hidden Number $\alpha\in [1,q-1]$。
$\arrowvert \sum\limits_{j=1}^n\lfloor A_{ij}s_j \rfloor - b_{ij} + 16\arrowvert_q< 16+16=32={q\over 2^3}$
- 这里的 $u = MSB_{l_i,n}(x)$,${q\over 2^{l_i+1} }$ 是作为限制范围的 upper_bound,而 $t_i$ 可以认作是随机数。
举个例子,假设:
q = getPrime(128)
(tα).bit_length() == 120
那么这里的 u = 1 « (120 - 1),$\arrowvert t\alpha -u\arrowvert < u \le {q\over 2^{l+1} }$,那么 l = 128 - 120 = 8
于是我们可以构造如下矩阵:
那么易知该格上有向量 $xB=(2^{l_1+1}\lfloor t_1\alpha \rfloor_q,…,2^{l_d+1}\lfloor t_d\alpha \rfloor_q,\alpha)$
而我们由以上不等式知道向量 $u=(2^{l_1+1}u_1,…,2^{l_d+1}u_d,0)$ 与之十分接近,于是我们可以使用 Embedded technique 来找到这个CVP。即可构造矩阵:
那么目标 SVP 为 $(xB-u,-q)$,其倒数第二项即为 $\alpha $
据paper中提到,一般来说 ${SVP}_2$ 即为目标向量。
- 应用 LLL HNP 问题来解决获取 DSA/ECDSA 中私钥的相关内容在另一篇博文,一直没发布(。
丢番图问题
待续
令 $\alpha_1,…,\alpha_n \in R, \epsilon > 0$。丢番图近似问题就是:
令 $Q\ge \epsilon^{-n} \in N$,找到 $0<q\le Q$ 使得 $\mid \alpha_i - {p_i\over q}\mid \le {\epsilon \over q}, 1\le i \le n$。
Method
令 $\alpha_1,…,\alpha_n \in \Q$,其分子、分母绝对值上界为 $X$。令 $0<\epsilon < 1$,则我们可以在多项式时间内得到满足条件的 $(q,p_1,…,p_n)$,其中 $0<q<2^{ {n(n+1)\over 4} }\epsilon ^{-(n+1) }$。
Proof
令 $Q=2^{ {n(n+1)\over 4} }\epsilon ^{-n}$,然后考虑如下格基:
其大小为 $(n+1)^2,det(L)=2^{ -{n(n+1)\over 4} }\epsilon ^{n+1}$
规约得到的向量 ${\cal v} = (q\epsilon/Q,q\alpha_1 - p_1,…,q\alpha_n-p_n)$,由闵可夫斯基界,$\Arrowvert {\cal v}\Arrowvert \le \epsilon < 1$
显然 $q>0$,又 $\Arrowvert {\cal v}\Arrowvert_{\infin} \le \Arrowvert {\cal v}\Arrowvert$,后面感觉有点问题,不算了。
RSA
见 RSA 1.0.1。