Cryptohack-LATTICES

LATTICES

1 Vectors

在某个域$F$上的一个向量空间$V$是用两个二元运算符定义的集合。

对于一个向量$v\in{V}$，和一个标量$a\in{F}$，向量的加法取两个向量并产生另一个向量：对于$v,w,z\in{V}$，$v+w=z$，标量乘法取一个向量和一个标量，并产生一个向量：对于$v,w\in{V},a\in{F}$，$a·v=w$.

考虑实数域上的二维向量空间，一个向量$v\in{V}$被看作是一对数：对于$a,b\in{R}$，$v=(a,b)$。向量加法以$v+w=(a,b)+(c,d)=(a+c,b+d)$的形式运算，标量乘法运算为$c·v=c·(a,b)=(c·a,c·b)$.

还可以定义内积（也称为点积），它取两个向量并返回一个标量。从形式上讲，我们认为：对于$v,w\in{V},a\in{F}$，$v·w=a$。在我们的二维例子中，内积运算为：$v·w=(a,b)·(c,d)=a·c+b·d$.

题目：

给出以下三个向量v = (2,6,3)，w = (1,0,0)，u = (7,7,2)，计算3*(2*v - w) · 2*u。

考察：基本的向量与标量之间的运算

直接计算或使用SageMath计算：

v = vector([2,6,3])
w = vector([1,0,0])
u = vector([7,7,2])
3*(2*v - w)*2*u
# 702

2 Size and Basis

一组向量$v_1,v_2…v_k\in{V}$是线性无关的，当且仅当
$$
a_1v_1+a_2v_2+…+a_kv_k=0
$$
仅在$a_1=a_2=…=a_k=0$时成立

基是一组线性独立的向量$v_1,v_2,…,v_n\in{V}$使得任何向量$w\in{V}$可以写成：
$$
w=a_1·v_1+a_2·v_2+…+a_k·v_n
$$

基中的元素数量是向量空间的维数

向量的大小，定义为||v||，向量自己和自己做内积：$||v||^2=v·v$

一组正交基(orthogonal)是指一组向量基$v_1,v_2,…,v_n\in{V}$，其两两不同的向量之间内积为0：$v_i·v_j=0,i\neq{j}$.

一组标准正交基(orthonormal)是指一组正交基，对于所有$i$，其大小$||v_i||=1$.

题目：

给出一个向量v=(4,6,2,5)，计算它的大小。

考察：求向量的大小或者说向量的模

直接计算或使用SageMath计算：

v = vector([4,6,2,5])
norm(v)
# 9

3 Gram Schmidt

给出一组向量空间的基$v_1,v_2,…,v_n\in{V}$，格拉姆-施密特算法可以计算这个向量空间的一组正交基$u_1,u_2,…,u_n\in{V}$.

在Jeffrey Hoffstein、Jill Pipher、Joseph H.Silverman所著的《数学密码学导论》中，格拉姆-施密特算法如下：

格拉姆-施密特算法

$u_1=v_1$

Loop $i$ = 2,3…,n

​ Compute $\mu_{ij}=v_i·u_j/||u_j||^2,1\leq{j}<i$.

​ Set $u_i=v_i-\mu_{ij}·u_j$(Sum over $j$ for $1\leq{j}<i$)

End Loop

题目：

给出以下一组基向量：
$$
v_1=(4,1,3,-1),v_2=(2,1,-3,4),v_3=(1,0,-2,7),v_4=(6,2,9,-5)
$$
使用格拉姆-施密特算法计算正交基。flag是$u_4$的第二个成员的浮点数值，保留小数点后五位。

考察：格拉姆-施密特算法计算正交基

使用SageMath计算：

v0 = vector([4,1,3,-1])
v1 = vector([2,1,-3,4])
v2 = vector([1,0,-2,7])
v3 = vector([6,2,9,-5])
M = Matrix([v0,v1,v2,v3])
M_GS = M.gram_schmidt()
round(M_GS[0][3][1],5)
# 0.91611

贴一个Python的Solution：

import numpy as np
v = [
    np.array([4,1,3,-1]),
    np.array([2,1,-3,4]),
    np.array([1,0,-2,7]),
    np.array([6,2,9,-5])
]

"""
u1 = v1
Loop i = 2,3...,n
   Compute μij = vi ∙ uj / ||uj||2, 1 ≤ j < i.
   Set ui = vi - μij * uj (Sum over j for 1 ≤ j < i)
End Loop
"""

u = [v[0]]
for vi in v[1:]:
    mi = [np.dot(vi, uj) / np.dot(uj,uj) for uj in u]
    u += [vi - sum([mij * uj for (mij, uj) in zip(mi,u)])]

print(round(u[3][1], 5))

4 What’s a Lattice?

给出一组线性无关的向量$v_1,v_2,…,v_n\in{R^m}$，由$v_1,v_2,…,v_n$生成的格子$L$是由$v_1,v_2,…,v_n$和对应整系数的组合。
$$
L=a_1·v_1+a_2·v_2+…+a_k·v_k:a_1,a_2,…,a_n\in{\mathbb{Z}}
$$
格$L$的基，可以是任意一组生成L的线性无关的向量。基的选择不唯一。在下图中，展示了一个由两组不同的基向量$u_1,u_2$和$v_1,v_2$生成的二维格。

使用基向量，我们可以用基向量的整数倍乘来到达格内的任意一点。基向量还定义了基本域：
$$
F(v_1,…,v_n)=t_1v_1+t_2v_2+…+t_n*v_n:0\leq{t_i}<1.
$$
举一个二维的例子，基本域是由边$u_1$和$u_2$构成的平行四边形。

我们可以通过基向量计算基本域的体积。例如，取一个以$v=(2,5),u=(3,1)$为基向量的二维格。创建一个矩阵$A$，其行对应于基向量：$A=[[2,5],[3,1]]$。这个基本域的体积为矩阵$A$行列式的大小：$vol(F)=|det(A)|=|2·1-5·3|=|-13|=13$.

题目：

计算由基向量$v_1=(6,2,-3),v_2=(5,1,4),v_3=(2,7,1)$构成的基本域的体积。

考察：基向量构成的基本域的体积

v = vector
v1 = v([6,2,-3])
v2 = v([5,1,4])
v3 = v([2,7,1])
A = matrix([v1,v2,v3])
det(A)

5 Gaussian Reduction

如果你仔细观察，格密码开始在密码学中无处不在。有时，它们通过操纵加密系统出现，破坏了不够安全地生成的参数。最著名的例子是Coppersmith对RSA密码学的攻击。

格密码也可用于构建加密协议，其安全性基于两个基本的困难问题：

最短向量问题（SVP）：在格L中找到最短的非零向量。换句话说，在$v\in{L}$内找到非零向量，使$||v||$取最小值。

最近向量问题（CVP）：给定一个不在L中的向量$w\in{R_m}$，找到与$w$最接近的向量$v\in{L}$，即找到向量$v\in{L}$，使$||v-w||$取最小值。

对于一般格来说，SVP很难，但对于足够简单的情况，有有效的算法来计算SVP的解或近似值。当格的维数为4或更小时，我们可以在多项式时间内精确计算；对于更高的维度，我们不得不接受一个近似值。

高斯开发了他的算法，为给定任意基的二维格找到最优基。此外，该算法的输出$v_1$是$L$中最短的非零向量，因此求解了SVP。

ps:对于更高维度，有一种称为LLL算法的格基约减算法，以Lenstra、Lenstra和Lovász的名字命名。如果你经常玩CTF，你就一定会知道。LLL算法在多项式时间内运行。不过，就目前而言，让我们停留在二维空间。

高斯的算法大致通过从另一个基向量中减去一个基向量的倍数来工作，直到不再可能使它们更小。由于这是在二维中工作的，因此很容易可视化。以下是Jeffrey Hoffstein、Jill Pipher和Joseph H.Silverman在《数学密码学导论》中对算法的描述：

高斯格约化算法

Loop

​ (a) If $||v_2||< ||v_1||$, swap $v_1,v_2$

​ (b) Compute $m=[v_1·v_2/v_1·v_1]$

​ (c) If $m=0$, return $v_1,v_2$

​ (d) $v_2=v_2-m·v_1$

Continue Loop

请注意，与欧几里德的GCD算法在“交换”和“缩减”步骤上的相似性，我们必须对浮点数进行四舍五入，因为在格上，我们可能只使用整数作为基向量的系数。

题目：

取两个向量$v=(846835985,9834798552),u=(87502093,123094980)$，通过高斯算法，找到最优基，flag为新的基向量的内积。

考察：高斯格约化算法求最优基

v = vector([846835985, 9834798552])
u = vector([87502093, 123094980])
v1,v2 = u,v
m = 1
while m != 0:
    if norm(v2) < norm(v1):
        print('swap')
        v1,v2 = v2,v1
    m = int((v1*v2)/(v1*v1))
    v2 = v2 - m*v1
print(v1, v2)
print(v1*v2)

6 Find the Lattice

正如我们所看到的，格包含一些难题，这些难题可以形成密码系统的陷门函数。我们还发现，在密码分析中，格可以破坏最初似乎与格无关的密码协议。

这个挑战使用模块化算法来加密标志，但协议中隐藏着一个二维格。我们强烈建议花时间应对这一挑战，并找到如何用格子打破它。这是一个著名的例子，有很多可用的资源，但知道如何在系统中发现格通常是打破它的关键。

作为提示，您将能够使用前一个挑战的高斯缩减来完成这个挑战。

题目代码如下：

from Crypto.Util.number import getPrime, inverse, bytes_to_long
import random
import math

FLAG = b'crypto{?????????????????????}'


def gen_key():
    q = getPrime(512)
    upper_bound = int(math.sqrt(q // 2))
    lower_bound = int(math.sqrt(q // 4))
    f = random.randint(2, upper_bound)
    while True:
        g = random.randint(lower_bound, upper_bound)
        if math.gcd(f, g) == 1:
            break
    h = (inverse(f, q)*g) % q
    return (q, h), (f, g)


def encrypt(q, h, m):
    assert m < int(math.sqrt(q // 2))
    r = random.randint(2, int(math.sqrt(q // 2)))
    e = (r*h + m) % q
    return e


def decrypt(q, h, f, g, e):
    a = (f*e) % q
    m = (a*inverse(f, g)) % g
    return m


public, private = gen_key()
q, h = public
f, g = private

m = bytes_to_long(FLAG)
e = encrypt(q, h, m)

print(f'Public key: {(q,h)}')
print(f'Encrypted Flag: {e}')

题目输出：

Public key: (7638232120454925879231554234011842347641017888219021175304217358715878636183252433454896490677496516149889316745664606749499241420160898019203925115292257, 2163268902194560093843693572170199707501787797497998463462129592239973581462651622978282637513865274199374452805292639586264791317439029535926401109074800)
Encrypted Flag: 5605696495253720664142881956908624307570671858477482119657436163663663844731169035682344974286379049123733356009125671924280312532755241162267269123486523

已知q, h, e，其中
$$
h\equiv{f^{-1}g}\mod{q}\
e\equiv{(rh+m})\mod{q}
$$

q 512位

f,g 低于256位

h,e 512位

r 256位

m为flag，大小约为231bit

要求得m，需要获得decrypt的参数，还剩$f$和$g$是未知的，由(6)式中可知
$$
f·h\equiv g\mod q
$$
用上一题格的思想，构造一个由下面这个矩阵$M$的两个行向量$(1,h),(0,q)$所张成的Lattice：
$$
M = \begin{bmatrix}
1 & h \
0 & q
\end{bmatrix} \tag{1}
$$
向量$(f,g)$在这个格上，即存在系数$a,b$使$a(1,h)+b(0,q)=(f,g)$
$$
f·h \equiv g \mod q\
f·h = g + u·q\
f·h - u·q = g
$$
即$a,b=f,-u$满足条件

向量$(f,g)$可以由两组基向量$M$的某种整系数线性组合$(f,-u)$来表示，因此向量$(f,g)$就在这个Lattice上。

对于两个基底向量，(1,h):512位,(0,q):512位

而向量$(f,g)$的长度约为256位，相比于基底向量极小，很大概率为此Lattice的最短向量。

EXP(SageMath):

from Crypto.Util.number import *

# Gauss Lattice Reduction
def Gauss(v1, v2):
    while True:
        if norm(v2) < norm(v1):
            v1, v2 = v2, v1
        m = round( v1*v2 / norm(v1)^2 )
        if m == 0:
            return (v1, v2)
        v2 = v2 - m*v1

def decrypt(q, h, f, g, e):
    a = (f*e) % q
    m = (a*inverse(f, g)) % g
    return m
        
q, h = (7638232120454925879231554234011842347641017888219021175304217358715878636183252433454896490677496516149889316745664606749499241420160898019203925115292257, 2163268902194560093843693572170199707501787797497998463462129592239973581462651622978282637513865274199374452805292639586264791317439029535926401109074800)
e = 5605696495253720664142881956908624307570671858477482119657436163663663844731169035682344974286379049123733356009125671924280312532755241162267269123486523
v = vector([1, h])
u = vector([0, q])
Gauss(v, u)
# ((47251817614431369468151088301948722761694622606220578981561236563325808178756, 43997957885147078115851147456370880089696256470389782348293341937915504254589),
# (-67269010250212717075432182693043963184097648880165008621907831284647116025901, 99012763459529858809608436133564630524350106000242070336818304053467942269178))
f, g = (47251817614431369468151088301948722761694622606220578981561236563325808178756, 43997957885147078115851147456370880089696256470389782348293341937915504254589)
m = decrypt(q, h, f, g, e)
print(long_to_bytes(m))
# b'crypto{Gauss_lattice_attack!}'