原理

总结一下RSA问题中 $gcd(e,\varphi(n)) \neq 1$ 的情况。
令 $gcd(e,\varphi(n)) = b$ ， $e=a \cdot b$ ，那么 $a$ 与 $\varphi(n)互素$ ，可以求得 $a$ 的逆元 $d$ 。

m^{ab} \equiv c \pmod{n} \\ c^{d} = m^{abd} \equiv m^a \pmod{n}

这个时候对 $m^a$ 的结果在模 $n$ 意义下开 $a$ 次根号即可。这里通常 $a$ 比较小，否则需要考虑 $+ k \cdot n$ 然后再开 $a$ 次根号。
还有一种特殊情况就是 $gcd(e,\varphi(n)) = e$ ，原理比较简单分别求出 $c$ 在模 $p,q$ 下的 $e$ 次根号的可疑解再利用中国剩余定理两两组合，脚本如下。

from Crypto.Util.number import *
def gth_root_mod_n(c, g, p, q):
    n = p * q
    Fp = GF(p)
    Fq = GF(q)
    roots_p = Fp(c).nth_root(g, all=True)
    roots_q = Fq(c).nth_root(g, all=True)
    for rp in roots_p:
        for rq in roots_q:
            m = crt([int(rp), int(rq)], [p, q])
            flag=long_to_bytes(m)
            if b'???' in flag:
                print(flag)

这里由于 $rp,rq$ 可能组合数量比较多，所以加一个if语句方便判断。
下面是一些例题

例题

Weird_E_Revenge

题目

from Crypto.Util.number import *
import random
from secret import flag
table='abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
pad=100-len(flag)
for i in range(pad):
    flag+=random.choice(table).encode()
e=343284449
m=bytes_to_long(flag)
assert m>(1<<512)
assert m<(1<<1024) 
p=getPrime(512)
q=getPrime(512)
r=getPrime(512)
print('p=',p)
print('q=',q)
print('r=',r)
n1=p*q
n2=q*r
c1=pow(m,e,n1)
c2=pow(m,e,n2)
print('c1=',c1)
print('c2=',c2)
#p=11820891196647569262137841192985418014377132106496147254821784946481523526822939129065042819464351666077658751406165276121125571355594004514547517855730743
#q=10450390015864176713581330969519712299844487112687677452105216477861582967322473997670559995588440097951786576039009337782247912476227937589298529580432797
#r=9484954066160968219229920429258150817546418633451929876581842443665029377287119340232501682142185708534413073877473741393278935479791561681402673403009771
#c1=69574855207460025252857869494766338442370688922127811393280455950372371842144946699073877876005649281006116543528211809466226185922844601714337317797534664683681334132261584497953105754257846471069875622054326463757746293958069752489458646460121725019594141157667480846709081917530190233900184428943585065316
#c2=66183492015178047844987766781469734325646160179923242098082430373061510938987908656007752256556018402101435698352339429316390909525615464024332856855411414576031970267795270882896721069952171988506477519737923165566896609181813523905810373359029413963666924039857159685161563252396502381297700252749204993228

分析

这道题目构造了一个比较特殊的情况 $gcd(e,\varphi(n))=e$ ，套用上面的脚本是无法实现的， $e$ 太大了，运行过程会爆内存，好在题目提供了两组 $n,c$ 。
这个时候我们考虑

res1 \equiv m^e \pmod{p} res2 \equiv m^e \pmod{q} res3 \equiv m^e \pmod{r}

如果把 $m^e$ 看作 $x$ 那么利用中国剩余定理可以得到

m^e \equiv res \pmod{pqr}

乍一看我们的问题并没有被简化，但是通过分析我们知道 $gcd(e,\varphi(n)) \neq 1$ 的罪魁祸首是 $q$ 也就是说 $gcd(e,p-1)=gcd(e,r-1)=1$ 。所以我们在上式的基础上可以化作一个正常的RSA题目。

m^e \equiv (res \pmod{q}) = c^\prime \pmod{pr}

脚本如下

from Crypto.Util.number import *
from libnum import *
p=11820891196647569262137841192985418014377132106496147254821784946481523526822939129065042819464351666077658751406165276121125571355594004514547517855730743
q=10450390015864176713581330969519712299844487112687677452105216477861582967322473997670559995588440097951786576039009337782247912476227937589298529580432797
r=9484954066160968219229920429258150817546418633451929876581842443665029377287119340232501682142185708534413073877473741393278935479791561681402673403009771
c1=69574855207460025252857869494766338442370688922127811393280455950372371842144946699073877876005649281006116543528211809466226185922844601714337317797534664683681334132261584497953105754257846471069875622054326463757746293958069752489458646460121725019594141157667480846709081917530190233900184428943585065316
c2=66183492015178047844987766781469734325646160179923242098082430373061510938987908656007752256556018402101435698352339429316390909525615464024332856855411414576031970267795270882896721069952171988506477519737923165566896609181813523905810373359029413963666924039857159685161563252396502381297700252749204993228
e=343284449
n1=p*q
n2=q*r
m1=c1%p
m2=c2%q
m3=c2%r
m=solve_crt([m1,m2,m3],[p,q,r])
n3=p*r
m%=n3
phi=(p-1)*(r-1)
d=inverse(e,phi)
print(long_to_bytes(pow(m,d,n3)))