格密码

LLL算法

1. 简介：LLL算法用于解决最短向量问题的多项式时间复杂度算法。

LLL算法解释

对格的认识

不同的基也可以生成同一个格。

例如一个基向量是（1,0)和（0，1）构成的格。该格用数学符号表示。

格的维数:即向量的个数，上述表示的是一个二维的格。

然后根据系数a的不同就能得到不同的L集合。

假定现在v1,v2,v3…vn(称为张空间) 是格L的基，让存在不同个集合属于L 即w1 w2 …,wm。

可以转化位矩阵运算。

AV=W

线性无关（linearly independence）v1 , v2 , … , vn线性无关，当且仅当方程a1v1+…+anvn=0的唯一解是a全部为0；否则线性相关（linearly dependent）

正交基（orthogonal basis）v1 , v2 , … , vn 中任意不同的两个v点积的结果为0

规范正交（orthonormal） 上面的每一个v的**欧几里得范数(类似于模 长度)**为1

据此在上面的w的||w||2 = 所有系数a的平方和

A(转置)=(a1,a2…,an) V=(v1,v2…,vn) w=(w1,w2..,wn)

AV=W;

示例一个有关向量的问题

选定基向量生成格L:

化作行矩阵

将设L的某向量组：

其系数a形成向量组U=

W(转置)=（w1,w2,w3).

W=A*U

操作代码

#sage
v1 = [2, 1, 3]
v2 = [1, 2, 0]
v3 = [2, -3, -5]

A= matrix([v1, v2, v3])
print(A)
U=matrix([[1, 0, 1], [1, -1, 2], [1, 2, 0]])
print(U)
print(U.det())
W=A*U
print(W)
int_U=U.inverse()#求矩阵的逆
print(".............")
print(int_U)
assert int_U*W==A

SVP(最短向量问题)

一个格会有无数多个向量集合v

最短向量问题，指的格L中最短的非零向量，即寻找一个v满足欧几里得范数最小（指的该集合每一个元素的平方和再开平方，类似于模的长度）范数就是长度。

1. 基：

在向量空间的每一个点，都可以通过对基的线性组合变化得到，叫做基向量

一个格可能会有很多个基 不唯一

2. 正交基：

基相互垂直，就是正交基

3. 格基约规

random basis也是一组基，可以构成这个格子中的所有点 但是不是正交基

通过LLL或BKZ算法 得到正交基或者是最接近正交基，我们通过到他们，在之中

Cvp(最近向量问题)—不是很能理解这里先留着

接下来实战一些格的题

hermite 定理

给出最短向量的上限。

2024极客大挑战

from Crypto.Util.number import *

flag = b'******'
m = bytes_to_long(flag)

assert m.bit_length() == 327
p = getPrime(1024)
a = getPrime(1024)
c = getPrime(400)

b = (a*m + c) % p

print(f'a = {a}')
print(f'b = {b}')
print(f'p = {p}')

'''
a = 169790849804323540946197204708402762862586197604183102589270741859708550301920348112941305999764092197996929298474590062625556806793613268527763774013772685954699561684244945434843656515307801882995934869499880288594142919381501796488815033294127591623260894764750214588993456840404443515671353802614450411717
b = 87985708831523238980948938165414984318379459926002798504435964538203443877988599888615810231215118828138306895572062833107988965151522391460216837691927960249874511818878134399363147008042562222910234739940697553852540265617603482995091203105040187460485673579382171260197291783748886765929376179151804062085
p = 131724494512065658801039766546788821718063963144467818735768040631367069153816254855229655449559099188694403260044990366292026916085340250077198735215774149087025577263769846650728593180101073940507285459917860726551385227481715873503612683249433020201729190862430476054822102865441136763977415824331858801617
'''

已知a,b,p。

接下来构造函数

b=am+c-kp

c=b+kp-am

m=0+m+0

1=[1,0,0]

[1,m,k]*[1,0,b//0,1,-a//0,0,p]=[1,m,c]

如果m和c远远小于a,b,p则[1,m,c]可视为最短向量,通过求出最短向量即可求出m和c。但是这里[1,0,b]不能确定是否一定比[1,m,c]大很多，所以我们可以先尝试

这里构造出来，$b-a*m +kp = c$
$$(1\quad m\quad k )\begin{bmatrix}1&0&b\0&1&-
a\0&0&p\end{bmatrix}=\begin{pmatrix}1&m&c\end{pmatrix}$$
$||\mathbf{v}||=\sqrt{1+|m|2+|c|2}\approx2^{401}>|p|{1/3}=2^{341}$
补个$2^{200}$
|V|<=|p|*1/3，并且大小接近，但是为了它解决一些问题（我也不知道是啥），但是加了ZZ之后早格的范围变大了一些。

from Crypto.Util.number import *

a = 169790849804323540946197204708402762862586197604183102589270741859708550301920348112941305999764092197996929298474590062625556806793613268527763774013772685954699561684244945434843656515307801882995934869499880288594142919381501796488815033294127591623260894764750214588993456840404443515671353802614450411717
b = 87985708831523238980948938165414984318379459926002798504435964538203443877988599888615810231215118828138306895572062833107988965151522391460216837691927960249874511818878134399363147008042562222910234739940697553852540265617603482995091203105040187460485673579382171260197291783748886765929376179151804062085
p = 131724494512065658801039766546788821718063963144467818735768040631367069153816254855229655449559099188694403260044990366292026916085340250077198735215774149087025577263769846650728593180101073940507285459917860726551385227481715873503612683249433020201729190862430476054822102865441136763977415824331858801617


M = matrix([[2^377,0, b], [0,1, -a],[0,0,p]])
L = M.LLL()[0]

print(long_to_bytes(L[1]))

#b'SYC{1e989433efffd767589e989ad0f091075c06}'

easyLattice

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     
"""

造格，(2p)**1/2>=(f^2+ g^2) ^1/2 不成立，所以我们需要配平，对h和p同时乘256如下

from Crypto.Util.number import *
import gmpy2
h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947     
b=2^256
L=matrix(ZZ,[[1,b*h],[0,b*p]])
print(L.LLL()[0])
f,g=L.LLL()[0]
f=abs(f)
print(long_to_bytes(f)
’‘’
(-50073894085033274448337202692453522746880698077702322983028272289946704698284083256500537353714697134260425361796, -29555150073396592208680335494684523983684143293301981158157800432304888982432677680588686983225737089584138075242496)
b'SICTF{e3fea01c-18f3-4638-9544-9201393940a9}A\xf0\x89\x84'
‘’‘