SYC安洵杯2023 Alexei needs help again

只有一解的密码题，还是自己太菜了。总是缺点什么。

前三个题被k烂了就不写了。

~~本来不想写的，看官方wp的代码太烂了。还是照官方给的卢卡斯公式来写一下。~~

还是贴一下原题代码，不然以后看不知道题目

n = 666
M = getrandbits(512) 
m = getrandbits(512)
seq = [getrandbits(32) for _ in range(n)] 
def cseq(i):
    ct = 0
    for j in seq:
        if i%j == 0: 
            ct+=1 
    return ct 

def homework(i):
    if i == 1: return 1 
    if i == 2: return 1 
    else: return (homework(i-2)+homework(i-1)+cseq(i-1) )%M # If u want mod, come and get it!
ans = homework(m) 

k = unhexlify(md5(str(ans).encode()).hexdigest())
aes = AES.new(k,AES.MODE_ECB)
data = flag + (16-len(flag)%16)*b"\x00"
ct = hexlify(aes.encrypt(data)) 
print(ct)
print(seq)

分析

具体来说就转成斐波那契数列固定间隔求和问题。~~早看到这里了，后面没想到好方法，还是tl哥强~~

$seq=[s_0,s_1,\cdots,s_n]\\ ans_i=F(m-s_i)+F(m-2*s_i)+\cdots+F(m-k*s_i)\\ k=m//s_i$ $ans=F(m)+\sum_{i=0}^nans_i$

比赛的时候没找到这个东西，有这个就很简单了

$F(n+k)=L(k)*F(n)+(-1)^{k+1}*F(n-k)$

看见了这个等式，就相当于LCG序列求和了，就常规矩阵就好。

我定义一个类来处理。

对于每一个$s_i$,数列和$ans_i$的第一项$c=m\%s_i$

$ans_i=F(c)+F(c+s_i)+F(c+2*s_i)+\cdots+F(c+k*s_i)\\c+k*s_i==m$ $class\ A:A_i=F(c+i*s)$

所以class A的每一项间隔为$s_i$，所以

$A_k=L(s_i)*A_{k-1}+(-1)^{s_i+1}*A_{k-2}$

即对每一个$s_i$，满足上述LCG递推式，上述所有等式在mod M下进行。

对每一个$ans_i$单独求解

$a=L(s_i),b=(-1)^{s_i+1}\\ MM=\begin{pmatrix}a&b&\\1&&\\1&&1\end{pmatrix}\\ S=\begin{pmatrix}A_1\\A_0\\A_0\end{pmatrix}$ $ans_i=MM^{k-1}*S\ ,k=m//s_i$

这里感觉还挺有意思，只要是线性都能转成矩阵的来表达。感觉学到了什么

exp

from Crypto.Cipher import AES
from hashlib import md5
from binascii import *
mod=12829041659394284307857221062697666364062866719089961329835167571637466859464459350524888222088988864340987270671846091784055132762437055993937758559806211
m=3510693360590935015859429855757884833472774716576844765150309153038369141267530117727135794989011465836700343607021684660331665506948350652663352653803583
ZZ=Zmod(mod)

def fibonacci(n):
    if n == 0:
        return 1
    M = Matrix(ZZ,[[1, 1], [1, 0]])
    M_power = M ** (n)
    return M_power[0, 0]
def lucas(n):
    if n == 0:
        return 2
    if n == 1:
        return 1
    if n == 2:
        return 3
    A = Matrix(ZZ,[[1, 1], [1, 0]])
    power = A^(n-2)*vector(Zmod(mod),[3,1])
    return power[0]

seq = [2595326515, 23180772, 3997687803, 3326360477, 2276157283, 2467209954, 2500673804, 1143199883, 2641431550, 1419029027, 350264058, 4053087274, 4053958055, 2513326751, 339420864, 
1011193327, 271856605, 1513947525, 2020417055, 883563173, 1547578383, 547304334, 351829798, 3642312362, 2921110987, 3148301320, 817993595, 1421185599, 1799335143, 835191090, 2150648746, 3967401199, 3003502005, 643104359, 2609214076, 3840706282, 686462863, 2978749817, 2989880195, 4116411541, 638017306, 4120616638, 1597189550, 3011705547, 3083335311, 2675246638, 2686884427, 3499126467, 4092013115, 1613371790, 1970975028, 969658130, 99110934, 3607741353, 1759331867, 2676116875, 2773617686, 2361770583, 89532012, 3083783497, 2234712564, 541053324, 2626904587, 3087162337, 2640404694, 3300233207, 3647200745, 3547410617, 3582999314, 2465603703, 2126377719, 4149124654, 138476758, 523401679, 2433383115, 3669851616, 86525204, 1374898657, 4045200933, 2868686313, 2337739152, 2281926848, 3989569066, 4070566171, 857308185, 2713842069, 1899103910, 805038016, 3704354207, 1581480981, 736387671, 2741130638, 507077521, 2206337801, 922151594, 2838078904, 3505028480, 3420665932, 1284793827, 2523062091, 3401665715, 3623189546, 1809973029, 3894323261, 2258205953, 1426203731, 2207475504, 1421407269, 712883663, 3025774184, 1437505487, 354824074, 4279560597, 2188573763, 1179625177, 2579894844, 3194995724, 1283521420, 1135324449, 1473616416, 715835593, 2107056108, 691042641, 2371082653, 1254628608, 3158228295, 818000855, 2557001734, 2040988505, 52312640, 252680184, 1981836677, 3089079663, 480804531, 1761541936, 126588265, 1210366606, 3737411248, 781392104, 3783893270, 3425167192, 792267934, 614551393, 2806921629, 2637795287, 382775306, 1478063635, 2461883536, 3584856992, 3573870252, 3398089673, 3977329470, 1810189120, 2563127601, 2610993483, 3703813521, 176152943, 934506937, 4075489690, 2159461914, 1711569283, 3681905316, 2391446598, 2802858914, 1599608333, 582339237, 4083811130, 3603659097, 1820065766, 1940652046, 1601051937, 1686029702, 3214225708, 626096315, 3303210795, 845320257, 1628905577, 2623206441, 3863048561, 3282287714, 2093932519, 691822855, 2810972244, 2734202132, 3103273726, 3374394469, 99122473, 1198473250, 2850988793, 475290944, 355799740, 2007358658, 1832567807, 409261747, 4128221233, 3186243510, 1505678597, 118934195, 2801556035, 2831148108, 3633663226, 2383066815, 4029162187, 4186049492, 1557349332, 3767979960, 3786287408, 2944862336, 2641414000, 586491880, 1158885215, 
609689300, 3716903319, 1189655822, 1285350048, 3626771802, 1630239597, 4232045507, 2836741297, 3540650942, 873784185, 3956580871, 1654596190, 828962693, 2241103382, 987968067, 2867681479, 542661969, 2732885133, 2291511952, 107639675, 1199900588, 3503460002, 4037358916, 3353436988, 3106421078, 2979993076, 2923808598, 1857157100, 2827347292, 2609932672, 
2584524205, 2089293405, 3129636000, 2220950206, 3138359470, 1932925027, 2234221191, 1370581559, 3028901069, 3710562178, 1131137053, 4080224718, 2924102520, 3276138392, 2605901145, 2273060669, 3877110064, 3177786839, 3410727907, 4132091933, 2481607479, 879351358, 3418049200, 3609105477, 2813795936, 2260936777, 617558951, 3157207817, 2488107340, 2898477888, 2524829762, 172627595, 822059892, 2860011718, 1684712121, 1984236044, 3688136037, 2078776978, 480328333, 93141946, 3474173863, 1234020763, 2249863005, 3745921519, 1457081143, 2385853482, 2248913964, 820071300, 3718075972, 1324074018, 475088565, 2958253316, 1341289223, 1620637057, 3994397025, 93449389, 308791574, 3490958092, 2540967073, 2310889365, 
702942123, 117751104, 4018639883, 2248435460, 2843381024, 3574659543, 2452028923, 2132263591, 3476164200, 8954269, 3206697476, 2853057742, 1456365483, 1082982734, 1068636703, 667607909, 219824541, 3870245303, 2091060006, 2964047264, 4029811900, 2356039555, 1908336693, 3718355579, 3638876848, 3216566492, 416832882, 2828647873, 4001012267, 2807111458, 1792797750, 1734892518, 3375708100, 3207637928, 3046584777, 945849513, 3073419563, 3271332119, 3883933284, 4186848929, 4097911388, 3612544183, 1194826711, 1233284669, 3482512536, 
1404018410, 2078197945, 2926152771, 63919719, 1330565043, 3837864559, 4116517348, 2691851961, 811807617, 2918150785, 2106740789, 1189082063, 874346773, 273086454, 1163652664, 2711964943, 1934985821, 1958980279, 8173558, 3264410820, 2294316976, 3314567282, 1502597925, 1468525675, 4119644439, 2120100930, 3903541325, 3149609846, 681075835, 2586592743, 1927148755, 506338789, 3624911484, 3657313748, 1914029921, 1384381536, 1529509472, 1616387737, 2680552716, 551196734, 588351272, 904040766, 3795641990, 3697883395, 1783651815, 2132576849, 197369352, 3175716923, 2597870651, 3658263056, 70001269, 1014930358, 2158445352, 221540231, 585585263, 2122302668, 399937442, 3210646977, 2268011990, 1721927806, 2865058856, 364263286, 2727747683, 4195126833, 3245443564, 3976083696, 177640136, 3701720923, 1394773300, 2926912972, 2574226055, 3768190066, 409666084, 1435373724, 14365298, 3121902131, 2944018561, 2671982360, 1683156955, 161015936, 3135869882, 497046853, 2857165322, 1651104105, 4136468209, 1310516600, 2915061784, 3073788860, 2777209233, 481503339, 3411502921, 472775448, 1956651704, 41551628, 1694173440, 1530788479, 3048560079, 1990395570, 3597635648, 3096309687, 1316587810, 190303266, 1755799976, 2733339124, 1962984809, 3086256135, 1304353757, 1808355161, 3526607550, 540366595, 2137389092, 4165091800, 3868217849, 865298295, 3967375579, 934437269, 842158193, 2145833847, 907161725, 1063817862, 3917584131, 
1382471752, 2290848699, 217016948, 2078740054, 3512023515, 3034471208, 822114632, 3290750093, 80754213, 2158167962, 1154816936, 2272639070, 3071834023, 3843663245, 2524329183, 3132931396, 729789660, 1086713161, 1479517061, 1203195638, 729214877, 2913728711, 2022939474, 1233771489, 2303109708, 2428751488, 4282556167, 1836561513, 3558386301, 2505864835, 
2016641451, 108653676, 4098077830, 905952785, 1814034784, 2901745130, 1189887853, 1681683501, 1198355966, 936372521, 3898325049, 215824261, 4116789808, 2820232323, 2890038521, 4182729512, 604732871, 4016768031, 2321663893, 2515037504, 4050314636, 702794677, 2961459925, 40400416, 4095059760, 956219451, 3849649494, 1922015975, 1744193407, 1138648647, 3315175304, 1115571875, 552591714, 3854175337, 3989311045, 2085781317, 1614257910, 3011965436, 3162375497, 829393285, 1201153327, 771917993, 360299656, 3759219688, 1308014821, 1367955176, 3953655004, 2282274211, 442767499, 2183054867, 3358816752, 3212849234, 4020234505, 372924337, 622276414, 713136280, 2268577293, 1001460604, 584394700, 2535981592, 860213893, 1796518622, 2383281908, 225709650, 459353092, 1336677515, 3045944304, 1977786023, 2401414751, 2849468597, 1795713298, 2614581318, 1328455769, 3784827954, 1405248029, 1260540058, 1644012036, 3503196746, 2708457053, 1650697250, 1129515384, 4190369094, 3722054749, 1478291090, 4241183563, 484701892, 2549014848, 1447709776, 4212153585, 1797864056, 3600764365, 3404412904, 3329305753, 2650982244, 963111196, 4092022285, 1756942112, 3265977672, 2386627115, 3144670390, 3914974036, 3446371882, 290290818, 3862974638, 2566756978, 3542661279, 2191748912, 825063906, 4059545118, 4038340163, 1979460431, 3062262439, 4067702476, 2717224905, 285845768, 530036375, 2325511596, 1272518080, 1758606610, 256991409, 1878156850, 3580339279, 2107013750, 1170026025, 681215682, 2911622954, 698626001, 332605315, 3488313095, 2132113161, 2726482290, 1222080383, 2978934938, 2181753820, 3161618585, 3692850587, 4051216623, 2686955509, 3015070988, 1112203990, 34245660, 3339982780, 220670341, 3589606923, 1115872535, 29967396, 2774865228, 4125098481, 1476995888, 78926061, 2482265247, 1609184053, 2012706446, 1451065950, 2674196994, 2927007707, 1436218421, 2064582175, 2197505437, 1107809803, 2138239872, 3731147470, 473071614, 2243697427, 2977343456, 3723291677, 480836923, 1777047244, 2758559347]

print(fibonacci(m-1))
class A:
    def __init__(self,s,m):
        self.s=s
        self.max=m//s
        self.n=m%s
        self.L=lucas(self.s)
    def nn(self,i):
        return fibonacci(self.n+i*self.s)
    def ab(self):
        return self.L,(-1)^(self.s+1)
    def sumall(self):
        a,b=self.ab()
        M=Matrix(ZZ,[[a,b,0],[1,0,0],[1,0,1]])
        S=vector(ZZ,[self.nn(1),self.nn(0),self.nn(0)])
        if (self.max-1)<0:
            return 0
        return (M^(self.max-1)*S)[-1]
# m=100
ans=fibonacci(m-1)
for i in seq:
    A1=A(i,m-1)
    ans+=A1.sumall()
#ans=4107452036166885538951409493731995805964894461071730493363712019873475510428779458602891565117593745273115233986541619492036968083722386786003154431663642
c='b8bbc6d03690b53f01f3076fe530a80c7d98d367ce6fe766f3cd78584f3d5bda1fca3ea4ec1a37689c22a3302ebc182c735c4c7b62cd95165b8db1c810bf93defe2ffb5c5bcacb60f3e3facee2e69449'

k = unhexlify(md5(str(ans).encode()).hexdigest())
aes = AES.new(k,AES.MODE_ECB)
msg = aes.decrypt(bytes.fromhex(c))

#b'3tl2nv1kn54o4ty4tv4z61b61lt50j54j1761ko1tt50h17d4va1gh5391lw1gi4va6w0\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'

CTF

CISCN华中赛区线下 Crypto

华中线下

2023-06-25 Crypto

CTF

2023ciscn badkey1&baykey2

ciscn badkey1&badkey2

2023-05-29 Crypto

CTF