RSA常用攻击

1.RSA

1.1.RSA证书格式：

各个标签头：

2048RSA示例：

1.2.e与L不互素：

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
# sagemath
def AMM(o, r, q):  
    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  
    print('Find one solution: {}'.format(result))  
    return result
    
# def findAllPRoot(p, e):
#     print("456")
#     proot = set()
#     while len(proot) <​ e:
#         proot.add(pow(random.randint(2, p-1), int((p-1)//e), int(p)))

#     return proot
# m1=findAllPRoot(p,7438)

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

低加密指数攻击：

1.3.coppersmith 定理:

1.3.1.已知p的高位(丢失位不超过454位)，脚本：

1
2
3
4
5
6
7
8
9
10
p_high = 
n = 
c = 
pbits = 1024 # p原本位数
kbits = pbits - p_high.nbits() # p丢失位数
p_high = p_high <​<​ kbits
PR.<​x> = PolynomialRing(Zmod(n)) # 构建一个以x为符号模n的一元多项式环
f = x + p_high
p0 = f.small_roots(X = 2 ^ kbits,beta = 0.4,epsilon=0.02)[0]# 多项式小值根求解及因子分解，其中X表示求解根的上界
print(p_high + p0)

注：

已知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
# [DASCTF 2023 & 0X401七月暑期挑战赛]ezRSA
# gift = P ^ (Q >> 16)  

import gmpy2  
from Crypto.Util.number import *  
  
N = 75000029……
gift = 800673061……
C = 141837 ……
  
ph = bin(gift)[2:][:16] + '0' * (512 - 16)  
ph = int(ph, 2)  
x = bin(gift)[2:][16:]  
  
# 递归函数剪枝法  
def fac(x, tp, tq):  
    if len(x) == 0:  # 所有位都处理完毕  
        return  
    if tp * tq > N:  # 乘积超过 N，剪枝  
        return  
    if N % (tp + 1) == 0:  # 找到因子 P        print(tp + 1)  
        return  
  
    v = x[0]  
    r = x[1:]  
    l = len(r)  
  
    if (tp + (1 <​<​ (l + 1))) * (tq + (1 <​<​ (l + 17))) <​ N:  
  
        return  
  
    if v == '0':  
        fac(r, tp, tq)  
        fac(r, tp + (1 <​<​ l), tq + (1 <​<​ (l + 16)))  
    else:  
        fac(r, tp + (1 <​<​ l), tq)  
        fac(r, tp, tq + (1 <​<​ (l + 16)))  
  
  
# q第1位为1 x[0]=='0'  
tq = 1 <​<​ 511  
tp = ph + (1 <​<​ (512 - 16 - 1))  
  
fac(x, tp, tq)  
  
P = 8006847171…… 
Q = N // P  
e = 11  
# pow(n, e, N) = C  
n = pow(C, gmpy2.invert(e, (P - 1) * (Q - 1)), N)

1.3.2已知p的高位和低位(丢失中间)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
这道题目是丢失459位，采用爆破剩下的五位(32次)
from gmpy2 import *
from Crypto.Util.number import *
 
p1 = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
q0 = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 218154......
mod=pow(2,265)
p0=(n/q0)%mod
pbar=(p1<​<​724)+p0
PR.<​x> = PolynomialRing(Zmod(n))# 构建以x为变量的一元多项式环
 
for i in range(32): # 循环爆破5位
    f=pbar+x*mod*32 # 构建多项式，pbar为已知的高位与低位，爆破较低的五位bit，剩下的直接套用前面脚本
    f=f.monic()# monic函数，将x的系数化为1，方便计算
    pp=f.small_roots(X=2^454,beta=0.4)
    if(pp):
        break
    pbar+=mod
 
p=pbar+pp[0]*32*mod # 得出p
assert n%p==0
print(p)

1.3.3 已知m的高位

1
2
3
4
5
6
7
8
9
10
11
12
基本所有的m高位攻击中e需要e = 3，可以当作已知条件使用（如果题目不给的话）
from Crypto.Util.number import *
n = 1411394818......
m_high = 152080028......
c = 6635663......
e = 3
kbits = 315
PR.<​x> = PolynomialRing(Zmod(n))
f = (m_high + x)^e - c
x0 = f.small_roots(2^kbits,1)[0]
m = m_high + x0
print(m)

1.3.4.低位攻击【d & (1 <​<​ 512 - 1)】

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
def get_full_p(p_low, n,d_low):
    PR.<​x> = PolynomialRing(Zmod(n))
    d_lowbits = d_low.nbits()
    nbits = n.nbits()
    p_lowbits = p_low.nbits()
    f = 2^p_lowbits*x + p_low
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-p_lowbits), beta=0.4)  
    if roots:
        x0 = roots[0]
        p = gcd(2^d_lowbits*x0 + p_low, n)
        return ZZ(p)

def find_p_low(d_low, e, n):
    X = var('X')
    for k in range(1, e+1):
        results = solve_mod([e*d_low*X == k*n*X + k*X + X-k*X**2 - k*n], 2^d_low.nbits())
        for x in results:
            p_low = ZZ(x[0])
            p = get_full_p(p_low, n,d_low)
            if p and p != 1:
                return p

n = 928965......
c = 5616437818......
d_low = 787673996......
e = 3
find_p_low(d_low, e, n)

1.3.5.高位攻击【d >> 222 <​<​ 222】

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
解出来的p与实际p的误差，和leakd与实际d之间的误差相当，故解出来的p的高位是准确的，后面可能会因进位产生误差，不过影响不大，之后p高位攻击求解的时候把最大限制位数上调几位就行

from tqdm import *
from Crypto.Util.number import *
def get_full_p(p_high, n,d_high,bits):
    PR.<​x> = PolynomialRing(Zmod(n))    
    f = x + p_high
    f = f.monic()
    roots = f.small_roots(X=2^(bits + 4), beta=0.4)  
    if roots:
        x0 = roots[0]
        p = gcd(x0 + p_high, n)
        return ZZ(p)


def find_p_high(d_high, e, n,bits):
    PR.<​X> = PolynomialRing(RealField(1000))
    for k in tqdm(range(1, e+1)):
	    # 由于我们不知道d_low，我们近似认为 d ≈ d_high * 2^bits：
        f=e * d_high * X - (k*n*X + k*X + X-k*X**2 - k*n)
        results = f.roots()
        if results:
            for x in results:
                p_high = int(x[0])
                p = get_full_p(p_high, n,d_high,bits)
                if p and p != 1:
                    return p


c1 = 896235......
leak1 = 13847488......
n1 = 1463316......
e1 = 149
p1 = find_p_high(leak1, e1, n1,222)
q1 = n1 // p1
d1 = inverse(e1,(p1 - 1) * (p1 - 1))
m1 = pow(c1,int(d1),n1)

1.3.6.多变量coppersmith攻击

注意：small_roots()只能用于单变量，当题目需要用到多变量是，需要我们自己构造格进行攻击！

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *  
flag = b'?'  
  
e = 65537  
p, q = getPrime(1024), getPrime(1024)  
N = p * q  
gift = p&(2**923-2**101)  
m = bytes_to_long(flag)  
c = pow(m, e, N)  
  
print("N = ",N)  
print("gift = ",gift)  
print("c = ",c)

脚本：

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#sage#
N = 
p0 = 
c =  

def bivariate(pol, XX, YY, kk=4):
    f = pol.change_ring(ZZ) # 转成整数环
    PR, (x, y) = f.parent().objgens()  
    # 获取多项式环对象和其生成元。
    # PR = f.parent()
    # x, y = PR.gens()
                                
    idx = [(k - i, i) for k in range(kk + 1) for i in range(k + 1)]
    monomials = list(map(lambda t: PR(x ** t[0] * y ** t[1]), idx))
    # collect the shift-polynomials
    g = []
    for h, i in idx:
        if h == 0:
            g.append(y ** h * x ** i * N)
        else:
            g.append(y ** (h - 1) * x ** i * f)

    # construct lattice basis
    M = Matrix(ZZ, len(g))
    for row in range(M.nrows()):
        for col in range(M.ncols()):
            h, i = idx[col]
            M[row, col] = g[row][h, i] * XX ** h * YY ** i

    # LLL
    B = M.LLL()

    PX = PolynomialRing(ZZ, 'xs')
    xs = PX.gen()
    PY = PolynomialRing(ZZ, 'ys')
    ys = PY.gen()

    # Transform LLL-reduced vectors to polynomials
    H = [(i, PR(0)) for i in range(B.nrows())]
    H = dict(H)
    for i in range(B.nrows()):
        for j in range(B.ncols()):
            H[i] += PR((monomials[j] * B[i, j]) / monomials[j](XX, YY))

    # Find the root
    poly1 = H[0].resultant(H[1], y).subs(x=xs)
    poly2 = H[0].resultant(H[2], y).subs(x=xs)
    poly = gcd(poly1, poly2)
    x_root = poly.roots()[0][0]

    poly1 = H[0].resultant(H[1], x).subs(y=ys)
    poly2 = H[0].resultant(H[2], x).subs(y=ys)
    poly = gcd(poly1, poly2)
    y_root = poly.roots()[0][0]

    return x_root, y_root

PR = PolynomialRing(Zmod(N), names='x,y')
x, y = PR.gens()
pol = 2 ** 923 * x + y + p0

x, y = bivariate(pol, 2 ** 101, 2 ** 101)  # 注意传参
p = 2 ** 923 * x + y + p0
q = N // p
print(p)
print(q)

##############################################################
import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []

1.4.Franklin-Reiter攻击原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def franklinReiter(n,e1,e2,c1,c2,noise1,noise2):
    # 在模n的多项式环上定义变量x
    PR.<​x> = PolynomialRing(Zmod(n))
    
    # 构造两个多项式：
    # g1 = (x + noise1)^e1 - c1
    # g2 = (x + noise2)^e2 - c2
    # 当x = q时，这两个多项式都等于0
    g1 = (x + noise1)^e1 - c1
    g2 = (x + noise2)^e2 - c2

    def gcd(g1, g2):
        # 计算两个多项式的最大公因式
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic() # 返回首一多项式
    
    # 最大公因式应该是(x - q)，所以取常数项的相反数就得到q
    return -gcd(g1, g2)[0]

1.5.wiener攻击

使用前提：

原理：连分数如果e很大的话可以用；或者求类似下面的式子：

$$\frac{n_0}{n_1} = \frac{p_0 \cdot q + r_0}{p_1 \cdot q + r_1} = \frac{p_0 + \frac{r_0}{q}}{p_1 + \frac{r_1}{q}} \approx \frac{p_0}{p_1}$$

1.6. Common Private Exponent 攻击

如果用一个d私钥来构造r组公钥，而构造出来的模数的数量级接近，可以尝试

**$ed = 1 \mod n$ –> $ed = 1 + k L$其中我们假设$n_1 < n_2 < n_3 < \ldots < n_r < 2n_1$​。论文中说：如果$\frac{\ln d}{\ln n} = \delta$ 则若 $\delta < 0.5 - \frac{1}{2(r+1)} - \frac{\ln \delta}{\ln n_r}$ 那么所有的模数 $n$ 都可以在多项式的时间复杂度内被分解。

下面我们简单地说一下解决方法：假设$M = (\sqrt{n_5})^-$,$s = n - \phi(n)$。（注：本博客用上标+表示向上取整或无限从右趋近，用下标-表示向下取整或者无限从左趋近）。那么我们可以构造这样的式子：**

$d\sqrt{n_5} = d\sqrt{n_5}$

$e_1 d - n_1 k_1 = 1 - k_1 s_1$

$e_2 d - n_2 k_2 = 1 - k_2 s_2$

$\cdots\cdots$

$e_5d - n_5k_5 = 1 - k_5s_5$

然后我们可以构造以下的矩阵（以 r=5 为例）

​$$
\begin{bmatrix}
\sqrt{n_5} & e_1 & e_2 & e_3 & e_4 & e_5 \
0 & n_1 & 0 & 0 & 0 & 0 \
0 & 0 & n_2 & 0 & 0 & 0 \
0 & 0 & 0 & n_3 & 0 & 0 \
0 & 0 & 0 & 0 & n_4 & 0 \
0 & 0 & 0 & 0 & 0 & n_5
\end{bmatrix}
$$

根据上面的式子和上面的矩阵（假设矩阵记为 B），我们就可以构造

$\vec{v} = (d, k_1, k_2, k_3, k_4, k_5)$, $\quad$
$\vec{w} = (d\sqrt{n_6}, 1 - k_1s_1, 1 - k_2s_2, 1 - k_3s_3, 1 - k_4s_4, 1 - k_5s_5)$。

这样我们就满足 $\vec{v}B = \vec{w}$ 的构造了。

由此可见，在数据足够多的情况下，如果 $\ln d < 0.5 \ln n$，那么我们就有可能解出来的值。

总结：Wienerattack是 n 相同，d 改变，$\ln d < 0.5 \ln n$。而共私钥指数攻击是 d 相同，n 改变，$\ln d < 0.5 \ln n$。

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
# 例题：[VNCTF2021]factor
from Crypto.Util.number import *  
from gmpy2 import *  
from secret import flag  
  
def get_public_key(d):  
    while 1:  
        p, q = getPrime(512), getPrime(512)  
        N, phi, not_phi = p * q, (p - 1) * (q - 1), (p + 1) * (q + 1)  
        try:  
            e = inverse(d, not_phi)  
            assert gcd(e, phi) == 1  
            break  
        except:  
            pass  
    return (N, e)  
  
def encrypt(pubkey, m):  
    N, e = pubkey  
    c = pow(m, e, N)  
    return c  
  
m = bytes_to_long(flag)  
d = getPrime(300)  
pubkeys = [get_public_key(d), get_public_key(d)]  
cs = encrypt(pubkeys[0], m), encrypt(pubkeys[1], m)  
print(pubkeys)  
print(cs)  

#解题脚本
#Sagemath  
from Crypto.Util.number import *  
n1=5362254810180378444......  
e1=3762917428094791884......  
n2=1154833387078533235......  
e2=5794296112064899907......  
c1=5320050759114401782......  
c2=5186139432313258226......  
assert n2>n1      # 要把大的n放在后面  格要根据具体情况构造
M=int(sqrt(n2))  
B=[[0,0,0],[0,0,0],[0,0,0]]  
B[0][0],B[0][1],B[0][2]=M,e1,e2  
B[1][1],B[2][2]=n1,n2  
B=Matrix(ZZ,B)  
B=B.LLL()  
if(B[0][0]<​0):  
	B=-B  
d,t1,t2=B[0][0]//M,B[0][1],B[0][2]  
k1,k2=(d*e1-t1)//n1,(d*e2-t2)//n2  
k1.nbits(),k2.nbits()  
s1,s2=(t1-1)//k1-1,(t2-1)//k2-1  
var('x')  
F,G=x^2-s1*x+n1,x^2-s2*x+n2  
p1,q1=F.roots()[0][0],F.roots()[1][0]  
p2,q2=G.roots()[0][0],G.roots()[1][0]  
phi1,phi2=(p1-1)*(q1-1),(p2-1)*(q2-1)  
d1,d2=inverse(e1,ZZ(phi1)),inverse(e2,ZZ(phi2))  
print(long_to_bytes(pow(c2,d2,n2)),long_to_bytes(pow(c1,d1,n1)))  
#b'vnctf{7d47956b-bc55-4897-a550-cda0b221ce67} vnctf{7d47956b-bc55-4897-a550-cda0b221ce67}'

1.7.dp泄露

$$
\begin{aligned}
ed_p-1=k(p-1) \
ed_p-1+k \equiv 0 \mod p \
A+x \equiv 0 \mod p \
A+x \equiv 0 \mod n
\end{aligned}
$$

coppersimth算法解出k
$e < n^{\frac{1}{4}-\varepsilon}$，其中$\varepsilon$是误差

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 *

e  = 19999999999999999999999999999999999999999999999999999999999999999999999999997
n  = 7195
dp = 34961
c  = 3014
# e dp = 1 + kp - k
# e dp + k - 1 = 0 mod p

PR.<x> = PolynomialRing(Zmod(n))
f = e * dp -1 + x
f = f.monic()
k = f.small_roots(X=e,beta=0.4)[0]
print(k)
assert (int(e)*int(dp) + int(k) -1) % int(k) == 0

p = ZZ((e*dp+k-1)/k)
print(p)
q = n / p
L = (p-1)*(q-1)
d = Integer(e).inverse_mod(L)
m = Integer(pow(c, d, n))
flag = bytes.fromhex(m.hex())
print(flag.decode())

广义解法：
m自选
$$
\begin{aligned}
m \equiv c_m^{d_p} \mod p \
c_m^{d_p}-m=kp \
p=gcd(c_m^{d_p}-m,n)
\end{aligned}
$$

1
2
3
4
5
6
7
n  = 71955 
dp = 34961  
  
m = 1997  
c = pow(m, e, n)  
p = gcd(pow(c, dp, n) - m, n)  
assert n % p == 0

1.8.选择明密文攻击

注：这个方面的内容均来自CTFwiki

1.8.1. 选择明文攻击

**每次乘2，根据modN后是奇数还是偶数来判断
第 i 次时，xN/2^i ≤ P < xN+N/2^i

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
# 2018 Google CTF Perfect Secrecy
#!/usr/bin/env python3  
import sys  
import random  
  
from cryptography.hazmat.primitives import serialization  
from cryptography.hazmat.backends import default_backend  
  
  
def ReadPrivateKey(filename):  
  return serialization.load_pem_private_key(  
      open(filename, 'rb').read(), password=None, backend=default_backend())  
  
  
def RsaDecrypt(private_key, ciphertext):  
  assert (len(ciphertext) <=  
          (private_key.public_key().key_size // 8)), 'Ciphertext too large'  
  return pow(  
      int.from_bytes(ciphertext, 'big'),  
      private_key.private_numbers().d,  
      private_key.public_key().public_numbers().n)  
  
  
def Challenge(private_key, reader, writer):  
  try:  
    m0 = reader.read(1)  
    m1 = reader.read(1)  
    ciphertext = reader.read(private_key.public_key().key_size // 8)  
    dice = RsaDecrypt(private_key, ciphertext)  
    for rounds in range(100):  
      p = [m0, m1][dice & 1]  
      k = random.randint(0, 2)  
      c = (ord(p) + k) % 2  
      writer.write(bytes((c,)))  
    writer.flush()  
    return 0  
  
  except Exception as e:  
    return 1  
  
  
def main():  
  private_key = ReadPrivateKey(sys.argv[1])  
  return Challenge(private_key, sys.stdin.buffer, sys.stdout.buffer)  
  
  
if __name__ == '__main__':  
  sys.exit(main())

解密脚本：

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
import gmpy2  
from pwn import *  
encflag = open('./flag.txt').read()  
encflag = encflag.encode('hex')  
encflag = int(encflag, 16)  
#context.log_level = 'debug'  
m = ['\x00', '\x07']  
n = 0xDA53A899D5573091AF6CC9C9A9FC315F76402C8970BBB1986BFE8E29CED12D0ADF61B21D6C281CCBF2EFED79AA7DD23A2776B03503B1AF354E35BF58C91DB7D7C62F6B92C918C90B68859C77CAE9FDB314F82490A0D6B50C5DC85F5C92A6FDF19716AC8451EFE8BBDF488AE098A7C76ADD2599F2CA642073AFA20D143AF403D1  
e = 65537  
flag = ""  
  
def guessvalue(cnt):  
    if cnt[0] > cnt[1]:  
        return 0  
    return 1  
  
i = 0  
while True:  
    cnt = dict()  
    cnt[0] = cnt[1] = 0  
    p = remote('perfect-secrecy.ctfcompetition.com', 1337)  
    p.send(m[0])  
    p.send(m[1])  
    tmp = pow(2, i)  
    two_inv = gmpy2.invert(tmp, n)  
    two_cipher = gmpy2.powmod(two_inv, e, n)  
    tmp = encflag * two_cipher % n  
    tmp = hex(tmp)[2:].strip('L')  
    tmp = '0' * (256 - len(tmp)) + tmp  
    tmp = tmp.decode('hex')  
    assert (len(tmp) == 128)  
    p.send(tmp)  
    #print tmp  
    data = ""  
	    while (len(data) != 100):  这道题因为有随机数存在，计算奇偶的频率，就可以去影响
        data += p.recv()  
    for c in data:  
        cnt[u8(c)] += 1  
    p.close()  
    flag = str(guessvalue(cnt)) + flag  
    print i, flag  
    i += 1

1.8.2.RSA Byte Oracle

*假设 $C = P^e \mod N$ 第一次向服务器发送 $C * 256^e$ 会得到 $C256^e = (256P)^e \mod N$
服务器会返回 $256 * P \mod N$ 既 $256P - kn$
因此 $\mod 256$ 后会得到 $-kn \mod 256$
因为每个 -kn模256 的结果都不同，所以可以做个映射表，能让我们根据服务器的返回判断256P在哪个区间： $kN <= 256P <= (k+1)N$
根据这个原理，尝试$256^{i+1}P \mod N = 256^{i+1}P - kN$ 可以每次求一个字节，
进一步我们可以这么归纳，初始情况下

1
2
3
4
5
6
7
lb = 0  
ub = N
# 假设服务器返回了 b，那么
k = mab[b] 
interval = (ub-lb)/256 
lb = lb + interval * k 
ub = lb + interval

**下面是例题的一个解密脚本

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
from pwn import *  
import gmpy2  
from fractions import Fraction  
p = process('./rsa.py')  
#p = remote('18.179.251.168', 21700)  
#context.log_level = 'debug'  
p.recvuntil('Here is the flag!\n')  
flagcipher = int(p.recvuntil('\n', drop=True), 16)  
  
def long_to_hex(n):  
    s = hex(n)[2:].rstrip('L')  
    if len(s) % 2: s = '0' + s  
    return s  
  
def send(ch, num):  
    p.sendlineafter('cmd: ', ch)  
    p.sendlineafter('input: ', long_to_hex(num))  
    data = p.recvuntil('\n')  
    return int(data, 16)  
  
if __name__ == "__main__":  
    # get n  
    cipher2 = send('A', 2)  
    cipher4 = send('A', 4)  
    nset = []  
    nset.append(cipher2 * cipher2 - cipher4)  
  
    cipher3 = send('A', 3)  
    cipher9 = send('A', 9)  
    nset.append(cipher3 * cipher3 - cipher9)  
    cipher5 = send('A', 5)  
    cipher25 = send('A', 25)  
    nset.append(cipher5 * cipher5 - cipher25)  
    n = nset[0]  
    for item in nset:  
        n = gmpy2.gcd(item, n)  
  
    # get map between k and return byte  
    submap = {}  
    for i in range(0, 256):  
        submap[-n * i % 256] = i  
  
    # get cipher256  
    cipher256 = send('A', 256)  
  
    back = flagcipher  
  
    L = Fraction(0, 1)    # 用分数的形式，可以避免浮点数计算导致的误差累积
    R = Fraction(1, 1)  
    for i in range(128):  
        print i  
        flagcipher = flagcipher * cipher256 % n  
        b = send('B', flagcipher)  
        k = submap[b]          # 重点理解下面的代码
        L, R = L + (R - L) * Fraction(k, 256), L + (R - L) * Fraction(k + 1, 256)  
    low = int(L * n)  
    print long_to_hex(low - low % 256 + send('B', back)).decode('hex')

1.8.3.RSA parity oracle variant

目前看不懂，等补档：RSA 选择明密文攻击 - CTF Wiki

相关消息攻击
1
2
3
4
5
6
7
# [DASCTF 2024金秋十月｜秋意浓，战火燃，码上见真章]ez_RSA
c1 = pow(p+num1,e1,n2)  
c2 = pow(p+num2,e2,n2)
e1= 1630  
e2= 1866  
c1= 8857135……
c2= 445310306……
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
def HGCD(a, b):  # half-gcd
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x ^ m)
    b_top, b_bot = b.quo_rem(x ^ m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x ^ (m // 2))
    e_top, e_bot = e.quo_rem(x ^ (m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11

        
def GCD(a, b):
    # 第一步：尝试用普通的欧几里得除法做一步
    # q 是商，r 是余数，满足 a = q * b + r
    q, r = a.quo_rem(b)

    if r == 0:
        return b

    # 调用 HGCD（Half-GCD，半最大公因式算法）
    # HGCD 返回一个 2x2 矩阵的四个元素：R00, R01, R10, R11
    # 这个矩阵的作用是：用 a 和 b 的线性组合快速生成一对“中间多项式”(c, d)，
    # 使得 GCD(c, d) = GCD(a, b)，但 deg(d) < deg(a)/2（次数大幅降低）
    R00, R01, R10, R11 = HGCD(a, b)

    # 计算新的多项式对 (c, d)
    # 这对 (c, d) 是 (a, b) 经过多步欧几里得迭代后的结果，但通过分治一次得到
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b

    # 如果 d 为 0，说明 c 就是最大公因式（因为 GCD(c, 0) = c）
    # .monic() 将多项式变为“首一多项式”（最高次项系数为 1），这是标准形式
    if d == 0:
        return c.monic()

    # 对 (c, d) 再做一次普通的欧几里得除法（可选优化，减少递归深度）
    q, r = c.quo_rem(d)
    if r == 0:
        return d  # 如果整除，直接返回 d

    # 否则，递归计算 GCD(d, r)
    # 此时 r 的次数比 d 小，而 d 的次数已远小于原始 a，问题规模显著缩小
    return GCD(d, r)

num1 = 9234477875452540050907055680812175733211030585401847024956094109885380715661662501110233684131338074697772834745898452222070551975818702828913932925854661 
num2 = 6762350904214303306453303458299415835504119332199015610928593488027530960090511757877122152908652987754908309308543812479366000921214925642982325588758637
PR.< x > = PolynomialRing(Zmod(n2))
f = (x+num1)^e1 - c1
g = (x+num2)^e2 - c2
s = GCD(f,g)
b,a = int(s[0]),int(s[1])
print(a,b)
p = -b * inverse(a, n2) % n2
print(p)

1.9.多元coppersmith

Link:https://al3xei709.github.io/2024/01/29/Crypto-Papers-Read-Recurrent/

1.10.1.Boneh & Durfee攻击（小逆元攻击）

**成立条件：$d < N^0.292$
比维纳攻击广
e大概是4096bit，即n^4长度，猜测这里是用n^4来做为N求到对应的phi

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
from Crypto.Util.number import long_to_bytes
import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = []
    for i in range(m + 1):
        base = (N ** (m - i)) * (f ** i)
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base
            for var, s in zip(f.variables(), shifts):
                g *= var ** s
            G.append(g)

    # 收集所有单项式
    monomials = set()
    for g in G:
        monomials |= set(g.monomials())
    monomials = sorted(monomials)

    # 构造矩阵 B
    rows = []
    for g in G:
        rows.append([g.monomial_coefficient(m) for m in monomials])
    B = matrix(ZZ, rows)

    # 缩放
    factors = []
    for m in monomials:
        fac = 1
        for var, b in zip(f.variables(), bounds):
            fac *= b ** m.degree(var)
        factors.append(fac)

    B = B.change_ring(QQ)
    for col, fac in enumerate(factors):
        B.rescale_col(col, fac)

    # LLL
    B = B.dense_matrix().LLL()

    # 还原缩放
    for col, fac in enumerate(factors):
        B.rescale_col(col, 1/fac)

    # 构造多项式列表
    H = []
    for row in B:
        poly = sum([c * m for c, m in zip(row, monomials)])
        if poly != 0:
            H.append(poly)
            I = ideal(H)
            if I.dimension() == 0:
                roots = []
                for root in I.variety(ring=ZZ):
                    roots.append(tuple(R(root[str(v)]) for v in f.variables()))
                return roots

    return []

n = 
e = 
c = 

P = Zmod(ZZ(e))["k,s"]
k, s = P.gens()
f = 1 + k * (n - s)
rs = small_roots(f, (2**540, 2**1025), m=4, d=5)
print(rs)

k, s = map(int, rs[0])
phi = n - s
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m)))

1.9.2.多素数RSA攻击

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
102
103
104
from Crypto.Util.number import long_to_bytes
import itertools


# --- helper: simulate coefficients_monomials() ---
def coeffs_monos(polys):
    """
    polys: list of polynomials
    return: matrix of coefficients, list of monomials
    """
    # 收集所有 monomials
    monos = set()
    for p in polys:
        monos |= set(p.monomials())
    monos = sorted(monos)

    # 构造矩阵
    rows = []
    for p in polys:
        c = p.coefficients()
        m = p.monomials()
        d = dict(zip(m, c))
        row = [d.get(mon, 0) for mon in monos]
        rows.append(row)

    return matrix(ZZ, rows), monos

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    lc = f.coefficients().pop(0)
    f = f / lc
    f = f.change_ring(ZZ)

    G = []
    for i in range(m + 1):
        base = (N ** (m - i)) * (f ** i)
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base
            for var, shift in zip(f.variables(), shifts):
                g *= var ** shift
            G.append(g)

    # ---- 使用我们自制的兼容函数 ----
    B, monomials = coeffs_monos(G)
    monomials = vector(monomials)

    # scaling
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.LLL()
    B = matrix(QQ, B)

    for i, factor in enumerate(factors):
        B.rescale_col(i, QQ(1) / factor)

    H = []
    P_QQ = f.parent().change_ring(QQ)

    for row in B.rows():
        h = sum([coef * mon for coef, mon in zip(row, monomials)])
        h = P_QQ(h)
        H.append(h)

        I = ideal(H)
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []

n = 
e =  
c =  

P = PolynomialRing(Zmod(e), ["k", "s"])
k, s = P.gens()

f = 1 + k * (n - s)

rs = small_roots(f, (2**490, 2**2050), m=4, d=5)
#################### 注意这里要传入k和s的上界，特别要注意三个素数是s的上界
#################### s = n - phi
print(rs)

k, s = map(int, rs[0])
phi = n - s

d = pow(e, -1, phi)
m = pow(c, d, n)

print(long_to_bytes(int(m)))

1.10common prime RSA

Link:Common Prime RSA 笔记 | 独奏の小屋
g 是一个素数，且p和q也是素数，a和b是随机生成的数
$$
\begin{align}
p &= 2ga+1 \
q &= 2gb+1 \
h &= 2gab +a+b \
N &= p * q = 2gh + 1\
N - 1 &= 2gh
\end{align}
$$
定义 $\gamma$ 表示共因子g的相对于N的大小，即$g = N^\gamma$
考虑$g <= N^{1/2}$，故$0 <= \gamma <= 1/2$

具体的原理看blog

1.10.1. $\gamma$ 接近1/2

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
import random
try:
    gcd
except NameError:
    from math import gcd

def rho(N):
    f = lambda x: (pow(x, N-1, N) + 3) % N
    while True:
        # 加快入环速度
        t = random.randint(2, N)
        h = f(t)
        step_times = 0
        step_limit = 2
        while True:
            if not step_times < step_limit:
                step_times = 0
                step_limit *= 2
                t = h
                h = f(h)
            p = gcd(abs(int(t) - int(h)), N)
            if p == N:
                break
            elif p > 1:
                return (p, N // p)
            else:
                h = f(h)
                step_times += 1

print(rho(N))

1.10.2.已知a，b

构造方程 $4abg^2+2(a+b)g-N+1=0$

1
2
3
4
5
6
7
8
9
10
11
12
13
a = 1185431345934512
b = 1989628969125971
N = 54692260436051338814890781701826055707958209029414126894070449935683071253184867947357262267840171428710181955973010913204514025135188192484651672240708141692701667242130748316666406528479191422804307020656050201187035928715833163999813216597718706449260040885862566373392398826670863398295350419792842640631
P.<g> = ZZ[]
f = 4 * a * b * g ^ 2 + 2 * (a + b) * g - N + 1
g = f.roots()
if g:
    g = g[0][0]
    p = 2 * g * a + 1
    q = 2 * g * b + 1
    assert p * q == N
    print('p =',p)
    print('q =',q)

1.10.3.已知g

g > a+b

令 $M = (N-1)/(2g) = 2gab+a+b,c = a+b$得：
$M = 2gab + c$
$M = c \mod g = a+b$
后面就是简单的解方程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
g = 2056971706333850947354991471886113601423457483931388832864204860321308350537317091564919029078296379733989138742162694786565228112885684303
N = 67324909911911622626246005558967775211455024820506932698435813321567574468019013664789401988015894964099052816176029553245881317276340043887466584645914352982274378611180595397686920214079479901514703963131435008906250160656759300390805929849374653321934393399433471228218819498373221757779799476717494079667
M = (N - 1) // (2 * g)
c = M % g
P.<a> = ZZ[]
f = 2 * g * a ^ 2 - 2 * g * c * a + M - c
a = f.roots()
if a:
    a, b = a[0][0], a[1][0]
    p = 2 * g * a + 1
    q = 2 * g * b + 1
    assert p * q == N
    print('p =',p)
    print('q =',q)

g=a+b

$N=2g(2gab+a+b)+1$
$(N-1)/ (4g^2) = ab + 1/2$
带入$b=g-a$得：
$2a^2-2ga+(N-1)/2g^2-1=0$

1
2
3
4
5
6
7
8
9
10
11
12
13
g = 2855372645569408464444580237486670388029956719716115953907612135874419892154982850222965560661211729647325085879529571229774148545656169021
N = 159549169988238873893531105042878385551537587717347282632324748268846735710748763722602882823022008548774298858161130258369850715542192739582830583643642436399008902770027668038725347353393047833875066622910131525247842517372845617227325882916166114361718015983671803859502931814932543107911548450229250776542101141849788751722460468073974316977656001286989710480324512919121409123619799426221232443036698458643438020098037548757403
M = (N - 1) // (2 * g)
P.<a> = ZZ[]
f = 2 * a ^ 2 - 2 * g * a + (N - 1) // (2 * g ^ 2) - 1
a = f.roots()
if a:
    a, b = a[0][0], a[1][0]
    p = 2 * g * a + 1
    q = 2 * g * b + 1
    assert p * q == N
    print('p =',p)
    print('q =',q)

g < a+b

要求：$\gamma$ 约等于 1/4

最复杂的一个，十分推荐去看大佬的博客

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
#!/usr/bin/env python3
from sage.all import *
from sage.groups.generic import bsgs

N=54642322838521966106812419124141939188989640814860878861908076164639367595914512196689546261469345514255441116302800139668437203232194709285409075862419734007902906374266399946334745212375047784704524011282117381662325280446704897787659122983658402386409111680527237824015035597005313191262677046034069311159229487077629209355803968123085023774573470039717820771904932963580385259183454286138826580540970458295849974865118842313357636425032600607639797650353675780470249861726402474026943128529940611865467085977350731870140237435132883515585257875892835970695457915025407153187085139372317622088931196367733198938707
g=3040871967959800581351382295274005388082419270793259228509099272494086612979335548205806725469849481228948811909984262857772287453967175931780503026101
nbits = 2048
gamma = 0.23
# gamma = 500/(1024*2) #记得调gamma参数和nbits
cbits = ceil(nbits * (0.5 - 2 * gamma))

M = (N - 1) // (2 * g)
u = M // (2 * g)
v = M - 2 * g * u
GF = Zmod(N)
x = GF.random_element()
y = x ** (2 * g)
# c的范围大概与N^(0.5-2*gamma)很接近
lower = ZZ(2**(cbits-1))
upper = ZZ(2**(cbits+1))
c = bsgs(y, y ** u, (lower, upper))
ab = u - c
apb = v + 2 * g * c
P = PolynomialRing(ZZ, 'x')
x = P.gen()
f = x ** 2 - apb * x + ab
a = f.roots()
if a:
    a, b = a[0][0], a[1][0]
    p = 2 * g * a + 1
    q = 2 * g * b + 1
    assert p * q == N

    print(f'p =',p)
    print(f'q =',q)

1.10.3.分解N-1

当$\gamma$在0.1左右时，直接yafu分解$(N-1)/2$

1.10.4.Mumtaz-Luo攻击

看blog

2.题目

2.1.I know phi (XSWCTF初赛)

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 *  
with open("/home/ctf/flag", "r") as f:  
    flag = f.read().strip().encode()  
  
def create():  
    pl = []  
    for i in range(3):  
        pl.append(getPrime(1024))  
    return sorted(pl)  
  
def encrypt(pl, flag):  
    m = flag  
    p, q, r = pl[0], pl[1], pl[2]  
    n = p * q * r  
    phi = (p-1) * (q-1) * (r-1)  
    e = 65537  
    phi_2 = (p-1) * (q-1)  
    n2 = p * q  
    c = pow(bytes_to_long(m), e, n2)  
  
    print(f"n = {n}")  
    print(f"phi = {phi}")  
    print(f"c = {c}")  
  
if __name__ == '__main__':  
    pl = create()  
    encrypt(pl, flag)

**题目的描述很简单，有俩种解法，解法一用的是非平凡平方跟的原理，解法二是用coppersmith方法。
解法一：
原理图如下

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
from Cryptodome.Util.number import long_to_bytes  
  
n = 125474178
phi = 12547417 
c = 3284379  
import gmpy2  
from Crypto.Util.number import long_to_bytes  
import random  
import sys  
  
e = 65537  
  
def decompose_power_of_two(x):  
    """返回 (t, s) 使得 x = 2^t * s, s odd"""    t = 0  
    s = x  
    while s % 2 == 0:  
        t += 1  
        s //= 2  
    return t, s  
  
def find_nontrivial_k(phi_val, n_val, trials=256):  
    """随机尝试基 y，计算 y^(phi/2^i) 并返回第一个满足非平凡条件的 k"""    t, _ = decompose_power_of_two(phi_val)  
    for attempt in range(trials):  
        # 随机基（避免过大基）  
        y = random.randrange(2, min(1 << 30, n_val - 2))  
        # if gmpy2.gcd(y, n_val) != 1:  
        #     continue        for i in range(1, t + 1):  
            exp = phi_val // (2 ** i)  
            k = int(pow(y, exp, n_val))  
            if k != 1 and k != (n_val - 1):  
                return k  
    return None  
  
def try_extract_factor_from_k(n_val, k):  
    """对 k 同时尝试 gcd(n, k-1) 与 gcd(n, k+1)，返回所有在 (1,n) 之间的非平凡因子列表"""  
    res = []  
    for delta in (-1, 1):  
        g = int(gmpy2.gcd(n_val, k + delta))  
        if 1 < g < n_val:  
            res.append(g)  
    return list(set(res))  # 去重  
  
def recover_factors_and_decrypt():  
    print("[*] 开始在 n 上寻找非平凡平方根 k ...")  
    # 在 n 上找 k    k = find_nontrivial_k(phi, n, trials=1024)  
    if k is None:  
        print("[-] 未能在 n 上找到非平凡 k（尝试增大 trials）。")  
        return False  
    print("[+] 找到 k:", k)  
  
    # 同时尝试 k-1 与 k+1    cand_rs = try_extract_factor_from_k(n, k)  
    if not cand_rs:  
        print("[-] k-1/k+1 均未提取出 1<g<n 的因子，尝试继续寻找其他 k。")  
        return False  
  
    print("[*] 在 n 上从 k 得到的候选 r:", cand_rs)  
    # 遍历每个候选 r，验证 phi 可被 (r-1) 整除并继续分解 n2    for r in cand_rs:  
        if (r - 1) == 0:  
            continue  
        if phi % (r - 1) != 0:  
            print(f"[-] 候选 r={r} 不满足 phi % (r-1) == 0，跳过")  
            continue  
        n2 = n // r  
        phi2 = phi // (r - 1)  
        print(f"[+] 试用 r={r}，得到 n2={n2} 和 phi2={phi2}（假设 n2 = p*q）")  
  
        # 在 n2 上重复找 k2        k2 = find_nontrivial_k(phi2, n2, trials=1024)  
        if k2 is None:  
            print("[-] 在 n2 上未找到非平凡 k2，尝试下一个 r 候选")  
            continue  
        print("[+] 在 n2 上找到 k2:", k2)  
  
        cand_factors = try_extract_factor_from_k(n2, k2)  
        if not cand_factors:  
            print("[-] k2-1/k2+1 未提取到因子，尝试下一个 r 候选")  
            continue  
  
        for f in cand_factors:  
            p_candidate = int(f)  
            q_candidate = int(n2 // p_candidate)  
            # 验证三因子是否满足 n 与 phi 的关系  
            facs = sorted([int(r), p_candidate, q_candidate])  
            p, q, rr = facs[0], facs[1], facs[2]  
            if p * q * rr != n:  
                print(f"[-] (p,q,r) = ({p},{q},{rr}) 乘积 != n，跳过")  
                continue  
            if (p - 1) * (q - 1) * (rr - 1) != phi:  
                print(f"[-] (p-1)(q-1)(r-1) != phi（p={p}, q={q}, r={rr}），跳过")  
                continue  
  
            print("[+] 成功分解出 p,q,r：", p, q, rr)  
            # 用 p,q 解密  
            n2_recon = p * q  
            phi2_recon = (p - 1) * (q - 1)  
            try:  
                d = int(gmpy2.invert(e, phi2_recon))  
            except Exception as ex:  
                print("[-] 计算 d 失败：", ex)  
                continue  
            m_int = int(gmpy2.powmod(c, d, n2_recon))  
            try:  
                m_bytes = long_to_bytes(m_int)  
            except Exception as ex:  
                print("[-] long_to_bytes 失败：", ex)  
                continue  
            print("[+] 解密得到明文（bytes）：", m_bytes)  
            try:  
                print("[+] 解密明文（utf-8）：", m_bytes.decode())  
            except:  
                pass  
            return True  
    print("[-] 遍历完所有候选 r 仍未成功，建议增加 trials 或改为确定性 k（若有）重试")  
    return False  
  
if __name__ == "__main__":  
    ok = recover_factors_and_decrypt()  
    if not ok:  
        sys.exit(1)

**解法二：

1
2
3
4
5
6
7
8
9
10
11
# sage
n = 
phi = 
c = 
e = 65537
d = inverse(e,phi)
s = pow(c,d,n)
R.<x> = PolynomialRing(Zmod(n))
f = x-s
res = f.small_roots(x=2^2048,beta = 0.5, epsilon = 0.05)
print(long_to_bytes(int(res[0])).decode())

多项式RSA

欧拉函数

$F(x) = P(x) * Q(x)$其中，P(x)和Q(x)是不可约多项式，且设俩个多项式的度(deg)为p和q
则： $phi = (2^p - 1) * (2^q - 1)$

#crypto #RSA
RSA常用攻击
https://baymax-fools.github.io/2026/02/12/crypto/RSA常用攻击/
Author
Baymax
Posted on
February 12, 2026
Updated on
September 16, 2026
Licensed under