# Lattice (格)

# 定义

给定一组线性无关的基向量$\vec{v_1},\vec{v_2},\cdots,\vec{v_n}$，那么这些基向量的所有整系数线性组合

$$V=\left\{a_1\vec{v_1}+a_2\vec{v_2}+\cdots+a_n\vec{v_n}\quad |\quad a_i\in \mathbb{Z}\right\}$$

形成的集合，就是这组基向量所张成的$\text{Lattice}$，对原基底进行整系数线性转换得到的新的基底，张成的$\text{Lattice}​$仍旧不变

$n$ 维空间中最简单的$\text{Lattice}$ 就是$\text{Integer Lattice}$(整数格)，可以向量成是一个空间中很多有规律分布、离散的点。

整数格中最简单的是基于笛卡尔坐标系的$\vec{x},\vec{y},\vec{z},\cdots​$等基向量组成的空间，一般记作$\Lambda=\mathbb{Z}^n​$

$\text{Lattice}$ 是$\mathbb{R}^n$ 这个空间中的一个离散的、具有加法运算的子群

# 格基规约

一个格可能有多个基，但并不是每个基的性质都是很好，我们认为长度短并且接近正交 (即内积接近$0$) 的基是好的基，可以使用$LLL$ 算法来进行格基规约，获得一个性质比较好的基

假设$A$ 和$B$ 是格$\mathbb{L}$ 上的两个基，则存在一个幺模矩阵$C$，使得$A=CB$

比较好的入门视频

# 相关属性

# 最短距离

一般用$\lambda_1$ 来定义这个格中点与点之间的最短距离，一般取定其中一个点为原点，则

$$\lambda_1=\min_{x,y\in V,x\ne y}(||x-y||)\\ =\min_{x\in V,x\ne \vec{0}}||x||$$

于是也有第$2,3,4,\cdots,n$ 近的点，并且满足$\lambda_1\le\lambda_2\le \cdots\le \lambda_n$

# 距离函数与覆盖半径

给定任意一个点$p$ (不需要在格上)，定义$\mu(p,V)$ 为这个点到附近的$\text{Lattice}$ 点的距离，即$\mu(p,V)=\min_{x\in V}||p-x||$

如果改变$p$ 的位置，可能会得到另一个不同的$\mu$ 值，定义最大可能取到的$\mu$ 值叫做覆盖半径 (最小中的最大，有二分的味道)

# 格中的难题

• $\text{SVP}$(最短向量问题)：给定$\text{Lattice}$ 和基向量，找到$\text{Lattice}$ 中的一个长度最短的非零向量
• $\text{CVP}$(最近向量问题)：给定$\text{Lattice}$ 和基向量，以及连续空间任意一个不在$\text{Lattice}$ 上的点，找到$\text{Lattice}$ 中一个距离点向量最近的格点

# SVP 问题

常见的求解$\text{SVP}$ 问题的算法是$\text{LLL}$ 格基约简算法

# CVP 问题

常见的求解$\text{CVP}$ 问题的算法是$\text{Babai}$ 算法

$\text{Babai}$ 是以$\text{LLL}$ 算法为基础的，因为$\text{Baiba}$ 算法需要在性质较好的规约基上运行。

# 相关例题 (Cryptohack 上 Lattice 部分)

# Problem1

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}')

已知$q$、$h$ 和$e$，其中$q$ 的二进制位数是$512$

加密过程可公开情报：

• e\equiv rh+m \mod

解密过程可公开情报：

• $a\equiv fe\mod q$
• m\equiv af^{-1}\mod

密钥生成过程：

• $h\equiv f^{-1}g\mod q$
• $f、g$ 的二进制位数在$256$ 左右

想要解密，需要知道$f$ 和$g$，而只有$h\equiv f^{-1}g\mod q$ 描述了$f$ 和$g$ 的关系，所以只能从这里入手

变形得到$hf+kq=g​$，因此我们可以把$g​$看做$h​$和$q​$的线性组合得到的，由于$h​$和$q​$已知，所以$(f,g)​$在$(1,h)​$和$(0,q)​$张成的格上，令$M=\left[ \begin{matrix} 1 & h \\ 0 & q\end{matrix}\right]​$，则有

$$\left[\begin{matrix}f&k \end{matrix}\right]\left[ \begin{matrix} 1 & h \\ 0 & q\end{matrix}\right]=\left[\begin{matrix}f&g \end{matrix}\right]$$

由于$h、g​$是$512​$位，而$f、g​$是$256​$位，所以$(f,g)​$的长度远小于$(1,h)​$和$(0,g)​$的长度，所以可以认为$(f,g)​$就是这个格的最短向量，即$SVP​$问题，用高斯算法二维求解即可

# Solve

def Guass(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

q,h=

v1,v2=vector([1,h]),vector([0,q])

f,g=Guass(v1,v2)

m=decrypt(q,h,f,g,e)

#crypto{Gauss_lattice_attack!}

# Problem2

import random

from collections import namedtuple

import gmpy2

from Crypto.Util.number import isPrime, bytes_to_long, inverse, long_to_bytes

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

PrivateKey = namedtuple("PrivateKey", ['b', 'r', 'q'])

def gen_private_key(size):

    s = 10000

    b = []

    for _ in range(size):

        ai = random.randint(s + 1, 2 * s)

        assert ai > sum(b)

        b.append(ai)

        s += ai

    while True:

        q = random.randint(2 * s, 32 * s)

        if isPrime(q):

            break

    r = random.randint(s, q)

    assert q > sum(b)

    assert gmpy2.gcd(q,r) == 1

    return PrivateKey(b, r, q)

def gen_public_key(private_key: PrivateKey):

    a = []

    for x in private_key.b:

        a.append((private_key.r * x) % private_key.q)

    return a

def encrypt(msg, public_key):

    assert len(msg) * 8 <= len(public_key)

    ct = 0

    msg = bytes_to_long(msg)

    for bi in public_key:

        ct += (msg & 1) * bi

        msg >>= 1

    return ct

def decrypt(ct, private_key: PrivateKey):

    ct = inverse(private_key.r, private_key.q) * ct % private_key.q

    msg = 0

    for i in range(len(private_key.b) - 1, -1, -1):

         if ct >= private_key.b[i]:

             msg |= 1 << i

             ct -= private_key.b[i]

    return long_to_bytes(msg)

private_key = gen_private_key(len(FLAG) * 8)

public_key = gen_public_key(private_key)

encrypted = encrypt(FLAG, public_key)

decrypted = decrypt(encrypted, private_key)

assert decrypted == FLAG

print(f'Public key: {public_key}')

print(f'Encrypted Flag: {encrypted}')

'''

flag:272bit

'''

背包问题介绍：假设$m$ 是信息，$A=(a_1,a_2,\cdots,a_n)$ 是$n$ 个不同正整数构成的$n$ 元组，称为背包向量，是公开信息，将$m$ 写成二进制形式，分块，每块的大小为$n$，长度不够补$0$。每块单独加密，加密方式为$\sum_{i=1}^nbit_ia_i$。

超递增背包问题：破译的基本思想是不必找出正确的模数$q$ 和数乘$r$ (即陷门信息)，只需找到任意模数$k^{'}$ 和乘数$t^{'}$ 对公开的背包向量$b​$求出新的超递增向量即可

构造如下格

$$A=\left[ \begin{matrix} 2 & 0 & 0 & \cdots & 0 & pub_0\\ 0 & 2 & 0 & \cdots & 0 & pub_1\\ 0 & 0 & 2 & \cdots & 0 & pub_2\\ \vdots & \vdots & \vdots &\ddots &\vdots &\vdots\\ 0 & 0 & 0 & \cdots & 2 & pub_n\\ 1 & 1 & 1 & \cdots & 1 & enc \end{matrix} \right]$$

计算$A.LLL()$，然后在每一行中寻找符合要求的即可

令$v_i$ 为$A$ 的第$i$ 个行向量，$x=(x_1,x_2,\cdots,x_n)$ 是明文，则$L=\sum_{i=1}^nx_iv_i-v_{n+1}=(2x_1-1,2x_2-1,\cdots,2x_n-1,0)$

所以最后求出答案的话，里面一定只有$1、-1、0$ 三个元素，并且只有最后一个元素是$0$，因为$x$ 是二进制形式的，所以特判每一行的元素种类即可。如果是$-1$，$x_i$ 是$1$，如果是$1$，$x_i$ 是$0$

# Solve

from Crypto.Util.number import getPrime, inverse, bytes_to_long,long_to_bytes

pk=[]

enc=

nbit = len(pk)

# N = nextprime(gmpy2.iroot(nbit,2)[0]//2)

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

#crypto{my_kn4ps4ck_1s_l1ghtw31ght}

# Problem3 (待补)(NTRU 相关)

# HNP 问题

问题描述：在一个素数域$\mathbb{Z}_q$ 上，恢复一个数$\alpha$ 使得对于多个已知随机数$t$，$t\alpha$ 的高位是已知的

其构造的格一般由以下形式

$$vM= \left[ \begin{matrix} l_1 & l_2 & \cdots & l_t & x &1 \end{matrix} \right] \left[ \begin{matrix} q\\ & q\\ & & \ddots\\ & & & q\\ A_1& A_2& \cdots & A_t & \frac{K}{q}\\ B_1& B_2& \cdots & B_t & & K \end{matrix} \right] = \left[ \begin{matrix} k_1 & k_2 & \cdots & k_t & \frac{Kx}{q} &K \end{matrix} \right]=v^{'}$$

一般我们需要使得$v^{'}$ 中每个分量的长度都很接近，并且尽量小。而$K$ 一般是我们需要泄漏的数的最大值，比如位数是$n$，一般取$2^n$，当然，有时候也需要根据$q$ 和$x$ 的位数来决定。其中$x$ 一般是密钥，未知

# 例题

LCG 同余随机数生成器：$s_i\equiv (s_{i-1}\times a+b)\mod{n}​$，其中$s_0=seed​$

题目已知$a、b、m$，其中$m$ 是$128$ 位的，并且给了$20$ 组$(s_i>>64)$ 位的值即$s_i$ 高$64$ 位的值

考虑把$s_i$ 拆成高$64$ 位和低$64$ 位，$s_i=h_i+l_i$

则有

$$l_2\equiv al_1+ah_1+b-h_2\pmod{m}\\ l_2\equiv A_1l_1+B_1\pmod{m} \ 其中，A_1=a,B_1=ah_1+b-h_2$$

依次类推，可以得到

$$l_i\equiv A_{i-1}l_1+B_{i-1}\pmod{m}\\ A_i=aA_{i-1}\ (A_0=1)\\ B_i=aB_{i-1}+ah_i+b-h_{i+1}\ (B_0=0)$$

变形可得

$$l_i=A_{i-1}l_1+B_{i-1}+k_im\\ vM= \left[ \begin{matrix} k_1 & k_2 & \cdots & k_{19} & l_1 &1 \end{matrix} \right] \left[ \begin{matrix} m\\ & m\\ & & \ddots\\ & & & m\\ A_1& A_2& \cdots & A_{19} & 1\\ B_1& B_2& \cdots & B_{19} & & 2^{64} \end{matrix} \right] = \left[ \begin{matrix} l_2 & l_3 & \cdots & l_{19} & l_1 & 2^{64} \end{matrix} \right]=v^{'}$$

由于$m$ 是$128$ 位的，所以可以认为$64$ 位的数在这个格上是很小的，因此使用$LLL$ 算法得到$v{'}$ 后可以得到$l_1$，从而可以得到$s_1$，求的$s_0$ 即$seed$

给出 sage 代码

for i in range(len(h)):

    h[i]<<=64

A=[1]

B=[0]

for i in range(1,len(h)-1):

    A.append(a*A[i-1]%m)

    B.append((a*B[i-1]+a*h[i]+b-h[i+1])%m)

A=A[1:]

B=B[1:]

print(len(A))

M=matrix(ZZ,21,21)

for i in range(19):

    M[i,i]=m

    M[19,i]=A[i]

    M[20,i]=B[i]

    M[i,19]=M[i,20]=0

M[19,19]=1

M[20,20]=2^64

M[19,20]=0

v1=M.LLL()[0]

l1=v1[-2]

h1=h[1]

s1=l1+h1

seed=((s1-b)*inverse_mod(a,m))%m

print(seed)