基础理论

向量空间

欧式空间

欧式空间就是二维空间、三维空间以及继承三维空间定理的N维空间。

欧式几何的关键就在于角度、长度的度量，因此需要在抽象的向量空间中引入长度、角度的概念。

格

格的定义

我的理解：

假设一个格拥有基向量{b1,b2,b3……bn}。那么这个Lattice就是它的基向量的任意线性组合的集合。

通俗地说，格可以理解为一种规则或者模式，用于在空间中排列和组织事物。我们可以将格想象成一张网格，其中每个交叉点都代表一个点或者一个向量。

在更高维的空间中，格由更多的向量所确定，这些向量决定了格的形状和结构。格中的点或向量可以是任意的整数倍，而且没有空隙，可以无限接近任意点。

两个向量来定义一个格

在二维空间中，我们可以用两个向量来定义一个格。这两个向量决定了格的方向和大小，我们可以通过沿着这两个向量的整数倍来生成格中的所有点。

两个向量所组成的格是两个向量所围成的空间。这个空间是由两个向量的线性组合所生成的，包含了两个向量上的所有点。

两个向量所组成的格可以是空间上的所有整数点，也可以是空间上的一部分整数点，或者甚至不包含任何整数点。这取决于两个向量的选择和它们的线性关系。如果两个向量是整数向量(向量的分量都是整数的向量)且线性独立(指向量集合中的向量不能通过线性组合得到零向量,即向量集合中的任何一个向量都不能表示为其他向量的线性组合)，那么它们所组成的格将包含空间上的所有整数点。但如果两个向量是实数向量或者线性相关，那么它们所组成的格可能只包含一部分整数点，或者不包含任何整数点。

格具有以下特点：

封闭性：格中的任意两个向量的线性组合仍然在格中。
整数性：格中的所有向量的坐标都是整数。
稠密性：格中的向量之间没有间隙，可以无限接近任意向量。

基变更

基底的变换或称基的变换（change of basis）在线性代数中，n 维向量空间的基是 n 个向量 α1, ..., αn 的序列，带有所有这个空间中的向量可以唯一的表达为基向量的线性组合的性质。因为经常需要处理一个向量空间的多于一个的基，在线性代数中能够轻易的变换向量的逐坐标表达，和变换关于一个基的线性映射到关于另一个基的等价表达是根本重要的。这种变换叫做基变更。

（个人理解）

相同的格可以用不同的基底表示，基变更就是更换格的基底，但是格不变，只是基底变了。

格基相互转化

格L的任意两个基可以通过在左边乘上一个特定的矩阵来相互转化，这个矩阵由整数构成，且它的行列式为 ±1

格的行列式

令B是格L的基矩阵（每个基是B的列向量），则格L的行列式Determinant定义为det(L)=|det(B)|。尽管格L可以有不同的基，但是对应的det(L)值却是相同。

从几何上来说，det(L)代表格L的基本平行体的体积，因此格L的不同的基其对应的基本平行体的体积是相等的。所以det(L)是独立于所选择的基，是格L的不变量。

格的密度

dim（L） 格的维度，即格的基中的向量个数

用一个Lattice的Determinant来衡量这个格的点阵分布的密度

我们如果在这个空间中任意的画一个球体(多维空间即超球体)然后可以数数看这个球体中覆盖了多少Lattice里的点。点的数量平均于球体的体积，就是这个格的密度了

直觉上来说，det(L)的值与格L中点的密度成反比，即det(L)的值越大，格L中点越稀疏。

向量范数

向量范数是用来衡量向量的大小的一种数学概念。它是一个实值函数，将向量映射到非负实数。2-范数（也称为欧几里德范数或L2范数）是向量空间中向量的度量，表示为 $||x||_2$,其中x向量。它是指向量中每个元素的平方和再开方

基础区域 F

一个格L的任何基础区域都有着相同的 “体积”，基础区域F的n维体积称为L的行列式，记为detL

数学定义较为抽象，我们可以直观地用“周期性”的思想来考虑这个问题：平移这样的一个“基础区域”，我们最终能得到整个格（二维情况下的整个平面）。基础区域通常用于描述一个格在空间中的基本重复单元。格是由整数线性组合生成的离散子群，而基础区域是该离散子群在空间中的一个最小的不相交区域。

Hadamard 不等式

L是一个格，任意一个基和基础区域 F ，有$v1,v2,...,v_m$,

det(L) = vol（F）≤||v1|| ||v2|| .....||vm|| ，基向量$v1,v2,...,v_m$越接近垂直，等式越成立，vol（F）是F的体积

对偶格

格的对偶空间：

空间中的每一个元素都是一个把这个格中的元素映射到整数空间中的线性变换，一般来说我们可以用一个向量来表达线性变换。

也就是说一个Lattice的对偶空间就是一组向量，而这些向量乘以格中的任意格点，都可以得到一个Z中的元素。

这些对偶的向量，乘以任意Lattice中的格点向量，都能得到一个整数。这些向量本身就组成了另一个Lattice，我们把这个新的Lattice成为对偶格（Dual Lattice）。

格与对偶格

我们可以把对偶格理解成是一个格的“倒数”，因为很多时候它们之间的关系是反过来的

格与对偶格之间唯一需要满足的就是任意两个格点之间相乘，乘积一定是在z中的整数。并且只有相乘这个操作有意义，加法是没有几何意义的。

连续最小长度

$\lambda_i时格中i个线性无关变量的最小长度$

Minkowski凸集定理（Convex body theorem）

Blichfeldt引理

Blichfeld's Theorem:

选取一个集合，只要所取集合的体积大于行列式，这里面一定有两个点，它们的差值是一个格点。注意，集合体积不能等于行列式，因为基本区域中有且只有一个格点（回忆基本区域的定义）

凸集

一个凸集是指其中的任意两点之间的线段都在该集合内部。简而言之，凸集是一个集合，其中任意两点之间的连线都在该集合内。

Minkowski凸集定理定义

在$\mathbb{R^n}$中选取一个关于原点对称的凸集，如果它的体积大于格的基本区域的体积乘与$2^n$,那么S中一定包含一个非零的格点。

在整数格$\mathbb{Z^n}$中非常好理解，因为以原点出发到所有下一个点这段距离构成的空间，恰好就是$2^n$，所以说任何凸集（集合的表面不能有凹陷）只要体积大于$2^n$，那就一定会溢出这段空间，进而覆盖某个非0的格点。

换成一个不规则的Lattice，即在原有的$\mathbb{Z^n}$上叠加线性变换，这个定理还是成立的。

理解如下：

定理的应用

Minkowski凸集定理推论

简单来说，L的最短向量，最长不会超过$\sqrt n\ \ det(L)^{\frac{1}{n}}$
如果说Minkowski第一定理给出了对于最短向量$\lambda_1$的一个上限的话，第二定理给出了对于其他最短向量$\lambda_i$的一个取值上限。

施密特正交化Gram-Schmidt Orthogonalization正交化 GSO

定义

在一个平面，或者三维空间中，任意一点都可以被坐标系表示出来。而我们更喜欢的是单位直角坐标系，因为在一个单位直角坐标系中，任意一个向量的坐标分量，通过简单的投影就可以搞定。因此，如何找到欧式空间的一个“直角坐标系”，变得非常重要。施密特正交化法就告诉我们了一种把“任意坐标系”变为“直角坐标系”的方法。

如何理解施密特正交？

首先需要理解一个向量$\alpha$2在另外一个向量$\alpha$1的投影公式。只要利用正交的定义，就很容易知道$\alpha$2在$\alpha$1的投影向量

二维空间

平面上任意两个不共线的向量都可以构成平面的一个坐标系(也就是一组基)，我们可以利用这两个向量之间的投影得到两个正交的向量

三维空间

N维空间

要得到一个单位直角坐标系，或者单位正交基，还需要对得到的正交向量逐个单位化即可。

例子

假设我们拥有一个格的基B={b1,b2……bn},这两个基向量是不垂直的。接下来，我们尝试找到一组互相垂直的基$B^*$

最短距离

除了行列式，格的另一个基本量是格上最短非零向量的长度，即格中最短距离，其定义为

如图，两两格点构成的向量都可以通过平移得到起始点为原点的向量，通过找到距离原点最近的格点即可计算出格中最短距离。格中最短距离也称为第一连续极小，记为$\lambda$1

同理可定义第二至第n连续极小,$\lambda$2,$\lambda$3……$\lambda$n

在二维格上，可以用多项式时间算法求解出$\lambda$1，但在多维格上求解$\lambda$1则十分困难。注意，给定一组格基，最短向量不一定是格基之一

距离函数（Distance Function）

给定任意一个点t（这个点不需要在Lattice上），我们可以定义距离函数为$\mu(t,L)$这个点到附近的Lattice点的最短距离。

覆盖半径（Covering Radius）

左右移动t的位置，然后就可以找到在这个Lattice中可以得到的最大的$\mu$。我们一般称这个最大值叫覆盖半径（Covering Radius）$\mathbb{R^n}$

假设在这个Lattice中，以每个格点为圆心画很多个圆，如果逐渐把圆的半径扩大的话，那么所有的圆就会逐渐开始覆盖整个$\mathbb{R^n}$空间

格的平滑参数

如果在每个格点上叠加一个圆形范围内取值的随机噪音(生成一个随机值，将这个随机值与圆形范围内的所有格点元的半径相加或替换)，那么当圆的半径达到覆盖半径之后，这个Lattice本身就和背后的连续空间$\mathbb{R^n}$合二为一了

为什么要用到平滑参数？

实际上，平滑参数只是定义了一个临界值，当格上的离散高斯分布的标准方差大于此参数时，那么从此分布中选取的点在模格的单元平行多面体中后，几乎将服从均匀随机分布，而当小于此参数时，则不服从均匀随机分布。

Lattice的几何构造

为什么要构造????

最简单的笛卡尔坐标系整数格$\mathbb{Z^n}$,其基向量都是相互垂直的（orthogonal basis），如果我们可以把一个任意的LatticeΛ转换为一个垂直基的格，那么可以更方便简单的在几何空间分析格，比如找到一个格中一个距离t（随意给定的目标值）最近的非零向量v，将其转化为几何空间，只需要通过上下取整，就可以快速找到。

如何构造?????

把一个Lattice的基进行变换，找到一组非常接近垂直的基的，这一过程称之为Lattice Basis Reduction。

比较常见的Basis Reduction方法是Gram-Schmidt正交化过程

回忆上面提到n维空间得到一组基

Lattice Rounding（取整）问题

刚刚Lattice的几何构造提到一个例子，“找到一个格中一个距离t（随意给定的目标值）最近的非零向量v，将其转化为几何空间，只需要通过上下取整，就可以快速找到”

如何取整呢？？

$||t-v||\leq \frac{1}{2}||b_i^||$$||t-v||\geq \frac{1}{2}||b_i^||$，那么我们通过取整操作就能解决
如果落点在外圈圆的话，那么很有可能就会被取整到隔壁的格点上去，那么那个点就不是最近的了

使用Sagemath进行格的计算

基本的向量于标量之间的运算

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

格的定义

sage:fromsage.modules.free_module_integer import IntegerLa ttice 
sage:A = Matrix(ZZ, [[6,1],[7,2]])
[6 1] 
[7 2]

格基规约

A.LLL()
[1 1] 
[2 -3]

用ctf一道例题初探格密码

题目

from Crypto.Util.number import *
import gmpy2
from flag import flag


def generate():
    p = getStrongPrime(2048)
    while True:
        f = getRandomNBitInteger(1024)
        g = getStrongPrime(768)
        h = gmpy2.invert(f, p) * g % p
        return (p, f, g, h)


def encrypt(plaintext, p, h):
    m = bytes_to_long(plaintext)
    r = getRandomNBitInteger(1024)
    c = (r * h + m) % p
    return c


p, f, g, h = generate()
c = encrypt(flag, p, h)
with open("cipher.txt", "w") as f:
    f.write("h = " + str(h) + "\n")
    f.write("p = " + str(p) + "\n")
    f.write("c = " + str(c) + "\n")
'''
h = 7257231567493321493497732423756001924698993879741072696808433246581786362611889417289029671240997843541696187487722285762633068287623369923457879458577466240950224087015909821079480431797917376609839097610864517760515986973340148901898582075413756737310797402537478388864632901178463429574227279668004092519322204990617969134092793157225082977967228366838748193084097651575835471869030934527383379794480007872562067799484905159381690179011192017159985260435844246766711550315143517066359521598424992244464723490166447105679062078049379153154659732304112563255058750656946353654402824529058734270363154894216317570784
p = 23969137365202547728693945383611572667294904799854243194734466236017441545927679469239814785947383727854265554138290421827510545078908517696536495567625593439996528098119344504866817224169113920532528233185011693829122447604993468817512696036673804626830507903206709121383065701222707251053362179946170981868061834734684494881504724254812067180384269711822738708203454131838741703416329765575995359232573740932069147491776326045743679105041246906081872936901848272288949389026129761726749334006319072981386763830897454245553866145620689939497868469730297795063648030738668273210516497399954626983672357236110363894081
c = 6388077150013017095358415295704360631706672647932184267739118115740221804173068089559645506533240372483689997499821300861865955720630884024099415936433339512125910973936154713306915269365877588850574948033131161679256849814325373882706559635563285860782658950169507940368219930971600522754831612134153314448445006958300840618894359885321144158064446236744722180819829183828290798747455324761671198097712539900569386477647697973195787663298318786718012522378981137877863153067057280649127202971806609339007027052518049995341356359016898069863799529357397514218249272201695539181908803360181347114492616706419618151757
'''

分析

求出f,g,就可以得到m,那么怎么求出f,g呢?
构造一个矩阵A中的两个向量(1,h)(0,g) 所张成的格子:

很大概率上，这个(f, g)就是这个lattice的最短向量

wp

from Crypto.Util.number import inverse, long_to_bytes
h = 7257231567493321493497732423756001924698993879741072696808433246581786362611889417289029671240997843541696187487722285762633068287623369923457879458577466240950224087015909821079480431797917376609839097610864517760515986973340148901898582075413756737310797402537478388864632901178463429574227279668004092519322204990617969134092793157225082977967228366838748193084097651575835471869030934527383379794480007872562067799484905159381690179011192017159985260435844246766711550315143517066359521598424992244464723490166447105679062078049379153154659732304112563255058750656946353654402824529058734270363154894216317570784
p = 23969137365202547728693945383611572667294904799854243194734466236017441545927679469239814785947383727854265554138290421827510545078908517696536495567625593439996528098119344504866817224169113920532528233185011693829122447604993468817512696036673804626830507903206709121383065701222707251053362179946170981868061834734684494881504724254812067180384269711822738708203454131838741703416329765575995359232573740932069147491776326045743679105041246906081872936901848272288949389026129761726749334006319072981386763830897454245553866145620689939497868469730297795063648030738668273210516497399954626983672357236110363894081
c = 6388077150013017095358415295704360631706672647932184267739118115740221804173068089559645506533240372483689997499821300861865955720630884024099415936433339512125910973936154713306915269365877588850574948033131161679256849814325373882706559635563285860782658950169507940368219930971600522754831612134153314448445006958300840618894359885321144158064446236744722180819829183828290798747455324761671198097712539900569386477647697973195787663298318786718012522378981137877863153067057280649127202971806609339007027052518049995341356359016898069863799529357397514218249272201695539181908803360181347114492616706419618151757

'''v1 = vector(ZZ, [1, h])
v2 = vector(ZZ, [0, p])
m = matrix([v1,v2])
re=m.LLL()'''
'''
[ 140165891500972861127767415311334757297477816480570735901532575717579672765221212171489392644327018202900088035383969034846193847149851961591661082906530495738734185460636601059708032788268225305120040067251226533612047405603785333261269570827395533567542600084996230099530440207162530350599289132101020447759                                                                               1493239469420336600577802657161324795848374750185055876743560582622232360193779109171117333425338766341860983348309692998243289015442909620365263900067613009409717218816514258676437322125744209790095123709189541828478158286030084857]
[  -6587436106779837286979819765610234656833614261370589490258759898084162842491296090778870009535549744355380840740453597473055836588394362920503294204938500850126824835496616433845450766569856593517735583365317459727862281287964787594208327606964344445826266006072948348367598049384609987564219203827072840682 -171005492909351510328086708105114534743476434461829561451746029304219829716002127008743009734683363852708528227855823854524294546575379923599178676596777288112643721937105318380215241021499702643702104988001343316155368228373179578005413549403402969043703160926672150203774232966694439971206554586812018038645]
'''
f=140165891500972861127767415311334757297477816480570735901532575717579672765221212171489392644327018202900088035383969034846193847149851961591661082906530495738734185460636601059708032788268225305120040067251226533612047405603785333261269570827395533567542600084996230099530440207162530350599289132101020447759
g= 1493239469420336600577802657161324795848374750185055876743560582622232360193779109171117333425338766341860983348309692998243289015442909620365263900067613009409717218816514258676437322125744209790095123709189541828478158286030084857
#print(f.bit_length())
#1024
#print(g.bit_length())
#768
iif=inverse(f,g)
#print(iif)
a=c*f%p%g
#print(a.bit_length())
m=a*iif%g
print(m)
#print(m.bit_length())
print(long_to_bytes(m))
#b'flag{c3bb1f88-2c0b-48fc-9902-beada6d50df6}'