image-20250809124458151

前言

  • 对于之前做过的一些RSA加密，求出ϕ(N)\phi(N)后就离解出密文非常近了，最关键一步其实就是求私钥dd也就是d≡e−1 mod (ϕ(n))d \equiv e^{-1}~mod~(\phi(n))，也就是求e在模ϕ(n)\phi(n)下的逆元。但是回顾一下数论知识就会发现在求e的逆元时首先逆元需要存在才能求得密文，而密文存在的条件是gcd(ϕ(n),e)=1gcd(\phi(n),e)=1，即二者互素。
  • 当gcd(ϕ(n),e)≠1gcd(\phi(n),e)≠1，也就是二者不互素的情况下，就不能使用求逆元的方法求得私钥dd，这就导致没办法正常的解密，此时就需要使用其他的方法进行处理，核心的方法是AMM算法。当然有些时候gcd(ϕ(n),e)gcd(\phi(n),e)比较小的时候会有更好的解决方法。

情况1—gcd(e,phi)比较小

推导

  • 对于gcd(e,ϕ(n))gcd(e,\phi(n))比较小的情况，这里有个疑问，到底怎么样才算是比较小呢？总需要有一个界限吧。这个先不急着知道，看完该情况处理方式的推导过程之后，其实就会明白了（当然到文章后面我也会说明）。

  • 对于gcd(e,ϕ(n))gcd(e,\phi(n))比较小的情况，不妨设gcd(e,ϕ(n))=tgcd(e,\phi(n))=t，则有e′=e//te'=e//t。那么就有如下推导：

c≡me≡me′t mod( n)d′=e′−1 mod( ϕ(n))⇒cd′≡mte′d′ mod( ϕ(n))⇒cd′≡mt∗1 mod( ϕ(n))⇒cd′≡mt mod( ϕ(n))\begin{array}{l} c \equiv m^e \equiv m^{e't}~mod(~n)\\ d' = e'^{-1}~mod(~\phi(n))\\ \Rightarrow c^{d'} \equiv m^{te'd'}~mod(~\phi(n))\\ \Rightarrow c^{d'} \equiv m^{t*1}~mod(~\phi(n))\\ \Rightarrow c^{d'} \equiv m^t ~mod(~\phi(n)) \end{array}

  • 通过如上推导其实就相当于对mem^e进行了一个降幂的操作，将mem^e降成了mtm^t。虽然这样求的并不是明文的原始数据，但是当mt<nm^t < n的时候，这其实就有cd′ mod( n)=mtc^{d'}~mod(~n) = m^t，因为mtm^t的实际值是小于n的，这样就可以得到真正的mtm^t的值，这样直接开根号就可以求得mm即明文
  • 所以上面所说的比较小的这个界限，其实就是根据mtm^t与n的大小相比较的情况。

例题

  • 题目来源：NSSCTF忘记具体哪题了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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
'''

解析如下：

  • 这题其实p、q、n、e、c都给了，先直接按照常规解密流程走走看，发现代码运行到d = gmpy2.invert(e,phi)会报错，报错内容是逆元不存在。
1
2
3
4
5
6
7
8
p = 
q = 
e = 
c = 
n = p*q
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
print(d)
  • 既然逆元不存在的话，那其实就是gcd(e,phi)!=1。那就先来看看e和phi的最大公因素，发现最大公因素是2，算是比较小的
1
2
print(gmpy2.gcd(e,phi))
# 2
  • 这时已经知道了gcd(e,phi)=2，那我们就尝试一下直接开方是否能解出flag。通过推导的过程得到m2m^2后直接开方，发现可以直接求得flag，那这题就算是完成了。exp如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import libnum
import gmpy2
p = 
q = 
e = 131074
c = 
n = p*q
phi = (p-1)*(q-1)
t = gmpy2.gcd(e,phi)
e_ = e//t
d_ = gmpy2.invert(e_,phi)
m_ = pow(c,d_,n)
m,x = gmpy2.iroot(m_,t)
print(libnum.n2s(int(m)))
# b'NSSCTF{inverse_and_root}'

情况2—e和(p-1)或(q-1)互素

推导

  • 这种情况是e和phi(n)phi(n)并不互素，但是e和p-1或q-1其中一个互素，这种情况也不需要使用AMM算法来求解。这里我们可以根据数论同余定理：若m=p1∗p2m=p_1*p_2，且a≡b( mod m)a\equiv b(~mod~m)，则有a≡b (mod p1)a\equiv b~(mod ~p_1)和a≡b (mod p2)a\equiv b~(mod~p_2)

  • 由于情况2是e和(p-1)、(q-1)其一互素，那就不妨设gcd(e,p−1)=1gcd(e,p-1)=1，也就是e−1 mod (ϕ(p))e^{-1}~mod~(\phi(p))存在

  • 这时对于情况2，就有如下推导：

n=p∗q,c≡me (mod n)⇒c≡me (mod p)gcd(e,p−1)=1⇒d′≡e mod( ϕ(p))⇒m≡me∗d′ mod( p)\begin{array}{l} n=p*q,c\equiv m^e~(mod~n)\\ \Rightarrow c\equiv m^e~(mod~p)\\ gcd(e,p-1)=1 \\ \Rightarrow d'\equiv e~mod(~\phi(p))\\ \Rightarrow m \equiv m^{e*d'}~mod(~p) \end{array}

  • 通过以上推导其实可以比较轻松的求出明文m。注意：这种条件下也有一个限制条件就是明文m必须小于p，或者不能远大于p，否则在计算m≡me∗d′ mod( p)m \equiv m^{e*d'}~mod(~p)时，没有办法还原出真正的m。

  • 所以情况2本质上是转换为这种形式的RSA加密从而去解密：

me≡c( mod p)me≡c( mod q)m^e \equiv c(~mod~p)\\ m^e \equiv c(~mod~q)

例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
import gmpy2
import uuid
p = getPrime(1024)
q = getPrime(1024)
e = 65537 * 3 * 5 * 7 * 9
flag = b'flag{' + str(uuid.uuid4()).encode() + b'}'
m = bytes_to_long(flag)
n = p*q
c = pow(m,e,n)
t = gmpy2.gcd(e,(p-1)*(q-1))
assert m**t > n
assert gmpy2.gcd(e,p-1) == 1
print("c =",c)
print("p =",p)
print("q =",q)
print("e =",e)
"""
c = 3337182590619332891367579450095260017621948297658608474765927585747734506999354328509683568925377515619204064576076990658487700251069936667303178625246768854069321364684053609635568733663779323983023955186264359508474160621887429553760676977134496070475993741436565049779300934693925938183415460792275981347122871322148183170843853299782459185390522709695133592628923912979653573313450679119054746286193009565269774894288416510194737513999402051586939745106744803143145962870026162701796980802087523932796322787192289532828027946970149619523331107916885023397981791618926415589540736035561888254541222060699696856314
p = 159938356510922739007311592848401509267166900696359028060364191269434588150823128062554654793663223011556473183265872894887579647809204570681388595087731937155662030332723972658713288321275408537705376086753101569069606146533249314025914677902624686308192979454352019032737737659516168971489486159303628756323
q = 96430824217229072069182669895140083481416631653486517954264036040832169030441397642841245167011632195729479683858486548460196751092827654037479770105468583618722386613888439003723062136646644840030371564874711263303175809941599945731077671059902934814813625011920226998576747817059406799637645523370079620639
e = 61932465
"""
  • 这题代码assert gmpy2.gcd(e,p-1) == 1已经告诉我们是e与p-1互素，并且此题也断言了m**t > n，这就导致我们并不能使用情况1的解法。就需要使用情况2推导的方法，exp如下：
1
2
3
4
5
6
7
8
9
10
11
12
import libnum
import gmpy2
c = 
p = 
q = 
e = 61932465
c = c % p
phi = p-1
d = gmpy2.invert(e,phi)
m = pow(c,d,p)
print(libnum.n2s(int(m)))
# b'flag{1858c133-a706-4110-af96-9639b25a3d5f}'

情况3—(p-1)或(q-1)是e的倍数

  • 情况3的解法会比前俩种情况复杂的多，这种情况一般是gcd(e,phi)=e或者是gcd(e,phi)=k*e，在解决此情况的时候需要使用到一个算法，这个算法为AMM算法，也就是

  • 在学习AMM算法之前需要先掌握几个定理和概念：

    • 二次剩余与二次非剩余
    • 欧拉判别法
    • 勒让德符号

AMM算法

  • AMM算法全称是AMM(全称为Adleman-Mander-Miller Method)，AMM算法与Tonelli-Shanks算法本质上是一样的，只不过乘积的时候顺序不同。

  • 首先提出AMM算法是在1977年，由Adleman, Manders, Miller发表于IEEE FOCS会议的一篇名为On taking roots in finite fields

  • 但是真正让AMM算法被重视的其实是在2011年，由Zhengjun Cao, Qian Sha, Xiao Fan发表的名为Adleman–Manders–Miller Root Extraction Method Revisited这篇论文，所以学习AMM算法主要参考的就是这篇论文，论文地址：1111.4877v1.pdf

  • 在论文中有介绍三种AMM算法：分别是二次同余方程的AMM算法，以及扩域后的二次同余方程的AMM算法，最后就是r次同余方程的AMM算法。这边我只学习二次同余方程的AMM算法和r次同余方程的AMM算法。

  • AMM算法的作用其实是快速求解同余方程x2≡a ( mod p)x^2\equiv a~(~mod~p)，其中p是素数。

问题：

求解二次同余方程x2≡δ (mod p)x^2 \equiv \delta~(mod~p)，其中p是奇素数。

算法推导：

  • 首先我们先将p-1（也就是奇素数p的欧拉函数），写成2t∗s2^t*s的形式，其中需要满足s是一个奇数。这样对于一个模p下的二次剩余δ\delta和模p下的二次非剩余ρ\rho来说有如下的式子(δs)2t mod( p)(\delta^s)^{2^{t}}~mod(~p)和式子(ρs)2t mod (p)(\rho^{s})^{2^{t}}~mod~(p)由欧拉判别可以得到：

(δs)2t−1≡1 mod( p),(ρs)2t−1≡−1 mod (p)(\delta^s)^{2^{t-1}}\equiv 1~mod(~p),(\rho^{s})^{2^{t-1}}\equiv -1~mod~(p)

  • 当t=1t=1的时候其实就有下式，即由上式左边的同余式同余号两边同乘δ\delta即可得到：

(δs+12)2≡δ mod( p)(\delta^{\frac{s+1}{2}})^2 \equiv \delta~mod(~p)

  • 当t≥2t≥2的时候，就会有(δs)2t−2 mod( p)∈{1,−1}(\delta^s)^{2^{t-2}}~mod(~p)\in\{1,-1\}，此时就可以找到一个k1=0 or 1k_1=0 ~or~1使得：

(δs)2t−2∗(ρs)2t−1∗k1≡1 mod( p)(\delta^s)^{2^{t-2}}*(\rho^s)^{2^{t-1}*k_1}\equiv1~mod(~p)

  • 对于(δs)2t−3(\delta^s)^{2^{t-3}}也有(δs)2t−3 mod( p)∈{1,−1}(\delta^s)^{2^{t-3}}~mod(~p)\in\{1,-1\}，此时也可以找到一个k2=0 or 1k_2=0~or~1使得：

(δs)2t−3∗(ρs)2t−1∗k2≡1 mod( p)(\delta^s)^{2^{t-3}}*(\rho^s)^{2^{t-1}*k_2}\equiv1~mod(~p)

  • 这样就可以找到k1,k2,...,kt−1∈{0,1}k_1,k_2,...,k_{t-1}\in\{0,1\}，使得：

(δs)(ρs)2∗k1+22∗k2+...+2t−1∗kt−1≡1 (mod p)(\delta^s)(\rho^s)^{2*k_1+2^2*k_2+...+2^{t-1}*k_{t-1}}\equiv1~(mod~p)

  • 最终我们就可以找到同余方程x2≡δ (mod p)x^2 \equiv \delta~(mod~p)的根即：

(δs+12)2((ρs)k1+2∗k2+...+2t−2∗kt−1)2≡δ (mod p)(\delta^{\frac{s+1}{2}})^2((\rho^s)^{k_1+2*k_2+...+2^{t-2}*k_{t-1}})^2 \equiv \delta~(mod~p)

  • 而这个程序运行的时间复杂度为O(log3p+t2log2p)O(log^3p+t^2log^2p)。

  • 下面这张图片就是AMM算法在有限域FpF_p下的求平方根的伪代码：

image-20250809180442472

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 random
def choose_one(p):
    while True:
        rho = random.randint(1,p)
        if pow(rho,(p-1)//2,p) != 1:
            return rho
def AMM(delta,p):
    """
    :param delta: 同余结果a
    :param p: 模数p
    :return:
    """
    if delta % p == 0:
        return 0
    if pow(delta,(p-1)//2,p) != 1:
        return None
    while True: # 在[1,p)中选择一个模p的二次非剩余
        rho = choose_one(p)
        if rho // p !=1:
            break

    t = 0 # 计算t、s
    phi = p-1
    while phi % 2 == 0:
        t += 1
        phi = phi//2
    s = (p-1)//(2**t)
    assert(s % 2 != 0)

    # 接下来就是最关键的一步,也就是我们花最多时间推导的部分
    a = pow(rho,s,p)
    b = pow(delta,s,p)
    h = 1
    for i in range(1,t):
        d = pow(b,pow(2,t-1-i),p)
        if d == 1:
            k = 0
        else:
            k = 1
        b = b * pow(a,2*k,p) % p
        h = h * pow(a,k,p) % p
        a = pow(a,2,p)

    return (pow(delta,(s+1)//2,p)*h) % p
  • 使用AMM算法解二次同余方程，可以解出一个解x1，而二次同余方程是有俩个解的，而第二个解其实就可以用(p-x1)%p这样其实就可以解得二次同余方程的所有解了。可以做一题算法题尝试一下：P5491 【模板】二次剩余 - 洛谷

拓展AMM算法

  • AMM算法是快速求解二次同余方程，而拓展AMM算法其实就是快速求解高次同余方程，即形如xr≡a (mod p)x^r\equiv a~(mod~p)，其中p是素数，对于这种形式的同余方程需要与离散对数这个同余方程的形式区别开来，离散对数的同余方程是这样的ax≡r (mod p)a^x\equiv r~(mod~p)。其实这俩式子容易混淆就和高一那时候幂函数与指数函数容易混淆是差不多的。

问题：

求解高次同余方程xr≡δ (mod p)x^{r}\equiv \delta~(mod~p)，其中p为奇素数。

算法推导：

  • 对于该高次同余方程，其实有两种情况：
    • 第一种其实就是RSA加密中求解私钥d的运算，也就是当gcd(r,ϕ(p))=1gcd(r,\phi(p))=1的情况下，就直接开根x≡δr−1x \equiv \delta^{r^{-1}}，这种情况已经算是相当的熟悉了
    • 第二种其实就是AMM算法的这种情况，也就是r∣p−1r\mid p-1这种情况
  • 当满足条件r∣p−1r\mid p-1这个情况时，此时p−1p-1就可以被表示成rt∗sr^t*s这种形式，这与前面AMM算法是类似的。此时还应该需要满足条件(s,r)=1(s,r)=1。
  • 此时已知的是一个n次剩余δ\delta，那么由r次剩余的判别就可以得到(δs)rt−1≡δp−1≡1 (mod p)(\delta^{s})^{r^{t-1}}\equiv \delta^{p-1} \equiv 1~(mod~p)。（对于r次剩余的判别可以问AI了解一下）
  • 因为(s,r)=1(s,r)=1，这样会很容易找到一个非负整数α\alpha使得s∣rα−1s\mid r\alpha -1，那其实就有rα−1=ksr\alpha-1=ks，这样就有如下式子：

(δrα−1)rt−1=(δks)rt−1=((δs)rt−1)k≡1 mod( p)(\delta^{r\alpha-1})^{r^{t-1}}=(\delta^{ks})^{r^{t-1}}=((\delta^{s})^{r^{t-1}})^k\equiv1~mod(~p)

  • 当t=1的时候，δα\delta^{\alpha}其实就是该同余方程的一个根。
  • 当t≥2的时候，这时随机生成一个r次方非剩余，ρ∈(0,p)\rho\in(0,p)，这时就有如下式子：

(ρs)i∗rt−1≠(ρs)j∗rt−1, i≠j,i,j∈{0,1,...,r−1}(\rho^{s})^{i*r^{t-1}} \not= (\rho^{s})^{j*r^{t-1}},~i\not=j, i,j\in\{0,1,...,r-1\}

  • 由于取遍{0,1,...,r−1}\{0,1,...,r-1\}，(ρs)i∗rt−1(\rho^{s})^{i*r^{t-1}}的结果都没有相同的情况，这样就不妨设Ki=(ρs)i∗rt−1and K={K0,K1,...,Kr−1}K_i=(\rho^{s})^{i*r^{t-1}} and~K=\{K_0,K_1,...,K_{r-1}\}

  • 这样其实就很容易找到一个KiK_i（任意取一个i好像都可以）满足式子Xr≡1 mod( p)X^r\equiv1~mod(~p)，该式子推导需要用上费马小定理：

Kir=(ρs)i∗rt=(ρs∗rt)i=(ρp−1)i≡1 mod( p)K_i^r=(\rho^s)^{i*r^t}=(\rho^{s*r^{t}})^{i}=(\rho^{p-1})^{i}\equiv1~mod(~p)

  • 而根据r次剩余的判别就有：

((δrα−1)rt−2)r≡1 mod( p)((\delta^{r\alpha-1})^{r^{t-2}})^{r} \equiv 1~mod(~p)

  • 联立上面俩个式子其实，并且存在唯一的j1∈{0,1,...,r−1}j_1\in\{0,1,...,r-1\}满足：

(δrα−1)rt−2≡Ki−j1 (mod p)(\delta^{r\alpha-1})^{r^{t-2}}\equiv K_{i-j_1}~(mod~p)

  • 此时取Ki=K0K_i=K_0就有，但是对于下面的这个式子，如果要求得j1j_1就逃不开解离散对数：

(δrα−1)rt−2≡K−j1 (mod p)⇒(δrα−1)rt−2Kj≡1 (mod p)⇒(δrα−1)rt−2(ρs)j1∗rt−1≡1 (mod p)(\delta^{r\alpha-1})^{r^{t-2}}\equiv K_{-j_1}~(mod~p)\\ \Rightarrow (\delta^{r\alpha-1})^{r^{t-2}}K_j \equiv 1~(mod~p)\\ \Rightarrow (\delta^{r\alpha-1})^{r^{t-2}}(\rho^{s})^{j_1*r^{t-1}} \equiv 1~(mod~p)

  • 以此类推，可以找到唯一的j2∈{0,1,...,r−1}j_2\in\{0,1,...,r-1\}使得：

(δrα−1)rt−3(ρs)j1∗rt−1(ρs)j2∗rt−2≡1 (mod p)(\delta^{r\alpha-1})^{r^{t-3}}(\rho^{s})^{j_1*r^{t-1}}(\rho^{s})^{j_2*r^{t-2}}\equiv 1~(mod~p)

  • 这样就可以得到j1,j2,...,jt−1j_1,j_2,...,j_{t-1}满足如下式子：

(δrα−1)(ρs)j1∗r(ρs)j2∗r2...(ρs)jt−1∗rt−1≡1 (mod p)⇒(δrα−1)(ρs)j1∗r(ρs)j2∗r2...(ρs)jt−1∗rt−1∗δ≡δ (mod p)⇒(δrα)((ρs)j1+j2∗r+...+jt−1∗rt−2)r≡δ (mod p)⇒(δα)r((ρs)j1+j2∗r+...+jt−1∗rt−2)r≡δ (mod p)\begin{array}{l} (\delta^{r\alpha-1})(\rho^{s})^{j_1*r}(\rho^{s})^{j_2*r^{2}}...(\rho^{s})^{j_{t-1}*r^{t-1}}\equiv 1~(mod~p)\\ \Rightarrow (\delta^{r\alpha-1})(\rho^{s})^{j_1*r}(\rho^{s})^{j_2*r^{2}}...(\rho^{s})^{j_{t-1}*r^{t-1}}*\delta\equiv \delta~(mod~p)\\ \Rightarrow(\delta^{r\alpha})((\rho^{s})^{j_1+j_2*r+...+j_{t-1}*r^{t-2}})^r\equiv \delta~(mod~p)\\ \Rightarrow(\delta^{\alpha})^{r}((\rho^{s})^{j_1+j_2*r+...+j_{t-1}*r^{t-2}})^r\equiv \delta~(mod~p) \end{array}

  • 这样就得到了一个解：x≡(δα)((ρs)j1+j2∗r+...+jt−1∗rt−2) (mod p)x\equiv(\delta^{\alpha})((\rho^{s})^{j_1+j_2*r+...+j_{t-1}*r^{t-2}})~(mod~p)

  • 下面这张图片是描述拓展AMM算法的伪代码：

image-20250809230550800

  • Python编写的拓展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
import random
import math
def choose_one(r,p):
    while True:
        rho = random.randint(1,p)
        if pow(rho,(p-1)//r,p) != 1:
            return  rho

def exAMM(delta,r,p):
    if (p-1) % r != 0: # 检测整除
        return None
    if pow(delta,(p-1)//r,p) != 1: # 检测N次剩余
        return None

    # 第一步、第二步: 先生成一个r次非剩余
    rho = choose_one(r,p)
    # 第三步(1): 求t,s
    t = 0
    phi = p-1
    while phi % r == 0:
        t += 1
        phi = phi//r
    s = (p-1)//(r**t)

    # 第三步(2): 计算最小的alpha,使得满足 s|r*alpha - 1
    if math.gcd(s,r) != 1:
        return None
    k = 1
    while (s*k+1) % r != 0:
        k+=1
    alpha = (s*k+1)//r

    # 第三步(3): 初始化一些值,为循环做准备
    a = pow(rho,pow(r,t-1)*s,p)
    b = pow(delta,r*alpha-1,p)
    c = pow(rho,s,p)
    h = 1
    for i in range(1,t):
        d = pow(b,pow(r,t-1-i),p)
        if d == 1:
            j = 0
        else:
            j = -math.log(d,a) % r # 这里可能还有点问题,但好像不影响可以跑出结果
        b = b*pow(c,r*j,p) % p
        h = h*pow(c,j) % p
        c = pow(c,r,p)
    return pow(delta,alpha,p) * h % p
  • 得到一组解后先别急，根据代数学基本定理：记重根的情况下，解的个数与方程最高次数相关，在模意义下也是这样的。所以使用AMM算法所求得的这个解不一定是m
  • 那应该如何求得其他解呢？已知一个解求其他解是比较容易的（这部分涉及到指数与原根）
  • 在模方程下有：Xr≡a (mod p)X^r\equiv a~(mod~p)，其中x0x_0是该方程的一个解，那么所有解的形式是：x=x0∗gk∗p−1r mod( p),k=0,1,...,r−1x=x_0*g^{k*\frac{p-1}{r}}~mod(~p),k=0,1,...,r-1，而这个g其实是一个生成元，满足gr≡1 (mod p)g^r\equiv1~(mod~p)
  • 所以得到一个解后，先要寻找一个满足条件的g，这样就可以求出全部的根了。但是当p太大的时候，找到生成元的时间复杂度太高了，所以就需要使用其他方式求得全部的解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 这种find_g的方式时间复杂度太高了
def find_g(p):
    for g in range(2,p):
        flag = True
        for d in range(1,p-1):
            if (p-1) % d == 0 and pow(g,d,p)==1:
                if d != p-1:
                    flag = False
        if flag:
            return g


def find_all_root(x0,r,p,g):
    roots = []
    for k in range(0,r):
        roots.append(x0 * pow(g,k*((p-1)//r),p) % p)
    return roots
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 得到所有的ri，即(ri*mp)^e%p = 1
def ALL_ROOT2(r, q):  # use function set() and .add() ensure that the generated elements are not repeated
    li = set()
    while(len(li) < r):
        p = powmod(random.randint(1, q-1), (q-1)//r, q)
        li.add(p)
    return li

def find_all_root(x0,p,li):
    roots = []
    for i in li:
        root = (x0*i) % p
        roots.append(root)
    return  roots

推导

  • 对应这个类型的题目，本质上是求解如下形式的高次同余方程。因为此时的e、phi不互素指数找不到逆元，正常的RSA解密方法就失效了。

image-20250810091234312

  • 首先要先进行如下的转化：

n=p∗qme≡c mod (n)⇒me≡c mod( p),me≡c mod( q)\begin{array}{l} n=p*q\\m^e\equiv c~mod~(n)\\ \Rightarrow m^e \equiv c ~mod(~p),m^e\equiv c~mod(~q) \end{array}

  • 然后使用AMM算法分别求得这俩个方程的一个解，求得一个解后再求生成元就很容易得到全部解，记me≡c mod( p)m^e \equiv c ~mod(~p)的解为m1im_{1i}，记me≡c mod( q)m^e\equiv c~mod(~q)的解为m2jm_{2j}

  • 最后再遍历m1i、m2jm_{1i}、m_{2j}，对他们使用CRT求解，总能求得一个解为m

{x≡m1i (mod p) i=1,2,...,ex≡m2j (mod q) j=1,2,...,e\begin{cases} x\equiv m_{1i} ~(mod~p)~i=1,2,...,e\\ x\equiv m_{2j} ~(mod~q)~j=1,2,...,e\\ \end{cases}

例题

  • 题目来源：NSSCTF，不知道是哪题
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
from Crypto.Util.number import *
import os
from gmpy2 import *

def getMyPrime(nbits):
    while True:
        n = 2*1009*getPrime(nbits//2)*getPrime(nbits//2)
        if is_prime(n+1):
            return n+1

p = getMyPrime(700)
q = getMyPrime(700)
n = p*q

e = 1009

flag = b'NSSCTF{******}' + os.urandom(100)

m = bytes_to_long(flag)
assert m.bit_length() < n.bit_length()
c = pow(m, e, n)

print(f'n = {n}')
print(f'c = {c}')
print(f'p = {p}')
print(f'q = {q}')

'''
n = 38041020633815871156456469733983765765506895617311762629687651104582466286930269704125415948922860928755218376007606985275046819516740493733602776653724917044661666016759231716059415706703608364873041098478331738686843910748962386378250780017056206432910543374411668835255040201640020726710967482627384460424737495938659004753604600674521079949545966815918391090355556787926276553281009472950401599151788863393804355849499551329
c = 2252456587771662978440183865248648532442503596913181525329434089345680311102588580009450289493044848004270703980243056178363045412903946651952904162045861994915982599488021388197891419171012611795147125799759947942753772847866647801312816514803861011346523945623870123406891646751226481676463538137263366023714001998348605629756519894600802504515051642140147685496526829541501501664072723281466792594858474882239889529245732945
p = 5220649501756432310453173296020153841505609640978826669340282938895377093244978215488158231209243571089268416199675077647719021740691293187913372884975853901554910056350739745148711689601574920977808625399309470283   
q = 7286645200183879820325990521698389973072307061827784645416472106180161656047009812712987400850001340478084529480635891468153462119149259083604029658605921695587836792877281924620444742434168448594010024363257554563
'''
  • 首先素数的生成满足一定的规律即：p-1的因子一定包含e=1009，所以e与p-1和q-1都不互素。这就需要使用AMM算法进行求根操作
  • 这题其实就是先使用AMM算法求出一个根，然后利用这个根求出所有解，最后遍历使用CRT操作，具体其实就看推导和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
88
89
90
91
92
93
94
import random
import math
import gmpy2
from Crypto.Util.number import *
from tqdm import tqdm
def choose_one(r,p):
    while True:
        rho = random.randint(1,p)
        if pow(rho,(p-1)//r,p) != 1:
            return  rho

def exAMM(delta,r,p):
    if (p-1) % r != 0: # 检测整除
        return None
    if pow(delta,(p-1)//r,p) != 1: # 检测N次剩余
        return None

    # 第一步、第二步: 先生成一个r次非剩余
    rho = choose_one(r,p)
    # 第三步(1): 求t,s
    t = 0
    phi = p-1
    while phi % r == 0:
        t += 1
        phi = (phi-1)//r
    s = (p-1)//(r**t)

    # 第三步(2): 计算最小的alpha,使得满足 s|r*alpha - 1
    if math.gcd(s,r) != 1:
        return None
    k = 1
    while (s*k+1) % r != 0:
        k+=1
    alpha = (s*k+1)//r

    # 第三步(3): 初始化一些值,为循环做准备
    a = pow(rho,pow(r,t-1)*s,p)
    b = pow(delta,r*alpha-1,p)
    c = pow(rho,s,p)
    h = 1
    for i in range(1,t):
        d = pow(b,pow(r,t-1-i),p)
        if d == 1:
            j = 0
        else:
            j = -math.log(d,a) % r
        b = b*pow(c,r*j,p) % p
        h = h*pow(c,j) % p
        c = pow(c,r,p)
    return pow(delta,alpha,p) * h % p

def ALL_ROOT2(r, q):  # use function set() and .add() ensure that the generated elements are not repeated
    li = set()
    while(len(li) < r):
        p = pow(random.randint(1, q-1), (q-1)//r, q)
        li.add(p)
    return li

def find_all_root(x0,p,li):
    roots = []
    for i in li:
        root = (x0*i) % p
        roots.append(root)
    return  roots
c = 2252456587771662978440183865248648532442503596913181525329434089345680311102588580009450289493044848004270703980243056178363045412903946651952904162045861994915982599488021388197891419171012611795147125799759947942753772847866647801312816514803861011346523945623870123406891646751226481676463538137263366023714001998348605629756519894600802504515051642140147685496526829541501501664072723281466792594858474882239889529245732945
p = 5220649501756432310453173296020153841505609640978826669340282938895377093244978215488158231209243571089268416199675077647719021740691293187913372884975853901554910056350739745148711689601574920977808625399309470283
q = 7286645200183879820325990521698389973072307061827784645416472106180161656047009812712987400850001340478084529480635891468153462119149259083604029658605921695587836792877281924620444742434168448594010024363257554563
r = 1009
delta1 = c % p
x0 = exAMM(delta1,r,p)
li1 = ALL_ROOT2(r,p)
roots1 = find_all_root(x0,p,li1)
delta2 = c % q
x1 = exAMM(delta2,r,q)
li2 = ALL_ROOT2(r,q)
roots2 = find_all_root(x1,q,li2)
print(roots1)
print(roots2)
for i in tqdm(range(len(roots1)),leave=True):
    for j in range(len(roots2)):
        # 除数p、q
        M = p*q
        m1 = q
        m2 = p
        m1_ = gmpy2.invert(m1,p)
        m2_ = gmpy2.invert(m2,q)
        m = (m1*m1_*roots1[i] + m2*m2_*roots2[j]) % M
        flag = long_to_bytes(m)
        if b'NSSCTF' in flag:
            print(flag)
            break
    if b'NSSCTF' in flag:
        break
# b"NSSCTF{ee5cb1a5-9d62-257a-9ef5-48b06ff0651a}\xbc\xbaw\xfe\xb8\x04A\x8es\xdct#\x1a\x91\x82\xbd\x0f\xfc<\xc4\xb0$\x01\xd0\xc8/\xd9d#\x9baf=\xf1\xfd\xde'\x0e=\xcfX\xd1\xdbM\x9f\xba\xaf\x8a\xb9\xf0\xd7\xaa{\xbf`:DY\xf5|\x11_R\x92\xa1\x9d\xc81\x12\xe9`\x17\xe3\n@K\\\xa5\x1f\xa7?\xdb\xf7p\x8aH\xba(\x02\xad\xf8n\xbe\xea\xcdTu\xac\xc4\xa1"
  • sagemath版本：
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 *
from tqdm import tqdm
c = 2252456587771662978440183865248648532442503596913181525329434089345680311102588580009450289493044848004270703980243056178363045412903946651952904162045861994915982599488021388197891419171012611795147125799759947942753772847866647801312816514803861011346523945623870123406891646751226481676463538137263366023714001998348605629756519894600802504515051642140147685496526829541501501664072723281466792594858474882239889529245732945
p = 5220649501756432310453173296020153841505609640978826669340282938895377093244978215488158231209243571089268416199675077647719021740691293187913372884975853901554910056350739745148711689601574920977808625399309470283   
q = 7286645200183879820325990521698389973072307061827784645416472106180161656047009812712987400850001340478084529480635891468153462119149259083604029658605921695587836792877281924620444742434168448594010024363257554563
r = 1009
c1 = c % p
c2 = c % q
Zmn = Zmod(p) # 创建一个模p的整数环
Zmn2 = Zmod(q)
# 在模p的整数环下求 x^r = c 的根，也就是x^p = c mod(p)满足该式子的未知数x
# all = True表示要求出所有解，而all = false则表示不需要求出所有解
x_list = Zmn(c1).nth_root(r,all=True)
y_list = Zmn2(c2).nth_root(r,all=True)
#print(y_list)

for i in tqdm(range(len(x_list)),leave = 'True'):
    for j in range(len(y_list)):
        m_ = [x_list[i],y_list[j]]
        p_ = [p,q]
        result = CRT(m_,p_)
        flag = long_to_bytes(result)
        if b'NSSCTF' in flag:
            print(flag)
            break
    if b'NSSCTF' in flag:
        break

情况4—(p-1)和(q-1)与e均不互素

  • 对于e与phi不互素来说通解其实都是有限域开根，但是对于这种情况，e与p-1和q-1均不互素并且p-1和q-1都不是r的倍数，那AMM算法适用的条件就失效了。
  • 但是思路还是有限域开根，这里直接使用sagemath一把梭，对于sagemath有限元两种开根方式，看sagemath一把梭部分。

例题

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

  • 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
from tqdm import tqdm
from Crypto.Util.number import *
p = 733089589724903586073820965792963746076789390539824437962807679954808310072656817423828613938510684864567664345751164944269489647964227519307980688068059059377123391499328155025962198363435968318689113750910755244276996554328840879221120846257832190569086861774466785101694608744384540722995426474322431441
q = 771182695213910447650732428220054698293987458796864628535794956332865106301119308051373568460701145677164052375651484670636989109023957702790185901445649197004100341656188532246838220216919835415376078688888076677350412398198442910825884505318258393640994788407100699355386681624118606588957344077387058721
n = p*q
c = 406314720119562590605554101860453913891646775958515375190169046313074168423687276987576196367702523895650602252851191274766072774312855212771035294337840170341052016067631007495713764510925931612800335613551752201920460877432379214684677593342046715833439574705829048358675771542989832566579493199671622475225225451781214904100440695928239014046619329247750637911015313431804069312072581674845078940868349474663382442540424342613429896445329365750444298236684237769335405534090013035238333534521759502103604033307768304224154383880727399879024077733935062478113298538634071453067782212909271392163928445051705642
e = 0x14
Zmn = Zmod(p) # 创建一个模p的整数环
Zmn2 = Zmod(q)
# 在模p的整数环下求 x^r = c 的根，也就是x^p = c mod(p)满足该式子的未知数x
# all = True表示要求出所有解，而all = false则表示不需要求出所有解
x_list = Zmn(c).nth_root(e,all = True)
y_list = Zmn2(c).nth_root(e,all = True)
#print(x_list)
#print(y_list)
for i in tqdm(range(len(x_list)),leave=True):
    for j in range(len(y_list)):
        c_ = [int(x_list[i]),int(y_list[j])]
        m = [p,q]
        x = CRT(c_,m)
        f = long_to_bytes(x)
        if b'flag' in f:
            print(f)
            break
    if b'flag' in f:
        break
# b'flag{r54__d34l1n6_w17h_3v3n_3 _&_f1nd1n6_n-7h_r0075~~}'

情况5—n=p^r*q的情况

  • 对于这种情况来说处理方式还是一样的去求根。

例题

  • 题目来源：2023年香山杯-list
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
import os
import gmpy2
from Crypto.Util.number import *
import random
from secrets import flag
def pad(s,l):
    return s + os.urandom(l - len(s))
def gen():
    g = getPrime(8)
    while True:
        p = g * random.getrandbits(138) + 1
        if isPrime(p):
            break
    while True:
        q = g * random.getrandbits(138) + 1
        if isPrime(q):
            break
    N = p ** 5 * q
    phi = p ** 4 * (p - 1) * (q - 1)
    d = random.getrandbits(256)
    e = inverse(d, phi)
    E = e * g
    hint = gmpy2.gcd(E, phi)
    return N, E, hint

flag = pad(flag,64)
m = bytes_to_long(flag)
n,e,hint = gen()
c = pow(m,e,n)
print(f'hint = {hint}')
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
# hint = 251
# n = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
# e = 3359917755894163258174451768521610910491402727660720673898848239095553816126131162471035843306464197912997253011899806560624938869918893182751614520610693643690087988363775343761651198776860913310798127832036941524620284804884136983215497742441302140070096928109039
# c = 72201537621260682675988549650349973570539366370497258107694937619698999052787116039080427209958662949131892284799148484018421298241124372816425123784602508705232247879799611203283114123802597553853842227351228626180079209388772101105198454904371772564490263034162

总结

通解

  • 对于情况1和情况2，这两种情况太特殊不具有一般性。在很多情况下不能使用情况1和情况2的方法。
  • 对于e和phi不互素的情形以及以后遇到的各种变形情况，需要牢牢抓住有限域开根与CRT配合这条思路，基本上这类题型换汤不换药。
  • 还有就是这类问题本质上就是使用算法的方式求第一类的高次同余式，如下图所示：

image-20250809235317052

  • 转化到RSA加密中其实就是去解如下高次同余方程：

xr≡δ mod( p)⇒me≡c (mod p)x^r\equiv \delta~mod(~p) \Rightarrow m^e\equiv c~(mod~p)

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
import random
import math
def choose_one(r,p):
    while True:
        rho = random.randint(1,p)
        if pow(rho,(p-1)//r,p) != 1:
            return  rho

def exAMM(delta,r,p):
    if (p-1) % r != 0: # 检测整除
        return None
    if pow(delta,(p-1)//r,p) != 1: # 检测N次剩余
        return None

    # 第一步、第二步: 先生成一个r次非剩余
    rho = choose_one(r,p)
    # 第三步(1): 求t,s
    t = 0
    phi = p-1
    while phi % r == 0:
        t += 1
        phi = (phi-1)//r
    s = (p-1)//(r**t)

    # 第三步(2): 计算最小的alpha,使得满足 s|r*alpha - 1
    if math.gcd(s,r) != 1:
        return None
    k = 1
    while (s*k+1) % r != 0:
        k+=1
    alpha = (s*k+1)//r

    # 第三步(3): 初始化一些值,为循环做准备
    a = pow(rho,pow(r,t-1)*s,p)
    b = pow(delta,r*alpha-1,p)
    c = pow(rho,s,p)
    h = 1
    for i in range(1,t):
        d = pow(b,pow(r,t-1-i),p)
        if d == 1:
            j = 0
        else:
            j = -math.log(d,a) % r
        b = b*pow(c,r*j,p) % p
        h = h*pow(c,j) % p
        c = pow(c,r,p)
    return pow(delta,alpha,p) * h % p

def ALL_ROOT2(r, q):  # use function set() and .add() ensure that the generated elements are not repeated
    li = set()
    while(len(li) < r):
        p = pow(random.randint(1, q-1), (q-1)//r, q)
        li.add(p)
    return li
    
def find_all_root(x0,p,li):
    roots = []
    for i in li:
        root = (x0*i) % p
        roots.append(root)
    return  roots

def solve_nth_root(c,e,p):
    x0 = exAMM(c,e,p)
    li = ALL_ROOT2(e,p)
    roots = find_all_root(x0,p,li)
    return roots

sagemath一把梭

  • 对于有限域开根，其实sagemath已经有对应的函数与方法了，其实还不止一种。接下来主要介绍sagemath中有限域开根的两中方式。所谓有限域开根其实在数论中就是求高次同余式xr=a (mod p)x^r= a~(mod~p)的根，而在其他代数结构可能就不是指模意义下的求根了。
  • 有了sagemath一把梭之后就不用AMM算法了，可以纯脚本小子哈哈哈，但是建议还是学一下AMM算法，都牢密码了，如果不是比赛的话认真学还是不错的。
  • 方式一：
1
2
3
4
5
6
7
8
p = 41
r = 8
c = 10
Zmn = Zmod(p) # 创建一个模p的整数环
# 在模p的整数环下求 x^r = c 的根，也就是x^p = c mod(p)满足该式子的未知数x
# all = True表示要求出所有解，而all = false则表示不需要求出所有解
x_list = Zmn(c).nth_root(r,all = True)
print(x_list)
  • 方式二：
1
2
3
4
5
6
7
8
9
p = 41
r = 8
c = 10
F = GF(p) # 创建一个有限域F_p
R.<x> = PolynomialRing(F) # 在F上定义一个多项式环,其变量为x 
f = x^r - c # 构造同余方程多项式
f = f.monic() # 转化为首一多项式
x_list = f.roots() # 有限域开方
print(x_list)

注意：实际上求根其实只需要求一个根，之后使用如下定理在模方程下有：Xr≡a (mod p)X^r\equiv a~(mod~p)，其中x0x_0是该方程的一个解，那么所有解的形式是：x=x0∗gk∗p−1r mod( p),k=0,1,...,r−1x=x_0*g^{k*\frac{p-1}{r}}~mod(~p),k=0,1,...,r-1，而这个g其实是一个生成元，满足gr≡1 (mod p)g^r\equiv1~(mod~p)即可快速求出。这个其实在拓展AMM算法中有详细讲解。

Rabin加密算法

加密算法

  • 参考博客：密码学之公钥密码体系（4）：Rabin公钥密码方案_rabin密码体制-CSDN博客

  • RSA加密算法在1977年就已经出现了，但是Rabin加密算法其实是在1979年被提出。该加密算法是基于平方根计算难度的公钥密码体系，而RSA是基于大整数分解的公钥密码体系，这俩点需要区别开来。

  • 但是为什么会在RSA加密中讲解Rabin加密算法呢？这是因为Rabin加密算法其实可以被看做是一个特殊的RSA加密算法，正常来说RSA加密的e一般都是选取65537，而Rabin加密算法基于平方根计算难度的公钥密码体系，所以e一般是选取2。

  • 接下来就介绍一下Rabin加密算法：

    • 首先先生成两个大素数p、q，这俩个大素数最好都满足p≡3 mod( 4),q≡3 (mod 4)p\equiv3~mod(~4),q\equiv3~(mod~4)，这样会简化求平方根的计算（后面会提到）
    • 然后计算模数n=p*q
    • 选取公钥pk=n
    • 选取私钥sk=(p,q)

  • 加密过程：对消息m进行模平方运算，也就是c≡m2 (mod n)c\equiv m^2~(mod~n)

  • 解密过程如下（其实解密过程就是上面求解高次同余式方程的过程）：

    • 将c≡m2 (mod n)c\equiv m^2~(mod~n)拆分成m2≡c mod( p),m2≡c (mod q)m^2\equiv c~mod(~p),m^2\equiv c~(mod~q)
    • 求解同余方程的根x2≡c mod( p),x2≡c (mod q)x^2\equiv c~mod(~p),x^2\equiv c~(mod~q)，这里有一个问题p、q越大二次同余方程的这个根就越难找到。
    • 所以在前面生成p、q有要求p≡3 mod( 4),q≡3 (mod 4)p\equiv3~mod(~4),q\equiv3~(mod~4)，这个其实就是用来化简求二次同余方程的这个过程。
    • 如果满足p≡3 mod( 4),q≡3 (mod 4)p\equiv3~mod(~4),q\equiv3~(mod~4)，此时x1≡cp+14mod p,y1≡cq+14 mod( q)x_1\equiv c^{\frac{p+1}{4}}mod~p,y_1\equiv c^{\frac{q+1}{4}}~mod(~q)，这样求可以快速求出两个式子的一个平方根但是这俩个平方根不一定是真的m
    • 所以分别求得这俩个同余式的平方根后，由根的对称性原理其实就很容易求得x2≡p−x1 (mod p),y2≡q−y1 (mod p)x_2\equiv p-x_1~(mod~p),y_2\equiv q-y_1~(mod~p)
    • 分别求得俩组解后，使用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
from Crypto.Util.number import *
import libnum
import gmpy2
def my_p_q(p_bit,q_bit):
    while True:
        p = getPrime(p_bit)
        q = getPrime(q_bit)
        if p % 4 == 3 and q % 4 == 3:
            return p,q
message = b'this_is_message'
m = bytes_to_long(message)
e = 2
p,q = my_p_q(512,512)
n = p*q
c = pow(m,e,n)
print("加密参数如下:")
print("n =",n)
print("p =",p)
print("q =",q)
print("e =",e)
print("m =",m)
print("c =",c)

# 接下来是解密过程,先解二次同余方程,再求解令一个根,最后使用CRT
x1 = pow(c,(p+1)//4,p)
y1 = pow(c,(q+1)//4,q)

x2 = (p-x1) % p
y2 = (q-y1) % q

c1 = [x1,x2]
c2 = [y1,y2]
for i in c1:
    for j in c2:
        M = p*q
        m1 = q
        m2 = p
        m1_ = gmpy2.invert(m1,p)
        m2_ = gmpy2.invert(m2,q)
        x = (m1*m1_*i + m2*m2_*j) % M
        print(long_to_bytes(x))
"""
b'this_is_message'
b"?\xbb\xfc<\x89/*`x\xc7V'y\xa7?\xf3#.T\x06R\xf2\x8b\x90\x16\xe5L\xc3\x82\x8a\xdfSS\x1e\x89-F\x8b\x1b\\\x12\t\xa3\xc79\xe9\x04\xe4\xe3\xa78E\x80A\xc8\xdf\xc7\xfc\xb84;P\xb8\x9b\xb6\xde^v\xd4&\xe3i\x91\xf6\x86\xdch\xf3\xd5\xb1\x93\xd7\xe8>0\x17\xf8Z\xfb\xc0\xe7\xb5-%\xaf\xa0t\xa6\xa9\x80\xfe\xa0*u\x96\xa0\xe2\x89\xf0&=\xb9\x88\xb6\x06\x07\x85,\x07\xb8\xa6\xba\xb3\xd7$M\xb0\xd6"
b'V\x85\x1cR\xd1\xc5\xb8r\xcenk\xba\x91\x17\xcdQ\xbd\xdc\x96\xc5MJ\x16\xa23|\xe0<=PZ\xec\xd8\x9d\x14*51f\x97\x19\x87/\x91&\xae\xee}\x1b\x1c\x9e\xa8\xb6VC,S\xfb\xfd\x8eh\xc5\x88\xea\xcb\xac\xcf \x85!\xdc\x04\xec\xdfz\x82\x0b\xa4\xe8\x97\xa9\x84\x9d\xea\xbb\xadF*\x89f8\xcc\xb9\xd2\xeb\xae"\x0b\x01\xb1\xbe\xd0K\xf2yC\x15+\xd4Z;\xe3\xa1y\x1e<\x019{\x13\xcc\x8c2\xe4\x9awfk'
b"\x96A\x18\x8fZ\xf4\xe2\xd3G5\xc1\xe2\n\xbf\rD\xe1\n\xea\xcb\xa0<\xa22Jb,\xff\xbf\xdb:@+\xbb\x9dW{\xbc\x81\xf3+\x90\xd3X`\x97\xf3a\xfe\xc3\xd6\xee6\x98\x0c\x0c\x1b\xf8\xb5\xc2\xa4\x16A\x86\x82\x8b-\x97YH\xbfn~\xd6\x01^t\x98\xbeI=\\\x86(\xeb\xc5>\x85\x85' \x81\xe6\xf8\x9bN\x96\xb1\xab2\xbdpvh\x0f\xe3\xf7\xb5\xc4\x80y\x9d)\xba\xbb\xda\x13\x06\x19Y\x13\xd9\x81HKc\xaf\xdc"
"""

例题1

  • 题目来源：VNCTF2025
  • 题目附件如下：
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 *
from secret import flag
flag=bytes_to_long(flag)
l=flag.bit_length()//3 + 1
n=[]
N=1
while len(n) < 3:
    p = 4*getPrime(l)-1
    if isPrime(p):
        n.append(p)
        N *= p

print(f'c={flag*flag%N}')
# flag**2 % N
from sympy import symbols, expand
x = symbols('x')
polynomial = expand((x - n[0]) * (x - n[1]) * (x - n[2]))

print(f'{polynomial=}')
# c=24884251313604275189259571459005374365204772270250725590014651519125317134307160341658199551661333326703566996431067426138627332156507267671028553934664652787411834581708944
# polynomial=x**3 - 15264966144147258587171776703005926730518438603688487721465*x**2 + 76513250180666948190254989703768338299723386154619468700730085586057638716434556720233473454400881002065319569292923*x - 125440939526343949494022113552414275560444252378483072729156599143746741258532431664938677330319449789665352104352620658550544887807433866999963624320909981994018431526620619

  • 非常典型的Rabin加密算法，其实还有不同的就是这个程序是三个素数的Rabin加密算法，而且题目没有正常的将n、p、q、r告诉我们而是给了一个多项式。
  • 其实直接那多项式的系数进行分解就行，这边sage可以支持分解多项式，那就用sage分解。
1
2
3
4
5
6
7
8
9
10
11
a3 = 1
a2 = -15264966144147258587171776703005926730518438603688487721465
a1 = 76513250180666948190254989703768338299723386154619468700730085586057638716434556720233473454400881002065319569292923
a0 = -125440939526343949494022113552414275560444252378483072729156599143746741258532431664938677330319449789665352104352620658550544887807433866999963624320909981994018431526620619
R.<x> = PolynomialRing(QQ)
f = x^3 + a2*x^2 + a1*x + a0
result = f.factor()
print(result)
"""
(x - 5908636118089697338533572785710162817248001570348495067227) * (x - 5487564316951417093934647798659941512646442958127439071827) * (x - 3868765709106144154703556118635822400623994075212553582411)
"""
  • 接下来其实就是正常的Rabin算法的界面，只不过要解三个二次同余式，CRT的次数也比较多，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
"""
(x - 5908636118089697338533572785710162817248001570348495067227) * (x - 5487564316951417093934647798659941512646442958127439071827) * (x - 3868765709106144154703556118635822400623994075212553582411)
"""
import gmpy2
from Crypto.Util.number import *
p = 5908636118089697338533572785710162817248001570348495067227
q = 5487564316951417093934647798659941512646442958127439071827
r = 3868765709106144154703556118635822400623994075212553582411
n = p*q*r
c = 24884251313604275189259571459005374365204772270250725590014651519125317134307160341658199551661333326703566996431067426138627332156507267671028553934664652787411834581708944
x1 = pow(c,(p+1)//4,p)
y1 = pow(c,(q+1)//4,q)
z1 = pow(c,(r+1)//4,r)
x2 = (p-x1) % p
y2 = (q-y1) % q
z2 = (r-z1) % r
c1 = [x1,x2]
c2 = [y1,y2]
c3 = [z1,z2]
print(c1)
print(c2)
print(c3)
for i in c1:
    for j in c2:
        for k in c3:
            M = n
            m1 = n//p
            m2 = n//q
            m3 = n//r
            m1_ = gmpy2.invert(m1,p)
            m2_ = gmpy2.invert(m2,q)
            m3_ = gmpy2.invert(m3,r)
            X = (m1*m1_*i + m2*m2_*j + m3*m3_*k) % M
            print(long_to_bytes(X))
# b'VNCTF{90dcfb2dfb21a21e0c8715cbf3643f4a47d3e2e4b3f7b7975954e6d9701d9648}'

例题2

  • 题目来源：