Mamor's Blog
0%

RSA中e与phi不互素问题

发表于 更新于 分类于
本文字数： 21k 阅读时长 ≈ 19 分钟

RSA中 e phi不互素问题

在一般的RSA题目中，通过得到phi后求出e在phi在的逆元进而私钥d， 随后可以进一步得到明文m。但是求逆元需要满足一个前提 gcd(e,phi) == 1 ，需要e与phi互素，如果e和phi不互素则需要其他方法。本文将简单总结下在RSA中e与phi不互素的情况。

【密码学小白，缺少较多的数学基础，所以有些地方看不懂只好先套轮子Orz，后续慢慢补，大佬莫怪】

类型一 e仅与p-1或q-1互素

2022MoeCTF Signin

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from secret import flag
m=bytes_to_long(flag)
p=getPrime(512)
q=getPrime(512)
print('p=',p)
print('q=',q)
n=p*q
e=65537
c=pow(m,e,n)
print('c=',c)
#p= 12408795636519868275579286477747181009018504169827579387457997229774738126230652970860811085539129972962189443268046963335610845404214331426857155412988073
#q= 12190036856294802286447270376342375357864587534233715766210874702670724440751066267168907565322961270655972226761426182258587581206888580394726683112820379
#c= 68960610962019321576894097705679955071402844421318149418040507036722717269530195000135979777852568744281930839319120003106023209276898286482202725287026853925179071583797231099755287410760748104635674307266042492611618076506037004587354018148812584502385622631122387857218023049204722123597067641896169655595

题目分析

题中phi%e == 0，gcd(e,phi)=65535【也可以使用AMM算法解决此题，具体见下文】

phi与p-1互素 gcd(e,p-1)=1，那么可以将原本的phi 转换成 p-1进行求解。

如果 gcd(e,phi)=1，根据欧拉定理则有 e^d ≡ 1 mod phi e^d=1+kphi = 1+k(p-1)(q-1)；m ≡ c^d mod (p*q)

现在 gcd(e,p-1)=1，则有 e^d ≡ 1 mod (p-1)；m ≡ c^d mod p

那么对应有 m = pow(c,d,n)，也就变成 m = pow(c,d,p)

WP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import long_to_bytes
import gmpy2

e= 65537
p= 12408795636519868275579286477747181009018504169827579387457997229774738126230652970860811085539129972962189443268046963335610845404214331426857155412988073
q= 12190036856294802286447270376342375357864587534233715766210874702670724440751066267168907565322961270655972226761426182258587581206888580394726683112820379
c= 68960610962019321576894097705679955071402844421318149418040507036722717269530195000135979777852568744281930839319120003106023209276898286482202725287026853925179071583797231099755287410760748104635674307266042492611618076506037004587354018148812584502385622631122387857218023049204722123597067641896169655595

phi = (p-1)*(q-1)

# print(gmpy2.gcd(e,phi))
# print(gmpy2.gcd(e,p-1))
# print(gmpy2.gcd(e,q-1))

phi = p-1
d = gmpy2.invert(e,phi)
m = pow(c,d,p)
print(long_to_bytes(m))
# b'moectf{Oh~Now_Y0u_Kn0W_HoW_RsA_W0rkS!}'

2023MoeCTF bad_E

和2022的一样的题 将模从phi转换为 p或q进行求解

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
p = getPrime(512)
q = getPrime(512)
e = 65537

print(p) # 6853495238262155391975011057929314523706159020478084061020122347902601182448091015650787022962180599741651597328364289413042032923330906135304995252477571
print(q) # 11727544912613560398705401423145382428897876620077115390278679983274961030035884083100580422155496261311510530671232666801444557695190734596546855494472819

with open("flag.txt","r") as fs:
    flag = fs.read().strip()

m = bytes_to_long(flag.encode())
c = pow(m,e,p*q)
print(c) # 63388263723813143290256836284084914544524440253054612802424934400854921660916379284754467427040180660945667733359330988361620691457570947823206385692232584893511398038141442606303536260023122774682805630913037113541880875125504376791939861734613177272270414287306054553288162010873808058776206524782351475805

wp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import gmpy2
from Crypto.Util.number import long_to_bytes

e = 65537

p = 6853495238262155391975011057929314523706159020478084061020122347902601182448091015650787022962180599741651597328364289413042032923330906135304995252477571
q = 11727544912613560398705401423145382428897876620077115390278679983274961030035884083100580422155496261311510530671232666801444557695190734596546855494472819
c = 63388263723813143290256836284084914544524440253054612802424934400854921660916379284754467427040180660945667733359330988361620691457570947823206385692232584893511398038141442606303536260023122774682805630913037113541880875125504376791939861734613177272270414287306054553288162010873808058776206524782351475805

print(gmpy2.gcd(e,(p-1)*(q-1)))
print(gmpy2.gcd(e,p-1))

print(gmpy2.gcd(e,q-1))
#  gcd(e,q-1) = 1

phi = q-1
d = gmpy2.invert(e,phi)
m = pow(c,d,q)
print(long_to_bytes(m))
# b'moectf{N0w_Y0U_hAve_kN0w_h0w_rsA_w0rks!_f!lP0iYlJf!M3ru}'

[黑盾杯 2020]Factor

题目描述

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

题目分析

yafu分解n可以得到 p q r 3个素数

gcd(e,p-1)=3 较小 可将phi=pqr转换为 phi=qr 进行求解，对应的m=pow(c,d,n)也就转变为pow(c,d,qr)

WP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import gmpy2
from Crypto.Util.number import long_to_bytes

n = 3454083680130687060405946528826790951695785465926614724373
e = 3
c = 1347530713288996422676156069761604101177635382955634367208
# yafu 分解n
p = 17100682436035561357
q = 17172929050033177661
r = 11761833764528579549

phi_n = (p-1)*(q-1)*(r-1)
# print(gmpy2.gcd(e,p-1))
# 3

phi = (q-1)*(r-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,q*r)
print(long_to_bytes(m))

# b'CMISCCTF{3_RSA}'

类型二 gcd(e,phi)较小 iroot开根

gcd2 = gcd(e,phi) 较小 可通过iroot开根 e//gcd2 次根

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
 
flag = b'NSSCTF{******}'
 
p = getPrime(512)
q = getPrime(512)
 
e = 65537*2
n = p*q 
m = bytes_to_long(flag)
c = pow(m, e, n)
 
print(f'p = {p}')
print(f'q = {q}')
print(f'e = {e}')
print(f'c = {c}')
 
'''
p = 9927950299160071928293508814174740578824022211226572614475267385787727188317224760986347883270504573953862618573051241506246884352854313099453586586022059
q = 9606476151905841036013578452822151891782938033700390347379468858357928877640534612459734825681004415976431665670102068256547092636766287603818164456689343
e = 131074
c = 68145285629092005589126591120307889109483909395989426479108244531402455690717006058397784318664114589567149811644664654952286387794458474073250495807456996723468838094551501146672038892183058042546944692051403972876692350946611736455784779361761930869993818138259781995078436790236277196516800834433299672560
'''

题目分析

t = gcd(e,phi)=gcd(e,p-1)=gcd(e,p-1)=2

e‘ = e // t

d = gmpy2.invert(e',phi)

(mt)e' ≡ c (mod n)

m^t ≡ c^d (mod n)

然后开t次方跟即可求出m

WP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import long_to_bytes
import gmpy2

p = 9927950299160071928293508814174740578824022211226572614475267385787727188317224760986347883270504573953862618573051241506246884352854313099453586586022059
q = 9606476151905841036013578452822151891782938033700390347379468858357928877640534612459734825681004415976431665670102068256547092636766287603818164456689343
e = 131074
c = 68145285629092005589126591120307889109483909395989426479108244531402455690717006058397784318664114589567149811644664654952286387794458474073250495807456996723468838094551501146672038892183058042546944692051403972876692350946611736455784779361761930869993818138259781995078436790236277196516800834433299672560
n = p*q
print(gmpy2.gcd(e,(p-1)*(q-1)))
print(gmpy2.gcd(e,p-1))
print(gmpy2.gcd(e,q-1))

t = gmpy2.gcd(e,(p-1)*(q-1))
d = gmpy2.invert(e//t, (p-1)*(q-1))
m_gcd = pow(c,d,n)
m = gmpy2.iroot(m_gcd,t)

if m:
    print(long_to_bytes(m[0]))
# b'NSSCTF{inverse_and_root}'

类型三 gcd(e,phi)较小 iroot开不出根 ，有限域内开根

gcd(e,phi)较小 但iroot开根跑不出来 ,可考虑结合CRT求解进行有限域内开根

题目1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from flag import flag
import gmpy2
assert(len(flag)==38)
flag = bytes_to_long(flag)

p = getPrime(512)
q = getPrime(512)

e = 304
enc = pow(flag,e,p*q)
print(p)
print(q)
print(enc)
#9794998439882070838464987778400633526071369507639213778760131552998185895297188941828281554258704149333679257014558677504899624597863467726403690826271979
#10684338300287479543408040458978465940026825189952497034380241358187629934633982402116457227553161613428839906159238238486780629366907463456434647021345729
#88310577537712396844221012233266891147970635383301697208951868705047581001657402229066444746440502616020663700100248617117426072580419555633169418185262898647471677640199331807653373089977785816106098591077542771088672088382667974425747852317932746201547664979549641193108900510265622890793400796486146522028


题目分析

gcd(e,q-1)=16 gcd(e,p-1)=2

m 38位，对应608个十六进制字符 304bit，而 p、q是512bit，m<p、m<q。

gcd(e,q-1)=16 ，(m16)((q-1)/16) ≡ c mod q

求(q-1)/16的逆元，c^d' ≡ m^16 mod q

但是这里的 m^16直接开不出根，需要结合CRT用有限域内开根解决。

可以用下面这个模版，根据n分解素数的个数 适当添加缩减即可。

WP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

from Crypto.Util.number import *

p = 9794998439882070838464987778400633526071369507639213778760131552998185895297188941828281554258704149333679257014558677504899624597863467726403690826271979
q = 10684338300287479543408040458978465940026825189952497034380241358187629934633982402116457227553161613428839906159238238486780629366907463456434647021345729
c = 88310577537712396844221012233266891147970635383301697208951868705047581001657402229066444746440502616020663700100248617117426072580419555633169418185262898647471677640199331807653373089977785816106098591077542771088672088382667974425747852317932746201547664979549641193108900510265622890793400796486146522028
e = 304
n = p*q

R.<x> = Zmod(p)[]
f = x ^ e - c
f = f.monic()
res1 = f.roots()

R.<x> = Zmod(q)[]
f = x ^e - c
f = f.monic()
res2 = f.roots()

for i in res1:
    for j in res2:
        m = crt(int(i[0]),int(j[0]),p,q)
        flag = long_to_bytes(m)
        if b'flag' in flag:
            print(flag)

# b'flag{947b6543117e32730a93d1b43c98bc57}'


unusualrsa5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# ********************
# @Author: Lazzaro
# ********************
 
from Crypto.Util.number import bytes_to_long
from secret import flag
 
e = 0x14
p = 733089589724903586073820965792963746076789390539824437962807679954808310072656817423828613938510684864567664345751164944269489647964227519307980688068059059377123391499328155025962198363435968318689113750910755244276996554328840879221120846257832190569086861774466785101694608744384540722995426474322431441
q = 771182695213910447650732428220054698293987458796864628535794956332865106301119308051373568460701145677164052375651484670636989109023957702790185901445649197004100341656188532246838220216919835415376078688888076677350412398198442910825884505318258393640994788407100699355386681624118606588957344077387058721
n = p*q
 
m = bytes_to_long(flag)
c = pow(m,e,n)
print(c)
 
 
#406314720119562590605554101860453913891646775958515375190169046313074168423687276987576196367702523895650602252851191274766072774312855212771035294337840170341052016067631007495713764510925931612800335613551752201920460877432379214684677593342046715833439574705829048358675771542989832566579493199671622475225225451781214904100440695928239014046619329247750637911015313431804069312072581674845078940868349474663382442540424342613429896445329365750444298236684237769335405534090013035238333534521759502103604033307768304224154383880727399879024077733935062478113298538634071453067782212909271392163928445051705642

题目分析

t=gcd(e,p-1)=gcd(e,q-1)=20

直接套脚本

WP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# sage
from Crypto.Util.number import *

e = 0x14
p = 733089589724903586073820965792963746076789390539824437962807679954808310072656817423828613938510684864567664345751164944269489647964227519307980688068059059377123391499328155025962198363435968318689113750910755244276996554328840879221120846257832190569086861774466785101694608744384540722995426474322431441
q = 771182695213910447650732428220054698293987458796864628535794956332865106301119308051373568460701145677164052375651484670636989109023957702790185901445649197004100341656188532246838220216919835415376078688888076677350412398198442910825884505318258393640994788407100699355386681624118606588957344077387058721
n = p*q
c = 406314720119562590605554101860453913891646775958515375190169046313074168423687276987576196367702523895650602252851191274766072774312855212771035294337840170341052016067631007495713764510925931612800335613551752201920460877432379214684677593342046715833439574705829048358675771542989832566579493199671622475225225451781214904100440695928239014046619329247750637911015313431804069312072581674845078940868349474663382442540424342613429896445329365750444298236684237769335405534090013035238333534521759502103604033307768304224154383880727399879024077733935062478113298538634071453067782212909271392163928445051705642

R.<x> = Zmod(p)[]
f = x ^ e - c
f = f.monic()
res1 = f.roots()

R.<x> = Zmod(q)[]
f = x ^e - c
f = f.monic()
res2 = f.roots()

for i in res1:
    for j in res2:
        m = crt(int(i[0]),int(j[0]),p,q)
        flag = long_to_bytes(m)
        if b'flag' in flag:
            print(flag)

# b'flag{r54__d34l1n6_w17h_3v3n_3 _&_f1nd1n6_n-7h_r0075~~}'

类型四 gcd(e,phi)很大 AMM

AMM算法

AMM算法在RSA中适用于 phi % e == 0的情况【e | phi_n】有限域上的高次开根

AMM算法作用就是在有限域中开出一个根。

这块暂时不搞了。算法看不懂 直接找轮子。。。【想去了解可参考https://www.anquanke.com/post/id/262634#h2-5】

[NCTF2019]easyRSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

(p-1)%e=0 (q-1)%e=0

p-1 q-1均是e的倍数【即 e|p-1，e|q-1】对c开e次方根，考虑AMM算法开根号求解

WP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
import random
import time
 
# 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 = - dicreat_log(a, d)
            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 findAllPRoot(p, e):
    print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
    start = time.time()
    proot = set()
    while len(proot) < e:
        proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return proot
 
def findAllSolutions(mp, proot, cp, p):
    print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
    start = time.time()
    all_mp = set()
    for root in proot:
        mp2 = mp * root % p
        assert(pow(mp2, e, p) == cp)
        all_mp.add(mp2)
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return all_mp
 
 
c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
e = 0x1337
cp = c % p
cq = c % q
mp = AMM(cp, e, p)
mq = AMM(cq, e, q)
p_proot = findAllPRoot(p, e)
q_proot = findAllPRoot(q, e)
mps = findAllSolutions(mp, p_proot, cp, p)
mqs = findAllSolutions(mq, q_proot, cq, q)
print mps, mqs
 
def check(m):
    h = m.hex()
    if len(h) & 1:
        return False
    if h.decode('hex').startswith('NCTF'):
        print(h.decode('hex'))
        return True
    else:
        return False
 
 
# About 16 mins to run 0x1337^2 == 24196561 times CRT
start = time.time()
print('Start CRT...')
for mpp in mps:
    for mqq in mqs:
        solution = CRT_list([int(mpp), int(mqq)], [p, q])
        if check(solution):
            print(solution)
    print(time.time() - start)
 
end = time.time()
print("Finished in {} seconds.".format(end - start))

2022MoeCTF Signin

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
from secret import flag
m=bytes_to_long(flag)
p=getPrime(512)
q=getPrime(512)
print('p=',p)
print('q=',q)
n=p*q
e=65537
c=pow(m,e,n)
print('c=',c)
#p= 12408795636519868275579286477747181009018504169827579387457997229774738126230652970860811085539129972962189443268046963335610845404214331426857155412988073
#q= 12190036856294802286447270376342375357864587534233715766210874702670724440751066267168907565322961270655972226761426182258587581206888580394726683112820379
#c= 68960610962019321576894097705679955071402844421318149418040507036722717269530195000135979777852568744281930839319120003106023209276898286482202725287026853925179071583797231099755287410760748104635674307266042492611618076506037004587354018148812584502385622631122387857218023049204722123597067641896169655595

WP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
# sage
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

e = 65537
p= 12408795636519868275579286477747181009018504169827579387457997229774738126230652970860811085539129972962189443268046963335610845404214331426857155412988073
q= 12190036856294802286447270376342375357864587534233715766210874702670724440751066267168907565322961270655972226761426182258587581206888580394726683112820379
c= 68960610962019321576894097705679955071402844421318149418040507036722717269530195000135979777852568744281930839319120003106023209276898286482202725287026853925179071583797231099755287410760748104635674307266042492611618076506037004587354018148812584502385622631122387857218023049204722123597067641896169655595
n = p*q

m_p = solve_in_subset(1,p)
m_q = solve_in_subset(e,q)

for mpp in m_p:
    for mqq in m_q: 
        m = crt([int(mpp),int(mqq)],[p,q])
        flag = long_to_bytes(m)
        if b'ctf' in flag:
            print(flag)
            break 

# moectf{Oh~Now_Y0u_Kn0W_HoW_RsA_W0rkS!}

小结

在RSA中 e与phi不互素情况下，可简要概括为如下：

如果 gcd(e,phi) 较小时，可以考虑 iroot开根，开不出跟可考虑有限域内开跟；

如果 gcd(e,phi) 较大时，考虑AMM算法。

References

https://blog.csdn.net/m0_74345946/article/details/133936371

https://tttang.com/archive/1504/

https://forum.butian.net/share/1689

https://xz.aliyun.com/t/13917

欢迎关注我的其它发布渠道

------------- 💖 🌞 本 文 结 束 😚 感 谢 您 的 阅 读 🌞 💖 -------------