公钥密码学也被称为非对称密码学，这是一种涉及两个密钥的密码学类型，即公钥和私钥。发送方使用接收方的公钥对明文进行加密，而接收方则使用其私钥对加密消息进行解密，因此该消息只能被预期的接收方解密。
RSA（Rivest Shamir Adleman）是一种公钥密码算法，其密钥生成基于两个大质数 p 和 q 的乘积，即 N = p × q。该算法安全性的核心在于，攻击者首先需要通过对 N 进行因式分解来找出 p 和 q，这一过程需要耗费指数级的时间。研究表明，如果 N 是一个 100 位的数字，这可能需要超过 70 年的时间。由于这种复杂性，攻击者无法计算出解密密钥 d，因为 d 依赖于 p、q 和加密密钥 e。因此，即使攻击者知道了 N 和 e，也无法计算出 d。
RSA 的现状：
截至 2017 年 4 月，RSA-2048 在未来许多年内可能都无法被因式分解。此外，最近的勒索软件病毒也使用 RSA-2048 来加密受感染系统上的文件。在没有解密密钥的情况下，这些文件无法被解密，因为如此巨大的密钥无法被因式分解。因此，RSA-1024 和 RSA-2048 现在正被广泛用于安全通信。
\ \textbf{\hspace{4cm} 密钥生成：} \\ 选择 \hspace{0.2cm} p, q \hspace{5cm} p,q \hspace{0.2cm}均为 \hspace{0.2cm} 质数\\ 计算 \hspace{0.2cm} n = pq \\ 计算 \hspace{0.2cm}\phi(n) = (p-1)(q-1) \\ 选择 \hspace{0.2cm}整数 \hspace{0.2cm}e \hspace{4cm} gcd(\phi(n),e)=1; 1<e<\phi(n)\\ 计算 \hspace{0.2cm} d\\ 公钥 \hspace{5cm} KU = {e,n}\\ 私钥 \hspace{4.7cm} KR = {d,n}
上图展示了 RSA 算法的三个不同阶段。考虑到质数生成器生成的是 1024 位的质数 p 和 q，结果 N 将是一个 2048 位的数字。由于加密和解密期间执行的所有模运算都是针对这个 2048 位的数字 N 进行的，因此软件实现可能会非常耗时。此外，C 语言中的 unsigned long long int 数据类型将计算限制在 64 位数字以内。为了支持 RSA 算法所需的生成大尺寸密钥，以及加速涉及大尺寸模数的加密和解密计算，我们可以使用一个名为 GMP（GNU 多精度算术库）的库。使用这个库将允许整个 RSA 算法在简单的 64 位操作系统上运行，从而避免使用超级计算机或高配置硬件设备。
什么是 GMP？
GMP 是一个开源库，它允许对有符号整数、有理数和十进制数执行算术运算，除了受运行机器的配置限制外，几乎没有其他精度限制。该库用于涉及非常大或高精度数字的算术计算，其中大部分用于密码算法。使用这个库的好处是它提供了对任意精度数字的支持，这些数字的大小在程序执行之前是未知的。使用该库提供的基本接口是针对 C 语言的。但包括 Ada、C++、C#、Julia、OCaml、Perl、PHP、Python、R、Ruby 和 Wolfram Language 在内的其他语言也都有相应的封装。
作为示例，下面提到了一个执行两个多精度数字乘法的 C 程序。
请注意，需要将 gmp.h 文件作为头文件包含在内。在 Unix 系统上编译此类程序可以使用以下命令
gcc program_name.c -lgmp
C
CODEBLOCK_84b13d04
RSA 算法的编码：
我们可以通过这里查看一个使用小质数展示 RSA 算法工作原理的 C 程序。为了理解使用大质数的真实 RSA 算法是如何工作的，我们可以查看这里使用 GMP 库的 C 代码。该程序通过生成随机质数 p 和 q（每个 512 位）来实现 RSA-1024，随后进行加密和解密。