近年来，椭圆曲线密码学方法因其高效性和强安全性而变得流行。本文旨在以比当前互联网上已有的资料更清晰的方式介绍这一主题。
在本文中，我将介绍什么是椭圆曲线、可以在其上执行的基本运算，以及它们如何在密码学背景下使用。本文的大部分内容是关于已知攻击的示例，针对不正确的实现或错误的使用方式。在整篇文章中，我尝试将解释分为直观的高层部分和更详细的数学部分。读者可以关注其中感兴趣的部分，并跳过不太感兴趣的部分。
祝阅读愉快！
一般来说，椭圆曲线是某种曲线。例如抛物线，其方程为 $𝑦 = 𝑎𝑥^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 协商出一个加密密钥，并且只有他们两人知道。从此以后，他们通过加密进行通信，房间里任何窃听的人都无法理解他们在说什么。
以下是该协议的示意图：
使用协商好的密钥，Alice 加密消息“嘿 Bob，明天晚上你愿意出来喝杯咖啡吗？”，并将加密后的消息传递给 Bob。Bob 用他也知道的密钥解密该消息。Alice 希望 Bob 会同意，但这不属于协议的一部分。
在已知的 Diffie-Hellman（DH）协议中，双方公开传输一个素数 𝑝 和一个属于与 𝑝 对应群的生成元 𝑔。Alice 随机生成私钥 𝑎，并公开广播她的公钥 $𝐴 = 𝑔^𝑎\ \ \ \ (mod\ 𝑝)$。类似地，Bob 随机生成私钥 𝑏，并公开广播他的公钥 $𝐵 = 𝑔^𝑏\ \ \ \ (mod\ 𝑝)$。然后 Alice 取 Bob 的公钥，将其提升到她的私钥次方，从而计算出值 $𝐾 = 𝐵^𝑎 = (𝑔^𝑏)^𝑎 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$。同样，Bob 计算出值 $𝐾 = 𝐴^𝑏 = (𝑔^𝑎)^𝑏 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$。在此过程结束时，Alice 和 Bob 能够在不在彼此之间传输 𝐾 值的情况下就共同的 𝐾 值达成一致。
监听他们的攻击者无法根据广播的值 𝑝、𝑔、𝐴、𝐵 找到 𝐾。为此，他们必须找到 Alice 或 Bob 的私钥。例如，要计算 Alice 的私钥，他们必须根据 𝑔 和 $𝑔^𝑎\ \ \ \ (mod\ 𝑝)$ 找出 𝑎，这是一个困难问题。该问题称为离散对数问题（DLP）。
基于 DLP 的 DH 与基于 ECDLP 的 ECDH 之间存在非常明显的相似性（它们基本相同，只是多了 EC 前缀）。在这两种协议中，相互通信的双方都可以就某个共享秘密值达成一致，而无需事先协调任何内容。任何监听双方消息的人都将获知他们之间传递的公开信息，但无法得到他们之间共享的秘密值。### 椭圆曲线的第二个用途——消息签名
继续我们的故事。假设 Alice 和 Bob 去约会，共度了一个愉快的夜晚。第二天，Alice 收到一条消息：“嗨，Alice，我是 Bob，我昨天和你玩得很开心，这个周末我还想再见到你。”Alice 怀疑这条消息不是 Bob 发的，因为她知道 Bob 昨天和她在一起非常开心，他不可能等到周末才来见她，而是会想明天就见到她！Alice 如何验证这条消息确实是 Bob 写的呢？
如果你的答案是“椭圆曲线”，那你就又答对了！
椭圆曲线离散对数问题（ECDLP）的难度也可以用于消息签名。约会期间，Alice 和 Bob 约定使用某条椭圆曲线及其上的一个生成元 𝐺。Bob 生成了一个值 $𝑑_𝐵$，称为 Bob 的私钥，并计算出点 $𝑃_𝐵 = 𝑑_𝐵𝐺$，称为 Bob 的公钥。Bob 把公钥给了 Alice，以便她之后可以用来验证收到的消息是否确实由他签名。
假设 Bob 想要对某条消息 𝑚 进行签名。他会使用某个安全的哈希函数计算值 $z = hash(m)$，并保留结果中与 n（生成元 𝐺 的阶）的位长度相同的比特数。Bob 会生成一个在 $1 ≤ 𝑘 ≤ 𝑛 − 1$ 范围内的随机值 𝑘。然后 Bob 计算出点 $𝑘𝐺 = (𝑥_1, 𝑦_1)$，取其 𝑥 坐标，并计算 $𝑟 = 𝑥1\ \ \ \ (mod\ n)$。最后，Bob 计算值 $𝑠 = 𝑘^{−1}(𝑧 + 𝑟𝑑_𝐵)$。
消息 𝑚 的签名定义为所计算出的值对 𝑟 和 𝑠。
假设 Alice 收到了一条消息 𝑚，其签名由值对 𝑟 和 𝑠 组成。Alice 希望确认这确实是 Bob 签的名。Alice 将像 Bob 一样计算值 $z = hash(m)$。然后 Alice 计算值 $𝑢_1 = 𝑧𝑠^{−1}$ 和 $𝑢_2 = 𝑟𝑠^{−1}$。最后 Alice 使用 Bob 的公钥 $𝑃_𝐵$，计算点 $𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = (𝑥_1, 𝑦_1)$。如果满足 $𝑟 ≡ 𝑥_1\ \ \ \ (mod\ n)$，则签名被视为有效。这样做的正确性在于以下等式成立：
$𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = 𝑧𝑠^{−1}𝐺 + 𝑟𝑠^{−1}𝑃_𝐵 = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑃_𝐵) = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑑_𝐵𝐺) = 𝑠^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘(𝑧 + 𝑟𝑑_𝐵)^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘𝐺$
如果签名有效，该点的 𝑥 坐标确实应当等于消息签名中定义的 𝑟。需要注意的是，生成元 𝐺 的阶（用字母 𝑛 表示）应为素数；这样才能在签名和验证算法中确实计算出相应的逆元。
可以看出，只有持有私钥 $𝑑_𝐵$ 的人才能为公钥 $𝑃_𝐵$ 生成有效签名。没有 $𝑑_𝐵$ 值的攻击者无法计算出签名中与 $𝑃_𝐵$ 对应的值 𝑠。如果攻击者想创建与某条消息匹配的签名，就必须求解 ECDLP 问题，即在已知 $𝐺$ 和 $𝑃_𝐵 = 𝑑_𝐵𝐺$ 的情况下找出私钥 $𝑑_𝐵$，而这是一个困难问题。
这个签名协议被称为椭圆曲线数字签名算法，简称 ECDSA。该协议确保被签名的消息未被篡改或伪造，并确保签名者无法否认自己创建了该签名。
与 ECDH 协议不同，ECDH 中双方无需事先协调任何内容；而在 ECDSA 协议中，双方必须事先就公钥达成一致。只有当每一方都确切知道自己所持有的公钥确实属于想要通信的对象时，该协议才能使用。否则，用各自持有的公钥来验证签名就毫无意义。
回到我们的故事。Alice 确信自己手中的公钥 $𝑃_𝐵$ 确实属于 Bob，因为 Bob 在约会时明确地把它给了她。Alice 尝试用它来验证消息，却发现并不匹配。当然！这条消息是别人创建并签名的，正如 Alice 所怀疑的那样。
下面是该协议的示意图：
在用于消息签名的 ElGamal 协议中，双方约定一个大素数 𝑝 和一个生成元 𝑔。签名方生成一个在 $1 ≤ 𝑑 < 𝑝 − 1$ 范围内的值 𝑑，称为私钥，计算出值 $𝑦 = 𝑔^𝑑\ \ \ \ (mod\ p)$，称为公钥，并将其公开。
为了对某条消息进行签名，他们计算值 $z = hash(m)$，并生成一个在 $1 ≤ 𝑘 < 𝑝 − 1$ 范围内且与 $(p-1)$ 互素的随机值 𝑘。他们计算 $𝑟 = 𝑔^𝑘\ \ \ \ (mod\ p)$ 和 $𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)\ \ \ \ (mod\ (p-1))$。消息 m 的签名定义为所计算出的值对 𝑟 和 𝑠。
收到某条消息 𝑚、且其签名由值对 𝑟 和 𝑠 组成的一方，使用公钥 𝑦 通过计算值 $𝑢_1 = 𝑟^𝑠𝑦^𝑟$ 和 $𝑢_2 = 𝑔^𝑧$ 来验证签名。如果 $𝑢_1 = 𝑢_2$，则签名被视为有效。这是因为根据 𝑠 的定义，有：
$𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)$，因此 $𝑘𝑠 = 𝑧 − 𝑑𝑟$，于是 $𝑧 = 𝑘𝑠 + 𝑑𝑟$。因此：
$𝑢_2 = 𝑔^𝑧 = 𝑔^{𝑘𝑠+𝑑𝑟} = 𝑔^{𝑘𝑠}𝑔^{𝑑𝑟} = (𝑔^𝑘)^𝑠(𝑔^𝑑)^𝑟 = 𝑟^𝑠𝑦^𝑟 = 𝑢_1$
攻击者在不了解私钥 𝑑 的情况下，无法为公钥 𝑦 创建有效签名。要在已知公钥的情况下获得私钥，攻击者必须求解 DLP 问题，而这是一个困难问题。
这里同样可以清楚地看到基于 ECDLP 的 ECDSA 与基于 DLP 的 ElGamal 之间的相似性。在这两种情况下，双方都必须事先协调好公钥，而且每次想要对一条新消息签名时都必须生成一个随机的 𝑘 值。此外，在这两种情况下，窃听双方消息的攻击者都无法推断出可用于伪造签名的有用信息。
我们已经看到椭圆曲线如何用于密码系统中，以协商共享秘密值和对消息进行签名。与生活中的一切事物一样，当真正付诸实践时，事情并不总是按计划进行。在本文的其余部分，我将介绍攻击基于 ECC 的密码系统的不同方法，这些系统要么被用户误用，要么以不安全的方式实现。
很自然地，我把这部分分为对 ECDH 的攻击和对 ECDSA 的攻击。在这两种情况下，如果找到了某一方的私钥，我们就说攻击“成功”了，然后就到此为止。对于 ECDH，这已经足够了，因为从私钥可以推导出共享秘密值以及之后用它加密的所有信息。对于 ECDSA，这也足够了，因为我们可以用私钥按自己的意愿对消息签名。
SageMath 是一个免费开源数学软件。它可以使用与 Python 几乎相同的语法编写，也可以作为 Python 库使用。该库实现了与椭圆曲线相关的实用函数，因此对于我们在 ECC 上下文中需要进行的计算非常有用。在本文中，我会提供用该库编写的代码片段。我发现它最容易安装在 Ubuntu 操作系统上，特别是 22.04 版本。要安装它，只需运行命令：sudo apt install sagemath。
若要运行包含代码的文件，请将文件保存为 .sage 扩展名并运行命令：sage file.sage。
此外，还可以像 Python 解释器一样，通过运行命令 sage 来使用解释器。也可以创建导入 sage.all 库的 .py 文件，并用命令 python3 file.py 运行它们。请注意，使用命令 sage 运行文件时，符号 ^ 被解释为幂运算；而使用 python3 运行时，该符号被解释为异或运算。
在本文中，我主要使用 SageMath 中的以下函数：
E.gens() - 在曲线 E 中查找生成元G.order() - 计算生成元 G 的阶n*G - 将生成元 G 与数字 n 相乘n.factor() - 将数字 n 分解为因子——该函数返回一组对 (𝑝, 𝑒)，其中 𝑝 是素因子，𝑒 是其指数，即 𝑝 在 n 的分解中出现的次数crt - 求解中国剩余定理的方程组也许最容易被攻击的 ECDH 误用，就是选择一个阶 n 过小的生成元。
如前所述，以 $O(\sqrt{n})$ 的复杂度求解 ECDLP 问题是可能的。当 𝑛 过小（例如 32 位）时，求解该问题就变得可行。有几种算法可以解决这个问题，包括 Baby-Step Giant-Step、Pollard's Rho 和 Pollard's Lambda。这些算法可以在 SageMath 的帮助下作为黑盒来运行，只需使用 discrete_log 函数即可：```python
import random
p = random_prime(2^32)
a = random.randrange(p)
b = random.randrange(p)
E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]
n = G.order()
private_key = random.randrange(n)
A = private_key * G
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
在此代码片段中，我们在限制 `𝑝` 为 32 位长的前提下，随机为曲线选择参数。这一限制保证了曲线上的点数为 $O(2^{32})$，因此其中每个点的阶也至多为 $O(2^{32})$。之后我们创建曲线，在其中选择某个生成元，生成一个随机私钥，并计算公钥。最后，从生成元和公钥出发，我们计算离散对数以找到私钥，并验证找到的密钥确实正确。这段代码最多只需几秒即可找到私钥。
## 生成元的阶是光滑数
如前所述，生成元的阶定义为生成点不断与自身相加所形成的"圆"上的点数，用 `𝑛` 表示。如果 `𝑛` 是一个可分解为更小素因数的合数，那么就可以高效地求解 ECDLP。这样的数称为光滑数，就本文而言，它是指能够分解为足够多的素因数、且每个素因数都足够小以使我们的攻击可行的数。光滑数的正式定义略有不同，但与我们无关。
直观地说，这是通过分别"攻击"每个素因数来实现的。给定一个生成点 `𝐺`，它构成一个非常大的"圆"，以及"圆"上的某个点 `𝑃`，满足 `𝑃 = 𝑘𝐺`。这个大的"圆"可以被拆解为若干小的"圆"，每一个的大小对应 `𝑛` 的一个素因数。在每个小"圆"中，我们可以将 `G` 和 `P` 映射到位于小"圆"中的其他对应点 `G'` 和 `P'`，并且满足 `𝑃′ = 𝑘′𝐺′`。由于"圆"很小，求解该问题并找到 `𝑘′` 相对容易。最后，我们可以将找到的所有小 `𝑘′` 组合成原"圆"中所需的 `𝑘`。
执行上述过程的算法称为 Pohlig-Hellman 算法。其运行时间复杂度为 $O(\sqrt{p_{max}})$，其中 $p_{max}$ 是 `𝑛` 分解中最大的素因数。这也合乎情理，因为该算法中最"重"的部分是在小"圆"中最大者内求解 ECDLP 问题。例如，`n` 可能是一个 128 位数，它分解出的素因数中最大的是一个 30 位数。该算法将求解问题的复杂度从 $2^{64}$ 降低到 $2^{15}$，从而将其从不可行变为可行。
幸运的是，SageMath 的 `discrete_log` 函数在其实现中执行了这一算法。要运行该攻击，你可以直接调用该函数：```python
p = 183740305291166889900894879302858411333
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(123764810000715262449972298016641419881,
144640915410606177233842123838934486566)
n = G.order()
print("number of bits in n:", n.nbits())
print("n's factors:", n.factor())
print("number of bits in n's greatest factor:", n.factor()[-1][0].nbits())
import random
private_key = random.randrange(n)
A = private_key * G
print("Calculating discrete_log...")
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
在此代码片段中，我们定义了一条椭圆曲线及其中的一个生成元，并打印其阶的质因数。输出为：``` number of bits in n: 128 n's factors: 2 * 3 * 13 * 101 * 211 * 21141581 * 38581057 * 60652309 * 2234328781 number of bits in n's greatest factor: 32 Calculating discrete_log... success!
可以看出，虽然生成元的阶长为 128 位，但其分解为素因子后，最大的素因子仅为 32 位。
之后，和之前的攻击一样——我们选择一个随机的私钥，由它计算出一个公钥，然后在给定生成元和公钥的情况下，计算出私钥并验证其正确性。
虽然我们已经完成了，但我们还没有看到“小”圈是如何定义的，如何将点 `𝐺` 和 `𝑃` 映射到它们对应的点 `𝐺′` 和 `𝑃′`，以及如何将所有小解合并成一个大解。我将在这里尝试直观地解释，因为下一个攻击也基于这一部分。
假设我们有一个阶为 `3𝑥5𝑥7 = 105` 的“圈”，其生成元是 `𝐺`。我们定义一个点 `𝐺′ = (5𝑥7)𝐺 = 35𝐺`，并观察由它生成的“圈”。如果我们从 `𝐺′` 前进一步，也就是将 `𝐺′` 加到自身，这就像在原“圈”中从点 `35𝐺` 前进 35 步，然后我们会到达点 `2𝐺′ = 70𝐺`。如果再前进一步，我们会到达点 `3𝐺′ = 105𝐺 = 𝒪`；如果再前进一步，我们会到达点 `4𝐺′ = 35𝐺 = 𝐺′`，也就是回到起点。由 `G′` 形成的“圈”的阶为 `3`，这并非巧合，因为在阶为 `105` 的“圈”上，恰好可以走 `3` 步大小为 `35` 的“步”。类似地，我们可以通过定义点 `𝐺′ = (3𝑥7)𝐺 = 21𝐺` 来创建一个阶为 `5` 的“圈”，并通过定义 `𝐺′ = (3𝑥5)𝐺 = 15𝐺` 来创建一个阶为 `5` 的“圈”。
反过来看会更有趣。假设在原“圈”中，我们从点 `G` 出发走了 `𝑛` 步，到达点 `𝑛𝐺`。如果在小“圈”中也从点 `𝐺′` 出发走 `𝑛` 步，我们会到达点 `𝑛′𝐺′`，且满足 `𝑛 ≡ 𝑛′ (𝑚𝑜𝑑 3)`。为什么这很有趣？因为 `𝐺′` 的阶远小于 `𝐺` 的阶，因此给定 `𝐺′` 和 `𝑛′𝐺′`，我们可以相对容易地求出 `𝑛′`。如果我们这样做，并且对“圈”的阶的另外两个素因子 `5` 和 `7` 也这样做，就会得到以下值：
𝑛 ≡ $𝑛'_1$ (𝑚𝑜𝑑 3)\
𝑛 ≡ $𝑛'_2$ (𝑚𝑜𝑑 5)\
𝑛 ≡ $𝑛'_3$ (𝑚𝑜𝑑 7)
根据这三个值，可以利用中国剩余定理轻松求出 `𝑛`，从而解决原始问题。
## 生成元的阶几乎是一个光滑数，且私钥较小
假设与之前的攻击类似，我们得到一条曲线，其中生成元的阶可以分解为素因子，但这一次，最大的素因子太大，导致求解其 ECDLP 不可行。例如，如果生成元的阶是 `256 bit`，但最大的素因子是 `128 bit`。
Pohlig-Hellman 算法大约需要 $O(2^{64})$ 次运算才能找到私钥，这是不可行的。
如果我们知道所使用的私钥相对较小，那么仍然可以高效地找到它。
假设私钥是 `64 bit`（而不是 `256 bit`）。当创建公钥时，生成元与私钥相乘，你会得到生成元所创建的“圈”中的某个点。尽管这个“圈”约有 $2^{256}$ 个点，该点仍会“落入”前 $2^{64}$ 个点中的某个位置。私钥与“圈”中对应更大值的点之间不存在任何“交互”。
可以运行 Pohlig-Hellman 算法，但“丢弃”过大的“圈”，前提是剩余“圈”的阶的乘积至少与私钥长度相当。如果能找到足够多的小素因子，且其乘积至少为 `64 bit`，那么相应的“圈”就足以执行我们之前看到的相同攻击。
如果说之前我们在编写代码方面很轻松，那么这次我们将不得不自己实现一些东西，因为 SageMath 的 `discrete_log` 函数并不知道我们想要“丢弃”部分素因子。以下代码片段实现了这一点：```python
p = 88664572752015126127869404674421545790506871948117527783533589813159111825511
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(19374976316789648652022260955836934561553454311144967863145605756652014623129,
68630819472054489323664324766002023315775509214344811025345735680440707888471)
n = G.order()
print("Number of bits in n:", n.nbits())
factors = n.factor()
print("n's factors:", factors)
PRIVATE_KEY_BIT_SIZE = 64
import random
private_key = random.randrange(2^PRIVATE_KEY_BIT_SIZE)
P = private_key * G
print("We know that the private key is", PRIVATE_KEY_BIT_SIZE, "bits long")
print("Lets find which of the factors of G's order are relevant for finding the private key")
# find factors needed such that the order is greater than the secret key size
count_factors_needed = 0
new_order = 1
for p, e in factors:
new_order *= p^e
count_factors_needed += 1
if new_order.nbits() >= PRIVATE_KEY_BIT_SIZE:
print("Found enough factors! The rest are not needed")
break
factors = factors[:count_factors_needed]
print("Considering these factors:", factors)
print("Calculating discrete log for each quotient group...")
subsolutions = []
subgroup = []
for p, e in factors:
quotient_n = (n // p ^ e)
G0 = quotient_n * G # G0's order is p^e
P0 = quotient_n * P
k = G0.discrete_log(P0)
subsolutions.append(k)
subgroup.append(p ^ e) # k the order of G0
print("Running CRT...")
found_key = crt(subsolutions, subgroup)
assert found_key * G == P
assert private_key == found_key
print("success!")
在以下代码片段中，我们定义了一条椭圆曲线及其生成元，并打印其阶的质因数。输出为：``` Number of bits in n: 256 n's factors: 2 * 3 * 29 * 2699 * 28751 * 831913766251 * 92996710252298530263979 * 84878782522781478604307230464271
生成元的阶为 `256 bit`，它分解为若干个素因子，其中最大的两个分别是 `77 bit` 和 `107 bit`。它们足够大，以至于求解 ECDLP 是不切实际的。然后，随机生成一个 `64 bit` 的私钥，并计算出公钥。下一步，我们“收集”足够的素因子，直到得到一个长度至少为 `64 bit` 的阶。输出如下：```
We know that the private key is 64 bits long
Lets find which of the factors of G's order are relevant for finding the private key
Found enough factors! The rest are not needed
Considering these factors: [(2, 1), (3, 1), (29, 1), (2699, 1), (28751, 1), (831913766251, 1)]
可以看出，最大的两个因子是冗余的，我们剩下最大的因子是 40 bit。下一步，对于我们剩下的每个因子，我们按照前面解释的方法计算点 𝐺′ 和 𝑃′，并针对每一个求解 ECDLP。结果和素数因子分别保存在列表 subsolutions 和 subgroups 中。最后，使用中国剩余定理将所有结果组合成私钥，并验证其确实正确。
在检验椭圆曲线上的点加法定义时，我们注意到一个有趣的性质：点加法中不使用值 𝑏，而只使用值 𝑎 和 𝑝。这意味着，将位于一条曲线上的点相加，对于另一条仅 𝑏 值不同的曲线也可能有意义。当然，这对于点乘以一个数同样成立。如果用户不验证从对方收到的作为公钥的点确实位于自己的曲线上，那么他们就会让自己暴露于无效曲线攻击（Invalid Curve Attack）之下。
假设两个参与方约定了某条椭圆曲线 $E_1$。攻击者可以创建一条恶意曲线 $𝐸_2$，它与 $𝐸_1$ 具有相同的 𝑎 和 𝑝 值，但 𝑏 值不同。在曲线 $𝐸_2$ 上，攻击者会选择阶很小的点 𝑃，例如 3。当然，点 𝑃 不会位于 $𝐸_1$ 上，因为它满足的方程具有与 $𝐸_1$ 不同的 𝑏 值。攻击者将点 𝑃 作为其公钥发送给用户。假设用户懒得去验证收到的点确实位于双方约定的曲线 $𝐸_1$ 上。用户会取出从攻击者处收到的公钥，乘以自己的私钥，得到一个点，该点应当是根据 ECDH 协议定义中的共享秘密点。从用户的角度看，他们会计算 $𝐸_1$ 上的乘法运算。但由于点 𝑃 根本不在 $𝐸_1$ 上，而在 $𝐸_2$ 上，用户实际上是在 $𝐸_2$ 上计算乘法运算。之后，用户将使用共享秘密点与攻击者继续通信。假设双方将该点的 𝑥 坐标用作 AES 加密密钥。这种情况下，用户会加密某条消息并发送给攻击者。
由于 𝑃 的阶是 3，用户计算出的共享点只有 3 种可能。攻击者遍历这些可能的点，找出其中哪一个对应于能成功解密用户所发送加密消息的密钥。有了这个点和起始点 𝑃，攻击者就能推断出用户私钥除以 3 的余数。攻击者可以向用户发送更多恶意的 𝑃 点，其阶依次增大，例如 5、7，等等。通过这种方式，攻击者可以收集足够多的值，这些值表示用户私钥除以一些小整数的余数。最后，攻击者可以使用中国剩余定理计算出用户的私钥，方式与我们在前一种攻击中看到的一样。
这里有一个更直观的解释：攻击者可以给用户提供一个位于非常小的“圆”上的点，例如长度为 2。用户会在这个“圆”上向前走任意步数，并到达目标点。攻击者知道用户的目标点，它只有 2 种可能。因此，攻击者可以判断用户是在圆上走了偶数步还是奇数步。攻击者可以给用户提供更多位于长度为 3、5、7 等的“圆”上的点，直到攻击者拥有足够多的此类因子，每个因子都包含关于用户所走步数的少量信息。最后，攻击者可以将所有这些值组合起来，得到用户所走的确切步数，也就是用户的私钥。
以下代码演示了这种攻击：```python from ecdsa.ecdsa import generator_128r1, curve_128r1 from Crypto.Util.number import long_to_bytes from Crypto.Util.Padding import pad, unpad from Crypto.Cipher import AES import random
curve = curve_128r1 G = generator_128r1 n = G.order() p = curve.p() a = curve.a()
private_key = random.randrange(n)
def encrypt_data(shared_point, message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)
message = pad(message.encode(), 16)
return cipher.encrypt(message)
def decrypt_data(shared_point, enc_message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)
decrypted = cipher.decrypt(enc_message)
return unpad(decrypted, 16)
def ECDH(A): # Send our public key to the other side # Have them reach the shared point and # Send us an encrypted message using the shared point as key
# This part takes place remotely and is unknown to the attacker
shared_point = private_key * A
message = "Inconceivable!"
return encrypt_data(shared_point, message)
def brute_force_encrypted_message(A, encrypted_message, max_order): # Returns n such that n*A matches the key used to encrypt the message for i in range(1, max_order): shared_point = i * A try: # If both padding is correct and all characters are ascii # Then it is probably the correct encryption key decrypted = decrypt_data(shared_point, encrypted_message) decrypted = decrypted.decode() return i except: continue raise Exception("Did not find a value for one of the encrypted messages")
def find_curves_with_small_subgroup(p, a, max_order): # Yield tuples of (order, point) such that the point is # on a curve with the same a & p values, but different b # and the point's order is <= max_order orders_found = set() b = 0 while True: b += 1 if b == p: # Ran out of b values break if (4a^3 + 27b^2) % p == 0: # Curve is singular continue
E = EllipticCurve(GF(p), [a, b])
for _ in range(100):
R = E.random_point()
n = R.order()
for f, e in n.factor():
if f in orders_found:
continue
if f > max_order:
break
# Create a point with order f
orders_found.add(f)
P = (n // f) * R
assert P.order() == f
yield (f, P)
subsolutions = [] subgroup = [] max_order = 10000 upto = 1 for order, A in find_curves_with_small_subgroup(p, a, max_order): upto *= order print("Found point with order", order, "so now can find keys of size up to", upto)
# Send this point as our public key and get an encrypted message from other side
encrypted_message = ECDH(A)
# Find the value n such that: private_key = n (mod order)
key_mod_order = brute_force_encrypted_message(A, encrypted_message, max_order)
# Save result to be used in CRT later
subsolutions.append(key_mod_order)
subgroup.append(order)
# Found enough values to calculate private key
if upto >= n:
break
print("Found enough values! Running CRT...") found_key = crt(subsolutions, subgroup) print("Found private key", found_key) assert private_key == found_key print("success!")
在这段代码中，选择了一条曲线和一个生成元，用户随机生成一个私钥，并在 ECDH 协议的每次使用中都使用这个私钥。函数 `find_curves_with_small_subgroup` 会找出点与阶的配对，使得每个点的阶都相对较小，并且该点位于一条与原始曲线仅在 `𝑏` 的值上有所不同的曲线上。代码会生成这样的配对，直到找到足够多的配对为止。对于每一对，公钥被发送给用户，并收到来自用户的加密消息。
对加密消息执行暴力破解，以找出用户的私钥值（对当前阶取模）。所有这些结果都会被保存下来，最后我们使用中国剩余定理来计算用户的私钥并验证其正确性。在这种情况下，双方约定使用 AES 进行通信，加密密钥是共享秘密点的 `x` 坐标，IV 是其 `𝑦` 坐标。
攻击的复杂度为 $𝑂(𝑛_{𝑚𝑎𝑥})$，其中 $𝑛_{𝑚𝑎𝑥}$ 是所有恶意点的阶中的最大值。这是因为攻击中“最重”的部分是对小“圆”中最大的那个“圆”进行暴力破解，而幸运的是，攻击者几乎可以完全控制这个值。因此，这种攻击在复杂度方面相对高效。如前所述，这个案例中问题的根源在于，用户没有检查收到的点是否位于自己正在使用的曲线上。此外，用户在每次新使用 ECDH 时都使用相同的私钥，这并不安全。
## 曲线是奇异的
椭圆曲线要在密码学上安全，必须具备的重要性质之一就是它是非奇异的。非奇异曲线是指其某个称为“判别式”的值不为零的曲线。当曲线的参数 `𝑎` 和 `𝑏` 满足以下不等式时，该条件成立：
$4a^3 + 27b^2 ≠ 0$
不满足这个不等式的曲线具有一个“有问题”的点，称为 `singular point`。这类点有两种类型：节点（node）和尖点（cusp）。节点型点位于一条曲线上，该曲线有一个在奇异点处自交的环，并且可以过这个点作两条不同的切线。
尖点则是曲线“尖锐”的点，仿佛有两条线从中伸出，但在该点处只有一条切线与曲线相切。
<img src="https://assets.kitploit.com/production/public/readmes/48932/a40d8ce67ecb97eeabe85b52937a8935bc917b622e02168d9047200ed54feafc.png" alt="Singular Elliptic Curves" width="500">
对于节点型点，存在一个二重根，因此曲线方程可以写成：
$y^2 = (x-x_0)^2(x-x_1)\ \ \ \ (mod\ p)$
通过将变量 $x$ 替换为变量 $(𝑥 + 𝑥_0)$，可以将曲线向左“移动”，从而得到如下形式：
$y^2 = x^2(x+x_0-x_1)\ \ \ \ (mod\ p)$
现在奇异点位于坐标轴的原点。数值 $t = (x_0-x_1)$ 可用于建立曲线上点与整数之间的映射，使得曲线上点之间的加法运算等价于数字之间的乘法运算。对于每个点 `(𝑥, 𝑦)`，我们将它匹配到数字
$\frac{y+\sqrt{t}x}{y-\sqrt{t}x}$。特别是，对于满足 `𝑄 = 𝑛𝐺` 的一对点 `𝐺` 和 `𝑄`，我们可以映射到数字 `𝑔` 和 `𝑞`，使得 $𝑞 ≡ 𝑔^𝑛\ \ \ \ (mod\ p)$，这就是一个“普通”的 DLP 问题。为了说明这一过程，我在文章末尾的参考资料中添加了一个使用小数字的示例链接。在我们所做的映射中，我们使用了直线方程 $y+\sqrt{t}x$ 和 $y-\sqrt{t}x$，这两条线对应于可以在奇异点处作出的两条切线（在我们将曲线“移动”之后），这基本上就是这种攻击能被使用的原因。
这样的 DLP 问题可以借助 Pohlig-Hellman 算法高效求解，我们在前面已经见过这个算法，因为它也可以用于整数而非仅用于曲线上的点。在点的语境中，我们看到当生成元的阶是光滑数时，该算法很有用。与曲线上点的“圆”不同——其阶可以是任意值——在模素数 `𝑝` 的整数域中，阶是 `𝑝 − 1`。如果 `𝑝 − 1` 是光滑数，那么该算法就能高效地求解 DLP 问题，从而找到私钥 `n`。
下面的代码片段实现了这一点：```python
p = 102360775616927576983385464260307534406913988994641083488371841417601237589487
a = -3
b = 2
assert (4*a^3 + 27*b^2) % p == 0
Gx = 1777671135698746847568710125129424132255529153914112337834835240247819869964
Gy = 6786424314307625790108882554225666781375821855884993473586521771737454762217
Qx = 45541468695354471317248123146376609839909398850045396377931300808635064950836
Qy = 42191909885728105279718027025083923092282618497451601162405594991792376530066
x = GF(p)["x"].gen()
f = x^3 + a*x + b
roots = f.roots()
assert len(roots) == 2 # two roots, so one must be double
if roots[0][1] == 2:
double_root = roots[0][0]
single_root = roots[1][0]
else:
double_root = roots[1][0]
single_root = roots[0][0]
print("double root:", double_root)
print("single root:", single_root)
# map G and Q to the new "shifted" curve
Gx = (Gx - double_root)
Qx = (Qx - double_root)
# Transform G and Q into numbers g and q, such that q=g^n
t = double_root - single_root
t_sqrt = t.square_root()
def transform(x, y, t_sqrt):
return (y + t_sqrt * x) / (y - t_sqrt * x)
g = transform(Gx, Gy, t_sqrt)
q = transform(Qx, Qy, t_sqrt)
print("g:", g)
print("q:", q)
# Find the private key n
print("Factors of p-1:", factor(p-1))
print("Calculating discrete log for g and q...")
found_key = discrete_log(q, g)
print("Found private key:", found_key)
from Crypto.Util.number import long_to_bytes
print("The secret is:", long_to_bytes(found_key).decode())
在这段代码片段中，我们定义了椭圆曲线的参数，并验证它确实是奇异的。我们找到与曲线对应的多项式的根，并确定其中哪个是重根。我们利用重根来“移动”曲线，并到达“移动”后的点 𝐺 和 𝑄。然后根据我们找到的根计算 $\sqrt{t}$，并用它将点 𝐺 和 𝑄 映射到数字 𝑔 和 𝑞。我们打印 𝑝 − 1 分解为其质因数的结果（以验证 DLP 确实可以高效求解）。最后我们计算 DLP，并将结果解释为字符串。
输出为： ``` double root: 1 single root: 102360775616927576983385464260307534406913988994641083488371841417601237589485 g: 79308184675041981395063385790064051127319168083579208141274962436724168376607 q: 72551144069373709737718398534799929820619379063890479978458954196900267190559 Factors of p-1: 2 * 41 * 2422091127107 * 3224683479179 * 3224849279789 * 3269304069319
This time I hid a message in the private key itself. It should be noted that because it is a singular curve, it is not possible in SageMath to create it in a normal way, define points on it and perform operations with them as we did before. In this code I defined the coordinates of the points as constant variables. To calculate the point `𝑄` I multiplied the private key with generator myself using my own implementation of the Double And Add algorithm.
## The Curve Is Supersingular
Given an elliptic curve modulo `𝑝`, and a generator whose order is `𝑛`, the Embedding Degree of the curve with respect to the generator is defined to be the smallest number `k` that satisfies the equation $p^k ≡ 1\ \ \ \ (mod\ 𝑛)$. With certain transformations, the ECDLP problem can be reduced into a DLP problem in a field of order $𝑝^𝑘$. The value `𝑘` is usually a very large number (about same size as `𝑝` itself), but when it is relatively small (say, smaller than `6`), the curve is called `supersingular` and it becomes feasible to solve this DLP problem efficiently. This attack is called MOV attack, named after its three inventors (Menezes-Okamoto-Vanstone).
The transformations I mentioned are functions that receive two points, and return some number in the complex numbers field. Transformations that can be used are Weil Pairing or Tate Pairing, and we will use them as a black box. Such transformation `𝑇` satisfies the following property for every pair of points `𝑃`, `𝑄`:
$T(mP, nQ)=T(P,Q)^{mn}$
Therefore, given two points `𝐺` and `𝑄 = 𝑚𝐺`, we can randomly select a third point `𝑅` and calculate the two values: \
$g = T(G, R)$ \
$q = T(Q, R)=T(mG,R)=T(G,R)^m=g^m$
From here we can solve the DLP problem for `𝑔` and `𝑞` in a field of order $p^k$, thus finding the private key `𝑚`. I included a link to a more detailed explanation of the math behind this attack, in the references at the end of the article.
The following code snippet performs this attack:```python
p = 682209701131405092329016993551
a = -35
b = 98
E = EllipticCurve(GF(p), [a, b])
G = E(516365702870683577608927237052,
524474557735717484100814381066)
# Find embedding degree k
Gn = G.order()
k = 1
while p^k % Gn != 1:
k += 1
print("Found k:", k)
# Select private key, and calculate public key Q
private_key = 5072587499125503347
Q = private_key * G
# Define new curve mod p^k and the points on it
Ek = EllipticCurve(GF(p ^ k), [a, b])
Gk = Ek(G)
Qk = Ek(Q)
Rk = Ek.random_point()
# Find a point T with order d such that d divides G's order
m = Rk.order()
d = gcd(m, Gn)
Tk = (m // d) * Rk
assert Tk.order() == d
assert (Gn*Tk).is_zero() # Point INFINITY
# Using T, pair G and Q to integers g and q such that q=g^n (mod p^k)
g = Gk.weil_pairing(Tk, Gn)
q = Qk.weil_pairing(Tk, Gn)
# Alternatively:
#g = Gk.tate_pairing(Tk, Gn, k)
#q = Qk.tate_pairing(Tk, Gn, k)
# Make sure the pairing did not break anything
assert g ^ private_key == q
print("Calculating private key...")
found_key = q.log(g)
assert found_key == private_key
print("success!")
from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
在此代码片段中，我们定义了一条曲线及其生成元，并计算其嵌入度值，本例中为 2，因此执行该攻击是可行的。我们定义了一条与原始曲线相同的曲线，区别在于计算基于模 $𝑝^𝑘$ 而非模 $𝑝$。两个点 𝐺 和 𝑄 也位于新曲线上。然后我们找到一个阶能够整除 𝑛 的第三点。
利用该第三点，我们将 𝐺 和 𝑄 映射为数字 𝑔 和 𝑞，并计算它们的离散对数。最后，我们验证所获得的结果确实是正确的。
输出为：``` Found k: 2 Calculating private key... success! The private key is: Festivus
从计算的角度来看，如今存在一些 Index Calculus 算法，可以相对高效地求解 DLP 问题，其复杂度为 $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$。这个表达式看起来可能有些吓人，但与复杂度为 $O(\sqrt{p})=e^{O(log\ p)}$ 的 ECDLP 算法相比，可以看出，在嵌入度（Embedding Degree，记为 `𝑘`）确实很小的情况下，求解 DLP 问题会更容易。
## 曲线异常
如果某条曲线具有这样的性质：曲线的阶（即其上的点数）恰好等于模数 `𝑝`，那么它就被称为 `Anomalous Curve`（异常曲线），并且容易受到一种名为 Smart 攻击的攻击。这种攻击使用 `𝑝-adic numbers`（p 进数）。这样的数可以表示为 `p` 的幂（正幂和负幂）与系数的和。形式上，这样的数 `s` 是如下形式的级数：
$s=\sum_{i = -k}^{\infty} a_{i}p^i = a_{-k}p^{-k} + \cdots + a_0 + a_1p + a_2p^2 + \cdots$
其中系数为 $0 ≤ 𝑎_𝑖 < 𝑝$ 范围内的整数，并且该和可以沿 `𝑝` 的正幂方向无限延伸。在这样的数中，我们“从右向左”而不是“从左向右”查看数字，因此这样的级数可以收敛到某个值。这样的数属于一个不同于我们所熟悉数系的数系，其行为也与“常规”数学规则截然不同。仅关于这个主题就可以单独写一整篇文章；对于感兴趣的读者，我在文章末尾的参考文献中附上了一个视频链接，该视频以相对清晰的方式对此进行了介绍。
无论如何，在此攻击中，会基于给定曲线创建一条新曲线，该新曲线被定义在 p 进数之上。在原始曲线上给定两个点 `𝐺` 和 `𝑄 = 𝑚𝐺`，我们将它们映射到新曲线上的对应点。从所得点的坐标可以轻松计算出 `𝑚`。
以下代码执行该攻击：```python
def lift(P, E, p):
# lift point P from old curve to a new curve
Px, Py = map(ZZ, P.xy())
for point in E.lift_x(Px, all=True):
# take the matching one of the 2 points corresponding to this x on the p-adic curve
_, y = map(ZZ, point.xy())
if y % p == Py:
return point
p = 82880337306360052550952380657384418102169134986290141696988204552000561657747
a = 26413685284385555604181540288021678971301314378522544469879270355650843743231
b = 10017655579196313780863100027113686719855502076415017585743221280232958057095
E = EllipticCurve(GF(p), [a, b])
G = E(37991937053350834320678619330546903567320901767090609881924528835279022654346,
28947208718252880061735762506756351277969075978732800286053352115837132331595)
assert E.order() == p
private_key = 28153370716511608040616395150859085058202177279382452583684367923334520519740
P = private_key * G
# Lift the points to some new curve over p-adic numbers
E_adic = EllipticCurve(Qp(p), [a+p*13, b+p*37])
G = p * lift(G, E_adic, p)
P = p * lift(P, E_adic, p)
# Calculate discrete log
Gx, Gy = G.xy()
Px, Py = P.xy()
found_key = int(GF(p)((Px / Py) / (Gx / Gy)))
assert found_key == private_key
print("success!")
from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
在这段代码片段中，定义了一个 lift 函数，它接收原始曲线上的一个点，并将其对应到新曲线上的一个点。然后我们定义一条椭圆曲线及其中的一个生成元，并验证该曲线的阶确实为 p。我们选择一个私钥并计算对应的公钥，然后执行攻击。我们在 𝑝-adic 数上定义一条新曲线，并使用 lift 函数将原始点 𝐺 和 𝑃 映射到新曲线上的对应点，然后将它们乘以 𝑝。
对于每个新点，我们计算其 𝑥 坐标与 𝑦 坐标之间的比值。这两个值的商就是原始点的 ECDLP 解。
输出是：``` success! The private key is: >>>>> Extraordinarily Nice <<<<<
这个计算之所以有效，与曲线上的点数恰好为 `𝑝` 这一事实有关。该性质允许我们执行若干映射，其中最后一个映射将 𝑝-adic 数上的曲线上的点，映射为模 $p^2$ 的数。这个映射具有这样的性质：与两个原始点对应的那对数字之间的比值，恰好就是这两个点的对数结果。我们将所有这些映射视为黑盒，但在文章末尾我添加了相关数学解释的参考资料。
# ECDSA 攻击
## 签名前不对消息进行哈希
我们在签名过程中看到，首先计算消息的哈希，并使用哈希的高位进行签名计算。假设在某个签名和验证的实现中，这个哈希步骤被跳过，并且不是取哈希的高位，而是直接按原样从消息中取比特。在这样的实现中，消息中影响其签名的唯一部分就是消息的开头。换句话说，如果我们有一条消息及其签名，我们可以保留消息的开头并更改其余部分，签名仍然有效。这是一个非常简单的攻击。
例如，假设你向银行写了下面这条消息，并且没有进行哈希就对其签名：```
"Please transfer 1,000$ from my account to GitHub so that they can continue hosting awesome repositories"
银行将成功验证此消息，并执行该操作。某些...攻击者...可以创建以下消息：``` "Please transfer 1,000$ from my account to GitHub and 1,000,000$ to Eli Kaski"
并使用你刚刚创建的签名。该签名对于这条消息同样有效，银行将执行该操作。这可不妙（好吧，取决于对谁而言）。
以下代码演示了该攻击：```python
from ecdsa import SigningKey, NIST256p
signing_key = SigningKey.generate(NIST256p)
verifying_key = signing_key.verifying_key
class MyHash:
def __init__(self, data):
self.data = data
def digest(self):
return self.data
# Sign the message and verify the signature
message = "Please transfer 1,000$ to GitHub"
signature = signing_key.sign(message.encode(), hashfunc=MyHash)
assert verifying_key.verify(signature, message.encode(), hashfunc=MyHash)
# Construct an evil message and verify the original message's signature is valid for it as well
evil_message = "Please transfer 1,000$ to GitHub and 1,000,000$ to Eli Kaski"
assert verifying_key.verify(signature, evil_message.encode(), hashfunc=MyHash)
print("success!")
在此代码片段中，使用了 ecdsa 库以及一条已知曲线。我们定义了一个类，它本应实现哈希函数，但实际上并未这样做，而是让消息保持原样。因此，在对消息签名时，只会使用原始消息的前几位，而不是其哈希值的前几位。随后，消息被成功签名并验证。接着创建一条恶意消息，代码验证原始消息的签名同样匹配该恶意消息。
在这样的场景下，我们可能并未获得私钥来生成自己的新签名，但给定一个签名，只要消息以相同前缀开头，我们就可以为任意多条消息签名。
k 值作为消息签名过程的一部分，用户需要随机生成一个 𝑘 值并用它来签名消息。在不同签名中使用不同的 𝑘 值非常重要。否则，如果用户对两条已签名消息使用了相同的 𝑘 值而不是重新生成，攻击者就能计算出用户的私钥。
如前所述，在消息签名期间，用户公开发送 $r=x_1\ \ \ \ (mod\ p)$ 和 $s=k^{-1}(z+rd_A)$。假设用户对两条不同消息进行签名，对应 $𝑧_1$ 和 $𝑧_2$，并公开发送两对值 $𝑟, 𝑠_1$ 和 $𝑟, 𝑠_2$，即在两次签名中使用了相同的 𝑘 值。我们注意到：
$s_1-s_2=k^{-1}(z_1+rd_A)-k^{-1}(z_2+rd_A)=k^{-1}(z_1+rd_A-z_2-rd_A)=k^{-1}(z_1-z_2)$
由此，攻击者可以通过计算得出 𝑘 的值：
$\displaystyle k=\frac {z_1-z_2}{s_1-s_2}$
攻击者找到 𝑘 后，就可以从其中一个签名计算出用户的私钥。注意：
$r^{-1}(ks-z)=r^{-1}(kk^{-1}(z+rd_A)-z)=r^{-1}(z+rd_A-z)=r^{-1}rd_A=d_A$
给定一条消息及其签名的 𝑟、𝑠 和 𝑧 的值，以及攻击者找到的 𝑘 值，攻击者可以计算出 $d_A=r^{-1}(ks-z)$。至此，攻击者可以代表其私钥已被获取的用户，对任意消息进行签名。
以下代码片段执行此攻击：```python from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key from Crypto.Util.number import bytes_to_long, long_to_bytes from hashlib import sha256 import random
curve = curve_256 generator = generator_256 n = generator.order()
secret_key = 6743529130774090927928101169617481154782309 public_key = Public_key(generator, generator * secret_key) private_key = Private_key(public_key, secret_key)
k = random.randrange(curve.p()) message1 = "Life is like a box of chocolates." message2 = "You never know what you're gonna get." z1 = bytes_to_long(sha256(message1.encode()).digest()) z2 = bytes_to_long(sha256(message2.encode()).digest())
signature1 = private_key.sign(z1, k) signature2 = private_key.sign(z2, k)
found_k = (z1 - z2) * inverse_mod(signature1.s - signature2.s, n) % n assert k == found_k
found_key = inverse_mod(signature1.r, n) * (found_k * signature1.s - z1) % n assert found_key == secret_key print("success!") print("The secret is:", long_to_bytes(found_key).decode())
在这段代码中，使用了库 `ecdsa` 以及一条已知曲线。我们定义一个私钥，并用它对两条消息进行签名。`𝑘` 的值是随机生成的，但两条签名使用的 `𝑘` 保持不变。给定两条消息及其签名，代码执行了我们之前看到的计算来求出 `𝑘`。最后，我们利用求得的 `𝑘` 值来计算私钥，正如之前所述。输出为：```
Success!
The secret is: Mistakes were made
It is interesting to note that this attack was actually used in 2010, when Sony insecurely implemented their signing mechanism on the PlayStation console software. Sony used a static value of 𝑘 for its signatures, which allowed attackers to obtain Sony's private key using the above calculation. This led to the ability to sign any code, and make PlayStation agree to run it. Later this ability was used to install pirated and unofficial games on the console.
k 值如果用户以随机性不足的方式选择 𝑘，那么私钥就可能被发现。例如，如果攻击者知道 𝑘 处于一个非常小的取值范围内，或者 𝑘 的部分字节为攻击者所知，那么在给定一条已签名消息的情况下，攻击者就可以通过简单的暴力破解找到用户的私钥。攻击者会对不同的 𝑘 值重复执行我们在前面攻击中看到的计算，直到找到正确的值，并从中获得私钥。
为了解决这个问题，有时用户会随机生成一个值，用某个哈希函数计算其哈希值，并将结果用作 𝑘。这种方法可能会引发问题。例如，假设生成元 𝑛 的阶为 256 bit，而选定的哈希函数是 SHA-1。该函数的输出是一个 160 bit 的数字。在模 𝑛 的计算中，已知 𝑘 的值开头包含 96 个零，这意味着 𝑘 是一个相对较小的数。在这种情况下，𝑘 值被认为是 biased，并且给定几条使用同一私钥签名的消息，就可以找到该私钥。
该攻击基于一种称为格（Lattice）的代数结构。非正式地说，格可以被视为 𝑚 维空间中的一组向量，这些向量可以表示为具有整数系数的“基”向量的线性组合。数学上，如果 $\{b_1,\dots,b_d\}$ 是 $ℝ^𝑚$ 上的基向量，那么与之对应的格为 $L=$ $\{\sum_{i=1}^d a_ib_i\mid a_i \in Z\}$。在这种结构中存在一个已知问题：给定一个格的基，找出该格中存在的最短向量。在此上下文中，非正式地说，“短向量”是指其元素尽可能接近零的向量。这个问题被称为最短向量问题（Shortest Vector Problem, SVP），并且被认为是 NP 难的。存在一些算法可以解决一个类似但更简单的问题——找到一个短向量，即一个相对“接近”格中最短向量的向量。这个问题被称为最近向量问题（Closest Vector Problem, CVP），解决该问题的算法之一被称为 Lenstra-Lenstra-Lovász（LLL）算法。在此攻击中，我们将该算法用作黑盒。
给定 𝑑 条签名消息，可以构造出一个包含向量 $(𝑘_1, \dots , 𝑘_𝑑)$ 的格，该向量的每个元素都是与一条签名相对应的 𝑘 值。LLL 算法将找到该格中最短向量的近似值。由于 𝑘 的值已知是较小的，因此算法找到的短向量有很大概率至少包含一个正确的 k 元素。一旦找到正确的 𝑘，就可以像我们在前面攻击中看到的那样计算出私钥。
要构造这个格，需要定义其基向量。我在文章末尾的参考文献中附上了一个链接，指向一篇解释这些基向量如何定义的文章。从技术上讲，格的基向量可以用一个矩阵来表示，矩阵中的每一行包含一个基向量的元素。为了提高 LLL 算法的准确性，建议在该矩阵中添加两列，分别包含 𝑘 值的预期大小以及 𝑘 与 𝑛 之间比率的信息。我附上的参考文献中也解释了这一改进。以下代码片段演示了这种攻击：```python
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from Crypto.Util.number import bytes_to_long, long_to_bytes
from hashlib import sha1
import random
def build_matrix(signatures, bias, q): # M matrix should be: """ [ B 0 m'1 m'2 m'2 ... m'n 0 B/q r'1 r'2 r'3 ... r'n 0 0 0 0 q * I 0 0 ] where: m' = s^-1 * m r' = s^-1 * r """
# Construct the first 2 rows of M:
row1 = [bias, 0]
row2 = [0, bias / q]
for m, r, s in signatures:
row1.append((inverse_mod(s, q) * m) % q)
row2.append((inverse_mod(s, q) * r) % q)
top_rows = Matrix(QQ, [row1, row2])
# Construct the q*I block along with 2 columns of zeros
zero_cols = zero_matrix(QQ, len(signatures), 2)
qI = q * identity_matrix(QQ, len(signatures))
bottom_rows = block_matrix([[zero_cols, qI]])
# Combine all rows into one matrix
M = top_rows.stack(bottom_rows)
return M
def find_private_key(L, signatures, public_key): # Check if any valid k was found in L generator = public_key.generator q = generator.order() for row in L.rows(): for i in range(len(signatures)): m,r,s = signatures[i] # Skip the first two vector components we used to improve LLL possible_k = row[i+2] # LLL might have swapped the sign of the found short vectors for k in [possible_k, -possible_k]: d = inverse_mod(r,q)(ks-m) % q if d*generator == public_key.point: return d
curve = curve_256 generator = generator_256 q = int(generator_256.order())
secret_key = 1793056234309773077862125006843383726029262764680727851636 public_key = Public_key(generator, generator * secret_key) private_key = Private_key(public_key, secret_key)
messages_to_sign = [ "And then I go and spoil it all", "By saying somethin' stupid like", "I love you" ]
signatures = [] for message in messages_to_sign: message_hash = bytes_to_long(sha1(message.encode()).digest()) k = bytes_to_long(sha1(long_to_bytes(random.randrange(q))).digest()) signature = private_key.sign(message_hash, k) signatures.append((message_hash, signature.r, signature.s))
bias = 2^160 M = build_matrix(signatures, bias, q)
L = M.LLL()
found_key = find_private_key(L, signatures, public_key) assert found_key == secret_key print("success!") print("The secret is:", long_to_bytes(found_key).decode())
在这段代码片段中，使用了一条标准曲线，选择了一个私钥，并由此计算出相应的公钥。创建了3条消息，并使用3个由SHA-1哈希函数产生的随机`k`值对其签名。然后，我们按照文章中的说明，创建对应于格基的矩阵，并对其运行LLL算法。之后，我们遍历结果矩阵的各行，检查其中某一行是否包含任何`𝑘`的正确值。检查的方法是，如我们在前一次攻击中所见，从潜在的`𝑘`计算私钥，并检查所得到的密钥是否确实正确。最后，我们确保找到的私钥确实正确。输出为：```
success!
The secret is: I am Jack's broken heart
此攻击的复杂度与LLL算法的复杂度相同，即 $O(d^6\ \log^3B)$，其中 𝐵 表示 𝑘 的偏置长度（本例中为 $2^{160}$），𝑑 表示签名消息的数量（本例中为3）。问题在于，为了能够运行该攻击，至少需要多少条已签名消息。答案是
$\displaystyle d=O(\frac {\log n}{\log n-\log B})$，其中 𝑛 是生成元的阶，𝐵 是偏置。对此的解释见本文末尾我附上的参考文献中的第二个链接。
在实践中，当 𝑘 的高位比特已知，或 𝑘 的任意比特已知时，也可以运行该攻击的变体。即使只知道一个比特的值，甚至只是以超过50%的概率知道一个比特的值，也可以运行该攻击！但当然，在这些情况下，执行攻击需要更多的已签名消息。
我们看到，在签名验证过程中，签名方将值对 𝑟 和 𝑠 发送给验证方。例如，在实现HTTPS协议的浏览器中，通常会在证书中发送这对值，证书中也可能包含签名方所用曲线的数据。验证方需要确保证书中的曲线数据与事先约定的曲线一致。如果不一致，可能会产生问题。
假设在某个曲线中，Alice拥有一个私钥 $d_A$ 和对应的公钥 $𝑃_𝐴$，这意味着对于该曲线中的生成元 𝐺，有 $𝑃_𝐴 = 𝑑_𝐴𝐺$。利用私钥 $𝑑_𝐴$，Alice可以按照ECDSA协议的定义对其消息进行签名。假设验证签名的验证方也从用户处接收生成元 𝐺，但并未验证从用户处收到的生成元确实是约定好的生成元。攻击者可以将Alice的公钥点作为生成元发送，即 $𝐺^′ = 𝑃_𝐴$。攻击者将选择一个“伪造”的私钥值 $𝑑_𝐴^′ = 1$，因此显然有 $𝑃_𝐴 = 𝑑_𝐴^′𝐺^′$。这意味着攻击者可以“证明”他们拥有与Alice公钥匹配的私钥。因此，攻击者可以创建任何他们想要的消息，并用 $𝑑_𝐴^′$ 以常规方式计算该消息的值对 𝑟 和 𝑠，生成的签名将被成功验证。
直觉上，在签名验证过程中，签名方证明他们确实是公钥的“所有者”，该公钥实际上是曲线上的一个“目标”点。这是因为只有签名者知道从起始点出发需要走多少步才能到达目标点。如果验证方不验证从用户处收到的起始点确实是真正的起始点，那么攻击者可以将起始点设为目标点，并将其出发步数设为零。签名验证的其他所有部分保持不变，签名将被成功验证。这种攻击称为Curveball。
这种攻击可以通过其他值进行推广。攻击者将选择某个值 𝑥，并计算 $𝐺^′ = 𝑥𝑃_𝐴$。伪造私钥将为 $𝑑'_𝐴 = 𝑥^{−1}\ \ \ \ (mod\ n)$。那么显然有 $𝑑'_𝐴𝐺^′ = 𝑥^{−1}𝑥𝑃_𝐴 = 𝑃_𝐴$。
以下代码演示了该攻击：```python from ecdsa.ecdsa import generator_256 from Crypto.Util.number import bytes_to_long from hashlib import sha256 import random
def hash_message(message): return bytes_to_long(sha256(message.encode()).digest())
def verify(public_key, G, message, r, s): n = G.order() if r < 1 or r > n - 1 or s < 1 or s > n-1: return False hash = hash_message(message) u1 = (hash * inverse_mod(s, n)) % n u2 = (r * inverse_mod(s, n)) % n P = u1 * G + u2 * public_key return P.x() % n == r
def sign(private_key, G, message): n = G.order() k = random.randrange(n) hash = hash_message(message)
r = (k * G).x() % n
s = inverse_mod(k, n) * (hash + r * private_key) % n
return r, s
G = generator_256 n = G.order() private_key = random.randrange(n) public_key = private_key * G
message = "Let me be the one that shines with you" r, s = sign(private_key, G, message) assert verify(public_key, G, message, r, s)
x = random.randrange(n) fake_G = x * public_key fake_private_key = inverse_mod(x, n) assert fake_private_key != private_key assert fake_G != G
evil_message = "Where did I go wrong?" r, s = sign(fake_private_key, fake_G, evil_message) assert verify(public_key, fake_G, evil_message, r, s)
在这段代码中，我们选择一个已知的生成元、一个私钥和一个公钥。我们对一条消息进行签名，并确保它成功通过验证。然后我们创建一个伪造的私钥和一个伪造的生成元，使两者都与原始公钥匹配。使用伪造的密钥对一条恶意消息进行签名，最后，伪造的签名使用原始公钥成功通过验证。这段代码的问题在于，验证算法没有验证生成元 `𝐺` 是否与公钥匹配。尽管在此攻击中我们并未找到用户的私钥，但攻击者可以利用不正确的签名验证实现，创建出能够成功通过验证的签名。然而，攻击者无法创建在正确实现的签名验证中确实能够成功通过的"真实"签名。
值得注意的是，这是 Windows CryptoAPI 架构中真实存在过的一个漏洞。在负责验证证书签名的函数中，当曲线参数包含在证书本身中时，对这些参数的验证并不充分。特别是，没有检查生成元是否确实是与公钥对应的生成元。攻击者可以创建伪造的证书，这些证书因为看起来像是受信任的证书颁发机构签发的而被视为受信任。这是通过向证书中添加恶意的曲线字段，并按照我描述的方式选择生成元来实现的。该漏洞由 NSA 组织发现，于 2020 年修复，编号为 CVE-2020-0601。
# 结论
## ECDH 攻击概述
| 问题类型 | 问题 | 攻击 | 攻击原理 | 攻击复杂度 |
| ------------- | ------------- | ------------- | ------------- | ------------- |
| 选择具有不安全生成元的曲线 | 生成元 `n` 的阶太小 | 小步大步法 | 中途相遇法 | $𝑂(\sqrt n)$ |
| 选择具有不安全生成元的曲线 | 生成元 `n` 的阶是光滑数 | Pohlig-Hellman | 将 `𝑛` 分解为素因子，分别攻击每一个因子，并使用中国剩余定理组合结果 | $O(\sqrt{p_{max}})$，其中 $p_{max}$ 是 `𝑛` 分解中最大的素因子 |
| 选择具有不安全生成元的曲线 + 选择不安全的私钥 | 生成元 `n` 的阶几乎是光滑数，且私钥很小 | 改进的 Pohlig-Hellman | 将 `𝑛` 分解为素因子，丢弃过大的因子，分别攻击每一个因子，并使用中国剩余定理组合结果 | $O(\sqrt{p_{max}})$，其中 $p_{max}$ 是 `𝑛` 分解中最大的素因子 |
| ECDH 的错误实现 | 未验证点是否在曲线上 | 无效曲线攻击 | 将恶意曲线上具有小阶的点作为公钥发送，分别攻击每一个点，并使用中国剩余定理组合结果 | $𝑂(𝑛_{𝑚𝑎𝑥})$，其中 $𝑛_{𝑚𝑎𝑥}$ 是恶意点的阶中最大的阶 |
| 不安全地选择曲线参数 | 曲线是奇异曲线 | 将 ECDLP 归约为 DLP | 将点映射为数字，从而将点的加法转换为整数的乘法 | $O(\sqrt{p_{max}})$，其中 $p_{max}$ 是 $(p-1)$ 分解中最大的素因子 |
| 不安全地选择曲线参数 | 曲线是超奇异曲线 | 将 ECDLP 归约为 DLP | 将点映射为数字，从而将点的加法转换为整数的乘法 | $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$，其中 `k` 是相对于生成元的嵌入次数 |
| 不安全地选择曲线参数 | 曲线是异常曲线 | Smart 攻击 | 在曲线上的点与 `p-adic` 数域上的曲线点之间进行一系列映射，并映射回整数 | $O(1)$ |
## ECDSA 攻击概述
| 问题类型 | 问题 | 攻击 | 攻击原理 | 攻击复杂度 |
| ------------- | ------------- | ------------- | ------------- | ------------- |
| 签名和验证的错误实现 | 在签名之前不对消息进行哈希 | 在给定一条已签名消息的情况下，伪造与该签名对应的其他消息 | 保持消息前缀不变并修改其余部分 | $O(1)$ |
| 签名算法的错误使用 | 在不同的签名中重复使用相同的 `k` 值 | 找到用户的私钥 | 找到 `k` 的值，并从中计算出用户的私钥 | $O(1)$ |
| 签名算法的错误使用 | 不安全地生成 `k` 值 | 在给定若干条已签名消息的情况下，找到用户的私钥 | 将问题归约为在格中寻找短向量，找到 `k` 的值，并从中计算出用户的私钥 | $O(d^6\ \log^3B)$，其中 `B` 是 `k` 的偏差，`d`d 是已签名消息的数量 |
| 验证的错误实现 | 未验证生成元是否有效 | 伪造能够成功通过验证的签名（Curveball） | 选择与另一个用户的公钥对应的伪造生成元和私钥 | $O(1)$ |
## 针对这些攻击的防护
需要指出的是，在 ECDH 中，双方必须在协议开始时商定所使用的曲线。如果用户正在与攻击者通信，并且曲线参数是由攻击者提供的，那么攻击者就可以提供不安全的参数。结果是攻击者可以获得用户的私钥。如果用户始终使用相同的私钥，那么攻击者就可以解密该用户与任何其他用户之间的所有会话。这就是为什么在无法信任不熟悉的用户时，绝不允许他们提供曲线参数，这一点非常重要。此外，你必须确保从外部用户收到的每一个点确实位于商定的曲线上。当然，你还应确保所选曲线本身不会受到我们所见过的已知攻击之一的影响。另外，每次使用 ECDH 协议时，最好都使用一个新的私钥。
同样，在 ECDSA 中，必须注意正确实现签名和验证算法。不要跳过消息的哈希处理，在每次使用该协议时都要随机且安全地生成 `𝑘` 值，当然，在签名验证中，如果生成元是从用户那里收到的——请确保它确实是之前商定的那个生成元。
## 参考资料
- 在本文中，我使用了 Christof Paar 所著《Understanding Cryptography》一书中的图表：\
https://gnanavelrec.wordpress.com/wp-content/uploads/2019/06/2.understanding-cryptography-by-christof-paar-.pdf
- 一个展示密码学椭圆曲线外观的网站：\
https://graui.de/code/elliptic2/
- 关于椭圆曲线中加法和乘法运算的详细说明：\
https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
- 关于椭圆曲线和点的加法的入门讲座——Christof Paar：\
https://www.youtube.com/watch?v=vnpZXJL6QCQ
- 关于生成元、ECDLP、问题难度、ECDH、Double And Add 的讲座——Christof Paar：\
https://www.youtube.com/watch?v=zTt4gvuQ6sY
- 关于不同加密算法安全级别的说明：\
https://en.wikipedia.org/wiki/Security_level
- 关于 ECDH 的说明：\
https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman
- 关于 ECDSA 的说明：\
https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
- 关于 ElGamal 签名的说明：\
https://en.wikipedia.org/wiki/ElGamal_signature_scheme
- 关于中国剩余定理的说明：\
https://en.wikipedia.org/wiki/Chinese_remainder_theorem
- 关于奇异曲线的判别式与其具有二重根这一事实之间关系的说明：\
https://www.quora.com/For-an-elliptic-curve-in-the-form-Y-2-X-3+AX+B-why-is-4A-3+27B-2-neq-0-the-condition-for-non-singularity
- 一个使用小数字示例说明奇异曲线中点和数字之间映射的例子：\
https://crypto.stackexchange.com/questions/61302/how-to-solve-this-ecdlp/61434#61434
- 关于 𝑝-adic 数的说明：\
https://en.wikipedia.org/wiki/P-adic_number \
https://www.youtube.com/watch?v=3gyHKCDq1YA
- 关于 MOV 攻击背后数学原理的说明：\
https://risencrypto.github.io/WeilMOV/
- 关于 Smart 攻击背后数学原理的说明（相当复杂，你已被警告）：\
https://wstein.org/edu/2010/414/projects/novotney.pdf \
http://www.monnerat.info/publications/anomalous.pdf
- 关于基于格的攻击和 LLL 算法的说明：\
https://forum.vac.dev/t/lattice-attacks-on-ecdsa/136 \
\
该攻击基于 Joachim Breitner 和 Nadia Heninger 文章中的第 4 部分：\
https://eprint.iacr.org/2019/023.pdf
- 关于 CVP 问题的说明：\
https://en.wikipedia.org/wiki/Lattice_problem#Closest_vector_problem_(CVP)
- 关于 LLL 算法的说明：\
https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm