0.出题思路

格的表示和操作：题目中通过多项式函数的系数和输入变量 ，构造了一个隐含的格结构。多项式计算本质上是对格点进行操作。

随机性和安全性：使用随机生成的多项式系数和质数确保安全性。通过随机生成共享值确保不同执行结果的多样性。

多项式计算：使用多项式计算构造复杂的函数，并通过模运算确保结果的范围受控。在格密码学中常用于构建复杂的加密方案。

密钥管理：通过连接多项式系数生成密钥，使用异或操作进行简单且安全的加密。这个密钥生成过程可以看作是在高维格子上的操作。

共享秘密：通过生成共享值，可以用于秘密分享和多方计算，确保在部分值丢失的情况下仍可恢复原始信息。这个过程类似于格密码学中的秘密共享机制。

利用格密码学的知识点

格结构：通过多项式的系数和输入变量构造了隐含的高维格结构。

最短向量问题（SVP）和带误差学习问题（LWE）：多项式系数和模运算的组合隐含了似格密码学中的困难问题。

安全性：通过随机生成的大质数和多项式系数，确保了加密过程的安全性，这类似于格密码学中的安全假设。

秘密共享：生成的共享值类似于格密码学中的秘密共享机制，通过多个共享值可以恢复原始信息。

1.格的来源：

计算机/数学家的目的是为了设计一个可以达到计算安全的密码算法。如果我们用编程的思维来想，假如我要编写一个程序来破解密码，那么这个破解程序的复杂度就一定要高于多项式时间复杂度。这就是“困难”的来源。一般来说，一个计算安全的算法，其破解难度都要高于多项式时间。

算法的时间复杂度定义：在计算机科学中，算法的时间复杂度是一个函数，用于定量描述算法的运行时间。算法所花费的时间与其执行的基本操作次数成正比，这些基本操作次数即为算法的时间复杂度。空间复杂度则是对算法在运行过程中临时占用存储空间大小的量度。

如果我设计了一个密码学算法，那么如何证明它是安全的？一种方式是证明其破解难度是高于多项式时间的。现代密码学大部分都建立在某个已知困难问题之上，例如质因数分解。当前数学和计算机技术尚无法在多项式时间内用传统计算机解决质因数分解问题。

现代密码学利用这些困难的数学问题设计了许多密码学算法，例如：

随机数生成器：区分一个真随机序列和伪随机序列的概率是可忽略的。

陷阱函数：函数容易计算，但其反函数计算非常困难。

这些困难问题是现代密码学算法的基础，因为它们保证了算法的安全性。特别是一些问题在一个方向上非常简单，但反过来却极其困难。比如质因数分解，质数相乘非常简单，但反过来分解质因数却是一个NP问题。公私密钥加密算法利用了这种性质。

除了质因数分解，还有其他许多困难的数学问题可以利用，比如椭圆曲线（ECC）在比特币和区块链技术中得到了广泛应用。有些算法有两个版本，一个基于质因数分解，另一个将质因数分解部分替换为ECC，即ECC版本。这个数学问题就是密码学算法的核心。

格问题（Lattice Problem）是现代密码学研究的一个新兴方向，因其在后量子时代的潜在应用价值而受到关注。质因数分解算法随着计算机算力的提升，可能会被破解，因此寻找新的困难问题成为必要，而格问题便是其中之一。

图中展示了格密码学的基本概念。格密码学是一种基于数学格子的加密技术。图中的网格点代表格点，向量表示算法的工作方式。

主要有两个重要问题：

最短向量问题（SVP）：找出格子中最短的非零向量。在图中，可以看到被高亮显示的最短向量。

带误差学习问题（LWE）：这是格密码学中的另一个核心问题，涉及通过带噪声的线性方程组来进行学习和推断。

图中的数学符号和方程展示了这些问题的数学表示。背景采用了渐变色，突出了网格和向量，使其更易于理解。

2.题目前置知识点介绍：

2.1.格的定义

格的定义： 格是N维空间中的规律分布且离散的点。最简单的格是整数格，即基于笛卡尔坐标系的ij等向量组成的空间。对格进行任意线性变换可以得到新的格B。任意一组线性无关的向量都可以生成一个格，称为该格的基，基向量的个数称为格的维度。

2.2.格的基本定理：

格的基本定理是指在数学中，格结构所遵循的几个重要性质和规则。主要包括以下几点：

a.离散性：格中的点是离散的，即每两个点之间有一定的最小距离。

b.周期性：通过一组基向量的线性组合生成整个格，基向量形成的基底具有周期性。

c.最近向量问题（SVP）：在格中找到离原点最近的向量，这一问题在计算上是困难的。

d.学习误差问题（LWE）：在已知一些带噪声的线性方程组下，求解未知变量的问题，也是一个在格中非常重要的难题。 这些定理和问题构成了基于格密码学的数学基础。

2.3.基于格的难题：

SVP（最短向量问题）：

最短向量问题 (SVP, Shortest Vector Problem) 是一个经典的计算复杂性问题，主要研究在给定的格（lattice）中找到欧几里得长度最短的非零向量。SVP 是格密码学中的核心问题之一，许多基于格的加密算法和协议都依赖于SVP的计算难度。

给定一个格,最短向量问题 (SVP) 要求找到一个非零向量 ,使得其欧几里得长度最短，即

其中表示向量u的欧几里得长度。

CVP（最近向量问题）：

给定连续空间中任意一点t，找到距离t最近的格点Bx。 Learning With Error（LWE）问题： 给定一个矩阵A和一个向量b，存在一个向量x，使得Ax=b。设定一组“系数”向量x，使基向量矩阵A的线性组合无限逼近目标向量b。可以引入误差噪音来表示和目标向量b的距离。

LWE(, , , ) : Search Version

Let , , . Given , find s.t.

在以上公式中：被称为整个LWE问题的安全参数。如果系统中的未知变量越多（即n越大），整个LWE问题会越难。的一个多项式倍数，。用的方程组越多，整个LWE问题会越简单。的一个多项式倍数。我们可以设置。 误差上限B<<q。误差越小，问题相对来说也就越简单。 以上参数依次设置的话不利于问题的求解，为了将问题简单化可以指定一个参数都设置成一个函数的输出。只要参数设置的符合问题定义的要求，生成的LWE问题实例（problem instance）大概率会有一个唯一的解。

2.4.LLL算法

LLL算法（Lenstra-Lenstra-Lovász算法）是由Arjen Lenstra、Hendrik Lenstra和László Lovász于1982年提出的一种格基规约算法。该算法可以在多项式时间内将任意格的基向量规约成一个“较短且更接近正交”的基。这在计算机科学、密码学和数论等领域有着广泛的应用。

算法原理

LLL算法的目标是找到一个格的“较短”基向量。它通过不断调整基向量，使它们满足一定的长度和角度条件。算法主要基于以下两个操作：

交换操作：当基向量不满足Lovász条件时，交换两个向量。

格矢量减法：通过减去其他基向量的整数倍，减小当前基向量的长度。

算法的核心是以下两步：

格矢量减法：调整基向量，使其长度尽可能短。

交换操作：当基向量不满足Lovász条件时，交换两个向量以改进基向量。

具体步骤

Step1.设定初始基。

Step2.对基向量 进行格矢量减法，使得，(其中是系数）。

Step3.检查Lovász条件：

如果不满足，交换 和，并返回第2步。

Step4.重复以上步骤，直到所有向量都满足Lovász条件。

Lovász条件 Lovász条件是确保LLL算法能够收敛的关键条件。对于每个基向量和,它要求

其中，，是Gram-Schmidt正交化过程中得到的系数，是在去掉之前所有基向量的投影部分后的向量。

应用

LLL算法有很多重要应用，特别是在密码学和数论中。以下是一些典型应用：

格密码学：LLL算法被用来破解基于格问题的密码系统，如NTRU公钥加密算法。

数论：LLL算法可以用于找到多项式方程的有理数解，例如Thue方程和Diophantine方程。

编码理论：LLL算法可以用于纠错码的解码。

计算几何：LLL算法可以用于计算凸包和Voronoi图。

2.5.格密码学在实际应用中的案例

Google的后量子密码学实验：

应用：Google在其Chrome浏览器中进行了后量子密码学的实验，使用了格密码学的算法（如New Hope）来替代传统的密钥交换协议。

目的：评估格密码学在实际互联网通信中的性能和安全性，为未来可能的量子计算攻击做好准备。

结果：实验结果显示，格密码学算法在性能和安全性方面表现良好，能够有效抵御量子计算机的攻击。

NIST的后量子密码标准化项目：

应用：美国国家标准与技术研究院（NIST）正在进行一个多阶段的后量子密码标准化项目，旨在选择和标准化能够抵御量子计算攻击的密码学算法。格密码学算法是其中的重要候选者之一。

算法：一些基于格的算法，如Kyber和Dilithium，在NIST的候选列表中表现出色。

目标：确保未来的信息安全，通过标准化后量子密码学算法来保护敏感数据。

比特币和区块链技术：

应用：在区块链和比特币等加密货币系统中，密码学算法的安全性至关重要。虽然目前主要使用椭圆曲线加密（ECC），但未来可能会转向格密码学，以增强抵御量子计算攻击的能力。

方案：基于格的数字签名方案和密钥交换协议可以作为现有方案的替代，以提高系统的整体安全性。

3.题目解析：

我们可以把calculate_f函数看成是以下表达式：

要得出flag，我们知道，解的关键在于求出这几个系数值，从下面代码我们就可以看出：

coefficients = [randint(0, 2**128) for _ in range(8)]

key = 0
for coeff in coefficients:
    key <<= 128
    key ^= coeff

cipher_text = bytes_to_long(flag) ^ key

![](https://files.mdnice.com/user/53928/26ef3b17-ff2f-4dd5-963a-485980a17f98.png)

因此，我们主线任务就是求出的值。由于从给出的已知数据中，我们知道和以及的值，于是我们可以知道以下几个等式：

其中我们是可以计算出来的，并且我们可以尝试将其模拟即最近向量问题。 最近向量问题是什么呢？ 举个简单的例子： 假设我们有一个基向量，𝑣1=(5,1)，𝑣2=(−2,8)，而我们需要找到的是通过对这组基向量进行一个线性组合，找到离点(27,8)最近的整数向量。简单来说，我们可以设向量为(𝑎1,𝑎2),有,

可解出𝑎1=232/42,𝑎2=13/42,我们需要的是整数，取整可得(6,0)，离(27,8)最近的向量为(5∗6+0 ,6+0) = (30,6),这里的(30,6)就是很可能我们要找的最近向量。

从图中来看，我们要找的就是图中离红点最近的点。这样看，这个问题看着还可以简单解决，但当问题转变为更高维，基变得更加复杂时，那么找到一个已知点的最近向量是很困难的。 那既然这个问题困难，我们为什么又要去模拟这个问题呢，那是因为由于本问题中，和都是512bit，而的系数都是128bit，参数中，未知的也是128bit，正是因为512bit和128bit相差过大，所以我们可以借助一些算法来求解这个问题，那就是LLL格基规约，以及巴拜最近平面算法。巴拜最近平面算法是一种用于解决最近向量问题（CVP）的启发式算法。其主要应用场景包括：

公钥密码学：

应用：在基于格的公钥密码系统中，最近向量问题是基础难题之一，巴拜算法可以用于求解这种问题。

例子：在LWE问题中，给定一个矩阵 A 和向量 b，找到一个向量 x 使得 Ax ≈ b，巴拜算法可以用于逼近解。

计算机图形学：

应用：在计算机图形学中，网格生成和点云处理需要找到最近的网格点，巴拜算法可以用于求解这种问题。

例子：在三维建模中，给定一个点云数据，需要将这些点映射到最近的网格点上，巴拜算法可以用于优化这种映射过程。

那我们又如何去模拟这个CVP问题呢，首先构造基B，如下：

我们已经有一个格基了，至于为什么要这样构造，首先我们观察前4列，假设我们有个这样的,

其中…代表参数不确定，把这个向量t和基B相乘就会得到碰撞。把得到的结果写在下面，至于…，将他们变为结果依次为：

有没有觉得这些式子很熟悉呢，前4个结果，是不是和我们已知的等式有些关联，我们把等式取过来，如下：

把去掉，并对式子进行一些转变，我们可以得到下面式子：

我们把它和我们，的第一个结果进行对比，

我们可以发现，好巧不巧，第一个结果就可以，同理，剩余其他三个也是，我们把结果进行一个化简，如下：

此时，虽然我们不知道这个结果的具体值是多少，但是我们可以知道它们的范围！前4个值，我们可以近似的看作是,后6个值我们可以近似地看作，最后一个值，我们可以看作是。到这里，我们已经构造了一组基，根据上面的值范围构造一个近似目标值

那此时我们就可以利用算法来求解了，算法会为我们找到一个接近的，由基的每个向量线性组合得到的整数向量。假设此整数向量为，根据我们之前得到的理想结果，我们就会有

那我们就可以得到的值，但我们仍然不知道c和s的值。拿出我们的式子：

两式相减，我们可以得到，

里面除了，其他均是已知的，那我们就可以得到值c(z_0 - z_2), , c(z_0 - z_3), , c(z_1 - z_2), , c(z_1 - z_3) , ...,

，那我们就可以使用求解数组的最大公约数来得到系数，得到之后，也就可以得到，此时系数全部已知，我们就可以顺利求解出我们的flag。运行结果如下：

Flag即为：flag{hahah_it_cost_my_much_much_time!I_am_happy_you_can_solve_it!}

4.题目附件：

from random import randint
from Crypto.Util.number import *
from secret import flag  # 假设 flag 是一个字符串或字节串，需要从 secret 模块中导入

def calculate_f(coefficients, x, y, z, p):
    """
    计算多项式函数 f 的值
    f(x, y, z) = x * coefficients[0] + x^2 * coefficients[1] + x^3 * coefficients[2]
               + y * coefficients[3] + y^2 * coefficients[4] + y^3 * coefficients[5]
               + z * coefficients[6] + coefficients[7] (mod p)
    """
    ret = 0
    ret += x * coefficients[0] + pow(x, 2, p) * coefficients[1] + pow(x, 3, p) * coefficients[2]
    ret += y * coefficients[3] + pow(y, 2, p) * coefficients[4] + pow(y, 3, p) * coefficients[5]
    ret += z * coefficients[6]
    ret += coefficients[7]
    return ret % p

# 生成一个512位的大质数 p
p = getPrime(512)

# 生成8个128位的随机整数作为多项式的系数
coefficients = [randint(0, 2**128) for _ in range(8)]

# 计算密钥 key，将8个系数连接成一个大整数
key = 0
for coeff in coefficients:
    key <<= 128
    key ^= coeff

# 使用密钥异或加密 flag，得到密文 cipher_text
cipher_text = bytes_to_long(flag) ^ key
print("ct = ", cipher_text)

# 生成4组 (x, y, z, w) 共享值，其中 w 是通过 calculate_f 函数计算得到的
shares = []
for _ in range(4):
    x = randint(0, p)
    y = randint(0, p)
    z = randint(0, 2**128)
    w = calculate_f(coefficients, x, y, z, p)
    packed_share = ((x, y), w)
    shares.append(packed_share)

# 打印生成的模数 p 和共享值 shares
print("p = ", p)
print("shares = ", shares)

# 示例输出
# ct = 120313272653925008664831175834010828151754133707667135295150624568794166269524381333775180215386968067578694598561057412384792990136851148486779591612382880227473454097958541083466297307687388296492960766280135212787015528970367856227945921838055878206992653001675475313687971017580306995639994442234339006434
# p = 10397669022112040578450537965937658537845116404027804289416685461564936847285022267932941110470658663625422867831808379039192822429009009665551670230876679
# shares = [((3894258154489977739652155964360456087062082875751222866438980583666202241223925160188381911698595421488802744607534814842902250603173068827415926279451139, 6985120774773009843975909180860790047409885752734097949052904836596988210213215594138711864004538669889354215820884683349706742655333022399973904367883636), 9460325788539910263119617753431234495477002959765562780111659233527058807751887401212072296283331812722416651321562396565060039184737354059720574321950805), ((6876390602549820901919003764565062807249619884423824085195458757710326251861154739951407857380976976618863368481349995334022404153683079632956016863862276, 410319117008001616321461335096349683089514454388344958718281052266984555170328264658043143971215272047722588835962821608992318541921021222105999541064251), 810871935622828231801791044393384010734851281157320381701122700384321539374657084719867561007312015773683802266017345211307495302193096569632678903674225), ((2555208149576856276805145897259405656471237552036956649187243879600810480847111894131464719365469987855703295607755301550975557578828192746396025274681602, 9942435058773913872095514414972319650411802920660543790613131011190364382975235763470898767800371565767582293433927004918447893798464768180539881763412697), 7912422090335950642817203316578712108705784166418469973439732089894334840362524238179747945188716869289013887923245194549541812148154127670147754688249973), ((1521774710640104354149282851795288635133872499974699443206192520410501572632503584275879365055371406036787443027752954404784362290182756737603274968112008, 148785904233613900307888584281018596651114897083281806069480364405752165120136922833937078062232194954394776563150898881746273194224433040826183532047669), 2793176564581920350738342962295776245211382819155207551847585198052739739325124254722557509211896202233576169798115843757096010178763162055388230865001973)]

5.解题代码

from random import randint
from Crypto.Util.number import getPrime, bytes_to_long 
file1 = open("./output.txt", "w+")

# from secret import FLAG  # 假设FLAG是密文，如果提供，可以取消注释

def closest_vector(B, target):
    # 进行LLL规约
    M = B.LLL()
    G = M.gram_schmidt()[0]  # 获取Gram-Schmidt正交基
    file1.write(str(M))  # 将LLL规约后的矩阵写入文件
    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  # 调整向量
            file1.close()
            return target - small  # 返回最接近的向量

# 已知的密文和模数
ct = 120313272653925008664831175834010828151754133707667135295150624568794166269524381333775180215386968067578694598561057412384792990136851148486779591612382880227473454097958541083466297307687388296492960766280135212787015528970367856227945921838055878206992653001675475313687971017580306995639994442234339006434
p = 10397669022112040578450537965937658537845116404027804289416685461564936847285022267932941110470658663625422867831808379039192822429009009665551670230876679

# 已知的共享值
shares = [
    (
        (3894258154489977739652155964360456087062082875751222866438980583666202241223925160188381911698595421488802744607534814842902250603173068827415926279451139,
        6985120774773009843975909180860790047409885752734097949052904836596988210213215594138711864004538669889354215820884683349706742655333022399973904367883636),
        9460325788539910263119617753431234495477002959765562780111659233527058807751887401212072296283331812722416651321562396565060039184737354059720574321950805),
        (
            (6876390602549820901919003764565062807249619884423824085195458757710326251861154739951407857380976976618863368481349995334022404153683079632956016863862276, 
            410319117008001616321461335096349683089514454388344958718281052266984555170328264658043143971215272047722588835962821608992318541921021222105999541064251),
            810871935622828231801791044393384010734851281157320381701122700384321539374657084719867561007312015773683802266017345211307495302193096569632678903674225),
            (
                (2555208149576856276805145897259405656471237552036956649187243879600810480847111894131464719365469987855703295607755301550975557578828192746396025274681602,
                9942435058773913872095514414972319650411802920660543790613131011190364382975235763470898767800371565767582293433927004918447893798464768180539881763412697),
                7912422090335950642817203316578712108705784166418469973439732089894334840362524238179747945188716869289013887923245194549541812148154127670147754688249973),
                (
                    (1521774710640104354149282851795288635133872499974699443206192520410501572632503584275879365055371406036787443027752954404784362290182756737603274968112008,
                    148785904233613900307888584281018596651114897083281806069480364405752165120136922833937078062232194954394776563150898881746273194224433040826183532047669),2793176564581920350738342962295776245211382819155207551847585198052739739325124254722557509211896202233576169798115843757096010178763162055388230865001973)
            ]
F = Zmod(p)  # 定义一个模p的有限域
# 将shares中的x, y值处理成多项式的形式
share_xxxyyy = [
    [ZZ(i) for i in [F(x), F(x)**2, F(x)**3, F(y), F(y)**2, F(y)**3]] for (x, y), _ in shares
]

share_w = [w for _, w in shares]  # 提取w值

r, c = 11, 11  # 定义矩阵的行列数
two_128 = 2**128
large = 2**1024

# 初始化矩阵和向量
mat = [
   [0 for _ in range(c)]
   for _ in range(r)
]
vec = [0 for _ in range(c)]

# 填充矩阵和向量
for coeff_i in range(6):
    for share_i in range(4):
        mat[coeff_i][share_i] = share_xxxyyy[share_i][coeff_i]
        mat[coeff_i][4 + coeff_i] = two_128
        vec[coeff_i + 4] = two_128 * two_128

for share_i in range(4):
    mat[6 + share_i][share_i] = p
    mat[10][share_i] = -shares[share_i][1]
    vec[share_i] = -two_128 * two_128

mat[10][10] = large
vec[10] = large
mat = Matrix(ZZ, mat)
vec = vector(vec)

# 调用LLL算法进行最短向量求解
cv = closest_vector(mat, vec)
assert cv[10] == large  # 验证结果

print("_____________________________________")
for idx, cvi in enumerate(cv):
    print(f"cv[{idx}] = {cvi}")

# 提取系数
coeffs_6 = [i // two_128 for i in cv[4:10]]

clist = []
czs = [(w - sum([a * b for a, b in zip(xxxyyyy, coeffs_6)])) % p for xxxyyyy, w in zip(share_xxxyyy, share_w)]

for i in range(0, 4):
    for j in range(0, 4):
        if i != j:
            clist.append(czs[i] - czs[j])

c6 = gcd(clist)  # 求解c6

c7 = czs[0] % c6  # 求解c7
coeffs1 = [*coeffs_6, c6, c7]

# 输出系数
for idx, coeff_i in enumerate(coeffs1):
    print(f"coeffs[{idx}] = {coeff_i}")

# 计算密钥
key = 0
for coeff in coeffs1:
    key <<= 128
    key ^= coeff

print("key =", key)

# 解密得到flag
flag = ct ^ key
print(bytes.fromhex(hex(flag)[2:]))

1. Lattice-Based Cryptography:

• Paper: "A Comprehensive Survey on Lattice-Based Cryptography" by Tancrède Lepoint and Vadim Lyubashevsky provides a detailed overview of lattice-based cryptography, including its foundations and various cryptographic schemes built on lattice problems.
• URL:https://www.ece.ufl.edu/wp-content/uploads/sites/119/publications/csur19.pdf

2. Polynomial Encryption:

• Paper: "Efficient Polynomial Multiplication and Its Applications to Lattice-Based Cryptography" by Léo Ducas, Eike Kiltz, and Adeline Roux-Langlois discusses the use of polynomial operations in lattice-based cryptographic algorithms.
• URL:https://academic.oup.com/nsr/article/8/9/nwab154/6360327

3. Learning With Errors (LWE) Problem:

• Paper: "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography" by Oded Regev introduces the Learning With Errors problem, a fundamental problem in lattice-based cryptography, and discusses its applications and implications.
• URL:https://ar5iv.org/pdf/2401.03703

4. Lattice-Based Zero-Knowledge Proofs:

• Paper: "Lattice-Based Zero-Knowledge Proofs: Tutorial and New Results" by Vadim Lyubashevsky and Thomas Prest provides a tutorial on zero-knowledge proofs in lattice-based cryptography and presents new results in the field.
• URL:https://eprint.iacr.org/2020/292.pdf