RSA中e和phi不互素问题的总结归纳

整理完之后发现，这类题本身难度不算特别大，但我之前因为数学基础薄弱，很多关键点理解不到位；再加上没有熟悉的解题模板/套路，导致遇到不互素的题目时经常卡住，甚至做不出来。现在把这类问题系统地整理一下，方便之后复盘和套用。

整体思路：e小的时候使用有限域开方，e如果比较大，需要使用AMM算法，常用算法还有CRT算法和hensel定理。

AMM算法是什么：本质上也是一种有限域开方。

CRT什么时候用：如果说m的位数比较小，小于其中一个素数，那么就不需要使用CRT，如果CRT的位数比较大，则需要在各素数下进行有限域开方，然后进行CRT恢复m。

类型一：有限域开方

例题 [LitCTF 2023]e的学问

from Crypto.Util.number import *
m=bytes_to_long(b'xxxxxx')
p=getPrime(256)
q=getPrime(256)
e=74
n=p*q
c=pow(m,e,n)
print("p=",p)
print("q=",q)
print("c=",c)
#p= 86053582917386343422567174764040471033234388106968488834872953625339458483149
#q= 72031998384560188060716696553519973198388628004850270102102972862328770104493
#c= 3939634105073614197573473825268995321781553470182462454724181094897309933627076266632153551522332244941496491385911139566998817961371516587764621395810123

e比较小，直接进行有限域开方，本题不需要crt

解码代码

from Crypto.Util.number import *
p= 86053582917386343422567174764040471033234388106968488834872953625339458483149
q= 72031998384560188060716696553519973198388628004850270102102972862328770104493
c= 3939634105073614197573473825268995321781553470182462454724181094897309933627076266632153551522332244941496491385911139566998817961371516587764621395810123
e=74
m_p= Zmod(p)(c).nth_root(e, all=True)
for mpp in m_p:
    flag=long_to_bytes(int(mpp))
    if b'flag{' in flag or b'CTF{' in flag or b'ctf{' in flag:
        print(flag)

类型二：解决 rabin 加密

rabin加密和RSA加密很像，但它是一个独立的公钥加密体系

rabin加密的特征是：p%4==3，q%4==3，e=2

例题 [syc 2025] baby_rabin

from Crypto.Util.number import *
from gmpy2 import next_prime
​
from secret import flag
e=8
while 1:
    p = getPrime(512)
    q = next_prime(p + 2 ** 400)
    r = getPrime(512)
    if(p%4==3 and q%4==3 and r%4==3):
        break
assert p%4==3 and q%4==3 and r%4==3
n=p*q*r
hint=p*q
m=bytes_to_long(flag)
C=pow(m,e,n)
print(f'C={C}')
print(f'n={n}')
print(f'hint={hint}')
'''
C=451731346880007131332999430306985234187530419447859396067624968918101700861978676040615622417464916959678829732066195225132545956101693588984833424213755513877236702139360270137668415610295492436471366218119012903840729628449361663941761372974624789549775182866112541811446267811259781269568865266459437049508062916974638523947634702667929562107001830919422408810565410106056693018550877651160930860996772712877149329227066558481842344525735406568814917991752005
n=491917847075013900815069309520768928274976990404751846981543204333198666419468384809286945880906855848713238459489821614928060098982194326560178675579884014989600009897895019721278191710357177079087876324831068589971763176646200619528739550876421709762258644696629617862167991346900122049024287039400659899610706153110527311944790794239992462632602379626260229348762760395449238458507745619804388510205772573967935937419407673995019892908904432789586779953769907
hint=66035251530240295423188999524554429498804416520951289016547753908652377333150838269168825344004730830028024338415783274479674378412532765763584271087554367024433779628323692638506285635583547190049386810983085033061336995321777237180762044362497604095831885258146390576684671783882528186837336673907983527353
'''

本题目是稍微魔改的rabin加密，但做法是相同的，有限域开方，如果需要，使用crt

解码代码

from Crypto.Util.number import *
C=451731346880007131332999430306985234187530419447859396067624968918101700861978676040615622417464916959678829732066195225132545956101693588984833424213755513877236702139360270137668415610295492436471366218119012903840729628449361663941761372974624789549775182866112541811446267811259781269568865266459437049508062916974638523947634702667929562107001830919422408810565410106056693018550877651160930860996772712877149329227066558481842344525735406568814917991752005
n=491917847075013900815069309520768928274976990404751846981543204333198666419468384809286945880906855848713238459489821614928060098982194326560178675579884014989600009897895019721278191710357177079087876324831068589971763176646200619528739550876421709762258644696629617862167991346900122049024287039400659899610706153110527311944790794239992462632602379626260229348762760395449238458507745619804388510205772573967935937419407673995019892908904432789586779953769907
hint=66035251530240295423188999524554429498804416520951289016547753908652377333150838269168825344004730830028024338415783274479674378412532765763584271087554367024433779628323692638506285635583547190049386810983085033061336995321777237180762044362497604095831885258146390576684671783882528186837336673907983527353
e=8
r=n//hint
m_r= Zmod(r)(C).nth_root(e, all=True)
for mrr in m_r:
    flag=long_to_bytes(int(mrr))
    if b'syc{' in flag or b'CTF{' in flag or b'ctf{' in flag:
        print(flag)

类型三：有限域开方(m较大)

例题 [黑盾杯 2020]Factor

n = 3454083680130687060405946528826790951695785465926614724373
e = 3
c = 1347530713288996422676156069761604101177635382955634367208
gcd(m, n) = 1

分解得到

p=11761833764528579549 q=17100682436035561357 r=17172929050033177661

e也比较小，但是直接套类型一的代码是出不来的，本质原因是m的位数比p，q，r大，此时就得使用crt

解码代码

from Crypto.Util.number import *
p=11761833764528579549
q=17100682436035561357
r=17172929050033177661
n = 3454083680130687060405946528826790951695785465926614724373
e = 3
c = 1347530713288996422676156069761604101177635382955634367208
m_p=Zmod(p)(c).nth_root(e, all=True)
m_q=Zmod(q)(c).nth_root(e, all=True)
m_r=Zmod(r)(c).nth_root(e, all=True)
for mpp in m_p:
    for mqq in m_q:
        for mrr in m_r:
            m=crt([int(mpp),int(mqq),int(mrr)],[p,q,r])
            flag=long_to_bytes(m)
            if b'ctf{' in flag or b'CTF{' in flag or b'flag{' in flag:
                print(flag)

类型四：AMM算法（m比较大）

例题 [NCTF 2019]easyRSA

from flag import flag
​
e = 0x1337
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
n = p * q
​
assert(flag.startswith('NCTF'))
m = int.from_bytes(flag.encode(), 'big')
assert(m.bit_length() > 1337)
​
c = pow(m, e, n)
print(c)
# 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359

当时被这到题目吓到了，主要是时间长，但是学会用tqdm库之后我们就可以轻松的解决这道题目了

我们分别在p和q下面进行AMM之后并没有求出来flag，问题还是同类型三，m的位数超过p和q，那么我们需要进行CRT

解码代码

import random
import time
from tqdm import tqdm
from Crypto.Util.number import *
# About 3 seconds to run
def AMM(o, r, q):
    start = time.time()
    print('\n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            print('[+] Calculating DLP...')
            j = - discrete_log(d, a)
            print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c^r
    result = o^alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    print('Find one solution: {}'.format(result))
    return result
​
def onemod(p,r): 
    t=random.randint(2,p)
    while pow(t,(p-1)//r,p)==1: 
         t=random.randint(2,p)
    return pow(t,(p-1)//r,p) 
 
def solution(p,root,e):  
    while True:
        g=onemod(p,e) 
        may=[] 
        for i in tqdm(range(e)): 
            may.append(root*pow(g,i,p)%p)
        if len(may) == len(set(may)):
            return may
​
​
def solve_in_subset(ep,p):
    cp = int(pow(c,inverse(int(e//ep),p-1),p))
    com_factors = []
    while GCD(ep,p-1) !=1:
        com_factors.append(GCD(ep,p-1))
        ep //= GCD(ep,p-1)
    com_factors.sort()
​
    cps = [cp]
    for factor in com_factors:
        mps = []
        for cp in cps:
            mp = AMM(cp, factor, p)
            mps += solution(p,mp,factor)
        cps = mps
    for each in cps:
        assert pow(each,e,p)==c%p
    return cps
​
c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
e = 0x1337
print(gcd(e,p-1))
print(gcd(e,q-1))
m_p = solve_in_subset(e,p)
m_q = solve_in_subset(e,q)
for mpp in tqdm(m_p):
    for mqq in m_q:
        m=crt([int(mpp),int(mqq)],[p,q])
        flag=long_to_bytes(m)
        if b'NCTF{' in flag:
            print(flag)
            break

运行时间有时候很长，让我一度以为 AMM 算法本身不稳定：有时很快，有时很慢。后来仔细排查才发现，耗时主要不在 AMM，而是在后续的组合/恢复阶段——尤其是把不同模数下的多个候选根进行配对，再用 CRT 合并并逐个筛选时，复杂度会明显上升。 另外，tqdm 用来观察枚举进度和定位性能瓶颈确实很好用。

下面简单说明脚本用法。

solve_in_subset() 函数：

• 第一个参数 t：用于把指数分解成 e = t * (e/t)，并确保 gcd(e/t, p-1) = 1，从而可以在模 p 的乘法群里对 (e/t) 取逆。
• 第二个参数 p：对应的素数因子（或当前处理的模数），用于在该模数下求出候选解集合。脚本

脚本需要在sage下运行，如果报错，尝试Restart

类型五：多组加密+单素数互素

例题 [MoeCTF 2022]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

共享素数可以求到p,q,r

但是本题不同的是q-1和e不互素

我们可以分别求 mod p下的mp和mod r下的mr，然后进行CRT 恢复m，本质其实还是m比p,q,r都大，但是比p*r小

解码代码

from Crypto.Util.number import *
p= 11820891196647569262137841192985418014377132106496147254821784946481523526822939129065042819464351666077658751406165276121125571355594004514547517855730743
q= 10450390015864176713581330969519712299844487112687677452105216477861582967322473997670559995588440097951786576039009337782247912476227937589298529580432797
r= 9484954066160968219229920429258150817546418633451929876581842443665029377287119340232501682142185708534413073877473741393278935479791561681402673403009771
c1= 69574855207460025252857869494766338442370688922127811393280455950372371842144946699073877876005649281006116543528211809466226185922844601714337317797534664683681334132261584497953105754257846471069875622054326463757746293958069752489458646460121725019594141157667480846709081917530190233900184428943585065316
c2= 66183492015178047844987766781469734325646160179923242098082430373061510938987908656007752256556018402101435698352339429316390909525615464024332856855411414576031970267795270882896721069952171988506477519737923165566896609181813523905810373359029413963666924039857159685161563252396502381297700252749204993228
e=343284449
dp=pow(e,-1,p-1)
dr=pow(e,-1,r-1)
mp=pow(c1,dp,p)
mr=pow(c2,dr,r)
m=crt([int(mp),int(mr)],[p,r])
print(long_to_bytes(m))

类型六：p的多次

例题 [强网杯 2023]not only rsa

from Crypto.Util.number import bytes_to_long
from secret import flag
import os
​
n = 6249734963373034215610144758924910630356277447014258270888329547267471837899275103421406467763122499270790512099702898939814547982931674247240623063334781529511973585977522269522704997379194673181703247780179146749499072297334876619475914747479522310651303344623434565831770309615574478274456549054332451773452773119453059618433160299319070430295124113199473337940505806777950838270849
e = 641747
m = bytes_to_long(flag)
​
flag = flag + os.urandom(n.bit_length() // 8 - len(flag) - 1)
m = bytes_to_long(flag)
​
c = pow(m, e, n)
​
with open('out.txt', 'w') as f:
    print(f"{n = }", file=f)
    print(f"{e = }", file=f)
    print(f"{c = }", file=f)
    
n = 6249734963373034215610144758924910630356277447014258270888329547267471837899275103421406467763122499270790512099702898939814547982931674247240623063334781529511973585977522269522704997379194673181703247780179146749499072297334876619475914747479522310651303344623434565831770309615574478274456549054332451773452773119453059618433160299319070430295124113199473337940505806777950838270849
e = 641747
c = 730024611795626517480532940587152891926416120514706825368440230330259913837764632826884065065554839415540061752397144140563698277864414584568812699048873820551131185796851863064509294123861487954267708318027370912496252338232193619491860340395824180108335802813022066531232025997349683725357024257420090981323217296019482516072036780365510855555146547481407283231721904830868033930943

通过搜索大量的wp了解到了hensel定理

hensel定理

代码实现，chat写的，之后要是有更好用的会换

def hensel_lift_xe_c(a, e, c, p, k):
    """
    给定 a 满足 a^e ≡ c (mod p)，把解提升到 mod p^k
    适用于非退化情况：p ∤ (e*a^(e-1))，通常大素数p下都成立（a≠0 且 p∤e）
    """
    a = ZZ(a); e = ZZ(e); c = ZZ(c); p = ZZ(p); k = ZZ(k)
​
    # sanity check：a 是否真的是 mod p 的根
    if power_mod(a, e, p) != (c % p):
        raise ValueError("a 不是模 p 的根：a^e != c (mod p)")
​
    inv_d = inverse_mod((e * power_mod(a, e-1, p)) % p, p)  # (f'(a))^{-1} mod p
​
    mod = p  # p^m
    for m in range(1, k):
        mod_next = mod * p  # p^(m+1)
​
        # 只算到 p^(m+1) 的精度：f(a) = a^e - c (mod p^(m+1))
        fa_mod = (power_mod(a, e, mod_next) - (c % mod_next)) % mod_next
​
        # s = f(a)/p^m  (mod p)  => 先取到 mod_next 再整除 mod
        s = (fa_mod // mod) % p
​
        t = (-s * inv_d) % p
        a = a + t * mod     # 提升：a <- a + t*p^m
        mod = mod_next
​
        # 可选：更新导数逆元（严格来说导数在每层会变，但非退化时用模p的inv足够做一步提升）
        # 更稳妥的话，每层重新算 inv_d 也行：
        inv_d = inverse_mod((e * power_mod(a, e-1, p)) % p, p)
​
    return a

那么我们思路就有了，先用AMM求出mod p下的有限域开方，然后通过hensel进行解决

其实hensel本质上还是解决m比较大的问题

找到了偏hensel的文章：https://zhuanlan.zhihu.com/p/367203571

解码代码一

import random
import time
from tqdm import tqdm
from Crypto.Util.number import *
# About 3 seconds to run
def AMM(o, r, q):
    start = time.time()
    print('\n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            print('[+] Calculating DLP...')
            j = - discrete_log(d, a)
            print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c^r
    result = o^alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    print('Find one solution: {}'.format(result))
    return result
​
def onemod(p,r): 
    t=random.randint(2,p)
    while pow(t,(p-1)//r,p)==1: 
         t=random.randint(2,p)
    return pow(t,(p-1)//r,p) 
 
def solution(p,root,e):  
    while True:
        g=onemod(p,e) 
        may=[] 
        for i in tqdm(range(e)): 
            may.append(root*pow(g,i,p)%p)
        if len(may) == len(set(may)):
            return may
​
​
def solve_in_subset(ep,p):
    cp = int(pow(c,inverse(int(e//ep),p-1),p))
    com_factors = []
    while GCD(ep,p-1) !=1:
        com_factors.append(GCD(ep,p-1))
        ep //= GCD(ep,p-1)
    com_factors.sort()
​
    cps = [cp]
    for factor in com_factors:
        mps = []
        for cp in cps:
            mp = AMM(cp, factor, p)
            mps += solution(p,mp,factor)
        cps = mps
    for each in cps:
        assert pow(each,e,p)==c%p
    return cps
def hensel_lift_xe_c(a, e, c, p, k):
    """
    给定 a 满足 a^e ≡ c (mod p)，把解提升到 mod p^k
    适用于非退化情况：p ∤ (e*a^(e-1))，通常大素数p下都成立（a≠0 且 p∤e）
    """
    a = ZZ(a); e = ZZ(e); c = ZZ(c); p = ZZ(p); k = ZZ(k)
​
    # sanity check：a 是否真的是 mod p 的根
    if power_mod(a, e, p) != (c % p):
        raise ValueError("a 不是模 p 的根：a^e != c (mod p)")
​
    inv_d = inverse_mod((e * power_mod(a, e-1, p)) % p, p)  # (f'(a))^{-1} mod p
​
    mod = p  # p^m
    for m in range(1, k):
        mod_next = mod * p  # p^(m+1)
​
        # 只算到 p^(m+1) 的精度：f(a) = a^e - c (mod p^(m+1))
        fa_mod = (power_mod(a, e, mod_next) - (c % mod_next)) % mod_next
​
        # s = f(a)/p^m  (mod p)  => 先取到 mod_next 再整除 mod
        s = (fa_mod // mod) % p
​
        t = (-s * inv_d) % p
        a = a + t * mod     # 提升：a <- a + t*p^m
        mod = mod_next
​
        # 可选：更新导数逆元（严格来说导数在每层会变，但非退化时用模p的inv足够做一步提升）
        # 更稳妥的话，每层重新算 inv_d 也行：
        inv_d = inverse_mod((e * power_mod(a, e-1, p)) % p, p)
​
    return a
n = 6249734963373034215610144758924910630356277447014258270888329547267471837899275103421406467763122499270790512099702898939814547982931674247240623063334781529511973585977522269522704997379194673181703247780179146749499072297334876619475914747479522310651303344623434565831770309615574478274456549054332451773452773119453059618433160299319070430295124113199473337940505806777950838270849
e = 641747
c = 730024611795626517480532940587152891926416120514706825368440230330259913837764632826884065065554839415540061752397144140563698277864414584568812699048873820551131185796851863064509294123861487954267708318027370912496252338232193619491860340395824180108335802813022066531232025997349683725357024257420090981323217296019482516072036780365510855555146547481407283231721904830868033930943
p=91027438112295439314606669837102361953591324472804851543344131406676387779969
print(gcd(e,p-1))
m_p = solve_in_subset(e,p)
print(m_p[0])
for mpp in tqdm(m_p):
    m = hensel_lift_xe_c(int(mpp),e,c,p,5)
    flag=long_to_bytes(m)
    if b'flag' in flag:
        print(flag)
print('end')

sage好像有内置的hensel但是我没有找到

除此之外还有另一种解法

解码代码二

from Crypto.Util.number import *
​
p = 91027438112295439314606669837102361953591324472804851543344131406676387779969
n = 6249734963373034215610144758924910630356277447014258270888329547267471837899275103421406467763122499270790512099702898939814547982931674247240623063334781529511973585977522269522704997379194673181703247780179146749499072297334876619475914747479522310651303344623434565831770309615574478274456549054332451773452773119453059618433160299319070430295124113199473337940505806777950838270849
e = 641747
c = 730024611795626517480532940587152891926416120514706825368440230330259913837764632826884065065554839415540061752397144140563698277864414584568812699048873820551131185796851863064509294123861487954267708318027370912496252338232193619491860340395824180108335802813022066531232025997349683725357024257420090981323217296019482516072036780365510855555146547481407283231721904830868033930943
​
phi = p^4*(p-1)
res = Zmod(p^5)(c).nth_root(e, all=True)
for i in res:
    temp = long_to_bytes(int(i))
    if(b"flag" in temp):
        print(temp)
​
#flag{c19c3ec0-d489-4bbb-83fc-bc0419a6822a}

但是sage会跑很大的内存