RSA

常用工具

  • 分解大素数

    factordbhttp://www.factordb.com / API: http://factordb.com/api?query=

    yafu($p,q$相差过大或过小yafu可分解成功)

    sagedivisors(n))(小素数)

    Pollard’s p−1python -m primefac -vs -m=p-1 xxxxxxx)(光滑数)

    Williams’s p+1python -m primefac -vs -m=p+1 xxxxxxx)(光滑数)

    cado-nfs

  • 在线sage环境:https://sagecell.sagemath.org/

  • Openssl

    解析加密密钥:

    openssl rsa -pubin -text -modulus -in pub.key

    生成解密密钥:

    python rsatool.py -f PEM -o key.key -p 1 -q 1 -e 1

    openssl rsautl -decrypt -inkey key.pem -in flag.enc -out flag

    openssl rsautl -decrypt -oaep -inkey key.pem -in flag.enc -out flag (OAEP方式)

    脚本生成解密密钥:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    # coding=utf-8
    import math
    import sys
    from Crypto.PublicKey import RSA
    from Crypto.Cipher import PKCS1_OAEP

    n =
    e =
    d =
    p =
    q =

    rsa_components = (n, e, d, p, q)
    myrsa = RSA.construct(rsa_components)

    private = open('private.pem', 'w')
    private.write(myrsa.exportKey())
    private.close()

    # rsakey = RSA.importKey(myrsa.exportKey())
    # rsakey = PKCS1_OAEP.new(rsakey)
    # decrypted = rsakey.decrypt(c_bytes)
  • 脚本集

常见类型

给p,q,e,c

1
2
3
4
5
6
7
8
9
10
11
12
import gmpy2 as gp
import binascii
p =
q =
e =
c =
n = p*q
phi = (p-1)*(q-1)
d = gp.invert(e,phi)
m = pow(c,d,n)
print(m)
print(bytes.fromhex(hex(m)[2:]))

给n,e,dp,c

$dp\equiv d \pmod {(p-1)}$

$\because dp\cdot e\equiv d\cdot e\equiv 1 \pmod {(p-1)}$

$\therefore dp\cdot e-1=k\cdot (p-1)$

$\therefore (dp\cdot e-1)\cdot d\cdot e=k’\cdot (p-1),\quad k’=k\cdot d\cdot e \\\Leftrightarrow d\cdot e=-k’\cdot (p-1)+dp\cdot e\cdot d\cdot e\equiv 1 \pmod{\varphi(n)}\\\Leftrightarrow -k’\cdot (p-1)+dp\cdot e\equiv 1\pmod{\varphi(n)}$

$\therefore k_{1}\cdot (p-1)+dp\cdot e-1=k_{2}\cdot (p-1)\cdot (q-1)\\\Leftrightarrow (p-1)\cdot (k_{2}\cdot (q-1)-k_{1})+1=dp\cdot e$

$\because dp<p-1\quad \therefore (k_{2}\cdot (q-1)-k_{1})\in (0, e)$

$\therefore$ 遍历 $(1, e)$,当同时满足 $(dp\cdot e-1)\bmod i==0$ 和 $n\bmod((dp\cdot e-1)//i+1)==0$ 时,$N$ 成功分解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import gmpy2 as gp

e =
n =
dp =
c =

for x in range(1, e):
if(e*dp%x==1):
p=(e*dp-1)//x+1
if(n%p!=0):
continue
q=n//p
phin=(p-1)*(q-1)
d=gp.invert(e, phin)
m=gp.powmod(c, d, n)
if(len(hex(m)[2:])%2==1):
continue
print('--------------')
print(m)
print(hex(m)[2:])
print(bytes.fromhex(hex(m)[2:]))
  • 变种1:给 $p,e,d_p,c,b$,其中 $n=p^bq$。

    Hensel lifting for Takagi’s scheme(p.189):

    Hensel_lifting_for_Takagi's_scheme

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    from Crypto.Util.number import *
    import gmpy2
    p =
    dp =
    c =
    b =
    e =
    mp1 = pow(c, dp, p)
    mp = pow(c, dp - 1, p)
    for i in range(1, b - 2):
    x = pow(c - pow(mp1, e), 1, p**(i + 1))
    y = pow(x * mp * (gmpy2.invert(e, p)), 1, p**(i + 1))
    mp1 = mp1 + y
    print(long_to_bytes(mp1))
  • 变种2:给 $n,e,dp_0,c,k$,其中 $dp_0$ 为 $dp$ 高 $(n\text{bits}-k)$ 位,即 $dp_0=dp>>k$。

    (Coppersmith攻击,已知dp高位攻击)

    $e\cdot dp \equiv e\cdot d\equiv 1 \pmod {(p-1)} \\\Leftrightarrow e \cdot dp=k(p-1)+1=kp-k+1 \\\Leftrightarrow e\cdot dp+k-1 \equiv 0 \pmod p$

    $\because dp<p-1$,$\therefore k<e$

    $\therefore e\cdot (dp_0<<k+x)+k-1 \equiv 0 \pmod p$

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    #Sage
    dp0 =
    e =
    n =

    F.<x> = PolynomialRing(Zmod(n))
    d = inverse_mod(e, n)
    for k in range(1, e):
    f = (secret << 200) + x + (k - 1) * d
    x0 = f.small_roots(X=2 ** (200 + 1), beta=0.44, epsilon=1/32)
    if len(x0) != 0:
    dp = x0[0] + (secret << 200)
    for i in range(2, e):
    p = (e * Integer(dp) - 1 + i) // i
    if n % p == 0:
    break
    if p < 0:
    continue
    else:
    print('k = ',k)
    print('p = ',p)
    print('dp = ',dp)
    break
  • 变种3:给 $n,e,dp,c$​​,其中 $dp$​​​ 很小,$e$ 很大。

    枚举 $dp$,因 $e\cdot dp \equiv 1 \pmod {(p-1)}$,又由费马小定理,对任意 $r$,有 $m^{e \cdot dp}\equiv m \pmod p$,即 $p \mid (m^{e \cdot dp}-m)$;

    又 $p \mid n$,很大概率 $p=\gcd(m^{e \cdot dp}-m,n)$。

  • 变种4:给 $N,e,c$,其中 $dp$ 过小。

    情形1:$q<N^{0.382}$

    参数 $\beta=\cfrac{q_{\text{bit}}}{N_{\text{bit}}}, \delta=\cfrac{dp_{\text{bit}}}{N_{\text{bit}}}$,满足 $3\beta < 1+\beta^2+2\delta$,可确定 $\beta$ 和 $\delta$ 的值。

    构造格子维度为 $n$,格子中模数 $N$ 的最大次幂为 $m$,应满足关系

    $\cfrac{m(m+1)}{2} + \cfrac{n(n-1)(2\delta+\beta)}{2}-(1-\beta)nm < 0$

    确定 $\beta$ 和 $\delta$ 之后,可枚举确定 $n$ 和 $m$ 的取值(最小值),$m=(1-\beta)n$ 是一个较优的取值。

    1
    2
    3
    4
    5
    beta = 
    delta =
    n = round((1-2*beta-2*delta)/((1-beta)^2-2*delta-beta),6)
    m = (1-beta)*n
    print(m,n)

    构造多项式,分解多项式为 $(ax+by)$ 项,其中 $a=k,b=dp$。

    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
    # 脚本1
    # Sage
    def getC(Scale):
    C = [[0 for __ in range(Scale)] for _ in range(Scale)]
    for i in range(Scale):
    for j in range(Scale):
    if i == j or j == 0:
    C[i][j] = 1
    else:
    C[i][j] = C[i-1][j-1] + C[i-1][j]
    return C

    def getMatrix(Scale, Mvalue, N, E, Del, Bet):
    M = [[0 for __ in range(Scale)] for _ in range(Scale)]
    C = getC(Scale)
    X, Y = int(pow(N,Del)*(Scale+1)//2), int(pow(N,(Del+Bet))*(Scale+1)//2)
    for i in range(Scale):
    for j in range(Scale):
    M[i][j] = N**max(Mvalue-i,0)*E**(max(i-j,0))*X**(Scale-1-j)*Y**j*C[i][j]*(-1)**j
    return M

    N =
    E =
    delta = 0.01
    beta = 0.37
    Scale = 35
    Mvalue = 22
    M = getMatrix(Scale,Mvalue,N,E,delta,beta)
    M = matrix(ZZ,M)
    A = M.LLL()[0]
    p = []
    X = int(pow(N,delta)*(Scale+1)//2)
    Y = int(pow(N,(delta+beta))*(Scale+1)//2)
    for i in range(Scale):
    p.append(A[i]//(X**(Scale-1-i)*Y**i))
    PR.<x,y> = PolynomialRing(ZZ)
    f = 0
    for i in range(Scale):
    f += p[i]*x^(Scale-1-i)*y^i
    print(f.factor())
    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
    # 脚本2
    # Sage
    N =
    e =

    n = 12
    beta = 0.36
    delta = 0.02

    X = int(N ** delta*(n+1)/2)
    Y = int(N ** (delta + beta)*(n+1)/2)

    def C(a,b):
    ret=1
    for i in range(b):
    ret *= (a-i)
    ret /= (b-i)
    return ret
    def get_Matrix(n,m):
    MM=[[0 for __ in range(n)] for _ in range(n)]
    for j in range(n):
    pN = max(0,m-j)
    for i in range(j+1):
    MM[j][i] = pow(N,pN)*pow(X,n-i-1)*pow(Y,i)*pow(e,j-i)*C(j,i)*pow(-1,i)
    MM = Matrix(ZZ,MM)
    return MM

    M = get_Matrix(n,n//2+1)
    L = M.LLL()[0]

    x,y = var('x'),var('y')
    f = 0
    for i in range(n):
    f += x**(n-i-1) * y**i * (L[i] // pow(X,n-i-1) // pow(Y,i))

    print(f.factor())

    参考:

    Cryptanalysis of Unbalanced RSA with Small CRT-Exponent

    https://hash-hash.github.io/2022/05/14/Unbalanced-RSA-with-Small-CRT-Exponent/#An-Approach-Modulo-e

    NSSCTF Round#3 - Secure_in_N

    情形2:$q<N^{0.468}$

    参数 $\beta=\cfrac{q_{\text{bit}}}{N_{\text{bit}}}, \delta=\cfrac{dp_{\text{bit}}}{N_{\text{bit}}},\alpha=\cfrac{e_{\text{bit}}}{N_{\text{bit}}}$,

    变量上界 $X=2N^{\alpha+\beta+\delta-1},Y=N^{\beta},Z=2N^{1-\beta}$ ,对于变量 $m$ 需充分大。

    $\tau=\cfrac{(1-\beta)^2-\delta}{2\beta(1-\beta)},\sigma=\cfrac{1-\beta-\delta}{2(1-\beta)},t=\tau m,s=\sigma m$

    整数域上有根 $(x,y,z)=(x_0,p,q)$。

    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
    from copy import deepcopy
    # https://www.iacr.org/archive/pkc2006/39580001/39580001.pdf
    # Author: ZM__________J, To1in
    N =
    e =
    alpha = log(e, N)
    beta =
    delta =
    P.<x,y,z>=PolynomialRing(ZZ)

    X = ceil(2 * N^(alpha + beta + delta - 1))
    Y = ceil(2 * N^beta)
    Z = ceil(2 * N^(1 - beta))

    def f(x,y):
    return x*(N-y)+N
    def trans(f):
    my_tuples = f.exponents(as_ETuples=False)
    g = 0
    for my_tuple in my_tuples:
    exponent = list(my_tuple)
    mon = x ^ exponent[0] * y ^ exponent[1] * z ^ exponent[2]
    tmp = f.monomial_coefficient(mon)

    my_minus = min(exponent[1], exponent[2])
    exponent[1] -= my_minus
    exponent[2] -= my_minus
    tmp *= N^my_minus
    tmp *= x ^ exponent[0] * y ^ exponent[1] * z ^ exponent[2]

    g += tmp
    return g

    m = 5 # need to be adjusted according to different situations
    tau = ((1 - beta)^2 - delta) / (2 * beta * (1 - beta))
    sigma = (1 - beta - delta) / (2 * (1 - beta))

    print(sigma * m)
    print(tau * m)

    s = ceil(sigma * m)
    t = ceil(tau * m)
    my_polynomials = []
    for i in range(m+1):
    for j in range(m-i+1):
    g_ij = trans(e^(m-i) * x^j * z^s * f(x, y)^i)
    my_polynomials.append(g_ij)

    for i in range(m+1):
    for j in range(1, t+1):
    h_ij = trans(e^(m-i) * y^j * z^s * f(x, y)^i)
    my_polynomials.append(h_ij)

    known_set = set()
    new_polynomials = []
    my_monomials = []

    # construct partial order
    while len(my_polynomials) > 0:
    for i in range(len(my_polynomials)):
    f = my_polynomials[i]
    current_monomial_set = set(x^tx * y^ty * z^tz for tx, ty, tz in f.exponents(as_ETuples=False))
    delta_set = current_monomial_set - known_set
    if len(delta_set) == 1:
    new_monomial = list(delta_set)[0]
    my_monomials.append(new_monomial)
    known_set |= current_monomial_set
    new_polynomials.append(f)
    my_polynomials.pop(i)
    break
    else:
    raise Exception('GG')

    my_polynomials = deepcopy(new_polynomials)

    nrows = len(my_polynomials)
    ncols = len(my_monomials)
    L = [[0 for j in range(ncols)] for i in range(nrows)]

    for i in range(nrows):
    g_scale = my_polynomials[i](X * x, Y * y, Z * z)
    for j in range(ncols):
    L[i][j] = g_scale.monomial_coefficient(my_monomials[j])

    # remove N^j
    for i in range(nrows):
    Lii = L[i][i]
    N_Power = 1
    while (Lii % N == 0):
    N_Power *= N
    Lii //= N
    L[i][i] = Lii
    for j in range(ncols):
    if (j != i):
    L[i][j] = (L[i][j] * inverse_mod(N_Power, e^m))

    L = Matrix(ZZ, L)
    nrows = L.nrows()

    L = L.LLL()
    # Recover poly
    reduced_polynomials = []
    for i in range(nrows):
    g_l = 0
    for j in range(ncols):
    g_l += L[i][j] // my_monomials[j](X, Y, Z) * my_monomials[j]
    reduced_polynomials.append(g_l)

    # eliminate z
    my_ideal_list = [y * z - N] + reduced_polynomials

    # Variety
    my_ideal_list = [Hi.change_ring(QQ) for Hi in my_ideal_list]
    for i in range(len(my_ideal_list),3,-1):
    print(i)
    V = Ideal(my_ideal_list[:i]).variety(ring=ZZ)
    print(V)

    参考:

    New Attacks on RSA with Small Secret CRT-Exponents

    NCTF 2022 - dp_promax

给p,q,dp,dq,c

$dp=d \bmod (p-1)$,$dq=d \bmod (q-1)$

$\because d=k_{1}(p-1)+dp=k_{2}(q-1)+dq\\\Leftrightarrow k_{1}(p-1)=(dq-dp)+k_{2}(q-1)\\\Leftrightarrow k_{1}\frac{p-1}{\gcd(p-1,q-1)}=\frac{dq-dp}{\gcd(p-1,q-1)}+k_{2}\frac{q-1}{\gcd(p-1,q-1)}\\\Rightarrow k_{1}\frac{p-1}{\gcd(p-1,q-1)}\equiv\frac{dq-dp}{\gcd(p-1,q-1)} \pmod {\frac{q-1}{\gcd(p-1,q-1)}}\\\Leftrightarrow k_{1}\equiv \text{inv}(\frac{p-1}{\gcd(p-1,q-1)},\frac{q-1}{\gcd(p-1,q-1)})\cdot \frac{dq-dp}{\gcd(p-1,q-1)} \pmod {\frac{q-1}{\gcd(p-1,q-1)}}$

将 $k_{1}=k_{3}\frac{q-1}{\gcd(p-1,q-1)}+\text{inv}(\frac{p-1}{\gcd(p-1,q-1)},\frac{q-1}{\gcd(p-1,q-1)})\cdot \frac{dq-dp}{\gcd(p-1,q-1)}$

代入 $d=k_{1}(p-1)+dp$

$d=k_{3}\frac{(p-1)(q-1)}{\gcd(p-1,q-1)}+\text{inv}(\frac{p-1}{\gcd(p-1,q-1)},\frac{q-1}{\gcd(p-1,q-1)})\cdot \frac{(dq-dp)(p-1)}{\gcd(p-1,q-1)}+dp\\\Rightarrow d\equiv \text{inv}(\frac{p-1}{\gcd(p-1,q-1)},\frac{q-1}{\gcd(p-1,q-1)})\cdot \frac{(dq-dp)(p-1)}{\gcd(p-1,q-1)}+dp \pmod{\frac{(p-1)(q-1)}{\gcd(p-1,q-1)}}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2 as gp

p =
q =
dp =
dq =
c =

n = p*q
phin = (p-1)*(q-1)
dd = gp.gcd(p-1, q-1)
d=(dp-dq)//dd * gp.invert((q-1)//dd, (p-1)//dd) * (q-1) +dq
print(d)

m = gp.powmod(c, d, n)
print('-------------------')
print(m)
print(hex(m)[2:])
print(bytes.fromhex(hex(m)[2:]))

给e,d,n

计算 $k=ed-1$,选择一个随机数 $g,g \in (1,N)$。

$k$ 为偶数,故 $k=2^tr$,其中 $r$ 为奇数且 $t \ge 1$,然后计算 $x = g^{\frac{k}{2}},g^{\frac{k}{4}},\cdots,g^{\frac{k}{2^t}} \pmod N$ 直到 $x \gt 1$ 且 $y=\gcd(x-1,N) \gt 1$。

如果这样的 $y$ 存在,则其中的因子 $p=y,q=\cfrac{N}{y}$;如这样的 $y$ 不存在,则重新生成随机数 $g$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import random
import gmpy2

def divide_pq(e, d, n):
k = e*d - 1
while True:
g = random.randint(2, n-1)
t = k
while True:
if t % 2 != 0:
break
t //= 2
x = pow(g, t, n)
if x > 1 and gmpy2.gcd(x-1, n) > 1:
p = gmpy2.gcd(x-1, n)
return (p, n//p)

p, q = divide_pq(e, d, n)
print(f'p = {p}')
print(f'q = {q}')
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
import random
import gmpy2

def factor_with_kphi(n, kphi):
t = 0
while kphi % 2 == 0:
kphi >>= 1
t += 1
for i in range(1, 101):
g = random.randint(0, n)
y = pow(g, kphi, n)
if y == 1 or y == n - 1:
continue
else:
for j in range(1, t):
x = pow(y, 2, n)
if x == 1:
p = gcd(n, y-1)
q = n//p
return p, q
elif x == n - 1:
continue
y = x
x = pow(y, 2, n)
if x == 1:
p = gcd(n, y-1)
q = n//p
return p, q

低解密指数攻击/低私钥指数攻击(e长度较大,d小,Wiener Attack)

适用情况:已知 $N,e$,且 $e$ 过大或过小。

$\varphi(n) = (p-1)(q-1)=pq - (p + q) + 1=N - (p + q) + 1$

$\because p, q$ 非常大,$\therefore\,pq\gg p+q$, $\therefore\varphi(n)\approx N$

$\because ed\equiv1\,mod\,\varphi(n)$,$\therefore ed-1=k\varphi(n)$,这个式子两边同除 $d\varphi(n)$ 可得:

$\cfrac{e}{\varphi(n)}-\cfrac{k}{d}=\cfrac{1}{d\varphi(n)}$

$\because \varphi(n)\approx N$,$\therefore \cfrac{e}{N}-\cfrac{k}{d}=\cfrac{1}{d\varphi(n)}$,同样 $d\varphi(n)$ 是一个很大的数,所以 $\cfrac{e}{N}$ 略大于 $\cfrac{k}{d}$

因为 $e$ 和 $N$ 是知道的,所以计算出 $\cfrac{e}{N}$ 后,比它略小的 $\cfrac{k}{d}$ ,可以通过计算 $\cfrac{e}{N}$ 的连分数展开,依次算出这个分数每一个渐进分数,由于 $\cfrac{e}{N}$ 略大于 $\cfrac{k}{d}$,Wiener 证明了,该攻击能精确的覆盖 $\cfrac{k}{d}$。

在 $e$ 过大或过小的情况下,可使用算法从 $e$ 中快速推断出 $d$ 的值。可以解决 $q<p<2q,d<\cfrac{1}{3}N^{\frac{1}{4}}$ 的问题。

RSAWienerHacker工具:https://github.com/pablocelayes/rsa-wiener-attack

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
#脚本1
#Sage
def factor_rsa_wiener(N, e):
N = Integer(N)
e = Integer(e)
cf = (e / N).continued_fraction().convergents()
for f in cf:
k = f.numer()
d = f.denom()
if k == 0:
continue
phi_N = ((e * d) - 1) / k
b = -(N - phi_N + 1)
dis = b ^ 2 - 4 * N
if dis.sign() == 1:
dis_sqrt = sqrt(dis)
p = (-b + dis_sqrt) / 2
q = (-b - dis_sqrt) / 2
if p.is_integer() and q.is_integer() and (p * q) % N == 0:
p = p % N
q = q % N
if p > q:
return (p, q)
else:
return (q, 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
#脚本2
#Sage
def rational_to_contfrac(x,y):
# Converts a rational x/y fraction into a list of partial quotients [a0, ..., an]
a = x // y
pquotients = [a]
while a * y != x:
x, y = y, x - a * y
a = x // y
pquotients.append(a)
return pquotients

def convergents_from_contfrac(frac):
# computes the list of convergents using the list of partial quotients
convs = [];
for i in range(len(frac)): convs.append(contfrac_to_rational(frac[0 : i]))
return convs

def contfrac_to_rational (frac):
# Converts a finite continued fraction [a0, ..., an] to an x/y rational.
if len(frac) == 0: return (0,1)
num = frac[-1]
denom = 1
for _ in range(-2, -len(frac) - 1, -1): num, denom = frac[_] * num + denom, num
return (num, denom)

n =
e =
c =

def egcd(a, b):
if a == 0: return (b, 0, 1)
g, x, y = egcd(b % a, a)
return (g, y - (b // a) * x, x)

def mod_inv(a, m):
g, x, _ = egcd(a, m)
return (x + m) % m

def isqrt(n):
x = n
y = (x + 1) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x

def crack_rsa(e, n):
frac = rational_to_contfrac(e, n)
convergents = convergents_from_contfrac(frac)

for (k, d) in convergents:
if k != 0 and (e * d - 1) % k == 0:
phi = (e * d - 1) // k
s = n - phi + 1
# check if x*x - s*x + n = 0 has integer roots
D = s * s - 4 * n
if D >= 0:
sq = isqrt(D)
if sq * sq == D and (s + sq) % 2 == 0: return d

d = crack_rsa(e, n)
m = hex(pow(c, d, n))[2:]
print(bytes.fromhex(m))
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
#脚本3
from Crypto.Util.number import long_to_bytes
e =
n =
c =

#将分数x/y展开为连分数的形式
def transform(x,y):
arr=[]
while y:
arr+=[x//y]
x,y=y,x%y
return arr

#求解渐进分数
def sub_fraction(k):
x=0
y=1
for i in k[::-1]:
x,y=y,x+i*y
return (y,x)
data=transform(e,n)

for x in range(1,len(data)+1):
data1=data[:x]
d = sub_fraction(data1)[1]
m = pow(c,d,n)
flag = long_to_bytes(m)
if b'flag{' in flag:
print(flag)
break
  • 变种1:$\cfrac{N_1}{N_2}<\cfrac{q_1}{q_2}<1$

    参考:2020年羊城杯 - RRRRRRRSA

    Paper: https://eprint.iacr.org/2015/399.pdf

    尝试对 $\cfrac{N_1}{N_2}$ 进行连分数展开并求其各项渐进分数,记为 $\cfrac{t_i}{s_i}$ 并验证 $N_1\% {t_k}==0$ 是否成立,如果成立,那么 $q_1=t_k,q_2=s_k$。

    连分数逼近

    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
    def transform(x,y):	   #使用辗转相除将分数x/y转为连分数的形式
    res=[]
    while y:
    res.append(x//y)
    x,y=y,x%y
    return res

    def continued_fraction(sub_res):
    numerator,denominator=1,0
    for i in sub_res[::-1]: #从sublist的后面往前循环
    denominator,numerator=numerator,i*numerator+denominator
    return denominator,numerator #得到渐进分数的分母和分子,并返回

    #求解每个渐进分数
    def sub_fraction(x,y):
    res=transform(x,y)
    res=list(map(continued_fraction,(res[0:i] for i in range(1,len(res))))) #将连分数的结果逐一截取以求渐进分数
    return res

    def wienerAttack(n1,n2):
    for (q2,q1) in sub_fraction(n1,n2): #用一个for循环来注意试探n1/n2的连续函数的渐进分数,直到找到一个满足条件的渐进分数
    if q1==0: #可能会出现连分数的第一个为0的情况,排除
    continue
    if n1%q1==0 and q1!=1: #成立条件
    return (q1,q2)
    print("该方法不适用")

    N1=
    N2=
    print(wienerAttack(N1,N2))
  • 变种2:$Ax \equiv y \pmod P$,即 $Ax-kP=y$ 或 $Ax+kP=y$

    Wiener’s

    $\Big\vert \cfrac{A}{P}-\cfrac{k}{x}\Big\vert \le \cfrac{1}{2x^2}$,连分数方法,用 $\cfrac{A}{P}$ 逼近求出 $\cfrac{k}{x}$,进而解出 $y$。

    Lattice

    $(x,k)\begin{bmatrix}1&A\\0&P\ \end{bmatrix} = (x,y)$,记为 $vM=w$,$w$ 有很大概率为 $M$ 里的最短向量,使用LLL算法求出最短向量,即解出 $w’=(x,y)$。

    参考:Wiener’s v.s Lattices —— Ax≡y(mod P)的方程解法笔记

  • 变种3:$N=p^2q$,$q \lt p \lt2q$,$d=N^\beta$

    可用 $\cfrac{e}{N-(2N^\frac{2}{3}-N^\frac{1}{3})}$ 逼近 $\cfrac{k}{d}$。

    参考:New Attacks on RSA with Modulus N = p^2q Using Continued Fractions

低加密指数广播攻击(Hastad攻击)

适用情况: $n,c$ 不同,$m,e$ 相同。一般会是 $e=k$,然后给 $k$ 组数据。

如果一个用户使用同一个加密指数 e 加密了同一个密文,并发送给了其他 e 个用户。那么就会产生广播攻击。这一攻击由 Håstad 提出。

使用不同的模数 $n$,相同的公钥指数 $e$ 加密相同的信息,就会得到多个 $m^e \equiv c_i \pmod {n_i}$,将 $m^e$ 视为一个整体 $M$,这就是典型的中国剩余定理适用情况。容易求得 $m^e$ 的值,当 $e$ 较小时直接开 $e$ 方即可,可使用gmpy2.iroot(M,e) 方法。

更一般情况($k$ 组数据的 $N$ 不同)见15。

1
2
3
4
5
6
7
8
9
#sage
def chinese_remainder(modulus, remainders):
Sum = 0
prod = reduce(lambda a, b: a*b, modulus)
for m_i, r_i in zip(modulus, remainders):
p = prod // m_i
Sum += r_i * (inverse_mod(p,m_i)*p)
return Sum % prod
chinese_remainder([3,5,7],[2,3,2]) #23
1
2
#sage
crt([2,3,2],[3,5,7])

共模攻击(n,m相同,c,e不同)

当$n$不变的情况下,知道$n,e_1,e_2,c_1,c_2$可以在不知道$d_1,d_2$的情况下,解出$m$。

首先假设$e_1,e_2$互质,

即 $\gcd(e_1,e_2)=1$

此时则有 $e_1s_1+e_2s_2 = 1$

式中,$s_1,s_2$皆为整数,但是一正一负。

通过扩展欧几里德算法,我们可以得到该式子的一组解$(s_1,s_2)$,假设$s_1$为正数,$s_2$为负数。

因为 $c_1 = m^{e_1}\bmod n, c_2 = m^{e_2}\bmod n$

所以 $(c_1^{s_1}c_2^{s_2})\bmod n = ((m^{e_1}\bmod n)^{s_1}(m^{e_2}\bmod n)^{s_2})\bmod n$

根据模运算性质,可以化简为 $(c_1^{s_1}c_2^{s_2})\bmod n = ((m^{e_1})^{s_1}(m^{e_2})^{s_2})\bmod n$

即 $(c_1^{s_1}c_2^{s_2})\bmod n = (m^{e_1s_1+e_2s_2})\bmod n$

又前面提到 $e_1s_1+e_2s_2 = 1$

所以 $(c_1^{s_1}c_2^{s_2})\bmod n = m\bmod n$

即 $c_1^{s_1}c_2^{s_2}= m$

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
import gmpy2 as gp
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

n =
c1 =
c2 =
e1 =
e2 =
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
if s1<0:
s1 = - s1
c1 = gp.invert(c1, n)
elif s2<0:
s2 = - s2
c2 = gp.invert(c2, n)

m = pow(c1,s1,n)*pow(c2,s2,n) % n
print(hex(m)[2:])
print(bytes.fromhex(hex(m)[2:]))

e,m相同,多个n中存在两个n有GCD(模不互素)

适用情况:存在两个或更多模数 ,且 $\gcd(n_1,n_2)\ne 1$ 。

多个模数 $n$ 共用质数,则可以很容易利用欧几里得算法求得他们的质因数之一 $\gcd(n_1,n_2)$,然后这个最大公约数可用于分解模数分别得到对应的 $p$ 和 $q$,即可进行解密。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gmpy2 as gp

n=[]
for i in n:
for j in n:
if (i<>j):
pub_p=gp.gcdext(i,j)
if (pub_p[0]<>1)&(i>j):
print(i)
print(j)
print(pub_p[0])
a=i,p=pub_p[0]
q=a//p
p =
q =
e =
c =
n = p*q
phi = (p-1) * (q-1)
d = gp.invert(e, phi)
m = pow(c, d, n)
print(hex(m)[2:])
print(bytes.fromhex(hex(m)[2:]))

Rabin加密

适用情况:$e=2$ 。

一般先通过其他方法分解得到 $p,q$,然后解密。

函数返回四个数,这其中只有一个是我们想要的明文,需要通过其他方式验证。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gmpy2

def rabin_decrypt(c, p, q, e=2):
n = p * q
mp = pow(c, (p + 1) // 4, p)
mq = pow(c, (q + 1) // 4, q)
yp = gmpy2.invert(p, q)
yq = gmpy2.invert(q, p)
r = (yp * p * mq + yq * q * mp) % n
rr = n - r
s = (yp * p * mq - yq * q * mp) % n
ss = n - s
return (r, rr, s, ss)

c =
p =
q =
m = rabin_decrypt(c,p,q)
for i in range(4):
try:
print(bytes.fromhex(hex(m[i])[2:]))
except:
pass

Boneh and Durfee attack

$e$ 非常大接近于$N$,即 $d$ 较小时。与低解密指数攻击类似,比低解密指数攻击(Wiener Attack)更强,可以解决$\cfrac{1}{3}N^{\frac{1}{4}} \leq d \leq N^{0.292}$的问题。

$\because ed=k \varphi +1$

$\therefore k \varphi+1 \equiv 0 \pmod e \Rightarrow k(N+1-p-q)+1 \equiv 0 \pmod e \Rightarrow 2k(\frac{N+1}{2}+\frac{-p-q}{2}) \equiv 0 \pmod e$

设 $A=\frac{N+1}{2},y=\frac{-p-q}{2},x=2k$,有 $f(k,y)=1+x\cdot(A+y)$

如果在模 $e$ 下解得该方程的根 $x,y$,由 $ed=1+x\cdot(A+y)$ 可以得到 $d$。

参考 RSA-and-LLL-attacks

  • 变种1:$e$ 很大,$dp$ 很小,且 $d>2N^{\beta}$。

    May’s Attack

    假设 $e<\varphi(N),q \le N^{\beta},\beta \le \frac{1}{2}$,因 $ed_p \equiv 1 \pmod {p-1}$,有 $ed_p=1+k(p-1)$,

    对于 $k \in \mathbb{N}$,有 $ed_p=(k-1)(p-1)+p$,即 $ed_pq=(k-1)(N-q)+N$。

    设 $x,y$ 为参数,则多项式 $f(x,y)=x(N-y)+N$ 在模 $e$ 下存在根 $(x_0,y_0)=(k-1,q)$,用coppersmith attack可解。

光滑数

p-1 光滑

Pollard’s p-1分解算法。

如果一个整数的所有素因子都不大于 $B$,我们称这个数为 $B$-Smooth 数。

设 $p-1$ 是 $B$-Smooth 的,可设 $p-1=p_1p_2 \cdots p_n(\forall 1 \leq i \leq n,p_i \leq B)$,

若 $p_1,p_2, \cdots ,p_n$ 两两不同,则 $p_1p_2 \cdots p_n \mid B! \Rightarrow (p-1) \mid B! \Rightarrow B!=k(p-1)$。

因此 $a^{B!} \equiv a^{k(p-1)} \equiv 1 \pmod p$,假设 $N=pq$,计算 $\gcd(a^{B!}-1,N)$,只要结果大于 $0$ 小于 $N$,那么结果就为 $p$。

1
2
3
4
5
6
7
8
9
10
11
12
13
from gmpy2 import *
a = 2
k = 2
N =
while True:
a = powmod(a, k, N)
res = gcd(a-1, N)
if res != 1 and res != N:
q = N // res
print("p =",res)
print("q =",q)
break
k += 1
p+1 光滑

William’s p+1分解算法。

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def mlucas(v, a, n):
""" Helper function for williams_pp1(). Multiplies along a Lucas sequence modulo n. """
v1, v2 = v, (v**2 - 2) % n
for bit in bin(a)[3:]:
v1, v2 = ((v1**2 - 2) % n, (v1*v2 - v) % n) if bit == "0" else ((v1*v2 - v) % n, (v2**2 - 2) % n)
return v1

for v in count(1):
for p in primegen():
e = ilog(isqrt(n), p)
if e == 0:
break
for _ in xrange(e):
v = mlucas(v, p, n)
g = gcd(v-2, n)
if 1 < g < n:
return g # g|n
if g == n:
break

Coppersmith定理指出在一个 $e$ 阶的 $\bmod n$ 多项式 $f(x)$ 中,如果有一个根小于 $n^{\frac{1}{e}}$,就可以运用一个 $O(\log n)$ 的算法求出这些根。

Coppersmith攻击(已知p的高位攻击)

知道 $p$ 的高位为 $p$ 的位数的约$\frac12$时即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#Sage
n =
p4 = #p去0的剩余位
pbits = 1024
kbits = pbits - p4.nbits()
print(p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
if roots:
p = p4 + int(roots[0])
q = n//p
print(f'n: {n}')
print(f'p: {p}')
print(f'q: {q}')

Coppersmith攻击(已知m的高位攻击)

这里我们假设我们首先加密了消息 $m$,如下

$C\equiv m^e \bmod N$

并且我们假设我们知道消息 $m$ 的很大的一部分 $m_0$,即 $m=m_0+x$,但是我们不知道 $x$。那么我们就有可能通过该方法进行恢复消息。这里我们不知道的 $x$ 其实就是多项式的根,需要满足 Coppersmith 的约束。

可以参考 https://github.com/mimoo/RSA-and-LLL-attacks

$e$ 足够小,且部分明文泄露时,可以采用Coppersmith单变量模等式的攻击,如下:

$c=m^{e}\bmod n=(mbar+x_{0})^{e}\bmod n$,其中 $mbar = (m >> k\text{bits}) << k\text{bits}$

当 $\vert x_{0}\vert\leq N^{\frac{1}{e}}$ 时,可以在 $\log N$ 和 $e$ 的多项式时间内求出 $x_0$。

1
2
3
4
5
6
7
8
9
10
11
12
13
#Sage
n =
e =
c =
mbar =
kbits =
beta = 1
nbits = n.nbits()
print("upper {} bits of {} bits is given".format(nbits - kbits, nbits))
PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)^e - c
x0 = f.small_roots(X=2^kbits, beta=1)[0] # find root < 2^kbits with factor = n
print("m:", mbar + x0)

Coppersmith攻击(已知d的低位攻击)

如果知道 $d$ 的低位,低位约为 $n$ 的位数的 $\frac14$ ($\frac{n.n\text{bits}()}{4}$)就可以恢复 $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
#Sage
def partial_p(p0, kbits, n):
PR.<x> = PolynomialRing(Zmod(n))
nbits = n.nbits()
f = 2^kbits*x + p0
f = f.monic()
roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.4) # find root < 2^(nbits//2-kbits) with factor >= n^0.4
if roots:
x0 = roots[0]
p = gcd(2^kbits*x0 + p0, n)
return ZZ(p)
def find_p(d0, kbits, e, n):
X = var('X')
for k in range(1, e+1):
results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
for x in results:
p0 = ZZ(x[0])
p = partial_p(p0, kbits, n)
if p and p != 1:
return p
if __name__ == '__main__':
n =
e =
c =
d0 =
beta = 0.5
nbits = n.nbits()
kbits = d0.nbits()
print("lower %d bits (of %d bits) is given" % (kbits, nbits))
p = int(find_p(d0, kbits, e, n))
print("found p: %d" % p)
q = n//int(p)
print("d:", inverse_mod(e, (p-1)*(q-1)))
  • 变种1:$n=p\cdot q\cdot r$,已知 $n,p,d=\text{inv}(e,\varphi(n)),e,c$

    $k(p-1)\rightarrow k’,qr\rightarrow n’,q+r\rightarrow s$

    $ed_{0}\equiv 1+k’(n’-s+1) \pmod {2^{d_{0}.n\text{bits}()}}\quad (1)$

    $q^{2}-sq+n’\equiv 0 \pmod {2^{d_{0}.n\text{bits}()}}\quad (2)$

    联立可得,$(ed_{0}-1-k’n’-k’)q+k’q^{2}+k’n’\equiv 0 \pmod {2^{d_{0}.n\text{bits}()}}$

    即求解同余方程可得 $q$ 的低 $size(d0)$ 位,本来是个partial d的coppersmith问题,但因为step1求解同余方程后得到的 $q$ 已是完整的 $q$,所以无需后续的coppersmith。

    参考:Dragon CTF 2019 - RSA Chained

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    #Sage
    def find_p(d0, kbits, e, n, p):
    X = var('X')
    for k in range(1, e + 1):
    k_dot = k * (p - 1)
    results = solve_mod([e * d0 * X - k_dot * X * (n - X + 1) + k_dot * n == X], 2^kbits)
    for x in results:
    q = ZZ(x[0])
    if n % q == 0:
    return q
    return None

    n = ... # q * r
    p =
    c =
    d0 =
    e =
    kbits = d0.nbits()
    q = find_p(d0, kbits, e, n, p)
    phi = (p - 1) * (q - 1) * (n // q - 1)
    d = inverse_mod(e, phi)
    print(bytes.fromhex(hex(pow(c, d, p * n))[2:]))

Coppersmith攻击(已知N一个因子的高位,部分p)

当我们知道一个公钥中模数 $N$ 的一个因子的较高位时,我们就有一定几率来分解 $N$。

参考 https://github.com/mimoo/RSA-and-LLL-attacks

关注下面的代码:

1
2
3
4
5
6
7
beta = 0.5
dd = f.degree()
epsilon = beta / 7
mm = ceil(beta**2 / (dd * epsilon))
tt = floor(dd * mm * ((1/beta) - 1))
XX = ceil(N**((beta**2/dd) - epsilon)) + 1000000000000000000000000000000000
roots = coppersmith_howgrave_univariate(f, N, beta, mm, tt, XX)

其中,

  • 必须满足 $q\ge N^{beta}$,所以这里给出了 $beta=0.5$,显然两个因数中必然有一个是大于的。
  • XX 是 $f(x)=q′+x$ 在模 $q$ 意义下的根的上界,自然我们可以选择调整它,这里其实也表明了我们已知的 $q′$ 与因数 $q$ 之间可能的差距。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#Sage
n =
e =
c =
pbar =
kbits =
print("upper %d bits (of %d bits) is given" % (pbar.nbits()-kbits, pbar.nbits()))
PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
x0 = f.small_roots(X=2^kbits, beta=0.4)[0] # find root < 2^kbits with factor >= n^0.4
p = x0 + pbar
print("p:", p)
q = n // int(p)
d = inverse_mod(e, (p-1)*(q-1))
print("m:", pow(c, d, n))

注:

sage的small_root传参X不能过大,需自行判断阈值并调整(如果X过大,即使存在X内的解,也无法求出);

比如 $p$ 的低位泄露时因为不确定缺失高位的具体比特数,所以要在 $2^{\frac{n.n\text{bits}()}{2}−k\text{bits}}$ 附近作X的阈值估计;

无法确定拿到的 $p$ 是否大于 $q$,所以对 $\beta=0.5$ 进行调整至 $0.4$。

目前在大部分消息加密之前都会进行 padding,但是如果 padding 的长度过短($m \in (0,\lfloor\frac{n.n\text{bits}()}{e^2}\rfloor]$),也有可能被很容易地攻击。

这里所谓 padding 过短,其实就是对应的多项式的根会过小。

当 Alice 使用同一公钥对两个具有某种线性关系的消息 $M_1$ 与 $M_2$ 进行加密,并将加密后的消息 $C_1$,$C_2$ 发送给了 Bob 时,我们就可能可以获得对应的消息 $M_1$ 与 $M_2$ 。这里我们假设模数为 $N$,两者之间的线性关系如下:

$M_1 \equiv f(M_2) \bmod N$

其中 $f$ 为一个线性函数,比如说 $f=ax+b$。

在具有较小错误概率下的情况下,其复杂度为 $O(e\log^2N)$。

这一攻击由 Franklin与Reiter 提出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#脚本1
#Sage
import binascii
def attack(c1, c2, n, e):
PR.<x>=PolynomialRing(Zmod(n))
# replace a,b,c,d
g1 = (a*x+b)^e - c1
g2 = (c*x+d)^e - c2

def gcd(g1, g2):
while g2:
g1, g2 = g2, g1 % g2
return g1.monic()
return -gcd(g1, g2)[0]
c1 =
c2 =
n =
e =
m1 = attack(c1, c2, n, e)
print(binascii.unhexlify("%x" % int(m1)))
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
#脚本2
#Sage
def short_pad_attack(c1, c2, e, n):
PRxy.<x,y> = PolynomialRing(Zmod(n))
PRx.<xn> = PolynomialRing(Zmod(n))
PRZZ.<xz,yz> = PolynomialRing(Zmod(n))
g1 = x^e - c1
g2 = (x+y)^e - c2
q1 = g1.change_ring(PRZZ)
q2 = g2.change_ring(PRZZ)
h = q2.resultant(q1)
h = h.univariate_polynomial()
h = h.change_ring(PRx).subs(y=xn)
h = h.monic()
kbits = n.nbits()//(2*e*e)
diff = h.small_roots(X=2^kbits, beta=0.4)[0] # find root < 2^kbits with factor >= n^0.4
return diff
def related_message_attack(c1, c2, diff, e, n):
PRx.<x> = PolynomialRing(Zmod(n))
g1 = x^e - c1
g2 = (x+diff)^e - c2
def gcd(g1, g2):
while g2:
g1, g2 = g2, g1 % g2
return g1.monic()
return -gcd(g1, g2)[0]
if __name__ == '__main__':
n =
e =
c1 =
c2 =
diff = short_pad_attack(c1, c2, e, n)
print("difference of two messages is %d" % diff)
m1 = related_message_attack(c1, c2, diff, e, n)
print("m1:", m1)
print("m2:", m1 + diff)
  • 变种1: $c_i=(a_im+b_i)^e \pmod {n_i}$

    用CRT计算系数 $T_i$ 使得 $T_i \equiv 1 \pmod{n_i},T_i \equiv 0 \pmod{n_{j \neq i}}$,

    则可建立多项式为 $f(x) = \sum_{i} T_i [ (a_i x + b_i)^e - c_i]$,符合 $f(m) \equiv 0 \pmod{n_i}$,

    故 $m$ 是 $f(m) \equiv 0 \pmod N$ 的一个根,其中 $N= \prod_i n_i$。

    如果 $m < \left (\prod_i n_i \right)^{1/e} = M^{1/\deg{f(x)}}$,可以使用coppersmith找出 $m$。

    参考:

    Security Fest 2022 - really_sick_æsthetic

    PlaidCTF 2017 - Multicast

    CakeCTF 2021 - Party Ticket

RSA Hastad Attack with non-linear padding and different public keys(带非线性padding和不同公钥的广播攻击)

适用情况:$m$ 经 $k$ 次非线性padding处理后,分别用 $k$ 组 $(N_i,e_i)$ 加密后得 $k$ 组 $c_i$。

参考:2020年羊城杯 - Invitation

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
#Sage
#e=3, padding: m²+(3^431)k
def linearPaddingHastads(cArray,nArray,aArray,bArray,eArray,eps):
if(len(cArray) == len(nArray) == len(aArray) == len(bArray) == len(eArray)):
for i in range(4):
cArray[i] = Integer(cArray[i])
nArray[i] = Integer(nArray[i])
aArray[i] = Integer(aArray[i])
bArray[i] = Integer(bArray[i])
eArray[i] = Integer(eArray[i])
TArray = [-1]*4
for i in range(4):
arrayToCRT = [0]*4
arrayToCRT[i] = 1
TArray[i] = crt(arrayToCRT,nArray)
P.<x> = PolynomialRing(Zmod(prod(nArray)))
gArray = [-1]*4
for i in range(4):
gArray[i] = TArray[i]*(pow(aArray[i]*x**2 + bArray[i],eArray[i]) - cArray[i])
g = sum(gArray)
g = g.monic()
roots = g.small_roots(epsilon=eps)
if(len(roots)== 0):
print("No Solutions found!")
return -1
return roots
else:
print("Input error!")

def nonLinearPadding():
eArr = [3 for i in range(4)]
nArr = []
cArr = []
aArr = [1 for i in range(4)]
bArr = [i * 3 ** 431 for i in [3,8,10,11]]
msg = linearPaddingHastads(cArr,nArr,aArr,bArr,eArr,eps=1/20)
for i in msg:
print(bytes.fromhex(hex(i)[2:]))

if __name__ == '__main__':
nonLinearPadding()

选择明/密文攻击

选择明文攻击

适用情况:对输入的任意明文服务器返回 RSA 加密结果,可以通过选择明文攻击来获取 $n$。

首先发送 $2$,让服务器进行加密,返回 $c_2=2^e \bmod n$;

继续发送 $2^2$,让服务器进行加密,返回 $c_4=4^e \bmod n$;

不妨设 $2^e=a+bn$,有 $c_2=(a+bn) \bmod n=a$,$c_4=(a^2+2abn+b^2n^2) \bmod n = a^2 \bmod n$,

所以 $c_2^2$ 和 $c_4$ 模 $n$ 同余,即 $c_2^2-c_4=kn$,同理 $c_2^3-c_8=k’n$,

一般来说 $a^2$ 比 $n$ 大,所以 $k \neq 0$。

同理还可以构造更多的例子取他们的公因数,来更加确定地找 $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
import gmpy2

def get_n():
nset = []
c2 = server_encode(2)
c4 = server_encode(4)
c8 = server_encode(8)
nset.append(c2 * c2 - c4)
nset.append(c2 * c2 * c2 - c8)
c3 = server_encode(3)
c9 = server_encode(9)
c27 = server_encode(27)
nset.append(c3 * c3 - c9)
nset.append(c3 * c3 * c3 - c27)
c5 = server_encode(5)
c25 = server_encode(25)
c125 = server_encode(125)
nset.append(c5 * c5 - c25)
nset.append(c5 * c5 * c5 - c125)
n = nset[0]
for x in nset:
n = gmpy2.gcd(x, n)
while n % 2 == 0:
n //= 2
while n % 3 == 0:
n //= 3
while n % 5 == 0:
n //= 5
print('n =', n)
return n
选择密文攻击

适用情况:可以构造任意密文并获得对应明文,通过选择密文攻击获得特定的明文。

假设服务器创建了密文 $c=m^e \bmod n$,并且把 $c$ 发送给用户,用户可以发送任意密文服务器返回解密后的明文,可以通过以下方法求出 $m$:

  1. 选择任意的 $x$ 与 $n$ 互素;
  2. 计算 $y=cx^e \bmod n$;
  3. 由于可以进行选择密文攻击,可以求得 $y$ 对应的解密结果 $z=y^d$;
  4. 则 $z=y^d=(cx^e)^d=c^dx=mx \bmod n$,由于 $x$ 与 $n$ 互素,容易求得相应逆元,进而可以得到 $m$。
1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *

def get_M():
X = getPrime(5)
Y = (c * (X ** e)) % n
Z = server_decode(Y)
i = 0
while True:
M = (n * i + Z) // X
if 'flag' in long_to_bytes(M):
print(long_to_bytes(M))
break
Parity Oracle Attack
LSB Oracle Attack(Least Significant Bit Oracle Attack )

适用情况:可以选择密文并泄露明文的最低位(奇偶性)。

服务器会对一个给定的密文进行解密,并且会检查解密的明文的奇偶性,并根据奇偶性返回相应的值,比如1表示奇数,0表示偶数。那么给定一个加密后的密文,只需要 $\log_2n$ 次就可以知道这个密文对应的明文消息。

假设 $c=m^e \bmod n$,第一次时,构造密文 $c \cdot 2^e \bmod n=(2m)^e \bmod n$,服务器解密后得到 $2m \bmod n$。

这里:

  • $2m$ 是偶数,它的幂次也是偶数;
  • $n$ 是奇数,因为它是由两个大素数相乘得到。

那么:

  • 服务器返回奇数,即 $2m \bmod n$ 为奇数,则说明 $2m>n$,且减去了奇数个 $n$,又因为 $2m<2n$,因此减去了一个 $n$,即 $\frac{n}{2}\leq m \lt n$;
  • 服务器返回偶数,则 $2m<n$,即 $0 \leq m \lt \frac{n}{2}$。

第二次时,构造密文 $c \cdot 4^e \bmod n$,服务器解密后得到 $4m \bmod n$,判断其奇偶性可以知道 $m$ 和 $\frac{n}{4}$ 的大小关系。

以此类推,第 $i$ 次时,构造密文 $c \cdot 2^{ie} \bmod n$,服务器解密后得到 $2^im \bmod n$,判断其奇偶性可以知道 $m$ 和 $\frac{n}{2^i}$ 的大小关系。

所以我们就有了一个二分算法,可以在 $\log_2n$ 次内将 $m$ 的范围逼近到一个足够狭窄的空间。

假设服务器返回 b,那么可以归纳为:

1
2
3
4
5
6
7
L = 0
R = n
for i in range(1024):
if b:
L = (L+R) // 2
else:
R = (L+R) // 2

由于此处有大量整除运算,所以最好用 decimal 库进行精确计算,否则最后结果很可能会出错。decimal.getcontext().prec 用来设定精度。

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

def get_flag():
k = n.bit_length()
decimal.getcontext().prec = k
L = decimal.Decimal(0)
R = decimal.Decimal(int(n))
for i in range(k):
c = (c * pow(2, e, n)) % n
recv = server_decode(c)
if recv == 1:
L = (L + R) // 2
else:
R = (L + R) // 2
print(long_to_bytes(int((R))))

更多信息可参考:RSA Least-Significant-Bit Oracle AttackRSA least significant bit oracle attack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import decimal
def oracle():
return lsb == 'odd'

def partial(c, e, n):
k = n.bit_length()
decimal.getcontext().prec = k # for 'precise enough' floats
lo = decimal.Decimal(0)
hi = decimal.Decimal(n)
for i in range(k):
if not oracle(c):
hi = (lo + hi) // 2
else:
lo = (lo + hi) // 2
c = (c * pow(2, e, n)) % n
# print i, int(hi - lo)
return int(hi)
MSB Oracle Attack(Most Significant Bit Oracle Attack )

适用情况:可以选择密文并泄露明文的最高位(奇偶性)。

假设远程提供一个解密服务,但是只返回明文的最高字节,并且明文的形式是64字节,高位用 \x00 填充。

将加密的内容拿去解密会得到 $m$,但是回显最高位是 \x00,构造密文 $c \cdot 2^e$,解密会得到 $2m \bmod n$,

不断构造密文 $c \cdot 2^{ie}$,当最高位不是 \x00 时,记录下值为 $x$,则说明 $mx>2^{\text{kbit}}$,

然后再相应缩小 $x$ ,可以利用二分法,比如当第一次拿到 $mx>2^{\text{kbit}}$,那么有 $m(\frac{x}{2})<2^{\text{kbit}}$,因此新的 $x’$ 必定满足 $\frac{x}{2} \lt x’ \lt x$,接着尝试 $\frac{x+\frac{x}{2}}{2}$ 就好。

最终可以找到一个 $X$,满足 $mX \lt 2^{\text{kbit}}$ 且 $m(X+1) \gt 2^{\text{kbit}}$,由于是整除,所以会有误差,最后的 $m$ 在 $\frac{2^{\text{kbit}}}{x}$ 附近。

参考:Pwnhub - pkcs4

Byte Oracle Attack

适用情况:可以选择密文并泄露最后一个字节。

服务器会对一个给定的密文进行解密,并且会给出明文的最后一个字节。那么给定一个加密后的密文,只需要 $\log_{256}n$ 次就可以知道这个密文对应的明文消息。

这是 RSA Parity Oracle 的扩展,既然可以泄露出最后一个字节,那么按道理获取密文对应明文的次数应该可以减少。

假设 $c=m^e \bmod n$,第一次时,构造密文 $c \cdot 256^e \bmod n=(256m)^e \bmod n$,服务器解密后得到 $256m \bmod n$。

这里:

  • $256m$ 是偶数,它的幂次也是偶数;
  • $n$ 是奇数,因为它是由两个大素数相乘得到。

由于 $m=c^d \bmod n$,所以 $m \lt n$,那么:$256m \bmod n=256m-kn$,$(k<256)$,

而且对于两个不同的 $k_1,k_2$,有:$(256m-k_1n) \bmod 256 \neq (256m-k_2n) \bmod 256$,

同时 $256m-kn$ 的最后一个字节其实就是 $-kn$ 在模 $256$ 的情况下获取的。

那么,可以首先枚举出 $0 \sim 255$ 情况下的最后一个字节,构造一个 $k$ 和最后一个字节的映射表 $\text{M}$。

当服务器返回最后一个字节,可以根据上述构造的映射表 $\text{M}$ 得知 $k$,即减去了 $k$ 个 $n$,即 $kn \leq 256m \leq (k+1)n$。

以此类推,第 $i$ 次时,构造密文 $c \cdot 256^{ie} \bmod n$,服务器解密后得到 $256^im \bmod n = 256^im-kn$,即:

$kn \leq 256^im \leq (k+1)n$, $\frac{kn}{256^i} \leq m \leq \frac{(k+1)n}{256^i}$。

那么,可以设初始范围为:$\frac{M}{n} \in [L_0,R_0],(L_0=0,R_0=1)$,

第 $i$ 次迭代后:$L_i=L_{i-1}+\frac{k_i}{256^i},R_i=R_{i-1}+\frac{k_i+1}{256^i}$。

最后一个问题是迭代的次数,由于明文的最后一个字节可以直接由服务器解密得到,那么只需要限定 $m$ 的范围至 $m_{\text{max}}-m_{\text{min}} \lt 256$,即 $n(R_i-L_i)= \frac{n}{256^i} \lt 256$。

例如,假设 $n \lt 2^{1024}$,由上式可得 $i \gt 128$。

一般对于这样的 Oracle,最多需要 $\log_{2^{\text{bits}}}n$ 次迭代即可确定明文,其中 bits 为泄露的明文 bit 数。RSA Parity Oracle 为 1,RSA Byte Oracle 为 8。

假设服务器返回了 b,那么可以归纳为:

1
2
3
4
5
6
7
L = 0
R = 1
for i in range(128):
k = mab[b]
L = L + k // 256**(i+1)
R = L + (k+1)// 256**(i+1)
M = L * n

如果不知道 $e$ 但服务器提供任意明文加密服务,可以让服务器加密 $256$,得到 $256^e \bmod n$。

由于有大量除法运算,为保证精度,将中间过程用 Fraction 库保存为分数。

最后一字节的数据不准确要减掉,从服务器返回精确的最后一字节数据。

其实只要求出 L 下限即可,无需求出 R 上限。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
from fractions import Fraction

def get_flag():
map = {}
for i in range(0, 256):
map[-n * i % 256] = i

cipher256 = server_encode(256)
backup = c

L = Fraction(0, 1)
R = Fraction(1, 1)
for i in range(128):
c = c * cipher256 % n
b = server_decode(c)
k = map[b]
L, R = L + Fraction(k, 256**(i+1)), L + Fraction(k+1, 256**(i+1))
m = int(L * n)
print(long_to_bytes(m - m % 256 + server_decode(backup)))

Common Private Exponent(共私钥指数攻击,d相同)

加密用同样的私钥并且私钥比较短,从而导致了加密系统被破解。

假定:

$\begin{cases} e_1d=1+k_1\varphi(N_1) \newline e_2d=1+k_2\varphi(N_2) \newline {\vdots} \newline e_rd=1+k_r\varphi(N_r) \end{cases}$

其中,$N_1 \lt N_2 \lt \cdots \lt N_r \lt 2N_1$。

构造格:

$B_r=\begin{bmatrix}{M}&{e_1}&{e_2}&{\cdots}&{e_{r}}\newline
{0}&{-N_1}&{0}&{\cdots}&{0}\newline{0}&{0}&{-N_2}&{\cdots}&{0}\newline{\vdots}&{\vdots}&{\vdots}&{\ddots}&{\vdots}\newline{0}&{0}&{0}&{\cdots}&{-N_r}\newline\end{bmatrix}$

其中 $M=\lfloor N_r^{\frac{1}{2}} \rfloor$。

再利用LLL算法进行规约得到 $\vert b_1\vert=Md$,则 $d=\cfrac{\vert b_1 \vert}{M}$,从而解密密文得到明文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
###Sage###
from gmpy2 import *
e0=
n0=
c0=
e1=
n1=
c1=
e2=
n2=
c2=

M=iroot(int(n2),int(2))[0]
a=[0]*4
a[0]=[M,e0,e1,e2]
a[1]=[0,-n0,0,0]
a[2]=[0,0,-n1,0]
a[3]=[0,0,0,-n2]

Mat = matrix(ZZ,a)
Mat_LLL=Mat.LLL()
d = abs(Mat_LLL[0][0])/M
print(bytes.fromhex(hex(pow(c1,int(d),int(n1)))[2:]))

多组低解密指数攻击

适用情况:2-4组 $e$,且 $d$ 较小

  • 给定2组

    $g=\gcd(p-1,q-1),\lambda(n)=\frac{\varphi(n)}{g},s=1-p-q$

    且有 $ed-k\lambda(n)=1$,得到 $edg-kn=g+ks\quad (1)$

    设 $e_1$ 对应 $k_1$,$e_2$ 对应 $k_2$,则有 $k_{2}d_{1}e{1}-k_{1}d_{2}e_{2}=k_{2}-k_{1}\quad (2)$

    由(1)(2)有:

    $\left\{ \begin{matrix} e_{1}d_{1}g-k_{1}n=g+k_{1}s \newline k_{2}d_{1}e{1}-k_{1}d_{2}e_{2}=k_{2}-k_{1} \newline e_{1}e_{2}d_{1}d_{2}g_{2}-e_{1}d_{1}gk_{2}n-e_{2}d_{2}gk_{1}n+k_{1}k_{2}n^{2}=(g+k_{1}s)(g+k_{2}s) \end{matrix} \right.$

    上述等式组也可表示为

    $bL_2 =[k_{1}k_{2},k_{2}d_{1}g,k_{1}d_{2}g,d_{1}d_{2}g^{2}]\cdot\left[ \begin{matrix} n & -M_{1}n & 0 & n^{2} \newline 0 & M_{1}e_{1} & M_{2}e_{1} & -e_{1}n \newline 0 & 0 & -M_{2}e_{2} & -e_{2}n \newline 0 & 0 & 0 & e_{1}e_{2} \end{matrix} \right] =[k_{1}k_{2}n,M_{1}k_{2}(g+k_{1}s),M_{2}g(k_{2}-k_{1}),(g+k_{1}s)(g+k_{2}s)]$

    (其中 $M_{1}=n^{1/2},M_{2}=n^{1+\alpha_{2}},d\approx n^{\alpha_{2}}$)

    对部分参数进行上界估计,k上界近似于 $d\approx N^{\alpha_{2}}$, $|s|$ 上界 $\approx N^{1/2}$,$g$ 一般相对极小

    因此上面的矩阵表示 $BA=C$ 中,$C$ 的每个元的size都近似 $n^{1+2\alpha_{2}}$,所以 $|C|\approx 2\cdot n^{1+2\alpha_{2}}$

    $B$ 作为格基的格中,最短向量由Minkowski Bounds知 $\approx \sqrt{4}\det(B)^{1/4}\approx 2\cdot n^{(13/2+\alpha_{2})/4}$

    因此只要满足 $n^{1+2\alpha_{2}}<n^{(13/2+\alpha_{2})/4}$ 即可将问题转化为SVP($\alpha_{2}<\frac{5}{14}$)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
     from sage.all import *
    import gmpy2
    N =
    e1 =
    e2 =
    c =
    for i in range(1000):
    alpha2 = i/1000
    M1 = int(gmpy2.mpz(N)**0.5)
    M2 = int( gmpy2.mpz(N)**(1+alpha2) )
    D = diagonal_matrix(ZZ, [N, M1, M2, 1])
    B = Matrix(ZZ, [ [1, -N, 0, N**2],
    [0, e1, -e1, -e1*N],
    [0, 0, e2, -e2*N],
    [0, 0, 0, e1*e2] ]) * D
    L = B.LLL()
    v = Matrix(ZZ, L[0])
    x = v * B**(-1)
    phi = (x[0,1]/x[0,0]*e1).floor()
    try:
    d = inverse_mod( 65537, phi)
    m = hex(power_mod(c, d, N))[2:]
    if m.startswith('44415343'):
    print(i)
    print(bytes.fromhex(m))
    break
    except:
    pass

    参考:De1CTF 2020 - easyRSA

  • 给定3组

    类似2组情况,其中

    $b=[k_1k_2k_3,d_1gk_2k_3,k_1d_2gk_3,d_1d_2g^2k_3,k_1k_2d_3g,k_1d_3g,k_2d_3g,d_1d_2d_3g^3]$

    $L_3=\left[\begin{matrix} 1-N & 0 & N^2 & 0 & 0 & 0 & -N^3 \newline e_1 & -e_1 & -e_1N & -e & 0 & e_1N & e_1N^2 \newline 0 & e_2 & -e_2N & 0 & e_2N & 0 & e_2N^2 \newline 0 & 0 & e_1e_2 & 0 & -e_1e_2 & -e_1e_2 & -e_1e_2N \newline 0 & 0 & 0 & e_3 & -e_3N & -e_3N & e_3N^3 \newline 0 & 0 & 0 & 0 & e_1e_3 & 0 & -e_1e_3N \newline 0 & 0 & 0 & 0 & 0 & e_2e_3 & -e_2e_3N \newline 0 & 0 & 0 & 0 & 0 & 0 & e_1e_2e_3 \end{matrix}\right] \times D$

    其中 $D={\rm diag}(N^{3/2},N,N^{(3/2)+\alpha_3},N^{1/2},N^{(3/2)+\alpha_3},N^{1+\alpha_3},N^{1+\alpha_3},1)$

    参考:3kCTF - RSA Textbook

    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
    from sage.all import *
    import gmpy2

    N =
    e1 =
    e2 =
    e3 =
    c =

    for i in range(1000):
    alpha2 = i/1000
    M1 = int(gmpy2.mpz(N)**(3./2))
    M2 = int( gmpy2.mpz(N) )
    M3 = int(gmpy2.mpz(N)**(3./2 + alpha2))
    M4 = int( gmpy2.mpz(N)**(0.5) )
    M5 = int( gmpy2.mpz(N)**(3./2 + alpha2) )
    M6 = int( gmpy2.mpz(N)**(1.+alpha2) )
    M7 = int( gmpy2.mpz(N)**(1.+alpha2) )
    D = diagonal_matrix(ZZ, [M1, M2, M3, M4, M5, M6, M7, 1])
    B = Matrix(ZZ, [ [1, -N, 0, N**2, 0, 0, 0, -N**3],
    [0, e1, -e1, -e1*N, -e1, 0, e1*N, e1*N**2],
    [0, 0, e2, -e2*N, 0, e2*N, 0, e2*N**2],
    [0, 0, 0, e1*e2, 0, -e1*e2, -e1*e2, -e1*e2*N],
    [0, 0, 0, 0, e3, -e3*N, -e3*N, e3*N**2],
    [0, 0, 0, 0, 0, e1*e3, 0, -e1*e3*N],
    [0, 0, 0, 0, 0, 0, e2*e3, -e2*e3*N],
    [0, 0, 0, 0, 0, 0, 0, e1*e2*e3] ]) * D

    L = B.LLL()

    v = Matrix(ZZ, L[0])
    x = v * B**(-1)
    phi_ = (e1*x[0,1]/x[0,0]).floor()
    try:
    d = inverse_mod( 65537, phi_)
    m = hex(power_mod(c, d, N))[2:]
    if m.startswith('44415343'):
    print(i)
    print(bytes.fromhex(m))
    break
    except:
    pass
  • 给定更多组

    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
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    from Crypto.Util.number import *

    isdigit = lambda x: ord('0') <= ord(x) <= ord('9')
    def my_permutations(g, n):
    sub = []
    res = []
    def dfs(s, prev):
    if len(s) == n:
    res.append(s[::])
    for i in g:
    if i in s or i < prev:
    continue
    s.append(i)
    dfs(s, max(prev, i))
    s.remove(i)
    dfs(sub, 0)
    return res

    class X3NNY(object):
    def __init__(self, exp1, exp2):
    self.exp1 = exp1
    self.exp2 = exp2

    def __mul__(self, b):
    return X3NNY(self.exp1 * b.exp1, self.exp2 * b.exp2)

    def __repr__(self):
    return '%s = %s' % (self.exp1.expand().collect_common_factors(), self.exp2)

    class X_Complex(object):
    def __init__(self, exp):
    i = 0
    s = '%s' % exp
    while i < len(s):
    if isdigit(s[i]):
    num = 0
    while i < len(s) and isdigit(s[i]):
    num = num*10 + int(s[i])
    i += 1
    if i >= len(s):
    self.b = num
    elif s[i] == '*':
    self.a = num
    i += 2
    elif s[i] == '/':
    i += 1
    r = 0
    while i < len(s) and isdigit(s[i]):
    r = r*10 + int(s[i])
    i += 1
    self.b = num/r
    else:
    i += 1
    if not hasattr(self, 'a'):
    self.a = 1
    if not hasattr(self, 'b'):
    self.b = 0

    def WW(e, d, k, g, N, s):
    return X3NNY(e*d*g-k*N, g+k*s)
    def GG(e1, e2, d1, d2, k1, k2):
    return X3NNY(e1*d1*k2- e2*d2*k1, k2 - k1)

    def W(i):
    e = eval("e%d" % i)
    d = eval("d%d" % i)
    k = eval("k%d" % i)
    return WW(e, d, k, g, N, s)

    def G(i, j):
    e1 = eval("e%d" % i)
    d1 = eval("d%d" % i)
    k1 = eval("k%d" % i)

    e2 = eval("e%d" % j)
    d2 = eval("d%d" % j)
    k2 = eval("k%d" % j)

    return GG(e1, e2, d1, d2, k1, k2)

    def R(e, sn): # min u max v
    ret = X3NNY(1, 1)
    n = max(e)
    nn = len(e)
    l = set(i for i in range(1, n+1))
    debug = ''
    u, v = 0, 0
    for i in e:
    if i == 1:
    ret *= W(1)
    debug += 'W(%d)' % i
    nn -= 1
    l.remove(1)
    u += 1
    elif i > min(l) and len(l) >= 2*nn:
    ret *= G(min(l), i)
    nn -= 1
    debug += 'G(%d, %d)' % (min(l), i)
    l.remove(min(l))
    l.remove(i)
    v += 1
    else:
    ret *= W(i)
    l.remove(i)
    debug += 'W(%d)' % i
    nn -= 1
    u += 1
    # print(debug, end = ' ')
    return ret, u/2 + (sn - v) * a

    def H(n):
    if n == 0:
    return [0]
    if n == 2:
    return [(), (1,), (2,), (1, 2)]
    ret = []
    for i in range(3, n+1):
    ret.append((i,))
    for j in range(1, i):
    for k in my_permutations(range(1, i), j):
    ret.append(tuple(k + [i]))
    return H(2) + ret

    def CC(exp, n):
    cols = [0 for i in range(1<<n)]

    # split exp
    texps = ('%s' % exp.exp1.expand()).strip().split(' - ')
    ops = []
    exps = []
    for i in range(len(texps)):
    if texps[i].find(' + ') != -1:
    tmp = texps[i].split(' + ')
    ops.append(0)
    exps.append(tmp[0])
    for i in range(1, len(tmp)):
    ops.append(1)
    exps.append(tmp[i])
    else:
    ops.append(0)
    exps.append(texps[i])
    if exps[0][0] == '-':
    for i in range(len(exps)):
    ops[i] = 1-ops[i]
    exps[0] = exps[0][1:]
    else:
    ops[0] = 1
    # find e and N
    l = []
    for i in range(len(exps)):
    tmp = 1 if ops[i] else -1
    en = []
    j = 0
    while j < len(exps[i]):
    if exps[i][j] == 'e':
    num = 0
    j += 1
    while isdigit(exps[i][j]):
    num = num*10 + int(exps[i][j])
    j += 1
    tmp *= eval('e%d' % num)
    en.append(num)
    elif exps[i][j] == 'N':
    j += 1
    num = 0
    if exps[i][j] == '^':
    j += 1
    while isdigit(exps[i][j]):
    num = num*10 + int(exps[i][j])
    j += 1
    if num == 0:
    num = 1
    tmp *= eval('N**%d' % num)
    else:
    j += 1
    if tmp == 1 or tmp == -1:
    l.append((0, ()))
    else:
    l.append((tmp, tuple(sorted(en))))

    # construct h
    mp = H(n)
    for val, en in l:
    cols[mp.index(en)] = val
    #print(cols)
    return cols

    def EWA(n, elist, NN, alpha):
    mp = H(n)
    var('a')
    S = [X_Complex(n*a)]
    cols = [[1 if i == 0 else 0 for i in range(2^n)]]
    for i in mp[1:]:
    eL, s = R(i, n)
    cols.append(CC(eL, n))
    S.append(X_Complex(s))

    alphaA,alphaB = 0, 0
    for i in S:
    alphaA = max(i.a, alphaA)
    alphaB = max(i.b, alphaB)
    #print(alphaA, alphaB)
    D = [int(NN^((alphaA-S[i].a)*alpha + (alphaB - S[i].b))) for i in range(len(S))]
    #print(D)
    kw = {'N': NN}
    for i in range(len(elist)):
    kw['e%d' % (i+1)] = elist[i]
    print(cols)
    B = Matrix(ZZ, Matrix(cols).T(**kw)) * diagonal_matrix(ZZ, D)
    L = B.LLL(0.5)
    v = Matrix(ZZ, L[0])
    x = v * B**(-1)
    phi = int(x[0,1]/x[0,0]*elist[0])
    return phi

    def attack(NN, elist, alpha):
    phi = EWA(len(elist), elist, NN, alpha)
    print(phi)

    elist = [ ]
    NN=
    alpha = 400./2048
    for i in range(1, len(elist)+1):
    var("e%d" % i)
    var("d%d" % i)
    var("k%d" % i)
    g, N, s = var('g'), var('N'), var('s')

    for i in range(len(elist)):
    elist[i] = Integer(elist[i])
    attack(NN, elist, alpha)
    phi =
    c=
    d=inverse(65537,int(phi))
    m = pow(c,d,NN)
    print(long_to_bytes(int(m)))

    参考:西湖论剑 2021 - WienerStudyTwice

  • 参考Paper

    Common Modulus Attacks on Small Private Exponent RSA and Some Fast Variants (in Practice)

    Extending Wiener’s Attack in the Presence of Many Decrypting Exponents

多项式RSA

在整数RSA原理基础上将多项式代入分析:

在有限域上选取两个不可约多项式 $g(p),g(q)$,$g(n)=g(p) \cdot g(q)$,计算出 $g(n)$ 的欧拉函数 $\varphi(g(n))=\varphi$,

选取一个整数 $e$ 作为公钥,$e$ 与 $\varphi$ 是互素的,那么对于明文 $g(m)$,加密过程为 $g(m)^e \equiv g(c) \pmod {g(n)}$,

计算私钥 $d$ 满足 $ed \equiv 1 \pmod \varphi$,则 $g(c)^d \equiv (g(m)^e)^d \equiv g(m)^{ed} \equiv g(m)^{\varphi+1} \pmod {g(n)}$,

同样考虑 $g(n)$ 与 $g(m)$ 互素,欧拉定理对于多项式亦成立,

得到 $g(m)^{\varphi+1} \equiv g(m) \pmod {g(n)}$,所以 $g(c)^d \equiv g(m) \pmod {g(n)}$。

显然RSA对于整数的体制可以适用于有限域上的多项式。

★注意:

对于素数 $x$,$\varphi(x)=x-1$,但是对于不可约多项式 $g(x)$,$\varphi(g(x))=p^n-1$。(此 $p$ 为 $GF(p)$ 的模,此 $n$ 为多项式最高项次数)

原因:

由欧拉函数定义本身,欧拉函数是小于 $n$ 的所有与 $n$ 互质的数的个数。

多项式的欧拉函数则类似,表示不高于 $g(x)$ 幂级的环内所有多项式中,与 $g(x)$ 无公因式(非1)的其他多项式的个数,所以每一个不高于 $g(x)$ 幂级的环内多项式(除了它自己)均满足此条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#脚本1
#Sage
#已知p,n,m^e
p=
P = PolynomialRing(Zmod(p), name = 'x')
x = P.gen()
e =
n =
c =

#分解N
q1, q2 = n.factor()
q1, q2 = q1[0], q2[0]

#求φ,注意求法,
phi = (p**q1.degree() - 1) * (p**q2.degree() - 1)
assert gcd(e, phi) == 1
d = inverse_mod(e, phi)
m = pow(c,d,n)

#取多项式系数
flag = bytes(m.coefficients())
print("Flag: ", flag.decode())
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
#脚本2
#Sage
#已知p=2,n,e,c
p =
P = PolynomialRing(GF(p), name = 'x')
x = P.gen()
e =
n =
R.<a> = GF(2^2049)
c = []

q1, q2 = n.factor()
q1, q2 = q1[0], q2[0]

phi = (p**q1.degree() - 1) * (p**q2.degree() - 1)
assert gcd(e, phi) == 1
d = inverse_mod(e, phi)

ans = ''
for cc in c:
cc = P(R.fetch_int(cc))
m = pow(cc,d,n)
m = R(P(m)).integer_representation()
print(m)
ans += chr(m)
print(ans)
1
2
3
4
5
#Sage
#x.nbits()==2^32
poly = sum(e * x^i for i,e in enumerate(Integer(n).digits(2^32)))
(p, _), (q, _) = poly.factor_list()
p, q = p(x=2^32), q(x=2^32)

参考:

0ctf - babyrsa

watevrCTF 2019 - Swedish RSA

InCTF 2020 - PolyRSA

Polynomial based RSA

Crypto CTF2020 - Decent RSA

SecurityFest CTF 2022 - small rsa

Weak prime factors (p具线性特征)

适用情况:$p$ 满足 $ap=u_0+M_1u_1+\cdots+M_ku_k$

先根据 $n$ 确定 $M$ 的大小,再根据 $M$ 选取符合要求的 $k$ 和 $c$,然后构造一个格如下:

$M(\mathcal{L})=\begin{bmatrix}{1}&{0}&{0}&{\cdots}&{0}&{CM^{2k}} \newline
{0}&{1}&{0}&{\cdots}&{0}&{CM^{2k-1}} \newline {\vdots}&{\vdots}&{\vdots}&{\ddots}&{\vdots}&{\vdots} \newline {0}&{0}&{0}&{\cdots}&{1}&{CM} \newline {0}&{0}&{0}&{\cdots}&{0}&{-CN} \newline \end{bmatrix}$

用LLL算法进行格基规约,将规约后的某个向量作为多项式系数,再对多项式进行分解,即可完成对 $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
from tqdm import tqdm
import gmpy2

class success(Exception):
pass

def attack_weak_prime(basenum, exp, n):
m = basenum^exp
k = len(n.str(base=basenum))//(2*exp) + 1
c = gmpy2.iroot(2*k^3, int(2))
# assert c[1] == True
tmp = int(c[0])

try:
for c in tqdm(range(1, tmp)):
amount = 2*k+1

M = Matrix(RationalField(), amount, amount)
for i in range(amount):
M[i, i] = 1
M[i, amount-1] = c*m^(2*k-i)
M[amount-1, amount-1] = -c*n

new_basis = M.LLL(delta=0.75)
for j in range(amount):
last_row = list(new_basis[j])
last_row[-1] = last_row[-1]//(-c)

poly = sum(e * x^(k*2-i) for i,e in enumerate(last_row))
fac = poly.factor_list()
if len(fac) == 2:
p_poly, q_poly = fac
p_coefficient = p_poly[0].list()
q_coefficient = q_poly[0].list()
ap = sum(m^i * j for i,j in enumerate(p_coefficient))
bq = sum(m^i * j for i,j in enumerate(q_coefficient))
p = gcd(ap, n)
q = gcd(bq, n)

if (p*q == n) and (p != 1) and (q != 1):
raise success

except:
print ('n =', n)
print ('p =', p)
print ('q =', q)
print ('p*q == n ?', bool(p*q == n))


if __name__ == '__main__':
print ('[+] Weak Prime Factorization Start!')
print ('-------------------------------------------------------------------------------------------------------------------------------')
basenum, exp = (3, 66)
n = 32846178930381020200488205307866106934814063650420574397058108582359767867168248452804404660617617281772163916944703994111784849810233870504925762086155249810089376194662501332106637997915467797720063431587510189901

p多次幂因子

适用情况:$N=p^rq$

  • 情形1

    条件:$(N,e)$ 满足 $ex-\varphi(N)y=z$,其中 $x$ 与 $\lvert z \rvert$ 为小参数。

    $f(x) = ex-z \equiv 0 \pmod {p^{r-1}}$

    计算 $\gcd(ex - z,N)=g$,则

    $p = \begin{cases} g^{\frac{1}{r-1}},\text{if } g=p^{r-1} \newline g^{\frac{1}{r}},\text{if } g=p^{r} \newline \frac{N}{g},\text{if } g=p^{r-1}q \end{cases}$

    1
    2
    3
    4
    P.<x> = PolynomialRing(Zmod(n))
    f = e * x - b
    root = f.monic().small_roots(X=2**672,beta=0.75)[0]
    g = gcd(int(e * root - b),n3)
  • 情形2

    条件:小 $\lvert d_1-d_2 \rvert$,$\lvert d_1-d_2 \rvert \lt N^{\frac{r(r-1)}{(r+1)^2}}$。

    $f(x) = e_1e_2(d_1-d_2) - (e_2-e_1) \equiv 0 \pmod {p^{r-1}}$

    等价于 $g(x) = x-a \equiv 0 \pmod {p^{r-1}}$,其中 $a \equiv (e_2-e_1)(e_1e_2)^{-1} \pmod {N}$。

    计算 $\gcd(e_1e_2x - (e_2-e_1),N)=g$,则

    $p = \begin{cases} g^{\frac{1}{r-1}},\text{if } g=p^{r-1} \newline g^{\frac{1}{r}},\text{if } g=p^{r} \newline \frac{N}{g},\text{if } g=p^{r-1}q \end{cases}$

    1
    2
    3
    4
    P.<x> = PolynomialRing(Zmod(n))
    f = e1*e2*x - e1 + e2
    root = f.monic().small_roots(X=2**672,beta=0.75)[0]
    g = gcd(int(e1*e2*root - e1 + e2),n)

    情形3

    条件:$N_1=p_1^rq_1,N_2=p_2^rq_2$,小 $\lvert p_1-p_2 \rvert$,$\lvert p_1-p_2 \rvert \lt \cfrac{p_1}{2rq_1q_2}$。

    $\left| \cfrac{N_2}{N_1} - \cfrac{q_2}{q_1} \right| = \cfrac{q_1q_2 \lvert p_1^r - p_2^r \rvert}{q_1^2p_1^r} < \cfrac{1}{2q_1^2}$

    利用 $\cfrac{N_2}{N_1}$ 的连分数展开对应的渐进分数逼近 $\cfrac{q_2}{q_1}$。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    cf = continued_fraction(n1/n2)
    fracs = cf.convergents()
    for xx in tqdm(fracs):
    q1 = xx.numerator()
    q2 = xx.denominator()
    if q1.nbits() in range(511, 513) and q2.nbits() in range(511, 513):
    if n1 % q1 == 0:
    print(q1)
    assert n1 % q1 == 0
    p1 = int((n1 // q1)^(1/2))
    p2 = int((n2 // q2)^(1/2))
    assert p1^2 * q1 == n1
    break

参考:

New attacks on RSA with Moduli $N = p^rq$

D^3CTF 2022 - d3factor

RSA-CRT

  • 故障注入攻击

    RSA-CRT fault attack

    假设在计算 $S_q$ 时发生了错误,$S_q=m_q^{d_q} \bmod q$,$m_q=m \bmod q$,$d_q=d \bmod (q-1)$,

    正确签名:$S=S_p \cdot(q^{-1} \bmod p) \cdot q+S_q \cdot(p^{-1} \bmod q) \cdot p$,

    错误签名:$\hat{S} = S_p \cdot (q^{-1} \bmod p) \cdot q + \hat{S_q} \cdot (p^{-1} \bmod q) \cdot p$,

    则 $S - \hat{S} = (S_q - \hat{S_q}) \cdot (p^{-1} \bmod q) \cdot p$,即有 $p=\gcd(S-\hat{S},N)$。

    或由错误签名 $\hat{S}$,有 $p=\gcd(S’^e-m,N)$。

  • 错误模攻击

    有明文 $m$ 经对应编码后的 $\sigma_p = \mu(m)^d \bmod p, \sigma_q = \mu(m)^d \bmod q$,生成RSA-CRT签名 $\sigma = (\sigma_p\cdot\alpha + \sigma_q\cdot\beta) \bmod N$,其中参数 $\alpha = q \cdot (q^{-1} \bmod p),\beta = p \cdot (p^{-1} \bmod q)$。

    利用错误模注入技术得到错误签名 $\sigma’$,即 $\sigma’ = (\sigma_p\cdot\alpha + \sigma_q\cdot\beta) \bmod N’$,

    对生成的两种签名 $\sigma$ 和 $\sigma’$ 使用CRT可计算出 $v=(\sigma_p\cdot\alpha + \sigma_q\cdot\beta) \bmod (N \cdot N’)$。

    针对 $l \ge 5$ 的编码后消息进行分析,通过计算签名对 $(\sigma,\sigma’)$ 分解 $N$ 的攻击方法:

    1. 对所有的 $i$,计算出对应的整数 $v_i= \text{CRT}_{N,N’}(\sigma_i,\sigma_i’)$,这些对应的 $v_i$ 构成 $\mathbb{Z}^l$ 上的向量 $\mathbf{v}=(v_1,\cdots,v_i)$;

    2. 利用LLL定理计算出垂直于向量 $\mathbf{v}$ 的正交格 $\mathbf{v}^{\perp}$ 的规约基 $\mathbf{b}_1,\cdots,\mathbf{b}_{l-1}$,其中所有的向量和格的分布都是在 $\mathbb{Z}^l$ 内。通过对存在于 $\mathbb{Z}^{1+l}$ 中的格应用LLL定理,即对如下矩阵使用LLL定理:

      $\begin{pmatrix} kv_1 & 1 & & 0 \newline \vdots& & \ddots & \newline kv_l & 0 & & 1 \end{pmatrix}$

      其中 $k$ 为合适的大常量,并去除计算出来的向量的第1个元素;

    3. 前 $l-2$ 个向量 $\mathbf{b}_1,\cdots,\mathbf{b}_{l-2}$ 将生成秩为 $l-2$ 的格 $L’$,再次利用LLL定理来计算出正交格 $(L’)^{\perp}$ 的规约基 $\mathbf{x}’,\mathbf{y}’$。同样可以通过对如下矩阵使用LLL定理得到对应的规约基:

      $\begin{pmatrix} k’b_{1,1} & \cdots & k’b_{l-2,1} & 1 & & 0 \newline \vdots& & \vdots & & \ddots & \newline k’b_{1,l} & \cdots & k’b_{l-2,l}& 0 & & 1 \end{pmatrix}$

      同步骤2,保留计算出来的向量的最后 $l$ 个元素;

    4. 将所有长度不超过 $\sqrt{lN}$ 的并在 $(L’)^{\perp}$ 内的向量 $\mathbf{z}=a \mathbf{x}’+b \mathbf{y}’$ 列举出来,对符合条件的向量 $\mathbf{z}$,计算出 $\gcd(\mathbf{v}-\mathbf{z},N)$,可以得出 $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
    from tqdm import tqdm
    import gmpy2,sys

    def orthogonal_lattice(B):
    LB = B.transpose().left_kernel(basis="LLL").basis_matrix()
    return LB

    cs = []
    s = []
    l = 6

    v = []
    for i in range(len(cs_)):
    v.append(int(crt([s_[i], cs_[i]], [n, N])))

    v = vector(ZZ, v)
    Lv = orthogonal_lattice(Matrix(v))
    L1 = orthogonal_lattice(Lv.submatrix(0, 0, l-2, l))
    x, y = L1
    for a in tqdm(range(333)):
    for b in tqdm(range(333)):
    z = a*x+b*y
    for each in (v-z):
    tmp = gcd(each,n)
    if tmp>1:
    p = tmp
    print(p)
    sys.exit()

    参考:

    Modulus Fault Attacks Against RSA-CRT Signatures

    2022巅峰极客 - Learning with Fault

其他特别情形

  • 多素数因子(Multi-prime RSA)

    $n=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m} \\ \Rightarrow \begin{eqnarray}\varphi(n) &=&\varphi(p_1^{k_1})\varphi(p_2^{k_2}) \cdots \varphi(p_m^{k_m}) \\ &=&(p_1^{k_1-1}\cdot(p_1-1))(p_2^{k_2-1}\cdot(p_2-1)) \cdots (p_m^{k_m-1}\cdot(p_m-1)) \end{eqnarray}$

  • next_prime()

    根据素数定理,素数的平均间隔为:$\cfrac{x}{\pi(x)} \approx \ln(x)$,因此常见的下一个素数比当前素数大一点,一般不会超过1500。

    • 变种1:$n=p \cdot q \cdot \text{nextprime}(p) \cdot \text{nextprime}(q)$

      费马因式分解

  • 给 e,p,c

    $c \equiv m^e \pmod n \\\Leftrightarrow c_1 \equiv c \pmod p \equiv m^e \pmod p$

    令 $ed_1 \equiv 1 \pmod {(p-1)}$,有 $m \equiv c^d \pmod n \equiv c_1^{d_1} \pmod p$。

  • 给 e,d,modinv(q,p),c

    已知:$p,q$ 同比特位数。

    令 $cf=q^{-1} \bmod p$,有 $q\cdot cf=1 \pmod p$。

    • $ed=1+k(p-1)(q-1)$,

      比较比特位数,$k$ 与 $e$ 同长,可爆破 $k$,得 $\varphi(n)=(p-1)(q-1)=\cfrac{ed-1}{k}$;

    • 上式 $\varphi(n) =(p-1)(q-1) \pmod p=-(q-1) \pmod p$,

      结合 $q\cdot cf=1 \pmod p$,即 $q\cdot cf-1=0 \pmod p$,

      联立:

      $\begin{eqnarray} \varphi(n)&=&(p-1)(q-1)\\&=&pq-p-q+1\\&=&n-p-q+1 \end{eqnarray}$

      $\begin{eqnarray} cf\cdot \varphi(n)&=&cf\cdot(n-p-q+1)\\&=&cf\cdot n-cf\cdot p-cf\cdot q+cf \end{eqnarray}$

      $\begin{eqnarray} cf\cdot \varphi(n) \bmod p&=&(cf\cdot n-cf\cdot p-cf\cdot q+cf) \bmod p\\&=&0-0-(cf\cdot q)+cf \bmod p\\&=&-1+cf \bmod p \end{eqnarray}$

      有 $1+cf\cdot \varphi(n)-cf=0\pmod p$,

      即$x=1+cf\cdot \varphi(n)-cf$ 能被 $p$ 整除;

    • 由费马小定理,存在 $r$ 满足 $r^{p-1}=1 \pmod p$,

      $\begin{eqnarray}r^{\varphi(n)}&=&(r^{(p-1)})^{(q-1)}\\&=&1^{(q-1)} \pmod p\\&=&1 \pmod p \end{eqnarray}$,

      因对于任意 $r,k_1,k_2$,当 $k_2$ 为 $k_1$ 因子时,$r \bmod k_2=(r \bmod k_1) \bmod k_2$,

      故 $r^{\varphi(n)} \bmod p=(r^{\varphi(n)} \bmod x) \bmod p=1 \bmod p=kp$,

      已知 $\varphi(n)$,由 $(r^{\varphi(n)} \bmod x) \bmod p=kp$ 可得到多组 $p$ 的乘积,计算 $\gcd$ 可得到 $p$;

    • 由 $q\cdot cf=1 \pmod p$ 求模逆可得 $q$,再用 $c$ 计算出 $m$。

      参考:TSG CTF 2020 - Modulus Amittendus

  • gcd(e,φ(n)) ≠ 1

    $\gcd(e,\varphi(n))\neq 1$ 时,$e$ 与 $\varphi(n)$ 不互素,

    $m^e \equiv (m^{\gcd(e,\varphi(n))})^{\frac{e}{\gcd(e,\varphi(n))}} \equiv c \pmod n$,计算 $\frac{e}{\gcd(e,\varphi(n))}$ 的模逆 $d’$,

    则 $c^{d’}\equiv m^{\gcd(e,\varphi(n))}\pmod n$。

    当 $\gcd(e,\varphi(n))$ 较小时,可以直接对 $c$ 开根,有两种情况:

    • $m^e = c<n$,这种情况直接对 $c$ 开 $e$ 次方即可;
    • $m^e = c>n$,这种情况需要在有限域下对 $c$ 开方,一般先计算 $c_p=c \bmod p$,$c_q=c \bmod q$,分别求出 $c_p,c_q$ 在 $c$ 下的 $e$ 次根(可能有多个),然后使用CRT遍历所有组合,分别check得出明文。

    当 $\gcd(e,\varphi(n))$ 较大时,求 $p,q$ 的 $e$ 次根步骤需要替换为一些有限域开根的高效算法(如AMM算法等)进行计算。

    参考:

    De1CTF2019 - Baby RSA

    0ctf 2016 - RSA?

  • e|(p-1), e|(q-1)

    上面的 $\gcd(e,\varphi(n))\neq 1$ 情况不针对 $\gcd(e,\varphi(n))= e$,这里对 $e\mid (p-1),e\mid (q-1)$ 的特殊情况进行讨论。

    解题思路即求解 $m \bmod p$ 和 $m \bmod q$ ,再通过CRT还原 $m \bmod n$。主要难点则是在 $\text{GF}(p)$ 上求 $e$ 次根。

    在有限域上求r-th root有两个常见算法(Adleman-Manders-Miller algorithm和Cipolla-Lehmer algorithm),Namhun Koo提出一种更具一般性的开根算法,且在 $s$ 足够小的时候更高效($r^{s}\mid (p-1),r^{s}\nmid (p-1)$)。

    参考NCTF 2019 - easyRSAAdleman-Manders-Miller rth Root Extraction Method

    本题则为 $e$ 和 $p-1$ (或 $q-1$)的最大公约数就是 $e$ 本身,也就是说 $e\mid (p-1)$,只有对 $c$ 开 $e$ 次方根才行。

    可以将同余方程 $m^e \equiv c \pmod n$ 化成

    $\begin{cases} m^e \equiv c \pmod p \\ m^e \equiv c \pmod q \end{cases}$

    然后分别在 $\text{GF}(p)$ 和 $\text{GF}(q)$ 上对 $c$ 开 $e$ 次方根,再用CRT组合一下即可得到在 $\bmod n$ 下的解。

    问题是,如何在有限域内开根

    这里 $e$ 与 $p-1$ 和 $q-1$ 都不互素,不能简单地求个逆元就完事。

    这种情况下,开平方根可以用Tonelli–Shanks algorithmWiki说这个算法可以扩展到开n次方根

    在这篇paper里给出了具体的算法:Adleman-Manders-Miller rth Root Extraction Method

    这个算法只能开出一个根,实际上开 $e$ 次方,最多会有 $e$ 个根(这题的情况下有0x1337个根)。

    如何找到其他根?

    StackOverflow – Cube root modulo P 给出了方法。

    如何找到所有的primitive 0x1337th root of 1?

    StackExchange – Finding the n-th root of unity in a finite field 给出了方法。

    Exploit(以 e=0x1337​ 为例)

    • 先用Adleman-Manders-Miller rth Root Extraction Method在 $\text{GF}(p)$ 和 $\text{GF}(q)$ 上对 $c$ 开 $e$ 次方根,分别得到一个解。大概不到10秒。
    • 然后去找到所有的0x1336primitive nth root of 1,乘以上面那个解,得到所有的0x1337个解。大概1分钟。
    • 再用CRT对 $\text{GF}(p)$ 和 $\text{GF}(q)$ 上的两组0x1337个解组合成 $\bmod n$ 下的解,可以得到0x1337**2=24196561个 $\bmod n$ 的解。最后能通过check()的即为flag。大概十几分钟。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    #脚本1
    #Sage
    c =
    p =
    q =
    e =

    for mp in GF(p)(c).nth_root(e, all=True):
    for mq in GF(q)(c).nth_root(e, all=True):
    m = crt([ZZ(mp), ZZ(mq)], [p, q])
    try:
    res = bytes.fromhex(hex(m)[2:])
    if res.isascii():
    print(res)
    except:
    pass
    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
    #脚本2
    #Sage
    import random
    import time

    # About 3 seconds to run
    def AMM(o, r, q):
    start = time.time()
    print('\n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
    p = g(random.randint(1, q))
    print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
    t += 1
    s = s // r
    print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
    k += 1
    alp = (k * s + 1) // r
    print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
    d = b ^ (r^(t-1-i))
    if d == 1:
    j = 0
    else:
    print('[+] Calculating DLP...')
    j = - discrete_log(a, d)
    print('[+] Finish DLP...')
    b = b * (c^r)^j
    h = h * c^j
    c = c ^ r
    result = o^alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    print('Find one solution: {}'.format(result))
    return result

    def findAllPRoot(p, e):
    print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
    start = time.time()
    proot = set()
    while len(proot) < e:
    proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return proot

    def findAllSolutions(mp, proot, cp, p):
    print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
    start = time.time()
    all_mp = set()
    for root in proot:
    mp2 = mp * root % p
    assert(pow(mp2, e, p) == cp)
    all_mp.add(mp2)
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return all_mp


    c =
    p =
    q =
    e = 0x1337
    cp = c % p
    cq = c % q
    mp = AMM(cp, e, p)
    mq = AMM(cq, e, q)
    p_proot = findAllPRoot(p, e)
    q_proot = findAllPRoot(q, e)
    mps = findAllSolutions(mp, p_proot, cp, p)
    mqs = findAllSolutions(mq, q_proot, cq, q)
    print(mps, mqs)

    def check(m):
    h = m.hex()
    if len(h) & 1:
    return False
    if bytes.fromhex(h).startswith(b'NCTF'):
    print(bytes.fromhex(h))
    return True
    else:
    return False


    # About 16 mins to run 0x1337^2 == 24196561 times CRT
    start = time.time()
    print('Start CRT...')
    for mpp in mps:
    for mqq in mqs:
    solution = CRT_list([int(mpp), int(mqq)], [p, q])
    if check(solution):
    print(solution)
    print(time.time() - start)

    end = time.time()
    print("Finished in {} seconds.".format(end - start))

  • SMUPE 问题(不同N,e加密线性关系明文)

    a system of univariate polynomial equations problem = 一元多项式方程组求解问题

    • 定义

      $k$ 是一个整数,$N$ 为满足RSA算法的模数,$\delta$ 是多项式的阶。有

      $N_i<N_{i+1},\delta_i \in N\quad(i=1,2,\cdots,k)$

      多项式方程组表示如下, 目的是求解 $x$:

      $\begin{cases} f_1(x)\equiv 0 \pmod {N_1}\newline f_2(x)\equiv 0 \pmod {N_2} \newline {\vdots} \newline f_k(x)\equiv 0 \pmod {N_k} \end{cases}$

    • 求解条件

      Alexander May, Maike Ritzenhofent提出一种求解方法,简单地说当多项式的阶 $\delta$ 满足以下情况时可解($\delta$ 是多项式的阶):

      $\sum\limits_{i=1}^k \cfrac{1}{\delta_i} \geq 1$

      具体描述:

      令 $(f_i,\delta_i,N_i) \quad(i=1,2,\cdots,k)$ 作为SMUPE问题的首一多项式组,

      定义 $M=\prod\limits_{i=1}^k N_i^{\frac{\delta}{\delta_i}},\delta=\text{lcm}(\delta_i) \quad (i=1,2,\cdots,k)$

      则SMUPE问题可以在 $O(\delta^6\cdot \log_2M)$ 复杂度解决。

    参考:2019红帽杯 - 精明的Alice

  • 反素数(emirp数)

    已知:$q=\text{reverse_x}(p)$,$\text{x}$ 为进制数。

    爆破思路类似RSA parity oracle。$p,q$ 是bit翻转关系,已知 $p$ 最低的 $k$ 位,则已知 $q$ 最高的 $k$ 位。

    假设已知 $k$ 位的 $p,q$,记为 $ph,qh$,利用不等式

    $ph\cdot qh\cdot 2^{1024-2k}<=n<(ph+1)\cdot(qh+1)\cdot 2^{1024-2k}$ ,

    逐位向低地址爆破,不断收缩不等式的范围,最终可求得 $n$ 值。

    参考:

    ASIS 2015 Finals: RSASR

    Midnight Sun CTF 2020 Quals

    RoarCTF 2020 - Reverse

    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
    #python2
    #x=10
    n = 6528060431134312098979986223024580864611046696815854430382374273411300418237131352745191078493977589108885811759425485490763751348287769344905469074809576433677010568815441304709680418296164156409562517530459274464091661561004894449297362571476259873657346997681362092440259333170797190642839587892066761627543
    def t(a, b, k):
    # sqrt(n) has 155 digits, so we need to figure out 77 digits on each side
    if k == 77:
    if a*b == n:
    print a, b
    return
    for i in xrange(10):
    for j in xrange(10):
    # we try to guess the last not-already-guessed digits of both primes
    a1 = a + i*(10**k) + j*(10**(154-k))
    b1 = b + j*(10**k) + i*(10**(154-k))
    if a1*b1 > n:
    # a1 and b1 are too large
    continue
    if (a1+(10**(154-k)))*(b1+(10**(154-k))) < n:
    # a1 and b1 are too small
    continue
    if ((a1*b1)%(10**(k+1))) != (n%(10**(k+1))):
    # The last digits of a1*b1 (which won't change later) doesn't match n
    continue
    # this a1 and b1 seem to be a possible match, try to guess remaining digits
    t(a1, b1, k+1)

    # the primes have odd number of digits (155), so we try all possible middle digits (it simplifies the code)
    for i in xrange(10):
    t(i*(10**77), i*(10**77), 0)

  • 4p-1 method

    对使用一类特定素数乘积的模数的分解。

    当一类特殊的素数用在 RSA 模数中时,可以轻易的将该素数从 $n$ 中分解出来。由于这一类素数都形如 $4p−1=Ds^2$,因此又被称为 4p-1 method。此外,有些人也会将其视为 RSA 的后门之一,称之为 RSA backdoor

    • QiCheng Prime

      $Ds=\{3,11,19,43,67,163\}$

      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
      import sys

      sys.setrecursionlimit(10^6)

      def QiCheng(n):
      R = Integers(n)
      attempts = 20
      js = [0, (-2^5)^3, (-2^5*3)^3, (-2^5*3*5)^3, (-2^5*3*5*11)^3, (-2^6*3*5*23*29)^3]

      for _ in range(attempts):
      for j in js:
      if j == 0:
      a = R.random_element()
      E = EllipticCurve([0, a])

      else:
      a = R(j)/(R(1728)-R(j))
      c = R.random_element()
      E = EllipticCurve([3*a*c^2, 2*a*c^3])

      x = R.random_element()
      z = E.division_polynomial(n, x)
      g = gcd(z, n)
      if g > 1:
      return g

      n =
      p = int(QiCheng(Integer(n)))
    • Masaaki Shirase & Vladimir Sedlacek Improvement

      更多 $Ds$ 值。

      CM-based factorization

    参考:

    浅谈 QiCheng Prime

    NCTF 2020 - RSA_revenge

    CryptoHack Challenge - RSA Backdoor Viability

  • Common Prime RSA

    情形:$\gcd(p-1,q-1)=g$

    分解的n方法有四种:

    (1)修改Pollard’s rho方法分解n;

    (2)知道a、b的值分解n;

    (3)知道g的值分解n;

    (4)分解N-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
    # Pollard’s rho
    from Crypto.Util.number import *
    import gmpy2

    def f(x, n):
    return (pow(x, n - 1, n) + 3) % n
    def rho(n):
    i = 1
    print 'Factorizing'
    while True:
    x1 = getRandomRange(2, n)
    x2 = f(x1, n)
    j = 1
    while True:
    p = gmpy2.gcd(abs(x1 - x2), n)
    if p == n:
    break
    elif p > 1 and isPrime(p):
    print 'Found!'
    return (p, n // p)
    else:
    x1 = f(x1, n)
    x2 = f(f(x2, n), n)
    j += 1
    i += 1

    参考:Common Prime RSA 笔记

  • RSA Padding Oracle Attack

    RSA PKCS #1 v1.5 填充用于需要RSA加密的信息,为了加密K,消息首先被0x00、一些随机字节和0x00 0x02填充,随机字节的选择方式是为了让填充的信息达到特定的块长度(1024、2048或4096位)。

    pkcs1padding

    PKCS #1 v1.5 标准中可以伪造RSA签名。

    Bleichenbacher攻击

    可以识别在 0x00 02 后以明文开始的密文信息,然后进行Padding Oracle攻击来解密预主密钥,进一步可以取得SSL的会话密钥。

    充分利用 0x00 02 开头的特性,假设攻击者获得密文 $C_0$,想恢复出明文 $M_0$。攻击方法是通过向服务器多次发送修改后的密文,分析响应是正确还是错误来确定修改结果,进而解密信息。

    如果收到正确,则表示是 0x00 02 开头,那么 $2B \lt m \lt 3B-1$,且 $B=2^{8(L-2)}$,而且基于RSA加密的延展性,可得 $C=(C_0S)\bmod N=(M_0S)^e \bmod N$ ,攻击者可用 $C$ 进行查询,如果收到错误则增加 $S$,并重复上一步骤。

    攻击者可以利用 0x00 02 大幅度减少可能的取值,$2B \lt M_0S-rN \lt 3B$,因此攻击者能够降低范围$\cfrac{2B+rN}{S} \lt M_0 \lt \cfrac{3B+rN}{S}$,然后迭代选择 $S$,进行Oracle查询,计算新的 $r$ 值,攻击者便可以不断缩小包含 $M_0$ 的范围,不断重复直到最后只剩唯一解。

    参考:

    Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1

    Bleichenbachers “Million Message Attack” on RSA

    Pwnhub - pkcs_fix

  • Return of Coppersmith’s attack (ROCA)

    CVE-2017-15361

    形如 $p=kM+(65537^a \bmod M)$ 生成素数的RSA系统,$M$ 是前 $n$ 个连续素数的乘积,$n$ 是仅取决于所需密钥大小的常数。

    https://github.com/jvdsn/crypto-attacks/blob/master/attacks/factorization/roca.py

    https://github.com/FlorianPicca/ROCA

PEM密钥

-----BEGIN <TAG>-----开头,-----END <TAG>-----结尾,中间是Base64编码的一串二进制,每64个字母(即解码后的48bytes)有一个换行。中间的Base64解码后是一串遵循ASN.1协议的DER编码,简单来说可以看成一种序列化,把一个结构体中的整数、字串等编码成一个方便传输的二进制。

生成代码:

1
2
3
4
5
6
7
8
9
10
11
from Crypto.PublicKey import RSA

rsa = RSA.generate(1024)
pk = rsa.publickey().exportKey()
sk = rsa.exportKey()

with open ('./pub.pem', 'wb') as f:
f.write(pk)

with open ('./priv.pem', 'wb') as f:
f.write(sk)

RSA私钥

1
2
3
-----BEGIN RSA PRIVATE KEY-----
...Base64 encoded key...
-----END RSA PRIVATE KEY-----

RFC3447定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponent INTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- (inverse of q) mod p
otherPrimeInfos OtherPrimeInfos OPTIONAL
}
Version ::= INTEGER { two-prime(0), multi(1) }
(CONSTRAINED BY
{-- version must be multi if otherPrimeInfos present --})

例:

1
3082025d02010002818100a0d154d5bf97c40f7797b44819d09c608fa4b5c38e70d83bc13267138c6eff4c1aacefe3ddb571e1b41d911c7ab6136cf90493189563450e1f4270cabbc4207c54c4da7b84a20311cfbbabe82b9fe60bdf48a08d57839d0cdf9464d84262bcc06bc308095a6987f60ad07d669a312b5a7e4133213788eecf25863248b91349ef02030100010281800f8270c496903bf3e3ec4912450f15edc81cb1fcf4b154615aee11fbd428e64d402b5a8d66d5f770358f3e6df935b324e8d5349c83d7c992a5982249a31734acb1db19c4c8d829267514bc1ef7bbfbe242d4350f67a002a56d33e56d1a94adc71c68f020dc39ab7d0064c111b164e26ba0698dc94a03cdfd516ffd966e877949024100ca97e49c058237f96e99118ce383f91912cba1163de9236181ff754ef3ef1a260fac8d2d9aee866d51a8b6836983b05cf850e786289b6859925bc8695fc67c47024100cb3630aafffcb29607f0833dc7f05c143ee92fadfe975da4cf6719e71226bee72562e8631328a25d7351507a8d43c1295ab6ea242b60a28b109233a983f4211902401b4a32a541a8b4d988a85dd0d8a4e25d1a470bbfef3f0461121dd3337b706dd94aab37a9390180622169d48c071e921733ebd204245c2ac6460ccf0642bc7de90241008d9f44a7c823eaaa58fa2bdd20bcc8cf6b50c463f4acb51ca956e75c7ceff7d7cbdc74aca7ab880cacd39cccec2aae320e00b0896899be6e40ac43c8fe2763f1024100c67ca6d988f53abea82159431a146512a8d942978d4a8f83f2d426f1095e3bf1b5b9b8b1ccbbad2a31c6401880447a45f5e0790269061ac13b5f68f1777d7f07

30是Sequence的tag,82是指接下来后两个bytes是这个Sequence的长度,即0x025d个bytes,也就是剩下全部都是;接着的020100就是整数0,其中02是整数的tag,01是这个整数占1byte,00是value同样的方法也可以解02818100a0...和后面其他整数,拆分:

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
3082025d  	# Begin Sequence: len=0x025d

0201 # Version: (len=0x01)
00

028181 # n: (len=0x81)
00a0d154d5bf97c40f7797b44819d09c608fa4b5c38e70d83bc13267138c6eff4c1aacefe3ddb571e1b41d911c7ab6136cf90493189563450e1f4270cabbc4207c54c4da7b84a20311cfbbabe82b9fe60bdf48a08d57839d0cdf9464d84262bcc06bc308095a6987f60ad07d669a312b5a7e4133213788eecf25863248b91349ef

0203 # e: (len=0x03)
010001

028180 # d: (len=0x80)
0f8270c496903bf3e3ec4912450f15edc81cb1fcf4b154615aee11fbd428e64d402b5a8d66d5f770358f3e6df935b324e8d5349c83d7c992a5982249a31734acb1db19c4c8d829267514bc1ef7bbfbe242d4350f67a002a56d33e56d1a94adc71c68f020dc39ab7d0064c111b164e26ba0698dc94a03cdfd516ffd966e877949

0241 # p: (len=0x41)
00ca97e49c058237f96e99118ce383f91912cba1163de9236181ff754ef3ef1a260fac8d2d9aee866d51a8b6836983b05cf850e786289b6859925bc8695fc67c47

0241 # q: (len=0x41)
00cb3630aafffcb29607f0833dc7f05c143ee92fadfe975da4cf6719e71226bee72562e8631328a25d7351507a8d43c1295ab6ea242b60a28b109233a983f42119

0240 # d mod (p-1): (len=0x40)
1b4a32a541a8b4d988a85dd0d8a4e25d1a470bbfef3f0461121dd3337b706dd94aab37a9390180622169d48c071e921733ebd204245c2ac6460ccf0642bc7de9

0241 # d mod (q-1): (len=0x41)
008d9f44a7c823eaaa58fa2bdd20bcc8cf6b50c463f4acb51ca956e75c7ceff7d7cbdc74aca7ab880cacd39cccec2aae320e00b0896899be6e40ac43c8fe2763f1

0241 # (inverse of q) mod p: (len=0x41)
00c67ca6d988f53abea82159431a146512a8d942978d4a8f83f2d426f1095e3bf1b5b9b8b1ccbbad2a31c6401880447a45f5e0790269061ac13b5f68f1777d7f07

# End Sequence

RSA公钥

1
2
3
-----BEGIN PUBLIC KEY-----
...Base64 encoded key...
-----END PUBLIC KEY-----

例:

1
30819f300d06092a864886f70d010101050003818d0030818902818100a0d154d5bf97c40f7797b44819d09c608fa4b5c38e70d83bc13267138c6eff4c1aacefe3ddb571e1b41d911c7ab6136cf90493189563450e1f4270cabbc4207c54c4da7b84a20311cfbbabe82b9fe60bdf48a08d57839d0cdf9464d84262bcc06bc308095a6987f60ad07d669a312b5a7e4133213788eecf25863248b91349ef0203010001

拆分:

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
30819f 		# Begin Main Sequence: len=0x9f

300d # Begin Sub1 Sequence: len=0x0d

0609 # algo_oid: (1.2.840.113549.1.1.1 - PKCSv1.2)
2a864886f70d010101

0500 # params: (null)


# End Sub1 Sequence

03818d # BitString: len=0x8d ([n, e])

00308189 # Begin Sub2 Sequence: len=0x89

028181 # n:
00a0d154d5bf97c40f7797b44819d09c608fa4b5c38e70d83bc13267138c6eff4c1aacefe3ddb571e1b41d911c7ab6136cf90493189563450e1f4270cabbc4207c54c4da7b84a20311cfbbabe82b9fe60bdf48a08d57839d0cdf9464d84262bcc06bc308095a6987f60ad07d669a312b5a7e4133213788eecf25863248b91349ef

0203 # e:
010001

# End Sub2 Sequence

# End Main Sequence

参考

手撕PEM密钥

详细原理

二十年以来对 RSA 密码系统攻击综述

CTF Wiki - RSA

0xDktb’s Blog

RSA常见攻击方法

Cryptanalysis of RSA and It’s Variants