格基础 | 烟虚境

之前是浅尝辄止，没有体会到格的意味，重新学一遍，果然眉目又清晰了不少。

格运算(线性代数相关)

有基向量v_1,v_2,v_3构成三维向量空间，这个向量空间中任一向量都可由这三个基向量的线性组合表示，

在格中，要求其中每个向量都能由其基向量的整系数线性组合表示，也就是说，用来表示格中任一向量的每个基向量前的系数必须为整数。

最基础的

$v_1=(2,1,3),v_2=(1,2,0),v_3=(2,-3,-5)\\ 设A=(v_1,v_2,v_3)^T\\ 格中任一向量都能由此向量组的整系数组合表示\\ 有L中其他三维向量组：\\ w_1=v_1+v_3,w_2=v_1-v_2+2v_2,w_3=v_1+2v_2\\ 也就是w_1=A*(1,0,1),w_2=A*(1,-1,2),w_3=A*(1,2,0)\\ 设W=(w_1,w_2,w_3)^T\\$

有A（1 0 1 =W，设A U=W,有A=W *A{-1}
1 -1 2
1 2 0）

$设A *U=W,有A=W *A^{-1}$

SVP最短向量问题

在格L中存在无数多个不同的向量，而最短向量问题就是指找出这个格L中最短的非零向量，即寻找这个格中欧几里得范数(该集合的每一个元素的平方和再开方)最小,范数就是指长度。

那我们该如何找到这个最短向量呢？

先从简单的栗子出发

由向量v_1=（0,1）和v_2=（1,0）张成的格，由于其他向量都是这两个向量的整系数线性组合，即a=2v_1+1 v_2,b=2 v_1+0v_2，无论是（2,1）还是（2,0），只要系数是整数，必然系数>=1,（我们可以放到向量空间里去理解，任一向量都能看成是在v_1方向上延伸k倍在加上在v_2方向上延伸m倍，而m,k恒大于等于1）所以对于v_1和v_2来说，没有比他们前面的系数1更小的了，他俩就是最短向量。

扩展开来，由于格中基向量可以是任意的，那么有可能此基向量非正交（正交在空间中理解就是向量互相垂直）

首先我们要明白两个关系：

假设v不是基中的向量，此刻该向量一定可以通过在其他基向量方向的投影来得到一个更短的向量。（非正交的向量比正交向量长）
假设v是这个基中的某个向量，在其他向量上的投影长度为0（正交向量是短向量）

所以求任意格中最短向量问题的通用解法就出来了

若v不是基中向量，通过LLL算法得到正交基或者是最接近正交基，最短向量就在这组正交基上。

若是，那最短向量就在这组基上。

现在思考我们为什么要找到这个最短向量？

对于像

的式子，我们考虑它的几何意义，（以下左边右边指等号左边两向量的相对位置）

左边乘以右边相当于将左边的向量放在了右边向量组构成的向量空间里，而左边的向量也变成了这个向量空间中的向量。

如果右边是个足够大的向量空间，而等式右边的向量是个足够小的向量，那这就是SVP问题了。

做法：若（1,0)和（h,p）不正交，则需使用LLL算法将其正交化并找到其中最短向量，就是（f,g)，

看题：

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

assert len(flag) == 47

f = bytes_to_long(flag)
p = getPrime(512)
g = getPrime(128)
h = gmpy2.invert(f, p) * g % p

print('h =', h)
print('p =', p)

"""
h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947     
"""

要求f,看出f相对于512bits的p和h是微不足道的，就转化成SVP问题找到最短向量，就得到f。

但是

最短向量是有上界的，根据

Hermite定理：

n表示维数，即基向量的个数。

Hermite测试脚本

import gmpy2
from Crypto.Util.number import *

b = 2 ** 0#有时候需要调整b的值
flag = b'flag{Do_you_like_Laooooooo00000ooottice?Addoil}'
print(len(flag))
f = bytes_to_long(flag)
print(f.bit_length())  
p = getPrime(512)
g = getPrime(128)
g = g

#行列式的值
temp = gmpy2.iroot(2 * b * p, 2)[0]  
print(temp.bit_length()) 

#最短向量的值
temp2 = gmpy2.iroot(f**2+(b*g)**2, 2)[0]  #主要在于f g没有太大影响

print(temp2.bit_length())

当b=1时，有357>257,超过上界，此时我们对b的值进行调整，

b=2^256时满足Hermite定理，进行求解。

def GaussLatticeReduction(v1, v2):
    while True:
        if v2.norm() < v1.norm():
            v1, v2 = v2, v1
        m = round( v1*v2 / v1.norm()^2 )
        if m == 0:
            return (v1, v2)
        v2 = v2 - m*v1

h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947     
c = 6388077150013017095358415295704360631706672647932184267739118115740221804173068089559645506533240372483689997499821300861865955720630884024099415936433339512125910973936154713306915269365877588850574948033131161679256849814325373882706559635563285860782658950169507940368219930971600522754831612134153314448445006958300840618894359885321144158064446236744722180819829183828290798747455324761671198097712539900569386477647697973195787663298318786718012522378981137877863153067057280649127202971806609339007027052518049995341356359016898069863799529357397514218249272201695539181908803360181347114492616706419618151757
print(h.nbits(),p.nbits())
D = 2^256  #配平数与位数相关 需要学习补充 237-256次方均可解
# Construct lattice.
v1 = vector(ZZ, [1, D * h])
v2 = vector(ZZ, [0, D * p])
m = matrix([v1,v2]);

import libnum

# Solve SVP.
shortest_vector = m.LLL()[0]
f, g = shortest_vector
print(f, g)
#BKZ
L = m.BKZ(block_size=2)
shortest_vector = L[0]
f, g = shortest_vector
print(f, g)
print(libnum.n2s(int(abs(f))))
import gmpy2
#验证
print(QQ((f**2+g**2)**0.5))
print(QQ((p/2)**0.5))

https://blog.csdn.net/jayq1/article/details/140872034