# RSA 加密

RSA（Rivest-Shamir-Adleman）加密算法是基于大数分解困难性的一种非对称加密算法
其核心思想是利用两个大素数的乘积作为模数，结合模幂运算实现加密和解密

取 $p, q$ 为两个相异大素数，计算模数 $n = p \cdot q$
计算欧拉函数

$$\varphi(n) = (p-1)(q-1)$$

选择公钥指数 $e$，其满足

$$\gcd(e, \varphi(n)) = 1$$

• 公钥对 $(e, n)$ 用于加密
• 私钥对 $(d, n)$ 用于解密

对于输入 $x$，假设 $x \lt n$
信息发送方利用 $e$ 和 $n$ 计算密文

$$c \equiv x^e \pmod n$$

信息接收方利用私钥 $d$ 计算明文
由于 $\gcd(e, \varphi(n)) = 1$，利用 $e, p, q$ 根据扩展欧几里得算法可以计算出

$${}^\exists d \in \mathbb Z: e \cdot d \equiv 1 \pmod {\varphi(n)}$$

那么 ${}^\exists k \in \mathbb Z$，使得

$$c^d \equiv (x^e)^d \equiv x^{ed} \equiv x^{1 + k \varphi(n)} \pmod n$$

根据欧拉定理，有

$$x^{\varphi(n)} \equiv 1 \pmod n$$

所以

$$c^d \equiv x \pmod n$$

从而实现解密

对其安全性的考察：
如果攻击者获取了密文 $c$ 和公钥对 $(e, n)$，是否可以破解
要破解 RSA 加密，攻击者需要从密文 $c$ 和公钥 $(e, n)$ 中恢复出明文 $x$

数学上，这个问题等价于：是否可以从公钥对 $(e, n)$ 中计算出私钥指数 $d$
如果可以对模数 $n$ 进行质因数分解，得到 $p$ 和 $q$，那么可以计算出 $\varphi(n)$，进而利用扩展欧几里得算法计算出 $d$

然而，对于大素数 $p$ 和 $q$，目前已知的质因数分解算法在计算复杂度上是指数级别的
因此，RSA 加密的安全性主要依赖于大数分解的困难性
只要选择足够大的素数 $p$ 和 $q$，使得 $n$ 足够大，攻击者在合理时间内无法完成质因数分解，从而无法计算出私钥 $d$，保证了加密信息的安全性