非对称加密公式详解：RSA、ECC、ElGamal密钥生成与签名验签

搞密码学相关开发，或者面试时被问过非对称加密细节的朋友，应该都有过这种体验：RSA、ECC这些词张口就来，但真让你把公钥加密、私钥解密、签名验签的公式完整写出来，能写对的人不多。很多人背过 ( c = m^e \bmod n )，但对 ( e )、( d )、( n ) 到底怎么选出来的，( \lambda(n) ) 和 ( \phi(n) ) 哪个该用，ECC 里的点加、点乘到底怎么算，心里没底。

这篇文章就把常见公钥算法的加解密公式一次性讲透。覆盖 RSA、ElGamal、ECC（含 ECDH、ECDSA、ECIES）三套主流体系，从密钥生成、加解密、签名验签的完整公式链，到每个参数背后的安全约束和工程取舍，再到实际开发中容易踩的坑，全部拆开揉碎。适合刚接触非对称加密的开发者、准备面试的候选人，以及需要在工程里选型或排查加解密问题的从业者。读完你至少能自己手推一遍密钥生成过程，也能说清楚为什么某些参数是红线。

1. 公钥算法加解密的核心思路与通用模型

1.1 为什么统一看“密钥生成、加密解密、签名验签”三件套

公钥算法虽然数学形态各不相同，但几乎所有方案都可以拆成三件事：密钥生成、加解密、签名验签。密钥生成做的事，是构造一个有“陷门”的数学结构——陷门信息就是私钥，公开的信息就是公钥。加密方拿公钥把消息“锁”进这个结构里，解密方用私钥当作钥匙打开。签名则是反过来：私钥生成一段别人无法伪造的“印记”，公钥负责验证印记是否真的对应某条消息。

用生活化的类比，公钥就像一个上了锁的邮箱，任何人都能把信投进去（加密），但只有持有私钥的人能打开邮箱取信（解密）。签名则是私钥持有者给文件盖一个私章，别人用公钥验证章是真的。公式本身并不难，难点在于理解每一步为什么要有这些参数、每个参数的大小和关系决定了什么安全等级、哪些参数一旦选错会导致算法直接被攻破。

RSA 的数学地基是大整数分解难题，ElGamal 的地基是有限域上的离散对数难题，ECC 的地基是椭圆曲线群上的离散对数难题。这三个难题的共同点是：正向计算很容易，逆向计算极难。正因为这个“易算难逆”的不对称性，才撑起了非对称加密的整个安全模型。

1.2 三种常见公钥算法的“数学地基”与选型逻辑

RSA 是最早被广泛商用的公钥算法，公式直观，开发者接受度最高，但密钥长度要求长（推荐 2048 位以上），加解密性能相对慢。ElGamal 在国内实际工程中不如 RSA 和 ECC 常见，但它是理解离散对数体系的最佳入门，而且它的变体（如 Cramer-Shoup）和一些隐私计算协议里经常出现。ECC 是目前综合性价比最高的选择——256 位左右的密钥能提供与 3072 位 RSA 相当的安全强度，密钥短、运算快、带宽占用低，适合移动端、物联网、区块链等场景。

选型时不能只看“哪个更安全”，还要看生态、标准合规要求、性能预算和现有系统的兼容性。比如很多政企系统要求使用 RSA-SHA256 签名，金融行业对 ECC 曲线参数有明确推荐标准。我在实际项目里见过团队为了“追新”直接上 ECC，结果业务系统里对接的老网关只支持 RSA，最后不得不做双算法兼容，成本和风险都翻倍。选型的第一原则是：先看对接方和合规要求支持什么，再谈技术偏好。

2. RSA 加解密公式拆解与实操参数

2.1 RSA 密钥生成的完整公式链

RSA 密钥生成的第一步是选择两个大素数 ( p ) 和 ( q )。这两个素数要求随机且长度接近，实际工程中通常用 Miller-Rabin 素性检测来生成。计算出 ( n = p \times q )，( n ) 的二进制长度就是 RSA 的密钥长度（比如 2048 位）。接下来关键的一步是计算 ( \phi(n) = (p-1)(q-1) )，也就是欧拉函数——在 1 到 ( n ) 之间与 ( n ) 互素的整数个数。

然后选择一个公钥指数 ( e )，要求 ( 1 < e < \phi(n) ) 且 ( \gcd(e, \phi(n)) = 1 )。工程上 ( e ) 经常取 65537（即 ( 2^{16}+1 )），它是个素数，计算速度快，且保证与绝大多数 ( \phi(n) ) 互素。接着用扩展欧几里得算法求出私钥指数 ( d )，满足 ( e \times d \equiv 1 \pmod{\phi(n)} )。这个 ( d ) 就是私钥的核心，一旦泄露，任何人都能还原明文。

需要特别说明一个容易混的点：现代 RSA 标准（如 PKCS#1 v2.2）实际使用的是卡迈克尔函数 ( \lambda(n) = \operatorname{lcm}(p-1, q-1) ) 而不是 ( \phi(n) )。用 ( \lambda(n) ) 求出的 ( d ) 可能更小，而且 ( \phi(n) ) 求出的 ( d ) 也满足加密解密互逆，因为 ( \phi(n) ) 是 ( \lambda(n) ) 的整数倍。绝大多数教程用 ( \phi(n) ) 是为了推导简单，实现时两种都能跑通，但按标准实现建议使用 ( \lambda(n) )。

2.2 RSA 加解密与签名验签公式及常见陷阱

RSA 加密公式是 ( c = m^e \bmod n )，解密公式是 ( m = c^d \bmod n )。其中 ( m ) 是明文经过填充后的整数表示，( c ) 是密文整数。为什么能还原？因为 ( m^{ed} \equiv m \pmod{n} )，这个等式由 ( ed \equiv 1 \pmod{\lambda(n)} ) 保证。

这里有个严重的工程陷阱：不能拿原始消息直接做模幂运算。直接 RSA（教科书式 RSA）存在大量攻击面，比如选择密文攻击、小指数攻击、共模攻击。实际实现必须使用填充方案，比如 RSA-OAEP（最优非对称加密填充）或 PKCS#1 v1.5。OAEP 会把消息加盐、加哈希、做两轮 Feistel 置换，再送入模幂运算，这样同一明文每次加密的密文都不同，抵抗已知明文攻击的能力大幅提升。

RSA 签名公式是 ( s = m^d \bmod n )，验签公式是 ( m = s^e \bmod n )。签名其实是用私钥做“加密”，用公钥做“解密”。但真实实现里不会直接签原始消息的整数表示，而是先对消息做哈希，再对哈希值做填充（如 EMSA-PKCS1-v1_5 或 PSS），最后才做模幂。PSS 是随机化填充，每次签名结果不同，安全性优于传统 v1.5，新系统建议直接用 RSA-PSS。

我遇到过最典型的 RSA 问题是：两端明明用同一个密钥对，加密解密却失败。排查下来发现是填充模式不匹配——一方用 OAEP-SHA256，另一方用 PKCS#1 v1.5，结果密文长度和结构对不上。另一个高发问题是密钥长度不匹配，一端生成的是 1024 位密钥，另一端按 2048 位解析，直接报错。RSA 这块的教训就一句话：参数协商比算法本身更容易出问题，密钥位数、填充模式、哈希算法必须在两端的配置里完全一致。

3. ElGamal 加解密公式与关键工程要点

3.1 ElGamal 密钥生成与加解密公式

ElGamal 算法的数学基础是有限域 ( \mathbb{Z}_p ) 上的离散对数问题。密钥生成时，选择一个大的素数 ( p )，再选择一个生成元 ( g )（( g ) 是模 ( p ) 乘法群的一个生成元，实际中常选一个阶为大素数的元素）。私钥 ( x ) 是从 ( [1, p-2] ) 中随机选的整数，公钥是 ( y = g^x \bmod p )。安全性的核心在于：给定 ( y, g, p )，求 ( x ) 是困难的。

加密过程有个与众不同的地方：它需要临时选取一个随机数 ( k )，且 ( 1 \le k \le p-2 )，( k ) 与 ( p-1 ) 互素。密文是一对值：( c_1 = g^k \bmod p )，( c_2 = m \times y^k \bmod p )。解密时计算 ( m = c_2 \times (c_1^x)^{-1} \bmod p )。为什么能还原？因为 ( c_1^x = g^{kx} )，而 ( y^k = g^{xk} )，两者相等，所以 ( c_2 ) 除以 ( c_1^x ) 就能恢复出 ( m )。

这个公式展现了一个特别重要的特性：密文是概率性的。同一个明文 ( m )，每次加密用不同的 ( k )，得到的 ( c_1, c_2 ) 完全不同，但解密结果一致。这在密码学上叫语义安全，意思是敌手无法通过观察密文推断出明文之间的任何关系。相比之下，教科书式 RSA 是确定性加密，同一明文两次加密密文一样，这在很多场景下是缺陷。

3.2 随机数与密文膨胀的工程处理

ElGamal 在实际工程中最大的痛点有三个：随机数质量、密文膨胀、参数验证。

随机数 ( k ) 是生命线。如果 ( k ) 被泄露，攻击者能用 ( m = c_2 \times y^{-k} ) 直接恢复明文；如果两次加密用了同一个 ( k )，且攻击者已知其中一条明文，另一条明文也能被还原。这就是著名的“随机数重用攻击”。所以 ( k ) 必须来自密码学安全随机数生成器（CSPRNG），绝对不能用random()这类伪随机函数生成。

密文膨胀指 ElGamal 的密文长度是明文的两倍左右：两个 ( p ) 长度的大整数，而明文短得多。这意味着如果明文是长数据，直接 ElGamal 加密的带宽开销极高。实践中 ElGamal 基本只用来加密对称密钥（比如 AES 的会话密钥），真正的业务数据用对称加密，这就是混合加密的标准做法。公钥算法加密小块密钥，对称算法加密大块数据，性能和安全性都能兼顾。

参数验证也不能忽略。解密端拿到 ( c_1 ) 后要先检查它是否在 ( [1, p-1] ) 区间内，且 ( c_1^x ) 不为 0，否则可能出现无效密文攻击或信息泄露。很多实现只做“算出来再判断”，结果在异常输入时会报错泄露密文结构信息。我在做安全审计时见过一个 ElGamal Demo，完全没有对密文做有效性校验，攻击者可以通过构造特殊密文探测私钥信息。正确做法是解密前先验证 ( c_1, c_2 ) 的取值域。

4. ECC 椭圆曲线加解密公式与工程落地

4.1 椭圆曲线群运算基础

ECC 的数学对象不是有限域上的整数乘法，而是椭圆曲线上的点构成的群。一个典型曲线形式是 ( y^2 = x^3 + ax + b )，实际使用中会在有限域 ( \mathbb{F}_p ) 上取点，所有坐标都是模 ( p ) 的整数。曲线上的点之间存在“加法”运算：两点 ( P, Q ) 连线与曲线交于第三点 ( R' )，( R' ) 关于 x 轴对称的点 ( R = P + Q ) 即为和。点与自身相加叫倍点，( P + P = 2P )。

有了点加和倍点，就能定义标量乘法 ( kP = P + P + ... + P)（( k ) 次）。这个运算就是 ECC 的核心——给定 ( k ) 和 ( P )，算 ( Q = kP ) 很容易；给定 ( Q ) 和 ( P )，求 ( k ) 极难，这就是椭圆曲线离散对数问题（ECDLP）。ECC 的私钥就是一个随机整数 ( d )，公钥是曲线上的点 ( Q = dG )，其中 ( G ) 是公开的基点。

理解 ( kP ) 的关键在于它不是一个“乘法”的直觉，而是“连加”的缩写。工程实现中会用双倍与相加算法（Double-and-Add）把 ( kP ) 拆成若干次倍点和点加，复杂度是 ( O(\log k) ) 而不是 ( O(k) )。如果你要手算验证，最笨的办法就是不断做点加，但实际代码里没人这么干，OpenSSL、Java、Go 标准库都已经实现好了这些运算。

4.2 ECDH、ECIES 加解密公式与签名验签公式

ECDH（椭圆曲线 Diffie-Hellman）不是直接加解密，而是密钥协商协议。双方各自生成私钥 ( d_A, d_B )，公钥是 ( Q_A = d_A G, Q_B = d_B G )。交换公钥后，A 计算 ( S = d_A Q_B )，B 计算 ( S = d_B Q_A )，因为 ( d_A Q_B = d_A d_B G = d_B d_A G = d_B Q_A )，双方得到同一个共享点 ( S )，再把 ( S ) 的 x 坐标过哈希函数导出为对称密钥。

ECIES（椭圆曲线集成加密方案）是在 ECDH 基础上构造的公钥加密方案。加密时，A 临时生成一个随机私钥 ( r )，计算临时公钥 ( R = rG )，并用 ( r ) 与接收方公钥 ( Q_B ) 算出共享点 ( S = rQ_B )。然后用 KDF（密钥导出函数）从 ( S ) 派生出对称密钥 ( k_{enc} ) 和 ( k_{mac} )，用 ( k_{enc} ) 加密消息，用 ( k_{mac} ) 生成认证标签，最终密文包含 ( R )、密文体和标签三部分。解密时接收方用自己的私钥 ( d_B ) 计算 ( S = d_B R )，因为 ( d_B R = d_B rG = rQ_B )，得到的共享点与加密方一致。

ECDSA（椭圆曲线数字签名算法）的公式是这样的：签名方有私钥 ( d )，公钥 ( Q = dG )，消息哈希为 ( z )。签名第一步随机选整数 ( k )，计算 ( R = kG )，取 ( R ) 的 x 坐标得到 ( r )，再算 ( s = k^{-1}(z + r \times d) \bmod n )，其中 ( n ) 是基点 ( G ) 的阶。签名结果是 ( (r, s) )。验签时计算 ( w = s^{-1} \bmod n )，( u_1 = z \times w \bmod n )，( u_2 = r \times w \bmod n )，再算点 ( P = u_1G + u_2Q )，如果 ( P ) 的 x 坐标模 ( n ) 等于 ( r )，签名有效。

ECDSA 有一个著名的坑：随机数 ( k ) 绝对不能泄露或重用。如果同一个私钥签两条消息用了同一个 ( k )，攻击者能直接算出私钥 ( d )。2010 年 PlayStation 3 的签名密钥被破解，就是因为索尼在签名时用了固定的 ( k )。所以实现 ECDSA 时，要么使用 RFC 6979 规定的确定性随机数（从私钥和消息哈希派生 ( k )），要么确保 CSPRNG 质量过硬。

5. 安全性分析与参数避坑

5.1 参数选择失败的典型场景：小密钥、小指数、弱随机数

RSA 的 ( p, q ) 必须足够大且相互独立。从同一个随机种子生成的两个“随机”素数如果恰好相等，( n ) 就能被平方根分解，整个密钥直接失效。这在实际中真发生过——某些老旧实现用弱随机数生成器批量生成密钥，导致大量 RSA 公钥共享同一个因子，攻击者通过批量计算最大公约数就能批量分解。

ElGamal 的 ( p ) 和 ( g ) 也有讲究。如果 ( p-1 ) 包含小因子，离散对数可以用 Pohlig-Hellman 算法降维打击，计算复杂度大幅下降。同理，如果 ( g ) 的阶太小，私钥空间就被压缩了。安全参数选型的核心原则是：所有参数都必须落在算法标准推荐的域内，不要自己“发明”参数。以 ECC 为例，直接用 NIST P-256、secp256k1 或者国产 SM2 标准曲线即可，自己造曲线极容易引入子群攻击或异常曲线攻击。

另一个高频问题是私钥长度和公开参数的位数不匹配。我看到过有人把 512 位 RSA 当作对称加密的密钥级别来用，理由是“反正攻击成本也不低”。这个思路是错的：RSA 512 位在现代算力下已经可以被轻松分解，2016 年就有研究团队在约 540 天内分解过 768 位 RSA 模数。2024 年之后，1024 位 RSA 也不该再用于任何新系统，最低 2048 位起步，合规要求高的场景直接上 3072 位。

5.2 填充方案与密文长度对照表

注意 RSA 密文长度始终等于模数长度，和明文长度无关，这也是 RSA 不适合直接加密长数据的另一个原因。ECC 加密的密文长度优势很明显，尤其适合物联网设备这种低带宽场景。ElGamal 的密文膨胀比是 2 倍，是三者里最不经济的，但它在一些特殊协议（比如同态加密、门限解密）里有不可替代的表达能力。

填充方案的选择直接决定算法是否满足 IND-CCA（选择密文攻击下不可区分）安全。RSA 必须用 OAEP 或至少 PKCS#1 v1.5；ECDSA 使用哈希后再签名；ECIES 使用 KDF+MAC 组合；ElGamal 直接形态只满足 IND-CPA，工程上需要叠加其他机制才能达到更高安全属性。如果真的要做高安全等级的系统，建议直接采用标准库的高层接口，而不是自己组装原语。

6. 常见问题速查表与排查心得

6.1 问题速查表：加解密失败时的第一反应清单

这些问题是跨语言的，我在 Go、Java、Python、Node.js 里都见过。最常见的“解密失败”不是算法算错了，而是编码、压缩格式、填充参数不一致。调试的时候不要一上来就觉得是数学公式写错了，先检查两端配置。

6.2 实测中的独家经验

根据我自己踩过几次坑之后的体会，处理公钥加解密问题有三个优先级极高的经验。

第一条，直接用标准库，别自己实现算法公式。RSA、ECC、ElGamal 的公式本身不难，但安全实现涉及常数时间运算、侧信道防护、随机数管理，标准库里这些细节都已经处理好了。自己实现很容易在指数运算的计时差异上泄露私钥信息。我做安全测试时用一台普通笔记本就能在简单实现上测出私钥恢复的时序侧信道，标准库反而不会有这个问题。

第二条，加解密与签名验签的“填充”概念不要混。加解密填充为了抵抗密文分析，签名填充为了抵抗伪造和哈希值欺骗。RSA-OAEP 和 RSA-PSS 虽然都叫填充，实现细节完全不同，签名时用 OAEP 是错的，解密时用 PSS 也是错的。很多新人把公钥加密和数字签名当成“同一个操作正反着用”，这在 RSA 里勉强成立，但真实填充语境下是不对的。

第三条，密钥轮换与版本兼容要提前设计。生产环境里密钥到期轮换时，经常出现旧数据用旧密钥加密、新系统只配新密钥导致无法解密的情况。我的做法是系统里保留密钥版本号，密文结构里带上密钥 ID，解密时按 ID 选择对应密钥。签名验签同理，验签时尝试多个版本的公钥，保证历史签名仍然可用。这个设计在金融、政务系统里尤其重要，因为数据生命周期往往长达数年甚至十几年。

最后再分享一点：不管用哪套公钥算法，密钥生成时必须用密码学安全随机数；密钥存储必须加密且做访问控制；私钥丢失后要靠密钥备份或托管机制恢复，否则历史密文将永久不可解密。公式只是入门钥匙，真正的工程安全体现在密钥管理、协议交互和异常处理的每一个细节上。把这几条刻在脑子里，比记住任何一条公式都更能保护你的系统。