Misay's blog

RSA--e与phi不互素

发表于 更新于 分类于
本文字数： 18k
整理一下e与phi不互素的情况下怎么处理

前言

我们知道，在RSA系统中，解密依赖于欧拉定理 以及同余等式 ,那么在已知 下，容易得到

但是当不互素的情况下，私钥就无法正常计算，在此之下想要顺利求解明文,衍生了一系列问题，本文基于笔者日常中遇到的相关题型，给出对应的处理方法

从简单情况出发

我们不妨令

那么考虑转化为公钥指数为的RSA，有

显然此时我们能够计算

如果不是很大（个位数），当的时候，我们直接能得到

，直接开次方就能得到

如果不那么大的话，我们姑且还能尝试爆破 ，但是如果数据不支持，大到爆破不了，我们就得进一步观察已有数据中的代数结构了

如果同时与，互质（CRT加速RSA问题）

这里也就是在RSA中使用CRT算法加速运算的例子，我们都来讲讲如何操作

为什么要用CRT？

在RSA的计算中，我们有

，我们知道，往往非常大，那么计算上面两个式子就非常的消耗时间，而且也需要,我们注意到也是两个大质数，很有可能与即 ; 即也互素，那么我能就能把问题转化到模 下来讨论，下面是推导过程 由

这是由于也就是模的传递性，那么我们转过来计算在模下的私钥，即

那么在解密的时候就有

记

这里是因为可能比要大，所以我们无法直接解出来，然后我们根据中国剩余定理可以构造出一个对的解，如下

由第二个同余式不妨设 我们进而只需要解出来,把这个式子带入另一个同余式

我们只需计算 那么有 得到之后回代即可成功求出

可见这里我们的计算都是在模的式子中进行的，乘法运算的次数少了不少，实现了加速

说回正题，从上面不难看出，我们自始至终都没有尝试计算，成功回避了这个问题

来个例子–黑盾杯 2020-Factor

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

这里n不是很大，简单分解后能得到三个素因子，我们记为pqr，如下

1
2
3
4
5
6
7
8
9
10
p=11761833764528579549
q=17100682436035561357
r=17172929050033177661
print(n-p*q*r) # 0
print(gcd(e,phi)) # 3
print(gcd(e,p-1)) # 1
print(gcd(e,q-1)) # 3
print(gcd(e,r-1)) # 1
print(gcd(e,(p-1)*(r-1))) # 1

简单检查了关系，如上，这题方法很多，在上面的解法下即利用来使用CRT求解，代码如下

1
2
3
4
5
6
7
8
9
10
#sage
dp=inverse(e,p-1)
dr=inverse(e,r-1)
m1=pow(c,dp,p)
m2=pow(c,dr,r)
Ir=pow(r,-1,p)
h=pow(Ir*(m1-m2),1,p)
m=m2+h*r
print(long_to_bytes(m))
# CMISCCTF{3_RSA}

这里也能转化到在模下尝试求解，但是那对明文的大小有一定要求，我们还是使用通法，这里只要能找到两个满足要求的因子就行，但是这不是什么时候都能生效，请看下题

强网杯2022–[ASR]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import getPrime
from secret import falg
pad = lambda s:s + bytes([(len(s)-1)%16+1]*((len(s)-1)%16+1))

n = getPrime(128)**2 * getPrime(128)**2 * getPrime(128)**2 * getPrime(128)**2
e = 3
flag = pad(flag)
print(flag)
assert(len(flag) >= 48)
m = int.from_bytes(flag,'big')
c = pow(m,e,n)
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
n = 8250871280281573979365095715711359115372504458973444367083195431861307534563246537364248104106494598081988216584432003199198805753721448450911308558041115465900179230798939615583517756265557814710419157462721793864532239042758808298575522666358352726060578194045804198551989679722201244547561044646931280001
e = 3
c = 945272793717722090962030960824180726576357481511799904903841312265308706852971155205003971821843069272938250385935597609059700446530436381124650731751982419593070224310399320617914955227288662661442416421725698368791013785074809691867988444306279231013360024747585261790352627234450209996422862329513284149

注意到这里特别对m进行了填充，就是保证m比n的因子大，无法转化为在小因子的域下求解，看看下面这段失败的exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
e = 3
n = 8250871280281573979365095715711359115372504458973444367083195431861307534563246537364248104106494598081988216584432003199198805753721448450911308558041115465900179230798939615583517756265557814710419157462721793864532239042758808298575522666358352726060578194045804198551989679722201244547561044646931280001
c = 945272793717722090962030960824180726576357481511799904903841312265308706852971155205003971821843069272938250385935597609059700446530436381124650731751982419593070224310399320617914955227288662661442416421725698368791013785074809691867988444306279231013360024747585261790352627234450209996422862329513284149

p = 225933944608558304529179430753170813347
q = 260594583349478633632570848336184053653
r = 218566259296037866647273372633238739089
t = 223213222467584072959434495118689164399

print(gcd(e,p-1)) # 3
print(gcd(e,q-1)) # 1
print(gcd(e,r-1)) # 3
print(gcd(e,t-1)) # 1
dt=inverse(e,t-1)
dq=inverse(e,q-1)
m1=pow(c,dt,t)
m2=pow(c,dq,q)
Iq=pow(q,-1,t)
h=pow(Iq*(m1-m2),1,t)
m=m2+h*q
print(long_to_bytes(m))

这里的确找到了满足的两个因子，但是我们注意到，若又,所以我们在上述代码中解出来的满足，也就是说，如果的时候，这个方法就暂时失效了，这是在多因子RSA下特别的问题，注意到我们还有两个因子没有使用，为了也能使用上它们，我们给出更加一般的方法

有限域开根

想想我们的核心目标是什么？–求解 那么我们为什么要找到这个的?重新捋一遍过程，我们就发现，是为了去计算来求解满足的,换言之，我们还是在求模不同素因子下的,我们不妨想一下，真的重要吗？,我们看这个方程 这不就是在下的方程吗？这里还非常小，完全可以在这个有限域下来开根求解所有符合题意的的取值集合，显然可能有多解，但是我们可以依次枚举中的值，由上述分析，若，那么否则也有

那么我们枚举这四个集合，一定能找到满足我们需要的 这就是中国剩余定理了，我们直接打CRT就能解出来m，而且我们用到了所有的因子，几乎可以保证这里是唯一的，如果不是唯一的，我们确定一下中的，转化到模下就行，下面是修改后的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
# sage
from Crypto.Util.number import *
from itertools import product

# Given parameters
e = 3
n = 8250871280281573979365095715711359115372504458973444367083195431861307534563246537364248104106494598081988216584432003199198805753721448450911308558041115465900179230798939615583517756265557814710419157462721793864532239042758808298575522666358352726060578194045804198551989679722201244547561044646931280001
c = 945272793717722090962030960824180726576357481511799904903841312265308706852971155205003971821843069272938250385935597609059700446530436381124650731751982419593070224310399320617914955227288662661442416421725698368791013785074809691867988444306279231013360024747585261790352627234450209996422862329513284149

# Prime factors
p = 225933944608558304529179430753170813347
q = 260594583349478633632570848336184053653
r = 218566259296037866647273372633238739089
t = 223213222467584072959434495118689164399

# Create polynomial rings and find roots in each field
R.<x> = Zmod(p)[]
f = x^e - c
res_p = f.monic().roots()

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

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

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

# Iterate through all possible combinations of roots
for (m_p, _) in res_p:
    for (m_q, _) in res_q:
        for (m_r, _) in res_r:
            for (m_t, _) in res_t:
                # Combine using CRT in stages
                # First combine p and q
                m_pq = crt(int(m_p), int(m_q), p, q)
                # Then combine r and t
                m_rt = crt(int(m_r), int(m_t), r, t)
                # Finally combine the two results
                m = crt(m_pq, m_rt, p*q, r*t)
                
                mes = long_to_bytes(m)
                print(mes)
        
# b'flag{Fear_can_hold_you_prisoner_Hope_can_set_you_free}\x06\x06\x06\x06\x06\x06'

在这个脚本下我们能解决大部分问题，但是当太大的时候我们就得考虑其他的方法来处理了

根据题型，我们有几种应付的思路

UCSCCTF2025–EzCalculate

题面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
p = 9586253455468582613875015189854230646329578628731744411408644831684238720919107792959420247980417763684885397749546095133107188260274536708721056484419031
q = 8998523072192453101232205847855618180700579235012899613083663121402246420191771909612939404791268078655630846054784775118256720627970477420936836352759291
n = p * q
e = 65536
c = 74962027356320017542746842438347279031419999636985213695851878703229715143667648659071242394028952959096683055640906478244974899784491598741415530787571499313545501736858104610426804890565497123850685161829628373760791083545457573498600656412030353579510452843445377415943924958414311373173951242344875240776

phi = (p - 1) * (q - 1)
print(gcd(e, phi)) # 4
print(gcd(e, p - 1)) # 2
print(gcd(e, q - 1)) # 2

print(gcd(e,(p-1)//2)) # 1
print(gcd(e,(q-1)//2)) # 1

在这里，我们注意到同时与和互素，于是我们能有一个取巧的方法，先转化到对因子的同余式，即

再不妨记

容易有 那么必然存在

写成等式，即

我们考虑同余式 这里就初见端倪了，我们做一个换元 那不就是二次剩余的判别式吗

注意到这里我们得到了重要的模式子，回看解密过程 也就是 也就是说我们有 回到了熟悉的地方，再构造CRT就可以解出了

那么这里如果再改成 呢，思路还是考虑这个式子 可以考虑去计算次的本原单位根，但考虑到虚数的引用带来的一系列不确定性，不再过度深入。

那么如果这种大素数呢？往往会伴随另外一个条件，是,在这种情况下，我们可以使用AMM算法来找到一个满足条件的

AMM算法

我们先从上面的RSA题目中抽离出来，来看看整数域开根下的一般问题，我们面对的是同余式 我们往往已知且是一个素数，我们想要找出一个满足方程的，从简单出发，我们先讨论的情况

e=2时

也就是处理方程

因为是素数，我们可以这样来设 其中为奇数

那么我们知道，对于所有的模的二次剩余数 （这里就是一个模的二次剩余）有 代入上面的式子，可以得到 再次从简单出发，如果

那么直接有 两边同乘一个 ，又，直接开方，有 前面强调了就是这样的一个二次剩余，也就是说，我们代入，这个方程是成立的，所以说 这个方程两边平方后，就是我们非常熟悉的 所以说，我们就找到了一个符合要求的

那么，如果呢？

我们知道对于所有的模的非二次剩余,有 我们不难得到 开方，能得到两种结果，即

为了避免负数的出现导致开根开出虚数，我们乘上一个非二次剩余，即 这里用来记录是否为负，是自己生成的

注意到我们这里实际上就是，而都是已知的，在代码中我们可以直接算这个，如果是1，就令，否则为1

同余式右边为1后继续开方，即 确定的方法和上面一样，我们一直开方，直到的指数幂中不含,会得到形似如下的式子 两边同乘一个，再开方就得到了我们需要的 这里的核心思路就是消去，构造 的代数式

这里AMM找到的只是一个满足要求的解，我们知道在的情况下，符合条件的有两个，为了找到另一个解，也就是描述在模下的,我们使用如下方法，任意找到一个，使得它不是模的二次剩余，那么有

也就是说，,都是满足要求的解，在下

e更大的时候

我们现在要考虑的是 这里的问题是从二次剩余转到次剩余，这里我们需要条件,设 那么对我们要求的，有 还是从简单出发，如果

即 此时如果，那么可以参考RSA的解法 代入， 可见这里就是一个满足要求的解

如果可以考虑离散对数的方法

如果

我们站在高一点的视角下一个结论

AMM算法就是在模p整数域中构造一个e阶子群来开根

先看要讨论的式子 其中

我们可以令 由欧拉定理,当 这里可以视为一个生成元为，阶为的模子群

那么稍微变形一下 令 那么我们就构造了一个模下，生成元为的阶子群 特别注意不能是模的次剩余，也就是 否则就是1开根开出来的一个结果，你拿生成的群就无法包含所有可能的根

接下来我们说明中元素进行次幂后模为1 那么也就是说，在模群下对1开次方根的结果都会落在群中

知道这个结论，我们对上式做一个小变形 再 我们都知道，仿照上面的思路，先对 开次方根，就能得到

我们再直接计算这个元素的值，然后在这个群中找到逆元

假设 那么逆元就是 所以说上面的同余式开根后就直接是 如此往下计算，直到同余式左边只剩下次幂，最后解出来之后还要记得根据这个群的个单位根对应出组解，当的时候，我们来操作一下，就是

分解p-1

计算逆元d，找到初始解

逐步上升

先找到生成元 再定义一些初始变量

可知

再在每一次迭代的过程中，计算 如果 说明这次开方的结果开出来就是次剩余根，无需调整，否则要进行修改，并同时对进行修正

最后对得到的根乘上个单位根，得到解

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
# sage
def AM1M(residue, e, p):
    """
    返回 x^e ≡ residue mod p 的所有解
    """
    if (p-1) % e != 0:
        raise ValueError(f"e={e} 不能整除 p-1={p-1}，AMM 不适用")

    # 分解 p-1 = e^t * s
    t = valuation(p - 1, e)
    s = (p - 1) // (e^t)
    
    # 计算 d = e^{-1} mod s
    d = inverse_mod(e, s)
    
    # 简单情况：t=1
    if t == 1:
        x = power_mod(residue, d, p)
        F = GF(p)
        zeta = F.zeta(e)
        return [ (x * zeta**i) % p for i in range(e) ]
    
    
    # 寻找 e 次非剩余（生成元）
    F = GF(p)
    g = F.multiplicative_generator()
    noresidue = g
    while (noresidue^((p-1)//e)) == 1:
        noresidue *= g
    
    # 计算单位根和辅助变量
    a = power_mod(noresidue, e^(t-1) * s, p)
    b = power_mod(residue, e * d - 1, p)
    c = power_mod(noresidue, s, p)
    h = 1
    
    # Hensel 提升
    for i in range(1, t):
        d_i = power_mod(b, e^(t-1-i), p)
        if d_i == 1:
            j = 0
        else:
            j = -discrete_log(d_i, a)  
        b = (power_mod(c, e, p)^j * b) % p
        h = (power_mod(c, j, p) * h) % p
        c = power_mod(c, e, p)
    
    x0 = (power_mod(residue, d, p) * h) % p
    ω = F.zeta(e)  # e 阶单位根
    return [ (x0 * ω^i) % p for i in range(e) ]  # 返回所有解

这里能得到所有模p下的解，再整合起来打CRT就解决了

来个实战例子

NCTF2019–EzRSA

1
2
3
4
5
6
7
8
9
10
11
12
e = 0x1337
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
n = p * q
c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359

phi = (p - 1) * (q - 1)
print(gcd(e, phi)) #4919
print(gcd(e, p - 1)) #4919
print(gcd(e, q - 1)) # 4919
print(int(e)) #4919

exp 这里使用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
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
from Crypto.Util.number import *
import itertools
from multiprocessing import Pool, cpu_count
from tqdm import tqdm
from sage.all import *

e = 0x1337
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
n = p * q
c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359

cp = c % p
cq = c % q

inv_p = pow(p, -1, q)
inv_q = pow(q, -1, p)

def AMM(residue, e, p):
    if (p-1) % e != 0:
        raise ValueError(f"e={e} does not divide p-1={p-1}")

    t = valuation(p - 1, e)
    s = (p - 1) // (e**t)
    
    d = inverse_mod(e, s)
    
    if t == 1:
        x = power_mod(residue, d, p)
        F = GF(p)
        zeta = F.zeta(e)
        return [ (x * zeta**i) % p for i in range(e) ]
    
    F = GF(p)
    g = F.multiplicative_generator()
    noresidue = g
    while (noresidue**((p-1)//e)) == 1:
        noresidue *= g
    
    a = power_mod(noresidue, e**(t-1) * s, p)
    b = power_mod(residue, e * d - 1, p)
    c = power_mod(noresidue, s, p)
    h = 1
    
    for i in range(1, t):
        d_i = power_mod(b, e**(t-1-i), p)
        if d_i == 1:
            j = 0
        else:
            j = -discrete_log(d_i, a)
        b = (power_mod(c, e, p)**j * b) % p
        h = (power_mod(c, j, p) * h) % p
        c = power_mod(c, e, p)
    
    x0 = (power_mod(residue, d, p) * h) % p
    ω = F.zeta(e)
    return [ (x0 * ω**i) % p for i in range(e) ]

def compute_crt(args):
    m1, m2 = args
    m1_int = int(m1)  # Convert to Python int
    m2_int = int(m2)  # Convert to Python int
    x = (m1_int * q * inv_q + m2_int * p * inv_p) % n
    return x

def find_flag():
    resp = AMM(cp, e, p)
    resq = AMM(cq, e, q)

    print(f"[+] Solutions in GF(p): {len(resp)}")
    print(f"[+] Solutions in GF(q): {len(resq)}")
    print(f"[+] Total combinations: {len(resp) * len(resq)}")

    with Pool(cpu_count()) as pool:
        combinations = itertools.product(resp, resq)
        for x in tqdm(
            pool.imap_unordered(compute_crt, combinations, chunksize=10000),
            total=len(resp) * len(resq),
            desc="Brute-forcing CRT"
        ):
            flag = long_to_bytes(x)
            if b'NCTF{' in flag:
                print(f"\n[+] Flag: {flag.decode()}")
                pool.terminate()
                return

    print("[-] Flag not found")

if __name__ == "__main__":
    find_flag()
    
    # 大约跑三分钟