RSA介绍

RSA 是一种基于数论的**非对称公钥密码算法**，可同时用于**加密**和**数字签名**，是现代密码学和互联网安全基础设施（如 TLS/SSL、HTTPS、PKI）的核心算法之一。其安全性建立在**大整数分解困难性**之上，即：将两个大素数相乘很容易，但反过来从其乘积还原出原始素数在计算上极其困难。

“RSA”这一名称取自三位发明者姓氏的首字母：Rivest、Shamir、Adleman。

1. RSA的历史¶

1976 年，美国密码学家**惠特菲尔德·迪菲（Whitfield Diffie）**和**马丁·赫尔曼（Martin Hellman）**发表了开创性的论文，首次提出了**公钥密码（非对称密码）**的概念，打破了“通信双方必须事先共享秘密密钥”的传统范式。

1977 年，麻省理工学院（MIT）的**罗纳德·李维斯特（Ron Rivest）**、**阿迪·萨莫尔（Adi Shamir）**和**伦纳德·阿德曼（Leonard Adleman）**共同提出了 RSA 算法。

在此之前的一年多时间里，三人一直在寻找一个**易于正向计算但难以逆向求解的单向函数**，以实现真正的公钥加密与数字签名。他们尝试了多种数学构造，包括：

基于背包问题的方案
基于置换多项式的方法
其他组合数学和数论构造

这些尝试均存在安全缺陷或可逆性问题，一度让他们怀疑目标是否可能实现。

据三位发明者回忆，关键突破出现在 1977 年逾越节期间。里维斯特在失眠时重新思考问题，最终意识到**大整数分解**可作为单向陷门函数的基础，并在清晨完成了论文的大部分数学框架。随后，他们正式提出了现在广为人知的 RSA 算法。

RSA 不仅支持加密，还天然支持**数字签名**，弥补了迪菲–赫尔曼体系中“缺乏可实现签名机制”的空白。

值得注意的是，英国政府通信总部（GCHQ）的数学家**克利福德·科克斯（Clifford Cocks）早在 **1973 年**就在内部文件中独立提出了一种**与 RSA 等价的系统，同样基于大素数乘积与模幂运算。

然而，由于：

当时计算机性能有限
实际部署成本极高
工作属于高度机密

该方案主要被视为理论性成果，从未在公开系统中使用。科克斯的工作直到 **1997 年**才被解密并公之于众，此后才被历史正式承认为“RSA 的先行发现”。

1997 年，研究人员提出了 Kid-RSA（KRSA），这是一种**简化且不安全的教学版 RSA**，用于帮助学生理解：

公钥与私钥的关系
模幂运算
欧拉函数
大整数分解与安全性的关联

Kid-RSA 在教育中的地位类似于密码学中的 Simplified DES（S-DES）：它**不适用于真实安全通信**，但非常适合课堂演示与实验教学。

RSA 的提出具有里程碑意义：

奠定了现代互联网安全基础
支撑了 HTTPS、电子签名、数字证书和 PKI
推动了计算数论、复杂性理论和量子安全研究
促进了密码学从“军事机密”走向公开学术领域

尽管量子计算的发展可能在未来威胁 RSA，但目前它仍是全球最重要的公钥密码算法之一。

2. 基本原理¶

RSA的安全性建立在**大整数分解的困难性**之上。

将两个大素数相乘在计算上是非常容易的。
但要将它们的乘积（极大的数）重新分解为原始的素数，在现有的计算能力下（对于足够长的密钥，如2048位）几乎是不可能的。