RSA选择明密文攻击

选择明文攻击

适用情况：

对输入的任意明文服务器返回 RSA 加密结果。

可以通过选择明文攻击来获取 $n$。

原理

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

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

不妨设 $2^e = a + bn$，有：

$\begin{aligned} c_2 & = (a + bn) \bmod n = a \\ c_4 & = (a^2 + 2abn + b^2n^2) \bmod n = a^2 \bmod n \end{aligned}$

所以 $c_2^2$ 和 $c_4$ 模 $n$ 同余

即：

$c_2^2 - c_4 = kn$

同理：

$c_2^3 - c_8 = tn$

一般来说 $a^2$ 比 $n$ 大，所以 $k$ 不为 $0$。

同理还可以构造更多的例子取他们的公因数，来更加确定地找 $n$。

代码

虽然有繁琐，但经过实践，$n$的准确性很高。

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$。

代码

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

RSA Parity Oracle

适用情况：

可以选择密文并泄露最低位。

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

原理

假设：

$C = M^e \bmod n$

第一次时，构造密文：

$C \times 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} ≤ M < n$。
• 服务器返回偶数，则 $2M < n$，即 $0 \leq M < \frac{n}{2}$。

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

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

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

假设服务器返回 b，那么可以归纳为：

L = 0
R = n
for i in range(1024):
    if b:
        L = (L+R) / 2
    else:
        R = (L+R) / 2

代码

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

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 Byte Oracle

适用情况：

可以选择密文并泄露最后一个字节。

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

原理

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

假设：

$C = M^e \bmod n$

第一次时，构造密文：

$C \times 256^e = (256M)^e \bmod n$

服务器解密后得到：

$256M \bmod n$

这里：

• $256M$ 是偶数。
• $n$ 是奇数，因为它是由两个大素数相乘得到。

由于 $M = C^d \bmod n$，所以 $M$ 小于 $n$，那么：

$256M \bmod n = 256M − kn, \quad (k < 256)$

而且对于两个不同的 $k_1$、$k_2$，有：

$256M − k_1 n \bmod 256 \neq 256M − k_2 n \bmod 256$

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

那么，我们可以首先枚举出 $0 - 255$ 情况下的最后一个字节，构造一个 $k$ 和最后一个字节的映射表 map。

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

以此类推，第 $i$ 次时，构造密文：

$C \times 256^{ie}$

服务器解密后得到：

$256^i \times M \bmod n = 256^i \times M − kn$

即：

$kn \leq 256^i \times M < n+kn \\ \frac{kn}{256^i} \leq M < \frac{(k+1)n}{256^i}$

那么，可以设初始范围为：

$\frac{M}{n} \in [L_0,R_0], \quad (L_0 = 0, R_0 = 1)$

第i次迭代后：

$L_i = L_{i-1} + \frac{k_i}{256^i} \\ R_i = L_{i-1} + \frac{k_i + 1}{256^i}$

还有最后一个问题，就是迭代的次数。由于明文的最后一个字节可以直接由服务器解密得到，那么只需要限定 $M$ 的范围至：

$M_{max} - M_{min} < 256$

即：

$n \times (R_i - L_i) = \frac{n}{256^i} < 256$

由于 $n$ 是由 512 bit 的 $p$ 和 $q$ 相乘得到，所以 $n < 2^{1024}$，那么由上式可得：$i \geq 128$。

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

综上，假设服务器返回了b，那么可以归纳为：

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 上限。

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

参考文章

https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_chosen_plain_cipher/