RSA(2)

# RSA(2)

# 小明文攻击

n 很大，不能直接分解，此时假设 m 很小此时：

$$m^e<n$$

可直接利用开放求解 m。

1

iroot(c,e)

[!TIP]

n 特别大的时候，可以考虑使用小明文攻击。

# 低加密指数攻击

n 很大，不能暴力解决时：

$$m^e>n$$

消去取模，即：

$$m^e=c+k*n$$

[!TIP]

m^e 不会太大，一般数值范围（10w，100w，1000w）；

当发现题目中 e 较小时，可以考虑此种攻击。

# Rabin 算法

题目会有 e 非常小。

加密流程，两个素数满足 p 和 q 都对同一个数取余的结果是恒等。n=p*q。

$$c\equiv m^2 \pmod n$$

解密需要参考二次剩余和欧拉准则。

解密脚本函数代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def rabin_attack(c, n, p, q):
    c1 = powmod(c, (p+1)//4, p)
    c2 = powmod(c, (q+1)//4, q)
    cp1 = p - c1
    cp2 = q - c2

    t1 = invert(p, q)
    t2 = invert(q, p)

    m1 = (q*c1*t2 + p*c2*t1) % n
    m2 = (q*c1*t2 + p*cp2*t1) % n
    m3 = (q*cp1*t2 + p*c2*t1) % n
    m4 = (q*cp1*t2 + p*cp2*t1) % n

    return m1, m2, m3, m4

# Wiener 攻击

该类攻击通过先选定 d 再来获取 e。与传统秘钥生成方式相反。

$$e d \equiv 1~~mod~~{\varphi(n)}$$

所以 ed-1=k⋅φ(n) 得

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

近似概念 φ(n)=(p−1)(q−1)=n−p−q+1，φ(n)≈n。

$$\frac{n}{e} \approx \frac{d}{k}$$

故 Wiener 攻击需要满足

$$N = p ⋅ q \quad \text{and} \quad q < p < 2q \quad \text{and} \quad d < \frac{1}{3} N^{\frac{1}{4}}$$

低加密指数广播攻击

如何与远程靶机进行交互

通过使用 pwntools 对远程靶场进行交互

1
2

from pwn import *
io = remote('#####.cn', 端口号)

交互可以先通过 nc 查看题目输入输出的内容

例如： nc ####.cn 8080

每次交互我们会发现程序会生成一组公钥来加密同一个明文，并且这些公钥中的 e 都相同。

因此

$$c_i \equiv m^e \pmod{n_i}$$

通过需要求解 m 可以看出，我们需要先求出 m^e。可以通解为：

$$m^e \equiv \sum_{i=1}^{n} c_i t_i M_i \pmod{N}$$

通过求出 m^e, 再通过开放求解 m 值。

# 光滑攻击

# p-1 光滑攻击

问题我们会得到

$$p=p_1p_2...p_n+1$$

当一个数的最大素因子组不大于 B 时，我们可以称其为 B - 光滑数。

因此我们假设 p−1 为 k - 光滑数，存在这样的一个数 M

$$M = \prod_{i} p_i^{\log_{p_i}{k}}$$

得到 (p−1)∣*M，那么 gcd (M,n)=*p。

设 M=t⋅(p−1)，根据费马小定理我们有，

$$a^M \equiv a^{t(p-1)} \equiv 1 \pmod{p}$$

得到 M∣k!，即：gcd (a^k!−1,n)=p。

具体计算中我们可以有：

$$a^{(x+1)!} \equiv (a^{x!} \mod n)^{x+1} \pmod{n}$$

# p+1 光滑攻击

同理将 p-1 换成 p+1:

$$a^M \equiv a^{t(p+1)} \equiv 1 \pmod{p}$$

1
2
3
4
5
6
7
8
9
10
11
12
13

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

# 共模攻击

使用了同样模数的公钥对同一消息进行加密，同时还需要满足公钥中的 e 互素。s_1e_1+s_2e_2=1

$$c_1^{s_1} \cdot c_2^{s_2} \equiv (m^{e_1})^{s_1} \cdot (m^{e_2})^{s_2} \equiv m^{e_1 s_1 + e_2 s_2} \equiv m \pmod{n}$$

我们通过 a^x*+*by=gcd(a,b) 求解（s_1,s_2）。

该方程一定有且仅有一组整数解 (x,y)。我们用到 gmpy2 中的 gcdext 。

# dp&dq 泄漏攻击

知道下面公式即可。

$$d_p = d \mod (p-1)$$

$$d_q = d \mod (q-1)$$

# dp 泄漏攻击

题目一般已知 e，但是会少一个 dq。

$$d_p e = 1 + k(p-1)$$

# e 很大的 dp 泄露攻击

欧拉降幂：

$$a^{ed_p} \equiv a^{ed_p\mod{p-1}} \equiv a \pmod{p}$$

得到解题思路：

$$(a^{ed_p} - a) \mid p$$

# d 泄露攻击

当私钥已经泄露的情况，能否利用公私钥来进行因数分解。

e^d*−1=*kφ(n)

a^(ed*−1)≡1(mod n)

n 为一个平凡因子，故：

$$\gcd(a^{2^{i-1} t} - 1, n)$$