本文部分内容翻译自 Practical-Cryptography-for-Developers-Book，笔者补充了密码学历史以及 openssl 命令示例，并重写了 RSA/ECC 算法原理、代码示例等内容。

这篇文章中会涉及到一些数论知识，本文不会详细介绍这些数学知识，可以在有疑惑的时候自行查找相关知识，或者选择跳过相关内容。

在介绍非对称密钥加密方案和算法之前，我们首先要了解公钥密码学的概念。

从第一次世界大战、第二次世界大战到 1976 年这段时期密码的发展阶段，被称为「近代密码阶段」。 在近代密码阶段，所有的密码系统都使用对称密码算法——使用相同的密钥进行加解密。 当时使用的密码算法在拥有海量计算资源的现代人看来都是非常简单的，我们经常看到各种讲述一二战的谍战片，基本都包含破译电报的片段。

第一二次世界大战期间，无线电被广泛应用于军事通讯，围绕无线电通讯的加密破解攻防战极大地影响了战局。

公元20世纪初，第一次世界大战进行到关键时刻，英国破译密码的专门机构「40号房间」利用缴获的德国密码本破译了著名的「齐默尔曼电报」，其内容显示德国打算联合墨西哥对抗可能会参战的美国，这促使美国放弃中立对德宣战，从而彻底改变了一战的走势。

1943 年，美国从破译的日本电报中得知山本五十六将于 4 月 18 日乘中型轰炸机，由 6 架战斗机护航，到中途岛视察。美国总统罗斯福亲自做出决定截击山本，山本乘坐的飞机在去往中途岛的路上被美军击毁，战争天才山本五十六机毁人亡，日本海军从此一蹶不振。

此外，在二次世界大战中，美军将印第安纳瓦霍土著语言作为密码使用，并特别征募使用印第安纳瓦霍通信兵。在二次世界大战日美的太平洋战场上，美国海军军部让北墨西哥和亚历桑那印第安纳瓦霍族人使用纳瓦霍语进行情报传递。纳瓦霍语的语法、音调及词汇都极为独特，不为世人所知道，当时纳瓦霍族以外的美国人中，能听懂这种语言的也就一二十人。这是密码学和语言学的成功结合，纳瓦霍语密码成为历史上从未被破译的密码。

在 1976 年 Malcolm J. Williamson 公开发表了现在被称为「Diffie–Hellman 密钥交换，DHKE」的算法，并提出了「公钥密码学」的概念，这是密码学领域一项划时代的发明，它宣告了「近代密码阶段」的终结，是「现代密码学」的起点。

言归正传，对称密码算法的问题有两点：

这会导致巨大的「密钥交换」跟「密钥保存与管理」的成本。「公钥密码学」最大的优势就是，它解决了这两个问题：

因此公钥密码学成为了现代密码学的基石，而「公钥密码学」的诞生时间 1976 年被认为是现代密码学的开端。

公钥密码系统的密钥始终以公钥 + 私钥对的形式出现，公钥密码系统提供数学框架和算法来生成公钥+私钥对。 公钥通常与所有人共享，而私钥则保密。 公钥密码系统在设计时就确保了在预期的算力下，几乎不可能从其公开的公钥逆向演算出对应的私钥。

公钥密码系统主要有三大用途：加密与解密、签名与验证、密钥交换。 每种算法都需要使用到公钥和私钥，比如由公钥加密的消息只能由私钥解密，由私钥签名的消息需要用公钥验证。

由于加密解密、签名验证均需要两个不同的密钥，故「公钥密码学」也被称为「非对称密码学」。

比较著名的公钥密码系统有：RSA、ECC（椭圆曲线密码学）、ElGamal、Diffie-Hellman、ECDH、ECDSA 和 EdDSA。许多密码算法都是以这些密码系统为基础实现的，例如 RSA 签名、RSA 加密/解密、ECDH 密钥交换以及 ECDSA 和 EdDSA 签名。

参考文档：https://en.wikipedia.org/wiki/Post-quantum_cryptography

目前流行的公钥密码系统基本都依赖于 IFP（整数分解问题）、DLP（离散对数问题）或者 ECDLP（椭圆曲线离散对数问题），这导致这些算法都是量子不安全（quantum-unsafe）的。

如果人类进入量子时代，IFP / DLP / ECDLP 的难度将大大降低，目前流行的 RSA、ECC、ElGamal、Diffie-Hellman、ECDH、ECDSA 和 EdDSA 等公钥密码算法都将被淘汰。

目前已经有一些量子安全的公钥密码系统问世，但是因为它们需要更长的密钥、更长的签名等原因，目前还未被广泛使用。

一些量子安全的公钥密码算法举例：NewHope、NTRU、GLYPH、BLISS、XMSS、Picnic 等，有兴趣的可以自行搜索相关文档。

非对称加密要比对称加密复杂，有如下几个原因：

此外，非对称密码比对称密码慢非常多。比如 RSA 加密比 AES 慢 1000 倍，跟 ChaCha20 就更没法比了。

为了解决上面提到的这些困难并支持加密任意长度的消息，现代密码学使用「非对称加密方案」来实现消息加解密。 又因为「对称加密方案」具有速度快、支持加密任意长度消息等特性，「非对称加密方案」通常直接直接组合使用对称加密算法与非对称加密算法。比如「密钥封装机制 KEM（key encapsulation mechanisms)）」与「集成加密方案 IES（Integrated Encryption Scheme）」

顾名思义，KEM 就是仅使用非对称加密算法加密另一个密钥，实际数据的加解密由该密钥完成。

密钥封装机制 KEM 的加密流程（使用公钥加密传输对称密钥）：

密钥封装机制 KEM 的解密流程（使用私钥解密出对称密钥，然后再使用这个对称密钥解密数据）：

RSA-OAEP, RSA-KEM, ECIES-KEM 和 PSEC-KEM. 都是 KEM 加密方案。

主要区别在于使用的是对称加密算法、还是非对称加密算法：

集成加密方案 (IES) 在密钥封装机制（KEM）的基础上，添加了密钥派生算法 KDF、消息认证算法 MAC 等其他密码学算法以达成更高的安全性。

在 IES 方案中，非对称算法（如 RSA 或 ECC）跟 KEM 一样，都是用于加密或封装对称密钥，然后通过对称密钥（如 AES 或 Chacha20）来加密输入消息。

DLIES（离散对数集成加密方案）和 ECIES（椭圆曲线集成加密方案）都是 IES 方案。

RSA 密码系统是最早的公钥密码系统之一，它基于 RSA 问题和整数分解问题 （IFP）的计算难度。 RSA 算法以其作者（Rivest–Shamir–Adleman）的首字母命名。

RSA 算法在计算机密码学的早期被广泛使用，至今仍然是数字世界应用最广泛的密码算法。 但是随着 ECC 密码学的发展，ECC 正在非对称密码系统中慢慢占据主导地位，因为它比 RSA 具有更高的安全性和更短的密钥长度。

RSA 算法提供如下几种功能：

RSA 可以使用不同长度的密钥：1024、2048、3072、4096、8129、16384 甚至更多位。目前 3072 位及以上的密钥长度被认为是安全的，曾经大量使用的 2048 位 RSA 现在被破解的风险在不断提升，已经不推荐使用了。

更长的密钥提供更高的安全性，但会消耗更多的计算时间，同时签名也会变得更长，因此需要在安全性和速度之间进行权衡。 非常长的 RSA 密钥（例如 50000 位或 65536 位）对于实际使用可能太慢，例如密钥生成可能需要几分钟到几个小时。

RSA 密钥对的生成跟我们在本系列文章的第 5 篇介绍的「DHKE 密钥交换算法」会有些类似，但是要更复杂一点。

首先看下我们怎么使用 openssl 生成一个 1024 位的 RSA 密钥对（仅用做演示，实际应用中建议 3072 位）：

OpenSSL 是目前使用最广泛的网络加密算法库，支持非常多流行的现代密码学算法，几乎所有操作系统都会内置 openssl.

RSA 描述的私钥的结构如下（其中除 $n, d$ 之外的都是冗余信息）：

再看下 RSA 公钥的结构：

可以看到私钥文件中就已经包含了公钥的所有参数，实际上我们也是使用 openssl rsa -in rsa-private-key.pem -pubout -out rsa-public-key.pem 命令通过私钥生成出的对应的公钥文件。

下面就介绍下具体的密钥对生成流程，搞清楚 openssl 生成出的这个私钥，各项参数分别是什么含义：

这里不会详细介绍其中的各种数学证明，具体的请参考维基百科。 相关数学知识包括取模运算的性质、欧拉函数、模倒数（拓展欧几里得算法）

下面我们使用 Python 来通过 $p,q,e$ 计算出 $n, d$ 来，跟 openssl 打印的对比下，看看是否一致。

对比 RSA 的输出，可以发现去掉冒号后，d 跟 n 的值是完全相同的。

RSA 加密算法，一次只能加密一个小于 $n$ 的非负整数，假设明文为整数 $msg$，加密算法如下：

$$ \text{encryptedMsg} = msg^e \mod n $$

通常的手段是，先使用 EAOP 将被加密消息编码成一个个符合条件的整数，再使用上述公式一个个加密。

解密的方法，就是对被每一段加密的数据 $encryptedMsg$，进行如下运算：

$$ \text{decryptedMsg} = \text{encryptedMsg}^d \mod n $$

这里的证明需要用到一些数论知识，觉得不容易理解的话，建议自行查找相关资料。

证明流程如下：

$$ \begin{alignedat}{2} \text{decryptedMsg} &= &\text{encryptedMsg}^d &\mod n \\ &= &{(msg^e \mod n)}^d &\mod n \\ &= &{msg^{ed}} &\mod n \\ &= &{msg^{ed}} &\mod {pq} \end{alignedat} $$

接下来将下面两个等式代入上述计算中：

这样就得到：

$$ \begin{alignedat}{2} \text{decryptedMsg} &= &{msg^{ed}} &\mod {pq} \\ &= &{(msg \mod pq) \cdot (msg^{ed-1} \mod pq)} &\mod {pq} \\ &= &{msg \cdot (msg^{(p-1)(q-1) \cdot k} \mod pq)} &\mod {pq} \end{alignedat} $$

又有费马小定理指出，在 $a$ 为整数，$p$ 为质数的情况下，有同余等式

$$a^{p-1} \equiv 1 {\pmod p}$$

因为我们的模数 $n=pq$ 并不是质数，不能直接利用费马小定理给出的同余公式。 但是 $p$, $q$ 两数都为质数，我们可以分别计算方程 对 $p$ 以及 $q$ 取模的结果，然后再根据中国剩余定理得出通解，也就得到我们需要的结果。

对于模 $p$ 的情况，计算方法如下：

同理，对模 $q$ 的情况，也能得到等式

$$msg^{ed} \equiv msg \pmod q$$

有了上面两个结果，根据中国剩余定理，就能得到

$$msg^{ed} \equiv msg \pmod {pq}$$

现在再接续前面的计算：

$$ \begin{alignedat}{2} \text{decryptedMsg} &= &{msg^{ed}} &\pmod {pq} \\ &= &msg &\pmod {pq} \\ &= &msg \end{alignedat} $$

这样就证明了，解密操作得到的就是原始信息。

因为非对称加解密非常慢，对于较大的文件，通常会分成两步加密来提升性能：首先用使用对称加密算法来加密数据，再使用 RSA 等非对称加密算法加密上一步用到的「对称密钥」。

下面我们用 Python 来验证下 RSA 算法的加解密流程：

前面证明了可以使用公钥加密，再使用私钥解密。

实际上从上面的证明也可以看出来，顺序是完全可逆的，先使用私钥加密，再使用公钥解密也完全是可行的。这种运算被我们用在数字签名算法中。

数字签名的方法为：

Python 演示：

ECC 椭圆曲线密码学，于 1985 年被首次提出，并于 2004 年开始被广泛应用。 ECC 被认为是 RSA 的继任者，新一代的非对称加密算法。

其最大的特点在于相同密码强度下，ECC 的密钥和签名的大小都要显著低于 RSA. 256bits 的 ECC 密钥，安全性与 3072bits 的 RSA 密钥安全性相当。

其次 ECC 的密钥对生成、密钥交换与签名算法的速度都要比 RSA 快。

在数学中，椭圆曲线（Elliptic Curves）是一种平面曲线，由如下方程定义的点的集合组成（$A-J$ 均为常数）：

$$ Ax^3 + Bx^2y + Cxy^2 + Dy^3 + Ex^2 + Fxy + Gy^2 + Hx + Iy + J = 0 $$

而 ECC 只使用了其中很简单的一个子集（$a, b$ 均为常数）：

$$ y^2 = x^3 + ax + b $$

比如著名的 NIST 曲线 secp256k1 就是基于如下椭圆曲线方程：

$$ y^2 = x^3 + 7 $$

椭圆曲线大概长这么个形状：

椭圆曲线跟椭圆的关系，就犹如雷锋跟雷峰塔、Java 跟 JavaScript…

你可以通过如下网站手动调整 $a$ 与 $b$ 的值，拖动曲线的交点查看图形的变化情况： https://www.desmos.com/calculator/ialhd71we3?lang=zh-CN

数学家在椭圆曲线上定义了一些运算规则，ECC 就依赖于这些规则，下面简单介绍下我们用得到的部分。

椭圆曲线上的运算跟我们所熟知的实数域运算不太一样，它在现实生活中并无实际意义，但是它的一些性质使其很适合被应用在密码学中。

对于曲线上的任意两点 $A$ 与 $B$，我们定义过 $A, B$ 的直线与曲线的交点为 $-(A+B)$，而 $-(A+B)$ 相对于 x 轴的对称点即为 $A+B$:

上述描述一是定义了椭圆曲线的加法规则，二是定义了椭圆曲线上的负元运算。

在加法规则中，如果 $A=B$，我们定义曲线在 $A$ 点的切线与曲线的交点为 $-2A$，于是得到二倍运算的规则：

对于 $(-A) + A$ 这种一个值与其负元本身相加的情况，我们会发现过这两点的直线与椭圆曲线没有第三个交点，前面定义的加法规则在这种情况下失效了。 为了解决这个问题，我们假设这条直线与椭圆曲线相交于无穷远点 $O_{\infty}$.

我们在前面已经定义了椭圆曲线上的加法运算、二倍运算以及无穷远点，有了这三个概念，我们就能定义k 倍运算 了。

K 倍运算最简单的计算方法，就是不断地进行加法运算，但是也有许多更高效的算法。 其中最简单的算法是「double-and-add」，它要求首先 $k$ 拆分成如下形式

$$ k = k_{0}+2k_{1}+2^{2}k_{2}+\cdots +2^{m}k_{m} \\ \text{其中} k_{0}~..~k_{m}\in {0,1},m=\lfloor \log _{2}{k}\rfloor $$

然后再迭代计算其中各项的值，它的运算复杂度为 $log_{2}(k)$.

因 Double 和 Add 的执行时间不同，根据执行时间就可以知道是执行 Double 还是 Add，间接可以推算出 $k$. 因此这个算法会有计时攻击的风险。 基于「double-and-add」修改的蒙哥马利阶梯（Montgomery Ladder）是可以避免计时分析的作法，这里就不详细介绍了。

椭圆曲线是连续且无限的，而计算机却更擅长处理离散的、存在上限的整数，因此 ECC 使用「有限域上的椭圆曲线」进行计算。

「有限域（也被称作 Galois Filed, 缩写为 GF）」顾名思义，就是指只有有限个数值的域。

有限域上的椭圆曲线方程，通过取模的方式将曲线上的所有值都映射到同一个有限域内。 有限域 $\mathbb {F} _{p}$ 上的 EC 椭圆曲线方程为：

$$ y^2 = x^3 + ax + b (\mod p), 0 \le x \le p $$

目前主要有两种有限域在 ECC 中被广泛应用：

通过限制 x 为整数，并使用取模进行了映射后，椭圆曲线的形状已经面目全非了，它的加减法也不再具有几何意义。 但是它的一些特性仍然跟椭圆曲线很类似，各种公式基本加个 $\mod p$ 就变成了它的有限域版本：

前面已经介绍了椭圆曲线上的 k 倍运算 及相关的高效算法，但是我们还没有涉及到除法。

椭圆曲线上的除法是一个尚未被解决的难题——「ECDLP 椭圆曲线离散对数问题」：

已知 $kG$ 与基点 $G$，求整数 $k$ 的值。

目前并没有有效的手段可以快速计算出 $k$ 的值。 比较直观的方法应该是从基点 $G$ 开始不断进行加法运算，直到结果与 $kG$ 相等。

目前已知的 ECDLP 最快的解法所需步骤为 $\sqrt{k}$，而 k 倍运算高效算法前面已经介绍过了，所需步骤为 $log_2(k)$。 在 $k$ 非常大的情况下，它们的计算用时将会有指数级的差距。

椭圆曲线上的 k 倍运算与素数上的幂运算很类似，因此 ECC 底层的数学难题 ECDLP 与 RSA 的离散对数问题 DLP 也有很大相似性。

首先，跟 RSA 一样，让我们先看下怎么使用 openssl 生成一个使用 prime256v1 曲线的 ECC 密钥对：

可以看到 ECC 算法的公钥私钥都比 RSA 小了非常多，数据量小，却能带来同等的安全强度，这是 ECC 相比 RSA 最大的优势。

私钥的参数：

使用安全随机数生成器即可直接生成出 ECC 的私钥 priv，因此 ECC 的密钥对生成速度非常快。

这个在前面写给开发人员的实用密码学（五）—— 密钥交换 DHKE 与完美前向保密 PFS已经介绍过了，不过这里再复述一遍：

这样两方就通过 ECDH 完成了密钥交换。 而 ECDH 的安全性，则由 ECDLP 问题提供保证。

ECC 本身并没有提供加密与解密的功能，但是我们可以借助 ECDH 迂回实现加解密。流程如下：

实际上就是消息的发送方先生成一个临时的 ECC 密钥对，然后借助 ECDH 协议计算出共享密钥用于加密。 消息的接收方同样通过 ECDH 协议计算出共享密钥再解密数据。

使用 Python 演示如下：

举例如下：

生成点 G 的选择是很有讲究的，虽然每个循环子群都包含有很多个生成点，但是 ECC 只会谨慎的选择其中一个。 首先 G 点必须要能生成出整个循环子群，其次还需要有尽可能高的计算性能。

数学上已知某些椭圆曲线上，不同的生成点生成出的循环子群，阶也是不同的。如果 G 点选得不好，可能会导致生成出的子群的阶较小。 前面我们已经提过子群的阶 $r$ 会限制总的私钥数量，导致算法强度变弱！因此不恰当的 $G$ 点可能会导致我们遭受「小子群攻击」。 为了避免这种风险，建议尽量使用被广泛使用的加密库，而不是自己撸一个。

ECC椭圆曲线由一组椭圆曲线域参数描述，如曲线方程参数、场参数和生成点坐标。这些参数在各种密码学标准中指定，你可以网上搜到相应的 RFC 或 NIST 文档。

这些标准定义了一组命名曲线的参数，例如 secp256k1、P-521、brainpoolP512t1 和 SM2. 这些加密标准中描述的有限域上的椭圆曲线得到了密码学家的充分研究和分析，并被认为具有一定的安全强度。

也有一些密码学家（如 Daniel Bernstein）认为，官方密码标准中描述的大多数曲线都是「不安全的」，并定义了他们自己的密码标准，这些标准在更广泛的层面上考虑了 ECC 安全性。

开发人员应该仅使用各项标准文档给出的、经过密码学家充分研究的命名曲线。

此曲线被应用在比特币中，它的域参数如下：

椭圆曲线方程除了我们前面使用的 Weierstrass 形式 $$y^2 = (x^3 + ax + b) \mod p$$ 外，还可以被写成其他多种形式，这些不同的形式是双有理等价的（别问，我也不懂什么叫「双有理等价」…）。 不同的方程形式在计算机的数值计算上可能会存在区别。

为了性能考虑，ECC 在部分场景下会考虑使用 Edwards 曲线形式进行计算，该方程形式如下：

$$ x^{2}+y^{2}=1+dx^{2}y^{2} $$

画个图长这样：

知名的 Edwards 曲线有：

https://cryptography.io/en/latest/hazmat/primitives/asymmetric/ed25519/

只要域参数选得好，Edwards 就可以以非常高的性能实现 ECC 密钥交换、数字签名、混合加密方案。

一个例子就是 Curve25519，它是 Edwards 曲线，其 Montgomery 形式的定义如下：

$$ y^{2}=x^{3}+486662x^{2}+x $$

其被定义在有限域 $\mathbb {F} _{p}$ 上，$p = 2255 - 19$, 其他域参数如下：

虽然此曲线并未以 Edwards 形式定义，但是它已被证明与如下扭曲 Edwards 曲线（edwards25519）双有理等价：

$$ -x^2 + y^2 = 1 + 37095705934669439343138083508754565189542113879843219016388785533085940283555 x^2 y^2 $$

上面给出的这种 Edwards 形式与前文给出的 Weierstrass 形式完全等价，是专为计算速度优化而设计成这样的。

Curve25519 由 Daniel Bernstein 领导的密码学家团队精心设计，在多个设计和实现层面上达成了非常高的性能，同时不影响安全性。

Curve25519 的构造使其避免了许多潜在的实现缺陷。根据设计，它不受定时攻击的影响，并且它接受任何 32 字节的字符串作为有效的公钥，并且不需要验证。 它能提供 125.8bits 的安全强度（有时称为 ~ 128bits 安全性）

Curve25519 的私钥为 251 位，通常编码为 256 位整数（32 个字节，64 个十六进制数字）。 公钥通常也编码为 256 位整数（255 位 y 坐标 + 1 位 x 坐标），这对开发人员来说非常方便。

基于 Curve25519 派生出了名为 X25519 的 ECDH 算法，以及基于 EdDSA 的高速数字签名算法 Ed25519.

https://cryptography.io/en/latest/hazmat/primitives/asymmetric/ed448/

Curve448（Curve448-Goldilocks）是一种非扭曲 Edwards 曲线，它的方程定义如下：

$$ x^2 + y^2 = 1 - 39081 x^2 y^2 $$

其被定义在有限域 $\mathbb {F} _{p}$ 上，$p = 2448 - 2224 - 1$，其他域参数：

与 Curve25519 一样，Curve448 也等价于前面给出的 Weierstrass 形式，选择 Edwards 形式主要是因为它能显著提升性能。

Curve448 提供 222.8 位的安全强度。 Curve448 的私钥为 446 位，通常编码为 448 位整数（56 个字节，112 个十六进制数字）。 公钥也被编码为 448 位整数。

基于 Curve448 派生出了名为 X448 的 ECDH 算法，以及基于 EdDSA 的高速数字签名算法 Ed448.

首先，Bernstein 的 SafeCurves 标准列出了符合一组 ECC 安全要求的安全曲线，可访问 https://safecurves.cr.yp.to 了解此标准。

此外对于我们前面介绍的 Curve448 与 Curve25519，可以从性能跟安全性方面考量：

如果你的应用场景中暂时还很难用上 Curve448/Curve25519，你可以考虑一些应用更广泛的其他曲线，但是一定要遵守如下安全规范：

目前（2022 年）在 TLS 协议以及 JWT 签名算法中，应用最广泛的椭圆曲线仍然是 NIST 系列：

但是我们也看到 Curve25519 正在越来越流行，因为美国政府有前科（[NSA 在 RSA 加密算法中安置后门是怎么一回事，有何影响？——知乎](https://www.zhihu.com/question/22343037），NIST 标准被怀疑可能有后门，目前很多人都在推动使用 Curve25519 等社区方案取代掉 NIST 标准曲线。

对于 openssl，如下命令会列出 openssl 支持的所有曲线：

在文章开头我们已经介绍了集成加密方案 (IES)，它在密钥封装机制（KEM）的基础上，添加了密钥派生算法 KDF、消息认证算法 MAC 等其他密码学算法以达成我们对消息的安全性、真实性、完全性的需求。

而 ECIES 也完全类似，是在 ECC + 对称加密算法的基础上，添加了许多其他的密码学算法实现的。

ECIES 是一个加密框架，而不是某种固定的算法。它可以通过插拔不同的算法，形成不同的实现。 比如「secp256k1 + Scrypt + AES-GCM + HMAC-SHA512」。

大概就介绍到这里吧，后续就请在需要用到时自行探索相关的细节咯。

如果你觉得这篇文章对你有所帮助，欢迎评论、分享、打赏~