公钥算法公式详解：RSA、ElGamal、ECC与密钥协商实战

做安全开发这些年接触最多的就是公钥算法这套体系。RSA、ElGamal、ECC、DH几乎所有的加密通信、数字签名、密钥协商场景都离不开这几个名字。很多人对算法名称耳熟能详可真要让把公式写出来或者解释清楚加密函数里每个变量怎么来的就支支吾吾了。尤其是像“RSA解密为什么是c^d mod n”“ElGamal解密时为什么要算个负指数”“ECDSA验签到底在验什么”这类问题不把公式彻底吃透遇到实际问题根本不知道怎么排查。这篇文章就把最常见公钥算法的加解密公式逐个拆开从密钥生成、加密公式、解密公式到签名验签公式逐项讲清楚来龙去脉和实操注意事项适合信息安全专业的学生、刚转行做密码学开发的工程师以及所有需要快速查漏补缺的系统架构师参考。1. 公钥算法的整体设计思路与现实选型1.1 为什么公钥算法要这么设计公钥算法的出现本质上是为了解决对称加密的一个死结两个人通信必须先安全地交换那把相同的密钥。如果在不安全信道上直接传密钥谁监听谁就能解密。公钥体系的思路很直白——把密钥拆成两半一半公开出去随便传一半自己藏起来永不泄露加密用公开的那一半解密必须用私藏的那一半。听起来像魔术但它是靠数学上的“单向性”实现的。什么叫单向性就是正向计算很容易反向推算极难。RSA靠的是大整数分解难题两个大素数相乘得到一个合数只需要毫秒级但把这个合数分解回两个素数计算量随位数指数级上升。ElGamal和DH靠的是离散对数难题给定底数和指数算出结果很容易但给定结果反推指数在精心选取的大素数域里几乎不可行。ECC靠的是椭圆曲线离散对数难题在曲线上做点加法容易但给定一个点和它被标量乘了多少倍求这个标量倍数极其困难。这个设计的精妙之处在于安全性不是靠算法保密实现的而是靠“私钥不泄露”这一个前提。公钥随便发给谁别人拿到了也只能用来加密或者验签做不了解密和签名。这也是为什么现代密码学体系里我们默认算法公开、参数公开唯独私钥必须物理隔离存放。1.2 不同公钥算法适合什么场景公钥算法各有各的脾气用错场景往往比不加密更危险。RSA目前依然是兼容性最好的公钥算法在证书体系如X.509证书、HTTPS握手、文件加密里用得最多。它的优势是数学直观、实现库成熟但缺点是密钥长度长、运算慢1024位以下的RSA已被证实不安全现在至少要求2048位。ElGamal在常规领域用得相对少但它是理解很多进阶方案的基础。它的密文是两段数据密文长度会膨胀一倍好处是引入了随机性同一个明文每次加密出来的密文都不一样被称为概率加密。这个特性在电子投票、门限密码、同态加密这些方向上有天然优势。ECC是后起之秀以更短的密钥达到同等级安全强度。256位椭圆的强度大致相当于3072位RSA。带宽和存储受限的场景比如物联网设备、移动端证书、区块链签名几乎都在用ECC。它的公式相对抽象但一旦理解了群运算反而比RSA更容易讲清楚。DH本身不算加解密算法它是密钥协商协议解决的是“两个人在公开信道上怎么把一个秘密商定出来”的问题。实际部署中往往用它的椭圆曲线版本ECDH。2. RSA加解密公式与实操要点2.1 RSA密钥生成与参数推导RSA的密钥生成是整个算法最核心的一步公式本身不复杂但每一步背后都有安全考量。第一步选两个大素数记作p和q。这两个数必须独立随机选取长度要相近但不要完全一样否则容易被特殊分解算法盯上。第二步计算n p × q这个n就是密钥模数公钥和私钥都共享它需要公开出去。第三步计算欧拉函数φ(n) (p - 1)(q - 1)这个值表示小于n且与n互素的整数个数私钥计算的关键参数就是它。第四步选择一个加密指数e要求满足1 e φ(n)并且gcd(e, φ(n)) 1即e和φ(n)互素。这个e就是公钥指数实际中通常固定取65537。65537是费马素数二进制是10000000000000001只有两个1bit做模幂运算时能极大减少乘法次数。而且它有良好的安全特性只要p和q足够大用这个e不会引入特别的薄弱点。第五步计算解密指数d满足d ≡ e⁻¹ mod φ(n)也就是e×d ≡ 1 mod φ(n)。d是私钥指数的核心必须保密。到这里密钥对就生成了公钥是(n, e)私钥是(n, d)。这里有一个无数人踩过的坑私钥里的p、q、φ(n)这些中间参数按规范应该销毁但是实操中很多密钥文件比如PKCS#1格式的RSA私钥会把这些参数一并存下来目的是用中国剩余定理加速私钥运算。存储本身没问题但一旦文件泄露攻击者能直接重建私钥所以对私钥文件的访问控制必须严格到位。2.2 RSA加密解密与签名验签公式假设明文消息是m加密过程就是做一次模幂运算加密c m^e mod n其中m必须满足0 ≤ m n。如果消息太长怎么办实际中不会直接拿RSA加密长消息因为RSA是慢速非对称算法也是定长算法——明文长度受密钥模数限制。标准做法是生成一个随机的对称密钥比如AES密钥用AES加密真正的内容再用RSA加密那把对称密钥。这种方式叫混合加密HTTPS、邮件加密全是这么干的。解密m c^d mod n为什么这个公式能还原出明文因为根据欧拉定理如果m与n互素那么m^φ(n) ≡ 1 mod n。从d ≡ e⁻¹ mod φ(n)可以推出e×d k×φ(n) 1于是c^d ≡ (m^e)^d ≡ m^(e×d) ≡ m^(k×φ(n)1) ≡ m × (m^φ(n))^k ≡ m mod n所以解密公式成立。这个推导是整个RSA加解密的根理解了它签名公式也就顺理成章了。RSA签名相当于用私钥“加密”一个摘要值。假设对消息m计算哈希得到h那么签名过程就是签名s h^d mod n验证签名时验证方用公钥做验签h s^e mod n如果h和消息哈希h相等签名有效。签名和加密在数学形式上完全一样只是操作密钥不同加密用公钥、解密用私钥签名用私钥、验签用公钥。这一点对称关系非常关键很多人搞混了签名和加密的方向就是因为没抓住这个本质。完整公式总结如下表操作使用密钥公式加密公钥(n, e)c m^e mod n解密私钥(n, d)m c^d mod n签名私钥(n, d)s h^d mod n验签公钥(n, e)h s^e mod n2.3 RSA安全性参数与常见坑RSA的实际安全边界比公式本身要复杂得多。密钥长度直接决定安全强度当前主流基线是2048位对应约112位安全强度如果处理的是长期敏感数据建议直接上3072位或4096位。1024位已经被学术界攻破多次属于明确不可用的范畴。第二个大坑是填充方案。教科书式的RSA——直接m^e mod n——叫“裸RSA”存在严重的安全问题确定性使得相同明文产生相同密文容易被频率分析而且由于模幂运算的代数结构攻击者可以把密文拆拼接制造出合法的密文块。因此实际应用中必须加填充目前两个主流标准是PKCS#1 v1.5和OAEP。OAEP引入了随机盐同一明文两次加密得到不同密文安全性更可靠新系统应当优先用它。签名侧对应的是PSS填充。第三个坑是私钥运算加速带来的信息泄露。用中国剩余定理加速RSA私钥运算时模数p和q会被分开处理如果硬件侧信道监测到运算差异理论上可能反推出p和q。几年前就有研究者通过CPU功耗分析成功恢复密钥的例子。应对手段是加入随机盲化因子即在计算前先乘一个随机数算完再除掉打乱侧信道上的统计规律。我在项目里要求所有涉及私钥运算的模块都必须带盲化逻辑哪怕性能损耗一点也不冒泄露的风险。3. ElGamal加解密公式详解3.1 ElGamal密钥生成与加密公式如果说RSA靠的是大数分解难题ElGamal靠的就是有限域上的离散对数难题。这个算法由El Gamal在1985年提出直接脱胎于Diffie-Hellman密钥交换理解起来有一条很清晰的脉络。密钥生成分三步。第一步选一个大素数p要求p足够大且p-1有大的素数因子这样才能构建一个安全的高阶循环群。第二步选一个生成元gg的阶要尽可能接近p-1这是保证离散对数难题成立的前提。第三步随机选取私钥x1 ≤ x ≤ p-2计算y g^x mod p公钥就是(p, g, y)私钥是x。加密过程是概率性的这一步一定要理解透彻。假设要给接收方发送明文mm必须小于p发送方做两件事选择一个随机数k要求1 ≤ k ≤ p-2且每次加密都必须重新随机取k绝不能复用计算两部分密文c1 g^k mod pc2 m × y^k mod p密文就是(c1, c2)这个二元素组。直观理解c1相当于一个临时“公钥”它把随机数k固化下来c2相当于用对方的公钥y做了k次幂运算后把明文m“藏”在这个结果背后。这里加密公式里有一个必须强调的细节k必须保持随机且一次性使用。如果同一个k加密了两个不同的明文攻击者用两个密文一比就能恢复出它们之间的线性关系还能解出真正的明文。我在审查一个旧系统时发现它是用时间戳直接当k用的结果多个密文的k值高度相关几乎等于把门敞开了。这个问题在ElGamal里是致命伤。3.2 ElGamal解密公式与运算本质解密时接收方拿到(c1, c2)私钥是x计算m c2 × (c1^x)⁻¹ mod p也就是c2乘上c1^x在模p下的逆元。为什么它能还原明文把加密公式代进去c2 × (c1^x)⁻¹ (m × y^k) × (g^k)^(-x) m × (g^x)^k × g^(-kx) m × g^(kx) × g^(-kx) m mod p所以等式成立。这里关键的一步是y^x和g^(kx)相互抵消的过程它本质上是Diffie-Hellman共享秘密的变形发送方用y^k作为加密因子接收方用对方的临时公钥c1和自己的私钥x算出同样的共享秘密c1^x g^(kx)两边在同一个群元素上对齐明文就被安全传递了。解密公式里那个负指数是许多初学者的困惑点。实际上你不需要真的计算负指数只需要计算c1^x然后求它在模p下的乘法逆元即可。模逆元运算可以用扩展欧几里得算法高效求出。ElGamal的密文长度是明文的两倍以上因为每个明文块都对应两个密文元素。传输效率不高但它天然支持概率加密、同态乘法运算适合做需要密文运算的进阶方案。现代应用中直接裸用ElGamal的场合不多但理解它的公式对学习门限密码、电子投票、可验证秘密分享非常有帮助。3.3 ElGamal的实用场景与注意事项ElGamal明文必须是小于p的整数。如果消息本身是字符串需要先编码成整数块。由于密文膨胀和性能开销它很少用于批量数据加密但在往下面这些方向走的时候它的价值反而体现出来门限解密多个参与方各自持有私钥分片每方对密文做部分解密合起来才能还原明文电子投票概率加密保证相同选票产生不同密文配合范围证明可以验证票数合法性同态乘法两个ElGamal密文相乘相当于它们明文的乘积加密结果这在隐私计算里是基础构件实操中还必须注意p和g的选择质量。p必须是强素数或安全素数即p 2q 1中的q也是素数g需要验证阶是否达到要求。很多人图省事直接从现成库拿默认参数这没问题但如果你在自研系统里自己生成参数建议至少用2048位以上的p且要做素性检测和子群攻击检测。更省心的做法是直接复用标准组参数比如RFC里推荐的模数群能避免很多自己踩坑的环节。4. ECC椭圆曲线算法公式详解4.1 椭圆曲线群运算与密钥生成ECC的公式体系和RSA、ElGamal完全不是一个风格。椭圆曲线不是椭圆形状它是一条满足特定方程的点集加上一套点运算规则。最常用的Weierstrass曲线方程是y² x³ ax b要求4a³ 27b² ≠ 0保证曲线没有奇异点也就是没有尖点和自交点。在这条曲线上定义一种“加法”运算两个点P和Q做“加法”得到第三个点R。几何上过P和Q两点做直线延长线交曲线于第三个点关于x轴做对称得到的点就是PQ。P和自己相加就是做切线。再加一个无穷远点O当作加法单位元这套点加运算就构成一个阿贝尔群。有了群运算就有了标量乘法nP表示n个P连加。这个运算就是椭圆曲线的“单向门”给定标量n和点P计算nP很快给定P和Q nP求n极难这就是椭圆曲线离散对数问题。ECC密钥生成极其简洁选择一条曲线指定一个基点G生成元随机选一个大整数d作为私钥计算公钥Q dG。严格说ECC本身是个公钥体系但它的“加密”不像RSA那样有单独的加解密公式而是建立在共享秘密点上。常用的加密方案有两种直接利用共享秘密点做对称密钥类似于DH或者用ECIES集成加密方案。4.2 ECIES加密解密公式ECIES是ECC体系里标准的公钥加密方案公式写出来其实很简练。假设Alice要把消息M发给BobBob的密钥对是私钥d_B和公钥Q_B。加密过程Alice执行选一个临时随机数k计算临时公钥R kG计算共享点S kQ_B (Sx, Sy)从Sx派生对称密钥K比如用哈希函数K KDF(Sx)用对称算法加密消息得到密文C Enc(K, M)附带对密文计算一个认证标签tag防止篡改Alice把(R, C, tag)发给Bob。解密过程Bob执行用自己的私钥d_B计算共享点S d_BR d_B(kG) kd_BG kQ_B可见S S同一共享点从Sx派生同样的对称密钥K用K解密C得到M并验证tagECIES的精髓在于“静态私钥临时密钥”的组合。R是临时公钥每次加密都不同所以同一个消息每次加密密文都不一样天然具备概率加密特性。整个过程中表面上没有直接加密公式但安全性完全建立在共享秘密点上只有持有私钥d_B的人才能把Alice的临时公钥R和自己的私钥组合出共享点。这里需要注意解密方必须验证收到的公钥确实属于对方否则第三方可以替换自己的公钥诱导对方计算错误共享点从而截获内容。ECIES一般会配合证书或公钥认证机制使用。4.3 ECDSA签名验签公式ECDSA是ECC体系里应用最广的签名算法比特币、以太坊、TLS的证书验证都在用它。它的公式比RSA签名复杂不少值得仔细展开。假设私钥为d公钥为Q dG消息M的哈希为e实际使用中是经过截断的哈希。签名过程从[1, n-1]中随机选取一个临时私钥kn是基点G的阶计算点R kG取其x坐标r Rx mod n计算s k⁻¹(e r×d) mod n签名输出为(r, s)。注意这里两个步骤都有随机性k必须每次重新生成且绝不能泄露。著名的教训就是如果两次签名用了同一个k攻击者可以直接恢复出私钥d。验签过程验证r和s都在[1, n-1]范围内计算w s⁻¹ mod n计算u1 e×w mod nu2 r×w mod n计算点V u1G u2Q如果V的x坐标的模n值等于r签名有效为什么这样能验签从签名公式反推s k⁻¹(e rd) mod n ⇒ k s⁻¹(e rd) we wrd u1 u2·d所以V (u1 u2·d)G u1G u2(dG) u1G u2Q正好就是签名时那个临时点R kG。如果V的x坐标等于r说明计算路径一致签名就通过了。ECDSA验签公式的核心逻辑在于整个运算把私钥映射进一个临时点坐标验签方只需要知道公钥Q就可以重新构造出那个临时点进行比对。这也回答了很多人问的“ECDSA验签时到底在验什么”——是在验证签名方是否知道私钥d而全程不需要暴露d。4.4 ECC参数选择与曲线安全ECC安全性极大依赖曲线参数。曲线方程里的a、b、基点G、阶n、余因子h这些参数都要精挑细选。目前行业公认的安全曲线是NIST P-256也叫secp256r1、Curve25519、secp256k1等。这些曲线经过了众多密码学家长期集体审查不建议自创曲线。自创曲线的历史教训太深刻了。前些年有个项目为了“显得技术高超”自己定义了一条椭圆曲线结果参数先天不足存在特殊弱点攻击者可以绕过离散对数难题直接破解。后来被审计团队发现整个系统被迫重构。曲线的群阶必须是足够大的素数或者素数乘以小余因子阶要抵抗Pollard rho攻击、MOV攻击等多种攻击路径这些不是普通开发者能设计好的。所以我的态度很明确除非你是专业密码学团队且有长期自研能力否则一律用经过验证的标准曲线。5. Diffie-Hellman密钥交换公式5.1 DH公式与中间人攻击Diffie-Hellman严格来说不是加密算法而是密钥协商协议。但它和ElGamal共享同一套数学基础公式同样值得讲透。假设Alice和Bob要在公开信道上确定共享密钥提前公开两个参数大素数p和生成元g。Alice随机选私密数a计算A g^a mod p发给BobBob随机选私密数b计算B g^b mod p发给Alice。Alice收到B后计算密钥K B^a mod p g^(ba) mod pBob收到A后计算K A^b g^(ab) mod p。因为(g^a)^b (g^b)^a g^(ab)两边算出的K就是同一个共享密钥。这个共享密钥K可以当种子用KDF派生后续的对称密钥。公式的本质非常简洁核心就是一个“交换幂次”的过程中间人即使拿到了A和B想从A反推a、或者从B反推b面临的都是离散对数难题计算上不可行。但是这里有一个公认的协议风险——中间人攻击。如果攻击者能在消息传递过程中同时冒充Alice和Bob他就能分别和双方各建立一对共享密钥然后转发所有消息。DH本身不提供身份认证只提供密钥协商。实际部署必须配合数字签名或证书来保证对方身份真实才能杜绝中间人拦截。很多新人对DH的误解就在这里以为用DH交换密钥就安全了忽略了对端身份验证结果被中间人耍得团团转。协议安全从来不是单个算法的功劳而是整个链路设计的结果。5.2 DH的作用与ECDH原始DH基于有限域上的模幂运算如果p是2048位每次幂运算开销不小。为了提升性能并缩短密钥字节数业界普遍转向ECDH即用椭圆曲线点运算替代模幂运算。ECDH的流程和DH几乎一样。Alice选私钥d_A计算公钥Q_A d_A × G发给BobBob选私钥d_B计算Q_B d_B × G发给Alice。此后Alice算S d_A × Q_B d_A × d_B × GBob算S d_B × Q_A d_B × d_A × G两人得到同一个共享点取该点的x坐标作为共享密钥材料。ECDH在TLS 1.3中承担了绝大多数的密钥协商任务配合ECDSA签名实现身份认证。实操心法上ECDH要求必须验证对方公钥确实在合法的曲线群上防止“无效曲线攻击”——攻击者把恶意构造的点发给对方使对方在弱曲线上做运算从而泄露私钥信息。许多主流密码学库会自动做点验证但如果你在使用底层API这个检查绝不能省。6. 常见问题与排查技巧实录6.1 明文长度限制问题RSA和ElGamal都有明文长度边界。RSA加密时明文m必须小于n。2048位RSA的n大约是256字节如果使用OAEP填充实际可加密数据长度是256 - 2×哈希长度 - 2。用SHA-256时OAEP最多只能加密256 - 32 - 2 222字节。ElGamal类似明文必须小于p而且密文膨胀成两个元素造成传输效率低。遇到“需要加密一个几KB的文件”时正确做法永远是混合加密先用对称算法生成会话密钥加密文件内容用公钥算法加密会话密钥。这个原则在HTTPS、PGP、各类安全协议中都是一致的。还有人容易踩的坑是给RSA塞入超过模数长度的明文程序往往会报错或静默截断不同库的处理方式还不一样调试起来相当痛苦。6.2 填充方案选择与兼容性不同年份写的系统填充方案兼容性差异经常让人抓狂。老系统可能用的是PKCS#1 v1.5填充新系统默认只有OAEP两边对接时就会出现“加密成功但解不开”的怪事。排查方法很简单看两边日志里的异常信息确认是不是padding异常再把两边的算法参数列出来逐项比对。我的建议是新开发系统优先用OAEP签名用PSS旧系统升级可以在构建配置里做成可切换填充模式的方案便于平滑过渡。同时要注意不要自己实现填充函数。标准库里的填充实现经过大量模糊测试和审计安全强度远高于手工代码。之前有一个项目为了提高“随机性”把OAEP的种子源改成了系统时间直接破坏了概率加密的语义属于典型的画蛇添足。6.3 侧信道与实现安全公式正确实现不对照样可能被攻破。最危险的几个实现层问题是密钥不隔离RSA私钥、ECC私钥以明文形式存到普通配置文件里或者随代码发到git仓库这比算法漏洞更致命随机数质量差ECC签名、ElGamal加密都依赖高质量随机数。随机数发生器被污染轻则让签名可预测重则直接泄露私钥私钥运算无盲化模幂运算中的中间值如果泄露可能被缓存侧信道或时序侧信道分析。RSA私钥运算必须做盲化处理ECC标量乘法要使用常数时间算法曲线点验证缺失ECDH和ECDSA都必须验证对方公钥是曲线上的合法点否则存在无效曲线攻击排查这些问题时先检查库版本和配置项再看审计日志中是否有异常计算耗时。比如一次RSA解密时间抖动异常可能说明盲化逻辑没有生效。最有效的防线还是用成熟密码学库比如OpenSSL、BoringSSL、libsodium、Java的JCA框架不要自己实现核心密码运算。7. 实操中的经验总结与建议7.1 选算法的通用决策路径项目里到底选哪套公钥算法我的决策路径通常是这样先看需求是加密还是签名还是密钥协商。加密场景通用首选是ECC的ECIES如果对接的老系统只支持RSA那就用RSAOAEP。签名场景通用首选是ECDSA或EdDSA证书体系里很多时候仍要用RSA兼容。密钥协商场景无脑选ECDH或基于标准曲线组的DH避免用自选参数。再看性能指标。如果设备主频低、RAM小ECC的优势非常明显。一个P-256签名只需64字节而RSA-2048签名是256字节验签速度上ECC也比RSA快好几倍。但同时要注意ECC的密钥生成和安全设计对底层库质量要求更高用错了曲线或参数可能反而比RSA更危险。7.2 安全维护的个人心得我在实际项目中总结了几条硬性纪律写下来供参考。第一永远不要自己发明密码算法或修改标准参数。哪怕改动一个看起来无关紧要的填充字节都可能引入灾难。公钥密码领域水太深公式之外还有太多实现级陷阱。第二所有密钥生命周期管理必须自动化。密钥生成、轮换、吊销、归档都要有统一平台定期检查证书有效期私钥的加密存储必须使用专门的密钥管理系统或硬件安全模块。第三善用开源库的默认安全配置。很多库默认就是安全的不要去为了兼容性下调安全强度。比如TLS库里默认的加密套件优先级往往是经过安全团队反复调整的贸然改成老算法会让你暴露在已知漏洞下。第四测试阶段就要加入负面测试用例。比如用大整数超过模数限制做边界测试、故意用相同的随机数测试签名是否产生相同输出、把密文篡改一位测试认证机制是否报错等。这些测试能提前暴露实现层的安全问题。公钥算法的公式看起来就那么几行真正难的是在纷繁复杂的工程细节里守住安全的底线。希望这篇拆解能帮你把底层逻辑理通遇到问题的时候能更快定位到根因。