RSA选择明密文攻击

选择明文攻击

适用情况:
对输入的任意明文服务器返回 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 = tn$
一般来说 $a^2$ 比 $n$ 大,所以 $k$ 不为 $0$。
同理还可以构造更多的例子取他们的公因数,来更加确定地找 $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
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


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,那么可以归纳为:

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 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$,$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]$,$(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,那么可以归纳为:

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