Mixed

1.题目

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

2.思路

(1)求p

从题中得知\(h_0=(2023p+2024)^{q_1}\ \%\ n_2\)

\[ \begin{gather} h_0=(2023p+2024)^{q_1}\ \% \ n_2 \\ \downarrow \\ h_0=(2023p+2024)^{q_1}+kn_2 \\ \downarrow \\ h_0=k_1p+2024^{q_1}+kp{q_1} \\ \downarrow ^{两边同时模p} \\ h_0\%p=k_1p\%p+2024^{q_1}\%p+kp{q_1}\%p\\ \downarrow \\ h_0\%p=2024^{q_1}\%{q_1} \\ \downarrow \\ h_0+k_2p=2024^{q_1} \\ \downarrow \\ 2024^{q_1}-h_0=k_2p \end{gather} \]

所以只要gcd(\((2021^{q_1}-h_0),n_2\))就可以求出p，但是此时并不知道q1的值，所以继续推导

\[ \begin{gather} n=p*{q_1}\\ \downarrow^{两边同时除以q} \\ n/{q_1}=p \\ \downarrow \\ n/{q_1}-1=p-1 \\ \downarrow^{两边同时乘以q} \\ n-{q_1}=(p-1){q_1} \\ \downarrow \\ {q_1}=n-(p-1){q_1} \\ \end{gather} \]

\[ \begin{gather} h_0\%p=2024^{n-{q_1}(p-1)}\%p\\ \downarrow\\ h_0\%p=2024^n\%p\ *(2024^{-{q_1}})^{p-1}\%p\\ \downarrow^{根据费马小定理a^{p-1}\%p=1\%p}\\ h_0\%p=2024^n\%p\\ \downarrow\\ h_0+k_3p=2024^n\\ \downarrow\\ 2024^n-h_0=k_3p \end{gather} \]

现在式子中都是已知数，可以求出p=gcd(\((2024^{n_2}\%n_2-h_0),n_2\))

(2)求q

\[ \begin{gather} h_1=(2024{p_1}+2023q)^{114}\%{n_1}\\ h_2=(2023{p_1}+2024q)^{514}\%{n_1}\\ \downarrow\\ h_1^{514}=(2024{p_1}+2023q)^{114*514}\%{n_1}\\ h_2^{114}=(2023{p_1}+2024q)^{514*114}\%{n_1}\\ \downarrow\\ h_1^{514}=(2024{p_1}+2023q)^{114*514}+k_1{p_1}q\\ h_2^{114}=(2023{p_1}+2024q)^{514*114}+k_2{p_1}q\\ \downarrow\\ h_1^{514}\%q=(2024{p_1}+2023q)^{114*514}\%q+k_1{p_1}q\%q\\ h_2^{114}\%q=(2023{p_1}+2024q)^{514*114}\%q+k_2{p_1}q\%q\\ \downarrow\\ h_1^{514}\%q=(2024{p_1})^{114*514}\%q\\ h_2^{114}\%q=(2023{p_1})^{514*114}\%q\\ \downarrow\\ h_1^{514}=(2024{p_1})^{114*514}+k_3q\\ h_2^{114}=(2023{p_1})^{514*114}+k_4q\\ \downarrow\\ h_1^{514}*2023^{114*514}=(2024{p_1})^{114*514}*2023^{114*514}+k_5q\\ h_2^{114}*2024^{114*514}=(2023{p_1})^{514*114}*2024^{114*514}+k_6q\\ \downarrow\\ h_1^{514}*2023^{114*514}=(2023*2024{p_1})^{114*514}+k_5q\\ h_2^{114}*2024^{114*514}=(2023*2024{p_1})^{114*514}+k_6q\\ \downarrow^{h_2-h_1}\\ h_2^{114}*2024^{114*514}-h_1^{514}*2023^{114*514}=k_7q\\ \end{gather} \]

得出\(h_2^{114}*2024^{114*514}-h_1^{514}*2023^{114*514}\)是q的倍数，通过gcd(\(h_2^{1919}*2022^{1919*9191}-h_1^{9191}*2021^{1919*9191}\),n1)即可得出q（为了减少计算量可以把每项模n1再进行计算）

现在有了p和q，按常规计算出m即可得到flag

3.解题脚本

from Crypto.Util.number import *
import gmpy2

e = 65537

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

q = GCD(pow(h2,114,n1)*pow(2024,114*514,n1)-pow(h1,514,n1)*pow(2023,114*514,n1), n1)
p = GCD(pow(2024,n2,n2)-h0, n2)

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

print(long_to_bytes(m))