RSA加密算法是一种非对称加密算法，也称公开密钥加密。该算法是1977年由Ron Rivest，Adi Shamir和Leonard Adleman三人一起提出的。非对称加密即加密过程会使用一对密钥，公钥和私钥各一个。使用公钥将明文加密成密文，并使用私钥将密文解密成明文。

RSA主要包含两个部分：

• 公钥和私钥的生成
• 加密和解密算法

假设Alice要向Bob发送一个RSA加密的报文，其实就是对报文的二进制模式的表现形式所代表的整数进行加密。例如，假设待加密报文的比特模式为1001，其实等价于加密整数9，解密亦然。

公钥和私钥的生成

为了让Alice可以发送加密的密文，Bob需要执行以下步骤生成公钥和私钥：

1. 选择两个大素数p和q。理论上p和q的乘积越大，则破译的难度越大。目前比较推荐的大小为p和q的乘积为1024比特的数量级。
2. 计算 n = pq 和 z = (p – 1)(q – 1)
3. 在小于n的整数中随机选择一个与z互质的整数e，此时公钥生成完成，其中包含n和e，记为K⁺ = (n, e)。
4. 求一个数d，满足 ed mod z = 1 即可。此时私钥生成完成，其中包含n和d，记为 K^– = (n, d)。

加密和解密算法

Alice要给报文加密时，假设报文的二进制表现形式的整数值为m，且 m < n，使用公钥对m加密的结果为c，则：

c = m^e mod n

Bob接收到密文后，使用私钥对c进行解密的算法为：

m = c^d mod n

RSA的工作原理

通过以上算法为何就能将加密后的密文c解密出原文m呢？在讲解原理之前，首先要引入取模运算的一个重要性质（该性质暂不证明），对于任意值a，n和d都有：

(a mod n)^d mod n = a^d mod n

将a = m^e代入该等式则有[等式A]：

(m^e mod n)^d mod n = m^ed mod n

将加密等式 c = m^e mod n 代入解密函数 f = c^d mod n 中可得：

f = (m^e mod n)^d mod n

结合[等式A]，可得：

f = (m^e mod n)^d mod n = m^ed mod n

再引入数论的一个结论（该结论暂不证明）：

如果p和q是素数，且有 n = pq 和 z = (p-1) (q-1) ，则：

x^y mod n = x ^{(y mod z)} mod n

应用这个结论，将 x = m 和 y = ed 代入等式可得[等式C]：

m^ed mod n = m^{(ed mod z)} mod n

将[等式C]代入函数 f ，可得：

f = m^ed mod n = m^{(ed mod z)} mod n

由前面选取公钥私钥的算法可知 ed mod z = 1，代入函数 f ：

f = m^{(ed mod z)} mod n = m¹ mod n = m

最终得出解密函数 f 的结果等于原文m。

RSA的安全性依据

RSA的安全性依赖于目前没有已知的算法可以快速分解一个大数的因数，所以n很难分解出素数p和q。所以根据公钥中已知的n和e，以人类目前计算机的计算能力，需要很多年才能推测出私钥中的d。但是当计算能力极强的量子计算机出现后，RSA的安全性也不是确保的。