RSA原理

RSA是最早提出并被广泛接受的公钥加密算法之一，其步骤如下

第一步，选择两个大素数$p,q$
第二步，计算$n=pq$和$\phi(n)=(p-1)(q-1)$
第三步，随机选择正整数$e<\phi(n)$满足$e$与$\phi(n)$互素
第四步，计算$e$在模$\phi(n)$意义下的逆元$d$，即$ed\equiv 1(\mod \phi(n))$

最后，公钥为${d,n}$，私钥为${e,n}$
加密和解密过程分别为 $C=M^e \mod n$ 和 $M=C^d\mod n=M^{ed}\mod n$

显然该算法要求$M<n$，应此实际应用中要将明文分组，每一分组转换成十进制数后要小于n

RSA实现

RSA的实现有很多计算上的问题需要考虑

首先是大素数$p,q$的选择问题，目前为止还没有有效的方法可以产生任意大素数
一般的做法是随机选择一个期望位数的奇数，然后测试它是否为素数，若不是则继续随机

一般的确定性素性测试需要$O(\sqrt n)$进行试除，这样的复杂度并不能被接受
基于概率性测试的Miller-Rabin算法是被广泛使用的素性检测算法
算法原理和cpp实现可参考Miller-Rabin素数测试与Pollard Rho大整数分解，此处给出python实现

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
31
32
33
34
def witness(a, n, u, t):
    x = qpow(a, u, n)  # a^u mod n
    for i in range(t):
        nx = x * x % n  # (a^u) ^ (2^k)
        if nx == 1 and x != 1 and x != n - 1:  # x^2为以n为膜的1的非平凡平方根，判断n是合数
            return True
        x = nx

    return x != 1  # 此时x = (a^u) ^ (2^t) = n-1，费马测试 x!=-1 则判断n是合数

def millerRabin(n, s):
    """
    executed s times of Miller Rabin to check if n is a prime
    """
    if n == 2:
        return True

    # n = 0/1 or n is even
    if n < 2 or n % 2 == 0:
        return False

    u, t = n-1, 0
    while not (u & 1):
        u >>= 1
        t += 1

    primes = [2, 3, 5, 7, 11, 13, 19, 61, 1103, 2333, 24251]
    for i, prim in enumerate(primes):
        if prim >= n or i >= s:
            break
        if witness(primes[i], n, u, t):
            return False

    return True

RSA实现所需考虑的另一个问题是乘法逆元的计算
基于扩展欧几里得算法的乘法逆元原理可以参考 扩展欧几里得和乘法逆元求解
RSA为了保证对穷举攻击的安全性，一般密钥都很大（至少1024位），因此扩展欧几里得最好用非递归形式

此处再给出RSA计算公钥和私钥的主体部分

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
class RSA:
    '''
    .......
    '''
    def generateKey(self):
        st, ed = 1 << (self.key_length - 1), (1 << self.key_length) - 1

        p = random.randint(st, ed)
        while not millerRabin(p, 11):
            p = random.randint(st, ed)

        q = random.randint(st, ed)
        while not millerRabin(q, 11):
            q = random.randint(st, ed)

        n = p * q
        phi_n = (p - 1) * (q - 1)

        e = random.randint(2, phi_n - 1)
        while gcd(e, phi_n) != 1:
            e += 1

        d = calInv(e, phi_n)

        print(f'p = {p}, q = {q}\nn = {n}, phi(n) = {phi_n}\ne = {e}, d = {d}')
        print('public key:', (e, n))
        print('secret key:', (d, n), '\n')
        return (e, n), (d, n)

RSA的安全性

RSA的安全性来源于对大整数进行因数分解的困难性

然而随机计算能力的不断增强和因子分解算法的不断改进，即使是大密钥的RSA也开始受到威胁
从2010年代开始，1024位的RSA也开始被建议逐步淘汰

选择密文攻击也是对RSA的一种有效攻击，其利用了RSA的如下性质

具体来说，攻击者截获了密文$C_1$，希望获得其对应明文$M_1$
攻击者可以选取明文$M$，构造$C_2=C_1\times C=C_1\times M^e\mod n$，并将$C_2$发送给接收者
接收者对$C_2$解密得到明文$M_2$，则攻击者可计算出$M_1=\frac{M_2}{M}\mod n$

抵御选择密文攻击的一种方法是最优非对称加密填充OAEP，该方法较为复杂，此处不展开说明

此外对RSA的攻击还有计时攻击，实际上计时攻击也可以用来攻击其他公钥加密算法，对于RSA来说则可以使用随机延时、隐蔽等手段进行防御