格格你好棒

题目内容

题目给出的脚本如下：

from Crypto.Util.number import *
import random

flag = b'******'
m = bytes_to_long(flag)

a = getPrime(1024)
b = getPrime(1536)

p = getPrime(512)
q = getPrime(512)
r = random.randint(2**8, 2**9)
assert ((p+2*r) * 3*a + q) % b < 70

c = pow(m, 0x10001, p*q)

print(f'c =', c)
print(f'a =', a)
print(f'b =', b)

'''
c = 75671328500214475056134178451562126288749723392201857886683373274067151096013132141603734799638338446362190819013087028001291030248155587072037662295281180020447012070607162188511029753418358484745755426924178896079516327814868477319474776976247356213687362358286132623490797882893844885783660230132191533753
a = 99829685822966835958276444400403912618712610766908190376329921929407293564120124118477505585269077089315008380226830398574538050051718929826764449053677947419802792746249036134153510802052121734874555372027104653797402194532536147269634489642315951326590902954822775489385580372064589623985262480894316345817
b = 2384473327543107262477269141248562917518395867365960655318142892515553817531439357316940290934095375085624218120779709239118821966188906173260307431682367028597612973683887401344727494920856592020970209197406324257478251502340099862501536622889923455273016634520507179507645734423860654584092233709560055803703801064153206431244982586989154685048854436858839309457140702847482240801158808592615931654823643778920270174913454238149949865979522520566288822366419746
'''

格密码基础

• 格定义：CTF 密码学：格密码基础（含例题）
• 矩阵乘法：线性代数基础——矩阵和矩阵的乘法

NTRU 密码

参数

• 模数 $p$
• 私钥 $(f,g)$
• 公钥 $h=f^{-1}\cdot g(\mathrm{mod}p)$
• 临时密钥 $r$

加解密

• 加密：

  $$c\equiv r\ast h+m\equiv r\ast f^{-1}\ast g+m(\mathrm{mod}p)$$

• 解密：

  $$c\equiv r\cdot g+f\cdot m(\mathrm{mod}p)\equiv f\cdot m(\mathrm{mod}p)(\mathrm{mod}g)$$

  再乘上 $f^{-1}$ 即可得到 $m$.

参数大小

显然当$r\cdot g+f\cdot m<p$，$m<g$ 时才能正确解密。

考虑格

$$L=\left[\begin{array}{cc}1& h\\ 0& p\end{array}\right]$$

同时我们有

$$h\cdot f+k\cdot p=g$$

此时，我们发现 $(f,g)$ 便是格中的一个格点。

因为

$$(f,k)L=(f,f\cdot h+p\cdot k)=(f,g)$$

则如果我们能够找到 $(f,k)$，则可以得到 $(f,g)$.

更多条件

$$f<\frac{1}{2}{p}^{\frac{1}{2}},g<\frac{1}{2}{p}^{\frac{1}{2}},m<\frac{1}{4}{p}^{\frac{1}{2}},r<\frac{1}{2}{p}^{\frac{1}{2}}$$

此时发现向量 $\overrightarrow{b}=(f,g)$ 的长度为

$$||\overrightarrow{b}||=(f^2+g^2{)}^{\frac{1}{2}}<\frac{p}{2}$$

分析：为什么构造这样的格

目标为 $\overrightarrow{v}=(f,g)$ 私钥

已知式子

$$\begin{array}{rl}h=f^{-1}\cdot g\mathrm{mod}p\to g& =h\cdot f\mathrm{mod}p\\ g& =\underset{―}{h}\cdot f+k\cdot \underset{―}{p}\end{array}$$

下划线的 $h$ 和 $p$ 是已知量

观察式子，左边的 $g$ 是我们想要求得，右边中也有 $f$ 是我们想要的，而 $k$ 并不重要。

则结合向量和格，我们构造的格最后一列为 $(h,p)$ 或者 $(p,h)$（以下之一）

$$\begin{array}{c}\overrightarrow{(f,k)}\left[\begin{array}{ccc}& & h\\ & & p\end{array}\right]\\ \overrightarrow{(k，f)}\left[\begin{array}{ccc}& & p\\ & & h\end{array}\right]\end{array}$$

为了获得 $f$，格的第一列第一个为 $1$，然后补 $0$，或者相反（以下之一）

$$\begin{array}{c}\overrightarrow{(f,k)}\left[\begin{array}{cc}1& h\\ 0& p\end{array}\right]\\ \overrightarrow{(k,f)}\left[\begin{array}{cc}0& p\\ 1& h\end{array}\right]\end{array}$$

矩阵相乘得到结果 $\overrightarrow{(f,g)}$，通过 LLL 算法得到最短向量 $\overrightarrow{v}$，然后取值 $$\begin{gathered} f=\overrightarrow{v}[0] \\ g=\overrightarrow{v}[1] \end{gathered}$$

又有式子

$$c=(r\cdot h+m)\mathrm{mod}p$$

两边同时乘 $f$，得

$$\begin{array}{rl}f\cdot c& \equiv r\cdot h\cdot f+m\cdot f\mathrm{mod}p\\ f\cdot c& =r\cdot g+m\cdot f+k\cdot p(1)\end{array}$$

转换一下

$$m=(c-r\cdot g\cdot f^{-1})\mathrm{mod}p$$

但 $r$ 未知，此路不通，回上一个式子 $(1)$

在模 $p$ 的同时再模上 $g$ 去消 $r$，即

$$m=(f\cdot c\mathrm{mod}p\mathrm{mod}g)\cdot f^{-1}\mathrm{mod}g$$

明确目标

找到私钥 $(f,g)$

构造格

由公钥公式得到 $g=h\cdot f+k\cdot p$ 因为右边只有两项，确定 $n$ 维数为 2，且只有 $h$ 和 $p$ 已知，得知最后我们要构造的格的最后一列是 $h$、$p$，再推出L前面相乘的向量是 $(f,k)$，最后再补上前一列 $1、0$.

解密

用 LLL 算法得到最短向量 $v$ 后，对照当初设想的 $v=(f，g)$，令 $f=v[0]$，$g=v[1]$.

获得 $f$、$g$ 后，代入解密式子，因为 $r$ 是临时密钥，无从得知，所以我们先模上 $p$，再模上 $g$，消去 $r$. 最后再乘上 $f$ 关于模 $g$ 的逆元，求得 $m$.

题目解析

从题目和描述，知识点指向格密码

题目给了一个断言

((p+2*r) * 3*a + q) % b < 70

可以看成 $h=((p-2\cdot r)\cdot 3\cdot a+q)modb<70$

其中 $r$ 和 $h$ 都是有范围的，最大的范围 $r$ 也是在 $2^{1}4$ 和 $2^{1}5$ 之间，对于计算机而言相当小，可以爆破，所以当成已知数。

化简式子，把模消去：

$$(p-2\cdot r)\cdot 3\cdot a+k\cdot b=h-q$$

和 NTRU 的式子（NTRU: c = (r * h + m) % p）相似

构造

$$L=\left[\begin{array}{cc}1& 3a\\ 0& b\end{array}\right]$$

发现

$$(p-r,k)L=(p-2\cdot r,-q+h)=\overrightarrow{v}$$

且

$$||\overrightarrow{v}||\approx \sqrt{2}\cdot 2^{512}<\sqrt{2}\cdot b^{\frac{1}{2}}$$

EXP

# sagemath

from Crypto.Util.number import *
from tqdm import tqdm
c = # ...
a = # ...
b = # ..

L = Matrix(ZZ,[[1,3*a],
               [0,b]])
p,q = L.LLL()[0] # 这里的 [0] 是取其中的最小向量
p,q = abs(p),abs(q)
# 爆破 r 和 h
for r in tqdm(range(2**8,2**9)):
    for h in range(70):
        pp = p - 2*r
        qq = q + h
        phi = (pp-1)*(qq-1)
        if gcd(phi,65537) != 1:
            continue
        m = power_mod(c,inverse_mod(65537,phi),pp*qq)
        if b'flag' in long_to_bytes(m):
            print(r,h)
            print(pp,qq)
            print(long_to_bytes(m))
            print(long_to_bytes(m)==b'flag{u_are_@_master_of_latt1ce_Crypt0gr@phy}')
            exit(0)

出题人的碎碎念

一开始听群里面说想学格密码，于是在 Week 5 打算出一个

• 出NTRU吗？——有模板，不方便改
• 出背包吗？——我当时认为掌握超数列就能 Python 手撕 QAQ

在笔记中寻找许久，便把窃取目标盯上了 xenny 师傅的格密码课程的 P3

直接抄违背了出题初心，但是 P3 的解题内核始终吸引着我，自己动手推导式子构造格（在这对因为我「窃取」题目的行为而受伤的师傅们说声对不起！）

那么我就转向修改参数，以往的 RSA 题目，在我手动调试验证各个参数大小关系的时候，都是能满足自身的关系的

但在这题 assert ((p-r) * a + q) % b < 50 似乎发生了变化，随意 getPrime() 的参数根本满足不了前面这个式子，换句话来说，这个式子太过于严谨了，怎么能取到那么合适的值，把 h 从 1536 位降到 5 位

答案是 getPrime + 自己构造

原题

让我们看原题目是怎么写的：

a = getPrime(1024)
b = getPrime(1536)

p = getPrime(512)
q = getPrime(512)
r = random.randint(2**14, 2**15)
assert ((p-r) * a + q) % b < 50

关键步 ((p-r) * a + q) % b < 50，那么我们只需：先 getPrime() 生成 $p$、$q$、$r$、$a$，然后手动取一个 $h$（或者取随机数）就行，让 b = ((p-r) * a + q) - h

等想到这步时，我才发现 ((p-r) * a + q) 的位数和 $b$ 相近（前者最大项是 $p\cdot a$），这才能使得 $h=((p-r)\cdot a+q)-b$ 成立，而不是 $h=((p-r)\cdot a+q)-\mathit{K}\cdot b$

代码附上：

a = getPrime(1024)


p = getPrime(512)
q = getPrime(512)
r = random.randint(2**8, 2**9) # 这个涉及到解题的速度，遍历 [2**8, 2**9] 要 2 分钟，遍历 [2**14, 2**15] 要2小时，速度好像也和后面构造出的格有关

print(((p+2*r) * 3*a + q).bit_length())  # 要为 a 的位数 + p 的位数
while ((p+2*r) * 3*a + q).bit_length() != a.bit_length() + p.bit_length():
    a = getPrime(1024)
    p = getPrime(512)
    q = getPrime(512)
    r = random.randint(2**8, 2**9)

print(((p+2*r) * 3*a + q))

b = ((p+2*r) * 3*a + q) - 58 # 可改式子的系数，或者是自己搞一个式子，核心就是 p*a 最大，b 的位数就是 a 的位数 + p 的位数，b 具体值是 ((p+2*r) * 3*a + q) - h，h 的值自己拟定
h = 58
print('p,q =',[p,q])
print('a,r =',[a,r])
print('b,h =',[b,h])
exit()

调试的方法（出题日常）

可以改 $a$、$p$、$q$ 的位数，$r$ 的范围需要后面在解题代码中看看跑的速度来调整。注意，$b$ 的位数要大于 2 倍的 $p$ 的位数（推导见 Hermite 定理）

式子也能改，式子的灵魂就是最大项 $p\cdot a$ 与 $b$ 在位数上相近，需要自己爆破的数字很小且可控，式子的未知数个数是 5 个，只有 2 个知道范围，$k$ 和 $p$、$q$ 都不知，式子导向用格级规约 LLL 来解决

式子各项的系数，$r$ 的可以随意改，只要不接近 p//r，EXP 只需要改动 pp = p - t*r 中的 t

$a$ 的系数改动就要改格中 $a$ 的系数

$q$ 的系数改动还不太清楚，改完 EXP 就跑不动，也许是向量内不平衡

$h$ 改动涉及爆破范围的扩大与缩小，只需要对应的改动 EXP 的 h：

for h in range(50):

完整出题代码如下

from Crypto.Util.number import *
import random

flag = b''
m = bytes_to_long(flag)


if 0:
    a = getPrime(1024)


    p = getPrime(512)
    q = getPrime(512)
    r = random.randint(2**8, 2**9)

    print(((p+2*r) * 3*a + q).bit_length())  # 要为 a 的位数 + p 的位数
    print(((p+2*r) * 3*a + q))

    b = ((p+2*r) * 3*a + q) - 58   # 可改式子的系数，或者是自己搞一个式子，核心就是p*a最大，b的位数就是 a 的位数 + p 的位数，b 具体值是 ((p+2*r) * 3*a + q) - h，h 的值自己拟定
    h = 58
    print('p,q =',[p,q])
    print('a,r =',[a,r])
    print('b,h =',[b,h])
    exit()

p, q = # ...
a, r = # ...
b, h = # ...

assert ((p+2*r) * 3*a + q) % b < 70

c = pow(m, 0x10001, p*q)

print(f'c = {c}')
print(f'a = {a}')
print(f'b = {b}')

先将 if 0: 改为 1，执行临近代码块，获取 [p,q] [a,r] [b,h] 然后直接复制到下方，将 if 1: 改成 0，获取 $c$、$a$、$b$

提取 $r$，复制

放到解题脚本调试

# sagemath
from Crypto.Util.number import *
from tqdm import tqdm
c = 75671328500214475056134178451562126288749723392201857886683373274067151096013132141603734799638338446362190819013087028001291030248155587072037662295281180020447012070607162188511029753418358484745755426924178896079516327814868477319474776976247356213687362358286132623490797882893844885783660230132191533753
a = 99829685822966835958276444400403912618712610766908190376329921929407293564120124118477505585269077089315008380226830398574538050051718929826764449053677947419802792746249036134153510802052121734874555372027104653797402194532536147269634489642315951326590902954822775489385580372064589623985262480894316345817
b = 2384473327543107262477269141248562917518395867365960655318142892515553817531439357316940290934095375085624218120779709239118821966188906173260307431682367028597612973683887401344727494920856592020970209197406324257478251502340099862501536622889923455273016634520507179507645734423860654584092233709560055803703801064153206431244982586989154685048854436858839309457140702847482240801158808592615931654823643778920270174913454238149949865979522520566288822366419746

L = Matrix(ZZ,[[1,3*a],
               [0,b]])
p,q = L.LLL()[0] # 这里的 [0] 是取其中的最小向量
p,q = abs(p),abs(q)
# 爆破 r 和 h
for r in tqdm(range(308,2**9)):
    for h in range(70):
        pp = p - 2*r
        qq = q + h
        phi = (pp-1)*(qq-1)
        if gcd(phi,65537) != 1:
            continue
        m = power_mod(c,inverse_mod(65537,phi),pp*qq)
        if b'flag' in long_to_bytes(m):
            print(r,h)
            print(pp,qq)
            print(long_to_bytes(m))
            print(long_to_bytes(m)==b'既定flag{}')
            exit(0)

先用 r 替换下面代码中的 2**8，跳过遍历环节，看看能否得到结果

for r in tqdm(range(2**8,2**9)):

如果可以，那么再换回成 2**8

看看遍历速度和所需时间，这里需要 2 分钟，实际上解题只需要 22 秒

出题时，两个 SageMath 版本（Windows 的 9.3 和 Linux 的 10.X）都测试了速度，以免新生因为环境问题而困扰

更换了参数和式子，也算半个魔改了。