近年来，椭圆曲线密码学方法因其高效性和强安全性而变得流行。本文旨在以比当前互联网上已有的资料更清晰的方式介绍这一主题。
在本文中，我将介绍什么是椭圆曲线、可以在其上执行的基本运算，以及它们如何在密码学背景下使用。本文的大部分内容是关于已知攻击的示例，针对不正确的实现或错误的使用方式。在整篇文章中，我尝试将解释分为直观的高层部分和更详细的数学部分。读者可以关注其中感兴趣的部分，并跳过不太感兴趣的部分。
祝阅读愉快！
一般来说，椭圆曲线是某种曲线。例如抛物线，其方程为 $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$，看起来像这样：
在密码学背景下，通常使用方程形式为如下的椭圆曲线：
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$
例如，对应于方程 $𝑦^2 = 𝑥^3 − 3𝑥 + 3$ 的椭圆曲线看起来像这样：
曲线方程定义了曲线上点的 𝑥 坐标与其 𝑦 坐标之间的关系。在密码学背景下，我们将 𝑥、𝑦、𝑎、𝑏 限制为整数，并将计算限制为对某个大素数取模。因此椭圆曲线方程为：
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$.
这意味着曲线上的点数是有限的。用数学语言来说，该曲线被定义在阶为 𝑝 的有限域上。因此，现在并非每个 𝑥 坐标都必然在曲线上有对应的点，因为与之对应的 𝑦 坐标可能不是整数。
曲线上的点集由满足曲线方程的整数对 (𝑥, 𝑦) 组成。除了这些点之外，还定义了一个称为“无穷远点”的特殊点，用 𝒪 表示。用数学语言来说，该点是曲线点集关于加法运算的单位元，我们将在下一节定义该运算。曲线上的点数（包括点 𝒪）称为“曲线的阶”。
另一个观察结果是，椭圆曲线关于 X 轴对称。这意味着如果点 𝑃 = (𝑥, 𝑦) 在曲线上，那么点 −𝑃 = (𝑥, −𝑦) 也在曲线上。事实上，这两个点被视为彼此的“逆元”（因此第二个点标记为 −𝑃），它们之间加法运算的结果被定义为单位元 𝒪。
一个称为 Hasse 定理的定理提供了 #𝐸（曲线的阶）的估计，其数量级为 Θ(𝑝)。更准确地说：
$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$
给定曲线上的两个点，可以定义它们之间的加法运算，结果是也位于曲线上的第三个点。为了在几何上找到这个点，我们在两个给定点之间画一条线，并将其延伸直到它与曲线相交于第三个点。将这个点关于 𝑋 轴反射，得到的点就是加法的结果。
下图展示了在给定点 𝑃 和 𝑄 的情况下，如何找到点 𝑃 + 𝑄：
从这个描述中可能产生的一个问题是：如果连接两个点的直线不再与曲线相交会怎样？在这种情况下，称该直线与曲线相交于“无穷远点”，加法的结果是点 𝒪。注意，当所画直线是竖直的时会发生这种情况，也就是说，我们试图将点 𝑃 与其逆点 −𝑃 相加：
由此可推导出两个基本恒等式。对于每个点 𝑃，都有：
𝑃 + 𝒪 = 𝑃
𝑃 + (−𝑃) = 𝒪
从几何描述中产生的另一个问题是如何将点与自身相加？我们看到，为了将两个不同的点 𝑃 和 𝑄 相加，我们在它们之间画一条直线，并观察其延长线与曲线的交点。直观地，我们保持 𝑃 不变，观察当 𝑄 越来越“靠近” 𝑃 时所产生的直线，直到 𝑄 与 𝑃 合并。我们将得到的是一条在点 𝑃 处越来越“切”于曲线的直线，而这正是我们想要将 𝑃 与自身相加时需要观察的直线：
要将点 𝑃 与自身相加，我们在点 𝑃 处画曲线的切线，并将其延伸直到它与曲线相交于第二个点。将这个点关于 𝑋 轴反射，得到的点就是加法的结果。通常将加法的结果记为 𝑃 + 𝑃 = 2𝑃。同样，如果切线没有与曲线相交于第二个点，则称其与曲线相交于“无穷远点”，这种情况下加法的结果是点 𝒪。
这些直观的几何描述很好地说明了点的加法是如何工作的，并帮助我们理解。但如何实际计算呢？当然是数学公式！
给定点 $𝑃 = (𝑥_𝑃, 𝑦_𝑃)$ 和 $𝑄 = (𝑥_𝑄, 𝑦_𝑄)$，它们相加的结果是点 $𝑅 = (𝑥_𝑅, 𝑦_𝑅)$，满足：
$𝑥_𝑅 = 𝜆^2 − 𝑥_𝑃 − 𝑥_𝑄\ \ \ \ \ \ \ \ \ (mod\ 𝑝)$
$𝑦_𝑅 = 𝜆(𝑥_𝑃 − 𝑥_𝑅) − 𝑦_𝑃\ \ \ \ (mod\ 𝑝)$
其中，𝜆 定义为连接两点的直线的斜率（如果两点不同），或曲线在该点处的切线的斜率（如果点与自身相加）。形式上：
$\displaystyle𝜆 = \frac{𝑦_𝑃 − 𝑦_𝑄}{𝑥_𝑃 − 𝑥_𝑄}\ \ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 ≠ 𝑄$
$\displaystyle𝜆 = \frac{3{𝑥_𝑃}^2 + 𝑎}{2𝑦_𝑃}\ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 = 𝑄$
点加法背后的数学计算对本文其余部分并不关键。就此而言，我们可以将点加法视为一个黑盒：它接收曲线上的两个点，并返回同样在曲线上的第三个点。
我们已经看到可以将点 𝑃 与自身相加，并将结果点记为 2𝑃。如果我们再次将点 𝑃 加到该结果上，就会到达一个记为 3𝑃 的点，依此类推。通过重复将点与自身相加，可以定义点与常数的“乘法”（类似于数字之间的乘法）：
$𝑛𝑃 = 𝑃 + 𝑃 + ⋯ + 𝑃\ \ \ \ \ (n\ times)$
表面看来，要将一个点乘以一个数 𝑛，我们需要执行 𝑛 次点之间的加法运算。这是因为，给定一个起点，如果不“一步一步”地到达终点，很难预先知道“最后”的点会落在哪里。这样的计算会非常低效，因为 𝑛 可能非常大。
为此，存在 Double And Add（倍点与加法）算法，我们从点 𝑃 开始，对于 𝑛 的二进制表示中的每一位，将当前点乘以 2（即与自身相加），如果该位为 1，则将其加到结果中。该算法的时间复杂度为 𝑂(log 𝑛)，可以高效地将点乘以非常大的数。
我们稍后将使用点乘法的一个重要性质：对于每个点 𝑃 以及一对数 𝑎、𝑏，都有：
$𝑏(𝑎𝑃) = (𝑏𝑎)𝑃 = (𝑎𝑏)𝑃 = 𝑎(𝑏𝑃)$
直观地说，假设我们从点 𝑃 出发，从其走 𝑎 步，到达点 𝑎𝑃。从这个点出发，我们走 𝑏 步，每步“大小”为 𝑎，到达点 𝑏(𝑎𝑃)。或者，在另一种情况下，我们可以从点 𝑃 出发，走 𝑏 步到达点 𝑏𝑃。从这个点出发，走 𝑎 步，每步“大小”为 𝑏，到达点 𝑎(𝑏𝑃)。
在两种情况下，我们总共从点 𝑃 走了相同的 𝑎𝑏 步，因此在两种情况下我们到达了相同的最终点。在数学上，点乘以常数满足结合律。
如果我们从一个点 𝑃 出发，一次又一次地将其与自身相加，每一步都会到达曲线上的某个新点。由于曲线上的点数是有限的，在某个阶段我们会再次到达之前已经到达过的点，从而进入某种循环或“圆圈”。更准确地说，在某个阶段我们会到达点 -𝑃，下一步到达点 𝒪，再下一步会再次到达我们出发时的点 𝑃。
产生这种“圆圈”的点称为生成元，因为可以从它生成整个“圆圈”，并且通常用字母 𝐺 表示。这个“圆圈”中的点数（包括点 𝒪）称为“生成元 𝐺 的阶”，通常用 𝑛 表示。曲线上的每个点都会形成某种“圆圈”。在数学上，这个“圆圈”上的点集构成一个循环群。
由此产生的一个有趣性质是，将点 𝐺 乘以其阶 𝑛 会得到无穷远点：
𝑛𝐺 = 𝒪
“给定点 𝑃 和 𝑄，且对于某个 𝑥 有 𝑄 = 𝑥𝑃，则很难找到 𝑥。”
用语言描述就是：假设有人从某个起点出发，走了若干步，到达终点。给定起点和终点，我们如何知道他们走了多少步？
这个问题的答案并不那么直观，因为很难预先从起点预测通过逐步走会到达哪些点。一个朴素的解决方案是让我们自己从 𝑃 出发，一步一步向前推进并计算所走的步数，直到到达 𝑄。该解法的复杂度为 𝑂(𝑥)，如果已知 𝑥 是一个很大的数，例如 𝑥 为 256 bit，那是不可行的。
这个问题称为椭圆曲线离散对数问题（ECDLP），它是一个困难问题。但它有多难呢？
在密码学背景下，通常使用称为安全级别的度量来衡量“问题的难度”或“密码系统的强度”。在该度量中，如果已知的最佳攻击以 $𝑂(2^𝑛)$ 步解决问题，则称问题具有“𝑛 位安全性”。
目前，解决 ECDLP 问题的最佳算法以 $𝑂(\sqrt n)$ 的复杂度完成，其中 𝑛 是点 𝑃 的阶，该算法使用中途相遇攻击。当选择具有足够大的阶的点时，解决它是不可行的，这正是该问题的强度所在。
例如，如果我们选择大小为 256 bit 的 𝑛，那么 ECDLP 问题具有 128 bit 的安全级别。作为比较，要在基于整数分解问题的 RSA 加密中达到同样的 128 bit 安全级别，需要大小为 3072 bit 的公钥。这使得椭圆曲线的使用在计算上相对更高效。
在介绍了这么多椭圆曲线的世界之后，我们将继续了解在密码学背景下可以用它们做什么。正如我们所知，密码系统通常基于难以解决的“困难问题”。例如，我们提到的 RSA 基于因数分解问题，Diffie-Hellman 协议基于离散对数问题。基于椭圆曲线上的 ECDLP 问题的密码系统属于椭圆曲线密码学家族，简称 ECC。
让我们从一个故事开始。假设你在一个派对上——一个满是人的房间里，每个人都可以和每个人交谈，每个人都能听到每个人。房间里还有 Alice 和 Bob，他们以前从未见过面。Alice 喜欢 Bob，想约他出去。Alice 有点害羞，所以她想把这个秘密消息告诉 Bob，而不让其他派对客人听到。Alice 和 Bob 事先没有任何协调，Alice 对 Bob 说的每一句话都会被房间里所有其他客人听到。Alice 怎样才能在不让其他人听到的情况下把消息告诉 Bob 呢？
如果你回答“椭圆曲线”，那么你答对了！
Alice 将选择某条椭圆曲线及其中的一个生成元，并告诉 Bob。具体来说，Alice 会将两个曲线参数 𝑎、𝑏、模数 𝑝 和生成元 𝐺 传递给 Bob（以及房间里的其他人）。此外，Alice 将选择一个处于 $1 ≤ 𝑑_𝐴 ≤ 𝑛 − 1$ 范围内的值 $𝑑_𝐴$，其中 𝑛 是 𝐺 的阶。值 $𝑑_𝐴$ 称为 Alice 的私钥。Alice 将计算点 $𝐴 = 𝑑_𝐴𝐺$，这个点称为 Alice 的公钥，并将其告诉 Bob。类似地，Bob 将选择一个私钥 $𝑑_𝐵$，计算点 $𝐵 = 𝑑_𝐵𝐺$，这个点称为 Bob 的公钥，并将其告诉 Alice。
Alice 将取 Bob 的公钥，将该点乘以她的私钥，得到第三个点 $𝑃_𝐴 = 𝑑_𝐴𝐵$。类似地，Bob 将取 Alice 的公钥，将其乘以他的私钥，得到他自己的第三个点 $𝑃_𝐵 = 𝑑_𝐵𝐴$。如果我们分别检查 Alice 和 Bob 到达的点，会发现他们到达了同一个点！这一事实来自我们之前看到的点乘以常数的结合律性质：
$𝑃_𝐴 = 𝑑_𝐴𝐵 = 𝑑_𝐴(𝑑_𝐵𝐺) = 𝑑_𝐵(𝑑_𝐴𝐺) = 𝑑_𝐵𝐴 = 𝑃_𝐵$
在整个过程结束时，Alice 和 Bob 成功就曲线上的某个点达成了共识，并且在任何阶段，他们中的任何一方都没有将该点传给对方。每个人听到的信息是：𝑎、𝑏、𝑝、𝐺、𝐴、𝐵。在房间里听到这些信息的人无法据此找到 Alice 和 Bob 达成一致的那个点。
这是因为，如果房间里的另一个人想要找到那个点，他们需要知道 Alice 的私钥或 Bob 的私钥，才能将 𝐵 或 𝐴 与它们相乘。例如，要找到 Alice 的私钥，他们会查看 $𝐴 = 𝑑_𝐴𝐺$，因为这是唯一被发送且“包含”Alice 私钥的信息。给定 𝐺 和 $𝑑_𝐴𝐺$，找到 $𝑑_𝐴$ 等价于求解椭圆曲线上的离散对数问题，如前所述，这是一个困难问题。
这个优美的协议称为：椭圆曲线 Diffie-Hellman（ECDH）。
我们的故事还没有结束。尽管 Alice 和 Bob 就一个共享秘密点达成了共识，Alice 仍然没有向 Bob 提出她非常渴望的约会邀请。
双方就共享秘密点达成共识后，可以将其用作任何加密方法（例如 AES）的加密密钥，并从此通过加密进行安全通信。
通常取该点的 𝑥 或 𝑦 坐标之一来使用。为了保持安全性，建议对所选值进行哈希，并且只使用哈希结果作为加密密钥。在实践中，有时该值太大，无法用作加密密钥。例如，如果使用的哈希函数是 SHA-1，其输出长度为 160 bit，而 AES 加密只需要 128 bit。在这种情况下，通常只使用这 160 位中的 128 bit，并丢弃其余部分。
无论如何，此时 Alice 和 Bob 协商出一个加密密钥，并且只有他们两人知道。从此以后，他们通过加密进行通信，房间里任何窃听的人都无法理解他们在说什么。
以下是该协议的示意图：
