SYCTF-2023 安洵杯 Crypto 题解

2023-06-11

字数统计: 2.4k字 | 阅读时长≈ 11分

Crypto 的斐波那契数列还挺有意思，其他都很常规。槽点就是，往其他赛道的题里面塞纯脑洞的 MISC 真的一点意思也没有。

Alexei Needs Help

需要我们求解一个类似斐波那契数列的数列通项表达式，该变体数列递推公式如下：

$S_n = \left\{ \begin{array}{**lr**} 1 & n \le 2 \\ aS_{n-1} + bS_{n-2} + f(n), & n \ge 3. \end{array} \right. \\ \text{where $f(n) = \sum_{i=0}^{9} c_ix^i$}$

考虑斐波那契数列的两种解法（参考 wiki），分别讨论一下上面斐波那契变体数列的求解：

待定系数法求解 ，目的是构造一个等比数列 $B_n$ ：
$B_n = (S_n + \alpha_1 S_{n-1} + \alpha_2) = \beta (S_{n-1} + \alpha_1 S_{n-2} + \alpha_2) = \beta B_{n-1}$
构建系数方程：
$\left\{ \begin{array}{**lr**} \beta - \alpha_1 = a & (1)\\ \beta \alpha_1 = b & (2)\\ \beta \alpha_2 - \alpha_2 = f(n) & (3) \end{array} \right.$
方程(1),(2) 是经典的斐波那契数列的方程（ $a = 1, b =1$ ），在有限域上，同样可以构造一元二次方程组进行求解得到 $\beta, \alpha_1$ ，但是也可能不存在解，需要在扩域上计算，比如复数域是实数域的扩域。带入 $\beta,\alpha_1$ 求解方程（3）是简单的，但是当函数 $f(n)$ 比较复杂时，就需要比较好的数学竞赛技巧去求原数列 $S_n$ 的通项表达式了，不太推荐这种方法。
线性代数求解 : 如果构造矩阵求解，利用一点点矩阵快速幂，有限域/整数环上的斐波那契数列计算就非常简单了。首先考虑 $f(n) = 0$ 的简单情况，有如下递推公式：
$\begin{pmatrix} S_n \\ S_{n-1} \end{pmatrix} = \begin{pmatrix} a & b \\ 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} S_{n-1} \\ S_{n-2} \end{pmatrix}$
给定初始向量 $(S_1,S_2)^T = (1,1)^T$ ，斐波那契数列的通用矩阵表达式如下：
$\begin{pmatrix} S_n \\ S_{n-1} \end{pmatrix} = \begin{pmatrix} a & b \\ 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} S_{n-1} \\ S_{n-2} \end{pmatrix} = \begin{pmatrix} a & b \\ 1 & 0 \end{pmatrix}^{n-2} \cdot \begin{pmatrix} 1 \\ 1 \end{pmatrix} \quad n \ge 2$
利用（有限域/整数环上）矩阵快速幂，可以快速求解任意 $S_n$ 。

回到题目本身，斐波那契数列递推公式后面附加了一个 $d = 10$ 次多项式 $f(n) = \sum_{i=0}^{9} c_ix^i$ 。多项式本身很好拟合，我们把高次项放进递推向量内，就退化至线性了。也就是说我们把递推向量换成 $\vec V^T_n = (S_{n}, S_{n-1},(n+1)^0,(n+1)^1,\cdots,(n+1)^d)$ ，需要找一个矩阵使得：

$\vec V_n = M \cdot \vec V_{n-1}$

考虑 M 前面两行，形式如下：

$M = \begin{pmatrix} a & b & c_0 & c_1 & \cdots & c_d \\ 1 & 0 & 0 & 0 & \cdots & 0 \\ 0 & 0 & ? & ? & \cdots & ? \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ 0 & 0 & ? & ? & \cdots & ? \\ \end{pmatrix}$

于是问题转换到求由 ? 组成的矩阵 $M_0$ ，要恰好使得：

$M_0 \cdot \begin{pmatrix} n^0 \\ n^1 \\ \cdots \\ n^d \end{pmatrix} = \begin{pmatrix} (n+1)^0 \\ (n+1)^1 \\ \cdots \\ (n+1)^d \end{pmatrix}$

右边作二项展开，取各个单项式 $n^i , i \in [n]$ 系数构成的矩阵即得 $M_0$ , 构建分块矩阵得到最终矩阵 $M$ 即可得到递推向量 $\vec V^T_n = (S_{n}, S_{n-1},(n+1)^0,(n+1)^1,\cdots,(n+1)^d)$ 的表达式：

$\vec V_n = M^{n-2} \cdot \begin{pmatrix} 1 \\ 1 \\ 3^0 \\ 3^1 \\ \cdots \\ 3^d \end{pmatrix} \ n \ge 2$

但是这题其实很简单，因为需要求解的 n = 2023 ，所以直接把迭代写成循环就 ok 了。

Exp（矩阵解法）：

# sagemath 9.5
from random import randint 
import gmpy2 as gp 
from Crypto.Util.number import *
from Crypto.Cipher import AES 
from hashlib import md5 
from binascii import * 
# fibonacci general formula
a =  12760960185046114319373228302773710922517145043260117201359198182268919830481221094839217650474599663154368235126389153552714679678111020813518413419360215
b =  10117047970182219839870108944868089481578053385699469522500764052432603914922633010879926901213308115011559044643704414828518671345427553143525049573118673
m =  9088893209826896798482468360055954173455488051415730079879005756781031305351828789190798690556659137238815575046440957403444877123534779101093800357633817
seq =  [1588310287911121355041550418963977300431302853564488171559751334517653272107112155026823633337984299690660859399029380656951654033985636188802999069377064, 12201509401878255828464211106789096838991992385927387264891565300242745135291213238739979123473041322233985445125107691952543666330443810838167430143985860, 13376619124234470764612052954603198949430905457204165522422292371804501727674375468020101015195335437331689076325941077198426485127257539411369390533686339, 8963913870279026075472139673602507483490793452241693352240197914901107612381260534267649905715779887141315806523664366582632024200686272718817269720952005, 5845978735386799769835726908627375251246062617622967713843994083155787250786439545090925107952986366593934283981034147414438049040549092914282747883231052, 9415622412708314171894809425735959412573511070691940566563162947924893407832253049839851437576026604329005326363729310031275288755753545446611757793959050, 6073533057239906776821297586403415495053103690212026150115846770514859699981321449095801626405567742342670271634464614212515703417972317752161774065534410, 3437702861547590735844267250176519238293383000249830711901455900567420289208826126751013809630895097787153707874423814381309133723519107897969128258847626, 2014101658279165374487095121575610079891727865185371304620610778986379382402770631536432571479533106528757155632259040939977258173977096891411022595638738, 10762035186018188690203027733533410308197454736009656743236110996156272237959821985939293563176878272006006744403478220545074555281019946284069071498694967]
ct = bytes.fromhex("37dc072bdf4cdc7e9753914c20cbf0b55c20f03249bacf37c88f66b10b72e6e678940eecdb4c0be8466f68fdcd13bd81")

def get_poly_matrix(n):
    pr.<x> = PolynomialRing(ZZ)
    vecs = []
    for i in range(n):
        f = (x+1)**i
        cs = f.coefficients(sparse = False)
        cs = cs + (n - len(cs))*[0]
        vecs.append(cs)
    return matrix(ZZ,vecs)

def vecN(n):
    if n == 1:
        return [1]
    if n == 2:
        return [1]
    else:
        init_vec = vector(GF(m),[1]*2 + [ 3**i for i in range(10)])
        return M**(n-2) * init_vec
    
m1 = get_poly_matrix(10)
zero_m = zero_matrix(ZZ,10,2)
M1 = block_matrix(ZZ,[zero_m, m1],ncols = 2)

m0 = [
    [a,b] + seq,
    [1] + [0]*11
]
M0 = matrix(ZZ,m0)

M = block_matrix(GF(m), [M0,M1], nrows = 2)
ans = vecN(2023)[0]
k = unhexlify(md5(str(ans).encode()).hexdigest())
aes = AES.new(k,AES.MODE_ECB)
print(aes.decrypt(ct))

Alexei needs help again

和上题类似：

$S_n = \left\{ \begin{array}{**lr**} 1 & n \le 2 \\ aS_{n-1} + bS_{n-2} + f(n - 1), & n \ge 3. \end{array} \right.$

此时 $f(n)$ 如下，给定一个数集 $\mathbb{S}$ ，满足：

$f(n) = \sum_{m\in \mathbb{S}} I(m|n)$

其中 I 表示括号内表达式为真则为 1，否则为 0 ， $f(n)$ 即一个计数器：n 能整除数集 $\mathbb S$ 中的数的个数。笔者没有成功构建出矩阵，因为这个函数比较难进行代数表达。于是思考斐波那契数列中常数部分的一般化表达，记斐波那契数列为 $F_n$ 。

不考虑常数项部分，根据上节给出的一般斐波那契数列矩阵表达式（ $a = b = 1$ ）：
$\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} a & b \\ 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix} = \begin{pmatrix} a & b \\ 1 & 0 \end{pmatrix}^{n-2} \cdot \begin{pmatrix} 1 \\ 1 \end{pmatrix} \quad n \ge 2$
记一般斐波那契数列的递推矩阵为 $M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$
现在 $S(n)$ 中加入了常数项 $f(n-1)$ ，考虑一个简单的事实，对于任意 $i < n$ , $f(i)$ 在 $S_n$ 中累加了多少次？记这个次数为 $Count(n,i)$ ，我们会发现巧合的是，固定 $i$ 之后 $Count(n,i)$ 也恰好是一个斐波那契数列，递推公式与斐波那契数列数列一致。准确来说：
$Count(n,i) = Count(n - 1,i) + Count(n - 2,i)$
更具体地，写成表达式就是，注意 $Count(n,i) = 0 \ \forall n \le i$ ，下标 1 表示取结果第一维：
$Count(n,i) = F_{n-i} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n - i - 2} \cdot \begin{pmatrix} 1 \\ 1 \end{pmatrix}_1 \quad n \ge i + 2$
我们发现对任意整除 $\mathbb{S}$ 中的数 , 所有 $f(s)$ 在 $S_n$ 中累加的次数，就是最终递推公式中常数项 $f(n)$ 对 $S_n$ 的总影响。考虑一个固定的数 $s \in \mathbb{S}$ , 则它对最终 $S_n$ 中的贡献为：
$C(s)_n = F_{n-s} + F_{n-2s} + \cdots + F_{n-ks} , \quad k = \lfloor n/s \rfloor$
写成矩阵递推公式即：
$\begin{pmatrix} C(s)_n \\ C(s)_{n-1} \end{pmatrix} = (M^{n-s} + M^{n-2s} + \cdots + M^{n-ks}) \cdot \begin{pmatrix} 1 \\ 1 \end{pmatrix} , \quad k = \lfloor n/s \rfloor$
即一个矩阵等比数列求和！
我们求出每个 $s \in \mathbb{S}$ 中的等比数列和，再累加起来，就是 $f(n)$ 项在递推公式中对 $S_n$ 的贡献。最终结果为 :
$S_n = F_n + \sum_{s \in \mathbb{S}} C(s)_n$

等比数列需要注意的两个点是：

乘法不可交换，求和公式要写作 $(1-q)^{-1} a_1(1-q^n)$ （手动推导一下）
矩阵不一定可逆，上述 $(1 - q) ^ {-1}$ 可能不存在。

Exp 实现：

# sagemath 9.5
from random import *
import gmpy2 as gp 
from Crypto.Util.number import *
from Crypto.Cipher import AES 
from hashlib import md5 
from binascii import * 
seq = #
m = #
M = #
ct = # 

m0 = [
    [1,1],
    [1,0]
]
_M = matrix(Zmod(M),m0)

def cseq(i, seq = seq):
    ct = 0
    for j in seq:
        if i%j == 0: 
            ct+=1 
    return ct 

def homework(i, seq = seq):
    if i == 1: return 1 
    if i == 2: return 1 
    else: 
        return (homework(i-2, seq)+homework(i-1,seq)+cseq(i-1, seq) )%M 

def Fib(n):
    if n <=2 :
        return 1
    else:
        return (_M^(n -1))[0][0]
    
def extra_cal(m, num):
    a0 = m % num - 1
    max_exp = m - num - 1 
    assert (max_exp - a0) % num == 0
    k = (max_exp - a0)//num + 1
    q = _M^num
    if a0 == -1:
        k = k - 1
        a0 = a0 + num
    A0 = _M^a0 
    MM = (1/(1-q))*A0*(1-q^k)
    return MM[0][0]

def Fib_plus(n, seq = seq):
    R = Fib(n)
    for num in seq:
        R += extra_cal(n, num)
    return int(R % M)

# seq_test = [3,5]
# print(Fib_plus(15,seq_test))
# print(homework(15, seq_test))
ans = Fib_plus(m,seq)

k = unhexlify(md5(str(ans).encode()).hexdigest())
aes = AES.new(k,AES.MODE_ECB)
msg = aes.decrypt(ct)
print(msg)

注 : 前面 MT19937 随机数的恢复和回溯就不写了，可以找找板子自己恢复 $m,M$ , 最后解出来是这个， 3tl2nv1kn54o4ty4tv4z61b61lt50j54j1761ko1tt50h17d4va1gh5391lw1gi4va6w0，还套了一层 MISC，我只能说国内赛真的会搞心态。
吐槽：这题槽点非常之多，附件更新了三次，笑死，最开始的源代码根本不对，解完了再来个 MISC，我是真的绷不住了，MISC 占领国内 CTF 是吧，此处省略 n 句礼貌用语。

在精度 600 比特的实数域上的比值 $k = data1/data$ , 由于 data1 和 data2 都只有 256 比特，因此可以格基规约直接求出 data1， data2，然后得到 $p - q$ ，从而分解 n。格的构造很简单，参考 exp。

Exp

# sagemath 9.5
prec = 600
ring = RealField(prec)
k = 1.42870767357206600351348423521722279489230609801270854618388981989800006431663026299563973511233193052826781891445323183272867949279044062899046090636843802841647378505716932999588
c = 1046004343125860480395943301139616023280829254329678654725863063418699889673392326217271296276757045957276728032702540618505554297509654550216963442542837
n = 2793178738709511429126579729911044441751735205348276931463015018726535495726108249975831474632698367036712812378242422538856745788208640706670735195762517
leak = 1788304673303043190942544050868817075702755835824147546758319150900404422381464556691646064734057970741082481134856415792519944511689269134494804602878628

K = int(ring(k)*2**600)
M = [
    [K,1,0],
    [2**600,0,1]
]
M = matrix(ZZ,M)
L = M.LLL()
r,d2,d1 = L[0]
d1 = abs(d1)
d2 = abs(d2)
assert is_prime(d1) and is_prime(d2)

N = d1*d2
d = int(inverse_mod(d1,(d1-1)*(d2-1)))
pmq = int(pow(leak,d,d1*d2))
PR.<x> = PolynomialRing(ZZ)
f = (x + pmq)*x - n
print(f.roots())

p = f.roots()[0][0]
q = n//p
assert p*q == n

d = int(inverse_mod(65537,(p-1)*(q-1)))
m = pow(c,d,n)
from Crypto.Util.number import *
print(long_to_bytes(int(m - d2)))

CrazyTreat

思路：

P,Q部分泄露了 P 的约高位300，因此可以 coppersmith 分解 clown 得到 P, Q
利用欧拉公式 $m^p = m \mod p \\ m^q = q \mod q \\ m^s = m \mod r$ , 构造方程 $(P - x)(Q-x)(R-x) = 0 \mod n$ , 利用 coppersmith即可求解小根，得到我们需要的 m ，即最后一个素因子。
解密 RSA 即可。

Exp

# sagemath 9.5
clown =  128259792862716016839189459678072057136816726330154776961595353705839428880480571473066446384217522987161777524953373380960754160008765782711874445778198828395697797884436326877471408867745183652189648661444125231444711655242478825995283559948683891100547458186394738621410655721556196774451473359271887941209
trick =  13053422630763887754872929794631414002868675984142851995620494432706465523574529389771830464455212126838976863742628716168391373019631629866746550551576576

n = 924936528644761261915490226270682878749572154775391302241867565751616615723850084742168094776229761548826664906020127037598880909798055174894996273670320006942669796769794827782190025101253693980249267932225152093301291975335342891074711919668098647971235568200490825183676601392038486178409517985098598981313504275523679007669267428032655295176395420598988902864122270470643591017567271923728446920345242491655440745259071163984046349191793076143578695363467259
P = 569152976869063146023072907832518894975041333927991456910198999345700391220835009080679006115013808845384796762879536272124713177039235766835540634080670611913370463720348843789609330086898067623866793724806787825941048552075917807777474750280276411568158631295041513060119750713892787573668959642318994049493233526305607509996778047209856407800405714104373282610244944206314614906974275396096712817649817035559000245832673082730407216670764400076473183825246052
Q = 600870923560313304359037202752076267074889238956345564584928427345594724253036201151726541881494799597966727749590645445697106549304014936202421316051605075583257261728145977582815350958084624689934980044727977015857381612608005101395808233778123605070134652480191762937123526142746130586645592869974342105683948971928881939489687280641660044194168473162316423173595720804934988042177232172212359550196783303829050288001473419477265817928976860640234279193511499
R = 502270534450244040624190876542726461324819207575774341876202226485302007962848054723546499916482657212105671666772860609835378197021454344356764800459114299720311023006792483917490176845781998844884874288253284234081278890537021944687301051482181456494678641606747907823086751080399593576505166871905600539035162902145778102290387464751040045505938896117306913887015838631862800918222056118527252590990688099219298296427609455224159445193596547855684004680284030

c =  10585127810518527980133202456076703601165893288538440737356392760427497657052118442676827132296111066880565679230142991175837099225733564144475217546829625689104025101922826124473967963669155549692317699759445354198622516852708572517609971149808872997711252940293211572610905564225770385218093601905012939143618159265562064340937330846997881816650140361013457891488134685547458725678949

cut = 207
PR.<x> = PolynomialRing(Zmod(clown))
f = trick + x 
p_low = f.small_roots(X = 2**207, beta=0.45)[0]

p_low = 76347864203588455868161824448305083084387260376528823546715135
p = p_low + trick
q = clown//p
assert p*q == clown

PR.<x> = PolynomialRing(Zmod(n))
r = (P-x)*(Q-x)*(R-x)
rm = r.monic()

_R = ZZ(rm.small_roots(X=2**256)[0])
N = ZZ(p)*ZZ(q)*ZZ(_R)

e = 65537
phi = (p-1)*(q-1)*(_R-1)
d = int(inverse_mod(e,phi))
m = pow(c,d,N)
from Crypto.Util.number import *
print(long_to_bytes(int(m)))

Alexei Needs Help

Alexei needs help again

Signin

CrazyTreat