1.題目

import gmpy2
import libnum
p = 165671388464282893752584125326556029512354679397368368220857653376434416617078001900277406804267355663751513682840337558216904117069008267677893985727230492593325173603042964427743989984503434019470910507115109513170452698000355325984181538737533266814217005071768519044490852862204995798270365958824235849109
q = 175651490687332204443530543796451733955950430025312028126121651885555378220332519727808277499974413469921166403868820510889929291685634889104148327524274922826871445228415469568630177323596856932622756981153120631004723510221017019084277515594390301668628385485041270510393136114778320441820348165683480429509
e = 867
c = 6660001775826165629475223259336063470824903598186378856629188913679962282858793440376297567100421858667621016533483512334538109479346679782212732404845310757840479720395378527082706256828554622756778693485769299876503864622653683484618754126624570844775655043102572727811993886306928017735680155402682728596637511542728152370291378415159847960544753739367663869108893974077536246398983936117278361731006622247248095303296948707291551372192438544963005437790454911837030171627510656854263564906498378877435418362195839052305558446674564302895256267149210518288365132749899457979906841577497745489758722670048505543942
n = p * q
phi_n = (p - 1) * (q - 1)
d = gmpy2.gcd(e // 6, phi_n)
m = pow(c, d, n)
#niyuan = gmpy2.invert(e, phi_n)
print(m)
print(libnum.n2s(int(m)))

2.e和phi不互素思路

首先我們要對RSA有基本的認知，私鑰如何求解d ≡ e?1 mod phi，那么如果gcd(e,phi)1,不就是代表逆元不存在嗎？解密也就無法進行下去了。

假設gcd(e,phi)=t?=>gcd(e//t,phi)=1由t=gcd(e,phi),得出t1=e//t即gcd(t1,phi)=1所以私鑰dt1=invert(t1,phi)根據這個求出c=m^(e)%n=>c=m^(t1*t)%n=>c=(m^t)^(t1)%n,滿足gcd(t,phi)=1=>mt=c^(d1)%n,這里的mt=m^t最后開方求出m即可

3.解題腳本

import gmpy2 
import libnum  p = 165671388464282893752584125326556029512354679397368368220857653376434416617078001900277406804267355663751513682840337558216904117069008267677893985727230492593325173603042964427743989984503434019470910507115109513170452698000355325984181538737533266814217005071768519044490852862204995798270365958824235849109
q = 175651490687332204443530543796451733955950430025312028126121651885555378220332519727808277499974413469921166403868820510889929291685634889104148327524274922826871445228415469568630177323596856932622756981153120631004723510221017019084277515594390301668628385485041270510393136114778320441820348165683480429509
e = 867  # 公鑰指數（注意：與φ(n)不互質）
c = 6660001775826165629475223259336063470824903598186378856629188913679962282858793440376297567100421858667621016533483512334538109479346679782212732404845310757840479720395378527082706256828554622756778693485769299876503864622653683484618754126624570844775655043102572727811993886306928017735680155402682728596637511542728152370291378415159847960544753739367663869108893974077536246398983936117278361731006622247248095303296948707291551372192438544963005437790454911837030171627510656854263564906498378877435418362195839052305558446674564302895256267149210518288365132749899457979906841577497745489758722670048505543942n = p * q  
phi = (p - 1) * (q - 1)# 處理e與φ(n)不互質的情況
t = gmpy2.gcd(e, phi)  # 計算e和φ(n)的最大公約數
print(f"gcd(e,phi) = {t}")  # 調試輸出：查看gcd值t1 = e // t  # 將e分解為t和t1
assert gmpy2.gcd(t1, phi) == 1  # 驗證t1與φ(n)互質（關鍵檢查點）# 第二步：對互質部分進行正常RSA解密
dt1 = gmpy2.invert(t1, phi)  # 計算t1的模逆元（即d1 = t1^-1 mod φ(n)）
mt1 = pow(c, dt1, n)  # 部分解密得到m^t mod n（因為c = (m^t)^t1 mod n）
print(f"m^t mod n = {mt1}") # 第三步：解決不互質部分（開t次方）
s, is_exact = gmpy2.iroot(mt1, t)  # 對m^t開t次方求m
assert is_exact  # 確保能完整開方（驗證m^t < n）
print(f"m = {s}")  # 調試輸出：查看解密后的明文數值flag = libnum.n2s(int(s))
print("Flag:", flag)