CTF中的RSA基本套路(1)

碰到东西老是忘老是忘，要用的时候总是得自己去搜索模板浪费时间，所以只能整理整理一下套路和解题模板才能活下去这样子

依赖库：

• gmpy2
• pycrypto

RSA原理#

私钥$n$,$d$，公钥$n$,$e$。其中n是两个素数$p$,$q$的乘积。$c$为密文，$m$为明文。$\varphi(n)$为欧拉函数。其中:$d$是$e$模$\varphi(n)$的逆元。我们有
$$ \varphi(n) = (p-1)(q-1) $$

$$ed \equiv 1 \mod \varphi(n)$$

$$ encrypt:c \equiv m^e \mod n $$

$$ decrypt:m \equiv c^d \mod n $$

openssl使用#

使用openssl查看pem文件：

openssl rsa -pubin -text -modulus -in public.pem

使用openssl和私钥解密

openssl rsautl -decrypt -in flag -inkey privatekey -out flag.txt

常规#

场景#

已知$p$、$q$、$c$

解法#

求$\varphi(n)$，再求出$d$即可

from Crypto.Util.number import inverse,long_to_bytes
p = 
q = 
n = p*q
phi = (p-1)*(q-1)
e = 
d = inverse(e,phi)
c = 
m = pow(c,d,n)
print(long_to_bytes(m))

模不互素#

场景#

已知如下：

$$n_1 = p \times q_1 $$

$$ n_2=p \times q_2 $$

$$c_1= m^e \mod n_1 $$

$$c_2 = m^e \mod n_2$$

解法#

求出$n_1$和$n_2$的公因子，即可解得$p$和$q$

from libnum import xgcd
from Crypto.Util.number import inverse,long_to_bytes
n1 = 
n2 = 
c1 = 
c2 = 
e = 
p = xgcd(n1,n2)[2]
q1 = n1//p
q2 = n2//p
phi1=(p-1)*(q1-1)
phi2=(p-1)*(q2-1)
d1 = inverse(e,phi1)
d2 = inverse(e,phi2)
m1 = pow(c1,d1,n1)
m2 = pow(c2,d2,n2)
print(long_to_bytes(m1))
print(long_to_bytes(m2))

共模攻击#

场景#

模数$n$相同，指数$e_1、e_2$不同且互质

已知：

$$c_1=m^{e_1}\mod n$$

$$c_2 = m^{e_2}\mod n$$

解法#

根据扩展欧几里得算法求出$re_1+se_2=1 \mod n$的整数$r、s$

根据
$$\begin{equation}
c_{1}^{r} c_{2}^{s} \equiv m^{r e_{1}} m^{s e_{2}} \bmod n \equiv m \mod n
\end{equation}$$
得到明文

from libnum import xgcd
from Crypto.Util.number import inverse,long_to_bytes

n = 
c1 = 
c2 = 
e1 = 
e2 = 
s = xgcd(e1,e2)
s1 = s[0]
s2 = s[1]
if s1 < 0:
    s1 = - s1
    c1 = inverse(c1, n)
elif s2 < 0:
    s2 = - s2
    c2 = inverse(c2, n)

m = pow(c1, s1, n)*pow(c2, s2, n) % n print(long_to_bytes(m))

e小指数攻击#

场景#

当$e$很小的时候，例如2、3，此时可能可以通过直接暴力开根的方式进行攻击

解法#

以$e=3$为例，已知$c\equiv m^3 \mod n$，因此有：
$$m^3=c+kN$$

$$m=\sqrt[3]{c+kN}$$

import gmpy2
from Crypto.Util.number import long_to_bytes
n = 
e = 3
c = 
i = 0
while(True):
    a,b = gmpy2.iroot(c+i*n,3)
    if(b==1):
        print(long_to_bytes(a))
        exit(0)

Rabin攻击#

场景#

当指数$e=2$，且已知$p$和$q$

解法#

• 计算

  $$m_p = \sqrt[2]{c} \mod p$$

  $$m_q= \sqrt[2]{c} \mod q$$

• 扩展欧几里得求$y_p$和$y_q$

  $$y_p p+y_q q=1$$

• 解得4个明文

  $$a =\left(y_{p} \cdot p \cdot m_{q}+y_{q} \cdot q \cdot m_{p}\right) \bmod n $$

  $$b =n-a $$

  $$c =\left(y_{p} \cdot p \cdot m_{q}-y_{q} \cdot q \cdot m_{p}\right) \bmod n $$

  $$d =n-c$$

• 条件：当$p\equiv q\equiv3 \mod 4$时，有

  $$m_p=c^{(p+1)/4} \mod p$$

  $$m_q=c^{(q+1)/4} \mod q$$

满足条件时#

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)

不满足条件时#

转换为模平方根问题

• 用python（代码来自yuri）

import gmpy2
import random

def exgcd(r0, r1):
    x0, y0 = 1, 0
    x1, y1 = 0, 1
    x, y = r0, r1
    r = r0 % r1
    q = r0 // r1
    while r:
        x, y = x0 - q * x1, y0 - q * y1
        x0, y0 = x1, y1
        x1, y1 = x, y
        r0 = r1
        r1 = r
        r = r0 % r1
        q = r0 // r1
    return x

def Jacobi(n, m):
    n = n % m
    if n == 0:
        return 0
    Jacobi2 = 1
    if not (n & 1):
        k = (-1) ** (((m**2 - 1) // 8) & 1)
        while not (n & 1):
            Jacobi2 *= k
            n >>= 1
    if n == 1:
        return Jacobi2
    return Jacobi2 * ((-1) ** ((((m - 1) // 2) * ((n - 1) // 2)) & 1)) * Jacobi(m % n, n)

def CRT(b, m): 
    M = 1
    for i in range(len(b)):
        M *= m[i]
    ans = 0
    for i in range(len(b)):
        ans += b[i] * M // m[i] * exgcd(M // m[i], m[i])
    return ans % M

def solve(a, p):
    a_1 = gmpy2.invert(a, p)
    s = p - 1
    t = 0
    while s % 2 == 0:
        t += 1
        s >>= 1
    n = 0
    while True:
        n = random.randint(1, p-1)
        if Jacobi(n, p) == -1:
            break

    b = pow(n, s, p)
    x_t_1 = pow(a, (s+1)//2, p)

    assert pow(b, 2**t, p) == 1
    assert pow(b, 2**(t-1), p) == p-1

    x, j, temp = 0, 0, 0

    for i in range(0, t-1):
        x = pow(a_1*(x_t_1**2), 2**(t-2), p)
        if x == 1:
            j = 0
        elif x == p-1:
            j = 1
        else:
            exit(0)
        t -= 1
        temp = x_t_1
        x_t_1 = (x_t_1 * (b**(j**(2**i)))) % p
    else: 
        if x == 1:
            return temp, -temp % p


p = 
q = 
n = p * q
e = 2
c = 

a, b = None, None
while True:
    try:
        a = solve(c % p, p)
        assert pow(a[0], e, p) == c % p
        assert pow(a[1], e, p) == c % p
        break
    except:
        pass

while True:
    try:
        b = solve(c % q, q)
        assert pow(b[0], e, q) == c % q
        assert pow(b[1], e, q) == c % q
        break
    except:
        pass

print(bytes.fromhex(hex(CRT([a[0],b[0]],[p,q]))[2:]))
print(bytes.fromhex(hex(CRT([a[0],b[1]],[p,q]))[2:]))
print(bytes.fromhex(hex(CRT([a[1],b[0]],[p,q]))[2:]))

• 用sage

使用一句话Mod(c_square, q).sqrt(all=True)分别求出$m_p$和$m_q$，代回去解得可能的明文

n分解攻击#

当n很小或者满足一定条件时，可以进行暴力分解

• yafu

• factordb

• 当$d<1/3 N^{1/4}$时，通过Wiener’s attack能够攻击得到$d$

• 当$p、q$十分接近时，可以使用费马分解分解$n$

• 当$q$较小，即$|p-q|$较大时，可以爆破$q$

• 当$d<N^{0.292}$时，通过Boneh Durfee Method分解$n$

广播攻击#

场景#

给定了不同的模数$n_i$，但指数$e$相同

已知:

$$c_1=m^e\mod n_1$$

$$c_2=m^e\mod n_2$$

$$c_3=m^e\mod n_3$$

解法#

使用中国剩余定理进行广播攻击

from gmpy2 import *
from Crypto.Util.number import long_to_bytes
def broadcast(n1, n2 ,n3, c1, c2, c3):
    n = [n1, n2, n3]
    C = [c1, c2, c3]
    N = 1
    for i in n:
        N *= i

    Ni = []
    for i in n:
        Ni.append(N / i)

    T = []
    for i in range(3):
        T.append(long(invert(Ni[i], n[i])))

    X = 0
    for i in range(3):
        X += C[i] * Ni[i] * T[i]

    m = X % N
    return m

n1 = 
n2 = 
n3 = 
e = 
c1 = 
c2 = 
c3 = 
result = broadcast(n1,n2,n3,c1,c2,c3)
m = iroot(result, e)
print(long_to_bytes(result))

参考资料#

• https://github.com/ctf-wiki/ctf-wiki
• https://www.freebuf.com/articles/others-articles/161475.html
• https://github.com/ius/rsatool/blob/master/rsatool.py
• https://github.com/pablocelayes/rsa-wiener-attack
• https://xz.aliyun.com/t/2446#toc-18