RSA加密解密

关键分发

设 Alice（接收方）和 Bob（发送方）使用 RSA：

• Alice 公开：公钥 (n,e)
• Alice 私有：私钥 d
• Bob 需要 Alice 的公钥才能加密或验证签名；
• 私钥永远不能被分发。

公钥可通过**公开但可信的渠道**传输，如数字证书、PKI 或 CA。

消息加密

Bob 想发送消息 M 给 Alice：

1. 先用**填充方案**（如 OAEP）将 M 转换为整数 m，满足：

$$ 0 \le m < n $$

1. 计算密文：

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

1. 将 c 发送给 Alice。

此运算可用**快速模幂算法（平方乘算法）**高效完成。

说明：理论上存在少量固定点 m 使得 m^e \equiv m \pmod n，但在正确填充下几乎不会影响安全性。

消息解密

Alice 使用私钥 d 计算： $$ m \equiv c^d \pmod n $$ 再反转填充得到原始消息 M。

重要安全原则： 若填充无效，Alice 必须直接丢弃消息，不给任何错误提示细节，否则可能遭受“填充预言机攻击”。

步骤操作

步骤	操作	公式	涉及参数
准备	生成密钥	n=pq, \phi(n)=(p-1)(q-1)	p, q (销毁)
加密	使用公钥	C = M^e \pmod{n}	n, e
解密	使用私钥	M = C^d \pmod{n}	n, d