RSA 签名

RSA 公钥密码系统提供了一种数字签名方案（签名和验证），其基础是模幂运算与离散对数的数学原理，以及 RSA 问题（及其相关的整数分解问题）的计算困难性。RSA 签名/验证#Signing_messages)算法的工作方式如下。

密钥生成

RSA 算法使用长度为 1024、2048、4096、...、16384 位的密钥。RSA 也支持更长的密钥（如 65536 位），但性能太慢，不适合实际使用（某些操作可能耗时数分钟甚至数小时）。要达到 128 位安全级别，需要 3072 位密钥。

RSA 密钥对由以下部分组成：

• 公钥 {n, e}
• 私钥 {n, d}

数字 n 和 d 通常是大整数（如 3072 位），而 e 较小，通常为 65537。

根据定义，RSA 密钥对具有以下性质：

$$(m^e)^d \equiv (m^d)^e \equiv m \pmod n$$ 对范围 [0...n) 内的所有 m 均成立

RSA 签名

使用私钥指数 d 对消息 msg 进行签名：

1. 计算消息哈希值：h = hash(msg)
2. 加密 h 以计算签名：$$s = h^d \pmod n$$

哈希值 h 应位于范围 [0...n) 内。得到的签名 s 是范围 [0...n) 内的整数。

RSA 签名验证

使用公钥指数 e 验证消息 msg 的签名 s：

1. 计算消息哈希值：h = hash(msg)
2. 解密签名：$$h' = s^e \pmod n$$
3. 比较 h 与 h'，判断签名是否有效

如果签名正确，则以下等式成立：

$$h' = s^e \pmod n = (h^d)^e \pmod n = h$$

RSA 签名/验证算法非常简单。下面用代码实现它。