[ctf.show 元旦水友赛 2024] crypto

感觉半个多月回家没有打开过电脑了。看到ctf.show上元旦的比赛，才想起似乎应该看看。

月月的爱情故事

上来这就是个小脑洞题，给了一大段文字和一个base64的串。并且提示：试试摩斯吧！

从文字上看只有三种标点符号，显然就是.-/ 程序过滤一下，不过无法区分./只能试。

a='你知道吗。月月今天遇到了一个让他心动的女孩，她的名字叫做小雨，太幸运了。小雨是一个活泼可爱的女孩！她的笑容如同春天里的阳光。温暖了月月的心，月月第一次见到小雨是在图书馆里！事情是这样的。当时小雨正在专心致志地看书。阳光洒在她的脸上。让她看起来如同天使一般美丽！月月被小雨的美丽和才华所吸引。开始暗暗关注她。在接下来的日子里。月月开始尝试与小雨接触！和她聊天和学习。他们有着许多共同的兴趣爱好，一起度过了许多快乐的时光，渐渐地！月月发现自己对小雨产生了特殊的感情，他开始向小雨表达自己的心意，然而，小雨并没有立即接受月月的感情！她告诉月月。她曾经受过感情的伤害，需要时间来慢慢修复自己的心灵。月月尊重小雨的决定！他开始用更多的时间和精力来陪伴小雨，帮助她走出过去的阴影。在接下来的几个月里。月月和小雨的关系逐渐升温！他们一起参加了许多校园活动。一起探索了那个城市的角角落落。渐渐地！雨也开始对月月产生了感情。她发现自己越来越依赖他。越来越喜欢他。最终！小雨和月月走到了一起，他们的爱情故事成为了校园里的佳话。让同学们都羡慕不已，他们一起度过了青春岁月，一起经历了成长和进步的喜悦与挫折！他们的感情越来越深厚。也越来越稳定。在他们的恋爱过程中，月月和小雨也学会了如何相处和包容对方！他们互相理解互相支持。一起面对生活中的挑战和困难！他们的爱情让他们变得更加坚强和勇敢，也让他们感受到了生命中最美好的东西。月月相信他们能走得更远，更相信自己不会辜负小雨，当他们遭遇挫折和失败的时候！两人永远不会被打倒。这正是他们彼此爱的力量。在他们空闲的时候，月月经常带小雨出去逛街！晚上一起看电影。有一天！月月说将来他要给小雨一场最美的婚礼，小雨十分感动也十分期盼。就这样。这份约定成为了两人前进的动力。两人共同努力最终一起考上了同一所大学的研究生。两人非常开心彼此深情地看着对方似乎有说不完的情话！研究生三年他们互相帮助一起度过了人生最有意义的大学时光，毕业后两人也很轻松找到了自己心仪的企业。月月没有忘记当初的约定。是的。他要给小雨一场最美好的婚礼。终于！这一天到来了，小雨穿上月月为她定制的婚纱。他们手牵手走向了更美好的未来。场下。所有的嘉宾都为他们鼓掌和欢呼并祝福他们的爱情能够永恒长存。'


b='VTJGc2RHVmtYMS9iVkY0NXp5dGxrZUVoZWZBcWtwSFFkTXF0VUxrMk9pYkxxNzlOSEpNbTlyUDNDdGtLckU0MQpDYUJKbU1JVmNVVlNiM0l6cEhldVd3PT0='


#hint:试试摩斯吧！
b64decode(b)
#U2FsdGVkX1/bVF45zytlkeEhefAqkpHQdMqtULk2OibLq79NHJMm9rP3CtkKrE41
#CaBJmMIVcUVSb3IzpHeuWw==

b = ''.join([i for i in a if i in ['，','。','！']]).replace('！','/').replace('，','-').replace('。','.')
#XNOODSKWMOLGTLGT111
#PASSWORDISYUEYUE666

试出两个结果，密码显然是后边这个，然后拿到B神的puzzleSolver上自动捘

麻辣兔头又一锅

只给了两个数组，这个还真不会，不过网上已经有WP了，看来脑洞真是大。这两个数组里都是斐波那契函数的项数，两组对应的数字导或后取尾字节。正常人应该想不出来，不过作出来的人真多。

#麻辣兔头又一锅/200/题目描述：/听说有人不喜欢短尾巴的兔兔？肿么可能？我也很疑惑呢。
a = [126292,165298,124522,116716,23623,21538,72802,90966,193480,77695,98618,127096,15893,65821,58966,163254,179952,134870,45821,21712,68316,87720,156070,16323,86266,148522,93678,110618,110445,136381,92706,129732,22416,177638,110110,4324,180608,3820,67750,134150,23116,116772,50573,149156,5292]
b = [60144,146332,165671,109800,176885,65766,76908,147004,135068,182821,123107,77538,86482,88096,101725,16475,158935,123018,42322,144694,186769,176935,59296,134856,65813,131931,144283,95814,102191,185706,55744,67711,149076,108054,135112,100344,35434,121479,14506,145222,183989,17548,38904,27832,105943]
#fib函数第126292项与第60144项异或的尾字节
from gmpy2 import fib 
bytes([(fib(a[i])^fib(b[i]))&0xff for i in range(len(a))])
#b'ctfshow{6d83b2f1-1241-4b25-9c1c-0a4c218f6c5f}'

NOeasyRSA

这个算是个中规中矩的CTF题吧。给了一个函数，并且已知f(w,a),f(w,b)求f(B,a),其中p,u,v,w已知，只是a,b未知。

def f(x, n):  
    return (pow(u,n,p)*x + v*(1-pow(u,n,p))*pow(1-u, -1, p)) % p  
A = f(w, a)
B = f(w, b)
key = long_to_bytes(f(B, a))[:len(FLAG)]

这是个初中数学里的换元，并不需要求出a只需要求出 $u^{a}$ 即可

from flag import FLAG
 
def f(x, n):  
    return (pow(u,n,p)*x + v*(1-pow(u,n,p))*pow(1-u, -1, p)) % p  
 
p = 97201997431130462639713476119411091922677381239967611061717766639853376871260165905989218335681560177626304205941143288128749532327607316527719299945637260643711897738116821179208534292854942631428531228316344113303402450588666012800739695018334321748049518585617428717505851025279186520225325765864212731597
u = 14011530787746260724685809284106528245188320623672333581950055679051366424425259006994945665868546765648275822501035229606171697373122374288934559593175958252416643298136731105775907857798815936190074350794406666922357841091849449562922724459876362600203284195621546769313749721476449207319566681142955460891977927184371401451946649848065952527323468939007868874410618846898618148752279316070498097254384228565132693552949206926391461108714034141321700284318834819732949544823937032615318011463993204345644038210938407875147446570896826729265366024224612406740371824999201173579640264979086368843819069035017648357042
v = 16560637729264127314502582188855146263038095275553321912067588804088156431664370603746929023264744622682435376065011098909463163865218610904571775751705336266271206718700427773757241393847274601309127403955317959981271158685681135990095066557078560050980575698278958401980987514566688310172721963092100285717921465575782434632190913355536291988686994429739581469633462010143996998589435537178075521590880467628369030177392034117774853431604525531066071844562073814187461299329339694285509725214674761990940902460186665127466202741989052293452290042871514149972640901432877318075354158973805495004367245286709191395753
w = 30714296289538837760400431621661767909419746909959905820574067592409316977551664652203146506867115455464665524418603262821119202980897986798059489126166547078057148348119365709992892615014626003313040730934533283339617856938614948620116906770806796378275546490794161777851252745862081462799572448648587153412425374338967601487603800379070501278705056791472269999767679535887678042527423534392867454254712641029797659150392148648565421400107500607994226410206105774620083214215531253544274444448346065590895353139670885420838370607181375842930315910289979440845957719622069769102831263579510660283634808483329218819353
a = randint(0, 2**2048)
b = randint(0, 2**2048)
A = f(w, a)
B = f(w, b)
key = long_to_bytes(f(B, a))[:len(FLAG)]
enc = strxor(FLAG, key)
print(f"{A = }")
print(f"{B = }")
print(f"{enc = }")
 
"""
A = 19000912802080599027672447674783518419279033741329820736608320648294849832904652704615322546923683308427498322653162857743332527479657555691849627174691056234736228204031597391109766621450008024310365149769851160904834246087493085291270515883474521052340305802461028930107070785434600793548735004323108063823
B = 73344156869667785951629011239443984128961974188783039136848369309843181351498207375582387449307849089511875560536212143659712959631858144127598424003355287131145957594729789310869405545587664999655457134475561514111282513273352679348722584469527242626837672035004800949907749224093056447758969518003237425788
enc = b'\xfd\xc1\xb7\x9d"$\xc2\xb0\xb5\xee\xf89\xa4V\x8e\x17\x01K9\xbc.\x92=\x85\x80\xd4\x03\xefAl"\xbd\x8b\xcdL\xb5\xa3!'
"""

#(pow(u,n,p)*x + v*(1-pow(u,n,p))*pow(1-u, -1, p)) % p
#u^a* x + v*(1-u^a)*(1-u)^-1 ==A 
#ka * w - v*(1-u)^-1*ka == A - v*(1-u)^-1
#=> u^a = (A - v*(1-u)^-1)*(w - v*(1-u)^-1)^-1 
ka = (A - v*pow(1-u,-1,p))*pow(w-v*pow(1-u,-1,p),-1,p)%p
kb = (B - v*pow(1-u,-1,p))*pow(w-v*pow(1-u,-1,p),-1,p)%p
f_Ba = (ka*B + v*(1-ka)*pow(1-u, -1, p)) % p
strxor(long_to_bytes(int(f_Ba))[:len(enc)], enc)
b'ctfshow{This_Is_Really_Not_So_Smooth!}'

sign_rand

也不会，只会爆破，但这题真的能爆破，爆破范围是28位。看了WP也不懂，不过记下来也不错。

题目跟梅森旋转有关，但又基本无关。先是生成一个随机序列，然后将这些作为state来设置随机函数。再通过生成的随机数求原来的值

import random
from hashlib import md5
from Crypto.Util.number import *
from flag import flag

def get_state(kbits, k):
    seed = [(random.getrandbits(kbits) >> k) & 0xfffffff for i in range(624)]
    state = (3, tuple(seed + [0]), None)  #state[1]的最后一项正常值为624,这里设置为0,则仅与第0项有关
    return state


def give_gift(kbits, num):
    gift = [random.getrandbits(kbits) for i in range(num)] #kbits=37则每次使用两个32位,加密时使用state[1][60]对应gift的第30项的低32位
    e = random.getrandbits(7)
    l_num = num - e
    s_box = list(range(num))
    random.shuffle(s_box)
    l_gift = [gift[i] for i in s_box[:l_num]]
    return (l_gift, s_box[:l_num], e) #e=60

#取seed的第60项
def enc_flag(state, e):
    key = bytes_to_long(md5(long_to_bytes(state[1][e])).digest())
    enc = bytes_to_long(flag) ^ key
    return enc


kbits, k, num = random.randrange(64), random.randrange(16), random.randrange(400, 600)
#kbits = 37,num=529,e=60
state = get_state(kbits, k) #k [0,15]
random.setstate(state)
gift = give_gift(kbits, num)
enc = enc_flag(state, gift[2])
print(gift, enc)
#---------------------------
gift = ([91463260584, 97520150804, 134987178347, 134745660347, 23369346769, 88869916197, 67723104206, 132211190015, 74383600340, 57357411421, 80301226226, 2847043233, 46071508714, 76391425800, 71113777427, 12603028605, 127607785895, 82661956584, 48539405830, 131191473154, 137430688091, 48026249914, 105523652421, 58217141456, 135651011411, 37099885733, 101903983367, 117525416468, 49720139903, 123719748136, 58611168240, 68135859850, 6355615539, 23769720298, 7999623487, 19601432037, 49460687576, 34510812373, 97988805553, 120381187017, 37643325426, 79314538948, 128727827227, 41938289773, 74120986880, 29052999070, 21215042789, 76176648906, 82899209179, 90338690991, 102277220210, 109016314367, 2419923303, 75246152672, 109203867772, 87030346778, 119151949871, 134868756437, 124854798665, 122116306769, 31536426951, 82104297926, 118556737102, 78417017414, 81807286830, 24688295471, 126360674284, 8870569872, 105339369180, 61910863416, 56597235604, 50122937080, 135836683348, 75685244539, 112566491901, 86217144353, 110999080631, 91114786530, 94967775022, 52680440255, 76947914257, 133052296759, 22589975272, 104632324223, 47428022416, 106941367714, 119250845700, 80196618477, 92917756830, 52764061858, 82855761133, 26800124167, 129317288037, 44051967549, 70500283649, 165355182, 78293334339, 45001066520, 84638985033, 32566871344, 38421055041, 56145488218, 83396525174, 116762960131, 58381974438, 132249926372, 36091120717, 35213963219, 88756092150, 45288405267, 27461079382, 19589246113, 28308681656, 47161727545, 69898448282, 22959597168, 132569999975, 100557577568, 127037292334, 29708117311, 33229333831, 29311547868, 135347707719, 85435007922, 54540391811, 109544478077, 66841548339, 47159376439, 42574542524, 62176229940, 3138675000, 21267865120, 22618290315, 126018690563, 21590061225, 9799239940, 10617934652, 40956988582, 131053131140, 90043238501, 81283244185, 109338223936, 68311960398, 25088200986, 28895564195, 17646619057, 82775422880, 81522377214, 28334564831, 100791800926, 85872403124, 127915503356, 72496838376, 109007653011, 96263138881, 69693106974, 4718076407, 68334177311, 31708464646, 96111162918, 48965277868, 54931198292, 105535767797, 105680940066, 109968562576, 23573023928, 48569942163, 106967716286, 94835446653, 92803971955, 53791818332, 14453746086, 132101017989, 26361874022, 32122658200, 51724426274, 114997634813, 75838224666, 89848273104, 73619960674, 97795812498, 132466249292, 25997032367, 40732063573, 59142286405, 68524304985, 49545031400, 28044368864, 95700359624, 108201671504, 127043767055, 9384509797, 120972803416, 41782179648, 76653307257, 44056421640, 101631026937, 99078185959, 54885001820, 69316726710, 19710227322, 86035277688, 42289562955, 98051921147, 79098792488, 106490144808, 13834874, 69114014086, 4418515159, 109316722991, 92603496375, 68830244931, 111949257703, 102637560761, 5012149380, 43811237017, 4526712578, 102995188930, 9165821006, 63456393327, 68912422322, 104913358841, 108860651772, 52967416635, 84227988465, 101715630295, 26297443306, 110653579906, 91487440397, 116959430145, 83499469513, 48913630229, 76988993305, 41832173701, 13694488408, 135450931748, 39634435716, 41679152695, 126540504548, 91399825525, 99004649347, 19517357430, 8279948639, 133596449559, 1449103211, 50732184406, 52247676129, 74928416312, 64326525401, 124673786795, 92042480385, 24404916254, 99622146133, 51463314254, 36722967192, 4007778602, 39109534005, 120478575332, 99886542155, 5756463131, 91679854224, 3608646835, 35655876863, 121959477025, 20408412916, 36341277711, 43627610089, 24855949002, 128669830633, 70347508117, 9425085453, 2022963949, 5053312318, 63243834495, 21497715007, 5936366400, 44266914863, 119468825913, 91726986385, 126494307832, 93847533617, 22070910941, 20204251399, 42254244260, 60489335607, 40705184865, 80919639775, 73360223499, 132743946450, 88897376509, 103144368275, 9982808097, 131532980487, 91081435155, 78915930938, 72790758029, 120696671493, 78255313725, 13309583510, 23841020581, 116634908326, 73400462338, 57323203784, 46210923108, 41134724194, 43089395737, 118503520944, 111039189867, 99418263301, 59298127775, 45252940179, 40345195432, 16841439060, 100422187771, 65791698364, 61167532292, 30338914082, 14930863404, 4703203112, 124912009656, 9195518396, 18552364400, 7303227315, 105753747788, 3079040268, 116480022128, 1215344111, 9934249637, 76178148585, 20033461169, 87344780021, 72391242953, 129540048833, 15495213032, 49963621916, 84362224351, 97100635498, 105086571577, 51150506310, 118045067326, 65966867679, 7925108854, 131280748402, 66481282233, 107509392827, 78521145687, 35456851157, 97461157961, 30244093674, 24123083085, 27909475052, 69646113342, 131930611276, 97792139629, 135917828529, 32305782568, 59325645293, 84962280113, 74529748221, 22659244720, 54776660364, 66934871192, 14824496938, 37231294479, 102244198902, 31674646475, 128196911226, 90158594889, 121714346066, 64647669235, 105263204191, 127988380741, 130175056631, 114272442969, 135960937840, 62465712860, 32333037569, 137012433094, 92929672123, 86030288893, 73602847949, 58136148471, 118893337093, 97692245318, 99539974338, 116231441994, 32445182154, 115683286754, 114711297102, 102210385893, 7687212992, 73626254322, 242951419, 5952493527, 96817591608, 45197171621, 122928115217, 106192593180, 99889552302, 125596158762, 136959359712, 67291405558, 71974425715, 115789979144, 59321975202, 84748820897, 133266408556, 6800817333, 110678933813, 96832595879, 97681824039, 89341148630, 84626208563, 58523733456, 93000780873, 68444996084, 775177345, 17204124036, 129474447019, 73589942581, 65415043899, 131703332659, 101783987222, 61388598262, 103435807803, 104030629529, 19123072760, 63612557945, 38245223725, 54345357864, 62016904380, 34602169486, 51229280420, 66624757580, 68760378559, 131556923700, 21935621011, 36349470821, 10120892182, 25883848878, 71735922493, 62883391871, 90647098, 41388569318, 52175456448, 71822304690, 19251125978, 91308465291, 50110754397, 91050175581, 83697004380, 6165622900, 129188497722, 71424103672, 57569171583, 13220579058, 118266862549, 21791521844, 70064705221, 83120075317, 83316886784, 111745960042, 26241940218, 32402511427, 118604113535, 98847819357, 117058412964, 57680263912, 83166477192], [508, 300, 327, 517, 431, 195, 41, 162, 110, 358, 433, 105, 40, 256, 172, 50, 474, 55, 67, 284, 215, 118, 513, 98, 120, 26, 155, 298, 4, 233, 243, 267, 428, 478, 494, 226, 146, 488, 20, 113, 143, 136, 49, 236, 128, 346, 501, 264, 498, 0, 413, 30, 410, 99, 1, 220, 443, 369, 290, 374, 119, 511, 483, 199, 248, 351, 388, 335, 131, 79, 496, 245, 414, 244, 158, 451, 255, 412, 47, 473, 254, 95, 299, 462, 169, 519, 493, 12, 257, 385, 432, 417, 59, 93, 455, 324, 52, 90, 407, 288, 112, 34, 528, 29, 192, 101, 419, 203, 123, 176, 177, 167, 204, 445, 416, 485, 196, 302, 424, 425, 6, 418, 258, 17, 370, 262, 227, 326, 387, 294, 295, 174, 25, 188, 81, 408, 469, 11, 472, 80, 400, 84, 382, 448, 201, 344, 7, 502, 163, 312, 484, 349, 239, 108, 411, 315, 303, 377, 36, 383, 78, 339, 491, 271, 216, 187, 322, 140, 405, 296, 402, 516, 450, 22, 482, 361, 371, 249, 453, 64, 152, 72, 194, 66, 345, 492, 447, 58, 486, 357, 149, 200, 83, 212, 219, 504, 333, 23, 439, 376, 457, 332, 153, 348, 210, 237, 173, 359, 129, 179, 426, 71, 19, 321, 338, 444, 139, 307, 515, 88, 266, 475, 182, 323, 336, 354, 272, 384, 330, 2, 211, 446, 238, 397, 230, 278, 141, 506, 181, 70, 316, 314, 459, 235, 121, 286, 76, 518, 280, 43, 111, 62, 487, 429, 524, 364, 86, 228, 353, 275, 104, 441, 268, 13, 500, 68, 87, 109, 403, 520, 231, 391, 42, 51, 328, 253, 436, 60, 497, 313, 481, 522, 53, 61, 420, 225, 189, 325, 183, 56, 100, 229, 27, 39, 3, 184, 291, 415, 454, 75, 28, 107, 347, 421, 166, 224, 279, 16, 342, 206, 207, 171, 368, 198, 456, 464, 406, 365, 151, 320, 161, 9, 89, 479, 142, 259, 401, 232, 523, 449, 150, 218, 15, 97, 287, 133, 458, 221, 63, 185, 350, 74, 135, 404, 466, 214, 116, 507, 355, 213, 178, 318, 423, 126, 395, 465, 440, 452, 157, 366, 190, 343, 467, 247, 509, 91, 205, 114, 193, 409, 375, 269, 373, 389, 148, 69, 396, 398, 317, 145, 122, 147, 512, 32, 130, 386, 94, 435, 310, 57, 422, 308, 305, 217, 8, 154, 156, 309, 223, 44, 24, 82, 160, 392, 477, 356, 134, 54, 138, 378, 331, 379, 250, 96, 489, 306, 399, 46, 18, 283, 470, 21, 360, 209, 168, 495, 180, 514, 191, 270, 510, 381, 186, 442, 31, 390, 5, 85, 92, 363, 33, 127, 197, 285, 380, 265, 48, 352, 505, 208, 438, 329, 468, 282, 45, 159, 301, 362, 341, 65, 263, 393, 222, 521, 175, 293, 37, 490, 35], 60) 
enc = 912396759652812740801869061695733452669218533249083289698313292427681899514848561025221753354562922565560034

1是random.setstate这个函数，参数是(3,(...,624),none)这里第2个有625项，最后一项是数字624，前边的将作为state的624个值。这个题的漏洞也就在这里，它把624改成了0，这样可以猜一下再试一下，就能得到结论，这个再生成的随机数只与第1个数有关，而且这个数大小只有28位，血腥的暴力还是可以作的。按WP的原来，可以通过矩阵还原，原理应该是跟生成方法有关吧。

2，gift经过了乱序处理并截了一部分，好在加密只使用了第60项，由于kbits=37所以每一项需要两个32位随机数才能得到，所以实际上对应的是gift的第30项的尾32位

3，在复现的时候发现在sage里生成随机数设置tuple有问题，所以将这块在python里生成，然后直接拿数字去sage生成矩阵（当最后为0时，这个矩阵是固定的，跟啥都没关系），然后用矩阵求左得到state

'''
python state = (3,(...624..., 624),None)
                                ^
                                | 当此值为0时,仅与第0相关
'''
'''
from random import Random
s_tmp = []
for i in range(32):
    rng = Random()
    s = [0]*624  #仅与第1项有关联
    s[0] = 1 << (31 - i)
    rng.setstate((3,tuple(s + [0]),None))
    s_tmp.append(rng.getrandbits(32))
'''
def buildT():
    s_tmp = [2282758660, 1141379330, 537135105, 285344832, 2281775616, 1140887808, 572541064, 2164260928, 143135266, 71567633, 304087176, 152043588, 76021794,541345937, 16908288, 2281779744, 1073778704, 572804225, 16917060, 134746624, 71567760, 33555584, 16777792, 8388896, 541083792, 64, 134222368, 16, 33817737, 16908868, 2, 4194449]
    T = matrix(GF(2), 32, 32)
    for i,tmp in enumerate(s_tmp):
        T[i] = vector(GF(2), [int(x) for x in bin(tmp)[2:].zfill(32)])
    return T

def get_key(key1):
    T = buildT()
    a = [int(i) for i in bin(key1)[2:].zfill(32)]
    a = matrix(GF(2), a)
    b = T.solve_left(a)
    c = ''.join([str(i) for i in b.list()])
    return (int(c, 2))

def dec_flag(enc, key):
    key = bytes_to_long(md5(long_to_bytes(key)).digest())
    dec = enc ^^ key
    return long_to_bytes(dec)

#gift[1]的第30项=51, data = gift[0][51]
data = gift[0][gift[1].index(30)]

key1 = (data & 0xffffffff)
key = get_key(key1)
print(dec_flag(enc, key))
# b'ctfshow{F2AD971D-66C2-2D1D-69D6-CE7DE2A49B35}'

哪位师傅知道这个是什么密码啊？

作完这个题一看WP，有一句话：没文化真可怕！

import os
from Crypto.Util.number import *

F = lambda x: x * F(x-1) if x > 0 else 1   #x!
G = lambda x, y: F(x) // (F(y) * F(x-y))   #Cxy//y!

def get_keys(n: int):
    p = getPrime(-11+45-14)
    print('Please wait...')
    s_list, t_list, u_list = [], [], []
    for i in range(n):
        print(f'Progress: {i+1} / {n}')
        while True:
            t, s = sorted(getPrime(101) for _ in 'NB')
            u = (G(s, t) % p) & 0xFF
            if (u != 0):
                s_list.append(s)
                t_list.append(t)
                u_list.append(u)
                break
    return (s_list, t_list, p), u_list 

FLAG = os.getenv('FLAG', 'ctfshow{never_gonna_give_you_flag}')
pubkey, privkey = get_keys(len(FLAG))
ciphertext = bytes(x ^ k for x, k in zip(FLAG.encode(), privkey))
print(f'{pubkey = }')
print(f'{ciphertext.hex() = }')


pubkey = ([1930151072665128353588734655537, 2031058415674042196947620002273, 2144863946566435250228859586391, 2204574594761764684195846866839, 2477828607642661430260650973099, 2012386255018188844730867225381, 1762053451781461688652926282351, 1432075294504073608412671363229, 2085972009627276502163685682109, 2356830745677576130564410837629, 2095586676389124116002874906797, 1834099033698162708991115616977, 1791840766877362122811192536119, 2466612221451031915438145152813, 2055669435753006117069851698387, 1945191352090331802358773354047, 1598384509815635624743575801559, 1734584046009665963460321198971, 1703291088463476485960557553999, 2109460578568002211705878463579, 2379112636954266631858709609297, 1562853987941503005527197137193, 2083127151176772865178055099623, 2531791820688251514294784000163, 2419383541724950707481401557879, 1296127912800791494923183159227, 1911458001898055656608791844607, 1946167119803607551220553328777, 1904512983764066793751568905519, 1916230655982693714440043335807, 2512594341307292494592511422453, 2440117129864142342199757415119, 1979899755487925628129637546103, 2194400805715240118886434137993, 2523064995519689703569774021401, 2114574063402299913941092965571, 2381937349061799920669414958047, 2527981840329087465484497504541, 1668501048060086166105530258267, 1806403234834223830758220690463, 1911471080586461098261469429017, 1339541095681286408183031500617, 2127226624970258161117347546391, 2099378880330092247471103157591, 1817979380085600544511932938511], [1873159646454515246371181002643, 1804013691198418310618414108771, 1812615686339814327371280875597, 1800999264458084929945557444697, 1588066281211920550828189195481, 1496728051871062086801855668249, 1610673865527813598676056481461, 1325014119495418821090259991869, 1505791236680543235885282691973, 2348852764652026182965706639791, 1824135303268604720787073263413, 1486244711603932363682065611853, 1501151560524825317540824912799, 2276201700800208762185986149943, 1499253769931649556267344414137, 1490433621401772012533417542801, 1595412721633675118799193648283, 1615752012174860792342907699697, 1513845996053825310963856994387, 1839003732354104170410208839841, 1512261084747354177738456894811, 1513982572527568106680720393517, 1510595005874590962689775078269, 2298184399106399375164579208311, 2293559104060307668205289912223, 1295846257932101474274146277553, 1492967151340481835523691948141, 1879040002400116343011683347177, 1511237029995360063024713359843, 1519174814929746722197973524961, 2396968969794891970606734609163, 1611070391525078159832743120311, 1723857192281627381668741919753, 1668048777606203158944880846963, 2413123925251955100868310793203, 1576149931563624798731285775403, 2310882643431694718623705671961, 1507535832710254742220535229081, 1527490022413322878990854933667, 1525819980673483186726141204931, 1619579736922652814136731512099, 1305493665697683014167156810817, 2052693973422009018345307802839, 1818586801929550427018944143523, 1777527018545957748163522728169], 942317)
enc=bytes.fromhex('cd0b53e2bb84f8581353701aabf7be2ab6b9c548a26394e47386842afde4fdaa018e73b75b6a120b109bdf4a99')

原是里有两个函数F和G，很显然F是阶乘，而G是 $C_{n}^{m} %p$

对于这么大的数是根本算不出阶乘来的。不过由于题目给出G(s,t)%p !=0 所以可以有一个解法：把阶乘展开每p项为一组，这样每组都是

(k*p+1)*(k*p+2)*...(k*p+p-1)*(k+1)*p，

最后是残域

(k*p+1)*...(k*p+x%p)

其中k $\in (1...x/p)$ 由于要求u!=0所以这些带k的项可以过滤掉，然后式子就变成

$(p-1)!^{x/p}*(p-x%p)!$ *(x/p)!

然后重写两个函数，注意有限域里没有除法，需要求逆运算

from gmpy2 import fac,invert
s_list,t_list,p = pubkey
fac_p1 = fac(p-1)%p
def F(x):
    if x<p:
        return fac(x)
    v = x//p 
    return pow(fac_p1,v,p) * F(v) * fac(x%p) %p

G = lambda x, y: F(x) * invert(F(y) * F(x-y),p)%p 
bytes([((G(s_list[i],t_list[i])%p)&0xff)^enc[i] for i in range(45)])
#b'ctfshow{b0964981-47b6-4c8f-b9ab-7090ffb8961a}'

完整后看WP原来是lucas定理，怎么没记得学过呢，真是没文化呀。这个方法可能跟lucas定理有出入但是结果是对的，而且时间也不算很长。再作的lucas定理的解法：

#lucas定理解法
C = lambda n,m,p: fac(n)* invert(fac(m)%p,p) * invert(fac(n-m)%p, p)%p 
Lucas = lambda n,m,p: 1 if m == 0 else (C(n % p, m % p, p) * Lucas(n // p, m // p, p)) % p

bytes([(Lucas(s_list[i],t_list[i], p)&0xff)^enc[i] for i in range(45)])