• 本篇文章主要讲讲基础的RSA中一些重要数据泄露之后如何对n进行分解（主要讨论的是正常RSA加密，也就是模数是两个素数相乘的RSA加密）
  • 本篇文章主要讲解的是如下两个部分：

image-20260205170010381

已知phi分解n

已知phi分解n 原理

  • 对于两个素数的RSA加密来说，已知ϕ(n)\phi(n)的条件下分解nn是很容易的，其实就相当于解方程，接下来就简单描述一下：
    • 首先已知ϕ(n)=(p−1)∗(q−1)\phi(n)=(p-1)*(q-1)，还已知n=p∗qn=p*q
    • 此时就可以将q=npq=\frac{n}{p}带入到ϕ(n)=(p−1)∗(q−1)\phi(n)=(p-1)*(q-1)中
    • 带入后得到的式子为：ϕ(n)=(p−1)∗(np−1)\phi(n)=(p-1)*(\frac{n}{p}-1)
    • 展开化简就可以得到ϕ(n)=n−p−np+1\phi(n)=n-p-\frac{n}{p}+1
    • 最终得到一个元二次方程：p2+(ϕ(n)−n−1)p+n=0p^{2}+(\phi(n)-n-1)p+n=0，解这个方程就行了

已知phi分解n 脚本

  • python解方程如下：
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
import math
def solve_2_th_root(a,b,c):
    """
    解一元二次方程: ax^2 + bx + c = 0
    :param a 二次项系数a
    :param b 一次项系数b
    :param c 常数项c
    :return: (x1,x2) x1,x2都是取整后的结果
    """
    delta = b**2 - 4*a*c
    if delta < 0:
        print("方程无实数解")
        return None

    elif delta == 0:
        x = (-1*b)//2*a
        return (x,x)

    elif delta > 0:
        sqrt_delta = math.isqrt(delta)
        x1 = int((-1*b + sqrt_delta)//2*a)
        x2 = int((-1*b - sqrt_delta)//2*a)
        return (x1,x2)

def know_phi_factor(n,phi):
    """
    已知phi分解n,仅限两个素数,n=pq
    参数n: 传入的是已知的n
    参数phi: 传入的是已知的phi
    :return: (p,q)
    """
    a = 1
    b = phi - n -1
    c = n
    p,q = solve_2_th_root(a,b,c)

    if p*q == n:
        print("正确分解出来p,q")
        return (p,q)
    else:
        print("分解不正确")
        return False


  • sagemath解方程如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def know_phi_factor(n,phi):
    """
    已知phi分解n,仅限两个素数,n=pq
    参数n: 传入的是已知的n
    参数phi: 传入的是已知的phi
    返回值: (p,q)
    """
    p,q = var('p,q')
    eq1 = p*q == n
    eq2 = p^2 + (phi-n-1)*p+n == 0
    result = solve([eq1,eq2],p,q)
    p = int(result[0][0].rhs())
    q = int(result[0][1].rhs())
    if p*q == n:
        print("正确分解出来p,q")
        return (p,q)
    else:
        print("分解不正确")
        return False
n = 
phi = 
p,q = know_phi_factor(n,phi)
print(p,q)

已知ed分解n

已知ed分解n 原理

  • 对于两个素数的RSA加密来说，已知dd分解nn算是比较简单的一部分，接下来推导一下，首先要明确一点已知dd的情况，一般都是要使用上密钥等式的，也就是ed=1+kλ(n)ed=1+k\lambda(n)这个等式，这里我们先讨论ed=1+kϕ(n)ed=1+k\phi(n)这个形式。

    • 下面这个推导是错误的思路
    • 设(n,e)(n,e)是一个有效的RSA加密公钥对，对应的私钥对为(d,p,q)(d,p,q)。
    • 我们已知e,d,ne,d,n，接下来需要对nn进行分解，从而完全破解出RSA加密的私钥对。
    • 首先我们考虑密钥等式：ed=1+kϕ(n)=1+k(p−1)(q−1)ed=1+k\phi(n)=1+k(p-1)(q-1)
    • 接下来我们其稍微变形：ed−1=k(p−1)(q−1)ed-1=k(p-1)(q-1)
    • 接下来我们将使用费马分解的思想，引入一个已知数g∈(1,n)g\in(1,n)（在算法的实现中一般采用随机生成）
    • 这样就有一个关系：ged−1=gk(p−1)(q−1)g^{ed-1}=g^{k(p-1)(q-1)}
    • 那么我们模将这个式子模一个nn转换为同余式，并设结果为xx就有：x≡ged−1≡gk(p−1)(q−1) mod( n)x\equiv g^{ed-1}\equiv g^{k(p-1)(q-1)}~mod(~n)，此时大部分情况都是满足p<x<np<x<n，只有少部分情况是x<p<nx<p<n的情况。错误的具体原因在这一步，这一步由欧拉定理可以得到x始终为1，所以下面的推导就不行了
    • 根据同余的性质：如果n=pq,a≡b mod( n)n=pq,a\equiv b~mod(~n)，那么就有a≡b mod( p),a≡b mod( q)a\equiv b~mod(~p),a\equiv b~mod(~q)
    • 所以就有：x≡gk(p−1)(q−1) mod( p)x\equiv g^{k(p-1)(q-1)}~mod(~p)
    • 由费马小定理可以得到：x≡(g(p−1))k(q−1)≡1 mod( p)x\equiv (g^{(p-1)})^{k(q-1)}\equiv 1~mod(~p)
    • 这个时候就出现了一个整除关系：x−1≡0 mod( p)x-1\equiv 0~mod(~p)
    • 当xx满足p<x<np<x<n这一条件的时候就能使用gcd(x-1,n)这一方法将nn分解了。

  • 接下来我们仍然进行一个推导操作，首先我们就可以进行这样的操作：

    • 这种操作有点类似于rabin素性检测以及AMM算法的其中一部分（有相当一部分算法都是利用这种模式）
    • 设(n,e)(n,e)是一个有效的RSA加密公钥对，对应的私钥对为(d,p,q)(d,p,q)。
    • 我们已知e,d,ne,d,n，接下来需要对nn进行分解，从而完全破解出RSA加密的私钥对。
    • 首先我们考虑密钥等式：ed=1+kϕ(n)=1+k(p−1)(q−1)ed=1+k\phi(n)=1+k(p-1)(q-1)
    • 接下来我们其稍微变形：ed−1=k(p−1)(q−1)ed-1=k(p-1)(q-1)
    • 接下来我们将使用费马分解的思想，引入一个已知数g∈(1,n)g\in(1,n)（在算法的实现中一般采用随机生成）
    • 这样就有一个关系：ged−1=gk(p−1)(q−1)g^{ed-1}=g^{k(p-1)(q-1)}，我们记ed−1=k(p−1)(q−1)=2tred-1=k(p-1)(q-1)=2^{t}r，所以就有：ged−1=g2trg^{ed-1}=g^{2^tr}
    • 同时在模nn的情况下会有ged−1≡g2tr≡1 mod( n)⇒g2tr−1≡p∗q≡0 mod( n)g^{ed-1}\equiv g^{2^tr}\equiv 1~mod(~n)\Rightarrow g^{2^tr}-1\equiv p*q\equiv 0~mod(~n)
    • 那么对于g2tr−1g^{2^tr}-1利用平方差就可以这样：

    \begin{align} g^{2^tr}-1&=(g^{2^{t-1}r}-1)(g^{2^{t-1}r}+1) \\&=(g^{2^{t-2}r}-1)(g^{2^{t-2}r}+1)(g^{2^{t-1}}+1) \\&=~...... \\&=(g^{r}-1)(g^{r}+1)(g^{2r}+1)...(g^{2^t-1}+1) \end{align}

    • 此时我们计算出xs≡(g2t−s−1) mod( n),s∈[1,t]x_s\equiv (g^{2^{t-s}}-1)~mod(~n),s\in[1,t]，此时xsx_s有可能就是pp或qq中的其中一个。可以使用gcd(n,xs)gcd(n,x_s)计算。（目前这个正确性证明还是有点不明白）
    • 如果gcd(n,xs)≠1gcd(n,x_s)≠1就可以直接出现了；如果gcd(n,xs)=1gcd(n,x_s)=1，那就重新选取一个随机数gg。

  • 以上就是推导过程，接下来概括一下算法流程：

    • 首先随机选取一个底数gg，计算出ged−1g^{ed-1}
    • 计算x=gcd(ged−1−1,n)x = gcd(g^{ed-1}-1,n)
    • 如果x=1x=1重新选取一个gg，如果x≠1x≠1就分解出来了pp

已知ed分解n 脚本

  • Python脚本1如下，这个分解比较简单，就只实现Python脚本了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import random
import math
from Crypto.Util.number import *
def know_ed_factor(n,e,d):
    """
    :param n: 待分解的模数n
    :param e: 公钥指数e
    :param d: 私钥指数d
    :return: (p,n//p)直接返回分解的两个素数
    """
    r = e * d - 1
    r_list = []
    
    while r % 2 == 0:
        r = r // 2
        r_list.append(r)

    while True:
        g = random.randint(1,n)
        for i in r_list:
            t = pow(g,i,n)
            p = math.gcd(t - 1,n)
            if p != 1 and p != n:
                return (p,n//p)
  • Python脚本2如下，由的时候直接给e∗de*d的结果：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import random
import math
def know_ed_factor(n,ed):
    """
    :param n: 待分解的模数n
    :param ed: 公钥指数和私钥指数的乘积ed
    :return: (p,n//p)直接返回分解的两个素数
    """
    r = ed - 1
    r_list = []

    while r % 2 == 0:
        r = r // 2
        r_list.append(r)

    while True:
        g = random.randint(1,n)
        for i in r_list:
            t = pow(g,i,n)
            p = math.gcd(t - 1,n)
            if p != 1 and p != n:
                return (p,n//p)

例题

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
import sympy
from gmpy2 import gcd, invert
from random import randint
from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, bytes_to_long, long_to_bytes
import base64

from zlib import *
flag = b"MRCTF{XXXX}"
base = 65537

def gen_prime(N):
    A = 0
    while 1:
        A = getPrime(N)
        if A % 8 == 5:
            break
    return A

def gen_p():
    p = getPrime(1024)
    q = getPrime(1024)
    assert (p < q)
    n = p * q
    print("P_n = ", n)
    F_n = (p - 1) * (q - 1)
    print("P_F_n = ", F_n)
    factor2 = 2021 * p + 2020 * q
    if factor2 < 0:
        factor2 = (-1) * factor2
    return sympy.nextprime(factor2)


def gen_q():
    p = getPrime(1024)
    q = getPrime(1024)
    assert (p < q)
    n = p * q
    print("Q_n = ", n)
    e = getRandomNBitInteger(53)
    F_n = (p - 1) * (q - 1)
    while gcd(e, F_n) != 1:
        e = getRandomNBitInteger(53)
    d = invert(e, F_n)
    print("Q_E_D = ", e * d)
    factor2 = 2021 * p - 2020 * q
    if factor2 < 0:
        factor2 = (-1) * factor2
    return sympy.nextprime(factor2)


if __name__ == "__main__":
    _E = base
    _P = gen_p()
    _Q = gen_q()
    assert (gcd(_E, (_P - 1) * (_Q - 1)) == 1)
    _M = bytes_to_long(flag)
    _C = pow(_M, _E, _P * _Q)
    print("Ciphertext = ", _C)
'''
P_n =  14057332139537395701238463644827948204030576528558543283405966933509944444681257521108769303999679955371474546213196051386802936343092965202519504111238572269823072199039812208100301939365080328518578704076769147484922508482686658959347725753762078590928561862163337382463252361958145933210306431342748775024336556028267742021320891681762543660468484018686865891073110757394154024833552558863671537491089957038648328973790692356014778420333896705595252711514117478072828880198506187667924020260600124717243067420876363980538994101929437978668709128652587073901337310278665778299513763593234951137512120572797739181693
P_F_n =  14057332139537395701238463644827948204030576528558543283405966933509944444681257521108769303999679955371474546213196051386802936343092965202519504111238572269823072199039812208100301939365080328518578704076769147484922508482686658959347725753762078590928561862163337382463252361958145933210306431342748775024099427363967321110127562039879018616082926935567951378185280882426903064598376668106616694623540074057210432790309571018778281723710994930151635857933293394780142192586806292968028305922173313521186946635709194350912242693822450297748434301924950358561859804256788098033426537956252964976682327991427626735740
Q_n =  20714298338160449749545360743688018842877274054540852096459485283936802341271363766157976112525034004319938054034934880860956966585051684483662535780621673316774842614701726445870630109196016676725183412879870463432277629916669130494040403733295593655306104176367902352484367520262917943100467697540593925707162162616635533550262718808746254599456286578409187895171015796991910123804529825519519278388910483133813330902530160448972926096083990208243274548561238253002789474920730760001104048093295680593033327818821255300893423412192265814418546134015557579236219461780344469127987669565138930308525189944897421753947
Q_E_D =  100772079222298134586116156850742817855408127716962891929259868746672572602333918958075582671752493618259518286336122772703330183037221105058298653490794337885098499073583821832532798309513538383175233429533467348390389323225198805294950484802068148590902907221150968539067980432831310376368202773212266320112670699737501054831646286585142281419237572222713975646843555024731855688573834108711874406149540078253774349708158063055754932812675786123700768288048445326199880983717504538825498103789304873682191053050366806825802602658674268440844577955499368404019114913934477160428428662847012289516655310680119638600315228284298935201
Ciphertext =  40855937355228438525361161524441274634175356845950884889338630813182607485910094677909779126550263304194796000904384775495000943424070396334435810126536165332565417336797036611773382728344687175253081047586602838685027428292621557914514629024324794275772522013126464926990620140406412999485728750385876868115091735425577555027394033416643032644774339644654011686716639760512353355719065795222201167219831780961308225780478482467294410828543488412258764446494815238766185728454416691898859462532083437213793104823759147317613637881419787581920745151430394526712790608442960106537539121880514269830696341737507717448946962021
'''

  • 很显然此题是考两个知识点，已知ϕ(n)\phi(n)分解nn，已知eded分解nn：
    • 对于pp的生成来说主要考察的是已知ϕ(n)\phi(n)分解nn
    • 对于qq的生成来说主要考察的是已知eded分解nn
  • 直接套脚本就行：
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
import random
import math
import sympy
from Crypto.Util.number import *
def know_ed_factor(n,ed):
    """
    :param n: 待分解的模数n
    :param ed: 公钥指数和私钥指数的乘积ed
    :return: (p,n//p)直接返回分解的两个素数
    """
    r = ed - 1
    r_list = []

    while r % 2 == 0:
        r = r // 2
        r_list.append(r)

    while True:
        g = random.randint(1,n)
        for i in r_list:
            t = pow(g,i,n)
            p = math.gcd(t - 1,n)
            if p != 1 and p != n:
                return (p,n//p)

def solve_2_th_root(a,b,c):
    """
    解一元二次方程: ax^2 + bx + c = 0
    :param a 二次项系数a
    :param b 一次项系数b
    :param c 常数项c
    :return: (x1,x2) x1,x2都是取整后的结果
    """
    delta = b**2 - 4*a*c
    if delta < 0:
        print("方程无实数解")
        return None

    elif delta == 0:
        x = (-1*b)//2*a
        return (x,x)

    elif delta > 0:
        sqrt_delta = math.isqrt(delta)
        x1 = int((-1*b + sqrt_delta)//2*a)
        x2 = int((-1*b - sqrt_delta)//2*a)
        return (x1,x2)

def know_phi_factor(n,phi):
    """
    已知phi分解n,仅限两个素数,n=pq
    参数n: 传入的是已知的n
    参数phi: 传入的是已知的phi
    :return: (p,q)
    """
    a = 1
    b = phi - n -1
    c = n
    p,q = solve_2_th_root(a,b,c)

    if p*q == n:
        print("正确分解出来p,q")
        return (p,q)
    else:
        print("分解不正确")
        return False


P_n = 
P_F_n =  
Q_n =  
Q_E_D = 
Ciphertext =  
e = 65537
# 已知phi分解n
p1,q1 = know_phi_factor(P_n,P_F_n)
if p1 > q1:
    p1,q1 = q1,p1

factor2 = 2021 * p1 + 2020 * q1
# 求得p
p = sympy.nextprime(factor2)

# 已知d分解n
p2,q2 = know_ed_factor(Q_n,Q_E_D)
if p2 > q2:
    p2,q2 = q2,p2
factor3 = 2021 * p2 - 2020 * q2
if factor3 < 0:
    factor3 = (-1) * factor3
# 求得q
q = sympy.nextprime(factor3)

# 进行正常RSA解密
n = p*q
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(Ciphertext,d,n)
flag = long_to_bytes(m)
print(flag)
# b'MRCTF{Ju3t_@_31mp13_que3t10n}'