Harry's Blog

温故知新

0%

初探格密码

发表于 更新于   阅读次数： Valine：
本文字数： 6.9k 阅读时长 ≈ 6 分钟
从2020年的一道NTRU题目，认识并运用格。

初探格密码·NTRU

笔者最早接触格密码是在先知社区Soreat_u师傅的发文中，其中便给出了如下的题目，学习后有了很大的收获。

而随着先知社区关闭、文章被删等原因，我找到了Soreat_u师傅博客原文, 但又因其图片失效问题影响阅读、分享，便有了此文。

题目

来源于2020年巅峰极客（数据为笔者生成的），赛时仅有2解。

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
import gmpy2
from secret import flag
from Crypto.Util.number import *


def generate():
    p = getStrongPrime(2048)
    while True:
        f = getRandomNBitInteger(1024)
        g = getStrongPrime(768)
        h = gmpy2.invert(f, p) * g % p
        return (p, f, g, h)


def encrypt(plaintext, p, h):
    m = bytes_to_long(plaintext)
    r = getRandomNBitInteger(1024)
    c = (r * h + m) % p
    return c


p, f, g, h = generate()
c = encrypt(flag, p, h)
print('h =', h)
print('p =', p)
print('c =', c)
"""
h = 15920807412952692847985174177588211960281948838307253586797239960508125481987882224605864406372742338485793530131031795389776531751200676051949170672004649326503467447518123006808297262753280286176914568491022298784897984879823370933511805201516939304165656461649805404345353075803763209810253831770288511818668398003443730898078080711296567200650962390927974385735100849320021423318726773493255693093044142610555698370275203822724528162516863483780170076614868308468049805668954554578089167666866242081591436319781031943877834260419842837279937368942586813623585114579680192182136454951076576180846308031147577895183
p = 29616445112694260274774681537287299269831042656521626513009034520717072986110554689452007791622053679125813101887358792411152206641110832730768759894034995329749945245036475665938165090997263055454214551943883405059392525425764609291470545536168035201657530029849113821500078015786845062143152799634844986753056256220285729693791666273618731684193516606613125066125143895019716948226556471128531174411802630235945882713680099627033330758906060609807833477234842026397619463093836747345939002210487194276855948870859245196439206070300222410002340377429280616491741559912351526804469748340235688215655559714767093336011
c = 24894154600738747801028572977171957374256712941786243361235711912410748252475712552938200529578615522555383736598357845901370674754857388874985225645650913059820754690696257510209172235875364336887131653254443697948965333434213242584604843844646774324930722413839123594241879178636469903372909302377061318833174246232722769872293078758804927418352848560803152544304608965368181815249876729133751310904899772060616419975025741262545479052454752165874425435226386604586446369944613258629120527951194286510228752204113015018002437399369034486123978271982779314575972603420464431960235222295086660836240988842127196837233
"""

题解

根据大小关系化简

关注题目参数大小

  • $p: 2048 \space bit$

  • $f: 1024 \space bit$

  • $g: 768 \space bit$

  • $h = f^{-1}*g \mod p :2048 \space bit$

  • $r: 1024 \space bit$

  • $c = (r \cdot h + m)= (r \cdot f^{-1}*g + m) \mod p :2048 \space bit$

于是有：
$$
c \cdot f = r \cdot g + m \cdot f \mod p
$$
让我们关注等式右侧，不难发现: $r \cdot g +m \cdot f$的大小肯定不会超过$p$（2048bit）

即，这不是同余式而是等式（记$c \cdot f \space \% \space p$的结果为$c’$）：
$$
c’= r \cdot g + m \cdot f
$$
若我们有了参数$f、g$，那么这题便可以绕过r求解m了，流程如下：

  1. 等式两边同时对g取余

    $c’= m \cdot f \mod g$

  2. 等式两边同时乘f对g的逆

    $c’ \cdot f^{-1}= m \mod g$

一般来说flag不会太大，模g有768bit比m大，如上运算便可以得到m的真值。

那么我们该如何求解f、g呢？

答案很显然了，格。

利用格求出未知量

与$f、g$同时有关系的只有如下这个式子：
$$
\begin{aligned}h &= f^{-1}*g \mod p \\ h \cdot f &= g + kp \end{aligned}
$$
“一个式子居然能求两个未知数吗？”，你想到。

「事实上，只要等式中参数大小足够巧妙，我们便能利用格来求解其中未知量」

先给出结论，对于如下矩阵M，对其使用LLL算法后，我们可以得到$f, g$
$$
M = \begin{bmatrix} 1 & h \\ 0 & p \end{bmatrix}
$$
那么，我们是如何写出这个矩阵的呢？

事实上，写出矩阵M的过程都是以这一句话为准则的，即：$v \cdot M = \vec w$

  • $v$：未知量矩阵
  • $M$：已知量矩阵
  • $\vec w$：要求量矩阵

对于本题，最容易确认的是$\vec w$, 因为我们需要求的量很明确，就是$f, g$。

所以，有：
$$
\vec w = [f \space\space\space g]
$$
其次，格是通过等式来建立的，我们看向本题的关系式：
$$
h \cdot f -kp= g
$$
其中，$f、k、g$为未知量，$f、g$为要求量

确定$v$，如下（一般来说，等式里能单独表示的要求量不放在未知量矩阵里，如本题中$g$）：
$$
v = [f \space\space\space -k ]
$$
最后，根据矩阵乘法确定$M$，如下：
$$
M = \begin{bmatrix} 1 & h \\ 0 & p \end{bmatrix}
$$
总的看来，我们写出如下$v \cdot M = \vec w$
$$
\begin{bmatrix} f & -k \end{bmatrix} \begin{bmatrix} 1 & h \\ 0 & p \end{bmatrix} =
\begin{bmatrix} f & g \end{bmatrix}
$$
值得一说，在确认已知量矩阵$M$时，依赖的等式有：

  • $f \cdot 1 - k \cdot 0 =f$
  • $f \cdot h -kp= g$

好的，知道$M$如何来的以后，又有一个问题产生了

为什么对$M$使用LLL算法能得到$f、g$?

格的定义以及原理

我们只需要弄懂以下格相关知识，便可进行接下来的题目讲解。

  1. 什么是格？
  2. SVP的上限是？
  3. LLL可以在一定程度内求解SVP

格是什么

线性无关基向量$v_1, v_2, v_3, .. ., v_n$的所有整系数线性组合所形成的$n$维离散空间。

给定n维空间中一组线性无关向量，其整系数组合构成的集合称为格。

格上的点排布呈周期性规律。

2-dimension Lattice

这里需要明确，不同的格基可能表示的是同一个格, 如下:

image-20221130231915760

SVP｜shortest vector problem

最短向量问题：给定一个基为$B$的Lattice $L(B)$，找到一个这个基构成的格点，使得这个点距离0坐标点的距离最近.

SVP的上限

根据Hermit定理（MINKOWSKI第一定理），有：

$$
\lambda_1(Λ) \leq \sqrt{n} * \sqrt[n]{det(Λ)}
$$

其中，参数意义如下：

  • $Λ$：格基矩阵

  • $\lambda_1(Λ)$： 格中最短向量的长度

  • $n$：格的维度

  • $det()$: 行列式

LLL

LLL 算法就是在格上找到一组基，满足如下效果

image-20230209221112075

可以简单的理解为：给定任意格基，LLL算法能规约出格中短的、正交性好的格基

如果得当，我们所寻找的最短向量就在其中。

值得一说，LLL后得到的格基矩阵中有多组基向量，越往下长度越长

题目讲解

回到题目，一言以蔽之，我们所写的$v \cdot M = \vec w$，如下：
$$
\begin{bmatrix} f & -k \end{bmatrix} \begin{bmatrix} 1 & h \\ 0 & p \end{bmatrix} =
\begin{bmatrix} f & g \end{bmatrix}
$$
运算本质是：对基向量$(1,h)、(0, p)$进行了线形组合，得到了$(f, g)$

而这，证明了这样一件事：点$(f, g)$在$M$所张成的格上。

相对于两个基向量$(1, h), (0, p)$来说，向量$(f, g)$的长度要小得多得多。

根据Hermit定理可知，在这个格中最短向量的长度大概在sqrt(2^2048)=2^1024左右。因此，很大概率上，$(f, g)$就是这个lattice的最短向量。

所以，我们可以对$M$使用LLL获得$(f, g)$。

到此，题目原理讲解便结束了。

但作为密码手，仅知悉这些知识还是远远不够的，应当更广泛的去了解、学习格的相关定义与构造法则。

这里给出两篇拓展阅读，望能对读者的CTF格基密码学习之路提供帮助。

exp

无论是矩阵的建立，还是LLL算法，SageMath都内置，很方便。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import libnum
h = 15920807412952692847985174177588211960281948838307253586797239960508125481987882224605864406372742338485793530131031795389776531751200676051949170672004649326503467447518123006808297262753280286176914568491022298784897984879823370933511805201516939304165656461649805404345353075803763209810253831770288511818668398003443730898078080711296567200650962390927974385735100849320021423318726773493255693093044142610555698370275203822724528162516863483780170076614868308468049805668954554578089167666866242081591436319781031943877834260419842837279937368942586813623585114579680192182136454951076576180846308031147577895183
p = 29616445112694260274774681537287299269831042656521626513009034520717072986110554689452007791622053679125813101887358792411152206641110832730768759894034995329749945245036475665938165090997263055454214551943883405059392525425764609291470545536168035201657530029849113821500078015786845062143152799634844986753056256220285729693791666273618731684193516606613125066125143895019716948226556471128531174411802630235945882713680099627033330758906060609807833477234842026397619463093836747345939002210487194276855948870859245196439206070300222410002340377429280616491741559912351526804469748340235688215655559714767093336011
c = 24894154600738747801028572977171957374256712941786243361235711912410748252475712552938200529578615522555383736598357845901370674754857388874985225645650913059820754690696257510209172235875364336887131653254443697948965333434213242584604843844646774324930722413839123594241879178636469903372909302377061318833174246232722769872293078758804927418352848560803152544304608965368181815249876729133751310904899772060616419975025741262545479052454752165874425435226386604586446369944613258629120527951194286510228752204113015018002437399369034486123978271982779314575972603420464431960235222295086660836240988842127196837233

# 求解f, g
Ge = matrix(ZZ, [[1, h], [0, p]])
f, g = Ge.LLL()[0]  # SVP
# 利用f, g求解m
f = abs(f)
g = abs(g)
c_ = (c*f)%p
m = c_*inverse_mod(f, g)%g
print(libnum.n2s(int(m)))