sagemath lattices 隨筆

, , , ,

Before all

絕對不承認這些都是CryptoHackㄉ題目
就晾在這邊owob
遇到坑了？ 

1
preparse("PR.<X> = PolynomialRing(F)")

Note

Vector

指派變數 

1
v0 = vector([4,1,3,-1])

內積 

1
v.dot_product(w)

Matrix

指派變數 

1
M = Matrix([v0,v1,v2,v3])

算行列式值 

1
det(M)

Gram Schmidt
所以我說Gram Schmidt是什麼ㄋ？
Gram Schmidt就是透過給定矩陣算出另一個矩陣滿足：
1.裡面都是單位向量
2.span跟給定矩陣一樣 

1
M.gram_schmidt()

Gaussian Reduction

Shortest Vector Problem (SVP)：
在lattice L裡面找到大小最小的向量v

Closest Vector Problem (CVP)：
給一個不在lattice L裡面的向量，從L裡面找最接近那隻向量
Gaussian Lattice Reduction
把兩個向量大小給壓小，保持相同Lattice。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def size(x):
    cnt=0
    for i in x:
        cnt+=i**2
    return sqrt(cnt)

def gaussian_lattice(v1, v2):
    while True:
        if(size(v2)<size(v1)):
            v1, v2=v2, v1
        m=int(v1.dot_product(v2)/v1.dot_product(v1))
        if m==0:
            return(vector(v1), vector(v2))
        v2=v2-m*v1

Backpack Cryptography

CTF WIKI-背包加密
完ㄌ我打完這題就好懶得寫(X)
總之就是LLL可以取逼近，改天試試看一般的dp戳不戳得了owob 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from output import *
from Crypto.Util.number import *
nbit = len(pk)
A = [[0] * (nbit+1) for _ in range(nbit+1)]
for i in range(nbit):
    A[i][i] = 2
    A[i][-1] = pk[i]# *N
    A[-1][i] = 1

A[-1][-1] = int(enc)# *N

A = Matrix(ZZ,A)
r = A.LLL()
for i in r:
    if len(set(i[:-1])) == 2:
        F = i
        print(long_to_bytes(int(''.join(str(i) for i in [1 if i == -1 else 0 for i in F][::-1]),2)))