RSA

RSA 加密算法

RSA（发明该算法的三个人名首字母）

• 非对称加密算法

公钥密码体制的由来

对称加密算法存在的问题：

• 密钥分发的问题
  • 保密双方需要共享密钥，而且密钥需要时常更新
  • $A$ 选择密钥直接发送给 $B$ （互联网环境中无法保证 $B$ 真的是 $B$ ）
  • 第三方 $C$ 分发密钥给 $A$ 和 $B$ （同样无法保证 $A$ 是 $A$ ， $B$ 是 $B$ ）
  • A 和 B 使用原先共享的密钥对新密钥加密再共享（需要复杂的密钥交换协议）
  • 第三方 $C$ 使用与 $A$ 和 $B$ 分别共享的密钥，加密分发新密钥（同样需要复杂的密钥交换协议）
• 密钥管理的问题
  • 密钥管理量大，当用户数为 $N$ 时，要支持任意两者的加密通信，需要 $\dfrac{N(N-1)}{2}$ 个密钥
• 数字签名问题，无法实现抗抵赖

公钥密码体系要求

• 两个密钥，一个公钥（公开），一个私钥（保密）
• 使用不同的密钥进行加密和解密
• 知道加密算法，无法推导出公钥和私钥的关系
• 两个密钥中任何一个都可以用来加密或解密

应用

• 加密
  • 用公钥进行加密，因为公钥大家都有，用私钥加密，谁都可以解密，不能实现加密
• 认证
  • 用私钥进行加密，因为公钥大家都有，用公钥加密，不知道是谁加密的，不能实现认证

RSA 加密过程

1. 用户选择随机的两个大的素数 $p, q$
2. 计算 $N = p \times q$
3. 计算 $N$ 的欧拉数，$\phi(N) = (p-1)(q-1)$
4. 随机选择一个加密密钥 $e$ ，$1 \le e \le \phi(N), \gcd(e, \phi(N)) = 1$
5. 解一个同余方程，得到解密密钥 $d$ ， $ed = 1 \mod \phi(N), 0 \le d \le N$
6. 加密消息得到密文 $C$ ， $C = M^e \mod N$
7. 解密消息得到明文 $M$ ， $M = C^d \mod N$

理论依据

费马定理

若 $p$ 是素数， $a$ 是一个正整数且不能被 $p$ 整除，则 $a^{p-1} \equiv 1 \mod p$

另一种表达形式是：$a^p \equiv a \mod p$

Eular 定理以及推论

先定义欧拉函数 $\phi(n)$ ，指的是小于 $n$ 且与 $n$ 互素的正整数的个数，习惯上， $\phi(1) = 1$ 对于 $n = pq$ ， $\phi(n) = \phi(p) \times \phi(q) = (p - 1)(q - 1)$。

欧拉定理 对任意互素的 $a$ 和 $n$ ，有： $a^{\phi(n)} \equiv 1 \mod n$

欧拉定理的另一种表述：$a^{\phi(n) + 1} \equiv a \mod n$

若 $n = pq, p \neq q$，都是素数， $k$ 是任意整数，则 $m^{k(p-1)(q-1)+1} \equiv m \mod n$ 对任意 $0 \le m \le n$ 成立

只要选择公钥 $e$ ，则私钥 $d$ 满足 $ed = k\phi(n) + 1$ ，即 $ed \equiv 1 \mod \phi(n) \to d \equiv e^{-1} \mod \phi(n)$ 求 $d$ 就是求 $e$ 的乘法逆元，可以使用扩展的欧几里得算法计算。

公钥： $K_U = \{e, n\}$ ，私钥： $K_R = \{e, n\}$

算法安全性保证

RSA 算法安全性是基于加密函数 $e_k(x) = x^e \mod n$ 是一个单向函数，所以对于攻击人，求逆运算是不可能的。

不可能在于，攻击者需要通过 $n$ 求解出对应的两个素数 $p, q$ 而当 $n$ 相当大的时候，这个求解的过程复杂度相当大。

所以可以说，RSA 算法的安全性是基于大整数因式分解的困难性上的。