Gauss格基约简算法

由Gauss提出的二维格基约化算法

算法伪代码

即对给定的两个基向量进行不断的相互约化，最终求得格上的最小向量

Loop

1. If ||v2|| < ||v1||, swap v1, v2

2. Compute m = ⌊ v1∙v2 / v1∙v1 ⌉

3. If m = 0, return v1, v2

4. v2 = v2 - m*v1

Continue Loop

代码实现

#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即为格上最短向量

例题

import numpy as np
from Crypto.Util.number import getPrime, inverse, bytes_to_long,long_to_bytes
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、h，以及明文e

要求私钥f、g

他们之间有如下关系：

fh ≡ g mod q

即 kq + g =fh

g = fh -kq 根据这一特点即可构造格，也就是格密码中很经典的，遇到一个向量乘矩阵，即可进行构造

由于存在一组a、b，使得a（1，h）+ b（0，q）=（f，g）\(a(1,h) + b(0,q) = (f,g)\)

a = f，b = k

选取一组基底为（1，h）和（0，q），也就是上述高斯约简算法当中的v1与v2，求出v1与v2格上最小的向量，即为（f，g）

EXP

q = 7638232120454925879231554234011842347641017888219021175304217358715878636183252433454896490677496516149889316745664606749499241420160898019203925115292257
h = 2163268902194560093843693572170199707501787797497998463462129592239973581462651622978282637513865274199374452805292639586264791317439029535926401109074800
e = 5605696495253720664142881956908624307570671858477482119657436163663663844731169035682344974286379049123733356009125671924280312532755241162267269123486523
u = np.array([1,h])
v = np.array([0,q])
gauss_reduction(u,v)
f = 47251817614431369468151088301948722761694622606220578981561236563325808178756
g = 43997957885147078115851147456370880089696256470389782348293341937915504254589
m = decrypt(q,h,f,g,e)
print(long_to_bytes(m))
#crypto{Gauss_lattice_attack!}