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

第一行给定同余方程，第二行给出 $k$ 的值，第三行给出 $N$ 与 $p$ $q$ 的关系及 $x$ 的约束

同时通过附件可知，压缩包密码为 $x$

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

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

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

将 $x$ 表示为 $x = x_{\text{divk}} \cdot k + x_{\text{modk}}$ ，其中 $x_{\text{modk}} = x \mod k$ 。现在我们将 $x$ 的表达式代入原方程

根据同余理论，我们有：

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

由于 $k$ 是模数， $x_{\text{divk}} \cdot k \equiv 0 \pmod{k}$ 。因此，上述方程可以简化为：

r \cdot x_{\text{modk}} + l \equiv 0 \pmod{k}

用逆元解出 $x_{\text{modk}}$ ：

x_{\text{modk}} = (-l \cdot r^{-1}) \mod k

避免萌新混淆：这里 $r^{-1}$ 是 $r$ 在模 $k$ 下的乘法逆元

接下来，将 $x$ 表达式代回原方程 $r \cdot x + l \equiv 0 \pmod{p \cdot k}$ ，并考虑模 $p$ ：

r \cdot (x_{\text{divk}} \cdot k + x_{\text{modk}}) + l \equiv 0 \pmod{p}

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

由于 k.bit_length() = 300，于是 $x_{\text{modk}} \leq 2^{300}$

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

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

small_roots() 解之

我

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

糖醋小鸡块

beta是说实际模数大于用的模数的 beta 次幂
因为你是要模 $p$ 下去做，但是你只能用 $n$
$p \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 的思路及代码

LOV3