4月份参加的比赛，搞定了一道 Crypto ,还是太菜了 XD

下载附件得到以下两个文件：

output：

output

task.py

task

由 task.py 可知本题为 RSA 类别的题目，output 的第一部分为 phi=(p-1)*(q-1)，第二部分为 N=p*q，第三部分为按位加密的密文。

phi：

9433451661749413225919414595243321311762902037908850954799703396083863718641136503053215995576558003171249192969972864840795298784730553210417983714593764557582927434784915177639731998310891168685999240937407871771369971713515313634198744616074610866924094854671900334810353127446778607137157751925680243990711180904598841255660443214091848674376245163953774717113246203928244509033734184913005865837620134831142880711832256634797590773413831659733615722574830257496801417760337073484838170554497953033487131634973371143357507027731899402777169516770264218656483487045393156894832885628843858316679793205572348688820

N：

9433451661749413225919414595243321311762902037908850954799703396083863718641136503053215995576558003171249192969972864840795298784730553210417983714593764557582927434784915177639731998310891168685999240937407871771369971713515313634198744616074610866924094854671900334810353127446778607137157751925680243990905528141072864168544519279897224494849206184262202130305820187569148057247731243651084258194009459936702909655448969693589800987266378249891157940262898554047247605049549997783511107373248462587318323152524969684724690316918761387154882496367769626921299091688377118938693074486325995308403232228282839975697

enc：

[8496947713967625688747051917345259919849436616378127353206205506038021293461527020161946574400176146891485385957784205610395979657632413714059788772154009625247319812180747880252792622607786831662770906618083260055375307283152779156046374949223651130182151637961986612962279450309600099007561129237942698815049037854849280208609836192610790091804945437651984019023488119575757202741525228601541312849428856402128908223668136814737595015697632233564641564297265843315503282099677245418512862603605854455747457289844970204592796599838807708185464118863991858628774060793091469902148505618063854053683802025104272242737L, 3821975570238613357809086371567645294936011650887348963699940559362491350302427260103053136240897247131898829678001091430328324888976446850850398553379083807041417622422302483244782735821628339123481969782358378946550852168035289256770460985872083926320944628963996424431121655082533250397690221796910212343850884623723978193835574954928395310744288586634227750389554284155693066143225219180179924909105208241568967550733169693235766203194833688349527756455298707071600274394141846255062034273957007624449391385234198744038949086834422360238042411148350057735839143597829523818407329475481765129224815789601127610789L, … ]

已知 phi 和 N 可以求出 p 和 q，但由于e是随机生成且数值比较大（x = random.randint(1, N)），无法通过常规方法解题。

经过搜索找到 https://ctftime.org/writeup/16120 中类似的题目（属于Goldwasser–Micali cryptosystem），知道 p，q 可以通过二次剩余判定进行解密。

解密脚本如下（需要安装Sage Math）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#python3 sage Math
n=9433451661749413225919414595243321311762902037908850954799703396083863718641136503053215995576558003171249192969972864840795298784730553210417983714593764557582927434784915177639731998310891168685999240937407871771369971713515313634198744616074610866924094854671900334810353127446778607137157751925680243990905528141072864168544519279897224494849206184262202130305820187569148057247731243651084258194009459936702909655448969693589800987266378249891157940262898554047247605049549997783511107373248462587318323152524969684724690316918761387154882496367769626921299091688377118938693074486325995308403232228282839975697
phi=9433451661749413225919414595243321311762902037908850954799703396083863718641136503053215995576558003171249192969972864840795298784730553210417983714593764557582927434784915177639731998310891168685999240937407871771369971713515313634198744616074610866924094854671900334810353127446778607137157751925680243990711180904598841255660443214091848674376245163953774717113246203928244509033734184913005865837620134831142880711832256634797590773413831659733615722574830257496801417760337073484838170554497953033487131634973371143357507027731899402777169516770264218656483487045393156894832885628843858316679793205572348688820
p=(n-phi+1-((n-phi+1)^2-4*n).nth_root(2))//2
q=n//p
print (n == p*q)
Fp=Integers(p)
flag=[...]#加密的flag 密文
f2=[0 if Fp(f).is_square() else 1 for f in flag]
print (hex(int('0'+''.join(str(i) for i in f2),2))[:])

脚本解密结果为十六进制的字符串：0x666c61677b62643466313739302d663461322d343930342d623464322d3864623862323466643836347d，Hex解码即可得到flag：

flag{bd4f1790-f4a2-4904-b4d2-8db8b24fd864}