3、密码学基础（二）：RSA算法原理、椭圆曲线密码学（ECC）简介
好，我们接着往下聊。上一章我们把哈希函数和对称加密讲透了，这一章要啃两块硬骨头——RSA 和 ECC。说实话，这两者在固件签名验证里是绝对的主角。你去看市面上任何一款支持 OTA 的物联网芯片，签名算法不是 RSA 就是 ECC，几乎没有例外。
我个人习惯是先理解数学原理，再去看工程实现。别怕，我不会给你推公式推到睡着。咱们用工程师的视角，把这两个算法「拆开揉碎」了讲。
3.1 RSA 算法：大数分解的数学游戏
RSA 的核心思想，说白了就是一句话：两个大质数相乘很容易，但把乘积分解回两个质数极难。你想想看，给你两个 1024 位的质数 p 和 q，计算机算 n = p × q 只要几毫秒。但反过来，给你一个 2048 位的 n，让你找出 p 和 q——嗯，用目前最好的算法，也得算到宇宙毁灭。
这就是 RSA 的安全根基。我当年第一次接触这个思想时，觉得这简直是个数学魔术。
3.1.1 密钥生成流程
RSA 的密钥对生成，我建议你记住这五个步骤。在嵌入式开发中，我们通常是在 PC 端生成密钥对，然后把公钥烧进设备固件里。
- 选两个大质数：p 和 q，长度至少 1024 位（实际中常用 2048 位）
- 计算 n：n = p × q，n 就是密钥长度
- 计算欧拉函数 φ(n)：φ(n) = (p-1) × (q-1)
- 选公钥指数 e：通常取 65537（0x10001），这个值有工程上的讲究
- 计算私钥 d：d ≡ e⁻¹ mod φ(n)，即 e 关于 φ(n) 的模逆元
关键点：公钥是 (e, n)，私钥是 (d, n)。公钥公开，私钥绝对保密。在 OTA 场景中，签名方（服务器）持有私钥，验证方（设备）持有公钥。
3.1.2 签名与验证过程
RSA 签名和加密其实是「镜像操作」。签名用私钥，验证用公钥。我在项目中遇到过不少新手搞反了，结果签名验证死活过不去。
| 操作 | 输入 | 计算 | 输出 |
|---|---|---|---|
| 签名 | 消息 m，私钥 d | s = md mod n | 签名值 s |
| 验证 | 消息 m，签名 s，公钥 e | m' = se mod n | 若 m' == m，验证通过 |
实际工程中，我们不会直接对固件做 RSA 签名——固件动不动几 MB，RSA 算起来太慢了。正确的做法是：先对固件做哈希，再对哈希值做 RSA 签名。这个我在上一章提过，这里再强调一遍。
工程经验：RSA-2048 在 Cortex-M4 上做一次签名验证大约需要 50-100ms。如果设备对启动时间有严格要求（比如汽车 ECU），这个延迟必须提前评估。
3.1.3 填充方案：PKCS#1 v1.5 vs PSS
直接做 RSA 签名是不安全的。为什么？因为 RSA 是确定性算法，同样的输入永远得到同样的输出。攻击者可以利用这个特性做选择明文攻击。
所以我们需要填充方案。目前主流的有两种：
- PKCS#1 v1.5：老牌方案，实现简单，但理论上存在一些攻击面。我在 2017 年的一个项目中用过，当时芯片的加密库只支持这个。
- PSS（Probabilistic Signature Scheme）：新标准，引入了随机数，安全性更高。现在新设计的系统我建议直接用 PSS。
避坑指南：我曾经在一个 OTA 项目中，因为用了 PKCS#1 v1.5 且没有做额外的随机化处理，被安全审计打回来重做。从那以后，只要芯片支持，我一律用 PSS。
3.2 椭圆曲线密码学（ECC）：更小的密钥，同等的安全
ECC 是 RSA 的「后浪」。它用更短的密钥长度，提供和 RSA 同等级别的安全性。你想想看，RSA-2048 和 ECC-256 的安全强度差不多，但 ECC 的密钥只有 256 位，计算量也小得多。这对嵌入式设备来说，简直是天赐之物。
3.2.1 椭圆曲线的数学直觉
ECC 的数学基础是椭圆曲线上的点群运算。别被「椭圆曲线」这个名字吓到，它和椭圆没有半毛钱关系。标准方程是：
y² = x³ + ax + b这条曲线上的点构成一个群。两个点相加得到第三个点，这个「加法」有几何意义——做切线、找交点、取对称点。嗯，听起来有点绕，但实际工程中我们只需要调用现成的库函数。
ECC 的安全性建立在「椭圆曲线离散对数问题」上：给定基点 G 和公钥 Q = kG，求私钥 k 几乎不可能。这比 RSA 的大数分解问题更难破解。
3.2.2 ECDSA 签名算法
在固件签名中，ECC 最常用的签名算法是 ECDSA（Elliptic Curve Digital Signature Algorithm）。它的流程比 RSA 复杂一些，但安全性更高。
ECDSA 签名过程：
- 生成随机数 k，计算点 R = kG
- 取 R 的 x 坐标作为 r
- 计算 s = k⁻¹ × (hash(m) + d × r) mod n
- 签名值为 (r, s)
验证过程：
- 检查 r 和 s 是否在有效范围内
- 计算 w = s⁻¹ mod n
- 计算 u₁ = hash(m) × w mod n，u₂ = r × w mod n
- 计算点 P = u₁G + u₂Q
- 若 P 的 x 坐标等于 r，验证通过
注意：ECDSA 的随机数 k 必须每次不同且绝对保密。如果 k 泄露，私钥 d 可以直接算出来。2010 年索尼 PS3 的签名被破解，就是因为用了固定的 k 值。这个坑，千万别踩。
3.2.3 曲线选择：NIST P-256 与 Curve25519
ECC 的曲线参数选择至关重要。不同的曲线，安全性和性能差异很大。目前主流的有两条：
| 特性 | NIST P-256 | Curve25519 |
|---|---|---|
| 密钥长度 | 256 位 | 255 位 |
| 安全强度 | ≈ RSA-3072 | ≈ RSA-3072 |
| 性能 | 较快 | 更快（常数时间） |
| 专利 | 有（部分已过期） | 无（开源友好） |
| 侧信道防护 | 需额外实现 | 天然抗侧信道 |
我个人更倾向于 Curve25519（Ed25519 签名）。原因很简单：它实现简单，天然抗侧信道攻击，而且没有专利包袱。我在一个智能门锁项目中用过 Ed25519，在 Cortex-M0 上签名验证只要 2ms，比 RSA 快了一个数量级。
3.3 RSA vs ECC：怎么选？
这个问题我几乎在每个技术评审会上都会被问到。我的建议是：
- 兼容性优先：如果设备需要和旧系统交互，或者芯片只支持 RSA 硬件加速，那就用 RSA-2048 + PSS 填充
- 性能优先：如果设备资源受限（比如 8 位 MCU），或者对启动时间有严苛要求，果断上 ECC（Ed25519）
- 安全等级：两者在合理密钥长度下都足够安全。RSA-2048 和 ECC-256 的安全等级相当，但 ECC 的密钥更短，签名也更短（64 字节 vs 256 字节）
我的经验：新项目我基本都用 ECC。原因很简单——省空间、省时间、省电。OTA 固件包每少 1KB，几百万台设备升级下来，带宽和电费都是实打实的成本。
3.4 本章知识体系
下面这张图把 RSA 和 ECC 的核心脉络梳理了一下。你可以把它当作一个快速参考。