RSA

常用工具

  • 分解大素数

    factordbhttp://www.factordb.com

    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
    # coding=utf-8
    import math
    import sys
    from Crypto.PublicKey import RSA
    from Crypto.Cipher import PKCS1_OAEP

    rsa_components = (n1, e, int(d1), p, q1)
    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$ 过小,$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$。

    参考:

    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

    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())

给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小,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))

低加密指数广播攻击(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-1}{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
17
18
19
#Sage
from sage.all import *
n =
p4 =
#p去0的剩余位
e =
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)
#经过以上一些函数处理后,n和p已经被转化为10进制
if roots:
p = p4+int(roots[0])
print("n: "+str(n))
print("p: "+str(p))
print("q: "+str(n//p))

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
  • 给定更多组

    西湖论剑 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

  • 错误模攻击

    有明文 $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
    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
    #脚本1
    #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))
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    #脚本2
    #Sage
    c = 346925245648012783854132941104554194717281878370806475831055718275298366664505658836564073456294047402009856656647760
    p = 21122913513992623721920275602985463699928507831138027
    q = 16471885912035642894544190467774867069446937372970845578732298073
    e = 239

    P.<a>=PolynomialRing(Zmod(p),implementation='NTL')
    f=a^e-c
    mps=f.monic().roots()

    P.<a>=PolynomialRing(Zmod(q),implementation='NTL')
    g=a^e-c
    mqs=g.monic().roots()

    for mpp in mps:
    x=mpp[0]
    for mqq in mqs:
    y=mqq[0]
    solution = hex(CRT_list([int(x), int(y)], [p, q]))[2:]
    if solution.startswith('666c'):
    print(solution)

  • 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
    # Pollard’s rho
    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

  • 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