RSA-e和phi不互素
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⁻¹ 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)