每当我对这世界感到沮丧，就去看看你眼中的光芒。

RSA基本介绍

公钥与私钥的产生

随机选择两个不同大质数 p 和 q ，计算 $N=p× q$ 。
根据欧拉函数, 求得 $r=φ(N)=φ(p)φ(q)=(p-1)(q-1)$ 。
选择一个小于r的整数e, 使e和r互质。并求得e关于r的模反元素, 命名为$d(ed≡1(mod r))$ 。
将p和q的记录销毁。

此时(N, e)为公钥, (N, d)为私钥。

消息加密

首先需要将消息 m 以一个双方约定好的格式转化为一个小于 N ，且与 N 互质的整数 n 。如果消息太长，可以将消息分为几段，这也就是我们所说的块加密，后对于每一部分利用如下公式加密:

$$n^e≡c (mod N)$$

消息解密

利用密钥 d 进行解密。

$$c^d≡n (mod N)$$

正确性证明

即我们要证$n^ed≡n mod N$, 已知$ed≡1 mod φ(N)$, 那么$ed=kφ(N)+1$, 即需要证明:

$$n^{kφ(N)+1}≡n mod N$$

这里我们分两种情况证明:

第一种情况:

$gcd⁡(n,N) = 1$, 那么$n^{φ(N)}≡1 mod N$, 因此原式成立;

第二种情况:

$gcd⁡(n,N) != 1$, 那么n必然是p或者q的倍数，并且n小于N。我们假设:

n=xp

那么x必然小于q，又由于q是素数。那么:

$$n^{φ(q)}≡1 mod q$$

进而:

$$n^{kφ(N)}=n^{k(p-1)(q-1)}=(n^{φ(q)})^{k(p-1)}≡1 mod q$$

那么$n^{kφ(N)+1}=n+uqn$, 进而$n^{kφ(N)+1}=n+uqn=n+uxN$, 所以原式成立.

漏洞场景分析

小公钥指数攻击:

攻击条件

e特别小, 例如e = 3

攻击原理

假设用户使用的公钥e = 3. 考虑到加密关系满足:

$$c≡m^3 mod N$$

则:

$$m^3=c+k × N$$

$$m=\sqrt[3]{c+k ×N}$$

可攻击者可以从小到达枚举k, 依次开三次方, 知道开出整数为止.

场景

其中包含公钥pubkey.pem, 密文flag.enc：

可以通过openssl 来获取公钥到N 和 e, 同时也可以通过python 脚本来获取, 这里将介绍这两种方法:

通过openssl 来获取 [N, e]:

1	openssl rsa -pubin -in pubkey.pem -text –modulus

可以看到其中指数 e = 3 很明显是小公钥指数攻击

通过python 脚本来获取, 这里推荐使用 gmpy2 和 Crpyto 两个库获取公钥内容:

获取密文:

漏洞场景利用

接下来通过完整的脚本来破解密文得到明文:

# coding=utf-8  
import gmpy2  
from Crypto.PublicKey import RSA  
  
# 提取key，N， e  
with open('pubkey.pem', 'r') as f:  
    key = RSA.importKey(f)  
    N = key.n  
    e = key.e  
  
# 提取密文 c  
with open('flag.enc', 'r') as f:  
    cipher = f.read().encode('hex')  
    cipher = int(cipher, 16)  
  
# 计算 k  
def calc(j):  
    print j  
    a, b = gmpy2.iroot(cipher + j * N, 3)    # a 为 cipher + j * N 开三次方的值,  b 取 True or False. 如果可得整数b = True; 反之, False.   
    if b == 1:  
        m = a  
        print '{:x}'.format(int(m)).decode('hex')  
        exit()  
  
def SmallE():  
    for i in range(0, 130000000):  
       calc(i)  
  
if __name__ == '__main__':  
    print 'start'  
    SmallE()

其中枚举k

通过密文c和公钥[N, e]有$m=\sqrt[3]{c+k ×N}$, 可以得到明文.