WP_2024HSCCTF_CRYPTO_MIXED

题目

import libnum
from flag import flag
from Crypto.Util.number import *

m = libnum.s2n(flag)
e = 65537
q = getPrime(1024)
q1 = getPrime(1024)
p = getPrime(1024)
p1 = getPrime(1024)
n = p * q
n1 = q * p1
n2 = p * q1
c = pow(m, e, n)
h0 = pow(2023 * p + 2024, q1, n2)
h1 = pow(2024 * p1 + 2023 * q, 114, n1)
h2 = pow(2023 * p1 + 2024 * q, 514, n1)

print(f'n1 = {n1}')
print(f'n2 = {n2}')
print(f'c = {c}')
print(f"h0 = {h0}")
print(f"h1 = {h1}")
print(f"h2 = {h2}")

# n1 = 14689930167621480307737218855980844793204825453111553640005733004311399091452749419195261723160562669712981077205514482387428543859060408330555457873612388970840075555219318724209919379670375754436986322725018229701175825510253987615017542205904982728558285520666278391637251512741084978804344612886660251741043298476839942441197788722691248949008018299101517153067904692310160459839327965213126456776042470327923603098133019640956702820908299859534676381094974148722668171932091455546601087513513432342088579253210930555185169910878657816252698605590059713584044287411998445279104965229112287195772355914014694372863
# n2 = 17914624231045471060767877283214815212078805279600237578901916178851704643026979522270658635212967285131654546207286875722198040564094351690066028556053274118826426726436922152056884333790850220488793722836758989770231697392015361745717234225528175411653330848965062023338707342188196332661335758350340958332400847642883219650661408895191363079017750144776587598058350920393498114498603046807597288603882782473322630631915467470131090200369527436760313289344813744004003957932606166823948354564464154141854938585629799995141656546295799610158824771809513458197812936595649326475123400845178122171317543843802357238737
# c = 13183645788828584902734975771833842634134772971197066374278716198331982362845597338541987579827576129126962300555023319276896080171662261983323670516457816608069076576704379871559881585100353737989915143190277856145677733747073530969459479608854483866886381406790221076900624083605418670450439523062190633487764982399334967431524831264337949814367905185282600511829794170139623625545288981992093108619556180352620171550284923452864402624195790781899415138548827684042790774382313520961335293225295922563245148598807498320652973409239921962292395269739151692443069186695137458774227330748775469621908962878548784542656
# h0 = 5690435858632801053001568276569200811072324786394351282330736437777643891675713760267573500875018036769819201228707494676033534733516436880434000381152290529934127584047681184797730806321117079578438213106595566102910231831641994870770844810797745935336962801658360541755214075101149142486964461669833043007174173934693214526552375910644574723526164021660497474760514459351270699055076380763188021265735007339272243426286470006040246926184305520860068095134003662496837644875879106318233600478000160450338727054920011063536387532763661934972965357326471012678550188382945584128136131833085006239075931753900705852481
# h1 = 12771704142231361356944931328203992824809472923288035056741145310446323135378739806430357600688780862532180394967607429708811767590541126019805423171023560973250443508427614362854583240402451944730512334908779225174763498122005198084487562912524477476241978066554026569609494641830034817298185887790987627444544391680388213205514284116732325350187204519755399841372144149840914651521842402817701298224803289451378581226204084757079457612984358925767378458994608562174048729806309230061089552045138514542758457243626150673888166620841134063713151240297774551489301504222933127458884374866611598279831562420720169790688
# h2 = 10768269134499905916388929049595509895751098112372323618798542159569174051578701710549609054808995774168931375186213550074900373023970882450822655786787740452681278837907191091338575561570211280095894576674089666981683405385847773819238581725093823429776684561667462626941518248024517707992035438082636259838822562843169441572048956484831730615047363383911454662789736761572912893234212875097536978423758275178050708616505311352511923810654873380808201395656416903900326634569672173228265730515727327832588326581592485713225927319225942965110285477266200380452637746037672411388696006933080509164615786616058664496851

解

本题可以看成一个混合加密的缝合怪，将几道类似的题目拼接到了一起，下面先放参考别的师傅写的WP

https://www.cnblogs.com/mumuhhh/p/17783610.html

具体而言分成了两个解密题，作用为别为求解p和q

第一个为

h0 = pow(2023 * p + 2024, q1, n2)

上述公式中发现只有一个未知数（p和q1可以看成一个未知数） 因此理论上可以轻松解出，实际上应该也不难。。。具体使用到了费马定理，前面已经讲过，化简后一行代码即可解决

p = gmpy2.gcd(h0-pow(2024,n2,n2),n2)

第二个为

h1 = pow(2024 * p1 + 2023 * q, 114, n1)
h2 = pow(2023 * p1 + 2024 * q, 514, n1)

两个未知数（p1、q）,两个方程，理论上也能解决

但实际上这个要复杂一点点。。。

原理不是很懂，但是可以简单讲讲过程

首先需要求解一个叫k的东西，这个k与114和514这两个数有关，具体而言

k = 2*57*257

如何计算的呢？

2代表的含义是114和514的最大公因数

2=gmpy2.gcd(114, 514)

然后57是114与2的商，257是514与2的商

57=114//2
257=514//2

知道了k之后就可以带入计算了，具体模板如下：

h5 = pow(h1,257,n)*pow(2023,k,n)-pow(h2,57,n)*pow(2024,k,n)
h6 = pow(h1,257,n)*pow(2024,k,n)-pow(h2,57,n)*pow(2023,k,n)
k1 = inverse(pow(2023,2*k,n)-pow(2024,2*k,n), n)
k2 = inverse(pow(2024,2*k,n)-pow(2023,2*k,n), n)
h3 = h5 * k1 % n
h4 = h6 * k2 % n
q = GCD(h3, n)

求出p、q之后就可以解密了

n = p * q
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(libnum.n2s(int(m)))

over!