本系列文章目录

1. 什么是密码学
2. 数论基础
3. 一文弄懂有限域
4. 传统密码：一文弄懂分组密码
5. 传统密码：一文弄懂流密码
6. 传统密码：一文弄懂散列函数
7. 后量子密码：基于编码密码学

在公钥密码学诞生之前，对称加密统治了数千年的加密史。其核心逻辑是加密与解密使用同一密钥。无论是古罗马的凯撒密码、中世纪的维吉尼亚密码，还是20世纪中叶的DES与AES，对称加密算法将加密效率和安全不断演进，但其始终未解决如何安全高效地共享密钥。

有人会说，提前设置一个安全通道交换密钥不就可以了吗？但安全通道本身也需要一个共享密钥，否则传输过去的密钥也无法解读。这就像"先有鸡还是先有蛋"的命题，陷入了一个无解的循环。有人又会说，那提前线下设置共享密钥总可以吧？当然可以，但如果双方距离太远呢？通过公开网络传输不安全，邮寄过去又有丢失或窃取的风险。这个看似简单的问题，在计算机网络时代被无限放大。

直到公钥密码学诞生，这个问题才得到安全高效的解决。

1976年，Whitfield Diffie与Martin Hellman发表了划时代论文《密码学的新方向》，首次提出了公钥密码学的构想。其核心突破在于加密和解密不再局限于同一把密钥，而是通过密钥对的形式，将密钥分为公钥和私钥。公钥可以公开，用于加密和验签；私钥需要保密，用于解密和签名。

1977年，MIT的三位学者Rivest、Shamir和Adleman提出了RSA算法，实现了真正的公钥加密，标志着公钥密码学的正式诞生。

RSA提出之后，密码学家们继续寻找基于其他数学难题的公钥加密方案。1985年，Neal Koblitz和Victor Miller分别独立地提出了椭圆曲线密码学（Elliptic Curve Cryptography，简称ECC）的概念。它的核心思想是：把之前用在普通数域上的离散对数问题，移植到椭圆曲线上的点群上。相比RSA依赖的大整数分解问题，ECDLP在同等安全强度下所需的密钥长度要短得多（例如256位的ECC安全性约等于3072位的RSA），运算更快、存储开销也更小。到了2004至2005年前后，ECC开始在各类安全系统中被广泛部署应用。

我国在公钥密码领域也有自主设计的标准。SM2椭圆曲线公钥密码算法于2010年12月首次公开发布，2012年成为商用密码标准（GM/T 0003-2012），2016年进一步升级为国家标准（GB/T 32918-2016）。SM2同样是基于椭圆曲线设计的，其安全性建立在椭圆曲线离散对数问题的难解性之上，在实现效率上相当于或略优于一些国际标准的同类ECC算法。

下面，我们从RSA算法开始，逐一介绍各个非对称算法原理。

1.1. RSA算法所需的数论基础

在数论基础章节中，我们曾介绍过质数、模运算、互质等关键内容，这里我们对相关概念进行简要回顾。

1. 质数
   质数是指大于1的自然数，除了1和它本身外，没有其他正整数能整除它。例如，2、3、5、7、11等均为质数。质数的重要性在于其不可分解性，这是下面RSA公钥算法安全性的核心依托。

2. 模运算
   模运算即求余运算。若两个整数a和b除以正整数m时余数相同，则称a和b对模m同余，记作 a ≡ b mod m，例如：26 ≡ 14 mod 12，因为两者除以12的余数均为2。

3. 互质关系
   若两个正整数a和b的最大公约数为1（即 gcd(a, b) = 1），则称它们互质。例如：7和15互质（公约数只有1），互质不一定要求两个数都是质数，例如15和32互质，虽然15非质数，但两数无共同因子，互质关系是欧拉函数和欧拉定理的基础。

4. 欧拉函数
   欧拉函数 φ(n) 计算小于n且与n互质的正整数的个数。例如，在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(8) = 4。

5. 欧拉定理
   若正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：
   a^φ(n) ≡ 1 (mod n)
   比如，3和7互质，而7的欧拉函数 φ(7)=6，所以 3^6 = 729 ≡ 1 mod 7。

6. 费马小定理
   当n是质数p时，欧拉定理简化为：
   a^(p−1) ≡ 1 (mod p)
   欧拉定理是RSA算法的数学核心，它保证了加密与解密过程的可逆性。

7. 模反元素
   若a与n互质，则存在整数b，使得：
   a × b ≡ 1 (mod n)
   b称为a模n的逆元。例如，3模11的逆元是4，因为 3×4 = 12 ≡ 1 mod 11。模反元素在RSA中用于生成私钥，是加密与解密的关键纽带。

1.1.1. 大数分解难题

大数分解难题说的是把两个大质数乘起来很容易，但拆解出乘积却极其困难。难题的源头，可以追溯到古希腊数学家欧几里得，他在《几何原本》中证明了算术基本定理：任何一个大于1的整数，都可以唯一地分解成若干个质数的乘积。这是大数分解问题的理论起点，但欧几里得只证明了"这种分解存在且唯一"，并没有给出"如何高效地找到这种分解"的方法。在接下来的两千多年里，数学家们一直在找各自办法，但都无法高效的完成，直到现在，对于这个问题，仍然没有找到数学上解密钥匙，只有依靠算力的暴力计算。

为了体会到难度，可以随手拿起一张纸，写下两个很大的质数：

p = 1,073,741,783
q = 1,073,741,791

用计算器算一下乘积，几秒钟就能得到：

n = 1,152,921,502,479,642,953

但反过来，如果给出这个153位的数字，告诉它是两个质数的乘积，要找出这两个质数，那就完全是另一回事了。不能用除法直接反推，因为除法需要知道其中一个乘数，而p和q都不知道的话，唯一能做的就是一个个试，从2开始，3、5、7、11……一个一个地试除，看看哪个能整除，如果这两个质数都接近十亿，平均要试几亿次才能找到答案。用手算的话，一辈子的时间都不够。

有人会说几亿次对计算机来说不是问题。确实，对于18位二进制的数字，现代计算机瞬间就能完成分解，但换成2048位的数字，情况就完全不同了。

把这两个308位的质数乘起来，电脑只需要几毫秒，但要把那个617位的乘积拆回那两个质数，目前世界上最快的计算机集群，用最先进的分解算法，也做不到。

RSA算法正是依靠大数分解难题正向计算容易、反向计算困难的陷门特性，构建起来的密码算法。下面我们看其怎么应用了这个难题。

1.1.2. RSA算法

RSA理论背景深厚，但算法的流程并不复杂，这其实是几乎所有密码算法的共性，核心逻辑用几个数论公式就能说清。但如果只列公式，估计对RSA怎么把数论几个公式串联起来仍不清楚，不如从一段故事讲起，看看这个设计是怎么一步步走出来的。

1976年，Diffie和Hellman发表了划时代的论文《密码学的新方向》，第一次提出了公钥密码学的构想，他们指出了打破对称密码的新方向：加密和解密可以使用不同的密钥。但他们没有找到实现这个想法的具体方法，而把关键问题留给了后来者，只要找到一个合适的单向函数，也就是正向计算容易、反向计算极其困难的数学函数。不过，他们设计了一个密钥交换协议，展示了模幂运算 g^a mod p 在密码学中的可行性，这个协议的逻辑是底数g和模数p公开，通信双方各自保密自己的指数a和b，通过交换 g^a mod p 和 g^b mod p，最终计算出共享密钥 g^(ab) mod p。这种"公开底数、保密指数"的形式，让密码学界第一次看到模幂运算可以在公开信道中完成某种安全交换。

Diffie和Hellman的这篇论文，也成了RSA三人组后来工作的起点。

当时在MIT任教的Ron Rivest读到了这篇论文，深受启发。他和同事Adi Shamir、Leonard Adleman组成了一个"攻防"团队：Rivest和Shamir负责设计算法方案，Adleman负责寻找漏洞并破解，今天我们看到RSA的公式，只有短短几行，或许会感叹怎么想到这么巧妙的方法，但很难体会设计者背后的艰辛，实际上，他们先后设计了42个方案，包括背包算法、置换多项式等多种思路，全部宣告失败，这个过程持续了整整一年。

转机发生在1977年4月的一个夜晚，三人在一位学生家中吃完逾越节晚餐，开怀畅饮后，午夜时分各自回家。Rivest到家后毫无睡意，躺在沙发上翻看数学教材，重新梳理这道难题，换了全新思路展开推演。

回过头看，他们被一套根深蒂固的思维框了整整一年。香农在论文《保密系统的通信理论》明确提出：一个安全的密码系统，必须通过扩散和混淆来打乱明文和密文之间的统计关系，让攻击者即使截获大量密文，也无法反推出任何有用的信息。这套理论统治了密码学界二十多年，所有对称密码的设计全都沿着这个方向走。RSA三人组的前42个方案，背包算法也好，置换多项式也好，骨子里都是同一个思路：找一个足够复杂的函数来搅拌明文，让它乱到攻击者分析不出规律。结果全被Adleman攻破了。但这里有一个被所有人忽略的细节：香农的理论是针对对称密码的，它回答的是"共享密钥的情况下如何安全加密"，从来没有也从未声称能覆盖"没有共享密钥"的场景。事实上，就在1976年，香农本人还公开表示他不相信公钥密码学是可行的。当Rivest在那个失眠的夜晚翻开数学教材，他才真正意识到，公钥加密完全不必遵循对称密码的规则，安全不一定来自"搅得足够乱"，也可以来自"算得足够难"。Diffie和Hellman已经把模幂运算这个"算起来容易、反推极难"的单向函数摆在了所有人面前，只是包括RSA三人组在内的整个密码学界，之前都被香农的框架死死框住，没人往那个方向多走一步。

因此，关键突破仍然来自于DH密钥交换用的模幂运的范式 g^a mod p，在DH密码交换协议，秘密藏在了指数a里，Rivest想到如果把保密的对象换一下，把明文M放在底数的位置，变成 C = M^e mod n，这个公式，对于Rivest理论功底深厚的密码学家来说，想到用欧拉定理来还原明文，几乎是顺理成章的事，因为如果d和e满足以下关系：

e × d ≡ 1 (mod φ(n))（式1）

那么就有 (M^e)^d ≡ M (mod n)，这样就把M还原出来，当然，这里有一个前提，M必须小于n。因为 x mod n 的结果是一个0到n-1之间的整数，如果M本来就小于n，那么这个余数就是M，否则，得到的只是与M同余的一个数，而不是原来的M，这样一来，加密运算的可逆性就有了。但到这里，C = M^e mod n 仍只是一个普通的幂运算公式，我相信Diffie和Hellman也一定无数次的运算这个公式，只是他们走到这里就停住了，而Rivest沿着这个式子继续往前走。

Rivest想到，如果把d隐藏起来，解密的路就堵死了。隐藏d的方法正是最关键的一步，因为e和d的关系来自于式1，式中的 φ(n) 是欧拉函数，如果取 n = p × q（p、q为两个大质数），则有

φ(n) = (p−1) × (q−1)

也就是说，如果想从这个式子 C = M^e mod n 消掉e得到明文，那么需要先知道d，而想得到d，需要先知道 φ(n) 的值，但前置条件是知道p、q的值，而p和q又是大数的乘积，这样把RSA算法的难题和大数分解联系起来，当然，如果攻击者觉得大数分解难题很难，那么直接去数 φ(n) 的值也是一种方法，因为 φ(n) 意思是小于等于n且与n互质的正整数的个数，但是n如果数值很大，例如是2048位（二进制），换算成十进制大约是617位数字，要数也要数到天荒地老。

那个失眠的夜晚，Rivest一气呵成写完了论文的大部分内容。第二天早上，他把方案拿给Adleman，这一次，Adleman认输了，这个方案是可行的，RSA算法就这样诞生了。

下面，我们正式介绍一下RSA算法的流程。

1.1.2.1. RSA加密算法流程

历史讲完，现在正式进入RSA的算法流程。有了前面的背景，再去看这几个公式，应该不会觉得太陌生了。

（1）密钥生成阶段

1. 选取两个大质数p和q
   RSA的第一步是随机挑选两个大质数，记为p和q。实际应用中，p和q通常为1024位甚至更高（2048位已成为当前安全标准），使得它们的乘积 n = p × q 难以被分解。

2. 计算模数n
   将p和q相乘，得到模数：
   n = p × q
   n将作为公钥的一部分公开。这就是前面故事里提到的那个"n"，Rivest把明文放在底数位置时，模数从DH中的p变成了n，而n的构造方式决定了后面的一切。

3. 计算欧拉函数 φ(n)
   当 n = p × q 且p、q均为质数时，欧拉函数满足：
   φ(n) = (p−1) × (q−1)
   这个 φ(n) 正是故事里Rivest用来隐藏d的那道门，知道它就能算出d，但算它必须先知道p和q，而知道p和q就得分解n。

4. 选择加密指数e
   选择一个整数e作为加密指数，需满足：
   1 < e < φ(n)，且 gcd(e, φ(n)) = 1
   e与 φ(n) 互质，目的是保证e的模逆元存在，也就是保证d能够算出来。
   实际应用中，e通常取65537。它是费马数 2^16 + 1，二进制表示为 10000000000000001，仅有两位为1，在快速幂运算中效率极高；同时作为较大的质数，能有效抵御针对小指数的低指数攻击。快速幂的核心思想是把指数拆成二进制位，通过逐次平方和选择性相乘，在每一步都对n取模，使得中间结果始终保持在小于n的范围内。65537的二进制只有两个1，意味着计算过程中需要额外乘法的次数极少，这也是为什么它成为实际应用中的标准选择。同时，65537本身就是质数，天然满足与 φ(n) 互质的条件（前提是 φ(n) 不被65537整除），避免了额外的筛选成本。

5. 计算解密指数d
   求解满足以下同余式的整数d：
   e × d ≡ 1 (mod φ(n))
   d就是e模 φ(n) 的模逆元，这就是故事里Rivest想要"藏起来"的那个d。

6. 生成密钥对
   公钥可以公开，私钥不公开，因此要把d隐藏了，隐藏其是私钥的一部分，而e公开，通过它来加密明文，所以公钥和私钥分别如下：

   • 公钥：(e, n) —— 加密指数和模数
   • 私钥：(d, n) —— 解密指数和模数
     注意，私钥只需要保留 φ(n)，p、q和 φ(n) 在生成d之后就可以销毁了，它们已经完成了使命，留着反而增加泄露风险，另外，注意到公钥和私钥是有关联的。攻击者拿到了 (e,n)，理论上可以尝试反推d。但反推d需要先知道 φ(n)，意味着同样被大数分解难题给拦住了。

（2）加密阶段

发送方要向接收方发送明文M时，需确保 0 < M < n。然后使用接收方的公钥 (e, n) 进行加密：

C = M^e mod n

其中C为加密后的密文。

这就是故事里Rivest在沙发上写下的那个公式——把明文M放在底数位置，用公钥e做指数。计算上只是一次模幂运算，正向极其容易。

关于e = 65537的补充：代入加密公式后是 C = M^65537 mod n。这个指数看似巨大，但借助快速幂算法，实际计算量并不大。快速幂将指数拆成二进制位，通过逐次平方和选择性相乘，在每一步都对n取模，使中间结果始终保持在小于n的范围内。65537的二进制 10000000000000001 中只有两个1，意味着计算过程中需要额外乘法的次数极少，这也是它成为实际应用标准的重要原因。

（3）解密阶段

接收方收到密文C后，使用自己的私钥 (d, n) 进行解密：

M = C^d mod n

推导如下：

e × d ≡ 1 (mod φ(n))

所以存在某个整数k，使得：

e × d = k × φ(n) + 1

k的具体值是多少不重要，重要的是它存在。又因为：

C ≡ M^e (mod n)

代入解密公式：

C^d ≡ (M^e)^d = M^(e×d) = M^(k×φ(n)+1) (mod n)

根据欧拉定理，当M与n互质时：

M^φ(n) ≡ 1 (mod n)

于是：

M^(k×φ(n)+1) ≡ M × (M^φ(n))^k ≡ M × 1^k ≡ M (mod n)

明文就还原出来了。

1.1.2.2. RSA签名算法流程

前面介绍了RSA加密算法，解决了别人怎么把消息安全地传给我的问题。但加密只是公钥密码的一个应用方向，另一个同样重要的方向是数字签名：用私钥对消息盖章，任何人用公钥可以验证这个章是不是真的。

RSA签名和RSA加密在数学上是"互逆"的：加密用公钥、解密用私钥；签名用私钥、验签用公钥。但两者解决的问题完全不同。

（一）签名生成（私钥签名）

假设发送方A要发送一条消息M给接收B，并且要让B能够验证这条消息确实来自A、没有被篡改过。

A用自己保密的私钥d对消息进行签名。但RSA算法处理的是整数，不能直接对任意长度的消息做运算，所以先要对消息做杂凑处理：

h = H(M)

其中H是一个杂凑函数（如SHA-256），将任意长度的消息压缩成一个固定长度的杂凑值e。然后对杂凑值e做签名运算，这样做有两个好处：一是任意长度的消息都能被处理，二是杂凑值比原始消息短得多，签名运算更快，签名的公式如下：

s = h^d mod n

这里的s就是签名值。

（二）签名验证（公钥验签）

接收方B收到消息M和签名s后，用A的公钥 (e,n) 进行验证：

1. 计算消息M的杂凑值：
   h' = H(M)
2. 用公钥对签名s做解密运算（即恢复出签名时加密的那个值）：
   h'' = s^e mod n
3. 判断 h'' 是否等于 h'。
   如果相等，说明签名有效；否则签名无效。

RSA的加密和签名在数学形式上是对称的，只是密钥的使用方向相反。对于同一个公钥对，加密时用e、解密时用d，签名时用d、验签时用e，两者使用的指数正好对调，相比后面要介绍的椭圆曲线签名要简单得多。

1.2. 椭圆曲线算法

RSA的成功证明了公钥密码学这条路走得通，也验证了一个可行的范式，即任何一个足够难的数学问题，都有可能被改造成加密算法。这像一把火，点燃了整个密码学界探索新方向的热情，椭圆曲线密码学（Elliptic Curve Cryptography，简称ECC）正是在这股探索浪潮中诞生。

1985年，IBM研究员Victor Miller在CRYPTO国际密码会议上，率先提出利用有限域椭圆曲线有理点构成的循环群搭建公钥密码系统；几乎同一时间，华盛顿大学数学家Neal Koblitz独立推导出完全一致的思路，并于1987年在期刊正式发表完整论文。

但从理论构思到大规模商用，ECC足足蛰伏了近二十年，多重现实壁垒将它挡在主流之外。彼时RSA如日中天，垄断整个公钥密码赛道，是行业公认的非对称算法代名词，其具有完整国际标准体系、全产业链厂商配套、数十年工程落地积累，教科书、商用软硬件几乎全部默认采用RSA。反观ECC，仅有几篇晦涩的数学论文支撑，椭圆曲线离散对数理论理解门槛远高于大数分解；再加加拿大Certicom公司持有全套ECC商用专利，早年企业落地必须承担高额授权费，自研商用实现极易触碰专利红线，进一步劝退商业部署。

随着硬件算力与分解算法持续迭代，经典计算机破解大数分解的速度不断提升，RSA为守住同等安全强度只能持续拉长密钥，2048位、3072位乃至更长密钥成为标配，变得越来越臃肿。于是，密码学家们想到ECC更短的密钥，更高的安全强度的优势，行业迎来转向ECC的契机。IEEE、ANSI、ISO等国际标准组织先后将ECC纳入正式标准，扫清标准化障碍；2005年美国国家安全局（NSA）正式发布Suite B密码套件，将ECC定为保护政府敏感非涉密（SBU）信息唯一的非对称密码方案，这是ECC安全能力获得国家级权威背书的标志性事件。

有了官方标准与政府落地示范，叠加2000年后物联网、移动终端普及带来轻量化加密刚需，ECC开始在移动支付、智能硬件、TLS网络、数字签名等场景批量落地，逐步成为新一代非对称密码算法的主流选择。

如果说RSA的故事像一场"顿悟"，而ECC的故事更像一场"防守反击"叙事模板：一个强大的旧霸主统治着一切。一个新玩家在角落里默默成长，它有某种旧霸主不具备的"基因优势"。等环境变化，旧霸主的优势变成包袱，新玩家就走了出来的爽文故事。

1.2.1. 椭圆曲线：一个"名不副实"的数学玩笑

说到椭圆，我们脑海中会立刻浮现出一个闭合的卵形曲线。但椭圆曲线加密里用的"椭圆曲线"，并不是这种形状，而是如下图的形状，和椭圆形状毫无相似之处。但名字里都带"椭圆"二字，它们之间确实有那么一点渊源。这就要从数学史上一段关于"椭圆周长"的故事说起了。

（图：椭圆曲线示意图）

大约在17世纪，数学家们开始研究一个看起来很简单的问题：椭圆的周长到底怎么算？

圆的周长有公式 C = 2πr，简洁又优美。但到了椭圆这里，事情就没那么简单了。椭圆的方程是 x^2/a^2 + y^2/b^2 = 1，想要计算它的周长，就需要求这样一个积分：

L = 4a ∫_0^(π/2) √(1 − e^2 sin^2θ) dθ

其中e是椭圆的离心率。

数学家们算了半天，发现这个积分没法用我们熟悉的初等函数，例如多项式、指数、三角函数之类表达出来。换句话说，它积不出来。牛顿和沃利斯都尝试过，只能把它展开成无穷级数来近似计算。

后来，这类"积不出来"但又经常出现的积分，被命名为椭圆积分（Elliptic Integrals）。

再后来，数学家雅可比、阿贝尔等人进一步研究，发现椭圆积分和一类三次方程 y^2 = x^3 + ax + b 的几何性质有着深刻的联系。于是，这条三次曲线就被顺手命名为椭圆曲线。

所以，"椭圆曲线"这个名字，纯粹是因为它和"椭圆周长"这道题在数学上同根同源，而不是因为它长得像椭圆。

因此，椭圆曲线到底和椭圆有什么关系？就像老婆饼里没有老婆一样——名字里有，实际上没有。

1.2.2. 椭圆曲线的加法：椭圆曲线上的"桌球游戏"

ECC算法最常用的椭圆曲线方程是：

y^2 = x^3 + ax + b (a, b ∈ GF(p), 4a^3 + 27b^2 ≠ 0)（1）

这里有一个限制条件：4a^3 + 27b^2 ≠ 0。这个条件是为了保证曲线不包含奇点，换句话说，确保曲线上任意一点都存在切线。例如下面两幅图，分别为 y^2 = x^3（左）和 y^2 = x^3 − 3x + 2（右），两者都符合 4a^3 + 27b^2 = 0，从图上可以清楚地看到，左边出现了尖点，右边出现了自交。在这两个位置，切线不存在。之所以要求曲线上每一点都有切线，是为了让接下来的椭圆曲线加法能够顺利定义。

在椭圆曲线的运算体系里，对于曲线上任意两点A和B，可以作一条过这两点的直线，找到该直线与椭圆曲线的第三个交点，然后将这个交点关于x轴作对称，得到的点就被定义为A与B的"和"，记作 A + B，如下图所示。

这里可能会产生一个疑问：为什么一定能找到这样一个关于x轴对称的点？这要从椭圆曲线自身的特性说起。曲线的方程中，y是以平方的形式出现的。这意味着，如果点 P = (x, y) 在曲线上，那么将它的纵坐标取反，得到点 −P = (x, −y)，也必然在同一条曲线上。换句话说，曲线上任意一点关于x轴的对称点，仍然属于这条曲线。这个性质保证了上述加法定义中的对称点一定存在，椭圆曲线上的加法运算也因此有了坚实的几何基础。

当点B沿着曲线逐渐靠近点A，直至与A完全重合时，就出现了 A + A 的情形，也就是点与自身相加。那么，这种特殊情况该如何处理？

这时，原本"过两点作直线"的规则不再适用，因为两点重合后无法确定一条直线。解决方法是用曲线在点A处的切线来代替那条割线。作出这条切线后，找到它与椭圆曲线的另一个交点，再将该交点关于x轴作对称，得到的点就是 A + A，记作 2A。

这也正是前面要求曲线必须光滑的原因，如果曲线在某点有尖点或自交，切线就可能不存在或无法唯一确定，2A 的计算也就无从谈起。所以，"处处有切线"这个条件，本质上是在为倍点运算铺路。

椭圆曲线加法的操作过程，像是在一张特制的椭圆球桌上打桌球。我们操控母球A以特定角度撞击子球B时，两球碰撞的动量会沿一条直线延伸，这条轨迹与椭圆曲线相交后，和桌球触边反弹一样，反弹到x轴的另一侧。

在真实的桌球运动中，如果击球力度或角度不对，会把球撞出球桌。在椭圆曲线的加法中，也存在这种"出界"现象，例如下图，当计算 2A 时，过点A的切线若垂直于x轴（斜率无穷大），这条直线将不与椭圆曲线产生第三个交点，为了处理这种情况，数学家引入了一个虚拟的点：无穷远点，记作 O。

在椭圆曲线加法体系中，这个无穷远点被定义为加法单位元，满足：

P + O = P

它的作用就像实数中的0一样。

引入无穷远点，本质上是为了让椭圆曲线上的加法运算保持封闭性：任意两个点相加，结果仍然在曲线上（要么是一个实体点，要么是这个特殊的无穷远点）。即便切线垂直导致出界，运算结果也能在数学空间里找到对应，出界的轨迹穿过无穷远点后"回来"，回到加法单位元，从而保证整个运算逻辑自洽。

有人可能会想：这个加法规则是数学家随便规定的吧？毕竟"过两点作直线，找交点，再翻折"，听起来像是一套自娱自乐的游戏规则。

还真不是。

数学家不是规定了这套规则，而是发现了这套规则。椭圆曲线本身长成那个样子，它的几何结构就天然决定了：只能这样定义加法，才能让所有点形成一个封闭的、自洽的代数系统，也就是阿贝尔群。

阿贝尔群，说通俗点就是一群元素之间可以做一种加法运算，而且这个加法和我们平时数数、算账的感觉差不多，算出来的结果还在这个圈子里，交换顺序不影响结果。

拆开来说，它满足四条规矩：

• 封闭性：在这个圈子里随便取两个数，用这种加法算一下，结果还在这个圈子里，不会跑出去。就像整数加法：两个整数相加，结果还是整数，不会变成小数。
• 结合律：先加谁后加谁，结果一样，(a+b)+c = a+(b+c)。
• 交换律：谁加谁无所谓，顺序不影响结果。a+b = b+a。这一点是阿贝尔群特有的，不是所有群都满足交换律，比如矩阵乘法就不换顺序。阿贝尔群的特点是可以随便换，所以也叫做交换群。
• 有零点和相反数：圈子里有一个零元素，任何数加上它还是自己（a+0 = a），而且每个数都有一个"相反数"，加上去就回到零（a+(-a) = 0），就像我们熟悉的整数加减法一样。

椭圆曲线上定义完加法之后，恰好满足上面这几条，于是数学家们就能站在前人的肩膀上，直接把群论里现成的工具拿过来用。当然我们更关心的是，定义了加法后，和加密有什么关系。

想象一下这样一场台球游戏：击球者背对着观察者，在球桌上随机击打母球。母球在台面上不断碰撞、反弹，沿着一条复杂的轨迹运动，最终停在某个位置。这时，观察者转过身来，看到的是台面上静止的球局。即便他对桌球运动有着专业级的理解，熟知各种击球技巧和力学原理，面对眼前的局面，想要逆向推演出母球从起始点出发、经历了怎样一系列碰撞才抵达当前位置，几乎是不可能完成的任务。

而对于击球者来说，情况完全不同。母球走过的每一段轨迹、每一次碰撞的角度与时机、每一次反弹的方向，他都了然于胸。整个运动过程在他眼中是清晰而确定的。正向推演轻而易举，逆向回溯却困难重重，这种特性，恰好构成了一个优秀陷门函数的基础。

回到椭圆曲线加法运算上来。每一次加法运算，都决定了结果在曲线上的落点；不同次数的加法，对应着不同的最终位置。这里的加法次数，好比台球场景中击球的操作记录，可以作为私钥，由击球者牢牢掌握；而最终在椭圆曲线上确定的那个落点位置，则好比台球静止后的位置，可以作为公钥，公开给所有人看到。

当然，这只是一个比喻。椭圆曲线加法的逆向困难，并非来自过程信息的丢失，而是来自椭圆曲线离散对数问题本身的计算难度：给定点P和 Q = kP，求k在计算上不可行。

1.2.3. 有限域椭圆曲线

上面的简化曲线，适合用来解释椭圆曲线的基本概念，但不能直接用于密码学。原因在于，上面讨论的椭圆曲线定义在实数域上，点集是连续的、无限的，相应的加法运算构成一个无限阿贝尔群。而连续空间中的计算依赖浮点数运算，存在精度误差，无法保证结果的唯一性和确定性，加密运算偏偏要求精确，不能有半点含糊，否则加密后就无法正确解密。

解决办法是把椭圆曲线搬到有限域上，改造方法很直接，将所有运算限制在模p下进行，公式如下：

y^2 = x^3 + ax + b (mod p) (a, b ∈ GF(p), 4a^3 + 27b^2 ≠ 0 (mod p))

这个公式意思找出所有满足左边 mod p = 右边 mod p 的整数点 (x, y)，其中x和y都在0到p-1之间。

举个例子，在有限域 F_23 中，给定椭圆曲线方程

y^2 = x^3 + 2x + 5 (mod 23)

取点 (x, y) = (3, 10)：

• 右侧计算：3^3 + 2×3 + 5 = 27 + 6 + 5 = 38，38再对23取模等于15
• 左侧计算：10^2 = 100，再拿100对23取模等于8

左右两侧不相等（8 ≠ 15），说明 (3, 10) 不在这条曲线上，而 (x, y) = (9, 4)，经过同样的计算方法，可以发现这个点在经过有限域改造的曲线上。

有人可能会问：如果遇到小数，比如 (1.2, 5.8) 这样的点怎么办？实际上，在有限域中，x和y只能是0到 p−1 之间的整数，不存在小数。这也意味着，有限域上的椭圆曲线不再是连续的曲线，而是离散的数据点。

下图左侧是实数域上的椭圆曲线（连续的），右侧是经过有限域改造后的椭圆曲线（离散的）。从几何曲线到代数点群，从连续数学到离散数学，这是一次彻底的范式迁移，也是密码学真正追求的完美形态。

（图：实数域椭圆曲线 vs 有限域椭圆曲线）

在实数域的椭圆曲线体系里，椭圆曲线加法规则有着直观的几何意义。曲线上任意一点关于x轴的对称点必然也处于该曲线上，这一特性符合阿贝尔群结构中负元的概念，也就是说，对于曲线上的点 P = (x, y)，其负元 -P = (x, -y)，二者相加会得到无穷远点。

然而，当视角切换到有限域的椭圆曲线时，情况发生了显著变化。在有限域中，点的坐标取值范围是从0到 (p - 1) 的非负整数，意味着有限域里不存在直观几何意义上的x轴对称点。所以，我们不能再简单生硬地套用实数域中基于x轴对称来确定负元的方式。

但问题是：密码学需要阿贝尔群结构，而阿贝尔群必须有逆元。如果我们不能在有限域上定义负元，那椭圆曲线仍不能用于密码学。

几何直观没了，但代数结构还在。关键是抓住负元的本质：

逆元就是那个能让 P + (-P) = O 的点，在实数域上，这个点靠画对称轴找到；在有限域上，没有对称轴可画，但我们可以用代数方式来定义：

-P = (x, -y mod p)

验证一下：因为 (-y mod p)^2 ≡ y^2 (mod p)，所以如果 (x, y) 在曲线上，(x, -y mod p) 也一定在曲线上。这就是有限域上的"负元"，它用模运算替代了几何对称。

有限域上的加法运算可以想象成一个贪吃蛇游戏：

在实数域上，两点连线找交点，是光滑连续的。在有限域上，同样作两点连线，但直线延伸出去后，一旦坐标超出范围（超过 p−1），就"穿墙"从另一侧回来，就像贪吃蛇撞到墙后从对面出现一样。直线在有限域上不断"穿墙"，直到撞到曲线上的一个离散点，然后翻折到 (x, -y mod p)。

这个穿墙操作，本质上就是模运算。

1.2.4. 椭圆曲线离散对数难题

有了前面的理论基础，我们可以来看椭圆曲线离散对数问题（Elliptic Curve Discrete Logarithm Problem，ECDLP）了，其是椭圆曲线密码学的安全根基，正如大数分解难题是RSA算法安全根基一样。

这个问题可以这样表述：

在一条椭圆曲线上，已知一个点G（称为基点）和另一个点 K = kG（即点G自加k次得到的结果），求k是多少。

正向很容易：给k和G，算K，只需要做k次加法，实际用快速算法，几百次运算就能完成。

反向极其困难：给G和K，反推出k。唯一的通用方法是暴力搜索，从1开始，逐个试 1G, 2G, 3G, …，直到找到等于K的那个。如果k是一个256位的数（大约10^77量级），搜索空间比宇宙中的原子总数还要大，穷举完全不可行。

难题主要来自于，实数域椭圆曲线的点，其距离和顺序在有限域上完全消失了。

在实数域上，点 1G, 2G, 3G, ... 在曲线上是连续移动的，1G 在旁边，2G 在稍远一点的位置，3G 再远一点，从终点走回来，每走一步都能看到上一个点的位置，这是有规律的。

但在有限域上，这些都没有了，可能 1G 在一个角落，2G 在完全相反的另一个位置，3G 又跳到了另一个地方，点的排列是伪随机的、混乱的、毫无规律的，拿到K之后，站在K的位置，根本不知道上一个点在哪个方向，因此，目前没有比暴力搜索更有效的通用解法，这正是ECC安全性的核心，不像RSA有亚指数级的分解算法（如数域筛法），ECDLP目前只有指数级的算法，这意味着ECC可以用更短的密钥达到更高的安全级别。

1.2.5. 椭圆曲线加密算法（ECC）

有了前面的铺垫，现在看ECC的算法流程就清晰多了。整个过程和RSA类似，也分为密钥生成、加密、解密三个阶段，但数学基础从"大整数分解"换成了"椭圆曲线离散对数"。

一、密钥生成阶段

1. 选取椭圆曲线和基点
   通信双方共同选定一条椭圆曲线E和一个基点G（即曲线上一个公开的点）。这些参数是公开的，类似RSA中的公钥指数e的选取标准。
   曲线的方程形式为：
   y^2 ≡ x^3 + ax + b (mod p)
   其中p是一个大质数，a、b满足 4a^3 + 27b^2 ≠ 0 (mod p)。基点G的阶为n（即 nG = O，n是一个大质数）。

2. 选取私钥
   发送方随机选取一个整数k（1 < k < n），作为私钥。这个就是点自加的次数，相当于台球场景中击球的"操作记录"，由用户自己保密。

3. 计算公钥
   计算点：
   K = kG
   即基点G自加k次，得到曲线上的另一个点K，作为公钥。

4. 生成密钥对

   • 私钥：k（一个整数）
   • 公钥：K（椭圆曲线上的一个点）

二、加密阶段

假设发送方要把明文M发送给接收方（接收方已经公开了自己的公钥K和曲线参数）。

和RSA加密不同，RSA可以把明文当作底数 C = M^e mod n，在ECC算法中，需要先把明文编码到椭圆曲线上，使之成为一个点 P_m。常见做法是把明文映射到x坐标，代入曲线方程看是否有对应的y值，如果有，这个点就在曲线上；如果没有，就微调x再试，直到找到一个合法点。接收方解密得到 P_m 后，从x坐标中还原出明文。不过，这个编码过程并非总是能一次性成功，有些明文可能需要调整多次才能找到合法点。因此在实际应用中，ECC更常用于密钥交换（如ECDH），而非直接加密消息。

发送方随机选取一个临时整数r（保密的），然后计算两个点：

C_1 = rG
C_2 = P_m + rK

其中K是接收方的公钥。

发送方将 (C_1, C_2) 作为密文发送给接收方。这一步，如果攻击者没有私钥k，想还原明文 P_m，理论上只要算出 rK 就行了，但是从 rG 和K算出 rK，他面临两个选择：

• 从 C_1 = rG 反推r：这是椭圆曲线离散对数问题。
• 从 K = kG 反推k：这也是椭圆曲线离散对数问题。

因此攻击者无法还原。

三、解密阶段

接收方收到密文 (C_1, C_2) 后，用自己的私钥k进行计算：

P_m = C_2 - kC_1

能还原是因为：

C_2 - kC_1 = (P_m + rK) - k(rG) = P_m + r(kG) - k(rG) = P_m

所以：

P_m = C_2 - kC_1

明文点 P_m 被成功还原，再解码回原始消息。

四、和RSA对比

从流程上看，ECC和RSA有几个明显的区别：

对比维度	RSA	ECC
公钥形式	两个整数 (e, n)	一个点K（包含两个坐标）
私钥形式	单个整数d	单个整数k
核心加密运算	模幂运算	椭圆曲线标量乘法 K = kG
底层数学困难问题	大整数分解问题	椭圆曲线离散对数问题
同等256位安全强度密钥长度	3072位	256位
加密后密文长度变化	密文长度与模数等长，膨胀小	密文明显膨胀（密文存储两个曲线点坐标）

另一个值得注意的差异是：RSA加密后密文长度和密钥长度基本一致，而ECC加密会产生两个点 (C_1, C_2)，存在一定的数据膨胀。这也是ECC在实际应用中常被用于密钥协商（如ECDH）而非直接加密的原因，因为直接加密的带宽开销相对较大。

五、小结

ECC的算法流程可以用一句话概括：

选一条曲线、定一个基点、取一个随机数作为私钥、做一次标量乘法得到公钥——然后像DH协议一样交换公钥、协商共享密钥。

和RSA相比，ECC的数学更抽象，但核心逻辑反而更简洁：RSA依赖的是"乘法容易、分解困难"，ECC依赖的是"加法容易、反推次数困难"。前者拼的是数论，后者拼的是几何加数论。而最终落地时，ECC凭借更短的密钥、更快的计算、更低的功耗，成为了移动互联网和物联网时代的首选。

1.2.6. 椭圆曲线签名算法（ECDSA）

和加密相比，椭圆曲线签名算法在现实中的应用更为广泛。TLS 1.3、JWT（JSON Web Token）等都在使用它。签名解决了另一个核心问题：验证消息的真实性和完整性，并确认发送者的身份，也就是证明这条消息确实是由持有私钥的那个人发送的，而且中途没有被篡改过。

签名的生成如下：

1. 签名者选一个随机数k，计算 [k]G，得到曲线上的一个点 (x_1, y_1) = [k]G
2. 然后计算：r = (e + x_1) mod n，其中e是消息的杂凑值。r把消息e和随机数（通过 x_1）绑在了一起
3. 接着计算：s = ((1 + d_A)^(-1) · (k - r · d_A)) mod n，这个式子用私钥 d_A 对r和k做了签名运算
4. 输出签名 (r, s)

所以签名者做的事情是：选一个随机数，在曲线上留一个标记点，把标记点的横坐标和消息混在一起得到r，再用私钥把r和随机数k绑定成s。最终签名 (r, s) 中，r用来验证消息是否正确，s用来验证私钥是否正确。

签名的验证如下：

验证者收到消息M和签名 (r, s) 后：

1. 计算同样的消息杂凑值e（使用相同的预处理方式）
2. 检查r和s是否在合法范围内，即 [0, n-1]
3. 计算 t = (r + s) mod n
4. 用签名者的公钥 P_A 重新计算一个曲线点：(x_1', y_1') = [s]G + [t]P_A，注意，这个公式是根据签名公式反推出来的，目的是让计算出来的点恰好等于签名者当时算的那个随机点 [k]G
5. 取这个点的横坐标 x_1'，计算：r' = (e + x_1') mod n
6. 判断 r' 是否等于签名里的r，如果 r' = r，说明验证者重新算出来的点，和签名者当时算的 [k]G 是同一个点，签名有效。

下面回答一下验证为什么能成立？

验证者要做的是，用公钥还原出签名者在曲线上生成的点，验证公式是 (x_1', y_1') = [s]G + [t]P_A，代入 t = (r + s) mod n 和 P_A = d_A G，展开后如下：

[s]G + [t]P_A = [s]G + (r + s)·d_A G = [s + (r + s)·d_A]G

为了让它等于 [k]G（签名者生成的曲线上的点 (x_1, y_1)），需要：

s + (r + s)·d_A ≡ k (mod n)

展开整理：

s·(1 + d_A) + r·d_A ≡ k (mod n)
s·(1 + d_A) ≡ k − r·d_A (mod n)

两边同时乘以 (1 + d_A)^(-1)（即逆元）：

s ≡ (k − r·d_A)·(1 + d_A)^(-1) (mod n)

这就得到了签名公式：

s = ((1 + d_A)^(-1) · (k - r · d_A)) mod n

也就是说，验证者用公钥和签名算出来的点，恰好等于签名者当时用随机数k算出来的那个点 (x_1, y_1)。因此，取横坐标后算出的 r' 一定等于原来的r。

所以验证本质上是验证者用公钥反推出签名者当时的随机点，看横坐标能不能对上。能对上，说明签名确实是用对应的私钥生成的；对不上，则签名无效。

和RSA签名的对比

RSA签名有一个特点：签名本身是可以从消息算出来的，因为签名本质上就是 s = M^d mod n，验证时用公钥还原出M，和原始消息比对。RSA签名中，签名值直接携带了消息的信息，验证方用公钥解签后得到的就是消息本身（或消息杂凑值）。

ECDSA则不同，签名值 (r, s) 和消息之间没有直接的代数关系，它是通过杂凑值和私钥共同构造出来的。验证方只能验证这个签名是否是针对这条消息生成的，而无法从签名中还原出任何东西。签名值本身不携带消息内容，它只是消息的凭证。

这个区别在实际使用中有一个直接影响：RSA签名可能会被伪造，如果签名者使用相同的私钥对两条不同消息进行签名，并且消息之间满足某种线性关系，攻击者可以构造出第三条有效签名。而ECDSA因为有随机数k的保护，相同消息每次签名结果都不同，抗伪造性更强。

1.2.7. 椭圆曲线密钥交换协议（ECDH）

这个协议本质上是经典DH密钥交换协议在椭圆曲线上的实现，继承了双方协商生成共享密钥的安全模型，前面的RSA没有介绍，是因为RSA那样加密传输密钥来实现密钥交换，也就是说，RSA是其中一方生成密钥，然后使用RSA传递给对方，而DH还有本节的ECDH是双方各自生成临时密钥对，然后交换公钥，各自独立计算出同一个共享秘密。具体过程如下：

公开参数：双方事先约定好椭圆曲线参数和基点G。

1. 生成临时密钥对：
   Alice选一个随机整数a（私钥），计算 A = aG（公钥）
   Bob选一个随机整数b（私钥），计算 B = bG（公钥）

2. 交换公钥：
   Alice把A发给Bob，Bob把B发给Alice。

3. 计算共享秘密：
   Alice计算 S = aB = a(bG) = abG
   Bob计算 S = bA = b(aG) = abG

由于椭圆曲线上标量乘法满足交换律和结合律，双方算出的结果是同一个点 abG，取它的x坐标（或再做一次哈希）就得到共享密钥。

RSA是加密传输，一方生成密钥后直接用对方公钥加密送过去；ECDH则是协商生成，双方各自出一半的力，共同算出一个共享秘密。这两种模式带来的安全属性也完全不同，主要是RSA密钥交换不具备前向安全性，一旦私钥泄露，所有历史会话都能被解密；而ECDH每次会话都重新生成临时密钥对，会话结束后立即销毁，即使长期私钥泄露也不会影响历史会话的安全。

此外在计算效率上，RSA需要服务器做私钥解密运算，随着密钥长度增加负担越来越重；而ECDH双方的运算量相当，且椭圆曲线运算本身更轻量。

不过RSA也有一个优势：它的公钥本身就承载了身份信息，不需要额外的认证机制；而ECDH的公钥是临时生成的，本身不携带任何身份信息，必须配合证书或签名来防止中间人攻击。

正是基于前向安全性和效率的综合考量，TLS 1.3彻底移除了RSA密钥交换，强制使用ECDHE作为密钥交换的唯一方式。

1.3. SM2算法简介

SM2是国家密码管理局于2010年12月发布、2016年成为中国国家密码标准的椭圆曲线公钥密码算法，标准号为GB/T 32918。SM2是在ECC（椭圆曲线密码）的基础上，结合中国商用密码应用需求设计的标准化算法族。

SM2使用素数域256位椭圆曲线，椭圆曲线方程：y^2 ≡ x^3 + ax + b (mod p)

曲线参数如下：

p = FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFF
a = FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFC
b = 28E9FA9E 9D9F5E34 4D5A9E4B CF6509A7 F39789F5 15AB8F92 DDBCBD41 4D940E93
n = FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF 7203DF6B 21C6052B 53BBF409 39D54123
Gx = 32C4AE2C 1F198119 5F990446 6A39C994 8FE30BBF F2660BE1 715A4589 334C74C7
Gy = BC3736A2 F4F6779C 59BDCEE3 6B692153 D0A9877C C62A4740 02DF32E5 2139F0A0

参数对应的含义如下：

参数	含义	对应前面讲过的概念
p	有限域的模数（一个大质数）	有限域F_p中的p，所有坐标都在0到p−1之间
a, b	椭圆曲线方程的系数	y^2 ≡ x^3 + ax + b，定义了曲线的形状
n	基点G的阶	满足 nG = O 的最小正整数，即点G自加n次回到无穷远点
Gx, Gy	基点G的坐标	公开的基准点，所有人用它做标量乘法

SM2算法的工程落地包括三种类型算法，分别是数字签名算法、密钥交换协议和公钥加密算法，下面逐一对这三种类型进行介绍。

1.3.1. SM2加解密

SM2的公钥加密算法在流程上与前面介绍的ECC加密高度相似，但有一个关键差异：SM2的密文不仅包含两个曲线点，还额外附加了一个杂凑值用于完整性校验。

加密流程如下：

假设发送方A要向接收方B发送明文消息M，接收方B已经公开了自己的公钥 P_B。

1. 产生随机数： A选取一个随机数 k ∈ [1, n-1]。
2. 计算C1： C_1 = [k]G = (x_1, y_1)，即基点G自加k次。
3. 计算共享秘密： [k]P_B = (x_2, y_2)，即用临时随机数k乘以接收方B的公钥，这一步在ECC加密中对应的是 rK。
4. 密钥派生： t = KDF(x_2 ∥ y_2, klen)，其中klen是明文的比特长度。KDF是密钥派生函数，基于SM3杂凑算法实现，用于从共享秘密中派生出加密密钥。如果t是全0串，则回到第1步重新生成随机数。
5. 加密明文： C_2 = M ⊕ t，用派生出的密钥对明文进行异或加密，注意到，这一步的本质是用对称密钥对明文做异或加密，类似于流密码的工作方式，这是SM2算法的一个设计特点，不像通用ECC加密那样需要先把明文编码成椭圆曲线上的点，自然也就不存在编码失败、反复尝试的问题，工程实现上更简洁、更高效。
6. 计算杂凑值： C_3 = Hash(x_2 ∥ M ∥ y_2)，对共享秘密的坐标和明文一起做SM3杂凑，用于解密时验证数据完整性。
7. 输出密文： C = C_1 ∥ C_3 ∥ C_2，密文是三部分拼接。

解密时，接收方用私钥 d_B 对 C_1 做标量乘法：[d_B]C_1 = [d_B]([k]G) = [k]P_B = (x_2, y_2)，得到共享秘密后重新派生密钥 t = KDF(x_2 ∥ y_2, klen)，得到派生密钥后，再对 C_2 异或，解出明文，最后验证 C_3 是否匹配。

这里的关键点在于：SM2加密过程从椭圆曲线点出发，通过密钥派生函数得到对称密钥来加密实际消息，而非直接用曲线点加法传递明文。同时，密文中包含了杂凑值，能够防止密文被篡改。这也解释了为什么与标准ECC相比，SM2加密可以在简化编码过程的同时保证数据完整性。

1.3.2. SM2签名

SM2数字签名算法在标准ECDSA的基础上做了一些调整，核心区别在于引入了可辨别标识和杂凑预处理。

签名生成的流程：

1. 预处理： 计算 Z_A = SM3(ENTL_A ∥ ID_A ∥ a ∥ b ∥ x_G ∥ y_G ∥ x_A ∥ y_A)，其中 ENTL_A 是用户标识 ID_A 的长度，a, b, x_G, y_G 是曲线参数和基点坐标，x_A, y_A 是签名者公钥的坐标。然后将待签名消息M与 Z_A 拼接，计算杂凑值 e = SM3(Z_A ∥ M)。这一步是SM2与标准ECDSA的重要区别，ECDSA通常不要求将用户标识纳入杂凑计算。

2. 选取随机数 k ∈ [1, n-1]，计算椭圆曲线点 (x_1, y_1) = [k]G

3. 然后计算：r = (e + x_1) mod n，其中e是待签名消息的SM3杂凑值（经过预处理），这一步，通过e将消息杂凑值引入，使得整个签名与具体消息绑定在一起，消息不同，r就不同，这一步主要是处理消息，为后面和私钥关联做准备

4. 如果 r = 0 或 r + k = n，则重新选取随机数

5. 计算 s = ((1 + d_A)^(-1) · (k - r · d_A)) mod n，其中 d_A 是签名者的私钥，-1 是"模逆元"的记号，表示这个数和 (1 + d_A) 相乘后在模n下为1，这一步是用私钥在构造一个数学等式，在签名验证时候用上

6. 如果 s = 0，则重新选取随机数

7. 输出签名：(r, s)

签名验证流程如下：

接收方收到签名 (r, s) 后，需要验证其有效性。验证流程如下：

1. 检查r和s是否都在 [1, n-1] 范围内，若不在则直接判定无效，通过排除明显不合法的签名，防止防御攻击者塞垃圾数据
2. 计算同样的杂凑值e（使用与签名方相同的预处理方式），核对消息是否被改过
3. 计算 t = (r + s) mod n，若 t = 0 则判定无效，t是后面用到的一个变量，这里是提前做准备
4. 根据签名和公钥 P_A 重新计算曲线的点：(x_1', y_1') = [s]G + [t]P_A，公式成立的过程和ECDSA推导过程一致
5. 计算 r' = (e + x_1') mod n
6. 判断 r' 是否等于r。若相等，签名有效；否则无效。

总结一下验证的整体思路：

签名方在生成签名时，做过这样一件事：选了一个随机数k，算了一个点 [k]G，取了它的横坐标 x_1，然后和消息杂凑e一起算出了r。

验证方看不到k，也看不到 [k]G，但验证方要做的是用签名 (r, s) 和公钥 P_A，重新算出一个点，看看这个点的横坐标能不能对得上签名里的r。

1.3.3. SM2密钥交换

SM2的密钥交换协议，本质上是国密版的ECDH。它和标准ECDH的核心思路一样：双方各自生成一对临时密钥，交换公钥后各自计算，最终得到同一个共享秘密。但SM2在ECDH的基础上增加了双方身份的绑定和可选的密钥确认机制，以防止中间人攻击。

SM2密钥交换的简化流程：

假设用户A（发起方）和用户B（响应方）要协商一个共享密钥，双方已经拥有各自的长期私钥 (d_A, d_B) 和公钥 (P_A, P_B)。

1. A方：选随机数 r_A ∈ [1, n-1]，算点 R_A = [r_A]G，把 R_A 发给B。
2. B方：选随机数 r_B ∈ [1, n-1]，算点 R_B = [r_B]G，把 R_B 发给A。
3. A方计算：用B的公钥 P_B、收到的 R_B、自己的私钥 d_A 和随机数 r_A，算出一个点U，然后通过KDF（密钥派生函数，通常基于SM3）派生出共享密钥 K_A。
4. B方计算：用A的公钥 P_A、收到的 R_A、自己的私钥 d_B 和随机数 r_B，算出同一个点V，然后通过同样的KDF派生出共享密钥 K_B。

核心公式是：双方各自计算的点最终都会落在 (r_A r_B G) 这个点上。因为椭圆曲线的标量乘法满足交换律和结合律，两人算出的点是同一个点，双方算出来的共享秘密是同一个，所以 K_A = K_B。

此外，协议中还包括一个可选的密钥确认步骤（S_A 和 S_B 的交换与校验），用于让双方互相确认对方确实算出了正确的共享密钥。

1.4. 总结

本章从对称加密的密钥分发困境出发，沿着公钥密码学的发展脉络，依次介绍了RSA算法、椭圆曲线密码学（ECC）以及国密SM2算法。

RSA是公钥密码学的里程碑，它首次将大整数分解难题转化为可用的加密和签名方案，证明了正向容易、反向困难的单向函数可以构建安全的非对称加密。但RSA的短板也随着时间逐渐显现，密钥越来越长、运算越来越慢。ECC用更短的密钥实现了同等的安全强度，凭借轻量高效的优势，在移动互联网和物联网时代成为主流。SM2则是中国标准的ECC，固定了256位素数域参数，搭配SM3杂凑算法，形成了完整的签名、加密、密钥交换算法族，核心意义在于密码体系的自主可控。

RSA和ECC两种算法的底层逻辑一脉相承：依赖一个数学难题作为安全根基，通过陷门函数实现正向容易、反向困难，用公钥和私钥的角色分离完成加密、签名或密钥协商。区别在于选取的数学难题不同、密钥长度和运算效率不同、标准化和适用场景不同。

理解这些算法背后的数学原理和设计逻辑，比记住公式本身更为重要，它们不仅解决了当下的安全问题，也为面对新的技术挑战提供了思考框架。