数学知识

Ⅰ.二次剩余

$$m^2 \equiv c \pmod{p}，记p=2^t \cdot {s}，由Euler准则：$$

$$对于二次剩余：x^{(p-1)/2} \equiv 1 \pmod p,即x^{2^{(t-1)} \cdot {s}} \equiv 1 \pmod p$$

$$对于二次非剩余：y^{(p-1)/2} \equiv -1 \pmod p,即y^{2^{(t-1)} \cdot {s}} \equiv -1 \pmod p$$

(1)当t=1时

$$x^s \equiv 1 \pmod p,两边同时乘x再开方得：x^{(s+1)/2} \equiv x^{1/2} \pmod p$$

$$将c代入：c^{(s+1)/2} \equiv c^{1/2} \pmod p$$

$$故m \equiv c^{1/2} \equiv c^{(s+1)/2} \pmod p$$

(2)当t>1时

$$若直接开方：x^{2^{t-2} \cdot {s}} \equiv 1或-1 \pmod p, -1时不满足$$

$$考虑给负根配一个二次非剩余y，x^{2^{t-2} \cdot {s}} \cdot y^{2^{t-1} \cdot {s} \cdot k}\equiv 1 \pmod p$$

$$对于k：若x^{2^{t-2} \cdot {s}} \equiv 1 \pmod p，则k=0；若x^{2^{t-2} \cdot {s}} \equiv -1 \pmod p，则k=1$$

$$不断开根使得x的幂次中不再有2:x^s \cdot y^{s(2k_1 + 2^2k_2 + \cdots + 2^{t-2}k_{t-2})} \equiv 1 \pmod{p}$$

$$两边同乘s再开根并将c代入：m \equiv c^{1/2} \equiv c^{(s+1)/2} \cdot y^{s(k_1 + 2k_2 + \cdots + 2^{t-3}k_{t-2})} \equiv 1 \pmod{p}$$

（3）多个解

对于二次剩余，模p下应有两个解m和p-m

Ⅱ.e次剩余

$$m^e \equiv c \pmod{p}，记p-1=e^t \cdot {s}，由Euler准则：$$

$$由费马小定理：x^{p-1} \equiv 1 \pmod p,则有(m^e)^{(p-1)/e} \equiv c^{(p-1)/e} \equiv 1 \pmod p$$

$$找到的满足ed \equiv 1 \pmod p,则c^{(p-1)/e} \equiv (c^s)^{e^{(t-1)}} \equiv 1 \pmod p$$

$$(c^{ed-1})^{e^{(t-1)}} \equiv (c^{ks})^{e^{(t-1)}} \equiv 1^k \equiv 1 \pmod p$$

(1)当t=1时

$$c^{ed-1} \equiv 1 \pmod p,则c^{ed} \equiv {c} \pmod p$$

$$故m \equiv c^{1/e} \equiv c^d \pmod p$$

(2)当t>1时

涉及到循环群，等学了再来补充

一、gcd(e,φ(n)较小

gcd(e，φ(n)=2

$$令g=gcd(e,\phi(n))=2,则e’=\frac{e}{2},c\equiv m^e \equiv (m^2)^{e’} \pmod n$$

$$又gcd(e’,\phi(n))=1,则可以求出d’\equiv (e’)^{-1} \pmod {\phi(n)}$$

$$即有：m’\equiv m^2 \pmod n$$

Rabin算法$$p、q\equiv -1\pmod 4$$

Ⅰ.$$若p、q \equiv -1 \pmod 4$$

$$由于x^2 \equiv a \pmod p,且a^{(p-1)/2} \equiv 1 \pmod p$$

$$那么x \equiv +-a^{(p+1)/4} \pmod p$$

$$记m_p \equiv c^{(p+1)/4} \pmod p,m_q \equiv c^{(q+1)/4} \pmod q$$

  • $$通扩展欧几里得算法计算出y_p和y_q:$$

$$y_pp+y_qq=1$$

$$解出四个可能值$$

$$\begin {cases} a=y_p\cdot p\cdot m_q+y_q\cdot q \cdot m_p \pmod n\ b=n-a\ c=y_p\cdot p\cdot m_q-y_q \cdot q \cdot m_p\pmod n\ d=n-c \end {cases} $$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from gmpy2 import *
p = 
q = 
e = 2
c = 
n = p*q
def rabin(c):
    mp = pow(c, (p + 1) // 4, p)
    mq = pow(c, (q + 1) // 4, q)
    yp = inverse(p,q)
    yq = inverse(q,p)
    a = (yp * p * mq + yq * q * mp) % n
    b = n - int(a)
    c = (yp * p * mq - yq * q * mp) % n
    d = n - int(c)
    aa = [a, b, c, d]
    for i in aa:
        print(i)
        print(long_to_bytes(i))
m = rabin()

一般的

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
from Crypto.Util.number import *
import sympy
import gmpy2
from sympy.ntheory.modular import crt
c =
e =
n =
p =
q =
phi = (p-1) * (q-1)
print(gmpy2.gcd(e,phi))
 
def find_quadratic_residues(a, p):
    #检查a是否为模p下的二次剩余
    if not sympy.is_quad_residue(a, p):
        return None  
    # 使用 sympy 的 nthroot_mod 找到一个解
    x = sympy.nthroot_mod(a, 2, p, all_roots=False)
    second_solution = p - x
    return (x, second_solution)
 
x1=find_quadratic_residues(c,p)      
x2=find_quadratic_residues(c,q)     
 
for i in x1:
    for j in x2:
        remainders = [i,j]
        mods = [p,q]
        m_ = crt(mods, remainders)[0]   # CRT合并得到模n的二次剩余解
        c_ = m_%n
 
        e_ = e//2
        d = inverse(e_,phi)
        m = pow(c_,d,n)
        print(long_to_bytes(m))

g较小,p较小

$$令e’=\frac {e}{g},e’d’\equiv 1 \pmod {\phi(n)}$$

$$t\equiv c^{d’}\equiv m^{ed’}\equiv m^{ge’d’}\equiv m^g \pmod n$$

在sagemath中，用nth_root开根：

  • $$若 g∣(p−1)g∣(p−1)，则根的个数为 g$$
  • $$若 g∤(p−1)g∤(p−1)，则根存在且唯一（但需验证t是否为g次剩余）$$
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 sage.all import *
from Crypto.Util.number import *
from sympy.ntheory.modular import crt
n = 
e = 
c =
p = 
q =
phi = (p-1)*(q-1)
g = gcd(e, phi)
e_prime = e // g
d_prime = inverse_mod(e_prime, phi)

t = pow(c, d_prime, n)
Rp = Zmod(p)
tp = Rp(t)
roots_p = tp.nth_root(g, all=True)   # 返回所有根（列表）

Rq = Zmod(q)
tq = Rq(t)
roots_q = tq.nth_root(g, all=True)
for rp in roots_p:
    for rq in roots_q:
        m = crt(int(rp), int(rq), p, q)
        if pow(m, e, n) == c:
            print(long_to_bytes(m))
            break

建立有限域

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
from Crypto.Util.number import *
from sympy.ntheory.modular import crt
import gmpy2
p=
q=
n=
c=
e=
phi=(p-1)*(q-1)
gcd=gmpy2.gcd(e,phi)
d=inverse(e//gcd,phi)

R.<x> = PolynomialRing(Zmod(p))
f = x^gcd - c
res1 = f.roots()
 
R.<x> = PolynomialRing(Zmod(q))
f = x^gcd - c
res2 = f.roots()

for i in res1:
    for j in res2:
        m = crt([p,q],[int(i),int(j)])
        if m is not None:
            try:
                print(long_to_bytes(int(pow(m[0],d,n))).decode())
            except Exception as e:
                continue

二、gcd较大

nth_root

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 sympy.ntheory.modular import crt
import gmpy2
p= 
q=
n=
c=
e=

phi = (p-1)*(q-1)
gcd =gmpy2.gcd(e,phi)
d =gmpy2.invert(e//gcd,phi)

res1 = Zmod(p)(c).nth_root(gcd, all=True)
res2 = Zmod(q)(c).nth_root(gcd, all=True)

for i in res1:
    for j in res2:
        m = crt([p,q],[int(i),int(j)])
        if m is not None:
            try:
                print(long_to_bytes(int(pow(m[0],d,n))).decode())
            except Exception as e:
                continue

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
import gmpy2
from Crypto.Util.number import *
from sympy.ntheory.modular import crt
import time
import random
from tqdm import tqdm
p=
e=
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(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

mp = AMM(c,e,p)
p_proot = findAllPRoot(p, e)
mps = findAllSolutions(mp, p_proot, c, p)

for i in mps:
        flag = long_to_bytes(int(i))
        if b'flag' in flag:
                print(flag)

三、例题

1、n由多个素数相乘

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)

'''
p=145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263
q=116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763
r=157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531
s=100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679
t=93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447
c=9144597920381774885442906257311149465702295057238600973973598305004391534618770363098565074541384771979931799878381439264848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687497388018406214041657278323855749902661752448796122517061920880552011343608609622885787617238758769398972009949575526258430282648817039091284796330585349957724522615105102735930258969562103112238020133587096826386028128471852377225525357348919204333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312842687601478117040419013468059983777273699192408773551806581458197324620065210523913467414181480875280203580147077789063808832356486197271376615883221558265591069223727607585313240243619515521180600435114131162272519949101464089935441251751426683447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810158857859460406828090199683324760956105682902577189283246483314689365570862217407333103243336691401424548702387876409228977278498691200028282744239512091373110111792177228979867318546462714521296256938374618636206565791541769138267080789842400796973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299689325208882261918460708833888406187912527346628912894921059735420931656953236560178909180587372589456926690219114173193202048332172538564489660440225377822914097420807957784201785024166011709377791129
'''

$$已知：m^2 \equiv c \pmod n，拆解为：$$

$$\begin {cases} m^2 \equiv c \pmod p\ m^2 \equiv c \pmod q\ m^2 \equiv c \pmod r\ m^2 \equiv c \pmod s\ m^2 \equiv c \pmod t \end {cases}$$

$$分别求出对应的m’,再进行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
from Crypto.Util.number import bytes_to_long
from sympy.ntheory.modular import crt
import gmpy2
p=145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263
q=116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763
r=157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531
s=100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679
t=93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447
c=9144597920381774885442906257311149465702295057238600973973598305004391534618770363098565074541384771979931799878381439264848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687497388018406214041657278323855749902661752448796122517061920880552011343608609622885787617238758769398972009949575526258430282648817039091284796330585349957724522615105102735930258969562103112238020133587096826386028128471852377225525357348919204333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312842687601478117040419013468059983777273699192408773551806581458197324620065210523913467414181480875280203580147077789063808832356486197271376615883221558265591069223727607585313240243619515521180600435114131162272519949101464089935441251751426683447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810158857859460406828090199683324760956105682902577189283246483314689365570862217407333103243336691401424548702387876409228977278498691200028282744239512091373110111792177228979867318546462714521296256938374618636206565791541769138267080789842400796973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299689325208882261918460708833888406187912527346628912894921059735420931656953236560178909180587372589456926690219114173193202048332172538564489660440225377822914097420807957784201785024166011709377791129
e=2
phi=(p-1)*(q-1)*(r-1)*(s-1)*(t-1)

PR.<x>=PolynomialRing(Zmod(p))
f=x^e-c
f=f.monic()
res1=f.roots()

PR.<x>=PolynomialRing(Zmod(q))
f=x^e-c
f=f.monic()
res2=f.roots()

PR.<x>=PolynomialRing(Zmod(r))
f=x^e-c
f=f.monic()
res3=f.roots()

PR.<x>=PolynomialRing(Zmod(s))
f=x^e-c
f=f.monic()
res4=f.roots()

PR.<x>=PolynomialRing(Zmod(t))
f=x^e-c
f=f.monic()
res5=f.roots()

for i in res1:
    for j in res2:
        for k in res3:
            for l in res4:
                for m in res5:
                    m_list=[int(i[0]),int(j[0]),int(k[0]),int(l[0]),int(m[0])]
                    a_list=[p,q,r,s,t]
                    solve=CRT_list(m_list,a_list)
                    flag=long_to_bytes(solve)
                    if b'ctf' in flag:
                        print(flag)

2、e|p-1

1
2
3
4
5
e = 1801
c = pow(m,e,p)

c =821562155714228494350968286343241874202753771452745916900616612053610190986294297934462409534126095213198464996196364868528238538372119009517541428785632007137206972918081643841690069171088425923887930051635578719252415693144672179185417101210954906623326286804995637775062840407550493095027500638719998 
p =19897846550210846565807788524492364050901480736489979129040638436463635149815428186161001280958415730930156556581274966745574164608778242980049611665461488306439665507971670397595035647317930606555771720849158745264269952668944940061576328219674721623208805067371087817766416300084129945316973502412996143

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

e = 1801
c = 821562155714228494350968286343241874202753771452745916900616612053610190986294297934462409534126095213198464996196364868528238538372119009517541428785632007137206972918081643841690069171088425923887930051635578719252415693144672179185417101210954906623326286804995637775062840407550493095027500638719998
p = 19897846550210846565807788524492364050901480736489979129040638436463635149815428186161001280958415730930156556581274966745574164608778242980049611665461488306439665507971670397595035647317930606555771720849158745264269952668944940061576328219674721623208805067371087817766416300084129945316973502412996143

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(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

mp = AMM(c,e,p)
p_proot = findAllPRoot(p, e)
mps = findAllSolutions(mp, p_proot, c, p)

for i in mps:
        flag = long_to_bytes(int(i))
        if b'flag' in flag:
                print(flag)
# flag{Enj01_m1sc_A0d_cr0}

法二e阶子群

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *

e = 1801
c = 821562155714228494350968286343241874202753771452745916900616612053610190986294297934462409534126095213198464996196364868528238538372119009517541428785632007137206972918081643841690069171088425923887930051635578719252415693144672179185417101210954906623326286804995637775062840407550493095027500638719998
p = 19897846550210846565807788524492364050901480736489979129040638436463635149815428186161001280958415730930156556581274966745574164608778242980049611665461488306439665507971670397595035647317930606555771720849158745264269952668944940061576328219674721623208805067371087817766416300084129945316973502412996143

g = pow(2,(p-1) // e,p)
d0 = inverse(e,(p - 1) // e)
m0 = pow(c,d0,p)

for i in range(e):
    m = m0 * pow(g,i,p) % p
    flag = long_to_bytes(m)
    if b"flag" in flag:
        print(flag)

$$记k=\frac{p-1}{e},则x^e \equiv c在\mathbb F_p中有解当且仅当:$$

$$c是模p的e次剩余即c^k \equiv 1\ pmod p$$

$$设H={x \in \mathbb F_p^* |x^e \equiv 1},即\mathbb F_p^*的e阶子群$$

$$若m_0是方程的一个特解，则所有的解为：$$

$$m=m_0*h(h \in H）$$

$$在\mathbb F_p^*中，任意元素的阶一定整除p-1$$

  1. 构造e阶子群生成元

$$记p-1=ek,取g=2^k,2的阶为d$$

$$则g的阶为\frac{d}{gcd(d,k)}$$

$$特别地，若2是原根（即d=p-1），则g的阶为\frac{p-1}{gcd(p-1,k)}=\frac{ek}{k}=e$$

  1. 求特解

$$令d_0=e^{-1}\pmod k,m_0 \equiv c^{d_0} \pmod p$$

$$则m_0^e \equiv c^{ed_0}\equiv c^{1+tk} \equiv c \pmod p$$

$$这个m_0就是方程的一个特解$$

  1. 生成所有解

$$由于g是e阶元，{g^i |i=0,1,…,e-1}是e次单位根集合H$$

$$m=m_0*h(h \in H$$​

四、总结

$$在gcd较小时,用多项式x^g-c求解更快$$

$$在gcd较大时，用nth_root或AMM$$

参考

RSA部分题型收集

RSA 加密及一些攻击方式 - SeanDictionary | 折腾日记

TGCTF

感谢