发表于 更新于

前提

结合前面的vectors Twisted Hessian,这里应该还是有一个题做基础的，SVP（维数控制在4以下）和CVP问题
Gauss格基简约算法
即对给定的两个基向量进行不断的相互约化，最终求得格上的最小向量

If∣∣v2∣∣<∣∣v1∣∣,swapv1,v2If ||v2|| < ||v1||, swap v1, v2
Computem=⌊v1∙v2/v1∙v1⌉Compute m = ⌊ v1∙v2 / v1∙v1 ⌉
Ifm=0,returnv1,v2If m = 0, return v1, v2
v2=v2−m∗v1v2 = v2 - m*v1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#python
import numpy as np
def e_norm(a):
    n = len(a)
    s = 0
    for i in range(n):
        res = a[i] * a[i]
        s += res
    return s

def gauss_reduction(v1, v2):
    while True:
        v1_enorm = e_norm(v1)
        v2_enorm = e_norm(v2)
        if v1_enorm > v2_enorm:
            v1, v2 = v2, v1
            v1_enorm, v2_enorm = v2_enorm, v1_enorm
        m = np.dot(v1, v2) / v1_enorm
        m = int(round(m))
        if m == 0:
            print("v1:" + str(v1))
            print("v2:" + str(v2))
            return True
        else:
            v2 = v2 - np.dot(m, v1)
#最后输出的两个向量，v1即为格上最短向量

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from Crypto.Util.number import getPrime, inverse, bytes_to_long
import random
import math

FLAG = b'crypto{?????????????????????}'


def gen_key():
    q = getPrime(512)
    upper_bound = int(math.sqrt(q // 2))
    lower_bound = int(math.sqrt(q // 4))
    f = random.randint(2, upper_bound)
    while True:
        g = random.randint(lower_bound, upper_bound)
        if math.gcd(f, g) == 1:
            break
    h = (inverse(f, q)*g) % q
    return (q, h), (f, g)


def encrypt(q, h, m):
    assert m < int(math.sqrt(q // 2))
    r = random.randint(2, int(math.sqrt(q // 2)))
    e = (r*h + m) % q
    return e


def decrypt(q, h, f, g, e):
    a = (f*e) % q
    m = (a*inverse(f, g)) % g
    return m


public, private = gen_key()
q, h = public
f, g = private

m = bytes_to_long(FLAG)
e = encrypt(q, h, m)

print(f'Public key: {(q,h)}')
print(f'Encrypted Flag: {e}')

Public key: (7638232120454925879231554234011842347641017888219021175304217358715878636183252433454896490677496516149889316745664606749499241420160898019203925115292257, 2163268902194560093843693572170199707501787797497998463462129592239973581462651622978282637513865274199374452805292639586264791317439029535926401109074800)
Encrypted Flag: 5605696495253720664142881956908624307570671858477482119657436163663663844731169035682344974286379049123733356009125671924280312532755241162267269123486523

能确定q 512位，f,g小于q,以及
h≡gh−1 mod qh\equiv gh^{-1}\,mod\,q
e≡(rh+m) mod qe\equiv(rh+m)\,mod \,q
这样没法直接推出密文m，看到还有一个decrypt函数没有用,所有往后应该就是求出未知的f和g
lattice，用基向量定义基本空间
g=fh−kqg=fh-kq
选定一组基底为(1,h),(0,q)

(1h0q)\begin{pmatrix} 1&h\\ 0&q\\ \end{pmatrix}

使得a(1,h)+b(0,q)=(f,g)a(1,h)+b(0,q)=(f,g)
存在a=fb=−k满足条件a=f b=-k满足条件
呈线性相关,所以(f,g)(f,g)这个向量在这个lattice上

1
2
3
4
v1:[47251817614431369468151088301948722761694622606220578981561236563325808178756
 43997957885147078115851147456370880089696256470389782348293341937915504254589]
v2:[-67269010250212717075432182693043963184097648880165008621907831284647116025901
 99012763459529858809608436133564630524350106000242070336818304053467942269178]

看出第一个符合f,g，带入函数decrypt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 import gmpy2
from Crypto.Util.number import long_to_bytes

def decrypt(q, h, f, g, e):
    a = (f*e) % q
    m = (a*gmpy2.invert(f, g)) % g
    return m
q=7638232120454925879231554234011842347641017888219021175304217358715878636183252433454896490677496516149889316745664606749499241420160898019203925115292257
h=2163268902194560093843693572170199707501787797497998463462129592239973581462651622978282637513865274199374452805292639586264791317439029535926401109074800
e=5605696495253720664142881956908624307570671858477482119657436163663663844731169035682344974286379049123733356009125671924280312532755241162267269123486523
f=47251817614431369468151088301948722761694622606220578981561236563325808178756
g=43997957885147078115851147456370880089696256470389782348293341937915504254589
m=decrypt(q,h,f,g,e)
print(long_to_bytes(m))
#b'crypto{Gauss_lattice_attack!}'