R3CTF 2024 S𝑪𝑷-0εε WriteUp

*S𝑪𝑷-0εε

4 solved

题面

ANY NON-AUTHORIZED PERSONNEL ACCESSING THIS FILE WILL BE IMMEDIATELY TERMINATED THROUGH BERRYMAN-LANGFORD MEMETIC KILL AGENT.

Download Attachment

关键词

猜谜 + 未知位数约到Coppersmith界内

Idea

打开附件中的 PDF

和题目关联度不是很大的信息:SCP-033

发现有四行代码

0x[REDACTED] * x + 156836185692941550685700830474694810801481665972206761284102272745592205857267403669744401464803337850596191972703703054530778045202934271320509563462849102899119175874347103045300490340884691560845949337977390221147286384470287571194570435220134004423720066330220713360755490696975534869765259187925645069511484082883584773826540218677265291260254674449374287218468318302260595563533738636720497174 % (k * p) == 0
k= 1384368362335504207966549759103327813579924965137177857370654240988463990646382435845333383
N=p*q= 16560864354170001754058994512672943318940563370976087798466444727881483330942761871352258869577528553572663755957451586119530166974019489639824958689951617276161495644698610967505623963141115301453407833169441870214457028613126422544192376164562636961183685768882768312923714718974394046529737415829239869985138300035260197768109884692196300418128283001411459636932202117661934374282660653623201000258881545142769739613476895287578432668782523878551310276636940681367529703509645615758511763411234629347145718846540646434928674409510317321022775260360951885592032817087179680011170316690231298208905101051835044960739 # p,q (1024 bits)
x < 2 ** 790

第一行给定同余方程,第二行给出 kk 的值,第三行给出 NN 与 pp qq 的关系及 xx 的约束

同时通过附件可知,压缩包密码为 xx

但回到代码,2未知量的同余方程并不容易求解,观察到 PDF 中黑框宽度一共只有两种情况,同时 PDF 中有 Morse 字眼,于是进行如下尝试

打开PDF,将所有除了黑框外的内容替换为空格,2宽黑框替换为 -, 1宽黑框替换为 ., 遍历文字, 连续空格均约简为一个空格, 拿着处理结果解莫斯密码, 得到 0x[REDACTED] 的值为 0x8150EF932C24CABD,结果为 0x 开头的hex,说明猜想大概率正确

回到给定的同余方程 r⋅x+l≡0(modp⋅k)r \cdot x + l \equiv 0 \pmod{p \cdot k},这时已经变为1未知量同余方程,我们先来处理模 kk 的部分

将 xx 表示为 x=xdivk⋅k+xmodkx = x_{\text{divk}} \cdot k + x_{\text{modk}},其中 xmodk=xmod  kx_{\text{modk}} = x \mod k。现在我们将 xx 的表达式代入原方程

根据同余理论,我们有:

r⋅(xdivk⋅k+xmodk)+l≡0(modk)r \cdot (x_{\text{divk}} \cdot k + x_{\text{modk}}) + l \equiv 0 \pmod{k}

由于 kk 是模数,xdivk⋅k≡0(modk)x_{\text{divk}} \cdot k \equiv 0 \pmod{k}。因此,上述方程可以简化为:

r⋅xmodk+l≡0(modk)r \cdot x_{\text{modk}} + l \equiv 0 \pmod{k}

用逆元解出 xmodkx_{\text{modk}}:

xmodk=(−l⋅r−1)mod  kx_{\text{modk}} = (-l \cdot r^{-1}) \mod k

避免萌新混淆:这里 r−1r^{-1} 是 rr 在模 kk 下的乘法逆元

接下来,将 xx 表达式代回原方程 r⋅x+l≡0(modp⋅k)r \cdot x + l \equiv 0 \pmod{p \cdot k},并考虑模 pp:

r⋅(xdivk⋅k+xmodk)+l≡0(modp)r \cdot (x_{\text{divk}} \cdot k + x_{\text{modk}}) + l \equiv 0 \pmod{p}

这是一个关于 xdivkx_{\text{divk}} 的一元多项式方程,使用 Coppersmith 方法,我们可以寻找方程的小根

由于 k.bit_length() = 300,于是 xmodk≤2300x_{\text{modk}} \leq 2^{300}

实际上刚刚已经通过求逆得到 xmodkx_{\text{modk}},其 bit 长为 297

又已知 x<2790x < 2 ^ {790},则 xdivkx_{\text{divk}} 的 bit 长度上限为 790-300+1,即 491,以此用于我们解的上界

small_roots() 解之

我

我对这道题的 beta 参数还是不知道为什么是 0.499

糖醋小鸡块

beta是说实际模数大于用的模数的 beta 次幂
因为你是要模 pp 下去做,但是你只能用 nn
p≥n0.499p \geq n^{0.499},就这个意思
epsilon 越小界越大,时间越长

Exploit

SageMath's Code

from sage.all import *
from sage.misc.verbose import set_verbose

set_verbose(2)

n = 16560864354170001754058994512672943318940563370976087798466444727881483330942761871352258869577528553572663755957451586119530166974019489639824958689951617276161495644698610967505623963141115301453407833169441870214457028613126422544192376164562636961183685768882768312923714718974394046529737415829239869985138300035260197768109884692196300418128283001411459636932202117661934374282660653623201000258881545142769739613476895287578432668782523878551310276636940681367529703509645615758511763411234629347145718846540646434928674409510317321022775260360951885592032817087179680011170316690231298208905101051835044960739
# Extract black blocks from the text, separated by Spaces if they are discontinuous
# ----- -..- ---.. .---- ..... ----- . ..-. ----. ...-- ..--- -.-. ..--- ....- -.-. .- -... -..
# Decode morse code
# 0X8150EF932C24CABD
r = 0x8150EF932C24CABD
k = 1384368362335504207966549759103327813579924965137177857370654240988463990646382435845333383
l = 156836185692941550685700830474694810801481665972206761284102272745592205857267403669744401464803337850596191972703703054530778045202934271320509563462849102899119175874347103045300490340884691560845949337977390221147286384470287571194570435220134004423720066330220713360755490696975534869765259187925645069511484082883584773826540218677265291260254674449374287218468318302260595563533738636720497174

# r * x + l = 0 mod (p * k)
# 
# suppose
#   x_modk = x mod k
# x = x_divk * k + x_modk
# x_modk ~= 2^300
# x_divk ~= 2^790 / 2^300 ~= 2^490
# 
# r * x + l = 0 mod (p*k)
#           = 0 mod k

x_modk = (- l * pow(r, -1, k)) % k

# r * x + l = 0 mod (p*k)
# r * (x_divk * k + x_modk) + l = 0 mod p
#
# consider coppersmith mod n ~= 2^2048
# for polynomial = 0 mod p, beta = 0.499, beta^2-eps ~=0.249
# log(x_divk) / log(n) ~= 490/2048 ~= 0.239
# bounds fit

R.<x_divk> = PolynomialRing(Zmod(n))
eqn = r * (x_divk * k + x_modk) + l
eqn = eqn.monic()

# kiona coppersmith
# from coppersmith_onevariable import coppersmith_onevariable

# x_divk_res = coppersmith_onevariable(eq, [2^491], 0.499)[0]
ans = eqn.small_roots(X=2^491, beta=0.499, epsilon=0.02)
print(f'[*] {ans = }')
# [3680323884613892336022118030917011450860195161797346644261547005763335758730998834427019313308708924125755664872564671226769527453448605659192869212]
x_divk_res = ans[0]
x = x_divk_res * k + x_modk
print(f'[+] {x = }')
# 5094923949007175285631052747707508010283040023197740034481064880016139884138170819632717737356263521029784363413449801564804696834313039643471090185353766255767805836463330168317945468638961762962159379842448710670544305494051979854791657

Reference

  • 参考(照抄) 4yn 的思路及代码