[Crypto学习笔记] 格基规约类问题

4 分钟阅读时长

发布时间： November 13, 2024

符号

向量长度

例如符号$$

$$表示向量a的向量长度, 我们可以按以下方式进行求解:

\[\begin{matrix} a = (x,y) \\ ||a|| = \sqrt{x^2+y^2} \end{matrix}\]

前置概念

rsa原理

从最基本的rsa开始, 标准题目中可以分解n为p, q构造phin获取私钥:

lll

定理1¹:

一组基B存在: $B=(b_1, b_2, ..., b_n) \\ B\in R_{m \times n}$ 如果满足以下条件, 称基B是带有参数δ的LLL约简基:
\[|\mu_{i,j}| \leq \frac{1}{2} (i > j)\]
对任意一组向量基$b_i$, $b_{i+1}$存在: $\delta||\pi(b_i)||^2 \leq ||\pi(b_{i+1})||^2$

定理2¹:

一组基B存在: $B=(b_1, b_2, ..., b_n) \\ B\in R_{m \times n}$ 如果基B是带有参数δ的LLL约简基, 且存在1/4<δ<1, 则有结论:
\[||b_1|| \leq \alpha^{(n-1)/2}\lambda_1\]
$||b_1|| \leq \alpha^{(n-1)/4}det(B)^{1/n}$ 其中有: $\alpha=1/(\delta-1/4) \geq 4/3$

Hermite定理3²:

一组基B存在: $B=(b_1, b_2, ..., b_n) \\ B\in R_{m \times n}$ 如果基B是LLL约简基, 对于n维的格L, 满足 $||b_1|| \leq \sqrt{n}det(B)^{1/n}$

最近题目比较多, 以后慢慢补.

sictfround3

easylattice

很久以前做的, 感觉很适合用来给LLL开头.

题目

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

assert len(flag) == 47

f = bytes_to_long(flag)
p = getPrime(512)
g = getPrime(128)
h = gmpy2.invert(f, p) * g % p

print('h =', h)
print('p =', p)

"""
h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947
"""

解析

考察格基规约的原理, 可以构造数学表达式如下:

\[h = f^{-1} * g \mod{p}\]

其中f为flag, 已知h与p, 可以将取模运算重新构造为多项式:

\[h * f + n * p = g\]

可以写成代数形式:

\[\begin{bmatrix} f & n \end{bmatrix} \begin{bmatrix} h \\ p \end{bmatrix} = g\]

我们期望求出f, 故我们可以从已知向量(h, p)为基础, 继续构造出满足(f, n)的向量基:

\[\begin{bmatrix} f & n \end{bmatrix} \begin{bmatrix} h & 1\\ p & 0 \end{bmatrix} = \begin{bmatrix} g & f \end{bmatrix}\]

LLL中定理2具有一定的性质可供我们构造向量基求解, 当然直接使用调用LLL()函数是无法拿到结果的:

from sage.all import *
from Crypto.Util.number import long_to_bytes

h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947


mat = matrix([
            [h, 1],
            [p, 0]
        ])
mat_LLL = mat.LLL()

print(long_to_bytes(abs(mat_LLL[0][1])))

# b'\xdc\xb3\x140+\x8c\x1d\x81\xbd\xb2NY\xa6q\xc3\x86C\xf2H\x01\xec]\xdc\xa7\xa4\x92\xdc\xd9\xb8\x15\xedo'

我们可以尝试使用LLL中Hermite定理3进行检验:

\[\begin{matrix} ||b_1|| = \sqrt{g_{<128>}^2+f_{<375>}^2} \approx g^3 \approx 2^{128*3}\\ n = 2 \\ det(B) = -p \\ 2^{128*3} \geq \sqrt{2p} \end{matrix}\]

不满足Hermite定理3, 我们需要稍微修整, 使

\[2^{128*3} \leq \sqrt{2p'}\]

由于p的比特长度为512, 我们可以计算比特长度的差值, 对向量基上的向量进行缩放, 因为SVP(最短向量问题)是一个范围, 可以使用以下公式模糊估计出向量缩放程度:

\[\delta = 2^{128*3}-\sqrt{2p}\]

代入公式可以得到

\[\begin{bmatrix} f & n \end{bmatrix} \begin{bmatrix} h*\delta & 1 \\ p*\delta & 0 \end{bmatrix} = \begin{bmatrix} g*\delta & f \end{bmatrix}\]

故可构造EXP(emmmm, 至于为什么要这样扩展长度, 肉眼可见的是g远小于f, 扩展以后可以尽量使得 $$

b_1

$$ 的改动尽可能小).

EXP

from sage.all import *
from Crypto.Util.number import long_to_bytes

h = 9848463356094730516607732957888686710609147955724620108704251779566910519170690198684628685762596232124613115691882688827918489297122319416081019121038443
p = 11403618200995593428747663693860532026261161211931726381922677499906885834766955987247477478421850280928508004160386000301268285541073474589048412962888947

delta = 2 ** ((128*3*2) - (2*p).bit_length())

mat = matrix([
            [h*delta, 1],
            [p*delta, 0]
        ])
mat_LLL = mat.LLL()

print(long_to_bytes(abs(mat_LLL[0][1])))

# b'SICTF{e3fea01c-18f3-4638-9544-9201393940a9}A\xf0\x89\x84'

2024网鼎半决赛

RSA加密分析

题目

偷了dexterjie师傅的博客²:

# sagemath
import random
from Crypto.Util.number import *

flag = b''

k = 3
d = k/(2*(k+1))
ns = []
pqs = []
es = []

for i in range(3):
    p = getPrime(512)
    q = getPrime(512)
    if p < q:
        tmp = p
        p = q
        q = tmp
    n = p*q
    ns.append(n)
    pqs.append((p,q))

n = min(ns)
x = random.randint(0,int(n^(d/2)))
x = next_prime(x)

for i in range(3):
    p,q = pqs[i][0],pqs[i][1]
    bound1 = int((p-q)/(3*(p+q)) * x * n ^ 0.25)
    bound2 = int((p-q)/(3*(p+q)) * x^2 * n ^ 0.25)
    z = random.randint(bound1,bound2)
    f = (p-1)*(q-1)
    e = inverse(x^2,f) * z % f
    es.append(e)

e = 8462913
c = pow(bytes_to_long(flag),e,ns[0])

print(f'ns={ns}')
print(f'es={es}')
print(f'c={c}')

'''
ns=[58456238154727772714762362790039415372652580738847549549926175214592421074440425380491278175531057453959583518365006871715668115289674464868754600641087664868445977308497244134179400977293896807231964047365956545629327100737851868274388108150918741474301542596310528990700043925342513137054619092876834352167, 77621328849675766747673031143217563980503830449890233197117569566535170499356584333526498228802079135043121885950830320777642529199704224484173792215691924850086027618183393165197503325417741686635820334799489140360184827244176669486536901652827052817389390205607840551799799037689580359943641014734459153393, 112244920700186260026594736958318991062998987080230137582151100770199379608284829383065111800934933346946496041561749555085922429662611986339400029890877247514987095240380019377389184545006798594193383230298132838994539491402564579629017309643629910561998268286162916487705908044261914142200286678017692930877]
es=[46762963588977775648213636278524171408894671002158172701955774077187382885695296449518850546775920334764033057745226744111631183010556541467024035131602309988991836959736948179491431343087734419406823467043032520956443072556932946767546576469286010676651317873358203560021064830688914958086524112915123700678, 49605058941818136068558533413619424099600243928109466352604646203354430655695939177245076016870792265350960174089601299549033530643078866868937787258274475767441534991912769995268058506952466739575911255510940326565376471493045685544056383561868628029099619187607579109612157304977780126730283103824111801708, 35433601810279274137096137736120773703247868305827931187532982974242279082633517463016086358856291932337981126992048059591164336008738979183437333221010305682689432537562502148059203087673302900990705589870381203411821061168753251557946997898741497047442934600089950257888693394999451561437497637827070063398]
c=45042826649205831967869785980034342377048541926664036544108272069702081866501394370318117629151408517708467341069558466115205805860156690204194355692872459196902123082567148537856941845388225814307822482217762135547080677443326657146552580523747535577686386312386011950929734955156100305548239483424574706729
'''

解析

感觉程序完成得不是很优雅, 总共经历了两次3轮循环, 但是可以总结为一次结果, 暂时忽略掉z的界:

z = random.randint(bound1,bound2)

我们得到三组同余式:

\[\begin{matrix} e_1 * x^2 \equiv z_1 \mod{f_1} \\ e_2 * x^2 \equiv z_2 \mod{f_2} \\ e_3 * x^2 \equiv z_3 \mod{f_3} \end{matrix}\]

其中x为定值, z为每轮随机生成的数值, f为p,q生成的phin, 其中有:

\[q < p\]

现在已知三组的n, e与最终加密的e, 考虑欲获得flag需要尽量回复同余式获取对应的phin以计算私钥, 故需要尝试获取x与z的数值, 与ns, es相关的有f与e, 可以尝试构造格:

\[e_1 * x^2 = z_1 - k_1*f_1 \\ e_2 * x^2 = z_2 - k_2*f_2 \\ e_3 * x^2 = z_3 - k_3*f_3\]

通过展开phin(即式中f)可以构造出包含n的关系式, 有:

\[phin = (p-1)(q-1) = n - p - q + 1\]

设c有:

\[c = p + q - 1\]

可以构造多项式:

\[e_1 * x^2 + k_1*n_1 = z_1 - k_1*c_1 \\ e_2 * x^2 + k_2*n_2 = z_2 - k_2*c_2 \\ e_3 * x^2 + k_3*n_3 = z_3 - k_3*c_3\]

转换为矩阵形式有:

\[\begin{bmatrix} x^2 & n_1 & n_2 & n_3 \end{bmatrix} \begin{bmatrix} e_1 & e_2& e_3 \\ n_1 & 0 & 0 \\ 0 & n_2& 0 \\ 0 & 0 & n_3 \end{bmatrix} = \begin{bmatrix} z_1 - k_1*c_1 & z_2 - k_2*c_2 & z_3 - k_3*c_3 \end{bmatrix}\]

欲求出x只需要再添加一个维度:

\[\begin{bmatrix} x^2 & n_1 & n_2 & n_3 \end{bmatrix} \begin{bmatrix} 1 & e_1 & e_2& e_3 \\ 0 & n_1 & 0 & 0 \\ 0 & 0 & n_2& 0 \\ 0 & 0 & 0 & n_3 \end{bmatrix} = \begin{bmatrix} x^2 & z_1 - k_1*c_1 & z_2 - k_2*c_2 & z_3 - k_3*c_3 \end{bmatrix}\]

尝试使用LLL中Hermite定理3进行检验:

\[\begin{matrix} ||b_1|| \approx \sqrt{x^4+\sum_{i=1}^3(z_i-k_i*c_i)^2}\\ x^2_{<381>} \\ z_{i<632>} \\ n = 4 \\ det(B) = n_1*n_2*n_3 \\ 2^{316} \geq 2\sqrt[4]{n_1*n_2*n_3} \end{matrix}\]

明显不满足Hermite定理3, 我们需要稍微修整配平, 这里可以考虑对x所在向量进行配平, 通过调试运行, 我们能大致感觉出x是最小的数:

\[||b_1|| \leq 2\sqrt[4]{n_1*n_2*n_3}\]

同样对最简向量进行缩放, 可以考虑模糊估计出向量的缩放程度:

\[\delta = (\frac{||b_1||}{2\sqrt[4]{n_1*n_2*n_3}}) ^ 4\]

实际上这里很麻烦, 因为我们无法几乎无法直接估计出delta(后来我想了一下其实也不是不行, 因为我们大致知道一定的值, 可能也可以极端地找出k与c的近似值, 通过复杂的近似也能找到大致的delta), 好在我们可以猜测出

\[\delta < 2^{1849}\]

星盟在ACTF中提供了一种方法³, 可以通过判断是否整除找出对应的x:

for i in range(50, 1849):
    delta = 2 ** i
    mat = [
        [delta,e1,e2,e3],
        [0,-n1,0,0],
        [0,0,-n2,0],
        [0,0,0,-n3]
    ]
    mat_lll = Matrix(mat).LLL()
    x2_delta = abs(mat_lll[0][0])
    x = iroot(x2_delta // delta, 2)
    if x2_delta%delta == 0 and x[1]:
        print('x is:', x[0])
        break

# x is: 1696237025993008832375257492068228509280454088630659960513

未知量还剩z, k和f(计算中f被转换为n与c), 由于均为

参考文献

Daniele Micciancio.Lecture 4: The LLL Algorithm[C].Lattice Algorithms and Applications.Spring-2007 ↩ ↩²
DexterJie.网鼎杯半决赛[EB/OL].https://dexterjie.github.io/2024/11/23/%E8%B5%9B%E9%A2%98%E5%A4%8D%E7%8E%B0/%E7%BD%91%E9%BC%8E%E6%9D%AF%E5%8D%8A%E5%86%B3%E8%B5%9B/.2024-11-23 ↩ ↩²
星盟安全团队.ACTF2023 Writeup[EB/OL]星盟安全团队.https://blog.xmcve.com/2023/10/31/ACTF-2023-Writeup/.2023.10.31 ↩

分享到

Twitter Facebook LinkedIn

CryingN

[Crypto学习笔记] 格基规约类问题

目录

符号

向量长度

前置概念

rsa原理

lll

sictfround3

easylattice

题目

解析

EXP

2024网鼎半决赛

RSA加密分析

题目

解析

参考文献

分享到

你可能感兴趣的

[Crypto学习笔记] Edwards curve类题目

[Crypto学习笔记] Schmidt-Samona密码系统

[Crypto学习笔记] DES对称加密类题目

[Crypto学习笔记] Hash类型攻击题目