Lattices

题目1_Vectors

题目描述如下：

image-20251124145653963

将其翻译后如下：

  • 在定义一个格或者谈论格在密码学中出现的作用之前，先来复习一下线性代数与基相关的知识。
  • 下面的挑战应该被视为复习，如果下面的知识对你来说是全新的，你可能需要做一些背景阅读。
  • 通常，我们推荐Hoffstein, Pipher, Silverman所写的《An Introduction to Mathematical Cryptography》这本书，以及这个pdf文档和他们的应用Wayback Machine

下面进入复习阶段：

  • 一个在域$F$的向量空间$\mathbf{V}$，定义向量的二元运算。一个向量$v\in V$以及一个数$a\in F$，两个向量的加法和标量乘法如下：

    • 对于向量的加法：$v+w=z$，其中$v,w,z\in V$。
    • 对于数量乘法，是域$F$中的一个数与向量空间的一个向量相乘，结果仍然是一个向量：$a*v=w$，$v,w\in V,a\in F$

  • 你可能第一次见到向量是在二维向量空间中，以及实数域定义的。我们也将用二维向量空间以及实数域来举一个例子：

    • 考虑一个二维的向量空间：$v\in V$其坐标为$v=(a,b)$，其中$a,b\in R$。
    • 该二维向量空间的加法为：$(a,b)+(c,d)=(a+c,b+d)$
    • 该二维向量空间的数乘运算为：$c*\mathbf{v}=c*(a,b)=(ca,cb)$

  • 除了向量的加法与数乘运算之外，还定义了内积（也称为点积），也就是两个向量相乘结果返回一个数。如下所示：

    • $\mathbf{v·w}=a$，对于$v,w\in V,a\in F$。
    • 在二维空间中的例子就为：$v·w=(a,b)·(c,d)=ac+bd$

  • 接下来做一题，该题是实数域下的三维向量空间中向量的加法、数乘、内积混合运算，题目如下，flag为计算出的结果没有东西包裹：

$$
v=(2,6,3),w=(1,0,0),u=(7,7,2)\
3*(2v-w)·2u=?
$$

  • 接下来就是计算过程：

$$
\begin{array}{l}
6*[(4,12,6)-(1,0,0)]·(7,7,2)\
= 6*(3,12,6)·(7,7,2) \
= 6*(37+127+62) \
= 6117\
=702
\end{array}
$$

  • 所以本题的答案为：702

题目2_Size and Basis

题目描述如下：

image-20251124152819566

翻译过来如下：

  • 我们说一个向量集合$v_1,v_2,…,v_k\in V$满足方程$a_1\mathbf{v_1}+a_2\mathbf{v_2}+…+a_k\mathbf{v_k}=\mathbf{0}$的解如果只有$a_1=a_2=…=a_k=0$，那么就说这组向量是线性无关的。
  • 为了更直观体现，想象一个向量从一个点出发。给定一组线性无关的向量，返回原点的唯一方法是沿原向量移动。其他向量不论经过多少加法运算和数乘运算都不会回到这个点。
  • 向量空间的基就是一组线性无关向量的集合$v_1,v_2,…,v_n\in V$，使得$w\in V$能被写成如下形式：

$$
w = a_1\mathbf{v_1}+a_2\mathbf{v_2}+…+a_k\mathbf{v_n}
$$

  • 向量空间的基中向量的个数也就是线性空间的维数，记作$dim~V$。
  • 我们定义向量的一个大小，记为$||v||$，利用向量与自身的内积,$||v||^{2}=v·v$。
  • 对于向量空间的一个基$v_1,v_2,…,v_n\in~V$，任意两个不同向量之间的内积为零：$v_i·v_j=0,i≠j$，则我们称这个基为正交基
  • 对于一个正交基来说，对于所有基向量来说$||v_i||=1$，那么就称该正交基为单位正交基。

接下来就是本题的尝试：

计算向量$v=(4,6,2,5)$的长度，flag的值就是这个向量的长度。
$$
\begin{array}{l}
||v||^{2}\
=v·v
\=(4,6,2,5)·(4,6,2,5)
\=16+36+4+25
\=16+4+36+25
\=20+36+25
\=20+61
\=81
\end{array}
$$

  • 所以最终答案为：9

题目3_Gram Schmidt

本题是介绍斯密特正交化，也就是将一个给定的基（可能是正交基，可能不是正交基），将该基转化成一个正交基。如果需要转化成单位正交基，还需要对该正交基进行归一化处理。

题目描述如下：

image-20251124155744633

翻译过来就如下所示：

  • 在上一个挑战中，我们了解到了一个被称为正交基的一个特别的基。给出向量空间中一个基$v_1,v_2,…,v_n\in V$，通过斯密特正交化算法可以计算出一个正交化的基$u_1,u_2,…,u_n \in V$
  • 在Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman所写的书《An Introduction to Mathematical Cryptography》，斯密特正交化算法的伪代码如下所示：

$$
\begin{array}{l}
u_1=v_1\
Loop~i=2,3,…,n\

~~~~~~Set~u_i=v_i-\mu_{ij}·u_{j}~(Sum~over~j~for~1≤j<i)\\
End~Loop
\end{array}
$$

+ 接下来就是根据伪代码编写一个斯密特正交化的代码，并计算下面这个基的正交基，flag的值是$u_4$第二个分量，该分量是浮点型，保留5位小数：

$$
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是错误的，这个错误点就是问题的所在。但是如果算法没有问题，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
def vec_multi(u1:list,v1:list):
    """
    :param u1: 进行内积的向量之一
    :param v1: 进行内积的向量之一
    :return: 内积的结果,float或int类型
    """
    result = 0
    length = len(u1)
    assert length == len(v1) # 判断两个向量必须是相同维数的
    for i in range(length):
        result += u1[i]*v1[i]
    return result

def vec_add(u1:list,v1:list):
    """
    :param u1: 进行向量加法的其中一个向量
    :param v1: 进行向量加法的其中一个向量
    :return: vec:list: 向量加法的结果
    """
    result = []
    length = len(u1)
    assert length == len(v1) # 判断两个向量必须是相同维数
    for i in range(length):
        result.append(u1[i]+v1[i])
    return result

def vec_sub(u1:list,v1:list):
    """
    :param u1: 被减向量
    :param v1: 减向量
    :return: vec:list: 向量减法的结果
    """
    result = []
    length = len(u1)
    assert length == len(v1) # 判断两个向量必须是相同维数
    for i in range(length):
        result.append(u1[i]-v1[i])
    return result

def vec_times(k:int or float,u1):
    """
    :param k: 数乘的值
    :param u1: 数乘向量
    :return: vec: 返回结果向量
    """
    result = []
    for i in range(len(u1)):
        result.append(k*u1[i])
    return result

def Gram_Schmidt(vec:list):
    """
    该函数实现的是斯密特正交化
    :param vec: 传入的是一个基,并且是一个列表类型,两个行向量v1 = (1,2),v2 = (3,4);则传入[[1,2],[3,4]],列向量就转置成行向量再传入
    :return: vec2 : 经过斯密特正交化后的一个正交基
    """
    vec2 = [] # 保存正交基
    vec2.append(vec[0]) # 将vec[0]加入正交基中
    for i in range(1,len(vec)):
        mu_list = []  # 用于存放mu_ij的结果
        for j in range(i):
            mu = vec_multi(vec[i],vec2[j])/vec_multi(vec2[j],vec2[j])
            mu_list.append(mu)
        temp = vec_sub(vec[i], vec_times(mu_list[0], vec2[0]))
        for k in range(1,len(vec2)):
            temp = vec_sub(temp,vec_times(mu_list[k],vec2[k]))
        vec2.append(temp)
    return vec2


vec = []
v1 = [4,1,3,-1]
v2 = [2,1,-3,4]
v3 = [1,0,-2,7]
v4 = [6,2,9,-5]
vec.append(v1)
vec.append(v2)
vec.append(v3)
vec.append(v4)
result = Gram_Schmidt(vec)
print(result)
"""
[[4, 1, 3, -1], [2.5925925925925926, 1.1481481481481481, -2.5555555555555554, 3.851851851851852], [-0.7229219143576828, -1.0201511335012596, 2.012594458438287, 2.1259445843828715], [-0.3619189659458126, 0.916107382550335, 0.21488938603032665, 0.11309967685806738]]
得到的结果是：0.916107382550335,保留五位有效数字就为:0.91611
"""


+ 所以flag为：`0.91611`

## 题目4_What's a Lattice?

本题正式介绍格，题目描述如下：

![image-20251124182427829](./cryptohack-lattices/image-20251124182427829.png)

翻译过来就如下：

+ 我们现在准备开始讨论格。有一个线性无关向量组$v_1,v_2,...,v_n\in ~R^{m}$，格$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 \Z
$$

+ 格$L$的基是任何能够创建出格$L$的线性无关向量组。因此基并不是独特的。如下图所示，展现了一个二维的格以及这个格的两个基$u_1、u_2$以及$v_1、v_2$。

![image-20251124183609659](./cryptohack-lattices/image-20251124183609659.png)

+ 使用一个基，我们能通过基向量的整数倍，到达格中的任一一点，基向量还定义了基本域，基本域定义如下：

$$
F(v_1,...,v_n)=t_1v_1+t_2v_2+...+t_nv_n:0≤t_i<1
$$

+ 还是以二维几何空间为例子，二维平面中格的基本域就是以基向量$u_1、u_2$为边长的平行四边形。
+ 我们可以通过格的基向量，计算基本域的体积。仍然使用二维几何空间为例子，有基向量$v=(2,5)$，$u=(3,1)$。可以构成一个矩阵，这个矩阵的行由基向量的坐标构成：$A=\pmatrix{2&5\\3&1}$，从而这个基本域的体积为矩阵$A$行列式的大小（也就是行列式的绝对值）

$$
vol(F)=|det(A)|=||2*1-5*3||=||2-15||=13
$$

+ 对于本题的flag，就是计算一个格基本域的体积，给出格基$v_1=(6,2,-3),v_2=(5,1,4),v_3=(2,7,1)$，计算该基生成格的基本域体积。
+ 该基构成了一个矩阵$A=\pmatrix{6&2&-3\\5&1&4\\2&7&1}$，下面就是计算该行列式的过程：

$$
\begin{array}{l}
vol(F)\\=||det(A)||\\=||6*1*1+2*4*2+(-3)*5*7-(-3)*1*2-6*4*7-1*5*2||\\=||6+16-105+6-168-10||
\\=||22-99-178||
\\=255
\end{array}
$$

## 题目5_Gaussian Reduction

题目描述如下：

![image-20251124185852361](./cryptohack-lattices/image-20251124185852361.png)

翻译过来如下：

+ 如果你仔细观察，格在密码学中悟出不再。有时他们通过某个密码系统通过代数操作显现出来的，用来攻破那些没有被安全地生成的参数。最著名的例子就是`Coppersmith`针对RSA的攻击。
+ 格也通过两个基本的格困难问题，也可以用来建造密码学协议，这两个基本的格困难问题如下：
  + 最短向量问题（SVP）：找到格$L$中最短的非零向量。即找到非零向量$v\in L$，使得$||v||$最小。
  + 最近向量问题（CVP）：有一个不在格上的向量$w\in R^{m}$,找到一个格中的向量，使得该向量距离$w$，最近。即找到向量$v\in L$，使得$||v-w||$最小。
+ SVP对于通用格来说是比较困难的，但是对于足够简单的情况，有高效的算法能够计算SVP的解或者近似解。当格的维数为四或更小时，我们可以在多项式时间内精确计算出最短向量。但是对于更高维度的格，我们只能得到其近似值。
+ 高斯发明了一个算法，该算法是用于二维格，给定任意一个格基，寻找二维格中的最优基，此外该算法输出结果中的向量$v_1$是$L$中的最短非零向量，因此解决了SVP问题。

>对于高维格来说，有一种格基规约算法该算法被称为`LLL`算法，它是以`Lenstra`、`Lenstra`、` Lovász`这三个人名字的首字母命名的。如果你经常玩CTF，那你已经早就知道它了。LLL算法运行在多项式时间内。不过现在我们依然在二维空间中讨论问题。

+ 高斯算法大致通过从一个基向量的倍数中减去另一个向量，直到无法让基向量变小。由于这个算法用于二维空间的，所以该算法是很容易可视化的。下面这个伪代码是高斯算法的具体过程，来源于`Jeffrey Hoffstein`、`Jill Pipher`、`Joseph H. Silverman`写的这本`《An Introduction to Mathematical Cryptography》`

$$
\begin{array}{l}
Loop\\
~~~~(a) If ||v_2||<||v_1||,swap~v_1,v_2 \\
~~~~(b) Compute~m=⌊\frac{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
\end{array}
$$

>注意：高斯算法与欧几里得的GCD算法中`swap`和`reduction`步骤有比较相似的地方，并且我们必须对浮点数进行四舍五入，因为格上我们只能使用整数系数作为基向量。

+ 本题的flag是，使用高斯算法找到两个向量$v=(846835985,9834798552),u=(87502093,123094980)$的正交基，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
def vec_multi(u1:list,v1:list):
    """
    :param u1: 进行内积的向量之一
    :param v1: 进行内积的向量之一
    :return: 内积的结果,float或int类型
    """
    result = 0
    length = len(u1)
    assert length == len(v1) # 判断两个向量必须是相同维数的
    for i in range(length):
        result += u1[i]*v1[i]
    return result
def vec_sub(u1:list,v1:list):
    """
    :param u1: 被减向量
    :param v1: 减向量
    :return: vec:list: 向量减法的结果
    """
    result = []
    length = len(u1)
    assert length == len(v1) # 判断两个向量必须是相同维数
    for i in range(length):
        result.append(u1[i]-v1[i])
    return result

def vec_times(k:int or float,u1):
    """
    :param k: 数乘的值
    :param u1: 数乘向量
    :return: vec: 返回结果向量
    """
    result = []
    for i in range(len(u1)):
        result.append(k*u1[i])
    return result

def Gaussian_reduction(v1:list,v2:list):
    """
    使用高斯规约法计算出给定二维格的最短向量
    :param basis: 传入的是一个基,v1=[1,2],v2=[3,4]
    :return: 返回(v1,v2)大致形式如下:([1,1],[0,1])
    """
    if vec_multi(v2,v2) < vec_multi(v1,v1):
        v1,v2 = v2,v1

    m = int(vec_multi(v1,v2)/vec_multi(v1,v1))

    while m:	# 这个地方就有点像欧几里得辗转相除法余数为0停止，而这里是一个向量在另一个向量的投影为0停止(投影为0即正交)
        v2 = vec_sub(v2,vec_times(m,v1))
        if vec_multi(v2, v2) < vec_multi(v1, v1):
            v1, v2 = v2, v1
        m = int(vec_multi(v1, v2) / vec_multi(v1, v1))

    return v1,v2

v1 = [846835985,9834798552]
v2 = [87502093,123094980]
v1,v2 = Gaussian_reduction(v1,v2)
print(v1)
print(v2)
print(vec_multi(v1,v2))
"""
[87502093, 123094980]
[-4053281223, 2941479672]
7410790865146821
"""




## 题目6_Find the Lattice

题目描述如下：

![image-20251124205007282](./cryptohack-lattices/image-20251124205007282.png)

翻译如下：

+ 正如我们所见，格中的困难问题能在密码系统中构成一个门限函数。我们也发现在密码分析学中，格能攻击那些一开始看起来与格无关的密码学协议。
+ 这个挑战使用模运算去加密`flag`，但是在这个协议中隐藏了一个二维的格。我们非常推荐花时间在这个挑战中以及你使用格能怎样破解它。
+ 这题是一个非常著名的例子，关于它的资料非常丰富，但是在一个密码系统中找到隐藏的格经常是破解该密码系统的一个关键。

接下来就是一个带附件的题目了，先来看看该附件的`source.py`


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
from Crypto.Util.number import getPrime, inverse, bytes_to_long
import random
import math

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

# 该函数用于创建密钥
def gen_key():
    q = getPrime(512) # 生成一个随机素数q
    upper_bound = int(math.sqrt(q // 2)) # 设置上界
    lower_bound = int(math.sqrt(q // 4)) # 设置下界
    f = random.randint(2, upper_bound) # 在(2,上界)之间生成一个随机数f
    while True:
        g = random.randint(lower_bound, upper_bound) # 在(下界,上界)之间生成一个随机数g
        if math.gcd(f, g) == 1: # 要求(f,g)互素
            break
    h = (inverse(f, q)*g) % q # 计算h = f^{-1}*g % p
    return (q, h), (f, g) # 返回的是(h,g),(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}')









## 题目7_Backpack Cryptography

题目描述如下：

![image-20251124201455993](./cryptohack-lattices/image-20251124201455993.png)

翻译如下：

我非常喜欢这个密码系统，我把它放背包中并且随身携带它。为了减轻负担，我确保背包的密度不会太高。



# LWE1

## 题目1_LWE Background

## 题目2_LWE Intro

## 题目3_LWE High Bits Message

## 题目4_LWE Low Bits Message

## 题目5_From Private to Public Key LWE

# LWE2

## 题目1_Noise Free

## 题目2_Bounded Noise

## 题目3_Nativity

## 题目4_Missing Modulus

## 题目5_Noise Cheap

## 题目6_Too Many Errors