ホーム

本文首发于跳跳糖社区（http://tttang.com/archive/1504/）

为什么说是针对 CTFer 的呢，本篇文章可能针对实用性强一点，针对算法的原理剖析会少一些。最后会总结出板子放在文章的结尾。

# 前言

在平常遇到的问题中，如果能求出公钥 n 的欧拉函数ϕ\phi，可以说这个 RSA 加解密问题已经接近成功了。要求私钥 d 需要求出 e 在 phi 中的逆元使得e∗d−1≡k∗ϕ(n)e*d-1 \equiv k*\phi(n)，但直接求逆元需要满足一个前提就是gcd(e,phi)==1gcd(e,phi)==1，也就是说 e 与 phi 是互素的，如果不互素，问题的复杂度将会增加不少。

相信在这个问题中，有一道 CTF 题是比较出名的，NCTF2019，附件如下

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

看似白给，但是这题的逆元 d 是求不出来的，因为 e 与 phi 不互素，gcd(e,p−1)==gcd(e,q−1)==gcd(e,phi)==egcd(e,p-1)==gcd(e,q-1)==gcd(e,phi)==e。该题的具体解法最后讨论，下面是我对 e 与 phi 不互素问题的一些小总结。

令t=gcd(e,phi)t=gcd(e,phi)

# ①mt<nm^{t}<n

这种情况可以把mtm^{t} 看成一个新的需要求的明文，这里以一道我自己之前摸鱼出的一道题目为例，附件如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from secret import flag
flag = b'flag{*********}'
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 114
c = pow(m,e,n)
print(c)
print(p >> 200)
print(n)

# 4981370648841772812759645290740849305394680703208798679296466901875830602835273402860232301263281323578956193947979697234640828088984992529165349436050379602381023059635247562226192384089521639938396211636613132291696135696985578958227320544060232615333466684704244997055833821133086665356126147182204658744167431612986909752009485714137028204041440181653812250548914729617593568901044728464293232061709058144788756823288190386071071979728390993033661221130338943191220680445314588574185565138844949934691183548291792150029676489045342419826189506616272247940278820931530398810621850374268800818970515221497093852109
# 62037304914409314363888940906845820031382619388386590204815535497699521033644001814874589864676342418539729790446530529473631795496696578029445470682035483391568820927435567100377626022924900710513454770616746573110984342344183967600234091673261776
# 10315159385090642346129000730749042701431892949303034712476198921384639021767097119992198421632142955005047146294210952031882321038272269972695714084199530336742619691272883151455898061330316812891004827724782855036289498818157782936179413509824274682055131552093071749522986951202502017564120645520386407170556413591537187759567563157956331577316042296031033014710853038209000676314440817362756989634719336973373719581572614119144998829076893422175956726616346716072744575347893245428145235967836165207095908913238287634122873060994828380614739915448587956681845973466847711337763120292734433687845920176310499582951

其中第一部分是一个 p 泄露高位的问题，老生常谈了，这里不过多赘述。求出 p 之后我们发现，e 与 phi 不互素且公约数t=gcd(e,phi)=6t=gcd(e,phi)=6，当时出题的 flag 值未设很长，故可进行尝试，数论推导如下：

e′=e//te'=e//t

d=gmpy2.invert(e′,phi)d=gmpy2.invert(e',phi)

用此公钥，即有如下关系

(mt)e′≡c(modn)(m^{t})^{e'} \equiv c \pmod n

mt≡cd(modn)m^{t} \equiv c^{d} \pmod n

其中mtm^{t} 可求且mt<nm^{t}<n，即直接对mtm^{t} 进行开tt 次方根即可。exp 如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
import gmpy2
c = 4981370648841772812759645290740849305394680703208798679296466901875830602835273402860232301263281323578956193947979697234640828088984992529165349436050379602381023059635247562226192384089521639938396211636613132291696135696985578958227320544060232615333466684704244997055833821133086665356126147182204658744167431612986909752009485714137028204041440181653812250548914729617593568901044728464293232061709058144788756823288190386071071979728390993033661221130338943191220680445314588574185565138844949934691183548291792150029676489045342419826189506616272247940278820931530398810621850374268800818970515221497093852109
e = 114
p = 99690105430259549732952386298363416480730988331578091065948950836198178325904426675017504756348563688521763268566954512895974110780822714951824351709232320913381679046309934991336770483285399157355308073567950907088479972767984569322594411195698421500521401221792581871025328456951904596576566123729811756413
n = 10315159385090642346129000730749042701431892949303034712476198921384639021767097119992198421632142955005047146294210952031882321038272269972695714084199530336742619691272883151455898061330316812891004827724782855036289498818157782936179413509824274682055131552093071749522986951202502017564120645520386407170556413591537187759567563157956331577316042296031033014710853038209000676314440817362756989634719336973373719581572614119144998829076893422175956726616346716072744575347893245428145235967836165207095908913238287634122873060994828380614739915448587956681845973466847711337763120292734433687845920176310499582951
q = 103472248730911851254553434648605804338564109979871343883653538836587422384404224866918549458325035655810767726029600292489262023711038658950506809510441640439838143226881684645307170720125749718552087605871880391263080540577543652043401824062555993901349884856226877853115632353980186588864859131611388824627
phi = (p - 1) * (q - 1)
t = gmpy2.gcd(e,phi)
print(t)
_e = e // t
d = gmpy2.invert(_e,phi)
_m = pow(c,d,n)
m = gmpy2.iroot(_m,t)[0]
print(long_to_bytes(m))

# ②mt>nm^{t}>n

这种情况需要结合中国剩余定理求解，由于mt>nm^{t}>n，就不能再单纯地用第一种方法，应该尝试在有限域内开根。以一道例题 (2022ctfshow 卷王杯现代密码签到) 为例，附件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import bytes_to_long
from secrets import p,q,r,s,t,flag

n = p * q * r * s * t
e = 2
m = bytes_to_long(os.urandom(500) + flag)
c = pow(m,e,n)

print(p,q,r,s,t,sep='\n')
print(c)

'''
145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263
116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763
157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531
100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679
93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447
9144597920381774885442906257311149465702295057238600973973598305004391534618770363098565074541384771979931799878381439264848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687497388018406214041657278323855749902661752448796122517061920880552011343608609622885787617238758769398972009949575526258430282648817039091284796330585349957724522615105102735930258969562103112238020133587096826386028128471852377225525357348919204333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312842687601478117040419013468059983777273699192408773551806581458197324620065210523913467414181480875280203580147077789063808832356486197271376615883221558265591069223727607585313240243619515521180600435114131162272519949101464089935441251751426683447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810158857859460406828090199683324760956105682902577189283246483314689365570862217407333103243336691401424548702387876409228977278498691200028282744239512091373110111792177228979867318546462714521296256938374618636206565791541769138267080789842400796973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299689325208882261918460708833888406187912527346628912894921059735420931656953236560178909180587372589456926690219114173193202048332172538564489660440225377822914097420807957784201785024166011709377791129
'''

这题的预期解应该是用 rabin 算法，一种针对指数为 2 的有限域开根算法。分析题目，flag 在 m 中，但是 flag 的前面添加了 500 个字节填充，这使得me>nm^{e}>n，且本题中t=et=e，可以在不同的环中对 c 开 e 次方，然后把得到的结果进行 CRT 组合，也就是说

xe≡c(modp)x^{e} \equiv c \pmod p x∈res1x \in res1

xe≡c(modq)x^{e} \equiv c \pmod q x∈res2x \in res2

xe≡c(modr)x^{e} \equiv c \pmod r x∈res3x \in res3

xe≡c(mods)x^{e} \equiv c \pmod s x∈res4x \in res4

xe≡c(modt)x^{e} \equiv c \pmod t x∈res5x \in res5

代码实现

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
from Crypto.Util.number import *
import gmpy2
import os
from functools import reduce

p = 145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263
q = 116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763
r = 157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531
s = 100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679
t = 93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447
c = 9144597920381774885442906257311149465702295057238600973973598305004391534618770363098565074541384771979931799878381439264848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687497388018406214041657278323855749902661752448796122517061920880552011343608609622885787617238758769398972009949575526258430282648817039091284796330585349957724522615105102735930258969562103112238020133587096826386028128471852377225525357348919204333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312842687601478117040419013468059983777273699192408773551806581458197324620065210523913467414181480875280203580147077789063808832356486197271376615883221558265591069223727607585313240243619515521180600435114131162272519949101464089935441251751426683447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810158857859460406828090199683324760956105682902577189283246483314689365570862217407333103243336691401424548702387876409228977278498691200028282744239512091373110111792177228979867318546462714521296256938374618636206565791541769138267080789842400796973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299689325208882261918460708833888406187912527346628912894921059735420931656953236560178909180587372589456926690219114173193202048332172538564489660440225377822914097420807957784201785024166011709377791129
n = p * q * r * s * t
e = 2
# print(n)
phi = (p - 1) * (q - 1) * (r - 1) * (s - 1) * (t - 1)
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()

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

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

R.<x> = Zmod(t)[]
f = x ^e - c
f = f.monic()
res5 = f.roots()
print(res1,res2,res3,res4,res5,sep='\n')

之后再进行 CRT 组合，其中满足题意的即为答案

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
#一个手写的CRT板子，sage中的CRT_list函数会快些
def union(x1, x2):
    a1, m1 = x1
    a2, m2 = x2
    d = gmpy2.gcd(m1, m2)
    assert (a2 - a1) % d == 0
    p1,p2 = m1 // d,m2 // d
    _,l1,l2 = gmpy2.gcdext(p1,p2)
    k = -((a1 - a2) // d) * l1
    lcm = gmpy2.lcm(m1,m2)
    ans = (a1 + k * m1) % lcm
    return ans,lcm


def excrt(ai,mi):
    tmp = zip(ai,mi)
    return reduce(union, tmp)
    
for i in res1:
    for j in res2:
        for k in res3:
            for l in res4:
                for m in res5:
                    ai = [i[0],j[0],k[0],l[0],m[0]]
                    # print(ai)
                    mi = [p,q,r,s,t]
                    flag = excrt(ai,mi)
                    flag = long_to_bytes(flag[0])
                    if b'ctfshow' in flag:
                        print(flag)

# ③AMM 算法 (Adleman-Manders-Miller cubic root extraction method)

如果谈论有限域开根问题，AMM 算法是绕不过的。AMM 算法在 RSA 中适用于指数 e 整除 phi 的情况，也就是说 phi % e == 0。其中有详细的论文，AMM 算法具体的作用就是在有限域中开出一个根。具体实现论文也明确地给出了

截图部分仅是 AMM 算法的实现过程，代码实现如下

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
from Crypto.Util.number import *
import gmpy2
import time
import random
from tqdm import tqdm
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

其中 AMM (o,r,q) 的返回值满足o≡resultr(modq)o \equiv result^{r} \pmod q，就是在有限域 q 中对 o 开 r 次根。还有一个比较方便的函数，但是没有具体研究过，作用也是在有限域内得到一个根。得到一个 x 满足xn≡a(modp)x^{n} \equiv a \pmod p

1
2
from sympy.ntheory.residue_ntheory import nthroot_mod
nthroot_mod(a,n,p)

先引入一个例题 (2022hws crypto_Elgamal)

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
from Crypto.Util.number import *
from key import FLAG

def keygen(size):
    q = getPrime(80)
    k = getPrime(944)   
    while True:
        p = q * k + 1
        if isPrime(p):
            break
        k += 1
    g = 2
    while True:
        if pow(g, q, p) == 1:
            break
        g += 1
    A = getRandomInteger(size) % q
    B = getRandomInteger(size) % q
    x = getRandomInteger(size) % q
    h = pow(g, x, p)
    return (g, h, A, B, p, q), (x)


def rand(A, B, q):
    global rand_state
    rand_state, ret = (A * rand_state + B) % q, rand_state
    return ret


def encrypt(pubkey, m):
    g, h, A, B, p, q = pubkey
    assert 0 < m <= p
    r = rand(A, B, q)
    c1 = pow(g, r, p)
    c2 = (m * pow(h, r, p)) % p
    return (c1, c2)

rand_state = getPrime(1024)
pubkey, privkey = keygen(1024)

m = bytes_to_long(FLAG)
c1, c2 = encrypt(pubkey, m)
c1_, c2_ = encrypt(pubkey, m)

print(c1, c2)
print(c1_, c2_)


s0 = 543263588863771657634119
s1 = 628899245716105951093835
s2 = 78708024695487418261582
s3 = 598971435111109998816796
s4 = 789474285039501272453373

assert ( A * s0 + B ) % q == s1
assert ( A * s1 + B ) % q == s2
assert ( A * s2 + B ) % q == s3
assert ( A * s3 + B ) % q == s4


p = 65211247300401312530078141569304950676358489059623557848188896752173856845051471066071652073612337629832155846984721797768267868868902023383604553319793550396610085424563231688918357710337401138108050205457200940158475922063279384491022916790549837379548978141370347556053597178221402425212594060342213485311
g = 27642593390439430783453736408814717946185190497201679721975757020767271070510268596627490205095779429964809833535285315202625851326460572368018875381603399143376574281200028337681552876140857556460885848491160812604549770668188783258592940823128376128198726254875984002214053523752696104568469730021811399216
h = 54585833166051670245656045196940486576634589000609010947618047461787934106392112227019662788387352615714332234871251868259282522817042504587428441746855906297390193418159792477477443129333707197013251839952389651332058368911829464978546505729530760951698134101053626585254469108630886768357270544236516534904


c1 = 60724920570148295800083597588524297283595971970237964464679084640302395172192639331196385150232229004030419122038089044697951208850497923486467859070476427472465291810423905736825272208842988090394035980454248119048131354993356125895595138979611664707727518852984351599604226889848831071126576874892808080133
c2 = 48616294792900599931167965577794374684760165574922600262773518630884983374432147726140430372696876107933565006549344582099592376234783044818320678499613925823621554608542446585829308488452057340023780821973913517239972817669309837103043456714481646128392677624092659929248296869048674230341175765084122344264
c1_ = 42875731538109170678735196002365281622531058597803022779529275736483962610547258618168523955709341579773947887175626960699426438456382655370090748369934296474999389316334717699127421889816721511602392591677377678759026657582648354688447456509292302633971842316239774410380221303269351351929586256938787054867
c2_ = 64829024929257668640929285124747107162970460545535885047576569803424908055130477684809317765011143527867645692710091307694839524199204611328374569742391489915929451079830143261799375621377093290249652912850024319433129432676683899459510155157108727860920017105870104383111111395351496171846620163716404148070

分析代码就是一个 lcg 算法 + Elgamal，这两个部分都不难做，得到数论关系之后最后有一个有限域开根问题。当时本人比赛的时候非预期出的，想着前面都分析推理出那么多东西了，最后求不出 e 是怀疑自己之前的 abq 求错了，后面还真给我用 lcg 的板子跑出了另一组 abq，完美地非预期绕过了最后的有限域开根的问题。

后面自己再回过头思考最后这个有限域开根问题，部分关键代码如下

1
2
3
4
5
e = 12742153496769814072596
p = 65211247300401312530078141569304950676358489059623557848188896752173856845051471066071652073612337629832155846984721797768267868868902023383604553319793550396610085424563231688918357710337401138108050205457200940158475922063279384491022916790549837379548978141370347556053597178221402425212594060342213485311
c = 45326527081735095684632585216508484943819720696878842043540554720229674414296707918873385105075387912310299691748216658256439485784388880803922134863731374059731970174794936075890019917038396488161530769759774808480182049272235808430693365496648819656078275683885130420969875204155207145247880895891885126527
phi = p - 1
assert pow(m,e,p) == c

私钥 d 无法通过直接求逆元求出，且公约数 t=7438，但这题有一个特殊点的地方为，当得到e′=e//te'=e // t 之后，得到的 e' 仍然不满足于 phi 互素，还有一个公约数 2，所以这题要先对 c 进行有限域内开二次方根，开完二次方根之后再将m7438m^{7438} 看作一个整体进行有限域内开根，即

设e=7438∗2∗e′e=7438*2*e'

(flage′∗7438)2≡c(modp)(flag^{e' * 7438})^{2} \equiv c \pmod p

flage′∗7438≡c′(modp)flag^{e'*7438} \equiv c' \pmod p

将flag7438flag^{7438} 看成一个整体进行 RSA 解密之后，得到

flag7438≡c′′(modp)flag^{7438} \equiv c'' \pmod p

问题转化成 c'' 在有限域 p 内开 7438 次根，但是 AMM 算法只能找到其中一个根，如何通过一个根找到其他的根，本篇文章给出了解法。用法大致如下，根据公式

(xp−1e)e≡xq−1≡1(x^{\frac{p-1}{e}})^{e} \equiv x^{q-1} \equiv 1

m0∗x(p−1e)(modp)m0*x^{(\frac{p-1}{e})} \pmod p 其中 m0 是求出来的一个根

1
2
3
4
5
6
7
8
9
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

上述代码的返回值就是xp−1ex^{\frac{p-1}{e}} 的合集，故最终求出本题的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
_gcd = gmpy2.gcd(e,phi)
#_gcd = 7438
e //= 2
_c = AMM(c,2,p)
d = gmpy2.invert(e // _gcd,phi)
_c = pow(_c,d,p)
# _m = AMM(_c,7438,p)
e = 7438
mps = findAllPRoot(p, e)
for r in mps:
    m = _m * r % p
    flag = long_to_bytes(m)
    if b'flag' in flag:
        print(flag)
        break

再引一个例题，2022SUSCTF large case

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 *
from secret import e,message

def pad(s):
    if len(s)<3*L:
        s+=bytes(3*L-len(s))
    return s

L=128
p = 127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q = 145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r = 165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
n = p * q * r

assert isPrime(GCD(e,p-1)) and isPrime(GCD(e,q-1)) and isPrime(GCD(e,r-1)) and e==GCD(e,p-1)*GCD(e,q-1)*GCD(e,r-1)
assert len(message)>L and len(message)<2*L
assert b'SUSCTF' in message
m=bytes_to_long(pad(message))

c=pow(m,e,n)
print(c)
'''
2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892
'''

仔细分析代码，发现 e 是 p-1,q-1,r-1 的一个因子积。所以思路很容易想到是用 yafu 或者是 factordb 先把他们给分解了，得到了

1
2
3
_p = [7,757,1709,85015583,339028665499,149105250954771885483776047,1642463892686572578602085475101104723805585678675707586553009837707279291648160744722745420570786735582631019452016654157586623543454908938807521637550223579103317696104438456966780396624343550451096013730928292041667133825444056448136643704677066463120079]
_q = [66553,81768440203,84405986771,38037107558208320033,16137718604846030589135490851713,14369576056311038198362075935199486201201115381094289671031774994452214307042971166730146897009438957078052300683916910041250723573953110349566216311685009675744215421971185909678546052934704709232060199286321405045769976194110037]
_r = [5156273,10012111,11607389,68872137169799749,9691125310820433463,193,503,8626099,23475306212762953,105542779117757989082125573006184239099114297326009052949090033290335389936473768853350493434701637229350628852969771464325532199330764558757048653132496329427393914440142892591943594757483633317785007973120414022644727591]

这里将过小的因子剔除了，因子不会太大，所以测出来e=757×66553×5156273e=757 \times 66553 \times 5156273。再分析题目，要求的明文 m 是被 pad 过，所以后 1/3 部分全是 0，可以根据数论变换给删去，得到

1
c = c * gmpy2.invert(pow(256,128 * e,n),n) % n

因为删去了 1/3，这里分别在 p 和 q 下开根，再 CRT 组合就好了。完整代码：

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
from Crypto.Util.number import *
import gmpy2
import time
import random
from tqdm import tqdm
p = 127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q = 145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r = 165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
n = p * q * r
c = 2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892
e = 757 * 66553 * 5156273
# c = c * gmpy2.invert(pow(256,128 * e,n),n) % n
c = 280255407228236757409815887816839305916013793019016233556655881177084422973195335022587512823438603244476043620827618294521590422727109511126415701233621433629240428867472167324658030697632936334280396757560948574122348115659399270054958107088934452614887088952896264179020173433953077103667481291070508539455758662089418673467059205006535938089060238423612896891987917999584958061136036905447992065531255981463313994015042735163816799075348821119889190340460982992279626227831798343223551589026122303723190113833517871336399306996954589023298254133748866058614684423538364147817066529477497132575245720700870565926266788795913995176704128093239281548107568333922105485755437756178962461996506944599470241130124718452661102076116228019710853593988020056387355430180299354138576803527595019867293888047502553256446787799726850487133374683211529254614387387388363258745961934823313987871646019723020739519484511573598334592780
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=p-2 
    while pow(t,(p-1) // r,p)==1: 
        t -= 1 
    return pow(t,(p-1) // r,p) 
 
def solution(p,root,e):  
    g = onemod(p,e) 
    may = set() 
    for i in range(e): 
        may.add(root * pow(g,i,p)%p) 
    return may

ep = 757
eq = 66553
er = 5156273
cp = pow(c,gmpy2.invert(eq*er,p-1),p)
cq = pow(c,gmpy2.invert(ep*er,q-1),q)
mp = AMM(cp,ep,p)
mq = AMM(cq,eq,q)
mps = solution(p,mp,ep)
mqs = solution(q,mq,eq)
for mpp in tqdm(mps):
    for mqq in mqs:
        ai = [int(mpp),int(mqq)]
        mi = [p,q]
        m = CRT_list(ai,mi)
        flag = long_to_bytes(m)
        if b'SUSCTF' in flag:
            print(flag)
            exit(0)

板子从 V 神 blog 里嫖的其中函数 onemod () 和 solution () 组合求出剩下的根并进行组合

1
2
3
4
5
6
7
8
9
10
11
12
def onemod(p,r): 
    t=p-2 
    while pow(t,(p-1) // r,p)==1: 
        t -= 1 
    return pow(t,(p-1) // r,p) 
 
def solution(p,root,e):#(质数环，AMM求出的一个根，需要开e次根)
    g = onemod(p,e) 
    may = set() 
    for i in range(e): 
        may.add(root * pow(g,i,p)%p) 
    return may

最终可以求解得到 flag

所以回到开头提到的 NCTF2019 的 AMM 问题，也大同小异，这里就不解释直接贴 exp 了。

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
from Crypto.Util.number import *
import gmpy2
import time
import random
from tqdm import tqdm
e = 0x1337
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
n = p * q
c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359

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=p-2 
    while pow(t,(p-1) // r,p)==1: 
        t -= 1 
    return pow(t,(p-1) // r,p) 
 
def solution(p,root,e):  
    g = onemod(p,e) 
    may = set() 
    for i in range(e): 
        may.add(root * pow(g,i,p)%p) 
    return may

def find_roots(c,e,p):
    mp = AMM(c,e,p)
    mps = solution(p,mp,e)
    return mps

cp = c % p
cq = c % q
# mp = AMM(cp,e,p)
# mq = AMM(cq,e,q)
mps = find_roots(c % p,e,p)
mqs = find_roots(c % q,e,q)
for mpp in tqdm(mps):
    for mqq in mqs:
        ai = [int(mpp),int(mqq)]
        mi = [p,q]
        m = CRT_list(ai,mi)
        flag = long_to_bytes(m)
        if b'NCTF' in flag:
            print(flag)
            exit(0)

# 总结

遇到 e 与 phi 不互素的问题，首先就考虑问题的复杂程度，从 e 的大小和 e 与 phi 的公约数大小入手。总结出了三个板子针对不同的情况。不过遇到实际的问题还需具体情况具体分析。

# ①e 较小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
import gmpy2
c = 
e = 
n = 
p = 
q = 
phi = (p - 1) * (q - 1)
t = gmpy2.gcd(e,phi)
print(t)
_e = e // t
d = gmpy2.invert(_e,phi)
_m = pow(c,d,n)
m = gmpy2.iroot(_m,t)[0]
print(long_to_bytes(m))

# ②e 不算大但需结合 CRT 求解

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
from Crypto.Util.number import *
import gmpy2
p = 
q = 
c = 
n = 
e = 
phi = (p - 1) * (q - 1)

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:
        ai = [int(i[0]),int(j[0])]
        mi = [p,q]
        flag = CRT_list(ai,mi)
        flag = long_to_bytes(flag)
        if b'flag' in flag:
        	print(flag)

# ③e 很大，AMM 算法

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
from Crypto.Util.number import *
import gmpy2
import time
import random
from tqdm import tqdm
e = 
p = 
q = 
n = p * q
c = 

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=p-2 
    while pow(t,(p-1) // r,p)==1: 
        t -= 1 
    return pow(t,(p-1) // r,p) 
 
def solution(p,root,e):  
    g = onemod(p,e) 
    may = set() 
    for i in range(e): 
        may.add(root * pow(g,i,p)%p) 
    return may

def find_roots(c,e,p):
    mp = AMM(c,e,p)
    mps = solution(p,mp,e)
    return mps

cp = c % p
cq = c % q
mp = AMM(cp,e,p)
mq = AMM(cq,e,q)
mps = solution(p,mp,e)
mqs = solution(q,mq,e)
for mpp in tqdm(mps):
    for mqq in mqs:
        ai = [int(mpp),int(mqq)]
        mi = [p,q]
        m = CRT_list(ai,mi)
        flag = long_to_bytes(m)
        if b'NCTF' in flag:
            print(flag)
            exit(0)