格密码

寒假自学了一部分格的知识点，但是感觉自己知识匮乏有些内容难以理解，现在有了一定的知识支撑再重新温习一遍。

线性代数知识

线性空间又叫向量空间。

向量

向量是空间上的一个点，或者从原点引出指向这个点的箭头，用坐标来表示这个向量。

设两个向量：
$$
a=(a_0,a_1,…,a_{n-1})
$$

$$
b=(b_0,b_1,…,b_{n-1})
$$

向量加：
$$
a+b=(a_0+b_0,a_1+b_1,…,a_{n-1}+b_{n-1})
$$
点乘（将向量看做矩阵，也可以理解为前面横向量乘以后面列向量）：
$$
a\cdot b=\sum^{n-1}_{i=0}a_i\cdot b_i
$$

$$
a\cdot b=ab^T=\begin{bmatrix}
a_0 & … & a_{n-1}
\end{bmatrix}
\begin{bmatrix}
b_0 \ … \ a_{n-1}
\end{bmatrix}
=\sum^{n-1}_{i=0}a_i\cdot b_i
$$

向量还有长度，长度就是这个点到空间原点的距离，写为：
$$
||x||=\sqrt{<x,x>}=\sqrt{\sum^n_{i=1}x^2_i}
$$

矩阵

矩阵相当于同元素数量向量的堆叠。矩阵运算有加法和乘法，加法需要两个矩阵有相同的行数和列数，加法将对应位置元素相加。

对$A,B$做乘法是将$A$对应的行向量和$B$对应的列向量做点乘，能做乘法的矩阵前矩阵列数应等于后矩阵的行数。

矩阵乘法是不可逆的：$AB≠BA$。

线性组合

给定一些向量：
$$
B ={b_0,b_1,…,b_{n-1}}
$$
如果存在系数$a_0,a_1,…,a_{n-1}$，使得$v=\sum^{n-1}_{i=0}a_ib_i$，那么称$v$是$B$的线性组合，$v$向量可以用$B$中的向量通过加法和数乘组合得到。

对于线性方程组：
$$
\begin{cases}
a_{0,0}x_0+a_{0,1}x_1+…+a_{0,n-1}x_{n-1}=y_0\
a_{1,0}x_0+a_{1,1}x_1+…+a_{1,n-1}x_{n-1}=y_1\
…\
a_{m-1,0}x_0+a_{m-1,1}x_1+…+a_{m-1,n-1}x_{n-1}=y_{m-1}\
\end{cases}
$$
可以转化成矩阵和向量表示的线性方程组：
$$
\begin{bmatrix}
a_{0,0}&a_{0,1}&\cdots & a_{0,n-1}\
a_{1,0}&a_{1,1}&\cdots& a_{1,n-1}\
\vdots&\vdots&\ddots&\vdots\
a_{m-1,0}&a_{m-1,1}&\cdots& a_{m-1,n-1}\
\end{bmatrix}
\begin{bmatrix}
x_{0}\x_{1}\\vdots \ x_{n-1}\
\end{bmatrix}

\begin{bmatrix}
y_{0}\y_{1}\\vdots \ y_{n-1}\
\end{bmatrix}
$$
如果$B$中某个向量是其他向量的线性组合，那么$B$线性相关，否则$B$线性无关，通常我们会更想去构造线性无关。

格理论

定义1：格（$L$）是群$R^n$上的离散子群。

这里的群$R^n$为域$R$上的$n$维向量空间。

如果在域$F_R$上的$R^n$，满足对于$a\in R,\overrightarrow{v}\in R^n$：

1.$a\overrightarrow{v}\in R^n$

2.$a,b\in R,a(bR)=(ab)R$

3.$(a+b)\overrightarrow{v}=a\overrightarrow{v}+b\overrightarrow{v}$

满足这三个性质，这个群$R^n$就叫做一个向量空间。

对于”离散”这一概念，可以理解为”不连续“：

$\exists \epsilon>0,$使得$\forall\overrightarrow{v_1},\overrightarrow{v_2}\in L$有：
$$
||\overrightarrow{v_1}-\overrightarrow{v_2}||>\epsilon
$$

最常见的格：$Z^n$，例如$Z^2$就是生活中我们所说的格：横竖交叉的点，它们有最短距离，也满足离散的特点：
$$
\begin{matrix} 。 &。 & 。\ 。& 。 &。 \ 。 & 。 & 。 \end{matrix}
$$
定义2：既然是$R^n$上的子群，那么存在$n$维空间的格基，格可以用基来表示，基的这些向量可以张成整个线性空间（$k≤n$）：
$$
B=(\overrightarrow{e_1},\overrightarrow{e_2},…,\overrightarrow{e_n})
$$

$$
L(B)={B\cdot\overrightarrow{x}|\overrightarrow{x}\in Z^k}
$$

$$
span(B)=R^n
$$

也就是说，我们设$v_1,…,v_n\in R^m$是一组线性无关的向量，根据$v_1,…,v_n$生成的格就是指向量$v_1,…,v_n$的线性组合构成的向量集合（这里需要要求系数都在$Z$这个整环上）：
$$
L={a_1\overrightarrow v_1+a_2\overrightarrow v_2+…+a_n\overrightarrow v_n:a_1,…a_n\in Z}
$$
现在又有$w_1,…,w_n\in L$为格$L$的另一组向量，根据格的定义，可以将每一个$w$都写成基向量的线性组合形式（这里的系数$a$均为整数），同时得到系数矩阵$A$：
$$
\begin{cases}\mathbf{w_1}=a_{11}\mathbf{v_1}+a_{12}\mathbf{v_2}+…+a_{1n}\mathbf{v_n}\\mathbf{w_2}=a_{21}\mathbf{v_1}+a_{22}\mathbf{v_2}+…+a_{2n}\mathbf{v_n}\…\\mathbf{w_n}=a_{n1}\mathbf{v_1}+a_{n2}\mathbf{v_2}+…+a_{nn}\mathbf{v_n}\\end{cases}
$$

$$
A=\begin{bmatrix} a_{11}&a_{12}&…&a_{1n}\a_{21} &a_{22}&…&a_{2n}\…\a_{n1}&a_{n2}&…&a_{nn}\end{bmatrix}
$$

根据矩阵的性质：
$$
\mathrm{det}(AA^{-1})=\mathrm{det}(A)\mathrm{det}(A^{-1})=\mathrm{det}(I)=1
$$
这里生成逆矩阵是为了用$\mathbf{w}$来表示$\mathbf{v}$，所以要求这里的$A$和$A^{-1}$的元素都为整数，所以根据上面的公式有$\mathrm{det}(A)=±1$。反过来，如果有$\mathrm{det}(A)=±1$，而且$A$中全为整数，那么也能得知$A^{-1}$也由整数构成。

定理：格$L$的任意两个基可以通过在左边乘上一个特定的矩阵相互转化，这个矩阵由整数构成，且行列式值为$±1$。

所有向量坐标都为整数的格为整数格，当$m≥1$是，有$Z^{m}$为加法子群。下面的$Z^m$为所有向量坐标都为整数的格。
$$
Z^m={(x_1,x_2,…,x_m):x_1,…,x_m\in Z}
$$
若$L\subset R^{m}$是一个维度为$n$的格，那么它的基可以作为行向量构成一个$n×m$的矩阵$A(n≤m)$。由上面定理知：通过在矩阵$A$的左边乘上一个$n×n$的矩阵$U$可以得到一组新的基,其中$U$应由整数构成且行列式值为$1$。这样的$U$的集合称为（在$Z$上的）一般线性群，记为$GL_n(Z)$。这个群中的矩阵及它们的逆矩阵全部都是由整数构成的。

基础区域

设$L$为$n$维格，且$\mathbf{v_1},…,\mathbf{v_n}$为$L$的基，对应这个基的基础区域为：
$$
\mathcal{F}(\mathbf{v_1},…,\mathbf{v_n})={t_1\mathbf{v_1}+…+t_n\mathbf{v_n}:0≤t_i＜1}
$$
下图展示了一个二维格的其中一个基础区域：

定理：设$L\subset R^n$为$n$维格，$\mathcal{F}$为基础区域，那么对于任意向量$\mathbf{w}\in R^n$都存在唯一的$t\in \mathcal{F}$和唯一的$\mathbf{v}\in L$，满足$\mathbf{w}=\mathbf{t}+\mathbf{v}$，也就是有：
$$
\mathcal{F}+ \mathbf{v}={ \mathbf{t}+ \mathbf{v}: \mathbf{t}\in \mathcal{F}}
$$
如果$\mathbf{v}$范围为$L$中所有向量，那么上述基础区域$\mathcal{F}+ \mathbf{v}$可以完整覆盖所有$R^n$。

格的行列式

设$L$是$n$维格，$\mathcal{F}$是$L$的一个基础区域。$\mathcal{F}$的$n$维体积称为$L$的行列式（也称为协体积），记为$\mathrm{det}L$。

格本身没有体积，因为它只是一系列点的可数集合。

Hadamard不等式

$$
\mathrm{det}L=\mathrm{vol}(\mathcal{F})\leqslant\left | \mathbf{v_1} \right |\left | \mathbf{v_2} \right |…\left | \mathbf{v_n} \right |
$$

基向量越接近垂直，不等式越接近等式。

这里的一些理论可以用来解释线性代数的一些知识：

所谓的$n$阶矩阵求行列式也就是矩阵行向量组成的空间（基础区域）的体积。对于二维矩阵，求行列式的值可以给出由行向量所组成的平行四边形的有向面积。具体来说，对于二维矩阵A = [[a, b], [c, d]]，其行列式的值为$ad - bc$，这个值就代表了由行向量所组成的平行四边形的有向面积。

行列式的值为$0$表示行向量线性相关，即为行向量共线，无法构成有面积的空间。

设$L\subset R^n$为$n$维格，且$\mathbf{v_1},…,\mathbf{v_n}$为$L$的基，$\mathcal{F}=\mathcal{F}(\mathbf{v_1},\mathbf{v_2},…,\mathbf{v_n})$，将基向量写为坐标转化为矩阵的行向量：
$$
F=F(\mathbf{v_1},\mathbf{v_2},…,\mathbf{v_n})=\begin{bmatrix}r_{11}&r_{12}&…&r_{1n}\r_{21} &r_{22}&…&r_{2n}\…\r_{n1}&r_{n2}&…&r_{nn}\end{bmatrix}
$$
由此可得$\mathcal{F}$的体积：
$$
\mathrm{vol}(\mathcal{F}(\mathbf{v_1},\mathbf{v_2},…,\mathbf{v_n}))=|\mathrm{det}(F(\mathbf{v_1},\mathbf{v_2},…,\mathbf{v_n}))|
$$
推论：设$L\subset R^n$为$n$维格，那么它所有的基础区域都有相同的体积，所以$\mathrm{det}L$是格的不变量。

格基约减算法

二维格高斯约减

输入：格$L$的一组基$\mathbf{v_1,v_2}$。

输出：一组具有良好的正交性的基向量。

算法描述：

循环：

1.如果$|\mathbf{v_2}|＜|\mathbf{v_1}|$，交换$\mathbf{v_1,v_2}$。

2.计算$m=[\frac{\mathbf{v_1\cdot v_2}}{|\mathbf{v_1}|^2}]$

3.如果$m=0$，返回基向量：$\mathbf{v_1,v_2}$。

4.用$\mathbf{v_1}-m\mathbf{v_2}$替换$\mathbf{v_2}$，继续循环。

准确来说。当算法终止时，向量$\mathbf{v_1}$就是格中的最短非零向量。

代码实现：

def LLL(L):
    v1,v2=L[0],L[1]
    while 1:
        van1,van2=pow(v1[0],2)+pow(v1[1],2),pow(v2[0],2)+pow(v2[1],2)
        if(van2<van1):
            v1,v2=v2,v1
            van1,van2=pow(v1[0],2)+pow(v1[1],2),pow(v2[0],2)+pow(v2[1],2)
        m=round((v1[0]*v2[0]+v1[1]*v2[1])/van1)
        print(m)
        if m==0:
            return v1,v2
        v2=[v2[i]-m*v1[i] for i in range(2)]


L1=[[6513996,6393464],[66586820,65354729]]
print(LLL(L1))

sage实现：

def Gauss(x,y):
    v1 = x; v2 = y
    finished = False
    while not finished:
        m = round(( v2.dot_product(v1) / v1.dot_product(v1) ))
        v2 = v2 - m*v1
        if v1.norm() <= v2.norm():
            finished = True
        else:
            v1, v2 = v2, v1
    return v1, v2

x=vector([6513996,6393464])
y=vector([66586820,65354729])
print(Gauss(x,y))

LLL格基约减

给定格$L$的一组基为${\mathbf{v}_1,\mathbf{v}_2,…,\mathbf{v}_n}$，对其进行约减，约减的主要目的就是将这组任意的基转化为正交性好的优质基，并且让这个优质基各个向量尽量最短。

施密特正交化

根据施密特正交化，可以构造出一组正交基：

先让$\mathbf{v}_1’=\mathbf{v}_1$，对于所有的$i≥2$，有：
$$
\mathbf{v}i’=\mathbf{v}i-\sum^{i-1}{j=1}\mu{i,j}\mathbf{v}j’(\mu{i,j}=\frac{\mathbf{v}_i\cdot\mathbf{v}_j’}{|\mathbf{v}_j’|},1≤j≤i-1)
$$
得到向量集合$B’={\mathbf{v}_1’,\mathbf{v}_2’,…,\mathbf{v}_n’}$正交基，张成的向量空间是$B={\mathbf{v}_1,\mathbf{v}_2,…,\mathbf{v}n}$，$B$为格$L$的一组基，有性质：
$$
\mathrm{det}L=\prod^n{i=1}|\mathbf{v}_i’|
$$
对于$B’$，有如下概念：

Size条件：$|\mu_{i,j}|=\frac{|\mathbf{v}_i\cdot\mathbf{v}_j’|}{|\mathbf{v}_j’|^2}≤\frac 12$对于所有$1≤j＜i≤n$都成立，两个基向量不要过小使得施密特正交化不会太小。

Lovász条件：Lovász条件保证了缩减不要太快，这个条件对于所有$1＜i≤n$都成立：
$$
|\mathbf{v}i’|^2=(\frac 34-\mu{i,i-1}^2)|\mathbf{v}{i-1}’|^2
$$
这个式子还等价于以下公式：
$$
|\mathbf{v}i’+\mu{i,i-1}\mathbf{v}{i-1}’|^2≥\frac 34|\mathbf{v}_{i-1}’|^2
$$

LLL算法

输入：格$L$的一组基${\mathbf{v_1,v_2,…,v_n}}$。

输出：LLL约减基。

算法描述：

输入${\mathbf{v_1,v_2,…,v_n}}$，令$k=2$，令$\mathbf{v}_1’=\mathbf{v}_1$。

当$k≤n$时循环：

1.循环$j=1,2,…,k-1$：使$\mathbf{v_k}=\mathbf{v_k}-[\mu_{k,j}]\mathbf{v_j}’$（size条件）

2.如果$|\mathbf{v}_k’|^2=(\frac 34-\mu_{k,k-1}^2)|\mathbf{v}_{k-1}’|^2$（满足Lovász条件）：令$k=k+1$，否则交换$\mathbf{v}_{k-1}$和$\mathbf{v}_{k}$且让$k=max(k-1,2)$。

当算法终止时，${\mathbf{v_1,v_2,…,v_n}}$为LLL约减基。

下面是sage实现LLL格基规约（sage里有L.LLL()可以进行格基规约）：

def max(a, b):
    return a if a > b else b

def LLL(M, delta=0.75):
    B = deepcopy(M)
    Q, mu = B.gram_schmidt()
    n, k = B.nrows(), 1
    while k < n:
        for j in reversed(range(k)):
            if abs( mu[k][j] ) > 0.5:
                B[k] = B[k] - round( mu[k][j] ) * B[j]
                Q, mu = B.gram_schmidt()
        if Q[k].dot_product(Q[k]) >= (delta - mu[k][k-1]^2) * Q[k-1].dot_product(Q[k-1]):
            k = k + 1
        else:
            B[k], B[k-1] = B[k-1], B[k]
            Q, mu = B.gram_schmidt()
            k = max(k-1,1)
        print(k)
    return B 

格的应用

格可用于构建密码协议，其安全性基于两个基本的问题：

最短向量问题（SVP）：在格$L$中找到一个最短的非零向量。在sage中有LLL、BKZ等算法方便求解最短向量，注意舍弃掉负值和大值。
最接近向量问题（CVP）：给定不在$L$中的向量$w∈R^m$，找到一个最接近$w$的向量$v∈L$，即找到向量$v∈L$，使得$||v-w||$最小化。

了解了格是怎么一回事之后，下面开始学习利用格的理论来解决密码问题。

最短向量问题

我们想要求解在一个格里的最短非零向量，这个值取决于格$L$的维度和行列式值。

Hermite定理

所有$n$维的格$L$都包含一个非零向量$\mathbf{v}\in L$，满足公式$|\mathbf{v}|≤\sqrt{n}\mathrm{det}(L)^{\frac 1n}$。

当为多种向量的情况，在$n$维格中存在一个基，存在：
$$
|\mathbf{v}_1||\mathbf{v}_1|…|\mathbf{v}_n|≤n^{\frac n2}\mathrm{det}(L)
$$
根据Hadamard不等式，可知：
$$
\mathrm{det}L≤|\mathbf{v}_1||\mathbf{v}_1|…|\mathbf{v}_n|≤n^{\frac n2}\mathrm{det}(L)
$$
由此，定义格的基$\mathcal{B}={\mathbf{v}_1,\mathbf{v}_2,…,\mathbf{v}_n}$的Hadamard比率：
$$
\mathcal{H(B)}=(\frac{\mathrm{det}L}{|\mathbf{v}_1||\mathbf{v}_1|…|\mathbf{v}_n|})^{\frac 1n}
$$
上式可知对于格的任何一个基，存在$0＜\mathcal{H(B)}≤1$，这个值越接近$1$，这个基中的向量越接近两两正交。

Hadamard比率的倒数（$\mathcal{H(B)}^{-1}$）被称作“正交缺陷”。

高斯启发式

启发式是什么？

大概理解为：证明不出它是对的，但是实际用起来效果很好。

在Hermite定理中提出了格的最短向量长度的上限，可以对这个定理进行进一步改进：

高斯启发式（Gaussian heurstic）：$L$为$n$维格，最短长度的高斯期望是$\sigma(L)=\sqrt{\frac{n}{2\pi e}}(det\ L)^{\frac 1 n}$。

高斯启发式可以衡量在格中寻找最短向量问题的难度，如果格中的最短向量长度约等于$\sigma (L)$，用格基约减算法可以找到最短向量。

超球体

超球体是高维空间的球体，这里需要用到它的容积。

设$B_R(a)$是一个以点$a$为圆心，半径为$R$的$n$维球体，那么它的容积为：
$$
Vol(B_R(a))=\frac{\pi^{\frac n2}R^n}{\Gamma(1+\frac n2)}
$$
看不懂是很正常的，通常用它的估算值。当维度足够大时：
$$
Vol(B_R(a))^{\frac 1n}=
\sqrt{\frac{2\pi e}n}R
$$
高斯认为一个以零点为圆心的超球体的格点数量可以用格基础区域的容积来估算：
$$
#{v\in L:||v||\leq R}\approx\frac {Vol(B_R(0))}{Vol(\mathcal{F})}
$$
将上式向量数量定为$1$，就可以估算包含一个格点的超球体半径，就是高斯启发式子的$\sigma(L)$，也就是找到了距离原点最近的向量。

同余密码系统

加解密原理

Alice选择一个大数$q$作为公共参数和另外两个秘密正整数$f,g$满足$f<\sqrt{\frac q2},\sqrt{\frac q4}＜g＜\sqrt{\frac q2}$，且$gcd(f,q)=1$。

计算$h\equiv f^{-1}g(\bmod q),0＜h＜q$，Alice的私钥是一对小整数$f,g$，公钥为大整数$h$。

Bob接收公钥，选择明文$m$和随机整数（临时密钥）$r$，同时也满足$0＜m＜\sqrt{\frac q4},0＜r＜\sqrt{\frac q2}$，计算密文$e=rh+m \bmod q$，发送密文。

Alice进行解密（第二个公式的$f^{-1}$是$f$模$g$的乘法逆元）：
$$
a\equiv fe(\bmod q)
$$

$$
b\equiv f^{-1}a(\bmod g)
$$

原理证明

需要证明$b=m$，可以直接看$a$：
$$
a\equiv fe\equiv f(rh+m)\equiv frf^{-1}g+fm=rg+fm(\bmod q)
$$
由于几个参数的范围限制导致$rg+fm$很小：
$$
rg+fm＜\sqrt{\frac q2}\cdot\sqrt{\frac q2}+\sqrt{\frac q2}\cdot\sqrt{\frac q4}\ll q
$$
所以实际得到的$a=rg+fm$，可以忽略模$q$的影响。
$$
b\equiv f^{-1}a\equiv m(\bmod g)
$$
注意到$0<b<g,m<\sqrt{\frac q4}<g$，就有$b=m$。

造格破解

我们通过造格可以得到私钥，根据以下向量造格：
$$
L=\begin{bmatrix}v_1\v_2\end{bmatrix}=\begin{bmatrix}1 & h\0 & q\end{bmatrix}
$$
向量$(f,g)$就在这个格上，根据$f,g$的取值能发现这个向量极有可能就是$L$中最短非零向量（可根据高斯启发式验证），即获得了私钥。

造格原理

上面我们通过实践知道了可以使用格去进行破解，那么是怎么构造出的这个格呢，拿上面的例子：

M = matrix(ZZ, [
  [1, h],
  [0, q]
])
L = M.LLL()  
f, g = L[0]
f = abs(f)
g = abs(g)

R = GF(q)
assert R(h) == R(f)^(-1) * R(g)

print('f = %d' % f)
print('g = %d' % g)

最终我们给出的格基是：
$$
L=\begin{bmatrix}1 & h\0 & q\end{bmatrix}
$$
因为$h\equiv f^{-1}g(\bmod q)$，消一下逆元，转成等式就是$g=fh-kq$，$k$为整数。

所以就有：
$$
h\cdot f-q\cdot k=g
$$
构造格基就是构造线性方程组，现在的方程里有两个未知数，一个式子肯定是求解不出来的，如果没有别的线索了可以尝试插入恒等式，如$f=f$：
$$
\begin{cases}1\cdot f-0\cdot k=f\
h\cdot f-q\cdot k=g\end{cases}
$$
就可以用矩阵表示，这里使用了横向量，改一下位置：
$$
\begin{bmatrix}f & -k\end{bmatrix}
\begin{bmatrix}1 & h\
0 & q
\end{bmatrix}

\begin{bmatrix}f & g\end{bmatrix}
$$
式子中的$f,-k$都是整数，有$w=(f,g)$是格基向量的整数线性组合，所以$w$是格中的一个格点。

我们有条件$f,g<\sqrt{\frac q2}$，估算一下长度：
$$
||w||=\sqrt{f^2+g^2}<\sqrt{\frac q2+\frac q2}=\sqrt q
$$

$$
\sigma(L)=\sqrt{\frac{1}{\pi e}}(\det(L))^{\frac 1 2}
\approx (\det(L))^\frac 12=\sqrt q
$$

满足$||w||\lessapprox \sigma(L)$，可以使用格基规约算法求得这个最短向量。通常，LLL规约后的第一个向量就是近似的最短向量，直接提取，验证是否正确就得解。

配平

实际应用中，还存在非常多不能这么轻松构造出符合条件的格基的情况，例如：

bits = 512
while True:
  q = random_prime(2^bits, lbound=2^(bits - 1))
  R = GF(q)
  f = R(random_prime(2^(3*bits//4 - 1)))
  g = R(random_prime(2^(bits//4 - 1)))
  if gcd(f, q*g) == 1:
    h = f^(-1) * g
    break

print('q = %d' % q)
print('h = %d' % h)
# q = 8114289192306045529468503816747459961749065015867824745830651826013976103158819451256549284151983553594151248484475469795886232064196980904146067875445697
# h = 838300814476084941348853046958667696551309880234911679429950542076545172518536842358788741627265361068496523434290150119253124253856647527559973827885148


# Aim: find f and g

在这个情况中，大小关系发生了变化，设bits为$l$，有$q\approx 2^l$：
$$
f\approx 2^{\frac 34 l-1}
$$

$$
g\approx 2^{\frac 14 l-1}
$$

如果我们还采用上面的格基进行求解，可以先测试一下$||w||,\sigma(L)$的关系：
$$
||w||\gtrapprox 2^{\frac 34 l-1}>\sqrt \frac q2
=\det(L)\approx \sigma(L)
$$
而$q\approx 2^l$，$ \sqrt\frac q2=2^{\frac{l-1}2}$，仔细想一想发现和$||w||$差的有点太多了。

在这个题目中，由于$f$比$g$大太多，所以可以认为是$f$把向量$w$拉长了，所以有一个方法就是扩大$g$的位置，可以设$f\approx Dg$，大概能得到$D\approx 2^{\frac l2}$，修改线性方程组：
$$
\begin{bmatrix}f & -k\end{bmatrix}
\begin{bmatrix}1 & Dh\
0 & Dq
\end{bmatrix}

\begin{bmatrix}f & Dg\end{bmatrix}
$$
此时，再去验证大小关系：
$$
||w’||=\sqrt{f^2+(Dg)^2}\approx
\sqrt{2^{\frac 32l-2}+2^{\frac 32l-2}}
=2^{\frac 34l-\frac 12}
$$

$$
\sigma(L)\approx \sqrt{Dq}\approx 2^{\frac 34l}
$$

这下得到了$||w||\lessapprox \sigma(L)$，格基规约求解即可，注意我们最后得到的是$\begin{bmatrix}f & Dg\end{bmatrix}$，要求$g$还要除回去$D$。

一些题目

[深育杯 2021]GeGe

from Crypto.Util.number import *
import gmpy2
from flag import flag

def encrypt(plaintext):
    p = getStrongPrime(3072) 
    m = bytes_to_long(plaintext)
    r = getRandomNBitInteger(1024)
    while True:
        f = getRandomNBitInteger(1024)
        g = getStrongPrime(768)
        h = gmpy2.invert(f, p) * g % p
        c = (r * h + m * f) % p
        return (h, p, c)

h, p, c = encrypt(flag)
with open("cipher.txt", "w") as f:
    f.write("h = " + str(h) + "\n")
    f.write("p = " + str(p) + "\n")
    f.write("c = " + str(c) + "\n")
    
h = 3967900409518491437091166715380802161532841159072519563471354336400750930009970177101953304861954502146570721506995224520631716261108071684882841102381144720177664434981608584075201907891964214604246219441325377602163957172642582158192223452845671007585556951922415200415538060247456213608112360361636912703380306386439846269645696750929811607783895294670639202472465920599542568227657152922843001792754116981992696203788298740550812661583820191877594185184758074771316815650833195023325150218113883046328740408517222933980589974912467363367727038230703152354450353199257411964288022409128890352346036423792759938468964462267528727695183747947515480432786669353434638860350849296620606820894819933050645748656981993408399675189724419997805599649975500093890450393421897803267909569938850674774386012819838940544502656293639875120854745249463561940935651895728242282430164407574626178693654713011323376912585958110558532953333
p = 4407206782832544188667944201727813617189883940490534227436068867901196311508151544316989531306678865408607390128649278629254128753967046691736522108356971272311308455619879297358588727267184200777923695048248757115057072357087881336680504033511958280710547178971268670442650871890760916203109226852889599638484429889898210426540567794020013920566784973281560628666918122674783539653720295629054898529900882965691587718212291373734218555167591690910246380516121338139063419587750344469214004539520017140593342859857394308703001939640899189432836134392830208318268131639318655382175643272565186884496188876341460968563623529229713790076050095498053846983536874648190033735162809614805624209827336432223553914651838063614534617044557310972056169869738746432924853953258079006936103497626054364115282007843847693813896856977882285910369660539092462408790126385881581833165309032853389777355480169212478669139225609058338565029211
c = 4052491539376955553220568757544621659293304958837707160681090710624505862889512520190589879197831394720145909992216099963759496125523078969015706069688556356682711471641851937470179182960755800968587551608595725470945584970094036299764623894583379909329996337429067328575804567222496890803396234507278490116354758303807070775249711087938549824010697869930856205244006491475201993228121418890520174179969294094963249013786611889790711801269524919695653453576043288934196952437164829830756439734795068980207758771052483500272264363028346668629397497794792110170275173209377114274164087320163340547019935562316429227119346802124620682293405375798340275679831750482339301440428527223801872439611461272229275824994734898078664180541096159146759378804836952981089673755590353588900522455968721971944276318473421193690310601002295637581030417570868955379815661133148339565983621730401675643094909263098778572081973142223744746526672

看起来像同余密码，进行同样的推导，这题有两个核心的加密公式：
$$
h\equiv f^{-1}g(\bmod p)
$$

$$
c\equiv rh+mf(\bmod p)
$$

题目里已知$h,p,c$，未知$r,m,f,g$，将1式代入2式，化简得到：
$$
cf\equiv rg+mf^2(\bmod p)
$$
$m$为flag转码值，应该不大，$mf^2<p$，变换一下上式：
$$
cf\bmod p=rg+mf^2
$$

$$
cf \bmod p\equiv mf^2(\bmod g)
$$
得到$m$表达式，求解$m$需要求解$f$和$g$：
$$
m=(cf\bmod p)\cdot f^{-2}\bmod g
$$
为了求解$f$和$g$，再看第一个式子：
$$
fh\equiv g(\bmod p)
$$

$$
fh+Rp=g
$$

构造格：$L=\begin{bmatrix}1 & h\\ 0 & p\end{bmatrix}$，有表达式：
$$
f(1,h)+R(0,p)=(f,g)
$$
根据高斯启发式，最短向量长度大约为$2^{1536}$，大概符合$(f,g)$，用sage求解：

from Crypto.Util.number import *
import gmpy2

h = 3967900409518491437091166715380802161532841159072519563471354336400750930009970177101953304861954502146570721506995224520631716261108071684882841102381144720177664434981608584075201907891964214604246219441325377602163957172642582158192223452845671007585556951922415200415538060247456213608112360361636912703380306386439846269645696750929811607783895294670639202472465920599542568227657152922843001792754116981992696203788298740550812661583820191877594185184758074771316815650833195023325150218113883046328740408517222933980589974912467363367727038230703152354450353199257411964288022409128890352346036423792759938468964462267528727695183747947515480432786669353434638860350849296620606820894819933050645748656981993408399675189724419997805599649975500093890450393421897803267909569938850674774386012819838940544502656293639875120854745249463561940935651895728242282430164407574626178693654713011323376912585958110558532953333
p = 4407206782832544188667944201727813617189883940490534227436068867901196311508151544316989531306678865408607390128649278629254128753967046691736522108356971272311308455619879297358588727267184200777923695048248757115057072357087881336680504033511958280710547178971268670442650871890760916203109226852889599638484429889898210426540567794020013920566784973281560628666918122674783539653720295629054898529900882965691587718212291373734218555167591690910246380516121338139063419587750344469214004539520017140593342859857394308703001939640899189432836134392830208318268131639318655382175643272565186884496188876341460968563623529229713790076050095498053846983536874648190033735162809614805624209827336432223553914651838063614534617044557310972056169869738746432924853953258079006936103497626054364115282007843847693813896856977882285910369660539092462408790126385881581833165309032853389777355480169212478669139225609058338565029211
c = 4052491539376955553220568757544621659293304958837707160681090710624505862889512520190589879197831394720145909992216099963759496125523078969015706069688556356682711471641851937470179182960755800968587551608595725470945584970094036299764623894583379909329996337429067328575804567222496890803396234507278490116354758303807070775249711087938549824010697869930856205244006491475201993228121418890520174179969294094963249013786611889790711801269524919695653453576043288934196952437164829830756439734795068980207758771052483500272264363028346668629397497794792110170275173209377114274164087320163340547019935562316429227119346802124620682293405375798340275679831750482339301440428527223801872439611461272229275824994734898078664180541096159146759378804836952981089673755590353588900522455968721971944276318473421193690310601002295637581030417570868955379815661133148339565983621730401675643094909263098778572081973142223744746526672

L = matrix(ZZ, [[1, h],[0, p]])
v = L.LLL()[0]
f,g=abs(v[0]),abs(v[1])
f_2=gmpy2.invert(f*f,g)
m=c*f%p*f_2%g
print(long_to_bytes(m))

[羊城杯 2022]LRSA

from random import *
from Crypto.Util.number import *
import gmpy2
from flag import flag

m=bytes_to_long(flag)

def getPQ(p,q):
    P=getPrime(2048)
    Q=getPrime(2048)
    t=(p*P-58*P+q)%Q
    assert (isPrime(Q))
    return P,Q,t

B=getRandomNBitInteger(11)
p=getPrime(B)
q=getPrime(B)
n=p*q
e=65537
c=pow(m,e,n)
P,Q,t=getPQ(p,q)

print("B=",B)
print("P*P*Q=",P*P*Q)
print("P*Q*Q=",P*Q*Q)
print("t=",t)
print("c=",c)

# B=1023
# P*P*Q=17550772391048142376662352375650397168226219900284185133945819378595084615279414529115194246625188015626268312188291451580718399491413731583962229337205180301248556893326419027312533686033888462669675100382278716791450615542537581657011200868911872550652311318486382920999726120813916439522474691195194557657267042628374572411645371485995174777885120394234154274071083542059010253657420242098856699109476857347677270860654429688935924519805555787949683144015873225388396740487817155358042797286990338440987035608851331840925854381286767024584195081004360635842976624747610461507795755042915965483135990495921912997789567020652729777216671481467049291624343256152446367091568361258918212012737611001009003078023715854575413979603297947011959023398306612437250872299406744778763429172689675430968886613391356192380152315042387148665654062576525633130546454743040442444227245763939134967515614637300940642555367668537324892890004459521919887178391559206373513466653484926149453481758790663522317898916616435463486824881406198956479504970446076256447830689197409184703931842169195650953917594642601134810084247402051464584676932882503143409428970896718980446185114397748313655630266379123438583315809104543663538494519415242569480492899140190587129956835218417371308642212037424611690324353109931657289337536406499314388951678319136343913551598851601805737870217800009086551022197432448461112330252097447894028786035069710260561955740514091976513928307284531381150606428802334767412638213776730300093872457594524254858721551285338651364457529927871215183857169772407595348187949014442596356406144157105062291018215254440382214000573515515859668018846789551567310531570458316720877172632139481792680258388798439064221051325274383331521717987420093245521230610073103811158660291643007279940393509663374960353315388446956868294358252276964954745551655711981
# P*Q*Q=17632503734712698604217167790453868045296303200715867263641257955056721075502316035280716025016839471684329988600978978424661087892466132185482035374940487837109552684763339574491378951189521258328752145077889261805000262141719400516584216130899437363088936913664419705248701787497332582188063869114908628807937049986360525010012039863210179017248132893824655341728382780250878156526086594253092249935304259986328308203344932540888448163430113818706295806406535364433801544858874357459282988110371175948011077595778123265914357153104206808258347815853145593128831233094769191889153762451880396333921190835200889266000562699392602082643298040136498839726733129090381507278582253125509943696419087708429546384313035073010683709744463087794325058122495375333875728593383803489271258323466068830034394348582326189840226236821974979834541554188673335151333713605570214286605391522582123096490317734786072061052604324131559447145448500381240146742679889154145555389449773359530020107821711994953950072547113428811855524572017820861579995449831880269151834230607863568992929328355995768974532894288752369127771516710199600449849031992434777962666440682129817924824151147427747882725858977273856311911431085373396551436319200582072164015150896425482384248479071434032953021738952688256364397405939276917210952583838731888536160866721278250628482428975748118973182256529453045184370543766401320261730361611365906347736001225775255350554164449014831203472238042057456969218316231699556466298168668958678855382462970622819417830000343573014265235688391542452769592096406400900187933156352226983897249981036555748543606676736274049188713348408983072484516372145496924391146241282884948724825393087105077360952770212959517318021248639012476095670769959011548699960423508352158455979906789927951812368185987838359200354730654103428077770839008773864604836807261909
# t=44
# c=4364802217291010807437827526073499188746160856656033054696031258814848127341094853323797303333741617649819892633013549917144139975939225893749114460910089509552261297408649636515368831194227006310835137628421405558641056278574098849091436284763725120659865442243245486345692476515256604820175726649516152356765363753262839864657243662645981385763738120585801720865252694204286145009527172990713740098977714337038793323846801300955225503801654258983911473974238212956519721447805792992654110642511482243273775873164502478594971816554268730722314333969932527553109979814408613177186842539860073028659812891580301154746

在我们还没有用格来解密码之前，对于这道题，首先可以用公因子来得到PQ，让在表达式t=(p*P-58*P+q)%Q中多知道两个未知数：

import gmpy2

sum1=17550772391048142376662352375650397168226219900284185133945819378595084615279414529115194246625188015626268312188291451580718399491413731583962229337205180301248556893326419027312533686033888462669675100382278716791450615542537581657011200868911872550652311318486382920999726120813916439522474691195194557657267042628374572411645371485995174777885120394234154274071083542059010253657420242098856699109476857347677270860654429688935924519805555787949683144015873225388396740487817155358042797286990338440987035608851331840925854381286767024584195081004360635842976624747610461507795755042915965483135990495921912997789567020652729777216671481467049291624343256152446367091568361258918212012737611001009003078023715854575413979603297947011959023398306612437250872299406744778763429172689675430968886613391356192380152315042387148665654062576525633130546454743040442444227245763939134967515614637300940642555367668537324892890004459521919887178391559206373513466653484926149453481758790663522317898916616435463486824881406198956479504970446076256447830689197409184703931842169195650953917594642601134810084247402051464584676932882503143409428970896718980446185114397748313655630266379123438583315809104543663538494519415242569480492899140190587129956835218417371308642212037424611690324353109931657289337536406499314388951678319136343913551598851601805737870217800009086551022197432448461112330252097447894028786035069710260561955740514091976513928307284531381150606428802334767412638213776730300093872457594524254858721551285338651364457529927871215183857169772407595348187949014442596356406144157105062291018215254440382214000573515515859668018846789551567310531570458316720877172632139481792680258388798439064221051325274383331521717987420093245521230610073103811158660291643007279940393509663374960353315388446956868294358252276964954745551655711981
sum2=17632503734712698604217167790453868045296303200715867263641257955056721075502316035280716025016839471684329988600978978424661087892466132185482035374940487837109552684763339574491378951189521258328752145077889261805000262141719400516584216130899437363088936913664419705248701787497332582188063869114908628807937049986360525010012039863210179017248132893824655341728382780250878156526086594253092249935304259986328308203344932540888448163430113818706295806406535364433801544858874357459282988110371175948011077595778123265914357153104206808258347815853145593128831233094769191889153762451880396333921190835200889266000562699392602082643298040136498839726733129090381507278582253125509943696419087708429546384313035073010683709744463087794325058122495375333875728593383803489271258323466068830034394348582326189840226236821974979834541554188673335151333713605570214286605391522582123096490317734786072061052604324131559447145448500381240146742679889154145555389449773359530020107821711994953950072547113428811855524572017820861579995449831880269151834230607863568992929328355995768974532894288752369127771516710199600449849031992434777962666440682129817924824151147427747882725858977273856311911431085373396551436319200582072164015150896425482384248479071434032953021738952688256364397405939276917210952583838731888536160866721278250628482428975748118973182256529453045184370543766401320261730361611365906347736001225775255350554164449014831203472238042057456969218316231699556466298168668958678855382462970622819417830000343573014265235688391542452769592096406400900187933156352226983897249981036555748543606676736274049188713348408983072484516372145496924391146241282884948724825393087105077360952770212959517318021248639012476095670769959011548699960423508352158455979906789927951812368185987838359200354730654103428077770839008773864604836807261909
PQ=gmpy2.gcd(sum1,sum2)
P=sum1//PQ
Q=sum2//PQ

所以，现在有式子：
$$
44= pP-58P+q+kQ
$$
变换一下得到：
$$
P(p-58)+kQ=44-q
$$
这个式子我们需要求得pq来解RSA，如果我们把pq想象成点坐标，就可以创建一个二维格，找到基来表示pq坐标。

注意到化简好的式子里有p-58和44-q可以利用，借助矩阵的知识，可以构造出：
$$
\begin{bmatrix}p-58 & k\end{bmatrix}\begin{bmatrix}1 & P\0 & Q\end{bmatrix}=\begin{bmatrix}p-58 & 44-q\end{bmatrix}
$$
由于PQ都为2048位大数，pq两个1023位的数比起来小太多了，借助这个，可以猜测在二维格中最短的向量就是等号右边，借助sage求解：

#sage
from Crypto.Util.number import *
import gmpy2

sum1 = 17550772391048142376662352375650397168226219900284185133945819378595084615279414529115194246625188015626268312188291451580718399491413731583962229337205180301248556893326419027312533686033888462669675100382278716791450615542537581657011200868911872550652311318486382920999726120813916439522474691195194557657267042628374572411645371485995174777885120394234154274071083542059010253657420242098856699109476857347677270860654429688935924519805555787949683144015873225388396740487817155358042797286990338440987035608851331840925854381286767024584195081004360635842976624747610461507795755042915965483135990495921912997789567020652729777216671481467049291624343256152446367091568361258918212012737611001009003078023715854575413979603297947011959023398306612437250872299406744778763429172689675430968886613391356192380152315042387148665654062576525633130546454743040442444227245763939134967515614637300940642555367668537324892890004459521919887178391559206373513466653484926149453481758790663522317898916616435463486824881406198956479504970446076256447830689197409184703931842169195650953917594642601134810084247402051464584676932882503143409428970896718980446185114397748313655630266379123438583315809104543663538494519415242569480492899140190587129956835218417371308642212037424611690324353109931657289337536406499314388951678319136343913551598851601805737870217800009086551022197432448461112330252097447894028786035069710260561955740514091976513928307284531381150606428802334767412638213776730300093872457594524254858721551285338651364457529927871215183857169772407595348187949014442596356406144157105062291018215254440382214000573515515859668018846789551567310531570458316720877172632139481792680258388798439064221051325274383331521717987420093245521230610073103811158660291643007279940393509663374960353315388446956868294358252276964954745551655711981
sum2 = 17632503734712698604217167790453868045296303200715867263641257955056721075502316035280716025016839471684329988600978978424661087892466132185482035374940487837109552684763339574491378951189521258328752145077889261805000262141719400516584216130899437363088936913664419705248701787497332582188063869114908628807937049986360525010012039863210179017248132893824655341728382780250878156526086594253092249935304259986328308203344932540888448163430113818706295806406535364433801544858874357459282988110371175948011077595778123265914357153104206808258347815853145593128831233094769191889153762451880396333921190835200889266000562699392602082643298040136498839726733129090381507278582253125509943696419087708429546384313035073010683709744463087794325058122495375333875728593383803489271258323466068830034394348582326189840226236821974979834541554188673335151333713605570214286605391522582123096490317734786072061052604324131559447145448500381240146742679889154145555389449773359530020107821711994953950072547113428811855524572017820861579995449831880269151834230607863568992929328355995768974532894288752369127771516710199600449849031992434777962666440682129817924824151147427747882725858977273856311911431085373396551436319200582072164015150896425482384248479071434032953021738952688256364397405939276917210952583838731888536160866721278250628482428975748118973182256529453045184370543766401320261730361611365906347736001225775255350554164449014831203472238042057456969218316231699556466298168668958678855382462970622819417830000343573014265235688391542452769592096406400900187933156352226983897249981036555748543606676736274049188713348408983072484516372145496924391146241282884948724825393087105077360952770212959517318021248639012476095670769959011548699960423508352158455979906789927951812368185987838359200354730654103428077770839008773864604836807261909
PQ = gmpy2.gcd(sum1, sum2)
P = sum1//PQ
Q = sum2//PQ

M = Matrix(ZZ, [[1, P], [0, Q]])
v = M.LLL()[0]
a, b = -v
p = a + 58
q = -b + 44
e = 65537
c = 4364802217291010807437827526073499188746160856656033054696031258814848127341094853323797303333741617649819892633013549917144139975939225893749114460910089509552261297408649636515368831194227006310835137628421405558641056278574098849091436284763725120659865442243245486345692476515256604820175726649516152356765363753262839864657243662645981385763738120585801720865252694204286145009527172990713740098977714337038793323846801300955225503801654258983911473974238212956519721447805792992654110642511482243273775873164502478594971816554268730722314333969932527553109979814408613177186842539860073028659812891580301154746
d = inverse_mod(e, (p-1)*(q-1))
m = pow(c, d, p*q)
print(long_to_bytes(int(m)))